Cantor-Bernstein-Schroeder定理
维基百科，自由的百科全书
在集合论中，Cantor–Bernstein–Schroeder 定理，得名于康托尔、Felix Bernstein 和 Ernst Schröder，它声称如果在集合 A 和 B 之间存在单射函数 f : A → B 和 g : B → A，则存在一个双射函数 h : A → B。依据这两个集合的势，这意味着如果 |A| ≤ |B| 并且 |B| ≤ |A|，则 |A| = |B|。这明显是在基数排序中非常有用的特征。
下面是证明:
设
![C_0=A\setminus g[B],\!](../../../math/8/c/e/8cee0cfc4586b198cd8d03c5a22702bd.png)
且
![C_{n+1}=g[f[C_n]]\quad \mbox{ for }n\ge 0](../../../math/2/b/d/2bdab3d1dbf2b97ebe92ed2147245489.png)
且
则对于 x∈A 设
如果 x 不在 C 中，则 x 必定在 g[B] 中，所以有一个唯一的元素 
而且 h 是良好定义的。你可以接着检查 h : 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
