[科普中國(guó)]-康托爾定理

康托爾****定理(Cantor's Theorem)：用P(X)記X的一切子集構(gòu)成的集，用cardX表示X的勢(shì)，則cardX 。康托爾定理指的是在Zermelo-Fr?nkel集合論中，聲稱(chēng)任何集合A的冪集（所有子集的集合）的勢(shì)嚴(yán)格大于A的勢(shì)?？低袪柖ɡ韺?duì)于有限集合是明顯的，但是令人驚奇的是它對(duì)于無(wú)限集合也成立。特別是，可數(shù)無(wú)限集合的冪集是不可數(shù)無(wú)限的。要展示康托爾定理的對(duì)于無(wú)限集合的有效性，只需要測(cè)試一下下面證明中無(wú)限集合。

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

。

要證明B不在f的像中，假設(shè)B在f的像中。那么對(duì)于某個(gè)y∈A，我們有f(y) =B?，F(xiàn)在考慮y∈B還是yB。如果y∈B，則y∈f(y)，但是通過(guò)B的定義，這蘊(yùn)涵了yB。在另一方面，如果yB，則yf(y)并因此y∈B。任何方式下都是矛盾。

性質(zhì)函數(shù)為一個(gè)滿射，當(dāng)且僅當(dāng)存在一個(gè)函數(shù)滿足等于上的恒等函數(shù)。（這個(gè)陳述等價(jià)于選擇公理。）

根據(jù)定義，函數(shù)為雙射當(dāng)且僅當(dāng)它既是滿射也是單射。

如果 是滿射，則是滿射。

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

為滿射，當(dāng)且僅當(dāng)給定任意函數(shù)滿足，則。

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

任意函數(shù)都可以分解為一個(gè)適當(dāng)?shù)臐M射和單射，使得。

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

如果和皆為具有相同元素?cái)?shù)的有限集合，則是滿射當(dāng)且僅當(dāng)是單射。

發(fā)展簡(jiǎn)史康托爾在1891年發(fā)表的論文"über eine elementare Frage der Mannigfaltigkeitslehre"中本質(zhì)上給出了這個(gè)證明，實(shí)數(shù)不可數(shù)的對(duì)角論證法也首次在這里出現(xiàn)。在這個(gè)論文中給出的這個(gè)論證的版本使用的是在集合上的指示函數(shù)而不是集合子集。他證明了如果f是定義在X上的函數(shù)，它的值是在X上的二值函數(shù)，則二值函數(shù)G(x) = 1 ?f(x)(x) 不在f的值域中。

羅素在《數(shù)學(xué)原理》(1903, section 348)中給出了一個(gè)非常類(lèi)似的證明，在這里他證明了命題函數(shù)要比對(duì)象多?！凹僭O(shè)所有對(duì)象和所有和它們相關(guān)的命題函數(shù)之間有一種對(duì)應(yīng)，并令phi-x為x所對(duì)應(yīng)的命題函數(shù)。則'非-phi-x(x)'，也即"phi-x對(duì)于x不成立",是一個(gè)在這個(gè)對(duì)應(yīng)中沒(méi)有出現(xiàn)的命題函數(shù)；因?yàn)樗趐hi-x假的時(shí)候?yàn)檎?，在phi-x真的時(shí)候?yàn)榧?，因此它和任何一個(gè)x所對(duì)應(yīng)的phi-x不同”。他在康托爾之后貢獻(xiàn)了這個(gè)想法。

恩斯特·策梅洛在他 1908 年發(fā)表的成為現(xiàn)代集合論基礎(chǔ)的論文"Untersuchungen über die Grundlagen der Mengenlehre I"中有一個(gè)定理（他稱(chēng)之為康托爾定理）同于上面的論證形式。2

本詞條內(nèi)容貢獻(xiàn)者為:

任毅如 - 副教授 - 湖南大學(xué)