康托爾公理

康托爾公理指的是在Zermelo-Fränkel集合論中，聲稱任何集合A的冪集（所有子集的集合）的勢嚴格大於A的勢。康托爾定理對於有限集合是明顯的，但是令人驚奇的是它對於無限集合也成立。特別是，可數無限集合的冪集是不可數無限的。要展示康托爾定理的對於無限集合的有效性，只需要測試一下下面證明中無限集合。

基本介紹

• 中文名：康托爾公理
• 外文名：Cantor's theorem
• 學科：數學

證明

設f是從A到A的冪集的任何函式。必須證明這個f必定不是滿射的。要如此，展示一個A的子集不在f的像中就足夠了。這個子集是

要證明B不在f的像中，假設B在f的像中。那么對於某個y∈A，我們有f(y) =B。現在考慮y∈B還是yB。如果y∈B，則y∈f(y)，但是通過B的定義，這蘊涵了yB。在另一方面，如果yB，則yf(y)並因此y∈B。任何方式下都是矛盾。

在X是可數無限時對證明的詳細解釋

要掌握這個證明，讓我們檢查X是可數無限時的特殊情況。不失去一般性，我們採用自然數集合，X=N= {1, 2, 3,...}。

假設N雙射於它的冪集P(N)。讓我們看一個樣例P(N)：

P(N)包含無限的N的子集，比如所有偶數的集合{2, 4, 6,...}，還有空集。

現在讓我們看一下P(N)的元素的樣子，我們嘗試給每個N的元素配對上每個P(N)的元素來證實這些無限集合是雙射的。換句話說，我們將嘗試對N的每個元素配對上來無限集合P(N)的元素，使得這兩個集合中沒有元素是未配對的。配對元素的嘗試將是如下樣子的：

某些自然數被配對上不包含它們的子集。例如，在我們的例子中，數1被配對上子集{4, 5}。其他自然被配對上包含它們的子集。比如數2被配對上子集{1, 2, 3}。

使用這個想法，讓我們建造一個自然數的特殊集合。這個集合將提供我們所求索的矛盾。設D是被配對上不包含它們的子集的所有自然數的集合。通過定義，我們的冪集P(N)必定包含這個集合D作為元素。所以，D必定被配對上某個自然數。但是這導致了一個問題 -- 哪個自然數和D配對呢?它不能是D的成員，因為D被特殊構造為只包含那些不配對上包含它們的子集的自然數。在另一方面，如果配對於D的自然數不包含在D中，則再次通過D的定義，它必定包含在D。

這是矛盾因為這個自然數不能同時在D的內部和外部。所以，沒有自然數可以配對於D，而我們的最初假定在N和P(N)之間有雙射是有矛盾的。

通過這個反證法我們證明了N的勢和P(N)的勢不能相等。我們還知道了P(N)的勢不能小於N的勢，因為根據定義P(N)包含所有單元素集合，而這些單元素集合形成在P(N)內的N的複製品。所以只剩下一個可能，就是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數。