From Two Injections to One Bijection
A bijection shows that two sets have the same cardinality. But when the sets are complicated, constructing a bijection directly can be difficult. The Cantor-Schroeder-Bernstein theorem gives a way around this: it is enough to find an injection in each direction. The proof builds a bijection by dividing one set into parts and using a different injection on each part.
Recall that a map is injective if distinct inputs have distinct outputs, and bijective if it is both injective and surjective. For an injective map \(g:B\to A\), each element of \(g(B)\) has a unique preimage in \(B\); this does not mean that \(g\) has an inverse defined on all of \(A\).
The key is to identify the part of \(A\) where it is safe to use \(f\), and to use the inverse of \(g\) on the remaining part. The alternating-chain construction specifies these parts precisely.
The Alternating-Chain Decomposition
Start with the elements of \(A\) that are not hit by \(g\). From those elements, repeatedly apply \(f\) and then \(g\). In symbols, set
Thus \(C\) consists of the starting elements and everything reached from them by repeatedly applying \(g\circ f\). The following properties explain why this decomposition works.
Proof. Since \(A_0=A\setminus g(B)\) and \(A_0\subseteq C\), any \(a\in A\setminus C\) is not in \(A_0\), so \(a\in g(B)\). This proves \(A\setminus C\subseteq g(B)\).
We next show that if \(b\in B\setminus f(C)\), then \(g(b)\notin C\). If instead \(g(b)\in C\), then \(g(b)\in A_n\) for some \(n\geq0\). It cannot belong to \(A_0\), because \(A_0\cap g(B)=\varnothing\). Thus \(n\geq1\), and \(g(b)\in A_n=g(f(A_{n-1}))\). There is then \(a\in A_{n-1}\subseteq C\) such that \(g(b)=g(f(a))\). Injectivity of \(g\) gives \(b=f(a)\), contradicting \(b\notin f(C)\). Hence \(g(b)\in A\setminus C\).
Conversely, take \(a\in A\setminus C\). The first part gives \(a=g(b)\) for some \(b\in B\). This \(b\) cannot be in \(f(C)\): if \(b=f(c)\) for some \(c\in C\), then \(a=g(f(c))\in C\), since \(c\in A_n\) for some \(n\) implies \(g(f(c))\in A_{n+1}\). Therefore \(b\in B\setminus f(C)\). We have proved both containments in \(g(B\setminus f(C))=A\setminus C\). \(\square\)
Constructing and Checking the Bijection
Because \(g\) is injective, every \(a\in g(B)\) has exactly one preimage under \(g\). The lemma shows that \(g^{-1}\) is therefore defined on all of \(A\setminus C\), and that its values there lie in \(B\setminus f(C)\). Define \(h:A\to B\) by
On \(C\), \(h\) is injective because it equals the injective map \(f\). On \(A\setminus C\), it is injective because if \(h(a_1)=h(a_2)=b\), then \(a_1=g(b)=a_2\). The disjointness of the two ranges then shows that \(h\) is injective on all of \(A\).
For surjectivity, let \(b\in B\). If \(b\in f(C)\), there is \(c\in C\) with \(b=f(c)=h(c)\). If \(b\notin f(C)\), the lemma gives \(g(b)\in A\setminus C\), and the definition gives \(h(g(b))=b\). Thus every element of \(B\) is hit, so \(h\) is surjective as well as injective. It is a bijection. If either set is empty, the assumed injections force both sets to be empty, and the unique map from the empty set to itself is a bijection. \(\square\)
Worked Example: Two Finite Sets
Let \(A=\{a,b\}\), \(B=\{x,y\}\), and define \(f(a)=x,\ f(b)=y\) and \(g(x)=b,\ g(y)=a\). Both maps are injective. Here \(g(B)=A\), so \(A_0=A\setminus g(B)=\varnothing\). Every later \(A_n\) is empty, and consequently \(C=\varnothing\).
The construction uses the inverse of \(g\) everywhere on \(A\): \(h(a)=y\) because \(g(y)=a\), and \(h(b)=x\) because \(g(x)=b\). The outputs \(x\) and \(y\) are distinct and together make up \(B\), so this particular \(h\) is a bijection. The calculation illustrates that the theorem constructs a bijection from the given injections; it does not require that the two injections be inverses of each other.
Worked Example: The Natural Numbers and an Extra Element
Let \(A=\mathbb{N}=\{1,2,\dots\}\) and \(B=\{0,1,2,\dots\}\). Define \(f:A\to B\) by \(f(n)=n\), and define \(g:B\to A\) by \(g(0)=1\) and \(g(n)=n+1\) for \(n\geq1\). Both maps are injective: \(f\) keeps distinct positive integers distinct, and \(g\) sends \(0\) to \(1\) and each positive \(n\) to a distinct integer at least \(2\).
The image \(g(B)\) is all of \(A\), since it contains \(1=g(0)\) and every \(k\geq2\) is \(g(k-1)\). Therefore \(A_0=\varnothing\), so \(C=\varnothing\). The resulting bijection uses \(g^{-1}\): it sends \(1\) to \(0\), and sends \(k\geq2\) to \(k-1\).
Check: the value \(1\) maps to \(0\), and each \(k\geq2\) maps to \(k-1\), so the outputs cover \(0,1,2,\dots\) exactly once. Equivalently, this is the inverse of the bijection \(g\), as expected when \(g(B)=A\).
Worked Example: Two Different Injections from the Natural Numbers to Themselves
Take \(A=B=\mathbb{N}\), with \(f(n)=n+1\) and \(g(n)=2n\). These are injections: \(n+1=m+1\) implies \(n=m\), and \(2n=2m\) implies \(n=m\). Neither is surjective: \(f\) misses \(1\), and \(g\) misses every odd positive integer.
Here \(g(B)\) is the set of positive even integers, so \(A_0\) is the set of positive odd integers. The next stage is \(A_1=\{2(n+1):n\text{ is positive and odd}\}=\{4,8,12,\dots\}\). Further stages continue the alternating process. For instance, \(1\in A_0\) gives \(4=g(f(1))\in A_1\), and then \(10=g(f(4))\in A_2\). The set \(C\) is the union of all these stages; in particular it contains every odd positive integer.
The theorem's map sends \(n\in C\) to \(n+1\). For \(n\notin C\), the construction sends the even integer \(n\) to its unique preimage under \(g\), namely \(n/2\). The lemma guarantees that every \(n\notin C\) is even, so this second rule is always defined. For example, \(1\in C\), so \(h(1)=2\); \(2\notin C\), so \(h(2)=1\); \(3\in C\), so \(h(3)=4\); and \(4\in C\), so \(h(4)=5\). The proof above guarantees that the full map is bijective, even though these two rules use injections that are not surjections.
A Common Pitfall: Trying to Invert an Injection
An injection has a unique inverse value only on its image. In the last example, \(f(n)=n+1\) has no preimage for \(1\), while \(g(n)=2n\) has no preimage for any odd positive integer. Therefore neither inverse can be used as a map on all of \(\mathbb{N}\). A proposed shortcut that “uses \(f\) on one part and \(g^{-1}\) on the rest” is incomplete until it proves that the rest lies in \(g(B)\) and that the two image parts do not overlap.
The alternating-chain decomposition supplies exactly those checks. Its starting set contains the elements that are not in \(g(B)\); those elements are assigned using \(f\). The lemma proves that every element outside \(C\) is in \(g(B)\), and that its image under \(g^{-1}\) lies outside \(f(C)\). Thus the two rules are defined everywhere on their respective parts and cannot produce conflicting outputs.
The theorem matters because cardinality comparisons often give injections more readily than bijections. Once injections in both directions are available, the theorem establishes equal cardinality without requiring a direct formula for a bijection in advance.
Check Your Understanding
For each question, identify which part of the construction or proof is relevant.
- Why does \(A_0=A\setminus g(B)\) imply that every element of \(A\setminus C\) belongs to \(g(B)\)?
- In the natural-number example with \(f(n)=n+1\) and \(g(n)=2n\), compute \(A_0\) and \(A_1\).
- Why must injectivity of \(g\) be used when showing that \(g(b)\in A_n\) for \(n\geq1\) forces \(b\in f(C)\)?
- Which part of the proof shows that the two rules defining \(h\) have disjoint ranges?
- If \(A=\varnothing\) and there is an injection \(g:B\to A\), what can be concluded about \(B\), and why?