康托爾定理

康托爾定理(Cantor's Theorem)：用P(X)記X的一切子集構成的集，用cardX表示X的勢，則cardX < cardP(X)。康托爾定理指的是在Zermelo-Fränkel集合論中，聲稱任何集合A的冪集（所有子集的集合）的勢嚴格大於A的勢。康托爾定理對於有限集合是明顯的，但是令人驚奇的是它對於無限集合也成立。特別是，可數無限集合的冪集是不可數無限的。要展示康托爾定理的對於無限集合的有效性，只需要測試一下下面證明中無限集合。

基本介紹

• 中文名：康托爾定理
• 外文名：Cantor's Theorem
• 提出者：康托爾
• 提出時間：1891年
• 適用領域範圍：數理科學

證明

設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。任何方式下都是矛盾。

性質

函式為一個滿射，若且唯若存在一個函式滿足等於上的恆等函式。（這個陳述等價於選擇公理。）

根據定義，函式為雙射若且唯若它既是滿射也是單射。

如果 是滿射，則是滿射。

如果和皆為滿射，則為滿射。

為滿射，若且唯若給定任意函式滿足，則。

如果為滿射，且是的子集，則，。因此，能被其原像復原。

任意函式都可以分解為一個適當的滿射和單射，使得。

如果為滿射函式，則在基數意義上至少有跟一樣多的元素。

如果和皆為具有相同元素數的有限集合，則是滿射若且唯若是單射。

發展簡史

康托爾在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"中有一個定理（他稱之為康托爾定理）同於上面的論證形式。