康托爾定理- 維基百科，自由的百科全書

康托爾定理[編輯] · 康托爾定理指的是在ZFC集合論中，聲稱任何集合A的冪集（所有子集的集合）的勢嚴格大於A的勢。

· 證明：對任何的集合 · （利用歸謬法）假設：可以找到一個 ... 康托爾定理 維基百科，自由的百科全書 跳至導覽 跳至搜尋 康托爾定理指的是在ZFC集合論中，聲稱任何集合A的冪集（所有子集的集合）的勢嚴格大於A的勢。

康托爾定理對於有限集合是明顯的（有限的集合的冪集的個數為集合個數 n {\displaystylen} 的 2 n {\displaystyle2^{n}} ），但是令人驚奇的是它對於無限集合也成立。

同時證明了，可數無限集合構造的冪集的基數是不可數無限，以此創造出出不可數無限的概念。

目次 1歸謬法證明 2對角線證明法 3歷史 4引用 5參見 歸謬法證明[編輯] 證明：對任何的集合 S {\displaystyleS} ，它的元素與冪集 P ( S ) {\displaystyle{\mathcal{P}}(S)} 的元素之間不可能存在一一對應（雙射）的關係。

（利用歸謬法）假設：可以找到一個集合 A {\displaystyleA} 和一個函數 f : A → P ( A ) {\displaystylef:A\to{\mathcal{P}}(A)} ，它使得兩個集合之間的全部元素都配對且僅配對一次。

對於 A {\displaystyleA} 中的任意元素 s {\displaystyles} ，顯然 s {\displaystyles} 或者屬於 f ( s ) {\displaystylef(s)} 或者不屬於 f ( s ) {\displaystylef(s)} 。

我們假設 T = { x ∈ A | x ∉ f ( x ) } {\displaystyleT=\{x\inA\,|\,x\notinf(x)\}} ，則 T ∈ P ( A ) {\displaystyleT\in{\mathcal{P}}(A)} ；由假設知存在 x {\displaystylex} 使得 f ( x ) = T {\displaystylef(x)=T} . （1）如果 x ∈ T {\displaystylex\inT} ，由 T {\displaystyleT} 的定義， x ∉ f ( x ) {\displaystylex\notinf(x)} ，既然 f ( x ) = T {\displaystylef(x)=T} ，那就推得 x ∉ T {\displaystylex\notinT} . （2）如果 x ∉ T {\displaystylex\notinT} ，由 T {\displaystyleT} 的定義， x ∈ f ( x ) {\displaystylex\inf(x)} ，既然 f ( x ) = T {\displaystylef(x)=T} ，那就推得 x ∈ T {\displaystylex\inT} . 兩者都矛盾。

因此我們對於存在函數 f {\displaystylef} 的假設是不成立的。

證明完畢[1] 對角線證明法[編輯] 集合的個數為可數無限時。

不失一般性，我們用自然數構造的集合來討論。

要證明：對於自然數N和它的冪集 P ( N ) {\displaystyle{\mathcal{P}}(N)} ，不存在一個雙射函數 f : N → P ( N ) {\displaystylef:N\to{\mathcal{P}}(N)} （利用歸謬法）假設：自然數N和它的冪集 P ( N ) {\displaystyle{\mathcal{P}}(N)} ，存在一個雙射函數 f : N → P ( N ) {\displaystylef:N\to{\mathcal{P}}(N)} 那麼我們就可以有序的將所有「對應」表列如下（這裡的數字只是示例），表中含有所有「自然數構成的集合」： X { 1 ⟺ { 4 , 5 } 2 ⟺ { 1 , 2 , 3 } 3 ⟺ { 4 , 5 , 6 } 4 ⟺ { 1 , 3 , 5 } ⋮ ⋮ ⋮ } P ( N ) {\displaystyleX{\begin{Bmatrix}1&\Longleftrightarrow&\{4,5\}\\2&\Longleftrightarrow&\{1,2,3\}\\3&\Longleftrightarrow&\{4,5,6\}\\4&\Longleftrightarrow&\{1,3,5\}\\\vdots&\vdots&\vdots\end{Bmatrix}}P(\mathbb{N})} 雖然元素的順序不重要，不過我們假設從左到右以由小到大的方式記錄冪集合中的元素，方便討論。

我們以這樣的表構造集合 W {\displaystyleW} ，構造方式為： 當左側的自然數「屬於」它對應的冪集合，我們就在 W {\displaystyleW} 裡面記錄「不存在」這個自然數。

反之當左側的自然數「不屬於」它對應的冪集合，我們就在 W {\displaystyleW} 裡面記錄「存在」這個自然數。

以上表為例： 1 ⟺ { 4 , 5 } , 1 ∉ { 4 , 5 } {\displaystyle1\Longleftrightarrow\{4,5\},1\notin\{4,5\}} ，我們定義 1 ∈ W {\displaystyle1\inW} 。

