5. 可數性與對角線論證

學習目標與約定

通過函數而非直觀大小比較有限和無限集合；枚舉乘積及有理數；寫出完整的對角線反證。這裏使用 $\mathbb N=\{0,1,2,\ldots\}$。若集合有限或可列成包含其每個元素的序列，稱其可數；若與 $\mathbb N$ 雙射，稱其可數無限。列舉中的重複元素可只保留首次出現；因此無限的可列集合有無重複的枚舉。

可數集的子集可數：掃描枚舉，只保留屬於子集的元素。對 $\mathbb N^2$，按 $m+n$ 排列數對，同一對角線上再按 $m$ 排列。在任何固定數對之前只有有限個數對，且每對都會出現。因此將兩個可數集的枚舉代入該對角線列表，可知它們的乘積可數。此論證可擴展到每個固定有限乘積，不能擴展到可數無限乘積。

定理：具有指定枚舉的可數並

若對每個 $j\in\mathbb N$，集合 $A_j$ 都有指定的列表（允許有限列表），則 $\bigcup_jA_j$ 可數。

證明。 按對角線列出指標對 $(j,k)$。在每對處，若 $A_j$ 的第 $k$ 項存在便輸出，否則跳過。每個元素屬於某個 $A_j$，並在該列表的有限位置出現，所以也會出現在輸出中。必要時刪除重複項；空集不貢獻元素。命題明確提供了枚舉；從無窮多個未指定的枚舉中選擇涉及額外的基礎選擇問題，此處不需要。

因此 $\mathbb Z$ 可由 $0,1,-1,2,-2,\ldots$ 列舉；$\mathbb Q$ 可通過列出分子與正分母的數對並輸出其分數來列舉。不同數對可能表示相同有理數；重複不妨礙可數性。

定理：康托爾對角線定理

對任何集合 $X$，不存在滿射 $F:X\to\mathcal P(X)$。

證明。 給定這樣的映射，構造 $D=\{x\in X:x\notin F(x)\}$。若某個 $d\in X$ 滿足 $D=F(d)$，則 $d\in D$ 當且僅當 $d\notin F(d)=D$，無論哪一情況都矛盾。因此值域遺漏 $D$。特別地，$\mathcal P(\mathbb N)$ 不能按自然數列舉。

為避免小數表示的歧義，將 $A\subseteq\mathbb N$ 映到

$$x_A=\sum_{n=0}^{\infty}\frac{2\mathbf1_A(n)}{3^{n+1}}\in[0,1].$$

若 $A,B$ 首次在 $m$ 處不同，首個差的模為 $2/3^{m+1}$，而所有後續項的差的模之和至多為 $1/3^{m+1}$。故 $x_A\ne x_B$。這將不可數冪集單射到 $[0,1]$，所以該區間及 $\mathbb R$ 不可數；論證不依賴小數表示的唯一性。

例題

無限子集可以有相同大小。 映射 $n\mapsto2n$ 將 $\mathbb N$ 與非負偶整數雙射。無限集合可以與其真子集等勢；有限集合中有關剩餘元素的直覺不能證明基數較小。

代數實數可數。 整系數多項式是有限整數元組的可數並，每種次數對應一種元組長度。每個非零多項式只有有限個實根。對其有限實根集採用確定性次序，並集定理說明所有代數實數組成可數集。由於 $\mathbb R$ 不可數，非代數的（超越的）實數存在；該證明沒有指出具體數值。

分層練習

1. 基礎。 給出 $\mathbb N$ 到正奇整數的一個雙射。
2. 核心。 證明 $\mathbb Q\times\mathbb Q$ 可數。
3. 核心。 證明有限二進制字符串的集合可數，但無限二進制序列的集合不可數。
4. 證明。 若 $U$ 不可數且 $C\subseteq U$ 可數，證明 $U\setminus C$ 不可數。

詳解

1. 映射 $n\mapsto2n+1$ 是單射，每個正奇整數又恰可寫成該形式，故為雙射。
2. 選定有理數列表。按 $\mathbb N^2$ 的對角線枚舉處理指標對，並輸出相應的有理數對。每對都會出現，重複可刪除。
3. 對每個長度 $n$ 有 $2^n$ 個字符串。按長度、再按字典序排列，可枚舉所有有限字符串。無限二進制序列是 $\mathbb N$ 子集的指標函數；康托爾定理說明這些子集及相應序列無法列舉。
4. 若 $U\setminus C$ 可數，將其列表與 $C$ 的列表交錯，便可列舉它們的並 $U$，與不可數性矛盾。故該補集不可數。

總結與術語

枚舉列出每個元素；雙射在兩個方向上唯一配對元素。對角線論證構造一個對象，使其在受控的第 $n$ 個特徵上與第 $n$ 個提議條目不同。代數數是非零整系數多項式方程的解。固定有限乘積及有給定枚舉的可數並保持可數性，但無限二進制乘積不保持。