One-to-One and Onto

Two questions you can always ask of a function: "do different inputs always give different outputs?" and "does every potential output actually get hit?" The first is injectivity; the second is surjectivity. Both questions are independently interesting, and a function answering "yes" to both — a bijection — is the formal definition of "the two sets are the same size." Bijections are how Cantor proved $|\mathbb{Q}| = |\mathbb{N}|$ and $|\mathbb{R}| > |\mathbb{N}|$; they are also how cryptographic ciphers (a bijection encrypts and decrypts) and lossless compression (a bijection between raw and compressed data) are built. This section gives you the proof patterns for both properties.

Injective (one-to-one)

A function $f: A \to B$ is injective if distinct inputs give distinct outputs:

(Contrapositive: $a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$.) To prove injectivity, assume $f(a_1) = f(a_2)$ and derive $a_1 = a_2$. To disprove it, exhibit two distinct inputs with the same output.

Surjective (onto)

A function $f: A \to B$ is surjective if every codomain element is hit:

Equivalently, $\text{Ran}(f) = B$. To prove surjectivity, take an arbitrary $b \in B$ and produce an $a \in A$ with $f(a) = b$. To disprove it, find a single $b \in B$ with no preimage.

Bijective

A function is bijective if it is both injective and surjective. Bijections pair the elements of $A$ perfectly with the elements of $B$ — this is the precise meaning of "$A$ and $B$ have the same cardinality."

Pause and think: $f: \mathbb{Z} \to \mathbb{Z},, f(n) = 2n$. Is it injective? Surjective? If you change the codomain to "even integers," does surjectivity status change?

Try it

• Predict, then prove: $f: \mathbb{R} \to \mathbb{R},, f(x) = 3x - 5$ is bijective.
• Show by counterexample that $g: \mathbb{R} \to \mathbb{R},, g(x) = x^2$ is neither injective nor surjective. What if we restrict the domain to $[0, \infty)$ and the codomain to $[0, \infty)$?
• Use the widget to build an injective-but-not-surjective function from ${1, 2}$ to ${a, b, c}$.
• Prove: if $f$ and $g$ are both injective, then $g \circ f$ is injective.
• Find a function $f: \mathbb{N} \to \mathbb{N}$ that is surjective but not injective.

A trap to watch for

To disprove injectivity you need two distinct inputs giving the same output — not just one repeated output. Writing "$g(2) = 4$ shows $g(x) = x^2$ is not injective" is incomplete; you need the second witness, e.g. "$g(-2) = 4$ as well, and $2 \neq -2$." Similarly for surjectivity: producing one preimage doesn’t prove a function is onto — you need to argue that every codomain element has a preimage.

What you now know

You can prove or disprove injectivity by the assume-equal-and-conclude-equal pattern, prove or disprove surjectivity by constructing or blocking preimages, and recognise bijections as the formal version of "same cardinality." Section 5.3 puts these properties to work: a function is invertible iff it is bijective.

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §5.2.
• Hammack, R. (2018). Book of Proof, ch. 12.
• Halmos, P. R. (1960). Naive Set Theory. Springer, §8-9.
• Cantor, G. (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre." Jahresbericht der DMV 1, 75-78 (the diagonal argument).
• Katz, J., Lindell, Y. (2014). Introduction to Modern Cryptography (2nd ed.). CRC Press, ch. 6 (hash functions and collision resistance).