康托爾定理

綠色箭頭代表可能的映射關係，紅色箭頭代表不可能的映射關係。圓圈表示集合或子集。

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.

參見

• 康托爾悖論