[科普中國]-康托爾定理

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

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

。

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

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

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

如果 是滿射，則是滿射。

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

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

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

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

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

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

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

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

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

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

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