カントール・ベルンシュタイン・シュレーダーの定理

与えられた2つの単射を $f : A \to B$、$g : B \to A$ とする。考え方は、各元について $f$ と $g$ を交互に逆にたどって得られる祖先の連鎖を追跡し、各連鎖が「どこから始まるか」に応じて最終的な全単射を部分ごとに組み立てることである。

$a \in A$ に対して、後退連鎖 $a, g^{-1}(a), f^{-1}(g^{-1}(a)), \ldots$ を、必要な逆写像が定義されている限り続けて定義し、$b \in B$ についても同様にする。各元の連鎖は、永遠に続くか、$g$ による原像を持たない $A$ の元で止まるか、$f$ による原像を持たない $B$ の元で止まるかのいずれかである。これにより $A$ は3つの部分 $A_A$(連鎖が $A$ で止まる)、$A_B$(連鎖が $B$ で止まる)、$A_\infty$(連鎖が止まらない)に分割され、同様に $B$ も $B_A, B_B, B_\infty$ に分割される。

$A$ で止まる連鎖、または止まらない連鎖の上では、$f$ 自身がすでにその部分の $A$ から対応する部分の $B$ への全単射を与えている(これらの元は単射によって到達され、$B$ 側で先に「尽きる」ことがないため)。$B$ で止まる連鎖の上では、$g$ がその部分の $B$ から対応する部分の $A$ への全単射を与えるので、その逆写像 $g^{-1}$ がその部分の $A$ からその部分の $B$ への全単射を与える。

$h : A \to B$ を、$a \in A_A \cup A_\infty$ のとき $h(a) = f(a)$、$a \in A_B$ のとき $h(a) = g^{-1}(a)$ と定義する。3つの部分は互いに素であり、それぞれが $B$ の対応する部分へ全単射で写る($f$ は $B_A \cup B_\infty$ へ、$g^{-1}$ は $B_B$ へ)ので、統合された写像 $h$ は $A$ 全体から $B$ 全体への全単射となり、$|A|=|B|$ が証明される。