查看“︁康托尔定理”︁的源代码

[[File:Cantor's theorem visual.png|thumb|绿色箭头代表可能的映射关系，红色箭头代表不可能的映射关系。圆圈表示集合或子集。]]
[[ZFC|ZFC集合论]]中，'''康托尔定理'''（{{lang-en|Cantor's theorem}}）斷言對任意集合<math>A</math>，其[[幂集]]（所有[[子集]]的[[集合 (数学)|集合]]）的[[势_(数学)|势]]严格大于<math>A</math>自身的势。

对于[[有限集合]]該結論是顯然的。對勢為<math>n</math>的有限集合，其冪集的勢為<math>2^n</math>，對所有[[非負整數]]<math>n</math>，<math>2^n > n</math>，因此不存在從原集合到其冪集的[[滿射]]。

但更重要的是對任意[[无限集合]]，康托爾定理也成立。這同時證明了，[[可数集合|可数无限]]集合構造的[[冪集]]的基數是嚴格大於任何可数无限，以此創造出[[不可數集|不可數無限]]的概念。

== 歸謬法證明 ==
證明：對任何的集合 <math>S</math>，它的元素與冪集 <math>\mathcal{P}(S)</math> 的元素之間不可能存在一一對應（雙射）的關係。

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

對於 <math>A</math> 中的任意元素<math>s</math>，顯然<math>s</math> 或者屬於<math>f(s)</math>或者不屬於<math>f(s)</math>。

我們假設 <math> T=\{x \in A \, | \, x \notin f(x)\}</math>，则 <math>T\in \mathcal{P}(A)</math>；由假设知存在 <math> x</math> 使得 <math> f(x)=T</math>.

（1）如果<math> x \in T</math>，由 <math>T</math> 的定義，<math> x \notin f(x)</math>，既然<math> f(x)=T</math>，那就推得 <math> x \notin T</math>.

（2）如果<math> x \notin T</math>，由 <math>T</math> 的定義，<math> x \in f(x)</math>，既然<math> f(x)=T</math>，那就推得 <math> x \in T</math>.

兩者都矛盾。因此我們對於存在函數 <math>f</math> 的假設是不成立的。證明完畢<ref>{{Cite book|title=数学桥——对高等数学的一次观赏之旅 ：1.1.7 超越無限大|last=Stenphen Fletcher Hewson|first=数学桥——对高等数学的一次观赏之旅 ：1.1.7 超越無限大|publisher=上海科技教育出版社|year=2010/8/7|isbn=978-7-5428-4981-6|location=|pages=p.12}}</ref>

== 對角線證明法 ==
集合的個數為[[可数无限]]时可以用對角線法證明康托爾定理。不失一般性地，我们考慮[[自然数]]的集合。

欲證：不存在從自然數集<math>\mathbb{N}</math>到它的[[冪集]]<math>\mathcal{P}(\mathbb{N})</math>的[[双射]]函數 <math>f:\mathbb{N} \to \mathcal{P}(\mathbb{N})</math>。

（利用歸謬法）假設：存在從自然數集<math>\mathbb{N}</math>到它的冪集 <math>\mathcal{P}(\mathbb{N})</math>的双射函數 <math>f:\mathbb{N} \to\mathcal{P}(\mathbb{N})</math>，

那麼我們就可以依序將所有兩個集合之間的「對應」如下列出（這裡的數字只是示例），表中含有所有「自然數構成的集合」：

<math>X\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})</math>

雖然在集合中，元素的順序不重要，但我們假設從左到右以由小到大的方式記錄冪集合中的元素，以便討論。

通過這個「對應表」，我們可以構造一個自然數集合<math>W</math>，構造方式為：

當左側的自然數「屬於」它對應的冪集合，我們就在  <math>W</math> 裡面記錄「不存在」這個自然數。

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


以上表為例：

<math>1 \Longleftrightarrow \{4, 5\},
1 \notin \{4, 5\}</math>，我們定義 <math>1 \in W</math> 。（顯然 <math>W</math>與這個自然數集合不同）

<math>2 \Longleftrightarrow \{1,2,3\},
2 \in \{1,2,3\}</math>，我們定義 <math>2 \notin W</math>。（顯然 <math>W</math>與這個自然數集合不同）

...... 


以此方式構造的<math>W</math>和表中每一個自然數集合都不同，所以它不可能在表中。

但<math>W</math>是自然數構成的集合，所以它必然在表中，矛盾。

因此假設的<math>f</math>不存在，說明 <math>\mathcal{P}(\mathbb{N})</math> 的[[势 (数学)|势]]和自然數的势不相等。

雖然用歸謬法沒能得知哪個集合的勢更大，但由於<math>\mathcal{P}(\mathbb{N})</math>包含所有自然數的[[單元素集合]]<math>\{n\}</math>，這相當於冪集<math>\mathcal{P}(\mathbb{N})</math>中包含一份所有自然數的「複製」，所以<math>\mathcal{P}(\mathbb{N})</math> 的基數大于<math>\mathbb{N}</math>的基數。

綜上，<math>\mathcal{P}(\mathbb{N})</math> 的基數嚴格大于<math>\mathbb{N}</math>的基數，證畢。

== 历史 ==
[[格奥尔格·康托尔]]在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》中有一个定理（他称之为康托尔定理）同于上面的论证形式。

康托尔定理的一个推论请参见[[ℶ_數|beth数]]。

== 参考资料 ==
=== 引用 ===
{{reflist}}
=== 来源 ===
* Paul Halmos, ''Naive set theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
* Jech, Thomas, 2003. ''Set Theory: The Third Millennium Edition, Revised and Expanded''. Springer. ISBN 3-540-44085-2.

== 参见 ==
* [[康托尔悖论]]

{{数理逻辑}}
{{集合论}}

[[Category:基数]]
[[Category:数学定理|K]]