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

整數和有理數都能由自然數逐一列出，但這並未回答：每個無限集合是否都能如此列舉？冪集提供了反例的構造方法。對任何候選子集列表，都可以根據各項的隸屬關係，構造出一個沒有列入其中的子集。

冪集與 Cantor 定理

定義 6.2.1

（冪集記號）

對集合 $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$ 開始。下面的定理更強：即使集合不是有限的，仍然可以嚴格比較集合與其冪集的基數。

構造列表遺漏的子集

設 $f:X\to2^X$ 為 $X$ 的每個元素指定一個子集。要構造 $f$ 遺漏的子集，只需讓它對每個 $x$ 都在某個元素上與 $f(x)$ 不同。指標 $x$ 本身便可擔當這個角色：當且僅當 $f(x)$ 不含 $x$ 時，把 $x$ 放入新子集。這樣，列表的每一項都有一個確定的隸屬判斷與新子集不同。

下面用 $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$ 的每個元素確定是否納入 $T$，毋須給 $X$ 安排數字次序，也不涉及逐項掃描完一個無限列表。

Cantor 定理

定理 6.2.2

（Cantor 定理）

設 $X$ 為集合。則

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

證明分兩部分。

首先，有單射

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

所以 $|X|\le |2^X|$。例如 $X=\{a,b\}$ 時，這個映射從四個子集 $\varnothing,\{a\},\{b\},\{a,b\}$ 中選中兩個；它不必覆蓋所有子集。

其次，不存在由 $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=\varnothing$ 時，冪集有一個元素，從空集出發的函數不可能命中它。因此結論也涵蓋空集的情形。

證明透視

滿射性用在哪裏

等式 $f(y)=T$ 是滿射性發揮作用的關鍵。對角論證沒有使用單射性，而是排除了所有由 $X$ 到 $2^X$ 的滿射。單點映射則提供嚴格基數不等式所需的另一部分。

探索對角差異

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

實數不可數

定理 6.2.3

（實數不可數）

實數集合 $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$ 的每個元素）送到一個實數。

例題 6.2.4

（把 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 .$$

部分和非遞減且以 $1/2$ 為上界，因此完備性保證實數極限存在。這與 4.6 小數展開與無理數 中由有限近似確定實數的原理相同，毋須再轉換成十進制。

為甚麼用底數 $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$ 的子集給出不同實數。

例題 6.2.5

（底數 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 只是詢問它們之間更精細的比較，通常公理沒有決定這個問題。因此寫證明時，要標出映射方向以及選擇或極大性原理的使用。

選擇函數與選擇公理

滿射 $f:X\to Y$ 能命中 $Y$ 的每個元素，卻未必指定應採用哪一個原像。要構造反方向的單射，我們希望為每個 $y$ 指定纖維 $f^{-1}(y)$ 中的一個元素。每個纖維都非空；額外的問題是，這些各自成立的存在性命題，能否給出一個同時完成所有選擇的函數。

對集合族 $S$，所有可能被選出的元素都在它的並集內：

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

定義 6.2.6

（選擇函數）

設 $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 證明。這裏記錄這一相對相容性陳述而不在本篇證明它；本篇要掌握的是準確的選擇函數陳述，以及後續構造在哪一步調用了它。

例題 6.2.7

（選擇函數做甚麼）

設

$$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$。這是有限族，所以可以一個接一個地寫出選擇。對沒有每個集合的「第一個」元素可用的無限族，選擇公理斷言仍存在滿足同一隸屬條件的函數。

滿射與基數不等式

定理 6.2.8

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

假設選擇公理，若 $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'$，所以不同目標的代表互不相同。

等式 $f\circ g=id_Y$ 說明 $g$ 是 $f$ 的右逆。它未必是雙側逆函數，因為 $g\circ f=id_X$ 並不一定成立。若 $f$ 本身是雙射，每個纖維就只有一個元素，此時 $g$ 正是通常的逆函數。

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

定理 6.2.9

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

假設選擇公理，若 ${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$ 屬於並集，指標集非空；自然數的良序性保證最小指標存在。這一歸納法推論的證明見 6.3 區間、Cantor 集、稠密性與良序。映射 $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 引理透過極大元素的存在性表達選擇公理。

定義 6.2.10

（鏈）

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

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

定義 6.2.11

（極大元素）

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

$$x\gt m.$$

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

例題 6.2.12

（極大比最大弱）

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

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

定理 6.2.13

（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 集、稠密性與良序，比較基數與長度、稠密性和次序。