The Schröder–Bernstein Theorem — Mathematics Knowledge System

Overview

The Schröder–Bernstein theorem (also called the Cantor–Schröder–Bernstein theorem) says that if there is an injection from set A into set B, and also an injection from B into A, then there must exist a bijection between A and B — that is, |A| ≤ |B| and |B| ≤ |A| together force |A| = |B|. This is exactly the property that makes cardinality behave like an ordering in the familiar sense (antisymmetry), and it is what justifies writing '≤' for cardinal comparison at all: without it, having injections both ways wouldn't guarantee the sets are truly the 'same size.' Remarkably, the theorem's proof needs no explicit description of either injection's inverse and does not require the Axiom of Choice — it works by a clever chain-tracing construction that stitches the two given injections together into one true bijection.

Intuition

Suppose you can fit a copy of set A snugly inside set B (an injection A→B), and you can also fit a copy of B snugly inside A (an injection B→A). Intuitively this feels like it should force A and B to be 'the same size' — otherwise one would have to be strictly bigger than the other while simultaneously fitting inside it. The theorem confirms this intuition even for INFINITE sets, where it is far from obvious (an infinite set can famously be the same size as a proper subset of itself, e.g. ℕ and the even numbers). The proof works by tracing 'ancestry chains': starting from any element, repeatedly apply the two injections backward (undoing whichever map most recently placed you) as far as possible. Every element's chain either goes back forever, terminates in A, or terminates in B — and on each type of chain, one of the two given injections (or its inverse) already acts as a perfect bijection; splicing these three cases together yields one bijection covering all of A and B at once.

Formal Definition

Definition

If f: A → B and g: B → A are both injections, then there exists a bijection h: A → B. Equivalently, in terms of cardinality, |A| ≤ |B| and |B| ≤ |A| implies |A| = |B|.

f: A \hookrightarrow B \;\land\; g: B \hookrightarrow A \implies \exists\, h: A \to B \text{ a bijection}

The Schröder–Bernstein theorem

|A| \le |B| \;\land\; |B| \le |A| \implies |A| = |B|

Cardinality-order form (antisymmetry)

Derivation

The classical chain-tracing (back-and-forth) proof: partition A into three classes based on tracing each element's ancestry through f and g, and define h piecewise.

\text{For } a \in A, \text{ trace its chain: } a \leftarrow g^{-1}(a) \leftarrow f^{-1}(g^{-1}(a)) \leftarrow \cdots \text{ as far as it is defined}

Repeatedly undo g then f (whichever applies) to find where a 'originally came from'

A_A = \{a : \text{chain terminates in } A\},\; A_B = \{a : \text{chain terminates in } B\},\; A_\infty = \{a : \text{chain never terminates}\}

Every element of A falls into exactly one of three classes

h(a) = f(a) \text{ for } a \in A_A \cup A_\infty, \qquad h(a) = g^{-1}(a) \text{ for } a \in A_B

Define h piecewise: use f on the first two classes, the inverse of g on the third

h: A \to B \text{ is a bijection}

On each class, h is forced to be a bijection onto the corresponding piece of B, and the three pieces partition B

Worked Examples

There is an obvious injection f: (0,1) → [0,1] given by the inclusion map f(x)=x, since (0,1) ⊆ [0,1].
$f(x) = x, \quad f: (0,1) \hookrightarrow [0,1]$
There is also an injection g: [0,1] → (0,1), e.g. g(x) = (x+1)/3, which maps [0,1] into the subinterval [1/3, 2/3] ⊂ (0,1).
$g(x) = \frac{x+1}{3}, \quad g: [0,1] \hookrightarrow (0,1)$
Both f and g are injections (f trivially; g because it's strictly increasing/linear), so by Schröder–Bernstein a bijection between (0,1) and [0,1] exists.
$f,g \text{ injective} \implies |(0,1)| = |[0,1]|$

Answer: |(0,1)| = |[0,1]| by Schröder–Bernstein — even though [0,1] has two extra points, the two sets have exactly the same cardinality (the continuum, 2^{ℵ₀}).

Practice Problems

Difficulty 6/10

State the two hypotheses needed to invoke the Schröder–Bernstein theorem and the conclusion it yields.

Difficulty 6/10

Which of these facts is a direct consequence of the Schröder–Bernstein theorem?

Every infinite set has a proper subset of the same cardinality|A| ≤ |B| and |B| ≤ |A| together imply |A| = |B|The Axiom of Choice is provable in ZFEvery set can be well-ordered

Difficulty 7/10

Show |ℕ × ℕ| = |ℕ| using Schröder–Bernstein by exhibiting an injection each way, rather than constructing a full bijection like Cantor's pairing function.

Common Mistakes

Common Mistake

Thinking that having an injection A→B and an injection B→A automatically hands you a bijection without further work — i.e. that f or g itself must already be a bijection.

Neither given injection need be surjective; the theorem's content is that a DIFFERENT function h, built by splicing pieces of f and g⁻¹ together via chain-tracing, is guaranteed to be a bijection.

Common Mistake

Believing the theorem requires the Axiom of Choice, by analogy with other infinite-cardinality comparison results.

Unlike the general trichotomy of cardinals (any two cardinals are comparable), which does require AC, Schröder–Bernstein is provable in plain ZF via the explicit chain-tracing construction.

Quiz

Historical Background

Georg Cantor stated the result and used it (assuming the well-ordering of cardinals, hence implicitly the Axiom of Choice) as early as 1887, but did not publish a fully general proof. Richard Dedekind independently proved it, without invoking choice, in a 1887 manuscript that went unpublished and unnoticed for decades. Felix Bernstein, then a young student in Cantor's seminar, produced a choice-free proof in 1897, which Cantor announced; Ernst Schröder published his own proof attempt in 1896 that turned out to contain a gap, though he later gave a corrected version around 1898. Because of this tangled priority history the theorem carries several names — Cantor–Bernstein, Schröder–Bernstein, or Cantor–Schröder–Bernstein — reflecting the contributions and disputes among all of these mathematicians.

1887
Cantor states the theorem and uses it in his work (assuming a form of choice); Dedekind independently proves it choice-free, in an unpublished manuscript
Georg Cantor, Richard Dedekind
1896
Schröder announces a proof, later found to contain a gap
Ernst Schröder
1897
Bernstein, a student of Cantor, gives a correct proof avoiding the Axiom of Choice
Felix Bernstein
1898
Schröder publishes a corrected proof
Ernst Schröder

Summary

If f: A→B and g: B→A are both injections, the theorem guarantees a bijection h: A→B exists.
Equivalently: |A|≤|B| and |B|≤|A| together imply |A|=|B| — cardinality comparison is antisymmetric.
The classical proof traces each element's 'ancestry chain' under f and g and splices three cases into one bijection.
The theorem needs no Axiom of Choice — it holds in ZF alone, unlike general cardinal trichotomy.
Classic use: proving (0,1) and [0,1] (or ℕ×ℕ and ℕ) have equal cardinality without building an explicit bijection.

References

WebsiteWikipedia — Schröder–Bernstein theorem
BookHalmos, P. Naive Set Theory, Ch. 22.