One-to-One and Onto Functions
The two properties a function \(f : X \to Y\) can have beyond being a function at all — injective (one-to-one) and surjective (onto) — with the proof templates for showing each and for showing its failure. Together they make a bijection, which is what inverse-functions needs. The definition of a function is in functions-on-general-sets; the lecture is 2026-09-07-functions-one-to-one-onto-inverse.
The definitions
Let \(f\) be a function, \(f : X \to Y\).
Injective function (one-to-one function): \(\forall x_1, x_2 \in X\), if \(f(x_1) = f(x_2)\) then \(x_1 = x_2\).
Surjective function (onto function): \(\forall y \in Y\), \(\exists x \in X\) such that \(f(x) = y\).
A function that is both one-to-one and onto is a bijection.
In words: one-to-one means no two inputs share an output — different inputs, different outputs. Onto means every element of the co-domain is hit — the range is the whole of \(Y\). Each name has a Latin and an English form, used interchangeably: injective / one-to-one, surjective / onto, bijective / one-to-one correspondence.
The two are about opposite ends of the arrows. One-to-one is a condition on the domain side: arrows never merge. Onto is a condition on the co-domain side: nothing is left unreached. They are independent, and all four combinations occur:
Figure 1: The four combinations, on the smallest sets that show them. Top left: one-to-one but not onto — arrows never merge, but the third dot of \(Y\) is missed. Top right: onto but not one-to-one — everything in \(Y\) is hit, but two arrows merge. Bottom left: both, a bijection — a perfect pairing. Bottom right: neither. A red ring marks the offending element of \(Y\) in each failing panel — a target that two arrows share, or a dot no arrow reaches; in the neither panel it marks one of each kind.
For finite sets the picture gives a counting fact for free: one-to-one forces \(|X| \leq |Y|\), onto forces \(|X| \geq |Y|\), and a bijection forces \(|X| = |Y|\). That is the beginning of the next topic, cardinality, where the same three facts become the definitions of \(\leq\), \(\geq\) and \(=\) for sets of any size.
On the real line
The graph versions of the two tests:
| Test on the graph | Example | |
|---|---|---|
| one-to-one | no horizontal line meets the graph twice | \(2^x\) passes; \(x^3 - x\) fails, \(x^2\) fails |
| onto \(\mathbb{R}\) | every horizontal line meets the graph at least once | \(x^3 - x\) passes; \(2^x\) fails (never \(\leq 0\)), \(x^2\) fails |
The vertical line test decides whether a curve is a function at all (functions-on-general-sets); the horizontal line test decides one-to-one.
Changing the co-domain
Onto depends on the declared co-domain, so it can be switched on by declaring a smaller one:
\[f : \mathbb{R} \to \mathbb{R}, \; f(x) = x^2 \text{ is not onto}; \qquad g : \mathbb{R} \to \mathbb{R}^{\geq 0}, \; g(x) = x^2 \text{ is onto.}\]
Same pairs, different function, because \(Y\) is part of what a function is. Any function becomes onto its own range. One-to-one, by contrast, is a fact about the pairs alone and cannot be adjusted by relabelling the co-domain — though it can be switched on by shrinking the domain, which is how \(\sqrt{\;}\) gets to be the inverse of \(x^2\) on \(\mathbb{R}^{\geq 0}\).
How to prove it
| To show \(f : X \to Y\) is … | Template |
|---|---|
| one-to-one | Suppose \(x_1, x_2 \in X\) with \(f(x_1) = f(x_2)\). … Hence \(x_1 = x_2\). \(\square\) |
| not one-to-one | Exhibit \(x_1, x_2 \in X\) with \(x_1 \neq x_2\) and \(f(x_1) = f(x_2)\). |
| onto | Let \(y \in Y\). Take \(x = \ldots\) (in terms of \(y\)). Check \(x \in X\). Check \(f(x) = y\). \(\square\) |
| not onto | Exhibit \(y \in Y\) such that \(f(x) \neq y\) for all \(x \in X\) (and say why). |
The shape follows the quantifiers (quantified-statements). One-to-one and onto are both universal statements, so proving them means starting from an arbitrary element and arguing in general; their negations are existential, so disproving means producing one witness. This is the same logic as the element method for sets (proving-set-properties), and the same warning applies: checking examples proves neither property, it can only disprove one.
One-to-one: algebra
\(g : \mathbb{Z} \to \mathbb{Z}^{\text{odd}}\), \(g(x) = 2x + 3\).
Let \(x_1, x_2 \in \mathbb{Z}\) with \(g(x_1) = g(x_2)\). Then \(2x_1 + 3 = 2x_2 + 3\), so \(2x_1 = 2x_2\), so \(x_1 = x_2\). \(\therefore g\) is one-to-one. \(\square\)
The proof is “undo the function”: peel operations off both sides until the inputs are exposed. Every step must be reversible-in-effect — dividing by 2 is fine; squaring both sides would not be, which is exactly why \(x^2\) is not one-to-one.
Onto: solve backwards, then run forwards
Same \(g\). Scratch work (not part of the proof): want \(x\) with \(2x + 3 = y\), so \(x = \frac{y - 3}{2}\).
Proof. Let \(y \in \mathbb{Z}^{\text{odd}}\). Take \(x = \frac{y-3}{2}\). Since \(y\) is odd, \(y - 3\) is even, so \(x \in \mathbb{Z}\). And \(g(x) = 2 \cdot \frac{y-3}{2} + 3 = y\). \(\therefore g\) is onto. \(\square\)
Three moves, always in this order: name the candidate, check it is in the domain, check it maps to \(y\). The middle one is where onto proofs go wrong. Here it is the only place the oddness of \(y\) is used; drop it and the same lines “prove” that \(2x + 3\) is onto all of \(\mathbb{Z}\), which is false (\(y = 4\) needs \(x = \frac{1}{2}\)).
Pairs as inputs
\(f : \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\), \(f((x,y)) = (y + 1, 2x)\).
One-to-one. Suppose \(f((x_1,y_1)) = f((x_2,y_2))\). Then \((y_1 + 1, 2x_1) = (y_2 + 1, 2x_2)\), so \(y_1 + 1 = y_2 + 1\) and \(2x_1 = 2x_2\); hence \(y_1 = y_2\) and \(x_1 = x_2\), so \((x_1,y_1) = (x_2,y_2)\). \(\square\)
Onto. Let \((a,b) \in \mathbb{R} \times \mathbb{R}\). Take \(\left(\frac{b}{2}, a - 1\right) \in \mathbb{R} \times \mathbb{R}\). Then \(f\!\left(\left(\frac{b}{2}, a-1\right)\right) = ((a-1)+1, 2 \cdot \frac{b}{2}) = (a,b)\). \(\square\)
Two ordered pairs are equal exactly when both coordinates are, so one equation of pairs is two equations of numbers, and both must be carried through. The coordinates also cross over — the output’s first entry comes from the input’s second — which is why the candidate in the onto proof has \(b\) first.
Disproofs
\(f : \mathbb{Z} - \{-1,0,1\} \to \mathbb{Z}^{>1}\), \(f(x) =\) the largest prime divisor of \(x\).
Not one-to-one: \(f(10) = 5 = f(15)\) and \(10 \neq 15\). Not onto: \(4 \in \mathbb{Z}^{>1}\), but \(4\) is not prime, so no \(x\) has \(f(x) = 4\) — the range of \(f\) is the set of primes, a proper subset of \(\mathbb{Z}^{>1}\). Both are one line, because both are witnesses.
Is it even a function?
Before either property, the candidate has to be a function. These are examples of how that fails (functions-on-general-sets):
- \(f : \mathbb{Z}^{+} \to \mathbb{Z}^{+}\), \(f(n) = \frac{(n+1)(n+3)}{3}\) — lands outside the co-domain (\(n = 1\) gives \(\frac{8}{3}\)).
- \(f : \mathbb{Q} \to \mathbb{Z}\), \(f\!\left(\frac{m}{n}\right) = m\) — one input, two values: \(f\!\left(\frac{1}{2}\right) = 1\) but \(f\!\left(\frac{2}{4}\right) = 2\), and \(\frac{1}{2} = \frac{2}{4}\). A rule that depends on how the input is written is not well defined.
- \(\{(x,y) : y^2 = x\}\) and \(\{(x,y) : x = \lvert y \rvert\}\) — one input, two values again: \((4,2)\) and \((4,-2)\); \((1,1)\) and \((1,-1)\).
A constant function (\(f(x) = 1\)) and \(f(n) = n!\) on \(\mathbb{Z}^{+}\) are functions; the constant one is neither one-to-one nor onto \(\mathbb{R}\), which makes it the fourth panel of Figure 1.
See also
- inverse-functions — what a bijection buys you
- composition-of-functions — how the two properties behave under \(g \circ f\)
- functions-on-general-sets — the definition, co-domain versus range
- counting-selections — a one-to-one function from an \(r\)-element set to an \(n\)-element set picks \(r\) different images in order, so there are \(\frac{n!}{(n-r)!}\) of them
- pigeonhole-principle — no function from a finite set to a smaller one is one-to-one, the pigeonhole principle
- quantified-statements · proof-techniques — why the templates have the shape they have
- 2026-09-07-functions-one-to-one-onto-inverse — Lecture 19
- practice-problems — §25