The Schroeder-Bernstein Theorem

The theorem is the standard tool throughout mathematics whenever one wants to show two sets have the same cardinality but a direct bijection is inconvenient to write down. In real analysis, it is the cleanest route to showing $|(0,1)| = |[0,1]| = |\mathbb{R}|$ and more generally that all nondegenerate intervals of $\mathbb{R}$ are equinumerous, feeding directly into discussions of Uncountable Sets and Cantor's Diagonal Argument where one needs to know the continuum has a single well-defined cardinality $\mathfrak{c}$ regardless of which interval or interval-type representative is used. In set theory and logic, Schröder–Bernstein is precisely what upgrades the preorder $\preceq$ on cardinalities into the partial order underlying Cardinal Arithmetic and the Power Set, where facts like $2^{|A|} = |\mathcal{P}(A)|$ and Cantor's theorem $|A| < |\mathcal{P}(A)|$ rely on having a clean, antisymmetric notion of cardinal comparison to state strict inequality meaningfully. In computer science, the theorem underlies arguments about the equivalence of data representations: showing two encodings of the same information (say, two different ways of serializing trees, or two numbering schemes for pairs of naturals as in the first worked example) have "the same information content" often reduces to producing injections each way rather than a single clean bijection, especially when the encodings are structurally very different. In descriptive set theory and computability theory, Borel and computable equivalents of Schröder–Bernstein (with "injection" replaced by "Borel injection" or "computable injection") are active tools for comparing the complexity of classification problems. In combinatorics, the theorem justifies "bijective-style" cardinality arguments even when only injections are visible, for instance comparing the sizes of two families of combinatorial objects (partitions, lattice paths, tilings) by exhibiting injections in both directions when a direct bijection is elusive — a technique sometimes called the "Schröder–Bernstein trick" in enumerative proofs.

Ask the tutor: Can you walk through why the backward-chain construction never gets stuck in a contradiction — that is, why every element really does fall into exactly one of the three types?

The Schröder–Bernstein Theorem

Think of $f$ as embedding a copy of $A$ inside $B$, and $g$ as embedding a copy of $B$ inside $A$. Composing gives an injection $g\circ f: A\to A$ that embeds $A$ into itself, possibly missing some points of $A$ (those never hit by $g$). The same happens on the $B$ side. Naively one might hope $f$ itself is already a bijection, but there is no reason for that — $f$ may miss huge parts of $B$, with those gaps only reachable via $g^{-1}$. The resolution is to sort every point of $A$ and every point of $B$ into one of three types of infinite (or finite) backward trajectories, obtained by alternately undoing $g$ and $f$: keep pulling a point back along $g^{-1}$ then $f^{-1}$ then $g^{-1}$, etc., as long as those preimages exist.

• Trajectories that terminate in $A$ (an element of $A$ with no $g$-preimage in $B$, or rather whose chain traced backward dies at a point in $A$ not in the image of $g$): call these $A$-stoppers.
• Trajectories that terminate in $B$: call these $B$-stoppers.
• Trajectories that never terminate (they extend infinitely backward, or loop): call these infinite/cyclic chains.

On $A$-stopper chains, $f$ turns out to biject the $A$-part onto the $B$-part of the chain. On $B$-stopper chains and infinite chains, $g^{-1}$ (equivalently $g$ restricted the other way) does the job. Gluing these three pieces together yields a single bijection $A\to B$.

Example 1: $|\mathbb{N}| = |\mathbb{N}\times\mathbb{N}|$ via two asymmetric injections, no explicit pairing function needed. Let $A=\mathbb{N} = \{0,1,2,\dots\}$ and $B = \mathbb{N}\times\mathbb{N}$. We build two injections that are not mirror images of each other, then apply Schröder–Bernstein rather than writing down the classical Cantor pairing bijection directly. Define $f: \mathbb{N} \to \mathbb{N}\times\mathbb{N}$ by

This is injective: if $f(n_1)=f(n_2)$ then $(n_1,0)=(n_2,0)$ forces $n_1=n_2$. Define $g: \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ by

This is injective by uniqueness of prime factorization: if $2^{m_1}3^{n_1} = 2^{m_2}3^{n_2}$, comparing exponents of the primes $2$ and $3$ in each factorization forces $m_1=m_2$ and $n_1=n_2$. Both $f$ and $g$ are highly asymmetric — $f$ hits only pairs with second coordinate $0$, and $g$ hits only numbers of the form $2^m3^n$ (missing, e.g., $5$, $6$, $7$, $10$, and most naturals). Neither is a bijection on its own. Schröder–Bernstein guarantees a bijection $h:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ exists regardless. Let's trace the chain-classification concretely for a few elements to see the machinery work.

