康托爾定理

康托爾定理

康托爾提出的定理
康托爾定理(Cantor's Theorem):用P(X)記X的一切子集構成的集,用cardX表示X的勢,則cardX < cardP(X)。康托爾定理指的是在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還是y∉B。如果y∈B,則y∈f(y),但是通過B的定義,這蘊涵了y∉B。在另一方面,如果yB,則yf(y)并因此y∈B。任何方式下都是矛盾。

性質

函數f:X→Y為一個滿射,當且僅當存在一個函數g:Y→X滿足等于Y上的恒等函數。(這個陳述等價于選擇公理。)

根據定義,函數為雙射當且僅當它既是滿射也是單射。

如果是滿射,則f是滿射。

如果f和g皆為滿射,則為滿射。

f:X→Y為滿射,當且僅當給定任意函數g,h:Y→Z滿足,則g=h。

如果f:X→Y為滿射,且B是Y的子集,則,。因此,B能被其原像複原。

任意函數h:X→Y都可以分解為一個适當的滿射f和單射g,使得

如果f:X→Y為滿射函數,則X在基數意義上至少有跟Y一樣多的元素。

如果X和Y皆為具有相同元素數的有限集合,則f:X→Y是滿射當且僅當f是單射。

發展簡史

康托爾在1891年發表的論文"Über eine elementare Frage der Mannigfaltigkeitslehre"中本質上給出了這個證明,實數不可數的對角論證法也首次在這裡出現。在這個論文中給出的這個論證的版本使用的是在集合上的指示函數而不是集合子集。他證明了如果f是定義在X上的函數,它的值是在X上的二值函數,則二值函數G(x)=1−f(x)(x)不在f的值域中。

羅素在《數學原理》(1903,section348)中給出了一個非常類似的證明,在這裡他證明了命題函數要比對象多。“假設所有對象和所有和它們相關的命題函數之間有一種對應,并令phi-x為x所對應的命題函數。則'非-phi-x(x)',也即"phi-x對于x不成立",是一個在這個對應中沒有出現的命題函數;因為它在phi-x假的時候為真,在phi-x真的時候為假,因此它和任何一個x所對應的phi-x不同”。他在康托爾之後貢獻了這個想法。

恩斯特·策梅洛在他1908年發表的成為現代集合論基礎的論文"Untersuchungen über die Grundlagen der Mengenlehre I"中有一個定理(他稱之為康托爾定理)同于上面的論證形式。

相關詞條

相關搜索

其它詞條