Exercise 2102Logic, sets and proofs › Countability and cardinalityM1Added 3 Nov 2026

Proof of Cantor–Bernstein–Schröder

#Cantor-Bernstein#proof#bijection

Statement

Sketch the proof of Cantor–Bernstein: injections $f:A\to B$ , $g:B\to A$ give a bijection $A\to B$ .

Hint

Iterate $g\circ f$ to build an infinite descending chain; use it to split $A$ into two parts.

Show solutionHide solution

Solution

Setup. Let $A_0=A\setminus g(B)$ , and $A_{n+1}=g(f(A_n))$ . Let $A_\infty=\bigcup_{n\ge0}A_n$ .

Bijection.
- On $A_\infty$ : use $f$ (since $A_\infty\subseteq g(B)$ implies $f$ surjects onto $f(A_\infty)$ ).
- On $A\setminus A_\infty$ : use $g^{-1}$ (well-defined since $A\setminus A_\infty\subseteq g(B)$ ).

Conclusion. This is a bijection $A\to B$ ; Cantor–Bernstein holds.

Proof of Cantor–Bernstein–Schröder

Statement

Solution

More problems in Countability and cardinality