康托尔定理

ZFC集合论中，康托尔定理（）斷言對任意集合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.

参见

• 康托尔悖论