康托爾定理

康托爾定理指的是在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.

參見

• 康托爾悖論