施罗德-伯恩斯坦定理

A B

g[B] f[A]

h[A]

当我第一次试图证明P(ℕ)与ℝ 之间等势的时候，我发觉，如果我仅仅将ℝ定义为有理数轴（ℚ，≤ℚ）上所有戴德金分割^的集合而完全不引入数位系统的话，要找到 P(ℕ) 与ℝ之间的双射其实是很有挑战的。于是，我想到一个捷径：如果我可以找到两个函数f：P(ℕ) → ℝ以及g：ℝ → P(ℕ)，而这两个函数都是单射的话，那么，应该足以说明这两个集合之间存在双射，即，它们是等势的。这个其实就是康托尔-伯恩斯坦-施罗德定理所包含的事实。但是，就如同许多集合论中的定理，它在直观上如此容易被接受，但是，当时我既不知道这个著名的定理，也不知道如何证明它。

在继续讨论之前，我声明一下这篇文章中使用的符号：

1.A≤ₑ B表示，存在一个函数f：A→B之为单射；

2.A＜ₑ B表示A≤ₑ B但是￢（B≤ₑ A)；

3.A~ₑ B表示，存在一个函数f：A → B之为双射，即 A 和 B 等势。

陈述及直接推论

施罗德-伯恩斯坦定理（Schröder-Bernstein

theorem )

设 A 和 B 为两个集合。如果 A≤ₑ B 且B≤ₑ A，那么，A~ₑ B。

根据该定理，许多关于集合间的等势的问题都变得简单了许多，例如，我在一开始提到的P(ℕ)~ₑ ℝ。并且，它也对基数的定义（以序数的术语）提供了极大的便利。并且，根据该定理，关系≤ₑ是宇宙𝒰上的一个序（伴随~ₑ 为这个序的等价关系），也就是说：

1.≤ₑ 在𝒰上是自反的：对于任何

x∈𝒰 ，我们有x ≤ₑ x；

2.≤ₑ 在𝒰上是传递的：对于任何

x，y，z ∈𝒰 ，如果x ≤ₑ y 且y ≤ₑ z，那么x ≤ₑ x；

3.≤ₑ 在𝒰上是反对称的：对于任何

x，y ∈𝒰，如果x ≤ₑ y 且y ≤ₑ x，那么

x~ₑ y。

≤e的反对称性正是施罗德-伯恩斯坦定理所声明的。（当然，必须注意的是，在没有选择公理°的情况下，≤ₑ 无法被展现为一个𝒰 上的全序——纵使这个结论再直观。≤ₑ 之为全序其实是策梅洛定理的一个结论--它经常是以基数的术语所叙述的。）

该定理的证明是否需要依赖选择公理？起码，就这个形式的施罗德-伯恩斯坦定理而言，其证明是不需要选择公理的参与的。最初，在1887年，康托第一次发表了该定理，但其中并未附带任何证明。此后的大约十年中，戴德金、施罗德、伯恩斯坦等人都对此进行了证明，并且，那些证明都绕开了选择公理。在下面，我介绍一种在我看来较为直观的证明。

证明

首先，我简单地介绍一下该定理的证明大纲。

设 A 和 B 为两个集合满足A≤ₑ B且B≤ₑ A。设f：A → B以及g：B → A为两个单射。

设

f B

h＝g◦f：A→f[A]⊆ BA.

由此，从下图中，我们看到，复合函数h 将A映射到了它的一个子集h[A]中；并且，h[A] ⊆ g [B]。

A B

y [B]

h[A] f[A]

由于f和 g 都是单射，那么，他们的复合函数h也是一个单射。因此，A~ₑ h[A]。这样，我们就找到了 A 的一个集合h[A]与之等势。现在，我们有了这样一个⊆-链：

h[A]⊆ g[B]⊆ A.

既然g 是一个单射，那么g[B]~ₑ B。现在，如果我们可以证明，在这个关系下，g[B]~ₑ A可以被保证，那么，根据~ₑ 的传递性，我们就可以得到

B~ₑ g[B]~A，

从而证明该定理。

引理

设X 和 X'为两个集合满足X' ⊆ X。如果X~ₑ X' 那么，对于任何Y，如果

X' ⊆ Y ⊆ X，

那么Y~ₑ X。

证明：

既然X' ⊆ X，要么X'＝X，要么

X' ⊂ X。如果X'＝X的话，那么，证明其实已经结束了。因此，假设X' ⊂ X，并且设 Y 为一个集合满足 X' ⊆ Y ⊆ X。设f：X → Y为一个单射；并且，既然X~ₑ X，我们可以假设f满足

f[X]＝X'。（确实，这种情况是存在的，因为，我们至少能找到一个这样的类型X，可以被一一对应地映射到它的某个真子集X'上；例如，X＝ℕ而

X'＝{2n：n ∈ ℕ }。)

这个引理的证明只存在一个难点。我们需要考虑函数f：X → Y可能不是一个满射的情况。由此，我们需要通过f的术语，定义一个函数g，使得g：X → Y是一个双射。

X

Y

f[X]

f[Y]

f[X]

f[Y]

R₀ R₁ R₂ ...

