The Cantor-Schröder-Bernstein Theorem

Constructing an explicit bijection between two infinite sets can be brutal. Try writing down a single function that pairs up $(0, 1)$ with the closed interval $[0, 1]$ — you immediately collide with the awkward endpoints 0 and 1, which have no obvious partners in the open interval. Or try mapping $\mathcal{P}(\mathbb{N})$ bijectively onto $\mathbb{R}$: the binary-expansion approach almost works but breaks at the $0.0111\ldots = 0.1000\ldots$ ambiguity. The Cantor-Schröder-Bernstein theorem cuts through all of this. It tells you that whenever you have an injection $A \hookrightarrow B$ and an injection $B \hookrightarrow A$, a bijection between $A$ and $B$ must exist — even though the theorem does not hand it to you. CSB is the constructive shortcut that powers most modern cardinality calculations.

The statement

Theorem (Cantor-Schröder-Bernstein). If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

Equivalently: if there exists an injection $f \colon A \to B$ and an injection $g \colon B \to A$, then there exists a bijection $h \colon A \to B$.

This is exactly the cardinality analog of antisymmetry: if $|A| \leq |B|$ and $|B| \leq |A|$ then $|A| = |B|$. It makes the ordering of cardinals well-behaved.

Why CSB is non-obvious

It is tempting to imagine that the two injections "stitch together" automatically — just use $f$ where you can and $g^{-1}$ on what is left over. But $f$ may miss elements of $B$, and $g$ may miss elements of $A$, and these "missed" pieces interact in complicated ways. Iterating $g \circ f$ and $f \circ g$ creates chains of elements that the proof must classify into three categories:

• An A-stopper: tracing the chain backwards (through $f^{-1}$ and $g^{-1}$) terminates in $A \setminus g(B)$.
• A B-stopper: tracing backwards terminates in $B \setminus f(A)$.
• An infinite chain: backward tracing never terminates.

For A-stoppers and infinite chains, define $h$ by $f$. For B-stoppers, define $h$ by $g^{-1}$ — this is well-defined because on a B-stopper chain every element of $A$ in the chain lies in $g(B)$ (otherwise the backward trace would have stopped earlier, in $A$). The resulting piecewise function is a bijection. This proof is constructive but the bijection it builds is typically not a "nice" formula — CSB is most useful precisely because it lets you avoid such formulas.

The standard cardinality dictionary

CSB underpins a cascade of identifications that organise the "two basic infinities" most students meet:

• $|(0, 1)| = |[0, 1]| = |\mathbb{R}| = \mathfrak{c}$.
• $|\mathcal{P}(\mathbb{N})| = |{0, 1}^{\mathbb{N}}| = |\mathbb{R}| = \mathfrak{c}$.
• $|\mathbb{R}^n| = |\mathbb{R}|$ for every finite $n \geq 1$.
• $|\mathbb{R}^{\mathbb{N}}| = |\mathbb{R}|$ (continuum many sequences of reals).

Almost every entry on this list is proved by exhibiting two injections (often very simple ones) and invoking CSB — rather than by writing down a bijection.

Worked example: $|(0, 1)| = |\mathbb{R}|$

Injection $f \colon (0, 1) \to \mathbb{R}$: the inclusion $f(x) = x$. Obviously injective.

Injection $g \colon \mathbb{R} \to (0, 1)$: $g(x) = \tfrac{1}{\pi} \arctan(x) + \tfrac{1}{2}$. Since $\arctan$ is strictly increasing with range $(-\pi/2, \pi/2)$, $g$ maps $\mathbb{R}$ injectively into $(0, 1)$.

Both injections exist, so by CSB, $|(0, 1)| = |\mathbb{R}|$. We are not told what the bijection looks like — and for most purposes we do not need to know.

That said, the $(0,1) \leftrightarrow \mathbb{R}$ bijection IS constructible (using $\tan$). Switch the widget below to that preset and watch the explicit construction step through. Compare with the other presets — CSB guarantees a bijection between, say, $\mathbb{N}$ and $\mathbb{Q}^+$, and the Cantor-Stern enumeration is one way to exhibit it.

Pause and think: Why does it matter that CSB only asserts the existence of a bijection rather than constructing one? (Hint: in many proofs — especially in measure theory and analysis — we only need to know that $|A| = |B|$ to make a counting argument or transfer a result. We do not need the actual bijection. CSB separates "are these the same size?" from "what is the explicit pairing?")

Try it

• Before reading further: use CSB to show $|[0, 1]| = |[0, 2]|$. Provide injections in both directions.
• Predict first: use CSB to show $|\mathbb{R}| = |(0, \infty)|$. (Hint: $e^x$ does half the work; what does the other injection look like?)
• Show $|\mathcal{P}(\mathbb{N})| = |{0, 1}^{\mathbb{N}}|$ — the power set of $\mathbb{N}$ equals the set of infinite binary sequences. Give a bijection (this one is so direct that CSB is overkill).
• Predict first: is it possible to have injections $A \to B$ and $B \to A$ without any actual bijection between them? (CSB says no — but think about why this is surprising.)
• Show $|\mathbb{R}^2| = |\mathbb{R}|$ using CSB. (Hint: the injection $\mathbb{R} \to \mathbb{R}^2$ is trivial; the injection $\mathbb{R}^2 \to \mathbb{R}$ uses an interleaving of decimal expansions.)

A trap to watch for

A common misreading is that CSB constructs a bijection explicitly — that having two injections somehow hands you the bijection ready-made. It does not. CSB is an existence theorem: it tells you that some bijection exists, but the proof has to do real work to extract one, classifying elements into A-stoppers, B-stoppers, and infinite chains. In many situations the bijection it produces is not a nice closed-form formula. The lesson is: when a problem only asks "do these sets have the same cardinality?", CSB and a pair of injections is usually the cleanest route. When a problem asks for an explicit bijection, CSB does not directly help — you must either construct the bijection or unpack the CSB proof for the specific case.

What you now know

You can state CSB, recognise the pattern (injection in each direction) that triggers it, and apply it to standard cardinality equations like $|(0, 1)| = |\mathbb{R}|$ and $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$. Together with Cantor's diagonal argument from the previous section, CSB completes the toolkit of basic cardinality reasoning. Chapter 8 closes here in Velleman’s text; further results — the Continuum Hypothesis, large cardinals, the Axiom of Choice and its consequences — belong to a follow-up course in axiomatic set theory.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 8.
• Halmos, P. R. (1960). Naive Set Theory. Springer (CSB chapter).
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press.
• Hrbacek, K., Jech, T. (1999). Introduction to Set Theory (3rd ed.). CRC Press.
• Smullyan, R. M., Fitting, M. (1996). Set Theory and the Continuum Problem. Oxford University Press.