康托尔-伯恩斯坦定理

康托尔-伯恩斯坦定理（Cantor-Bernstein定理）：设A和B是两个集合。如果从A到B有一个单射，并且从B到A也有一个单射，则A和B之间有一个一一映射。

换个表述也可以是：如果Cαrd(A) ≤ Cαrd(B)且 Cαrd(B) ≤ Cαrd(A)，那么一定有 Cαrd(A)＝Cαrd(B) 。

这两种表述无论哪种都是一看就说了句废话，这不是显而易见的吗？然而，它的证明并不显然。

先回顾下Card是什么。

对于有限集，我们把一个集合中包含的元素的个数称为这个集合的基数（cardinality）。

如果两个集合A 和 B 之间存在双射 f：A → B ，则称 A 与 B 是对等的，记作 A ~ B 。

两个对等的集合具有相同的基数。根据鸽笼原理/抽屉原则，对于有限集，一个集合不会与它的某一个真子集对等。但对于无限集合，结论不成立，因此需要从另一个角度理解基数的概念。

集合的基数是集合的固有特征，每一个集合都具有唯一的基数，对等的集合具有相同的基数。

我们通常把一个集合A的基数记作Card(A)。对于元素个数为n的集合，基数为n。但无限集合不宜简单地用∞ 表示，因为比如实数集的基数比自然数集的基数更大。

那么基数大小是怎么定义的呢：设A，B 两个集合，如果 A 与 B 的某个子集对等，则称 A 的基数不超过 B 的基数，记作 Cαrd(A) ≤ Cαrd(B) 。如果 Cαrd(A) ≤ Cαrd(B) 且 Cαrd ≠ Cαrd(B) ，则称A的基数小于B的基数，记作 Cαrd(A)＜Cαrd(B) 。

那么回到了我们最初的问题，两种表述显然等价。对于实数α，b ，我们都知道如果 α ≤ b 且 b ≤ α ，则一定有 α＝b ，但是换成集合的基数后，答案也是肯定的，但并不显然。证明如下。

Banach引理：设f：X → Y 和 g：Y → Ⅹ 都是映射，则存在分解

X＝A∪∼A Y＝B∪∼B

使得A∩∼A＝∅ ，且 B∩∼B＝∅。，且 f(A)＝B g(∼B)＝∼A。

证明：对于X的子集E，如果E∩g(Y\f(E))＝∅

则称E是X中的分离集。记X中的分离集之全体为Γ ，则 Γ 非空，因为 ∅ 是X中的分离集，因此 Γ 至少含有 ∅ 这个元素。

现在令

A＝∪E

E∈Γ

即A是集族Γ 中所有元素的并集，则 A∈Γ 。事实上，对任意 E∈Γ ，根据分离集的定义，E∩g(Y\f(E))＝∅成立，又因为 A ⊇ E ，因此

E∩g(Y\f(A))＝∅，

从而有

E∩g(Y\f(A))＝∪[E∩g(Y\f(A))]＝∅

E∈Γ

这就证明了A∈Γ 。此外，不难发现A是 Γ 中的最大元素，即X中的最大分离集。

现在令B＝f(A)，∼B＝Y\B，∼A＝g(∼B)，则显然有

Y＝B∪∼B B∩∼B＝∅ A∪∼A＝∅，

接下来只须证明X＝A∪∼A 即可。用反证法，如果 A∪∼A ≠ X ，则存在 x₀ ∈ X\(A∪∼A)，令 A₀＝A∪{x₀} ，则不难证明 A₀ ∈ Γ ，但这与A是 Γ 中的最大元素矛盾，故反设不成立，引理得证。

Cantor-Bernstein定理：若X 与 Y 的某个子集对等， Y 也与 X 的某个子集对等，则 X ~ Y 。

证明：由题设，存在单射f：X → Y 及 g：Y → X ，根据Banach引理，存在分解

X＝A∪∼A Y＝B∪∼B A∩∼A＝B∩∼B＝∅

使得f(A)＝B ， g(∼B)＝∼A ，注意到 g：∼B → ∼A 是单满映射，因此存在逆映射 g⁻¹：∼A → ∼B 。现在定义映射 h：X → Y 如下

f(x)， x ∈ A，

h(x)＝{

g⁻¹(x)， x ∈ ∼A，

则h是单满映射，因此X ~ Y 。

证毕。

这个定理最初由Cantor于1887年提出，Dedekind于同年证明了这个定理，但未公开；Schroder于1896年发表了该定理的首个不依赖于选择公理的证明，但后来被人发现有漏洞；Bernstein于1897年给出该定理第一个不依赖于选择公理的正确证明。这里给出的证明方法是由Banach提出的。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。