6.1.2-6.3 Cantor 定理、連續統與選擇公理

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

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

冪集與 Cantor 定理

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

證明分兩部分。

首先，有單射

$$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|<|2^X|$。

對角線實驗

下面的互動元件是用來輔助證明，而不是替代證明。可用它觀察 $T$ 為甚麼必 然會與每一個嘗試列出的子集不同。

圖示。對角集合透過反轉對角線上的隸屬判斷而成，所以不可能等於候選列表中任何一行。

實數不可數

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

由 Cantor 定理，

$$|N|<|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$ 的每個子集送到一個實數。

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

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

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

後面所有項加起來可能造成的抵消量比這個主要差距還小。因此兩個實數不可能 相等。故 $\phi$ 是單射，從而 $|2^N|\le |R|$。

合併得到

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

所以 $R$ 不可數。

連續統假設

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

這裏強調，這個猜想的地位非常特殊。連續統假設獨立於通常的集合論公理 ZFC。 Godel 在 1940 年證明它與 ZFC 相容；Cohen 在 1963 年使用 forcing 證明它 的否定也與 ZFC 相容。因此它不能從標準公理中被證明，也不能從標準公理中 被否證。

對本課程而言，重點不是證明這些元數學結果，而是知道：基數問題很快會進入 「公理是否足夠」的層面。

選擇函數與選擇公理

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

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

選擇函數會從族 $S$ 中每一個集合各選出一個元素。

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

這是公理，不是定理。這裏指出，如同連續統假設一樣，它的真偽不能由其他集 合論公理決定。

滿射與基數不等式

要證明它，需要構造單射 $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'$。

這解釋了前面的提醒：由滿射推出反方向基數不等式，在需要同時從無限多個纖 維中選代表時，會用到選擇公理。

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

這裏用滿射組織證明。由於每個 $A_n$ 可數，可選滿射

$$f_n:N\to A_n.$$

若 $A_n$ 有限，可把最後一個元素不斷重複，仍得到由 $N$ 到 $A_n$ 的滿射。 選擇公理用來同時選出整族映射 ${f_n}$。

定義

$$F:N\times N\to A,\qquad F(n,m)=f_n(m).$$

這是滿射：並集中任何元素都屬於某個 $A_n$，因此會被相應的 $f_n$ 命中。

最後，$N\times N$ 可數，證明方式與 $Q$ 可數的對角線方法類似。因此存在 滿射

$$N\to N\times N.$$

合成後得到滿射 $N\to A$，所以 $A$ 可數。

鏈、極大元素與 Zorn 引理

指定頁面的最後一部分陳述 Zorn 引理；它與選擇公理等價。

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

本課程把它作為基礎工具陳述。完整證明屬於更進階課程；但現在應該先準確讀 懂其中的詞：偏序、鏈、鏈的上界，以及極大元素。

常見錯誤與細節

快速檢查

練習

相關筆記

可先讀 6.1 基數、可數性與基數不等式 和 2.2 函數與關係。 下一個課程段落開始討論區間；這篇筆記則完成 Chapter 6.1-6.3 所需的大集 合基礎。