6.2 Cantor 定理、連續統與選擇公理

上一篇筆記用雙射和單射比較集合大小。這一篇從本章第一個真正的大集合定理 開始：Cantor 定理。它說明任何集合都嚴格小於它的冪集。

這個結果立即給出實數不可數的證明。同一部分隨後引入兩個基礎性命題： 連續統假設與選擇公理。本課程不證明它們背後深層的元數學結果，但會清楚說 明它們在理論中扮演甚麼角色。

冪集與 Cantor 定理

定義

冪集記號

對集合 $X$，記號 $2^X$ 表示 $X$ 的所有子集所成的集合，即 $X$ 的冪集。

因此

$$T\in 2^X$$

正是說 $T\subseteq X$。

記號 $2^X$ 帶有提示性：若 $X$ 有 $n$ 個元素，則冪集有 $2^n$ 個子集。 Cantor 定理說的不只是有限情況，而是對所有集合都成立。

對空集，這個記號已經說明了一個重要的起點：

$$2^\varnothing=\{\varnothing\}.$$

空集只有一個子集，就是空集本身。因此有限集合的計數模式 $|2^X|=2^{|X|}$ 從 $2^0=1$ 開始。下面的定理更強：即使集合不是有限 的，仍然可以嚴格比較集合與其冪集的基數。

定理

Cantor 定理

設 $X$ 為集合。則

$$|X|\lt |2^X|.$$

證明分兩部分。

首先，有單射

$$X\to 2^X,\qquad x\mapsto \{x\}.$$

所以 $|X|\le |2^X|$。

其次，不存在由 $X$ 到 $2^X$ 的雙射。反設 $f:X\to 2^X$ 是雙射。定義對角 集合

$$T=\{x\in X\mid x\notin f(x)\}.$$

因為 $T$ 是 $X$ 的子集，所以 $T\in 2^X$。若 $f$ 是滿射，便存在 $y\in X$ 使

$$f(y)=T.$$

現在考慮 $y$ 是否屬於 $T$。

• 若 $y\in T$，則按 $T$ 的定義有 $y\notin f(y)=T$，矛盾。
• 若 $y\notin T$，則按 $T$ 的定義有 $y\in f(y)=T$，同樣矛盾。

兩種情況也不可能。因此不存在雙射 $X\to 2^X$，所以 $|X|\lt |2^X|$。

這裏的矛盾關鍵在於滿射性。單點映射已經給出了 $|X|\le |2^X|$ 所需的單射；我們不需要證明每個子集都是單點集。為了排除 相等，假設有雙射，於是每個 $X$ 的子集（包括 $T$）都必須等於某個 $f(y)$。關於 $y$ 是否屬於 $T$ 的兩種情況窮盡了所有可能。空集的情況也 沒有例外：當 $X=\varnothing$ 時，$2^\varnothing$ 有一個元素，而從空集 出發的函數不可能滿射到它，因此假設的雙射立即失敗。

證明透視

Cantor 證明必須完成的兩件事

證明有兩個彼此獨立的任務。單點映射證明 $|X|\le |2^X|$。對角集合則在 座標 $x$ 處與 $f(x)$ 取相反的隸屬關係，從而排除相等。在矛盾段落中， $f(y)=T$ 來自滿射性；最後的分類只使用 $T$ 的隸屬定義。

把對角線讀成隸屬關係表

單點映射證明非嚴格不等式。例如 $X=\{a,b\}$ 時，它從四個子集 $\varnothing,\{a\},\{b\},\{a,b\}$ 中選中兩個。對角構造進一步說明， 任何候選映射都不能覆蓋全部子集，即使集合無限也一樣。

下面用 $X=\{a,b,c\}$ 作有限示範。每一行記錄 $f$ 的一個候選值； $1$ 表示欄標題中的元素屬於該子集，$0$ 表示不屬於。前三行的粗體數字 就是對角線上的隸屬判斷。

沿對角線讀到 $1,0,1$，逐個反轉就得到 $0,1,0$，所以 $T=\{b\}$。 它與 $f(a)$ 在 $a$ 處不同，與 $f(b)$ 在 $b$ 處不同，與 $f(c)$ 在 $c$ 處不同。即使其他位置一致，也無法消除這些差異。

