Two questions about any function come up again and again: does it ever send two inputs to the same place, and does it reach everything in its codomain? The answers decide whether the function can be undone, and they power many counting arguments.
Key idea
$f : A \to B$ is one-to-one (injective) when different inputs always give different outputs: $f(a_{1}) = f(a_{2})$ implies $a_{1} = a_{2}$. It is onto (surjective) when every element of $B$ is an output: for every $b \in B$ there is an $a \in A$ with $f(a) = b$. A function that is both is a bijection.
Why it works
In an arrow diagram: one-to-one means no dot of $B$ receives two arrows; onto means every dot of $B$ receives at least one. For finite sets this gives a size check. A one-to-one function needs at least as many outputs as inputs, so $|A| \le |B|$; an onto function needs enough inputs to cover the outputs, so $|A| \ge |B|$; and a bijection forces $|A| = |B|$. Both properties depend on the domain and codomain, not just the formula.
| $f(x) = x^{2}$ | one-to-one? | onto? |
|---|---|---|
| $\mathbb{R} \to \mathbb{R}$ | no: $f(-1) = f(1)$ | no: $-1$ is never reached |
| $\mathbb{R} \to [0, \infty)$ | no | yes |
| $[0, \infty) \to \mathbb{R}$ | yes | no |
| $[0, \infty) \to [0, \infty)$ | yes | yes: a bijection |
Worked examples
Worked example: Proving one-to-one, disproving onto
Let $f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n + 1$. Is $f$ one-to-one? Onto?
- One-to-one: suppose $f(a) = f(b)$. Then $2a + 1 = 2b + 1$, so $2a = 2b$ and $a = b$. Yes.
- Onto: is $2$ an output? $2n + 1 = 2$ gives $n = \frac{1}{2}$, not an integer. So $2$ is never reached: not onto.
- Over the real numbers, $f(x) = 2x + 1$ is onto ($x = \frac{y - 1}{2}$), so the same formula is a bijection $\mathbb{R} \to \mathbb{R}$.
Answer: One-to-one, not onto
Worked example: Counting one-to-one functions
How many one-to-one functions are there from a $3$-element set to a $5$-element set?
- The first input has $5$ choices of output.
- The second must avoid the first output: $4$ choices. The third: $3$ choices.
- $5 \cdot 4 \cdot 3 = 60$, out of $5^{3} = 125$ functions in all.
Answer: $60$
Common mistake
Deciding without looking at the domain and codomain. "Is $x^{2}$ one-to-one?" has no answer until you know the sets: the table above shows all four combinations happening. Check: to show "not one-to-one," name two inputs with the same output; to show "not onto," name an element of the codomain that no input reaches.