6.1 基數、可數性與基數不等式

第 6 章開始時，問題的角度有所改變。前面幾章主要構造和研究特定的數系； 這一章問的是更一般的問題：如果集合很大，尤其是無限集合，我們應該怎樣比 較它們的大小？

對有限集合來說，逐個數元素已經足夠。對無限集合來說，更穩定的方法是研究 函數。雙射表示兩個集合的元素可以完全一一配對；單射表示一個集合可以不撞 車地編碼到另一個集合裏。

相與基數

這個定義刻意不要求兩個集合的元素有相同性質。元素可以完全不同；真正重要 的是能否把 $X$ 的每個元素配到 $Y$ 的唯一元素，而且 $Y$ 的每個元素也都被 配到。

對有限集合來說，這與普通的數數一致。如果一個集合可以與 n 個標籤組成 的集合雙射，便說它有 n 個元素。

因此 |X| 不應被理解為任何集合都自動對應一個普通數字。它表示 $X$ 的 大小，即基數。有限集合的基數可用自然數表示；無限集合的基數則需要透過映 射來比較。

可數與不可數

所以，一個可數無限集合的元素可以排成一列而不遺漏、不重複：

$$x_0,x_1,x_2,\ldots$$

至於 $N$ 從 0 還是 1 開始，只影響索引寫法，不影響可數性的本質。

整數是可數的

這裏要求證明

$$|N|=|Z|.$$

核心想法是：所有整數可以排成一條無限序列。

這個例子說明無限集合的第一個現象：即使 $Z$ 看起來比 $N$ 多出很多元素， 兩者仍然可以有相與基數。

有理數是可數的

這裏先處理正有理數。只要能列舉 $Q_+$，便可以再把正有理數、負有理數和 零交錯列出，從而列舉整個 $Q$。

每個正有理數在最簡形式下可寫成

$$\frac{p}{q},$$

其中 $p,q\in N$ 為正，並且沒有大於 1 的公因子。把這個分數放在第 p 行、第 q 列的無限表格裏，然後按對角線

$$p+q=2,\quad p+q=3,\quad p+q=4,\quad \ldots$$

依次掃過，只記錄最簡分數。

圖示。對角掃描不是裝飾，而是將正有理數的二維格點轉成一條序列的機制。

這為甚麼給出 $Q_+$ 的列舉？

• 它是滿的：每個正有理數都有某個最簡表示 p/q，所以必定出現在表格中。
• 它不重複：只用最簡形式，便不會把 1/1、2/2、3/3 視為不同有理數。

有了 $Q_+$ 的列舉

$$q_1,q_2,q_3,\ldots,$$

便可列出

$$0,\ q_1,\ -q_1,\ q_2,\ -q_2,\ q_3,\ -q_3,\ldots .$$

因此 $Q$ 可數。

用單射比較基數

雙射判斷基數是否相等。若要比較可能不相等的大小，這裏使用單射。

單射 $X\to Y$ 的意思是：$Y$ 有足夠位置為 $X$ 的每個元素放置互不相同的 編碼。這正是基數版本的「小於或等於」。

基數不等式具有偏序性質

這裏中的證明結構如下。

自反性。 恒等映射

$$id_X:X\to X$$

是單射，所以 $|X|\le |X|$。

傳遞性。 若 $f:X\to Y$ 與 $g:Y\to Z$ 都是單射，則合成

$$g\circ f:X\to Z$$

也是單射。因此 $|X|\le |Y|$ 且 $|Y|\le |Z|$ 蘊含 $|X|\le |Z|$。

反對稱性。 這正是 Cantor-Bernstein 定理的內容。

Cantor-Bernstein 定理

換句話說，如果 $X$ 可以單射到 $Y$，而 $Y$ 也可以單射到 $X$，那麼二者實 際上有相與基數。這句話直觀上很合理，但無限集合情況下的證明並不只是有限 集合論證的直接翻版。

這裏給出一個證明梗概。設

$$f:X\to Y,\qquad g:Y\to X$$

為單射。由於 g 把 $Y$ 嵌入 $X$，像集 g(Y) 可視為放在 $X$ 裏的一份 $Y$ 的複本。證明構造 $X$ 的一串巢狀子集

$$A_0\supset B_0\supset A_1\supset B_1\supset\cdots$$

其中

$$A_0=X,\qquad B_0=g(Y),$$

並且

$$A_{n+1}=g(f(A_n)),\qquad B_{n+1}=g(f(B_n)).$$

映射 $g\circ f:X\to X$ 將每一層差集

$$A_n\setminus B_n$$

雙射到下一層差集

$$A_{n+1}\setminus B_{n+1}.$$

最後要構造的雙射 $h:X\to Y$ 分段定義如下：

$$h(x)= \begin{cases} f(x), & x\in A_n\setminus B_n\text{ for some }n,\\ g^{-1}(x), & \text{otherwise.} \end{cases}$$

這個構造的重點不是「一眼看出」雙射，而是兩個單射提供了足夠結構，可以把 $X$ 分成適當部分，再逐部分定義真正的雙射。

輔助比較實驗

下面的互動元件只是輔助正式語言。可用它分辨雙射、單射、兩邊單射分別在說 甚麼，再回到上面的定義與定理。

常見錯誤與細節

快速檢查

練習

相關筆記

可先讀 2.2 函數與關係， 特別是單射、滿射、雙射與偏序的部分。然後接著讀 6.1.2-6.3 Cantor 定理、連續統與選擇公理。