康托尔定理

维基百科，自由的百科全书

康托尔定理指的是在 Zermelo-Fränkel 集合论中，声称任何集合 A 的幂集(所有子集的集合)的势严格大于 A 的势。康托尔定理对于有限集合是明显的，但是令人惊奇的是它对于无限集合也成立。特别是，可数无限集合的幂集是不可数无限的。要展示康托尔定理的对于无限集合的有效性，只需要测试一下下面证明中无限集合。

[编辑] 证明

设 f 是从 A 到 A 的幂集的任何函数。必须证明这个 f 必定不是满射的。要如此，展示一个 A 的子集不在 f 的像中就足够了。这个子集是

$B=\left\{\,x\in A : x\not\in f(x)\,\right\}.$

要证明 B 不在 f 的像中，假设 B 在 f 的像中。那么对于某个 y ∈ A，我们有 f(y) = B。现在考虑 y ∈ B 还是 y $\notin$ B。如果 y ∈ B，则 y ∈ f(y)，但是通过 B 的定义，这蕴涵了 y $\notin$ B。在另一方面，如果 y $\notin$ B，则 y $\notin$ f(y) 并因此 y ∈ B。任何方式下都是矛盾。

因为 x 在表达式 "x $\notin$ f(x)" 中重复出现，这是对角论证法。

[编辑] 在 X 是可数无限时对证明的详细解释

要掌握这个证明，让我们检查 X 是可数无限时的特殊情况。不失去一般性，我们采用自然数集合， X = N = {1, 2, 3,...}。

假设 N 双射于它的幂集 P(N)。让我们看一个样例 P(N):

$P(\mathbb{N})=\{\varnothing,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,...\},...\}$

P(N) 包含无限的 N 的子集，比如所有偶数的集合 {2, 4, 6,...}，还有空集。

现在让我们看一下 P(N) 的元素的样子，我们尝试给每个 N 的元素配对上每个 P(N) 的元素来证实这些无限集合是双射的。换句话说，我们将尝试对 N 的每个元素配对上来无限集合 P(N) 的元素，使得这两个集合中没有元素是未配对的。配对元素的尝试将是如下样子的:

$X\begin{Bmatrix} 1 & \Longleftrightarrow & \{4, 5\}\\ 2 & \Longleftrightarrow & \{1, 2, 3\} \\ 3 & \Longleftrightarrow & \{4, 5, 6\} \\ 4 & \Longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}P(\mathbb{N})$

某些自然数被配对上不包含它们的子集。例如，在我们的例子中，数 1 被配对上子集 {4, 5}。其他自然被配对上包含它们的子集。比如数 2 被配对上子集 {1, 2, 3}。

使用这个想法，让我们建造一个自然数的特殊集合。这个集合将提供我们所求索的矛盾。设 D 是被配对上不包含它们的子集的所有自然数的集合。通过定义，我们的幂集 P(N) 必定包含这个集合 D 作为元素。所以，D 必定被配对上某个自然数。但是这导致了一个问题 -- 哪个自然数和 D 配对呢? 它不能是 D 的成员，因为 D 被特殊构造为只包含那些不配对上包含它们的子集的自然数。在另一方面，如果配对于 D 的自然数不包含在 D 中，则再次通过 D 的定义，它必定包含在 D!

这是矛盾因为这个自然数不能同时在 D 的内部和外部。所以，没有自然数可以配对于 D，而我们的最初假定在 N 和 P(N) 之间有双射是有矛盾的。

通过这个反证法我们证明了 N 的势和 P(N) 的势不能相等。我们还知道了 P(N) 的势不能小于 N 的势，因为根据定义 P(N) 包含所有单元素集合，而这些单元素集合形成在 P(N) 内的 N 的复制品。所以只剩下一个可能，就是 P(N) 的势严格大于 N 的势，这就证明了康托尔定理。

[编辑] 历史

康托尔在1891年发表的论文《Über eine elementare Frage der Mannigfaltigkeitslehre》中本质上给出了这个证明，实数不可数的对角论证法也首次在这里出现。在这个论文中给出的这个论证的版本使用的是在集合上的指示函数而不是集合子集。他证明了如果 f 是定义在 X 上的函数，它的值是在 X 上的二值函数，则二值函数 G(x) = 1 − f(x)(x) 不在 f 的值域中。

罗素在《数学原理》(1903, section 348)中给出了一个非常类似的证明，在这里他证明了命题函数要比对象多。“假设所有对象和所有和它们相关的命题函数之间有一种对应，并令phi-x为x所对应的命题函数。则'非-phi-x(x)'，也即"phi-x对于x不成立",是一个在这个对应中没有出现的命题函数；因为它在phi-x假的时候为真，在phi-x真的时候为假，因此它和任何一个x所对应的phi-x不同”。他在康托尔之后贡献了这个想法。

Ernst Zermelo 在他 1908 年发表的成为现代集合论基础的论文《Untersuchungen über die Grundlagen der Mengenlehre I》中有一个定理(他称之为康托尔定理)同于上面的论证形式。请参见Zermelo 集合论。

康托尔定理的一个推论请参见beth 数。