The Cantor-Bernstein-Schroeder Theorem

Statement

Theorem (Cantor-Bernstein-Schroeder): If there exist injections $f : A \hookrightarrow B$ and $g : B \hookrightarrow A$, then there exists a bijection $h : A \cong B$.

Significance

To prove $A \cong B$, we need only construct injections in both directions. The theorem guarantees a bijection exists implicitly.

Equivalent Formulation

If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

Proof Idea: The Ping-Pong Lemma

Setup

We have $f : A \to B$ injective and $g : B \to A$ injective.

Goal: Partition $A = A_0 \cup A_1$ such that $f$ bijects $A_0$ with some $B_0$ and $g^{-1}$ bijects $A_1$ with $B \setminus B_0$.

The Descending Chain Construction

Define a sequence of sets:

$A_0 = A \setminus g(B)$ $A_{n+1} = g(f(A_n))$

And let $A_{\infty} = \bigcup_{n \geq 0} A_n$.

Key Observation

• $f$ is a bijection from $A_{\infty}$ to $f(A_{\infty})$
• $g^{-1}$ is a bijection from $A \setminus A_{\infty}$ to $B \setminus f(A_{\infty})$

The Bijection

Define $h : A \to B$ by:

$h(a) = \begin{cases} f(a) & a \in A_{\infty} \\ g^{-1}(a) & a \notin A_{\infty} \end{cases}$

Well-defined: If $a \notin A_{\infty}$, then $a \in g(B)$, so $g^{-1}(a)$ exists.

Bijective: The two pieces are disjoint and $h$ is bijective on each.

Detailed Proof

Partition of $A$

Let:

• $D_0 = A \setminus \text{Im}(g)$ (elements of $A$ not in the image of $g$)
• $D_{n+1} = g(f(D_n))$ (apply $f$, then $g$)
• $D = \bigcup_{n \geq 0} D_n$

Define the Bijection

$h(a) = \begin{cases} f(a) & a \in D \\ g^{-1}(a) & a \notin D \end{cases}$

Injectivity

If $h(a_1) = h(a_2)$:

• If both in $D$: $f(a_1) = f(a_2)$, so $a_1 = a_2$ (since $f$ injective).
• If both in $A \setminus D$: $g^{-1}(a_1) = g^{-1}(a_2)$, so $a_1 = a_2$ (since $g$ injective).
• If one in $D$, one not: Let $a_1 \in D$, $a_2 \notin D$. Then $f(a_1) = g^{-1}(a_2)$, so $g(f(a_1)) = a_2 \in g(f(D)) = D \setminus D_0$. But $a_2 \notin D$. Contradiction.

Surjectivity

Let $b \in B$.

• If $b \in f(D)$: $b = f(a)$ for some $a \in D$, so $h(a) = b$.
• If $b \notin f(D)$: Then $g(b) \notin D$ (otherwise $g(b) \in D_n$ for some $n > 0$, so $b \in f(D_{n-1}) \subseteq f(D)$). Thus $h(g(b)) = g^{-1}(g(b)) = b$.

Alternative Proof Using Tarski’s Fixed Point Theorem

The theorem follows from the Knaster-Tarski fixed point theorem on the complete lattice of subsets of $A$.

The operator $\Phi(S) = A \setminus g(B \setminus f(S))$ has a fixed point $S^*$.

Then $h = f|_{S^*} \cup g^{-1}|_{A \setminus S^*}$ is the desired bijection.

Applications

$\mathbb{N} \times \mathbb{N} \cong \mathbb{N}$

• Injection $\mathbb{N} \hookrightarrow \mathbb{N} \times \mathbb{N}$: $n \mapsto (n, 0)$
• Injection $\mathbb{N} \times \mathbb{N} \hookrightarrow \mathbb{N}$: Cantor pairing $(a, b) \mapsto \frac{(a+b)(a+b+1)}{2} + b$

By CBS, $\mathbb{N} \times \mathbb{N} \cong \mathbb{N}$.

$\mathbb{R} \cong \mathcal{P}(\mathbb{N})$

• Injection $\mathbb{R} \hookrightarrow \mathcal{P}(\mathbb{N})$: send real to its binary expansion
• Injection $\mathcal{P}(\mathbb{N}) \hookrightarrow \mathbb{R}$: interpret subset as ternary expansion (0s and 2s only)

By CBS, $\mathbb{R} \cong \mathcal{P}(\mathbb{N})$.

---

Summary

• CBS: injections $A \hookrightarrow B$ and $B \hookrightarrow A$ imply $A \cong B$
• Proof partitions $A$ and uses $f$ on one part, $g^{-1}$ on the other
• Allows proving cardinality equality without explicit bijection