（顯然 W {\displaystyleW} 不可能和這一項的冪集合相同） 2 ⟺ { 1 , 2 , 3 } , 2 ∈ { 1 , 2 , 3 } {\displaystyle2\Longleftrightarrow\{1,2,3\},2\in\{1,2,3\}} ，我們定義 2 ∉ W {\displaystyle2\notinW} 。

（顯然 W {\displaystyleW} 不可能和這一項的冪集合相同） ...... 以此規則構造的 W {\displaystyleW} 和表中每一個冪集合都不同，所以它不可能在表中。

W {\displaystyleW} 是自然數構成的集合，所以它必然在表中。

得到矛盾。

假設的 f {\displaystylef} 並不成立，說明 P ( N ) {\displaystyle{\mathcal{P}}(N)} 的勢和自然數的勢不相等。

依照冪集合的定義 P ( N ) {\displaystyle{\mathcal{P}}(N)} 包含所有自然數的子集，所以我們得到 P ( N ) {\displaystyle{\mathcal{P}}(N)} 的基數大於N的基數。

證明完畢。

歷史[編輯] 康托爾在1891年發表的論文《ÜbereineelementareFragederMannigfaltigkeitslehre》中本質上給出了這個證明，實數不可數的對角論證法也首次在這裡出現。

在這個論文中給出的這個論證的版本使用的是在集合上的指示函數而不是集合子集。

他證明了如果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überdieGrundlagenderMengenlehreI》中有一個定理（他稱之為康托爾定理）同於上面的論證形式。

康托爾定理的一個推論請參見beth數。

引用[編輯] PaulHalmos,Naivesettheory.Princeton,NJ:D.VanNostrandCompany,1960.ReprintedbySpringer-Verlag,NewYork,1974.ISBN0-387-90092-6(Springer-Verlagedition). Jech,Thomas,2003.SetTheory:TheThirdMillenniumEdition,RevisedandExpanded.Springer.ISBN3-540-44085-2. 參見[編輯] 康托爾悖論 閱論編集合論公理 選擇 可數 相關（英語：Axiomofdependentchoice） 外延 無窮 配對 冪集 正則性 併集 馬丁公理（英語：Martin'saxiom） 公理模式 替代 分類 運算 笛卡兒積 德摩根定律 交集 冪集 補集 對稱差 併集 概念方法 勢 基數（大基數） 類 可構造全集（英語：Constructibleuniverse） 連續統假設 對角論證法 元素 有序對 多元組 集合族 力迫 一一對應 序數 超限歸納法 文氏圖 集合類型 可數集 空集 有限集合（繼承有限集合） 模糊集 無限集合 遞歸集合 子集 傳遞集合 不可數集 泛集（英語：Universalset） 理論 可替代的集合論 集合論 樸素集合論 康托爾定理 策梅洛 廣義（英語：Generalsettheory） 數學原理 新基礎 策梅洛-弗蘭克 馮諾伊曼-博內斯-哥德爾 Morse–Kelley（英語：Morse–Kelleysettheory） 克里普克–普拉特克（英語：Kripke–Plateksettheory） 塔斯基–格羅滕迪克（英語：Tarski–Grothendiecksettheory） 悖論（英語：Paradoxesofsettheory）問題 羅素悖論 薩斯林問題（英語：Suslin'sproblem） ZFC系統無法確定的命題列表 集合論者 亞伯拉罕·弗蘭克爾（英語：AbrahamFraenkel） 伯特蘭·羅素 恩斯特·策梅洛 格奧爾格·康托爾 約翰·馮·諾伊曼 庫爾特·哥德爾 盧菲特·澤德 保爾·貝爾奈斯（英語：PaulBernays） 保羅·寇恩 理察·戴德金 托馬斯·耶赫（英語：ThomasJech） 威拉德·蒯因 ^StenphenFletcherHewson,數學橋——對高等數學的一次觀賞之旅：1.1.7超越無限大.数学桥——对高等数学的一次观赏之旅：1.1.7超越無限大.上海科技教育出版社.2010/8/7:p.12.ISBN 978-7-5428-4981-6. 請檢查|date=中的日期值(幫助)引文格式1維護：冗餘文本(link) 取自「https://zh.wikipedia.org/w/index.php?title=康托尔定理&oldid=66005978」 分類：基數數學定理隱藏分類：使用ISBN魔術連結的頁面引文格式1錯誤：日期引文格式1維護：冗餘文本 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 已展開 已摺疊 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 已展開 已摺疊 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他專案 維基共享資源 其他語言 العربيةAsturianuCatalàČeštinaDeutschΕλληνικάEnglishEspañolفارسیSuomiFrançaisGalegoעבריתMagyarItaliano日本語ქართული한국어LombardNederlandsNorsknynorskNorskbokmålPolskiPortuguêsRomânăРусскийSimpleEnglishСрпски/srpskiSvenskaไทยTürkçeУкраїнськаTiếngViệt文言粵語 編輯連結