Surjective Functions

Surjectivity is a load-bearing concept far beyond pure set theory. In Comparing Cardinalities, the existence of a surjection $f: A \to B$ (with $A$ nonempty) is used to show $|B| \leq |A|$, dual to how injections show $|A| \leq |B|$ — the Cantor–Schröder–Bernstein circle of ideas depends on both notions working together. In the theory of Bijections and Inverse Functions, surjectivity is exactly half of what is needed for a function to admit a genuine two-sided inverse: a function has an inverse function precisely when it is both injective and surjective. In linear algebra, a linear map $T : V \to W$ between vector spaces is surjective exactly when its image equals all of $W$, which by the rank–nullity theorem constrains dimensions: if $\dim V < \dim W$ then no linear map $V \to W$ can be surjective. In group theory, surjective homomorphisms (epimorphisms) $\varphi : G \to H$ let one identify $H$ with a quotient $G/\ker\varphi$ via the First Isomorphism Theorem — surjectivity is precisely what guarantees no part of $H$ is left outside the image. In real analysis, the Intermediate Value Theorem is essentially a surjectivity statement: a continuous function on an interval that takes values $f(a)$ and $f(b)$ hits every value in between, making it surjective onto that sub-interval. In cryptography, hash functions are deliberately designed to be far from surjective onto their full theoretical output space in a controlled way, and the study of collision resistance is closely tied to failures of injectivity while surjectivity-like "coverage" properties matter for uniform output distribution. In computer science and databases, a surjective mapping from records to keys ensures no key-space value is "wasted" or unreachable, relevant to hashing schemes and enumerations. In statistics, surjective parameter maps in statistical models ensure that the full range of a statistic is achievable, which matters for identifiability and for constructing confidence procedures that cover the entire parameter space.

Ask the tutor: Can you show me why a surjection between finite sets of equal size is automatically injective, using the pigeonhole principle?

Picture a function as an arrow diagram: dots on the left representing the domain $A$, dots on the right representing the codomain $B$, and an arrow from each $a \in A$ to its image $f(a) \in B$. Surjectivity says that every dot on the right has at least one arrow pointing into it. It says nothing about how many arrows land on each dot — some elements of $B$ might receive two, three, or infinitely many arrows. All that matters is that no dot on the right is left unvisited. This is why surjectivity is fundamentally a statement about coverage, not about counting or matching one-to-one. It is the "dual" notion to injectivity, which forbids two arrows from the left landing on the same dot. A function can be surjective without being injective (many arrows piling onto one dot is fine, as long as every dot gets at least one), and it can be injective without being surjective (each dot gets at most one arrow, but some dots on the right may get none).

The second picture below shows the same rule, $f(x) = x^2$ on real numbers, behaving differently depending on the declared codomain — the crux of why codomain-checking is the whole game.

The technique used in the forward direction of Part 1, and throughout surjectivity proofs generally, is called codomain-chasing: fix an arbitrary target element, and either exhibit an explicit domain element mapping to it, or prove one must exist.

Example 1 — an explicit, asymmetric algebraic surjection. Let $f : \mathbb{R} \to \mathbb{R}$ be defined by

Claim: $f$ is surjective. Proof. Let $y \in \mathbb{R}$ be arbitrary; we must find $x \in \mathbb{R}$ with $f(x) = y$. Solve the equation directly:

Since the real cube root function $t \mapsto \sqrt[3]{t}$ is defined for every real number $t$ (unlike the square root, cube root has no domain restriction, because odd-degree real polynomials are surjective by the Intermediate Value Theorem applied to $t^3$, which is unbounded above and below and continuous), the expression $x = \sqrt[3]{(y+2)/5}$ is a well-defined real number for every real $y$. We verify this $x$ actually works: substituting back,

So $f(x) = y$ exactly, as required. Since $y \in \mathbb{R}$ was arbitrary, $f$ is surjective. $\checkmark$ Note how this differs from injectivity proofs: here we did not merely manipulate an equation $f(x_1) = f(x_2)$ — we solved for $x$ in terms of $y$ and verified the solution lies in the domain. This constructive solving is the hallmark of a surjectivity proof when an explicit inverse formula is available.

Example 2 — a surjection that is not injective, checked via range computation. Let $A = \{-3, -2, -1, 0, 1, 2, 3\}$ and let $B = \{0, 1, 4, 9\}$. Define $f : A \to B$ by $f(n) = n^2$. Claim: $f$ is well-defined and surjective, but not injective. Well-definedness check. We must confirm $f(n) \in B$ for every $n \in A$:

Every one of these values, $\{9,4,1,0\}$, lies in $B = \{0,1,4,9\}$, so $f$ is indeed a function from $A$ into $B$. Surjectivity check. We compute the range directly and compare to $B$:

By Range–Codomain Characterization of Surjectivity (Part 1 above), since $\operatorname{ran}(f) = B$, the function $f$ is surjective. Concretely, exhibiting a preimage for each element of $B$: $0 = f(0)$, $1 = f(1)$, $4 = f(2)$, $9 = f(3)$. Failure of injectivity. Note $f(-1) = 1 = f(1)$ but $-1 \neq 1$, so $f$ is not injective. This confirms surjectivity is logically independent of injectivity: this $f$ has every codomain element hit (some multiple times) without being one-to-one. A cautionary variant. Now consider the same rule $f(n) = n^2$ but with enlarged codomain $B' = \{0, 1, 4, 9, 16\}$. Recomputing, $\operatorname{ran}(f)$ is still $\{0,1,4,9\}$ (since $A$ has not changed), but now $\operatorname{ran}(f) = \{0,1,4,9\} \subsetneq \{0,1,4,9,16\} = B'$. So $f : A \to B'$ with the identical rule is not surjective — the value $16$ has no preimage in $A$. This illustrates precisely why the codomain must be checked, not just the formula.