對任意集合，同一規則就是 $x\in T$ 當且僅當 $x\notin f(x)$， 不需要給 $X$ 安排數字次序。表格說明構造機制；上面的證明則以完整量詞 處理所有集合，包括空集。

探索對角差異

利用下表追蹤每一行在哪個隸屬判斷上不可能等於對角集合。 注意區分行的指標與欄中的元素。

上一行下一行k = 0

改變每一行的對角項

f(k)	0	1	2	3	4	5
f(0)	1	0	1	0	1	0
f(1)	1	1	0	1	0	1
f(2)	0	0	1	1	0	0
f(3)	1	0	0	0	1	0
f(4)	0	1	0	0	1	1
f(5)	0	0	0	0	0	0
T	0	0	0	1	0	1

$0\in f(0)$, $0\notin T$; $T\ne f(0)$.

$1$ 表示屬於，$0$ 表示不屬於。定義 $T=\{n\in\mathbb N:n\notin f(n)\}$。對任意第 $k$ 行，其對角位與 $T$ 在第 $k$ 位恰好相反，所以 $T\ne f(k)$。六欄只是有限示意；證明適用於每個自然數，並沒有最後一行。

實數不可數

定理

實數不可數

實數集合 $R$ 不可數。特別地，

$$|N|\lt |R|.$$

這裏的證明使用 Cantor 定理，以及一個由 $2^N$ 到 $R$ 的單射。

由 Cantor 定理，

$$|N|\lt |2^N|.$$

所以只需證明

$$|2^N|\le |R|.$$

給定子集 $S\subseteq N$，用一個由 $0$ 和 $1$ 組成的序列來編碼它：

$$a_n= \begin{cases} 1, & n\in S,\\ 0, & n\notin S. \end{cases}$$

然後定義

$$\phi(S)=\sum_{n=0}^{\infty}\frac{a_n}{3^{n+1}}\in [0,1].$$

這把 $N$ 的每個子集（也就是 $2^N$ 的每個元素）送到一個實數。

例題

把 N 的子集編碼成實數

若

$$S=\{0,2,5,\ldots\},$$

則序列開頭為

$$a_0=1,\quad a_1=0,\quad a_2=1,\quad a_3=0,\quad a_4=0,\quad a_5=1.$$

對應的實數開頭可寫成

$$\phi(S)=\frac13+\frac1{3^3}+\frac1{3^6}+\cdots .$$

證明不需要把它轉寫成小數展開；只需要知道這個無窮級數確定了一個實數。

為甚麼用底數 $3$ 而不是 $2$？這裏使用底數 $3$，是為了避免兩個不同的 零一序列被後面的尾項抵消。

若 $S\ne S'$，令 $k$ 為兩個對應序列第一次不同的位置。在第 $k$ 位，兩個 和式相差

$$\frac1{3^{k+1}}.$$

更精確地，後面尾項的總和至多為

$$\sum_{n=k+1}^{\infty}\frac1{3^{n+1}} =\frac1{2\cdot 3^{k+1}},$$

嚴格小於第一個不同項的差距。因此兩個實數不可能相等。故 $\phi$ 是單射， 從而 $|2^N|\le |R|$。

合併得到

$$|N|\lt |2^N|\le |R|,$$

所以 $R$ 不可數。

常見錯誤

證明只需要單射到 R

要證明 $|2^N|\le |R|$，不需要 $\phi$ 命中每個實數。只需要不同的 $N$ 的子集給出不同實數。

例題

底數 3 分離的有限版

取兩個在位置 $k=2$ 首次不同的零一序列。該位置的貢獻大小為 $\frac1{27}$。即使後面每一位都朝着抵消方向取值，尾項總和也是

$$\frac1{3^4}+\frac1{3^5}+\cdots=\frac1{54},$$

只有首個差距的一半，所以首次不同不能被抵消。任意首次不同的位置都可用 同一個幾何級數估計。

連續統假設

假設 — 連續統假設.

