康托尔-伯恩斯坦-施罗德定理

设 $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$ 同理定义。每个元素的链要么无限地往回延伸,要么停在 $A$ 中某个没有 $g$-原像的元素处,要么停在 $B$ 中某个没有 $f$-原像的元素处。这把 $A$ 划分成三部分:$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)$。由于三部分两两不相交,且各自双射到 $B$ 中对应部分($f$ 映到 $B_A \cup B_\infty$,$g^{-1}$ 映到 $B_B$),合并后的映射 $h$ 就是从整个 $A$ 到整个 $B$ 的双射,证明了 $|A|=|B|$。