The Cantor–Bernstein theorem

Subpotence is reflexive and transitive (Proposition 1.12). This lesson proves that it is also antisymmetric: from an injection of $A$ into $B$ and an injection of $B$ into $A$, one can build a bijection between $A$ and $B$. The proof is constructive in the sense that it defines the bijection explicitly from the two injections, without any use of the axiom of choice. It is also a useful tool in practice: exhibiting two injections is often much easier than exhibiting a bijection.

2.1 The key lemma

The proof reduces to the case where one set is a subset of the other.

Lemma 2.1.#

Let $B \subseteq A$ be sets, and let $f : A \to B$ be injective. Then there is a bijection $h : A \to B$.

The elements of $A \setminus B$ must be sent into $B$, so they are moved by $f$. Their images may in turn be needed as images of other elements, so they are moved as well, and so on. Every other element can stay in place.

Proof of Lemma 2.1.

Define sets $C_n \subseteq A$ by induction:

$$C_0 = A \setminus B, \qquad C_{n+1} = f(C_n),$$

let $C = \bigcup_{n \in \nat} C_n$, and define $h : A \to A$ by

$$h(x) = \begin{cases} f(x) & \text{if } x \in C,\\ x & \text{if } x \notin C. \end{cases}$$

$h$ maps $A$ into $B$. If $x \in C$, then $h(x) = f(x) \in B$. If $x \notin C$, then in particular $x \notin C_0 = A \setminus B$, so $h(x) = x \in B$.

$h$ is injective. Its restriction to $C$ is $f$, which is injective, and its restriction to $A \setminus C$ is the identity. The image of $C$ is $\bigcup_n f(C_n) = \bigcup_n C_{n+1} \subseteq C$, and the image of $A \setminus C$ is $A \setminus C$. These images are disjoint, so two elements with the same image lie in the same piece, and are then equal.

$h$ is surjective onto $B$. Let $y \in B$. If $y \notin C$, then $h(y) = y$. If $y \in C$, then $y \in C_n$ for some $n$, and $n \neq 0$ since $y \in B$. So $y \in C_{m+1} = f(C_m)$ with $m = n - 1$: there is $x \in C_m \subseteq C$ with $h(x) = f(x) = y$.

Example 2.2.#

Let $A = [0, 1]$, $B = [0, 1) \subseteq A$ and $f(x) = x/2$, an injection of $A$ into $[0, \tfrac12] \subseteq B$. Then $C_0 = \{1\}$ and $C_n = \{2^{-n}\}$, so $C = \{1, \tfrac12, \tfrac14, \dots\}$. The bijection of the lemma is

$$h(x) = \begin{cases} x / 2 & \text{if } x = 2^{-n} \text{ for some } n \in \nat,\\ x & \text{otherwise.} \end{cases}$$

It shifts the sequence $1, \tfrac12, \tfrac14, \dots$ by one step, which frees the point $1$, and fixes every other point. This is the device of Exercise 1.14, applied to a copy of $\nat$ inside $[0, 1]$.

2.2 The theorem

Theorem 2.3 (Cantor–Bernstein).#

If $f : A \to B$ and $g : B \to A$ are injections, then there is a bijection between $A$ and $B$.

Proof of Theorem 2.3.

Let $A' = g(B) \subseteq A$. The map $g \circ f$ is an injection from $A$ into $A'$, so by Lemma 2.1 there is a bijection $h : A \to A'$. The map $g$, seen as a function from $B$ to $A'$, is a bijection; so $g^{-1} \circ h : A \to B$ is a bijection.

Corollary 2.4.#

If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$. Consequently, if $A \subseteq B \subseteq C$ and $|A| = |C|$, then $|A| = |B| = |C|$.

Proof of Corollary 2.4.

The first statement is a reformulation of Theorem 2.3. For the second, the inclusion gives $|B| \leq |C|$, and $|C| = |A| \leq |B|$ gives $|C| \leq |B|$.

The second statement is often used in the following form: to show that a set $B$ has the same cardinality as a set $C$, find a subset of $B$ equipotent to $C$, and an injection of $B$ into $C$.

2.3 The bijection, explicitly

Unfolding the two proofs gives a direct description of the bijection.

Proposition 2.5.#

Let $f : A \to B$ and $g : B \to A$ be injections, and let

$$C = \bigcup_{n \in \nat} (g \circ f)^n\big(A \setminus g(B)\big).$$

Then the function $\varphi : A \to B$ defined by $\varphi(x) = f(x)$ for $x \in C$, and $\varphi(x) = g^{-1}(x)$ for $x \notin C$, is a bijection.

Proof of Proposition 2.5.

In the proof of Theorem 2.3, the lemma is applied to $A' = g(B)$ and to the injection $g \circ f$. Its sets are $C_0 = A \setminus g(B)$ and $C_{n+1} = (g \circ f)(C_n)$, so their union is the set $C$ of the statement, and the bijection is $g^{-1} \circ h$, where $h(x) = g(f(x))$ for $x \in C$ and $h(x) = x$ otherwise. For $x \in C$, this gives $g^{-1}(g(f(x))) = f(x)$. For $x \notin C$, it gives $g^{-1}(x)$, which is defined since $x \notin C_0$ means $x \in g(B)$.

