[科普中国]-康托尔-伯恩施坦定理

康托尔-伯恩施坦定理也叫作定理****康托尔-伯恩斯坦-施罗德定理（Cantor-Bernstein-Schroeder theorem），是集合论中的一个基本定理，得名于康托尔、伯恩斯坦和 Ernst Schröder。

简介康托尔-伯恩斯坦定理（Cantor-Bernstein theorem）是集合论中的一个基本定理，得名于康托尔、伯恩斯坦和 Ernst Schröder。该定理陈述说：如果在集合A和B之间存在单射f:A→B和g:B→A，则存在一个双射h:A→B。从势的角度来看, 这意味着如果 |A| ≤ |B| 并且 |B| ≤ |A|，则 |A| = |B|，即A与B等势。显然，这是在基数排序中非常有用的特征。

证明下面是证明：1

**证明：**令

并令

对任意的a∈A定义映射

如果a不在集合C中，那么a不在集合C0中。因此由C0的定义可知a∈g[B]。由于g是单射，其逆映射g(a)存在。

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

**满射：**对任何b∈B，如果b∈f[C]，那么存在a∈C使得b=f(a)。因此由h的定义可知b=h(a)。如果b∉f[C]，定义a=g(b)。由C0的定义知，a不属于C0。由于f[Cn] 是f[C]的一个子集，因而b不属于任何一个f[Cn]，所以由集合Cn的递归定义知，a=g(b) 不属于Cn+1=g[f[Cn]]*此处错误，逻辑反了*。因此，a不属于C。那么根据h的定义b=g(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是单射得a=b。对于第三种情况，有f(a)=g(b)⇒g(f(a))=g(g(b))⇒g°f(a)=b，又由前提a∈C，而C在g°f下封闭，于是b∈C，但是由前提得b∉C，矛盾了，因此第三种情况不可能出现。同理第四种情况也不可能出现，这说明ran(f|C) ∩ ran(g|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 定理。

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学