連續統假設說：不存在集合 $S$ 使

$$|N|\lt |S|\lt |R|.$$

在知道 $R$ 比 $N$ 大之後，這是一個自然猜想：也許可數無限基數與實數基數 之間沒有中間大小。

這個猜想的地位非常特殊。連續統假設獨立於通常的集合論公理 ZFC。更準確 地說，如果 ZFC 是相容的，那麼 CH 和它的否定都不能由 ZFC 證明： Godel 的結果給出 ZFC+CH 的相對相容性，Cohen 的 forcing 結果給出 $ZFC+\neg\mathrm{CH}$ 的相對相容性。這些是元數學的相容性結果，不是本課程中對 CH 或其否定的證明。

獨立性不表示這句話沒有意義，也不表示所有基數命題都無法判定。Cantor 定理 和實數不可數性仍是 ZFC 定理；CH 只是詢問它們之間更精細的比較，通常公理沒 有決定這個問題。因此寫證明時，要標出映射方向以及選擇或極大性原理的使用。

選擇函數與選擇公理

在陳述選擇公理之前，這裏先定義一個由集合組成的集合的並集：

$$\bigcup S=\{x\mid \exists X\in S\text{ such that }x\in X\}.$$

定義

選擇函數

設 $S$ 為一個集合，其元素都是非空集合。$S$ 的選擇函數是函數

$$f:S\to \bigcup S$$

使得對每個 $X\in S$ 都有

$$f(X)\in X.$$

選擇函數會從族 $S$ 中每一個集合各選出一個元素。對帶指標的族 $(A_i)_{i\in I}$，同一件事寫成

$$c:I\to\bigcup_{i\in I}A_i,\qquad c(i)\in A_i.$$

如果 $S$ 含有空集，就不可能有選擇函數，因為空集中沒有元素可選。因此定 義必須假設 $S$ 的成員都是非空集合。

對於有限族，可以逐次從每個非空集合中選出元素，這只使用 ZF 中普通的 存在性和有限步構造。選擇公理處理任意的非空集合族，尤其是沒有給出一條 明確選擇規則而又包含無限多個成員的情況。空族本身有唯一的空選擇函數； 真正的障礙是族中含有空集，因為空集中沒有可選元素。

公理 — 選擇公理.

設 $S$ 為一個集合，其元素都是非空集合。則 $S$ 有選擇函數。

這是公理，不是本課程從其他公理推出的定理。應區分有限次選擇與對任意帶 指標族同時選擇：前者可以在 ZF 中逐步完成，後者正是選擇公理所保證的範圍。

在元數學層面，如果 ZF 是相容的，那麼 AC 和它的否定都 不能由 ZF 證明。這裏記錄這一相對相容性陳述而不在本篇證明它；本篇要掌握 的是準確的選擇函數陳述，以及後續構造在哪一步調用了它。

例題

選擇函數做甚麼

設

$$S=\{\{1,2\},\{3,4,5\},\{6\}\}.$$

一個選擇函數可以選

$$f(\{1,2\})=1,\qquad f(\{3,4,5\})=4,\qquad f(\{6\})=6.$$

它不一定要選最小元素；只需要從每個非空集合中選一個元素。

指標記號還可以把同一例子寫得更清楚。令 $I=\{1,2,3\}$，$A_1=\{1,2\}$，$A_2=\{3,4,5\}$， 以及 $A_3=\{6\}$。上面的選擇定義了定義域為 $I$ 的函數：

$$c(1)=1,\qquad c(2)=4,\qquad c(3)=6.$$

逐個指標檢查即可：$c(1)\in A_1$、$c(2)\in A_2$、$c(3)\in A_3$。 這是有限族，所以可以一個接一個地寫出選擇。對沒有每個集合的「第一個」 元素可用的無限族，選擇公理斷言仍存在滿足同一隸屬條件的函數。

滿射與基數不等式

定理

在選擇公理下，滿射給出反方向的基數不等式

假設選擇公理，若 $f:X\to Y$ 是滿射，則

$$|X|\ge |Y|.$$