The set $C$ has a simple description. Assume for this paragraph that $A$ and $B$ are disjoint (otherwise, replace them by disjoint copies). Starting from $x \in A$, one can try to go backwards: if $x \in g(B)$, its parent is the unique $y \in B$ with $g(y) = x$; if $y \in f(A)$, the parent of $y$ is the unique $x' \in A$ with $f(x') = y$; and so on. Every element thus has a unique sequence of ancestors, which either stops at an element of $A \setminus g(B)$, or stops at an element of $B \setminus f(A)$, or never stops. An element $x \in A$ lies in $C$ exactly when its ancestry stops in $A \setminus g(B)$: indeed, $x \in (g \circ f)^n(A \setminus g(B))$ means that the $2n$-th ancestor of $x$ exists and lies in $A \setminus g(B)$.

So the elements of $A \cup B$ split into chains under $f$ and $g$, and the bijection pairs elements within each chain. On a chain starting in $A$, it must use $f$, since the first element has no preimage under $g$. On a chain starting in $B$, it must use $g^{-1}$, since the first element is not in the image of $f$. On a chain without a first element, which is either infinite in both directions or a finite cycle, both choices work, and the proof makes the choice $g^{-1}$.

This is the proof of Cantor–Bernstein usually attributed to Julius König (1906). The proof above, by iteration of a single injection, is essentially Dedekind’s.

2.4 The role of the axiom of choice

The proof of Cantor–Bernstein uses only definitions by induction and set formation: it is a theorem of ZF, set theory without the axiom of choice. Two related statements behave differently.

• Surjections in both directions. If there are surjections $A \to B$ and $B \to A$, are $A$ and $B$ equipotent? With the axiom of choice, yes: each surjection has a right inverse, which is an injection in the opposite direction (Remark 1.3), and Cantor–Bernstein applies. Without choice, this is not provable in ZF, if ZF is consistent; we admit this independence result (see Jech’s monograph on the axiom of choice).
• Comparability. For any two sets $A$ and $B$, is $|A| \leq |B|$ or $|B| \leq |A|$? Zermelo’s well-ordering theorem shows that this follows from the axiom of choice, and Hartogs showed in 1915 that, conversely, comparability implies the axiom of choice. We admit both results.

In this course, the sets compared are mostly sets of integers, finite objects, sequences and real numbers, for which explicit injections are available, and no use of choice is needed except where stated.

2.5 Exercises

Exercise 2.6 ★.

Use the Cantor–Bernstein theorem to show that $\nat$ and $\nat \times \nat$ are equipotent, without writing down an explicit bijection.

Solution

The map $n \mapsto (n, 0)$ is an injection $\nat \to \nat \times \nat$. Conversely, $(a, b) \mapsto 2^a 3^b$ is an injection $\nat \times \nat \to \nat$, by uniqueness of prime factorization. By Theorem 2.3, the two sets are equipotent.

Exercise 2.7 ★.#

Show that $[0, 1]$, $[0, 1)$, $(0, 1)$ and $\mathbb R$ are pairwise equipotent.

Solution

We have $(0, 1) \subseteq [0, 1) \subseteq [0, 1] \subseteq \mathbb R$, and $|(0, 1)| = |\mathbb R|$ by Example 1.6. By the second part of Corollary 2.4, applied twice, all four sets are equipotent.

Exercise 2.8 ★★.

Let $E$ be the set of even numbers, $f : \nat \to E$ given by $f(n) = 4n$, and $g : E \to \nat$ the inclusion. Compute the bijection $\varphi$ of Proposition 2.5.

Solution

Write $v(x)$ for the exponent of $2$ in $x \geq 1$. Here $\nat \setminus g(E)$ is the set of odd numbers and $g \circ f(n) = 4n$, so $C$ is the set of numbers $4^k m$ with $m$ odd, that is, the $x \geq 1$ with $v(x)$ even. Hence $\varphi(x) = 4x$ if $x \geq 1$ and $v(x)$ is even, and $\varphi(x) = x$ otherwise, that is, for $x = 0$ and for $v(x)$ odd. One checks directly that $\varphi$ is a bijection onto $E$: the even numbers $x \geq 2$ with $v(x)$ odd are fixed, together with $0$, and those with $v(x) \geq 2$ even are the images $4y$ of the $y$ with $v(y)$ even.

Exercise 2.9 ★★.

In the proof of Lemma 2.1, show that the sets $C_n$ are pairwise disjoint.

Solution

For $n \geq 1$, $C_n \subseteq f(A) \subseteq B$, so $C_n$ is disjoint from $C_0 = A \setminus B$. Suppose $C_m \cap C_n \neq \emptyset$ with $m < n$, and choose such a pair with $m$ minimal. Then $m \geq 1$ by the first remark. Let $y \in C_m \cap C_n$: there are $x \in C_{m-1}$ and $x' \in C_{n-1}$ with $f(x) = f(x') = y$, hence $x = x'$ by injectivity, and $C_{m-1} \cap C_{n-1} \neq \emptyset$, contradicting the minimality of $m$.

2.6 Notes and references

The theorem was stated by Cantor, who could prove it only using the comparability of cardinals. Dedekind found a proof in 1887 but did not publish it. Schröder published a proof in 1898 that turned out to contain a gap, and the first published correct proof, by Felix Bernstein, appeared in Borel’s Leçons sur la théorie des fonctions (1898). The proof by chains is due to Julius König. Hartogs’ theorem on comparability is proved in Jech’s monograph.

• E. Borel, Leçons sur la théorie des fonctions, Gauthier-Villars, Paris, 1898, Note I.
• J. König, Sur la théorie des ensembles, Comptes rendus de l’Académie des sciences 143 (1906), 110–112.
• F. Hartogs, Über das Problem der Wohlordnung, Mathematische Annalen 76 (1915), 438–443.
• T. Jech, The Axiom of Choice, North-Holland, 1973.