康托尔定理

康托尔定理指的是在ZFC集合论中，声称任何集合A的幂集（所有子集的集合）的势严格大于A的势。康托尔定理对于有限集合是明显的（有限的集合的幂集的个数为集合个数 $n$ 的 $2^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$ 的假设是不成立的。证明完毕

对角线证明法

集合的个数为可数无限时。不失一般性，我们用自然数构造的集合来讨论。

要证明：对于自然数 N 和它的幂集 $\mathcal{P}(N)$，不存在一个双射函数 $f:N\to\mathcal{P}(N)$

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

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

我们以这样的表构造集合$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}(N)$ 的势和自然数的势不相等。依照幂集合的定义$\mathcal{P}(N)$包含所有自然数的子集，所以我们得到$\mathcal{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不同”。他在康托尔之后贡献了这个想法。

恩斯特·策梅洛在他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.

参见

• 康托尔悖论