假设f不是一个满射。这个时候，Y\f[X]并不是一个空集。由此，在上图中，我们可以看到，Y\f[X]形成了一个f[X]外的一个环状图像。如果我们将这个环再次通过f映射到X中，便会进而得到f[X]中的一个环状图像f[X\Y]。进而，如图所示，我们会得到一个序列的环：

{R₀＝X\Y，}

R－ {R₁＝f[R₀]，}

{R₂＝f[R₁]，}

{R₃＝f[R₂]，}

...

从图中，不难发现，∪R ⊂ Y，并且，Y\∪R 同样留下来了由一个个环组成的图像。由此，如果设y：X → Y为一个函数，并且定义它为

y(x)＝{f(x)：x∈∪R

{ z ：z ∉∪R

那么，g便是一个 X 到 Y 的双射。下面，我们来验证这个结论。

首先，我们需要验证一个从图上看十分直观的结论：对于任何j，k∈ℕ，如果j≠k，那么Rⱼ∩Rₖ＝∅。

由于f是一个从 X 映射到其自身子集的凶数，因此，

···⊂ f³[X] ⊂ f²[X] ⊂ f¹[X] ⊂ f⁰[X].

设j，k∈ℕ满足j≠k。首先，我们假设k＜j。由于Rⱼ ⊆ fʲ[X] ⊆ fᵏ[Y]以及Rₖ＝fᵏ[X]\fᵏ[Y]，我们得到

Rⱼ∩Rₖ ⊆ (fᵏ[X]\fᵏ[Y])∩fᵏ[Y]＝∅.

j＜k的情况与此类似，我就不在此赘述了。

因此，整个序列R 中的元素是互不相交的。也因此，对于任何i∈ℕ以及x∈X，如果x∈Rᵢ，那么f(x)∉ Rᵢ。（在下面的过程中，我们需要小心地辨别何时我们需要这个结论。）

现在，我们来验证y是否是一个双射。

设y∈Y。如果y ∉∪R，那么，由于y ∈ X，我们有g(y)＝y。因此，假设y∈∪R。由于y ∈ Y，因此

y∈Y∩∪R ⊆ f[X]。进而，y∈f[X]。这说明，一定存在一个x∈X，使得f(x)＝y；并且，这个x∈∪R，否则的话，x＝y导致y ∉∪R，从而产生了悖论。因此是一个满射。

设x，x'∈X满足x≠x'。这里，我们需要考虑三种情况：

1.x∈∪R且x'∈∪R；

2.x∉∪R且x'∉∪R；

3.x∈∪R且x'∉∪R。

在情况1中，由于f是一个单射，因此

f(x)≠f(x')。在情况2中，g(x)≠x'直接由于x≠x'。因此，我们考虑情况3。这个情况下，f(x)∈∪R，否则，f(x)＝x导致x∉∪R。由于x'∉∪R，我们有

f(x')＝x'∉∪R。因此，f(x)≠f(x')。由此，g是一个单射。

既然g：X → Y既是一个单射又是一个满射，那么它是一个双射；从而，X~ₑ Y。◾

我们将上述结论插入到证明大纲中去，便可以直接完成该定理的证明。

施罗德-伯恩斯坦定理是否可以被推广到类型关系上？

在我最初证明施罗德-伯恩斯坦定理的时候，其实是遇到了一个问题，那就是：根据MK中的尺寸限制公理（the axiom of limitation of size），一个类型X之为真类型（即，不是一个集合）当且仅当存在一个函数

f：𝒰 → X之为单射。我直观地认为，这个时候，宇宙𝒰 和真类型 X之间一定存在一个双射b：𝒰 → X。但是，要证明这个观点，我们就必须将施罗德-伯恩斯坦定理是可以被推广到任意两个类型之间的，也就是：对于任何类型A和B（不论它们是不是集合），如果A≤ₑ B且B≤ₑ A，那么

A~ₑ B。

但是，如果我们将上述证明中的“集合”全部替换为“类型”，那么，这个证明将会是不合理的。就算我们避免定义序列R，而只说，对于任何i∈ℕ，Rᵢ是一个类型（不论是不是集合）满足Rᵢ＝fⁱ[X\Y]，这时，我们依然会遇到一个问题：我们凭什么将ℕ作为一系列不一定是集合的类型 R₀，R₁，R₂，. . . 的索引类型？要知道，索引类型的存在本身是函数定义的一个衍生。如果我们说一个类型𝐼（不管它是不是集合）是某些类型

Cα，Cᵦ，Cᵧ，. . . 的索引类型，那么，这就意味着，我们承认存在一个函数φ：𝐼 → C之为一个索引函数；这时，如果存在某个i∈𝐼使得Cᵢ 不是一个集合，那么，不论是在NBG还是MK中，C都无法是一个类型。这也是为什么，任意并和任意交无法被定义于任意多个真类型之间。

因此，起码根据上述证明，我们无法将施罗德-伯因斯坦完理推广到类型关系上，如里，

我们接受一个可以以真类为元素的更广大的“集合论”，或者，接受选择公理，并在证明过程中避免制造R 这样的类型，那么，这种推广会变得简单很多—一起码，在这两种情况下，推广是可能的。对此，我就不在这篇文章中展开叙述了。

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