康托尔定理

ZFC集合论中，康托尔定理（英语：Cantor's theorem）断言对任意集合$A$，其幂集（所有子集的集合）的势严格大于$A$自身的势。

绿色箭头代表可能的映射关系，红色箭头代表不可能的映射关系。圆圈表示集合或子集。

对于有限集合该结论是显然的。对势为$n$的有限集合，其幂集的势为$2^{n}$，对所有非负整数$n$，$2^{n}>n$，因此不存在从原集合到其幂集的满射。

但更重要的是对任意无限集合，康托尔定理也成立。这同时证明了，可数无限集合构造的幂集的基数是严格大于任何可数无限，以此创造出不可数无限的概念。

归谬法证明

证明：对任何的集合 $S$，它的元素与幂集 ${\mathcal {P}}(S)$ 的元素之间不可能存在一一对应（双射）的关系。

（利用归谬法）假设：可以找到一个集合 $A$ 和一个函数$f:A\to {\mathcal {P}}(A)$，它使得两个集合之间的全部元素都配对且仅配对一次。

对于 $A$ 中的任意元素$s$，显然$s$ 或者属于$f(s)$或者不属于$f(s)$。

我们假设 $T=\{x\in A\,|\,x\notin f(x)\}$，则 $T\in {\mathcal {P}}(A)$；由假设知存在 $x$ 使得 $f(x)=T$.

（1）如果$x\in T$，由 $T$ 的定义，$x\notin f(x)$，既然$f(x)=T$，那就推得 $x\notin T$.

（2）如果$x\notin T$，由 $T$ 的定义，$x\in f(x)$，既然$f(x)=T$，那就推得 $x\in T$.

两者都矛盾。因此我们对于存在函数 $f$ 的假设是不成立的。证明完毕

对角线证明法

集合的个数为可数无限时可以用对角线法证明康托尔定理。不失一般性地，我们考虑自然数的集合。

欲证：不存在从自然数集$\mathbb {N}$到它的幂集${\mathcal {P}}(\mathbb {N} )$的双射函数 $f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )$。

（利用归谬法）假设：存在从自然数集$\mathbb {N}$到它的幂集 ${\mathcal {P}}(\mathbb {N} )$的双射函数 $f:\mathbb {N} \to {\mathcal {P}}(\mathbb {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} )$

虽然在集合中，元素的顺序不重要，但我们假设从左到右以由小到大的方式记录幂集合中的元素，以便讨论。

通过这个“对应表”，我们可以构造一个自然数集合$W$，构造方式为：

当左侧的自然数“属于”它对应的幂集合，我们就在 $W$ 里面记录“不存在”这个自然数。

反之当左侧的自然数“不属于”它对应的幂集合，我们就在 $W$ 里面记录“存在”这个自然数。

以上表为例：

$1\Longleftrightarrow \{4,5\},1\notin \{4,5\}$，我们定义 $1\in W$ 。（显然 $W$与这个自然数集合不同）

$2\Longleftrightarrow \{1,2,3\},2\in \{1,2,3\}$，我们定义 $2\notin W$。（显然 $W$与这个自然数集合不同）

......

以此方式构造的$W$和表中每一个自然数集合都不同，所以它不可能在表中。

但$W$是自然数构成的集合，所以它必然在表中，矛盾。

因此假设的$f$不存在，说明 ${\mathcal {P}}(\mathbb {N} )$ 的势和自然数的势不相等。

虽然用归谬法没能得知哪个集合的势更大，但由于${\mathcal {P}}(\mathbb {N} )$包含所有自然数的单元素集合$\{n\}$，这相当于幂集${\mathcal {P}}(\mathbb {N} )$中包含一份所有自然数的“复制”，所以${\mathcal {P}}(\mathbb {N} )$ 的基数大于$\mathbb {N}$的基数。

综上，${\mathcal {P}}(\mathbb {N} )$ 的基数严格大于$\mathbb {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不同”。他在康托尔之后贡献了这个想法。

恩斯特·策梅洛在他1908年发表的成为现代集合论基础的论文《Untersuchungen über die Grundlagen der Mengenlehre I》中有一个定理（他称之为康托尔定理）同于上面的论证形式。

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

参考资料

来源

• Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
• Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.

参见

• 康托尔悖论