查看“︁康托尔-伯恩斯坦-施罗德定理”︁的源代码

'''施罗德-伯恩斯坦定理'''（{{lang-en|Schröder–Bernstein theorem}}），又称'''康托尔-伯恩斯坦-施罗德定理'''（{{lang|en|Cantor-Bernstein-Schroeder theorem}}）是[[公理化集合论|集合论]]中的一个基本定理，得名于[[康托尔]]、[[费利克斯·伯恩斯坦|伯恩斯坦]]和施罗德。该定理陈述说：如果在[[集合 (数学)|集合]] ''A'' 和 ''B'' 之间存在[[单射]] ''f'' : ''A'' → ''B'' 和 ''g'' : ''B'' → ''A''，则存在一个[[双射]] ''h'' : ''A'' → ''B''。從[[势 (数学)|势]]的角度來看, 这意味着如果 |''A''| ≤ |''B''| 并且 |''B''| ≤ |''A''|，则 |''A''| = |''B''|，即''A''与''B''[[等势]]。显然，这是在基数排序中非常有用的特征。

== 证明 ==


下面是证明：<!-- due to Eilenberg? -->

'''证明：''' 令

:<math>C_0=A\setminus g[B],\qquad C_{n+1}=g[f[C_n]]\quad \forall n\ge 0</math>

并令

:<math>C=\bigcup_{n=0}^\infty C_n.</math>

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

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

如果''a''不在集合''C''中，那么''a''不在集合''C''<sub>0</sub>中。因此由''C''<sub>0</sub>的定义可知''a''&nbsp;∈&nbsp;''g''<nowiki>[</nowiki>''B''<nowiki>]</nowiki>。由于''g''是单射，其逆映射''g''<sup>&nbsp;–1</sup>(''a'')存在。

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

* '''满射：'''对任何 ''b''&nbsp;∈&nbsp;''B''，如果 ''b''&nbsp;∈&nbsp;''f''<nowiki>[</nowiki>''C''<nowiki>]</nowiki>，那么存在 ''a''&nbsp;∈&nbsp;''C'' 使得 ''b''&nbsp;=&nbsp;''f''(''a'')。因此由''h''的定义可知 ''b''&nbsp;=&nbsp;''h''(''a'')。如果 ''b''&nbsp;∉&nbsp;''f''<nowiki>[</nowiki>''C''<nowiki>]</nowiki>，定义 ''a''&nbsp;=&nbsp;''g''(''b'')。由 ''C''<sub>0</sub> 的定义知，''a'' 不属于 ''C''<sub>0</sub>。由于 ''f''<nowiki>[</nowiki>''C''<sub>''n''</sub><nowiki>]</nowiki> 是 ''f''<nowiki>[</nowiki>''C''<nowiki>]</nowiki>的一个子集，因而 ''b'' 不属于任何一个 ''f''<nowiki>[</nowiki>''C''<sub>''n''</sub><nowiki>]</nowiki>所以由集合''C''<sub>n</sub>的递归定义以及''g''为单射（''a'' 属于''g''<nowiki>[</nowiki>''f''<nowiki>[</nowiki>''C''<sub>''n''</sub>]]且''a'' 属于''g''[''B'']無法產生）的事实知，''a''&nbsp;=&nbsp;''g''(''b'') 不属于 ''C''<sub>''n''+1</sub>= ''g''<nowiki>[</nowiki>''f''<nowiki>[</nowiki>''C''<sub>''n''</sub><nowiki>]]</nowiki> 。因此，''a'' 不属于 ''C''（''C''<sub>0</sub>和''C''<sub>n</sub>）那么根据''h''的定义 ''b''&nbsp;= ''g''<sup>–1</sup>(''a'')&nbsp;= ''h''(''a'')。

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

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

==可视化==

''h'' 的定义可透過以下示意图展示。

[[File:Cantor-Bernstein.png|example of the definition of 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

[[Category:数学定理|K]]
[[Category:基数]]