綠色箭頭代表可能的映射關係,紅色箭頭代表不可能的映射關係。圓圈表示集合或子集。
ZFC集合論 中,康托爾定理 (英語:Cantor's theorem )斷言對任意集合
A
{\displaystyle A}
,其冪集 (所有子集 的集合 )的勢 嚴格大於
A
{\displaystyle A}
自身的勢。
對於有限集合 該結論是顯然的。對勢為
n
{\displaystyle n}
的有限集合,其冪集的勢為
2
n
{\displaystyle 2^{n}}
,對所有非負整數
n
{\displaystyle n}
,
2
n
>
n
{\displaystyle 2^{n}>n}
,因此不存在從原集合到其冪集的滿射 。
但更重要的是對任意無限集合 ,康托爾定理也成立。這同時證明了,可數無限 集合構造的冪集 的基數是嚴格大於任何可數無限,以此創造出不可數無限 的概念。
歸謬法證明
證明:對任何的集合
S
{\displaystyle S}
,它的元素與冪集
P
(
S
)
{\displaystyle {\mathcal {P}}(S)}
的元素之間不可能存在一一對應(雙射)的關係。
(利用歸謬法)假設:可以找到一個集合
A
{\displaystyle A}
和一個函數
f
:
A
→
P
(
A
)
{\displaystyle f:A\to {\mathcal {P}}(A)}
,它使得兩個集合之間的全部元素都配對且僅配對一次。
對於
A
{\displaystyle A}
中的任意元素
s
{\displaystyle s}
,顯然
s
{\displaystyle s}
或者屬於
f
(
s
)
{\displaystyle f(s)}
或者不屬於
f
(
s
)
{\displaystyle f(s)}
。
我們假設
T
=
{
x
∈
A
|
x
∉
f
(
x
)
}
{\displaystyle T=\{x\in A\,|\,x\notin f(x)\}}
,則
T
∈
P
(
A
)
{\displaystyle T\in {\mathcal {P}}(A)}
;由假設知存在
x
{\displaystyle x}
使得
f
(
x
)
=
T
{\displaystyle f(x)=T}
.
(1)如果
x
∈
T
{\displaystyle x\in T}
,由
T
{\displaystyle T}
的定義,
x
∉
f
(
x
)
{\displaystyle x\notin f(x)}
,既然
f
(
x
)
=
T
{\displaystyle f(x)=T}
,那就推得
x
∉
T
{\displaystyle x\notin T}
.
(2)如果
x
∉
T
{\displaystyle x\notin T}
,由
T
{\displaystyle T}
的定義,
x
∈
f
(
x
)
{\displaystyle x\in f(x)}
,既然
f
(
x
)
=
T
{\displaystyle f(x)=T}
,那就推得
x
∈
T
{\displaystyle x\in T}
.
兩者都矛盾。因此我們對於存在函數
f
{\displaystyle f}
的假設是不成立的。證明完畢[ 1]
對角線證明法
集合的個數為可數無限 時可以用對角線法證明康托爾定理。不失一般性地,我們考慮自然數 的集合。
欲證:不存在從自然數集
N
{\displaystyle \mathbb {N} }
到它的冪集
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
的雙射 函數
f
:
N
→
P
(
N
)
{\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
。
(利用歸謬法)假設:存在從自然數集
N
{\displaystyle \mathbb {N} }
到它的冪集
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
的雙射函數
f
:
N
→
P
(
N
)
{\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
,
那麼我們就可以依序將所有兩個集合之間的「對應」如下列出(這裏的數字只是示例),表中含有所有「自然數構成的集合」:
X
{
1
⟺
{
4
,
5
}
2
⟺
{
1
,
2
,
3
}
3
⟺
{
4
,
5
,
6
}
4
⟺
{
1
,
3
,
5
}
⋮
⋮
⋮
}
P
(
N
)
{\displaystyle 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} )}
雖然在集合中,元素的順序不重要,但我們假設從左到右以由小到大的方式記錄冪集合中的元素,以便討論。
通過這個「對應表」,我們可以構造一個自然數集合
W
{\displaystyle W}
,構造方式為:
當左側的自然數「屬於」它對應的冪集合,我們就在
W
{\displaystyle W}
裏面記錄「不存在」這個自然數。
反之當左側的自然數「不屬於」它對應的冪集合,我們就在
W
{\displaystyle W}
裏面記錄「存在」這個自然數。
以上表為例:
1
⟺
{
4
,
5
}
,
1
∉
{
4
,
5
}
{\displaystyle 1\Longleftrightarrow \{4,5\},1\notin \{4,5\}}
,我們定義
1
∈
W
{\displaystyle 1\in W}
。(顯然
W
{\displaystyle W}
與這個自然數集合不同)
2
⟺
{
1
,
2
,
3
}
,
2
∈
{
1
,
2
,
3
}
{\displaystyle 2\Longleftrightarrow \{1,2,3\},2\in \{1,2,3\}}
,我們定義
2
∉
W
{\displaystyle 2\notin W}
。(顯然
W
{\displaystyle W}
與這個自然數集合不同)
......
以此方式構造的
W
{\displaystyle W}
和表中每一個自然數集合都不同,所以它不可能在表中。
但
W
{\displaystyle W}
是自然數構成的集合,所以它必然在表中,矛盾。
因此假設的
f
{\displaystyle f}
不存在,說明
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
的勢 和自然數的勢不相等。
雖然用歸謬法沒能得知哪個集合的勢更大,但由於
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
包含所有自然數的單元素集合
{
n
}
{\displaystyle \{n\}}
,這相當於冪集
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
中包含一份所有自然數的「複製」,所以
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
的基數大於
N
{\displaystyle \mathbb {N} }
的基數。
綜上,
P
(
N
)
{\displaystyle {\mathcal {P}}(\mathbb {N} )}
的基數嚴格大於
N
{\displaystyle \mathbb {N} }
的基數,證畢。
歷史
格奧爾格·康托爾 在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數 。
參考資料
引用
^ Stenphen Fletcher Hewson, 數學橋——對高等數學的一次觀賞之旅 :1.1.7 超越無限大. 数学桥——对高等数学的一次观赏之旅 :1.1.7 超越無限大. 上海科技教育出版社. 2010/8/7: p.12. ISBN 978-7-5428-4981-6 .
來源
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 .
參見