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

康托尔-伯恩斯坦-施罗德(Cantor-Bernstein-Schroeder)定理 是集合论中的一个基本定理。该定理陈述说: 如果在集合 A 和 B 之间存在单射 f : A → B 和 g : B → A，则存在一个双射 h : A → B.依据这两个集合的势, 这意味着如果 |A| ≤ |B| 并且 |B| ≤ |A|，则 |A| = |B|, 即A与B等势. 显然, 这是在基数排序中非常有用的特征.

证明

下面是证明:

证明: 令

$C_0=A\setminus g[B],\qquad C_{n+1}=g[f[C_n]]\quad \forall n\ge 0$

并令

$C=\bigcup_{n=0}^\infty C_n.$

则对任意的 a∈A 定义映射

$h(a)=\left\{ \begin{matrix} f(a) & \,\,\mbox{if }a\in C \\ g^{-1}(a) & \mbox{if }a\not\in C \end{matrix} \right.$

如果a不在集合C中, 那么a不在集合C₀中. 因此由C₀的定义可知a ∈ g[B]. 由于g是单射, 他的逆映射g ^–1(a)存在.

接下来验证 h : A → B 就是想要的双射.

• 满射: 对任何 b ∈ B. 如果 b ∈ f[C], 那么存在 a ∈ C 使得 b = f(a). 因此由h的定义可知 b = h(a) . 如果 b 不属于 f[C], 定义 a = g(b). 由 C₀ 的定义知, a 不属于 C₀. 由于 f[C_n] 是 f[C]的一个子集, 因而 b 不属于任何一个 f[C_n], 所以由集合C_n的递归定义知, a = g(b) 不属于 C_n+1 = g[f[C_n]]. 因此, a 不属于 C. 那么根据h的定义 b = g ^–1(a) = h(a) .

• 单射: 若h(a)=h(b),则有a∈C∧b∈C,a∉C∧b∉C,a∈C∧b∉C,a∉C∧b∈C四种情况，对于前两种情况，由f与g ^–1是单射得a=b，对于第三种情况，有f(a)=g ^–1(b)⇒g(f(a))=g(g ^–1(b))⇒g°f(a)=b,又由前提a∈C，而C在g°f下封闭，于是b∈C，但是由前提得b∉C，矛盾了，因此第三种情况不可能出现，同理第四种情况也不可能出现，这说明ran(f|C)∩ran(g ^–1|A\C)=∅。综上若h(a)=h(b)，一定有a=b。

注意这个 h 的定义是非构造性的，在不存在一般性方法在有限步骤内判定，对于任何给定集合 A 和 B 与单射 f 和 g，是否 A 的一个元素 x 不位于 C 中的意义上。对于特殊集合和映射这当然是可能的。

可视化

h 的定义可可视化为如下示意图。

显示的是部分的(不相交)集合 A 和 B 和在一起的部分的映射 f 和 g.如果集合 A ∪ B，与两个映射一起，被解释为一个有向图，则这个双向图有多个连接起来的构件(component)。

这些可以分成四个类型: 无限扩展到两个方向的路径，偶数长度的有限圈(环)，开始于集合 A 中的无限路径，和开始于集合 B 中的无限路径(在图中通过元素 a 的路径是在两个方向上无限的，所以这个图包含所有类型的一个路径)。一般的说，不可能在有限步骤内判定　A 或 B 的一个给定元素属于那种类型的路径。

上面定义的集合 C 精确的包含是开始在 A 中的无限路径的一部分的 A 的元素。映射 h 接着被按如下方式定义，对于所有路径它生成一个双射，映射在路径中 A 的每个元素到在路径中直接前于或后于它 B 的一个元素。对于在两个方向上都是无限的路径，和对于有限圈，我们选择映射所有元素到它在路径中的前驱。

最初的证明

康托尔的早先证明有效的依赖于选择公理，通过推导出良序定理的推论。上面给出的证明证实了可以证明这个结果而不使用选择公理。

这个定理也叫做 Schroeder-Bernstein 定理，但是更加倾向于加上康托尔的名字，毕竟他贡献了最初的版本。它也叫做 Cantor-Bernstein 定理。

引用

• Proofs from THE BOOK, p. 90. ISBN 3540404600