The Schröder-Bernstein Theorem

The Schröder-Bernstein theorem is one of the most elegant and useful results in set theory. It provides a practical way to prove that two sets have the same cardinality by showing injections in both directions, which is often easier than constructing an explicit bijection.

TheoremSchröder-Bernstein Theorem

If there exist injections $f: A \hookrightarrow B$ and $g: B \hookrightarrow A$ , then there exists a bijection $h: A \xrightarrow{\sim} B$ . Equivalently, if $|A| \leq |B|$ and $|B| \leq |A|$ , then $|A| = |B|$ .

This theorem is remarkable because it allows us to establish equipollence without finding an explicit bijection, which can be difficult for complicated sets. The proof, while not trivial, is constructive and provides a method for building the bijection.

Proof

Let $f: A \to B$ and $g: B \to A$ be injections. We will construct a bijection $h: A \to B$ .

Step 1: Partition A into layers

Define a sequence of subsets of $A$ by tracing ancestry through $g$ and $f$ :

Let $C_0 = A \setminus g[B]$ be elements of $A$ that are not in the range of $g$
For $n \geq 0$ , let $C_{n+1} = g[f[C_n]]$ be the $(n+1)$ -th generation descended from $C_0$

Define $C = \bigcup_{n=0}^\infty C_n$ to be all elements with finite ancestry.

Step 2: Define the bijection

Define $h: A \to B$ by:

h(a) = \begin{cases} f(a) & \text{if } a \in C \\ g^{-1}(a) & \text{if } a \in A \setminus C \end{cases}

Here $g^{-1}$ denotes the inverse of $g$ restricted to its range (which is an injection, hence invertible on its range).

Step 3: Verify h is well-defined

For $a \in A \setminus C$ , we claim $a \in g[B]$ , so $g^{-1}(a)$ is defined. Suppose not, i.e., $a \in C_0$ . Then $a \in C$ , contradicting $a \in A \setminus C$ . For subsequent generations, if $a \in C_n$ for any $n$ , then $a \in C$ . Thus $a \in g[B]$ .

Step 4: Verify h is injective

Suppose $h(a_1) = h(a_2)$ . We consider cases:

If both $a_1, a_2 \in C$ : Then $f(a_1) = f(a_2)$ , so $a_1 = a_2$ since $f$ is injective
If both $a_1, a_2 \in A \setminus C$ : Then $g^{-1}(a_1) = g^{-1}(a_2)$ , so $a_1 = a_2$ since $g$ is injective
If $a_1 \in C$ and $a_2 \in A \setminus C$ (or vice versa): Then $f(a_1) = g^{-1}(a_2)$ , which means $a_2 = g(f(a_1)) \in g[f[C]]$ . But elements of $g[f[C]]$ are in $C$ , contradicting $a_2 \in A \setminus C$

Step 5: Verify h is surjective

Let $b \in B$ . We must find $a \in A$ with $h(a) = b$ . Consider two cases:

If $g(b) \in C$ : Then $g(b) \in C_n$ for some $n \geq 1$ , so $g(b) \in g[f[C_{n-1}]]$ . Thus $g(b) = g(f(c))$ for some $c \in C_{n-1} \subseteq C$ . Since $g$ is injective, $b = f(c)$ . Set $a = c$ . Then $a \in C$ and $h(a) = f(a) = f(c) = b$
If $g(b) \notin C$ : Set $a = g(b) \in A \setminus C$ . Then $h(a) = g^{-1}(a) = g^{-1}(g(b)) = b$

Therefore $h$ is a bijection.

■

Remark

The proof partitions $A$ into two parts: elements with "finite ancestry" (traced back through the images of $f$ and $g$ ) and elements with "infinite ancestry." On the first part, we use $f$ ; on the second part, we use the inverse of $g$ . This clever partition ensures both injectivity and surjectivity.

ExampleApplications of Schröder-Bernstein

Countability of rationals: There are obvious injections $\mathbb{Z} \hookrightarrow \mathbb{Q} \hookrightarrow \mathbb{Z} \times \mathbb{N}$ , and $|\mathbb{Z} \times \mathbb{N}| = |\mathbb{N}|$ , so $|\mathbb{Q}| = |\mathbb{N}|$
Open intervals: The interval $(0, 1)$ injects into $\mathbb{R}$ (obviously), and $\mathbb{R}$ injects into $(0, 1)$ via $x \mapsto \frac{1}{\pi}\arctan(x) + \frac{1}{2}$ . Thus $|(0, 1)| = |\mathbb{R}|$
Power sets: For any infinite set $A$ , there is an injection $A \hookrightarrow \mathcal{P}(A)$ via $a \mapsto \{a\}$ and an injection $\mathcal{P}(A) \hookrightarrow A \times \mathcal{P}(A)$ via $X \mapsto (a_0, X)$ for a fixed $a_0 \in A$ . However, Cantor's theorem shows these cardinalities are actually different, so the hypothesis of Schröder-Bernstein fails

TheoremTrichotomy of Cardinals

For any sets $A$ and $B$ , exactly one of the following holds:

$|A| < |B|$
$|A| = |B|$
$|A| > |B|$

This is the trichotomy law for cardinals. Its proof requires the axiom of choice (or equivalent principles).

The Schröder-Bernstein theorem, combined with trichotomy, gives a complete picture of cardinality comparisons. In practice, we often use Schröder-Bernstein to avoid constructing explicit bijections.

ExampleHilbert's Hotel Paradox

David Hilbert's famous "Grand Hotel" with infinitely many rooms (numbered $1, 2, 3, \ldots$ ) illustrates Schröder-Bernstein:

The hotel is full (one guest per room)
Infinitely many new guests arrive
Solution: Move guest in room $n$ to room $2n$ , freeing up all odd-numbered rooms

This works because $\mathbb{N} \hookrightarrow \text{Even} \subseteq \mathbb{N}$ via $n \mapsto 2n$ , and $\text{Even} \hookrightarrow \mathbb{N}$ naturally. By Schröder-Bernstein, $|\text{Even}| = |\mathbb{N}|$ .

Remark

The Schröder-Bernstein theorem holds in ZF (without choice) and is strictly weaker than trichotomy, which requires AC. The theorem is also known as the Cantor-Schröder-Bernstein theorem or the Cantor-Bernstein theorem, reflecting its discoverers.

The Schröder-Bernstein theorem is indispensable in set theory and analysis. It allows us to reason about cardinalities in a flexible way, often simplifying proofs significantly. Understanding this theorem and its applications is essential for working with infinite sets.