• Take $b = (1,1) \in B$. Does $b$ have an $f$-preimage? $f$'s image is $\{(n,0): n\in\mathbb{N}\}$, and $(1,1)$ is not of that form, so $b$ has no $f$-preimage. Hence the chain starting at $(1,1)$ terminates immediately at $(1,1)\in B$: this is a $B$-stopper, so $(1,1) \in B_B$.
• By Step 4 of the proof, we then use $g^{-1}$ near this element: $g(1,1) = 2^1 3^1 = 6 \in A_B \subset \mathbb{N}$, and indeed $h(6) := (g|_{B_B})^{-1}(6) = (1,1)$ provided $6$'s chain is confirmed type $B$ (traced backward: $6 = g(1,1)$, and $(1,1)$ has no $f$-preimage as shown, so the chain from $6$ is $6 \to (1,1) \to$ stop, terminating in $B$; type $B$ confirmed).
• Now take $a = 5 \in A$. Trace backward: does $5$ have a $g$-preimage? We'd need $2^m 3^n = 5$, impossible since $5$ is neither a power of $2$ times a power of $3$ (it's prime, not $2$ or $3$). So the chain starting at $5$ terminates immediately at $5 \in A$: an $A$-stopper, type $A$. By Step 3, $h(5) := f(5) = (5,0)$.
• Take $a = 0$: does $0$ have a $g$-preimage, i.e. is $0 = 2^m3^n$ for some $m,n\ge0$? No, since $2^m3^n \ge 1$ always. So $0$ is an $A$-stopper too, and $h(0) = f(0) = (0,0)$.
• Take $a=12 = 2^2\cdot 3 = g(2,1)$: it does have a $g$-preimage $(2,1)$. Continue the chain backward from $(2,1)$: does $(2,1)$ have an $f$-preimage? Only pairs $(n,0)$ are in $f$'s image, and $(2,1)$ has second coordinate $1\ne0$, so no. Chain: $12 \to (2,1) \to$ stop in $B$. Type $B$, so $h(12) = (g|_{B_B})^{-1}(12) = (2,1)$.

This example shows the theorem is not just an abstract existence claim — the chain-tracing algorithm is fully explicit and computable here, even though $f,g$ were chosen with very different "shapes."

Example 2: $|(0,1)| = |[0,1]|$, a case with genuinely infinite chains. Let $A = (0,1)$ and $B=[0,1]$. Define

(the inclusion, trivially injective), and

which is injective since it is a strictly increasing affine map ($g(y_1)=g(y_2) \Rightarrow y_1=y_2$ directly from the formula). Note $f$ and $g$ are deliberately asymmetric in construction — one is the identity inclusion, the other a nontrivial affine contraction — unlike a "symmetric" pair such as $f(x)=x$, $g(y)=y$ which wouldn't even be well typed here since $(0,1)\ne[0,1]$. Trace chains. Consider $y=1 \in B=[0,1]$. Is $1$ in the image of $f$? Image of $f$ is $(0,1)$, and $1 \notin (0,1)$, so $1$ has no $f$-preimage: chain stops immediately at $1$, type $B$. Consider $y = 0 \in B$. Same reasoning: $0 \notin (0,1) = \mathrm{im}(f)$, so $0$ has no $f$-preimage. Type $B$ as well. Now trace $g(1) = \frac{1+1}{4} = \frac12 \in A$. Does $\frac12$ have a $g$-preimage in $B$? We need $y$ with $\frac{y+1}{4} = \frac12$, i.e. $y = 1$. Yes: $\frac12 = g(1)$. Continue backward from $1$: as computed above, $1$ has no $f$-preimage, so the chain is

So $\frac12 \in A$ is type $B$, meaning $h(\tfrac12) = (g|_{B_B})^{-1}(\tfrac12) = 1$. Similarly $g(0) = \frac{0+1}{4} = \frac14$, and by the same logic $\frac14 \in A$ is type $B$ with $h(\frac14) = 0$. Now take $x = \frac{3}{10} \in A = (0,1)$, a "generic" point outside $[\frac14,\frac12]$. Does it have a $g$-preimage? We'd need $y\in[0,1]$ with $\frac{y+1}{4} = \frac{3}{10}$, i.e. $y = \frac{12}{10}-1 = \frac15$... let's actually solve: $y = 4\cdot\frac{3}{10} - 1 = \frac{12}{10}-1 = \frac{1}{5} \in [0,1]$. So it does have a preimage, $y = 1/5$. This means points near the edges of $(0,1)$ can still be reached by $g$, and the chain continues: from $y=1/5\in B$, does it have an $f$-preimage? Yes, $f(1/5) = 1/5 \in (0,1)$ trivially since $f$ is inclusion and $1/5\in(0,1)$. Continue: from $x=1/5 \in A$, does it have a $g$-preimage? Solve $\frac{y+1}{4}=\frac15 \Rightarrow y = \frac45 - 1 = -\frac15 \notin [0,1]$. No preimage — chain stops at $1/5 \in A$. So the full chain is

type $A$, and $h(3/10) = f(3/10) = 3/10$. Generic points of $(0,1)$ that are never expressible as iterates landing in $[\frac14,\frac12]$-type preimage chains from $0$ or $1$ will be type $A$ and map via $f$ (identity); only the countably many points in the specific backward orbit of $\{0,1\}$ under $g$ then $f^{-1}$ (namely $1,\frac12,\frac15$'s preimage chain, etc.) are type $B$ and get redirected via $g^{-1}$. The resulting $h$ is an explicit, computable bijection $(0,1)\to[0,1]$ built entirely from these two very different-looking injections.