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$ 个提议条目不同。代数数是非零整系数多项式方程的解。固定有限乘积及有给定枚举的可数并保持可数性，但无限二进制乘积不保持。