# Functions

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/functions

## Mapping Rules

A **function** $f: A \to B$ assigns to **each** element of the **domain** $A$ exactly **one** element of the **codomain** $B$. The **image** (range) is the set of outputs actually hit.

Three core properties describe how functions map sets:

| Property | Definition | Key Formula / Rule |
| --- | --- | --- |
| **Injective** | One-to-one, no two inputs collide | $f(a) = f(a') \implies a = a'$ |
| **Surjective** | Onto, codomain is fully covered | $\text{Image} = B$ |
| **Bijective** | Both injective and surjective | Perfect pairing between $A$ and $B$ |

Bijections are **invertible**, possessing an inverse $f^{-1}$ that undoes the mapping. They define set cardinality, letting us compare even **infinite** sets by checking if a bijection exists between them.

## Composition and Pitfalls

Functions **compose**: given $f: A \to B$ and $g: B \to C$, the composition $g \circ f: A \to C$ applies $f$ first, then $g$. Programs are built from composed functions transforming data step-by-step.

> **Common Pitfall:** Mixing up **injective** and **surjective**, or misreading **composition order**. Injective means inputs **do not collide**; surjective means the codomain is **fully covered**. Always remember that $g \circ f$ means **apply $f$ then $g$**—the right-hand function runs first, which looks backwards until you practice it.

## Practice questions

5 of this lesson's 9 practice questions, with answers. The full set is in the app.

### 1. A hash function maps a large key space into a small one, so collisions are guaranteed. Which mathematical fact makes that inevitable?

A. Nothing inevitable, a sufficiently clever hash function avoids all collisions
B. The birthday paradox, which makes collisions likely but not certain
C. The pigeonhole principle, more keys than buckets
D. The fact that hash functions are not injective by design

**Answer:** C. The pigeonhole principle, more keys than buckets

**Why:** Infinitely many possible strings and finitely many buckets means no function can be injective, collisions are a theorem, not a defect. That is why every hash table ships with a resolution strategy, and why the design goal is spreading keys evenly rather than the impossible one of avoiding collisions.

Page: https://tryals.app/practice/computer-science-i/functions/a-hash-function-maps-a-large-key-space-into-a-small-one-so

### 2. Each option lists a set of ordered pairs from {1, 2, 3} to {a, b}. Select every one that is a function on the whole of {1, 2, 3}.

A. {(1,b), (2,b), (3,b)}
B. {(1,a), (1,b), (2,a), (3,b)}
C. {(1,a), (2,b)}
D. {(1,a), (2,a), (3,b)}
E. {(1,a), (2,b), (3,a)}

**Answer:** A. {(1,b), (2,b), (3,b)}; D. {(1,a), (2,a), (3,b)}; E. {(1,a), (2,b), (3,a)}

**Why:** Options 1, 3 and 5 assign exactly one output to each of 1, 2 and 3. Option 2 gives 1 two outputs, so it is a relation but not a function; option 3 leaves 3 unassigned, so it is not defined on the whole domain. Several inputs sharing one output is perfectly allowed, that only costs injectivity, not functionhood.

Page: https://tryals.app/practice/computer-science-i/functions/each-option-lists-a-set-of-ordered-pairs-from-1-2-3-to-a-b

### 3. Order the steps of evaluating the composition h after g after f, applied to an input x.

**Answer:**

1. Apply f to x
2. Apply g to the result
3. Apply h to that result
4. Read off the final value

**Why:** The innermost function runs first and each result feeds the next, so the evaluation runs right to left through the written expression. This is exactly how a program built from a chain of transformations executes, which is why composition is the central idea behind pipelines of functions in computing.

Page: https://tryals.app/practice/computer-science-i/functions/order-the-steps-of-evaluating-the-composition-h-after-g-after-f

### 4. A function has an inverse exactly when it is bijective. Why do both injectivity and surjectivity turn out to be necessary?

A. Because only bijective functions can be computed, and an inverse must be computable.
B. Because an inverse must be a function on the whole codomain.
C. Because injectivity guarantees the inverse exists and surjectivity guarantees it is continuous.
D. Because bijectivity is the definition of having an inverse, so the question is circular.

**Answer:** B. Because an inverse must be a function on the whole codomain.

**Why:** The two conditions rule out the two ways an inverse fails to be a function: without injectivity the inverse of 4 must be both 2 and −2, and without surjectivity it is undefined somewhere in the codomain. Which is why restricting a domain manufactures an inverse, x² on the non-negatives is bijective, and every inverse trigonometric function is defined exactly this way.

Page: https://tryals.app/practice/computer-science-i/functions/a-function-has-an-inverse-exactly-when-it-is-bijective-why-do-both

### 5. Sort each description by the property of a function it is describing.

**Answer:**

- A statement about injectivity: No two different inputs share an output, If f(a) equals f(b) then a equals b, There are no collisions between inputs
- A statement about surjectivity: Every element of the codomain is hit by some input, The image is the whole of the codomain, Nothing in the codomain is left uncovered

**Why:** Injectivity restricts the inputs, distinct inputs must give distinct outputs, so nothing collides. Surjectivity restricts the codomain, nothing may be left out, so the image fills it. A function can have either without the other, and a bijection is precisely one that has both, which is what makes it invertible.

Page: https://tryals.app/practice/computer-science-i/functions/sort-each-description-by-the-property-of-a-function-it-is-describing