要證明它，需要構造單射 $g:Y\to X$；對任意多個纖維同時選擇代表，正是選 擇公理出現的地方。

對每個 $y\in Y$，纖維

$$f^{-1}(y)\subseteq X$$

非空，因為 $f$ 是滿射。令

$$S=\{f^{-1}(y)\mid y\in Y\}.$$

這是 $X$ 的非空子集所成的集合。由選擇公理，可從每個纖維選一個元素。定 義

$$g(y)=\text{在 }f^{-1}(y)\text{ 中被選出的元素}.$$

則 $g:Y\to X$ 是單射。若 $g(y)=g(y')$，同一個 $X$ 中元素同時落在兩個纖 維裏，所以

$$f(g(y))=y \qquad\text{且}\qquad f(g(y'))=y'.$$

由 $g(y)=g(y')$ 得 $y=y'$。

這也說明前面的提醒：滿射本身仍可能多對一；選擇函數只為每個目標取一個原 像。不同纖維互不相交，因為共同元素經 $f$ 映射會給出 $y=y'$，所以這些代 表互不相同，恰好構成單射，而不是原滿射的顯式逆函數。

可數個可數集合的並仍可數

定理

可數個可數集合的並仍可數

假設選擇公理，若 ${A_n}_{n\in N}$ 是一個可數族，而每個 $A_n$ 都可數， 則

$$A=\bigcup_{n\in N} A_n$$

可數。

若 $A=\varnothing$，空函數立即給出到 $N$ 的單射。現在假設 $A$ 非空。 由於每個 $A_n$ 可數，對每個指標 $n$ 都存在單射

$$i_n:A_n\to N.$$

當 $A_n=\varnothing$ 時，唯一的空函數就是這樣的單射。這裏使用選擇公理 同時選出整族單射 ${i_n}$，包括這些空成員的情況。這裏需要選擇的是整族 見證映射；這並不是說任意多個不可數集合的可數並會變成可數。

定義

$$h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)),$$

其中

$$n(x)=\min\{n\in N\mid x\in A_n\}.$$

由於 $x$ 屬於並集中的至少一個成員且 $N$ 良序，最小指標存在。映射 $h$ 是單射：若 $h(x)=h(x')$，第一座標給出 $n(x)=n(x')=n$，第二座標再給出 $i_n(x)=i_n(x')$，而 $i_n$ 的單射性推出 $x=x'$。

最後，$N\times N$ 的對角枚舉給出單射 $N\times N\to N$，與 $h$ 合成便得 到單射 $A\to N$。先列 $(0,0)$，再列座標和為 $1$、$2$ 等的點，每個點都 在有限階段出現；空成員不貢獻並集元素。指標集與每個成員都必須可數，否則 不可數的指標集單點族或一個不可數成員都可能使並集不可數。

常見錯誤

可數並不等於任意並

這個定理處理的是可數族 ${A_n}$。它不是說任意多個可數集合的並都必定可數。

鏈、極大元素與 Zorn 引理

Zorn 引理透過極大元素的存在性表達選擇公理。

定義

鏈

設 $X$ 為偏序集合。子集 $S\subseteq X$ 稱為鏈，如果它是全序子集： 對任意 $a,b\in S$，都有

$$a\le b \qquad\text{或}\qquad b\le a.$$

定義

極大元素

元素 $m\in X$ 稱為極大元素，如果不存在 $x\in X$ 使得

$$x\gt m.$$

極大元素不一定大於所有其他元素。這不同於最大元素；最大元素需要滿足 $m\ge x$ 對所有 $x\in X$ 成立。

例題

極大比最大弱

在偏序集合中，兩個元素可能不可比較。如果二者互不在對方之上，它們都可能 在某個小集合中是極大元素，但沒有任何一個是最大元素。

因此，「極大」的意思是「不能再往上延伸」，不是「支配所有元素」。

定理

Zorn 引理

選擇公理等價於以下命題：

若 $X$ 是非空偏序集合，且 $X$ 中每一條鏈都有一個屬於 $X$ 的上界，則 $X$ 有極大元素。

本課程把它作為基礎工具陳述，完整證明屬於更進階課程。量詞不能倒置：它不 是說每個子集都有最大元素，也不要求一個元素給整個偏序集作上界；對每條鏈 $C\subseteq X$，存在可能依賴於 $C$ 的 $u\in X$，使每個 $c\in C$ 都有 $c\le u$，從而至少有一個元素不能再嚴格向上延伸。

一個有限例子是按包含關係排列 $E=\{1,2,3\}$ 的真子集。鏈 $\varnothing\subset\{1\}\subset\{1,2\}$ 在同一偏序中以上界就是 $\{1,2\}$，而 $\{1,2\}$ 是極大元素，因為再加入剩餘元素就不再 是真子集。它卻不是最大元素：$\{1,3\}$ 與它不可比較。這個小例子把 一般引理所用的兩個術語區分開來。

常見錯誤與細節

常見錯誤

不要把 Cantor 定理只當作有限算術

有限集合中 $2^n\gt n$ 很熟悉；Cantor 定理更強，因為它對所有集合，包括無限 集合，都成立。

常見錯誤

不要混淆極大與最大

最大元素要大於或等於每個元素。極大元素只要求沒有更大的元素在它上方。在 偏序中，二者不同。

常見錯誤

不要隱藏選擇公理的角色

從無限多個非空集合中各選一個元素，正是選擇公理要保證的步驟。

快速檢查

思考檢查

為甚麼從 $2^N$ 到 $R$ 的單射使用底數 3？

考慮第一個不同的位置，以及後面尾項可能造成的影響。

解答 · 答案

底數 $3$ 令第一個不同項的大小大於後面所有尾項可能造成的總抵消量。因此 兩個不同的零一序列不會定義出同一個實數。

思考檢查

選擇函數選的是甚麼？

請同時提到集合族和被選元素。

解答 · 答案

對集合族 $S$ 中每個非空集合 $X$，選擇函數選出一個元素 $f(X)\in X$。

思考檢查

為甚麼 Cantor 矛盾需要滿射性？

指出產生 $f(y)=T$ 的那一步。

解答 · 答案

對角集合 $T$ 是 $X$ 的子集，因此是 $2^X$ 的元素。滿射性保證 $2^X$ 的每個元素都是某個 $f(y)$，所以存在 $y\in X$ 使 $f(y)=T$。若沒有滿射性，$T$ 可能在 $f$ 的像之外，矛盾就無法開始。

練習

思考檢查

證明單點映射 $x\mapsto\{x\}$ 是單射。

假設兩個單點集合相等。

解答 · 引導解答

若

$$\{x_1\}=\{x_2\},$$

則左邊單點集合的唯一元素等於右邊單點集合的唯一元素，所以 $x_1=x_2$。 因此 $x\mapsto \{x\}$ 是單射。

思考檢查

解釋為甚麼滿射 $f:X\to Y$ 會使每個纖維 $f^{-1}(y)$ 非空。

使用滿射的定義。

解答 · 引導解答

滿射表示對每個 $y\in Y$，都存在 $x\in X$ 使 $f(x)=y$。這正是說 $x\in f^{-1}(y)$，所以該纖維非空。

思考檢查

為帶指標族 $(A_i)_{i\in I}$ 寫出選擇函數的完整陳述。

說明定義域、陪域和成員條件。

解答 · 引導解答

若每個 $A_i$ 都非空，選擇函數是

$$c:I\to\bigcup_{i\in I}A_i$$

並且對每個 $i\in I$ 都有 $c(i)\in A_i$。

思考檢查

在 Zorn 引理中，為甚麼不能只談最大元素？

回想這裏的順序是偏序，不一定是全序。

解答 · 引導解答

在偏序中，有些元素可能不可比較。最大元素必須在所有元素之上，未必存在。 Zorn 引理在其假設下保證的是極大元素：沒有嚴格更大的元素在它上方。

相關筆記

可先讀 6.1 基數、可數性與基數不等式 和 2.2 函數與關係。 繼續閱讀6.3 區間、Cantor 集、稠密性與良序， 比較基數與長度、稠密性和次序。