TheoremProved

Cantor–Schröder–Bernstein theorem

Statement

If there exist injections $f:A\to B$ and $g:B\to A$ between two sets $A$ and $B$ , then there exists a bijection $h:A\to B$ . Equivalently: $|A|\le|B|$ and $|B|\le|A|$ together imply $|A|=|B|$ .

Why is it true?

Having an injective copy of each set sitting inside the other is already enough to guarantee they are genuinely the same size — you never need to exhibit a direct bijection, just two one-way embeddings that fit together.

Proof sketch

Trace each element of $A$ backward by alternately applying $g^{-1}$ and $f^{-1}$ where defined; every trail either stops in $A\setminus g(B)$ , stops in $g(B\setminus f(A))$ , or continues forever. Define $h=f$ on elements whose trail stops in $A$ or never stops, and $h=g^{-1}$ on elements whose trail stops in $B$ ; checking each case shows this $h$ is a well-defined bijection $A\to B$ .

Stated by

stated 1887Georg Cantor

Topics that use this theorem

Functions and cardinality

Related theorems

Uncountability of the reals (Cantor's diagonal argument)

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Kenneth Kunen (1980). Set Theory: An Introduction to Independence Proofs
Paul R. Halmos (1974). Naive Set Theory