形式陈述

若存在单射

$$ f:A\hookrightarrow B, \qquad g:B\hookrightarrow A, $$$$f:A\hookrightarrow B,g:B\hookrightarrow A,$$

则存在双射 $h:A\leftrightarrow B$$h:A\leftrightarrow B$。这就是 Cantor–Schröder–Bernstein 定理。

一种构造证明把 $A$$A$ 中不在 $g(B)$$g(B)$ 内的点记为 $A_0$$A_0$，递归令

$$ A_{n+1}=g(f(A_n)),\qquad C=\bigcup_{n\ge0}A_n. $$$$A_{n+1}=g(f(A_n)),C=\bigcup _{n\ge 0}{A}_n.$$

定义

$$ h(a)= \begin{cases} f(a),&a\in C,\\ g^{-1}(a),&a\notin C. \end{cases} $$$$h(a)=\{\begin{array}{ll}f(a),& a\in C,\\ g^{-1}(a),& a\notin C.\end{array}$$

可验证 $h$$h$ 良定义且为双射。

直觉

双向都能无碰撞地嵌入，说明两集合没有一方“严格装不下”另一方。证明把由未被 $g$$g$ 命中的点发出的交替链交给 $f$$f$，其余链用 $g$$g$ 反向匹配。

例子与边界

$(0,1)$$(0,1)$ 可单射进 $[0,1]$$[0,1]$，反向包含映射也是单射，因此两者等势；定理无需先猜出显式双射。仅有两边满射不能在无选择公理的任意语境中直接替代本定理的两边单射假设。

推论与应用

该定理允许用双向编码证明基数相等，尤其适合无限集合。它说明基数上的关系 $|A|\le|B|$$|A|\le |B|$ 具有反对称性，从而真正形成偏序。

参考资料

• Paul R. Halmos, Naive Set Theory, 1960; Dover reprint 2017，§22。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019，Ch. 7。