Comparing Sets Without Constructing a Bijection
A bijection gives a precise test that two sets have the same cardinality: it matches every element of one set with exactly one element of the other. But sometimes the question is only whether one set is no larger than another. An injection can answer that question by placing a distinct image in the second set for every element of the first. A surjection provides a related comparison in the opposite direction: every element of its codomain has at least one preimage. Turning that observation into an injection requires choosing one preimage for each codomain element, a point that matters for arbitrary sets.
Let \(X\) and \(Y\) be sets. A function \(f:X\to Y\) is injective if \(f(x_1)=f(x_2)\) implies \(x_1=x_2\). It is surjective if for every \(y\in Y\) there is some \(x\in X\) with \(f(x)=y\). It is a bijection if it is both injective and surjective. We use the notation \(|X|\le |Y|\) to mean that there exists an injection from \(X\) into \(Y\). Thus this notation defines a comparison of cardinalities; it does not require that the sets be finite.
What an Injection Guarantees
Proof. By definition, every element of \(i(X)\) has the form \(i(x)\) for some \(x\in X\), so the function \(i:X\to i(X)\) is surjective. It is injective because \(i:X\to Y\) is injective: if \(i(x_1)=i(x_2)\) as elements of \(i(X)\), then \(x_1=x_2\). Therefore \(i:X\to i(X)\) is a bijection. This argument also covers \(X=\varnothing\): its image is empty, and the unique function from the empty set to itself is a bijection. \(\square\)
This theorem explains why injections are suitable for comparing sizes. They do not have to use every point of the target set; their image is simply a subset of it. A surjection has a different guarantee: it uses every point of its target, but some points may have several preimages.
Worked Example: An Injection into the Natural Numbers
Let \(E=\{2,4,6,\dots\}\), the set of positive even natural numbers, and define \(i:\mathbb{N}\to\mathbb{N}\) by \(i(n)=2n\). We check that this is an injection and identify its image.
If \(i(m)=i(n)\), then \(2m=2n\). Dividing both sides by \(2\) gives \(m=n\), so \(i\) is injective. For \(n=1,2,3,4\), the values are \(i(1)=2\), \(i(2)=4\), \(i(3)=6\), and \(i(4)=8\). Every value is a positive even number. Conversely, if \(e\in E\), then \(e=2k\) for some \(k\in\mathbb{N}\), and \(i(k)=e\). Hence \(i(\mathbb{N})=E\).
Check: \(i(4)=2\cdot4=8\), which lies in \(E\). The map is not surjective onto \(\mathbb{N}\), since \(1\in\mathbb{N}\) but \(2n=1\) has no solution \(n\in\mathbb{N}\). Thus the injection compares \(\mathbb{N}\) with \(\mathbb{N}\) by placing its image in the proper subset \(E\), without itself being onto \(\mathbb{N}\).
Turning a Surjection into an Injection
If \(f:X\to Y\) is surjective, then each \(y\in Y\) has a nonempty set of preimages, called its fiber: \[ f^{-1}(\{y\})=\{x\in X:f(x)=y\}. \] To define a function from \(Y\) to \(X\), one can choose an element of each fiber. The selected elements must be distinct: if the same \(x\) were selected for \(y_1\) and \(y_2\), then \(f(x)=y_1\) and \(f(x)=y_2\), forcing \(y_1=y_2\).
Proof. For each \(y\in Y\), surjectivity says that the fiber \(f^{-1}(\{y\})\) is nonempty. The axiom of choice, applied to the family of these nonempty fibers indexed by \(Y\), gives a choice function \(s\) with \(s(y)\in f^{-1}(\{y\})\) for every \(y\in Y\). By membership in that fiber, \(f(s(y))=y\). If \(s(y_1)=s(y_2)\), applying \(f\) to both sides gives \(y_1=y_2\). Thus \(s\) is injective. If \(Y=\varnothing\), surjectivity is possible only when \(X=\varnothing\); the unique function \(\varnothing\to\varnothing\) is then an injective section, and the empty family of fibers requires no choices. \(\square\)
The choice assumption is explicit because a surjection supplies nonempty fibers, but does not in general specify which element of each fiber to select. In many concrete examples, the fibers have an evident representative—for instance, the least natural number in each fiber. In those examples, the section can be constructed directly without invoking the axiom of choice. The theorem’s general statement for arbitrary sets uses choice.
Worked Example: A Surjection from the Natural Numbers to Themselves
Define \(f:\mathbb{N}\to\mathbb{N}\) by \[ f(2k-1)=k,\qquad f(2k)=k\qquad(k\in\mathbb{N}). \] Every natural number is either odd, of the form \(2k-1\), or even, of the form \(2k\), so these rules define \(f\) on all of \(\mathbb{N}\).
The first values are \(f(1)=1\), \(f(2)=1\), \(f(3)=2\), \(f(4)=2\), \(f(5)=3\), and \(f(6)=3\). For any \(k\in\mathbb{N}\), the input \(2k-1\) satisfies \(f(2k-1)=k\). Therefore every \(k\) is hit, and \(f\) is surjective. For example, the preimages of \(2\) include \(3\) and \(4\).
Choose the odd preimage of each output by defining \(s(k)=2k-1\). Then \[ f(s(k))=f(2k-1)=k \] for every \(k\in\mathbb{N}\). If \(s(k_1)=s(k_2)\), then \(2k_1-1=2k_2-1\), so \(2k_1=2k_2\), and therefore \(k_1=k_2\). Thus \(s\) is an injection. Check: \(s(3)=2\cdot3-1=5\), and the defining rule gives \(f(5)=f(2\cdot3-1)=3\), as required.
Worked Example: Choosing Least Preimages
Let \(g:\mathbb{N}\to\{a,b,c\}\) be defined by the repeating rules \[ g(3k-2)=a,\qquad g(3k-1)=b,\qquad g(3k)=c\qquad(k\in\mathbb{N}). \] The first six values are \(g(1)=a\), \(g(2)=b\), \(g(3)=c\), \(g(4)=a\), \(g(5)=b\), and \(g(6)=c\). Each of \(a,b,c\) occurs, so \(g\) is surjective.
Define \(t:\{a,b,c\}\to\mathbb{N}\) by \(t(a)=1\), \(t(b)=2\), and \(t(c)=3\). These are the least natural-number preimages: \(g(1)=a\), \(g(2)=b\), and \(g(3)=c\). Hence \(g(t(a))=a\), \(g(t(b))=b\), and \(g(t(c))=c\). The values \(1,2,3\) are distinct, so \(t\) is injective.
Check: for the point \(c\), \(t(c)=3\) and \(g(t(c))=g(3)=c\). This verifies the section identity for that point as well as illustrating how a specified choice—here, the least preimage—avoids any ambiguity.
A Common Mistake: Reversing a Surjection
A surjection need not have an inverse function. In the natural-number example, \(f(1)=1\) and \(f(2)=1\), although \(1\ne2\). If one tries to define an inverse by sending \(1\) back to its preimage, there are at least two candidates, \(1\) and \(2\). So the inverse rule does not specify a unique output and is not a function.
The correct construction is not to reverse every pair in the graph of \(f\), but to select one preimage for each point. For example, the rule \(s(k)=2k-1\) makes one consistent selection and satisfies \(f(s(k))=k\). It also gives an injection. Confusing a section with an inverse would lead to the incorrect claim that a surjection must be injective. The explicit calculation \(f(1)=f(2)=1\) disproves that claim.
| Map type | What is guaranteed? | How it compares sets |
|---|---|---|
| Injection \(X\to Y\) | Distinct points of \(X\) have distinct images in \(Y\) | \(|X|\le |Y|\), by definition |
| Surjection \(X\to Y\) | Every point of \(Y\) has at least one preimage in \(X\) | With choice, select preimages to obtain \(|Y|\le |X|\) |
| Bijection \(X\to Y\) | Every point of \(Y\) has exactly one preimage | \(X\) and \(Y\) have equal cardinality |
These comparisons are useful even when no bijection has been constructed. An injection gives a direct way to place one set inside another; a surjection, together with a choice of representatives, gives an injection in the reverse direction. Having injections both ways is not, by itself, a bijection. The theorem that draws a conclusion from injections in both directions is a separate result.
Check Your Understanding
For each question, distinguish what the definition gives from what requires an additional construction.
- Show that the map \(h:\mathbb{N}\to\mathbb{N}\) given by \(h(n)=3n\) is injective and determine whether it is surjective.
- For the map \(f\) in the natural-number example, list the preimages of \(2\). Why does this prevent \(f\) from having an inverse function?
- Suppose \(i:X\to Y\) is injective. Explain why \(i:X\to i(X)\) is a bijection, including when \(X=\varnothing\).
- State precisely where the axiom of choice enters the proof that a surjection \(X\to Y\) yields an injection \(Y\to X\).
- Give a surjection from \(\mathbb{N}\) onto \(\{a,b\}\) and define an injection from \(\{a,b\}\) into \(\mathbb{N}\) by choosing one preimage of each point.