Lecture 12: Countability（可数性）
Lecture 12: Countability（可数性）
概述
本讲回答一个听上去像哲学、实际上是计算机科学地基的问题：无穷也有大小之分吗？ 答案是肯定的，而且这个区分恰恰决定了一门学科的存在性——如果所有无穷都一样大，那么”存在无法被任何程序解决的问题”这句话就无从谈起。我们先把”两个集合一样大”这件事严格定义为存在双射 (bijection)，然后证明 $\mathbb{N}$、$\mathbb{Z}$、$\mathbb{N}\times\mathbb{N}$、$\mathbb{Q}$、$\{0,1\}^*$、$\mathbb{N}[x]$ 全都一样大（都是可数 (countable) 的），而 $\mathbb{R}$、$\mathcal{P}(\mathbb{N})$ 严格更大（不可数 (uncountable)）。关键的技巧只有一个：对角线论证 (diagonalization)。它在本讲打倒实数，在下一讲（Lecture 13）会以完全相同的手势打倒一切通用停机判定程序。
本讲是 Fall 2026 序列中「极限与不可能」模块（L12–L13）的第一讲，紧接在图与匹配（L09–L11）之后；它是一个转折点——此前所有讲次都在教”怎么证明某件事成立”，从本讲开始我们学习”怎么证明某件事不可能成立”。
核心概念的直观解释
基数 (Cardinality, $\vert A\vert $)
- 定义：集合 $A$ 的基数 $\vert A\vert $ 是它的”元素个数”。对有限集，$\vert A\vert $ 就是一个自然数；对无限集，$\vert A\vert $ 是一个无穷基数（本讲只区分”可数”与”不可数”两档，并证明 $\mathcal{P}(A)$ 总比 $A$ 高一档）。
- 直观解释（”它是什么意思？”）：基数是”衡量集合大小”的尺子。麻烦在于，量有限集时我们可以真的去数，量无限集时”数到完”这个动作永远做不完。所以我们需要一把不需要数完就能比较的尺子——这就是双射。它的思想来自幼儿园：两个班里谁的人多？不必点名报数，让两个班的小朋友两两牵手，牵完之后若没人落单，就是一样多。
- 具体示例：$A=\{a,b,c\}$ 与 $B=\{1,2,3\}$ 之间可以建立 $a\leftrightarrow 1$、$b\leftrightarrow 2$、$c\leftrightarrow 3$，所以 $\vert A\vert =\vert B\vert =3$。而 $A=\{a,b,c\}$ 与 $B=\{1,2\}$ 之间无论怎么牵，$A$ 里总有一个人落单，所以 $\vert A\vert >\vert B\vert $。
单射 (Injection/One-to-one)、满射 (Surjection/Onto)、双射 (Bijection)
- 定义：设 $f:A\to B$ 是函数（$A$ 叫定义域 (domain)，$B$ 叫陪域/范围 (range)）。
- $f$ 是单射：不同输入给不同输出，即 $x\neq y \Rightarrow f(x)\neq f(y)$；等价地 $f(x)=f(y)\Rightarrow x=y$。
- $f$ 是满射：$B$ 中每个元素都被打到，即 $(\forall y\in B)(\exists x\in A)\,f(x)=y$。
- $f$ 是双射：既是单射又是满射。
- 直观解释：单射 = “不撞车”（没有两个输入共享一个输出）；满射 = “全覆盖”（输出端没有漏掉的元素）；双射 = “完美配对”（一一对应）。这三者的关系可以用三个小图刻在脑子里：
单射（不撞车，但有漏） 满射（全覆盖，但有撞车） 双射（既不撞也不漏）
A B A B A B
1 ────────► a 1 ──┐ a 1 ────────► a
2 ────────► b 2 ──┴──────► b 2 ────────► b
3 ────────► c 3 ────────► c 3 ────────► c
d (漏掉了) 4 ────────► c (撞到同一个) 4 ────────► d
每个输出至多 1 个前像 每个输出至少 1 个前像 每个输出恰好 1 个前像
- 具体示例：$f:\{1,2,3\}\to\{a,b,c,d\}$，$1\mapsto a,2\mapsto b,3\mapsto c$ 是单射但不是满射（$d$ 没人映射过来）。$g:\{1,2,3,4\}\to\{a,b,c\}$，$1\mapsto a,2\mapsto b,3\mapsto c,4\mapsto c$ 是满射但不是单射（$c$ 被撞了两次）。$h:\{1,2,3\}\to\{a,b,c\}$ 恒等配对才是双射。注意一个有限集上的铁律：若 $\vert A\vert =\vert B\vert $ 有限，则”单射 $\iff$ 满射 $\iff$ 双射”；但这条铁律对无限集失效，这正是本讲所有反直觉现象的根源。
等势 (Same cardinality)
- 定义：$\vert A\vert =\vert B\vert $ 当且仅当存在一个双射 $f:A\to B$。
- 直观解释（”它是什么意思？”）：这是我们给无穷集量身定制的”大小相等”定义。为什么不能用”包含关系”来定义大小？因为我们被迫二选一：要么接受一个会导致自相矛盾的”大小”概念，要么接受”真子集可以和自己一样大”。数学选择了后者，因为它逻辑上完全自洽。类比：一盏灯每隔一半时间闪一次——$[0,1]$ 秒内闪了无穷多次，但闪的次数和 $[0,2]$ 秒内闪的次数是”一样多”的（都是可数无穷），尽管第二个时间段在时间长度上是第一个的两倍。“多”这个词用在无穷上时，必须换成”能否配对”。
- 具体示例：$\mathbb{N}\subsetneq\mathbb{Z}$（$\mathbb{Z}$ 多了所有负数和更”多”的符号），但我们马上会给出一个显式双射，所以 $\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert $。
可数集 (Countable set)
- 定义：集合 $S$ 是可数的，若 $S$ 是有限集，或存在双射 $f:S\to\mathbb{N}$（等价地：存在双射 $f:\mathbb{N}\to S$，也等价地：可以把 $S$ 的元素排成一个序列 $a_0,a_1,a_2,\dots$，使每个元素恰好出现一次）。
- 直观解释：”可数”的字面意思是”能被自然数编号“，而不是”能被数完”。$S$ 可数 $\iff$ 我们可以给 $S$ 中每个元素贴上一个独一无二的门牌号 $0,1,2,3,\dots$，既不重号也不漏号。想象一个无限长的寄存柜走廊，每个柜子有一个编号；$S$ 可数就是说 $S$ 的元素恰好能一个萝卜一个坑地塞满这排柜子。
- 具体示例：$\{a,b,c\}$ 可数（有限，$\vert S\vert =3$，与 $\{0,1,2\}$ 双射）；$\mathbb{N}$ 可数（恒等映射 $f(n)=n$）；$\mathbb{Z}$ 可数（马上给公式）；$\mathbb{R}$ 不可数（本讲后半段证明）。
重要澄清：可数 $\neq$ 有限。$\mathbb{N}$ 是无限集，但它是可数的（最标准的可数集）。「可数」的反面是「不可数」，不是「无限」。同时注意 CS70 采用的这个定义把有限集也算作可数——这和某些教材把”可数”专指”可数无限”（countably infinite）不同，读英文材料时留意。
两种证明”等势”的策略
- 定义/事实：设 $A,B$ 是集合。
- 若存在单射 $f:A\to B$，则 $\vert A\vert \le\vert B\vert $。
- Cantor–Bernstein 定理 (Cantor–Bernstein Theorem)：若 $\vert A\vert \le\vert B\vert $ 且 $\vert B\vert \le\vert A\vert $（即存在两个方向的单射），则存在双射 $h:A\to B$，即 $\vert A\vert =\vert B\vert $。该定理的证明技巧性较强，CS70 只引用不证。
- 直观解释：这是一条极其实用的”夹逼”路线。直接造双射有时很难（因为要同时保证不撞车和全覆盖），但造两个单射往往容易得多（每个单射只需管一件事）。于是标准套路变成：先证 $\vert A\vert \le\vert B\vert $，再证 $\vert B\vert \le\vert A\vert $，收工。 我们在证明 $\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $ 时正是这么做的（$\vert \mathbb{N}\vert \le\vert \mathbb{Q}\vert $ 因为 $\mathbb{N}\subseteq\mathbb{Q}$ 是平凡的；难的只有 $\vert \mathbb{Q}\vert \le\vert \mathbb{N}\vert $）。
- 具体示例：要证 $\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $，只需造一个单射 $\mathbb{Q}\to\mathbb{N}$；$\mathbb{N}\to\mathbb{Q}$ 的恒等嵌入自动给出反向单射。这正是下面定理 12.4 的做法。
完整证明与推导（核心）
定理 12.1：$\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert $。也就是说，尽管 $\mathbb{Z}$ 比 $\mathbb{N}$ 多出无穷多个负数，二者一样大。
证明策略：构造性证明。我们不去数，而是直接写出一个 $f:\mathbb{N}\to\mathbb{Z}$，然后分别验证它单射、满射。这个证明的价值在于它示范了无穷基数比较的标准流程：写出公式 → 验证单射 → 验证满射 → 引用定义得等势。选这个策略是因为公式可以显式写出，而显式双射是最强的”等势证书”。
逐步推导：
第一步（构造）：定义 $f:\mathbb{N}\to\mathbb{Z}$ 为 \(f(x)=\begin{cases}\dfrac{x}{2}, & x \text{ 为偶数}\\[6pt] -\dfrac{x+1}{2}, & x \text{ 为奇数}\end{cases}\) 用列举的方式看它就是 \(0\mapsto 0,\quad 1\mapsto -1,\quad 2\mapsto 1,\quad 3\mapsto -2,\quad 4\mapsto 2,\quad 5\mapsto -3,\quad 6\mapsto 3,\dots\) 直观上就是”从 0 出发左右横跳”：$0,1,-1,2,-2,3,-3,\dots$。注意 $f(124)=62$（$124$ 偶数，$124/2=62$）。
第二步（验证单射）：设 $f(x)=f(y)$。观察公式：$x$ 偶数时 $f(x)\ge 0$，$x$ 奇数时 $f(x)<0$（因为 $-(x+1)/2\le -1$）。既然 $f(x)=f(y)$ 是同一个数，它不可能既非负又负，所以 $x$ 与 $y$ 必同奇偶。
- 若 $x,y$ 都是偶数：由 $f(x)=f(y)$ 得 $x/2=y/2$，两边乘 2 得 $x=y$。
- 若 $x,y$ 都是奇数：由 $f(x)=f(y)$ 得 $-(x+1)/2=-(y+1)/2$，两边乘 $-2$ 得 $x+1=y+1$，故 $x=y$。
两种情况都推出 $x=y$，所以 $f$ 是单射。
第三步（验证满射）：任取 $y\in\mathbb{Z}$，需要找到前像。
- 若 $y\ge 0$：取 $x=2y$（这是自然数）。因为 $2y$ 是偶数，$f(2y)=2y/2=y$。所以 $y$ 有前像 $2y$。
- 若 $y<0$：取 $x=-2y-1$。因为 $y<0$ 时 $-2y\ge 2$，所以 $x=-2y-1\ge 1$ 是奇数，也是自然数；则 $f(x)=-(x+1)/2=-(-2y-1+1)/2=-(-2y)/2=y$。所以 $y$ 有前像 $-2y-1$。
两种情况都找到前像，所以 $f$ 是满射。
第四步（收口）：$f$ 既单射又满射，故为双射。由”等势”的定义，$\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert $。$\blacksquare$
【证明机制解说】：核心的”灵光一现”是用奇偶性充当”符号位”。要枚举 $\mathbb{Z}$，我们面对的难题是 $\mathbb{Z}$ 有两个方向（正、负）而 $\mathbb{N}$ 只有一个方向（递增）。解决办法是给每个 $n\in\mathbb{N}$ 分配”往哪边走”的任务：偶数步向右，奇数步向左。这不是把 $\mathbb{Z}$”压扁”成 $\mathbb{N}$（那需要无穷时间），而是给每个整数发一个唯一的编号，编号本身是有限的。还要注意第三步给出的前像公式 $x=2y$（$y\ge 0$）与 $x=-2y-1$（$y<0$）正是 $f$ 的逆函数 $f^{-1}$，它满足 $f^{-1}(f(x))=x$。
反例（如果适用）：若把 $f$ 改成”先枚举所有非负整数，再枚举所有负整数”，即 $f(x)=x/2$（$x$ 偶）、$f(x)=-(x-1)/2$（$x$ 奇）——这看上去也对，但它得到的是 $0,0,-1,1,-2,2,\dots$，其中 $0$ 被撞了两次（$x=0$ 与 $x=1$ 都映到 0），于是不是单射。这个失败版本说明：横跳时必须让正负两侧”错开”，否则原点会被重复计算。
定理 12.2：$\mathbb{N}\times\mathbb{N}=\{(i,j):i,j\in\mathbb{N}\}$ 可数。
证明策略：构造性证明，核心是对角线枚举 (diagonal enumeration)，也叫反对角线枚举。朴素想法”先枚举第一行 $(0,0),(0,1),(0,2),\dots$，再枚举第二行”会失败——因为第一行就永远枚举不完，第二行永远轮不到。这暴露了本讲最重要的一个陷阱：“给每个元素编号”和”在有限时间内列出所有元素”是两件完全不同的事。对角线枚举绕过这个陷阱的办法是：按 $i+j$ 的大小分组，每一组只有有限个元素，先枚举有限组，再进下一组。
逐步推导：
第一步（分壳）：把 $\mathbb{N}\times\mathbb{N}$ 按”反对角线” $s=i+j$ 分成一层层的壳 (shell)： \(S_s=\{(i,j):i+j=s\},\qquad \vert S_s\vert =s+1.\) $s=0$ 时壳里 1 个元素，$s=1$ 时 2 个，$s=2$ 时 3 个……每个壳都是有限的。这是整个构造的支点。
第二步（壳内定序，壳间递增）：规定枚举顺序为——先枚举 $S_0$，再枚举 $S_1$，再 $S_2$，……；同一壳内按 $j$ 从小到大（即 $i$ 从大到小）。这样得到：
j=0 j=1 j=2 j=3 j=4 j=5 ...
┌───────┬───────┬───────┬───────┬───────┬───────┐
i=0 │ 0 │ 2 │ 5 │ 9 │ 14 │ 20 │
├───────┼───────┼───────┼───────┼───────┼───────┤
i=1 │ 1 │ 4 │ 8 │ 13 │ 19 │ 27 │
├───────┼───────┼───────┼───────┼───────┼───────┤
i=2 │ 3 │ 7 │ 12 │ 18 │ 26 │ 37 │
├───────┼───────┼───────┼───────┼───────┼───────┤
i=3 │ 6 │ 11 │ 17 │ 25 │ 36 │ 50 │
├───────┼───────┼───────┼───────┼───────┼───────┤
i=4 │ 10 │ 16 │ 24 │ 35 │ 49 │ 66 │
├───────┼───────┼───────┼───────┼───────┼───────┤
i=5 │ 15 │ 23 │ 34 │ 48 │ 65 │ 85 │
└───────┴───────┴───────┴───────┴───────┴───────┘
单元格填的是「该格子被枚举到的序号」。沿反对角线读：
s=0: (0,0) -> 0 共 1 个
s=1: (1,0) (0,1) -> 1, 2 共 2 个
s=2: (2,0) (1,1) (0,2) -> 3, 4, 5 共 3 个
s=3: (3,0) (2,1) (1,2) (0,3) -> 6, 7, 8, 9 共 4 个
s=4: (4,0) (3,1) (2,2) (1,3) (0,4) -> 10, ... , 14 共 5 个
s=5: ... 共 6 个
移动方向示意（一条条斜线扫过左上三角）：
┌────┬────┬────┬────┬────┐
│ ↘ │ │ │ │ │ ← 每一条斜线 = 一个壳 = 有限个格子
│ │ ↘ │ │ │ │ 扫完一条再扫下一条
│ │ │ ↘ │ │ │
│ │ │ │ ↘ │ │
└────┴────┴────┴────┴────┘
第三步（壳内起始序号）：前 $s$ 个壳（$s=0,1,\dots,s-1$）共有 $\sum_{t=0}^{s-1}(t+1)=\frac{s(s+1)}{2}$ 个元素。所以壳 $S_s$ 的第一个元素（即 $(s,0)$）的序号是 $\frac{s(s+1)}{2}$。
第四步（配对函数）：壳 $S_s$ 内，$(i,j)=(s-j,j)$ 排在第 $j$ 个（从 0 数），因此 \(\boxed{\ \pi(i,j)=\frac{(i+j)(i+j+1)}{2}+j\ }\) 这就是 Cantor 配对函数 (Cantor pairing function)。逐项验证： \(\pi(0,0)=0,\ \ \pi(1,0)=1,\ \ \pi(0,1)=2,\ \ \pi(2,0)=3,\ \ \pi(1,1)=4,\ \ \pi(0,2)=5.\) 再验证几个表里的数：$\pi(3,4)=\frac{7\cdot 8}{2}+4=28+4=32$；$\pi(4,3)=\frac{7\cdot 8}{2}+3=31$；$\pi(0,5)=\frac{5\cdot 6}{2}+5=20$；$\pi(5,0)=\frac{5\cdot 6}{2}+0=15$。全部与上表一致。
第五步（验证单射）：设 $\pi(i,j)=\pi(i^{\prime},j^{\prime})=z$。令 $s=i+j$、$s^{\prime}=i^{\prime}+j^{\prime}$。由定义 $z=\frac{s(s+1)}{2}+j$ 且 $0\le j\le s$，所以 \(\frac{s(s+1)}{2}\le z<\frac{s(s+1)}{2}+(s+1)=\frac{(s+1)(s+2)}{2}.\) 即 $z$ 落在区间 $\left[\frac{s(s+1)}{2},\frac{(s+1)(s+2)}{2}\right)$ 内。这些区间随 $s$ 递增且两两不交（相邻区间端点相接：$\frac{(s+1)(s+2)}{2}$ 正是下一个区间的左端），所以 $z$ 唯一确定 $s$，即 $s=s^{\prime}$。既得 $s=s^{\prime}$，由 $\frac{s(s+1)}{2}+j=\frac{s(s+1)}{2}+j^{\prime}$ 立刻得 $j=j^{\prime}$。再由 $i=s-j$、$i^{\prime}=s^{\prime}-j^{\prime}$ 得 $i=i^{\prime}$。故 $(i,j)=(i^{\prime},j^{\prime})$，$\pi$ 是单射。
第六步（验证满射）：任取 $z\in\mathbb{N}$。取唯一的 $s$ 使 $\frac{s(s+1)}{2}\le z<\frac{(s+1)(s+2)}{2}$（这样的 $s$ 存在且唯一，因为区间划分了整个 $\mathbb{N}$：$s=0$ 覆盖 $z=0$，$s=1$ 覆盖 $z=1,2$，$s=2$ 覆盖 $z=3,4,5$，……）。令 $j=z-\frac{s(s+1)}{2}$，则 $0\le j\le s$，令 $i=s-j\ge 0$。于是 $i,j\in\mathbb{N}$ 且 $\pi(i,j)=z$。故 $\pi$ 是满射。
第七步（收口）：$\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 是双射，故 $\vert \mathbb{N}\times\mathbb{N}\vert =\vert \mathbb{N}\vert $。$\blacksquare$
【证明机制解说】：对角线枚举的全部智慧浓缩成一句话——“把无穷切成可数多个有限块”。行优先扫描之所以失效，是因为它有一个”永远跨不过去的有限步”（第一行无穷长）；而反对角线每一块长度都是有限的 $s+1$，任何一块都能在有限步内扫完，于是虽然总数无穷，但”编号”这个动作对每个元素都在有限步内完成。这里的”有限”是逐元素的有限，不是整体的有限——这正是 FORMAT_SPEC 特别警告的易错点：不要因为列不完就说不可数。
反向地，$\pi$ 的逆也值得记下来（后面做题常用）：给定 $z$，令 $s=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor$，则 $(i,j)=\left(s-\left(z-\frac{s(s+1)}{2}\right),\ z-\frac{s(s+1)}{2}\right)$。验算：$z=20\Rightarrow s=5,j=20-15=5,i=0$，得 $(0,5)$ ✓；$z=15\Rightarrow s=5,j=0,i=5$，得 $(5,0)$ ✓；$z=100\Rightarrow s=13,j=100-91=9,i=4$，得 $(4,9)$ ✓（表中第 4 行第 9 列确实排在第 100 位附近）。
定理 12.3：设 $A_0,A_1,A_2,\dots$ 是一列可数集（可数多个可数集），则 $\bigcup_{i\in\mathbb{N}}A_i$ 也可数。特别地，有限个可数集的并也可数。
证明策略：构造性证明 + 复用定理 12.2。技术上的关键是把”第 $i$ 个集合的第 $j$ 个元素”看成一对 $(i,j)$，然后把定理 12.2 的反对角线枚举直接搬过来。但有一个障碍必须先处理：不同的 $A_i$ 可能互相重叠，同一个元素会被数到多次，这样得到的映射就不是单射了。解决办法是”第一次出现才算”——取每个元素首次出现的位置。
逐步推导：
第一步（把每个 $A_i$ 排成序列）：因为每个 $A_i$ 可数，可以对每个 $i$ 固定一个满射 $g_i:\mathbb{N}\to A_i$（若 $A_i$ 有限，就让 $g_i$ 在某个位置之后重复最后一个元素，或视为部分定义；这不影响结论）。于是 $A_i=\{g_i(0),g_i(1),g_i(2),\dots\}$——“可数”的定义在这里被兑现成了”有序列”，这是全部构造的起点。
第二步（铺成二维表）：把整个并集想象成一张无穷大的表格，第 $i$ 行是 $A_i$ 的枚举：
j=0 j=1 j=2 j=3 j=4 ...
┌────────┬────────┬────────┬────────┬────────┐
A0 │ g0(0) │ g0(1) │ g0(2) │ g0(3) │ g0(4) │
├────────┼────────┼────────┼────────┼────────┤
A1 │ g1(0) │ g1(1) │ g1(2) │ g1(3) │ g1(4) │
├────────┼────────┼────────┼────────┼────────┤
A2 │ g2(0) │ g2(1) │ g2(2) │ g2(3) │ g2(4) │
├────────┼────────┼────────┼────────┼────────┤
A3 │ g3(0) │ g3(1) │ g3(2) │ g3(3) │ g3(4) │
└────────┴────────┴────────┴────────┴────────┘
↑ 沿反对角线扫：先扫 A0[0]；再扫 A1[0],A0[1]；再扫 A2[0],A1[1],A0[2]；...
第三步（对角线扫描顺序）：按定理 12.2 的顺序访问表格单元格：依 $i+j$ 递增，同一反对角线上 $j$ 从小到大。访问顺序是 \(A_0[0];\quad A_1[0],A_0[1];\quad A_2[0],A_1[1],A_0[2];\quad A_3[0],A_2[1],A_1[2],A_0[3];\ \dots\)
第四步（去除重复）：按上述顺序走一遍，只保留首次见到的元素，之后重复出现的一律跳过。设去重后得到的序列为 \(b_0,b_1,b_2,b_3,\dots\)
第五步（验证这是到 $\mathbb{N}$ 的双射）：
- 每个元素都出现：任取 $x\in\bigcup_i A_i$，则存在某个 $i$ 使 $x\in A_i$，从而 $x=g_i(j)$ 对某个 $j$ 成立（因为 $g_i$ 满射）。于是 $x$ 出现于表格第 $i$ 行第 $j$ 列的格子里，而反对角线扫描迟早会访问这个格子（格子 $(i,j)$ 在第 $i+j=\text{const}$ 条对角线上，前面的对角线只有有限条、每条只有有限格）。既然 $x$ 出现过，去重后的序列里就一定有它。
- 每个元素只出现一次：去重规则保证序列中任意两项不相等。
- 每一项都确实属于并集：显然。
因此 $b_0,b_1,b_2,\dots$ 是 $\bigcup_i A_i$ 的一个无重复无遗漏的枚举，即存在双射 $\mathbb{N}\to\bigcup_i A_i$（把 $n$ 映到 $b_n$）。故并集可数。$\blacksquare$
【证明机制解说】：这个定理是”无穷也有算术”的第一次真正兑现——它说 $\aleph_0+\aleph_0+\aleph_0+\cdots=\aleph_0$（可数多个可数无穷相加仍是可数无穷）。它的全部工作就是把两个无穷压成一个：一维的 $i$（集合下标）和另一个一维的 $j$（集内下标）被反对角线编织成单个维度。这个”编织”动作是本讲后面处理 $\mathbb{Q}$、字符串、多项式的通用机器。
反例（如果适用）：定理要求”可数多个可数集”。如果是不可数多个可数集，结论就不再成立。具体例子：对每个实数 $r\in[0,1]$，取单点集 $\{r\}$——每个 $\{r\}$ 是可数的（有限），但 $\bigcup_{r\in[0,1]}\{r\}=[0,1]$ 不可数。所以”可数多个”这个条件是本质的，不能省。
定理 12.4：有理数集 $\mathbb{Q}=\left\{\frac{a}{b}:a,b\in\mathbb{Z},\ b\neq 0\right\}$ 可数。
证明策略：用 Cantor–Bernstein 夹逼，只造一个单射。具体路线：先证 $\vert \mathbb{N}\vert \le\vert \mathbb{Q}\vert $（平凡），再证 $\vert \mathbb{Q}\vert \le\vert \mathbb{N}\vert $——办法是把 $\mathbb{Q}$ 嵌入 $\mathbb{Z}\times\mathbb{Z}$，再用定理 12.2 型枚举。为什么不直接造双射？ 因为有理数有重复表示（$\frac{1}{2}=\frac{2}{4}=\frac{3}{6}$），直接枚举必然撞车，造双射反而麻烦。单射就足够了，这正是 Cantor–Bernstein 定理的用武之地。
逐步推导：
第一步（反向的平凡单射）：$\mathbb{N}\subseteq\mathbb{Q}$（每个自然数 $n$ 就是 $n/1$），故恒等嵌入 $\mathbb{N}\to\mathbb{Q}$ 是单射，于是 $\vert \mathbb{N}\vert \le\vert \mathbb{Q}\vert $。这一步不需要任何技巧。
第二步（把有理数交给整数对）：任取 $q\in\mathbb{Q}$，$q$ 至少有一种表示 $q=a/b$，其中 $a,b\in\mathbb{Z}$、$b\neq 0$。把分子分母同乘 $-1$ 可得 $b>0$ 的表示；再把分子分母同除 $\gcd(a,b)$ 可得最简表示 (lowest terms)，即 $\gcd(a,b)=1$、$b>0$。于是 \(q\ \longmapsto\ (a,b)\in\mathbb{Z}\times\mathbb{Z}_{>0}\subseteq\mathbb{Z}\times\mathbb{Z}\) 其中 $(a,b)$ 是 $q$ 的唯一最简表示。唯一性是关键：$q=a/b=a^{\prime}/b^{\prime}$ 且两组都最简时必有 $a=a^{\prime},b=b^{\prime}$（由整数唯一分解，或由 $\gcd$ 的整除论证）。所以这个映射是单射。
第三步（$\mathbb{Z}\times\mathbb{Z}$ 可数）：$\mathbb{Z}$ 可数（定理 12.1），$\mathbb{Z}\times\mathbb{Z}$ 就是两个可数集做配对。用螺旋枚举 (spiral enumeration) 显式展开它：
螺旋路径（从原点出发，一圈比一圈大）：
┌───────────────────────────┐
│ 19 18 17 16 15 14 13│
│ 20 5 4 3 2 11 12│
│ 21 6 0 1 10 27 ...│ ← 中心是 (0,0)
│ 22 7 8 9 25 26 ...│
│ 23 24 33 32 31 30 29│
└───────────────────────────┘
对应坐标（与官方 Note 的编号完全一致）：
0:(0,0) 1:(1,0) 2:(1,1) 3:(0,1) 4:(-1,1) 5:(-1,0)
6:(-1,-1) 7:(0,-1) 8:(1,-1) 9:(2,-1) 10:(2,0) 11:(2,1)
12:(2,2) 13:(1,2) 14:(0,2) 15:(-1,2) 16:(-2,2) 17:(-2,1)
18:(-2,0) 19:(-2,-1) 20:(-2,-2) ...
每个 $(a,b)\in\mathbb{Z}\times\mathbb{Z}$ 恰好占据螺旋上的一个位置（因为螺旋是逐圈向外、每圈穷尽该圈所有格子，不重不漏），所以”位置编号”是一个双射 $\sigma:\mathbb{Z}\times\mathbb{Z}\to\mathbb{N}$，$\mathbb{Z}\times\mathbb{Z}$ 可数。
第四步（复合出单射）：定义 $f:\mathbb{Q}\to\mathbb{N}$ 为 \(f(q)=\sigma\bigl(\text{$q$ 的最简表示 (a,b)}\bigr).\) 这是”单射 ∘ 单射”，从而是单射。
- 它是良定义的：$q$ 的最简表示唯一，所以 $f(q)$ 不依赖表示的选择。这一步必须写出来，否则证明有漏洞。
- 它是单射：若 $f(q_1)=f(q_2)$，则 $\sigma(a_1,b_1)=\sigma(a_2,b_2)$，由 $\sigma$ 单射得 $(a_1,b_1)=(a_2,b_2)$，于是 $q_1=a_1/b_1=a_2/b_2=q_2$。
因此 $\vert \mathbb{Q}\vert \le\vert \mathbb{N}\vert $。
第五步（夹逼收口）：已有 $\vert \mathbb{N}\vert \le\vert \mathbb{Q}\vert $ 与 $\vert \mathbb{Q}\vert \le\vert \mathbb{N}\vert $，由 Cantor–Bernstein 定理存在双射 $\mathbb{Q}\to\mathbb{N}$，故 $\vert \mathbb{Q}\vert =\vert \mathbb{N}\vert $，$\mathbb{Q}$ 可数。$\blacksquare$
用反对角线（而非螺旋）写出 $\mathbb{Q}$ 的显式枚举：如果不想绕道 Cantor–Bernstein，也可以直接在 $\mathbb{Z}\times\mathbb{Z}_{>0}$ 上做反对角线，并跳过非最简的格子。按”壳” $s=\vert a\vert +b$ 从小到大，壳内 $a$ 从小到大：
壳 s=1: (0,1) → 0/1
壳 s=2: (-1,1) (0,2) (1,1) → -1/1, (0/2 跳过), 1/1
壳 s=3: (-2,1) (-1,2) (0,3) (1,2) (2,1) → -2/1, -1/2, (0/3 跳), 1/2, 2/1
壳 s=4: (-3,1)(-2,2)(-1,3)(0,4)(1,3)(2,2)(3,1) → -3/1, (跳过), -1/3, (跳), 1/3, (跳), 3/1
壳 s=5: (-4,1)(-3,2)(-2,3)(-1,4)(0,5)(1,4)(2,3)(3,2)(4,1) → -4/1, -3/2, -2/3, -1/4, (跳), 1/4, 2/3, 3/2, 4/1
...
去重后前 19 个有理数（跳过 gcd≠1 的格子）：
0/1, -1/1, 1/1, -2/1, -1/2, 1/2, 2/1, -3/1, -1/3, 1/3,
3/1, -4/1, -3/2, -2/3, -1/4, 1/4, 2/3, 3/2, 4/1
注意 $\frac{3}{4}$ 出现在壳 $s=7$（$(-3,1)\dots(3,1)$ 里的 $(3,4)$），位置比较靠后——这正是”有理数看起来比自然数多得多”的量化体现：虽然一样多，但编号有稀疏。我们还可以数一数密度：在螺旋的 $0\sim 199$ 号位置中共有 67 个格子的最简表示合法（$b>0$ 且 $\gcd(a,b)=1$），比例约 $1/3$。
【证明机制解说】：核心洞察是“约分去重”让单射成为可能。$\mathbb{Q}$ 之所以看起来很”大”（任何两个自然数之间都有无穷多个有理数，即稠密 (dense)），是因为我们在用”序”的眼光看它——在 $\le$ 这个序下 $\mathbb{Q}$ 无处不密。但基数用的是”配对”的眼光，与序无关。一旦允许打乱顺序，稠密性就不再是障碍。这和 Lecture 14 要讲的计数问题形成有趣对照：序上的稠密 ≠ 基数上的更大。
反例（如果适用）：若跳过约分这一步，映射 $q\mapsto\sigma(a,b)$ 会不是单射：$\frac{1}{2}$ 与 $\frac{2}{4}$ 会映到不同位置，同一个有理数被数两次，这时的枚举不构成双射（虽然仍可”去重”补救，但那正是我们上面用反对角线版本做的事）。“良定义”是这类构造中最容易翻车的环节。
定理 12.5：所有有限长二进制串的集合 $\{0,1\}^*=\{\varepsilon,0,1,00,01,10,11,000,\dots\}$ 可数（$\varepsilon$ 表示空串 (empty string)，即长度为 0 的唯一串）。
证明策略：直接构造双射。”按长度递增、同长度内按字典序”给出一个显式列表，再把列表下标当作编号。为什么这个定理至关重要？ 因为一台程序本质上就是一个有限长的比特串，所以”所有程序”这个集合可数。下一讲的停机问题证明将整个儿建立在这一点上：程序可数，因此可以排成 $P_0,P_1,P_2,\dots$，于是可以做对角线。
逐步推导：
第一步（分块）：按长度把 $\{0,1\}^*$ 分成 \(L_\ell=\{\text{所有长度为 }\ell\text{ 的二进制串}\},\qquad \vert L_\ell\vert =2^\ell.\) $L_0=\{\varepsilon\}$，$L_1=\{0,1\}$，$L_2=\{00,01,10,11\}$，$L_3=\{000,001,\dots,111\}$。每一块都有限（这一点与定理 12.2 完全同构）。
第二步（块内定序、块间递增）：先列 $L_0$，再列 $L_1$，再 $L_2$，……；同一块内按二进制数值（即字典序）从小到大。得到列表 \(\varepsilon,\ 0,\ 1,\ 00,\ 01,\ 10,\ 11,\ 000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111,\ 1000,\dots\)
第三步（写出编号公式）：第 $\ell$ 块之前（长度 $0$ 到 $\ell-1$）共有 $\sum_{k=0}^{\ell-1}2^k=2^\ell-1$ 个串。所以对长度 $\ell$、二进制值为 $v$（$0\le v<2^\ell$）的串 $s$， \(\mathrm{idx}(s)=\bigl(2^{\ell}-1\bigr)+v,\qquad \ell=\vert s\vert .\) 逐项验证：$\mathrm{idx}(\varepsilon)=2^0-1+0=0$ ✓；$\mathrm{idx}(0)=2^1-1+0=1$ ✓；$\mathrm{idx}(1)=2^1-1+1=2$ ✓；$\mathrm{idx}(00)=2^2-1+0=3$ ✓；$\mathrm{idx}(11)=2^2-1+3=6$ ✓；$\mathrm{idx}(111)=2^3-1+7=14$ ✓；$\mathrm{idx}(1000)=2^4-1+8=23$ ✓（长度 $\le 3$ 的串共 15 个，占编号 $0\sim 14$，所以 $1000$ 从 15 开始，是长度 4 的第 9 个，$15+8=23$ ✓）。
第四步（验证双射）：每个串恰属于一个 $L_\ell$，在块内有唯一序号 $v$，故 $\mathrm{idx}$ 有唯一值（单射）；反过来，每个 $z\in\mathbb{N}$ 唯一确定 $\ell=\lfloor\log_2(z+1)\rfloor$ 与 $v=z-(2^\ell-1)$，从而唯一确定一个串（满射）。故 $\mathrm{idx}$ 是双射，$\{0,1\}^*$ 可数。$\blacksquare$
【证明机制解说】：这个证明的手法值得单独记住——“按长度分块，每块有限，块间递增”。它是”反对角线”的变体：反对角线按 $i+j$ 分层，这里按 $\vert s\vert $ 分层，两者都满足”无穷多个有限块”这一条件。凡是集合能按某个”规模参数”分层、且每层只有有限个元素，这个集合就可数。$\mathbb{N}\times\mathbb{N}$、$\{0,1\}^*$、$\mathbb{N}[x]$、所有程序、所有证明——全都是这一个模板。
推广：同样的构造给出任意有限字母表 $\Sigma$ 上的有限串集 $\Sigma^*$ 可数（只需把字母表编号，再把串看成 $\vert \Sigma\vert $ 进制数）。特别地三元串集 $\{0,1,2\}^*$ 可数，这是下一个定理的零件。
反例（如果适用）：注意区分 $\{0,1\}^*$（有限长串，可数）与 $\{0,1\}^\infty$（无限长二进制串，即从 $\mathbb{N}$ 到 $\{0,1\}$ 的函数全体，等价于 $\mathcal{P}(\mathbb{N})$，不可数）。两者的差别只在”长度是否有限”，但基数差了整整一级。这是初学者最容易混的一对概念，务必记牢：“每个元素有限”不等于”整体有限”，也不等于”整体可数”——$\{0,1\}^*$ 每个元素有限而整体仍可数，$\{0,1\}^\infty$ 每个元素无限且整体不可数。
定理 12.6：所有以自然数为系数的多项式之集 $\mathbb{N}[x]$ 可数。进一步，所有代数数 (algebraic number)（即某个非零整系数多项式的根）之集可数。
证明策略：构造单射 $\mathbb{N}[x]\to\{0,1,2\}^*$ 再用定理 12.5。编码器的设计要点是”可唯一解码“：我们要把一串自然数（系数）编码成一个不含歧义的串，用分隔符 $2$ 来标记边界（因为 $0,1$ 已经在二进制里用掉了，只有 $2$ 能当分隔符）。
逐步推导：
第一步（编码方案）：设 $p(x)=a_dx^d+\cdots+a_1x+a_0$，其中 $a_k\in\mathbb{N}$。把每个系数 $a_k$ 写成二进制串 $B(a_k)$（约定 $B(0)$ 为空串，即”没有 1 和 0 写出来”；或者更省事地直接写 $0$），然后用 $2$ 把这些二进制串从高次到常数串起来，得到三元串 \(f(p)=B(a_d)\ 2\ B(a_{d-1})\ 2\ \cdots\ 2\ B(a_0).\)
第二步（算例，与官方 Note 一致）：取 $p(x)=5x^5+2x^4+7x^3+4x+6$，系数向量（从高次到常数）是 $(5,2,7,0,4,6)$。二进制分别是 \(5\to101,\quad 2\to10,\quad 7\to111,\quad 0\to 0,\quad 4\to100,\quad 6\to110.\) 串起来（把零系数也保留，使位置信息不丢）： \(f(p)=101\,2\,10\,2\,111\,2\,0\,2\,100\,2\,110=\texttt{10121021112021002110}.\) 注意官方 Note 不加零系数（它直接忽略 0 系数），得到 $\texttt{101210211121002110}$。两种约定都能用，只要前后一致：区别在于”零系数是否占位”。本项目采用保留零系数的版本，因为解码时位置即幂次，不必另外记次数，更不易出错。
第三步（验证单射 —— 关键在可唯一解码）：给定编码串，按字符 $2$ 切分（$2$ 只作分隔符，绝不出现在系数内部，因为二进制只用 $0,1$），得到若干块 $B(a_d),B(a_{d-1}),\dots,B(a_0)$；每块按二进制读回一个自然数。于是原多项式被唯一还原（块的个数给出次数 $d$，块的顺序给出从高次到低次，各块的值给出系数）。因此若 $f(p)=f(q)$，切分与读回后得到相同的系数序列，从而 $p=q$，$f$ 是单射。
第四步（落回可数）：由定理 12.5 的推广，$\{0,1,2\}^$ 可数，存在双射 $h:\{0,1,2\}^\to\mathbb{N}$。复合 $h\circ f:\mathbb{N}[x]\to\mathbb{N}$ 是单射，故 $\vert \mathbb{N}[x]\vert \le\vert \mathbb{N}\vert $。又 $\mathbb{N}\subseteq\mathbb{N}[x]$（把自然数 $n$ 当常数多项式），故 $\vert \mathbb{N}\vert \le\vert \mathbb{N}[x]\vert $。由 Cantor–Bernstein 得 $\vert \mathbb{N}[x]\vert =\vert \mathbb{N}\vert $，$\mathbb{N}[x]$ 可数。$\blacksquare$
第五步（代数数可数）：设整系数多项式 $p\neq 0$ 的次数为 $d$，则 $p$ 至多有 $d$ 个（复）根，从而至多有限个实根。令 $\mathcal{A}$ 为所有代数数之集， \(\mathcal{A}=\bigcup_{p\in\mathbb{Z}[x],\,p\neq 0}\{\,r\in\mathbb{R}:p(r)=0\,\}.\) 这是可数多个有限集之并（因为 $\mathbb{Z}[x]$ 可数，与 $\mathbb{N}[x]$ 同理——把每个整数写成带符号的二进制即可编码），而每个有限集可数。由定理 12.3，$\mathcal{A}$ 可数。$\blacksquare$
【证明机制解说】：这里出现了本讲最有价值的思维方式——为了证明可数，不必写出显式枚举，只要给出一个可唯一解码的编码 (encoding) 即可。编码本质上是一个单射，而单射足以（配合 Cantor–Bernstein）确定基数。这个思想的威力在第五步爆发：我们根本不知道代数数有哪些、有多少，但我们知道每个代数数都是某个可数集合族里的有限集的一员，于是它可数。“可数多个有限集的并”是一个可以反复套用的公式。
反例（如果适用）：编码必须保证可唯一解码，否则单射性会崩。如果把系数直接拼在一起不加分隔符，$p(x)=5x^2+2x+7$ 的系数 $(5,2,7)$ 及 $(52,7)$、$(5,27)$ 都会编码成同一个串 $\texttt{10127}$，$f$ 就不是单射了。分隔符 $2$ 的作用不是装饰，而是防止歧义。
定理 12.7（Cantor 定理）：设 $A$ 是任意集合，$\mathcal{P}(A)=\{T:T\subseteq A\}$ 是它的幂集 (power set)。则 \(\vert A\vert < \vert \mathcal{P}(A)\vert .\) 特别地 $\vert \mathbb{N}\vert <\vert \mathcal{P}(\mathbb{N})\vert $：自然数的子集比自然数”多”得多。
证明策略：反证法 + 对角线论证。这是一个通用的、不依赖 $A$ 是否可数的证明。要证 $\vert A\vert <\vert \mathcal{P}(A)\vert $，需证两件事：$\vert A\vert \le\vert \mathcal{P}(A)\vert $（容易，用单元素子集）和不存在满射 (onto) $A\to\mathcal{P}(A)$（这才是难点）。而”不存在满射”的标准打法就是：假设有满射 $f$，构造一个被 $f$ 漏掉的集合 $D$，与满射矛盾。
逐步推导：
第一步（先看有限情形，建立直觉）：$\vert S\vert =k$ 时 $\vert \mathcal{P}(S)\vert =2^k$。理由：每个子集 $T\subseteq S$ 对应一个 $k$ 位比特串（特征向量 (characteristic vector)），第 $i$ 位为 1 表示 $S$ 的第 $i$ 个元素在 $T$ 里。例如 $S=\{1,2,3\}$，共 $2^3=8$ 个子集：
比特串 子集 比特串 子集
000 → {} 100 → {1}
001 → {3} 101 → {1,3}
010 → {2} 110 → {1,2}
011 → {2,3} 111 → {1,2,3}
（约定第 1 位对应元素 1，第 3 位对应元素 3）
$2^k$ 的来历：每一位独立二选一（在/不在），共 $\underbrace{2\times2\times\cdots\times2}_{k}=2^k$ 种
（注：表中位串的书写顺序与”第 $i$ 位对应第 $i$ 个元素”的约定不必逐字对应，只要选取一种固定约定即可。这里的约定是从右往左读位。）有限情形下 $2^k>k$ 对所有 $k\ge 0$ 成立（$k=0$ 时 $1>0$；$k\ge 1$ 时可由归纳或由 $2^k\ge k+1$ 证明）。但这不能推出无穷情形——我们必须用对角线。
第二步（$\vert A\vert \le\vert \mathcal{P}(A)\vert $）：映射 $a\mapsto\{a\}$ 把 $A$ 单射地映入 $\mathcal{P}(A)$（不同的 $a$ 给出不同的单元素集），所以 $\vert A\vert \le\vert \mathcal{P}(A)\vert $。
第三步（假设满射，准备打对角线）：为引出矛盾，假设存在满射 $f:A\to\mathcal{P}(A)$。为了直观，先取 $A=\mathbb{N}$，把 $f$ 想成一张无穷表：第 $n$ 行是集合 $f(n)\subseteq\mathbb{N}$ 的特征向量（$a_{n,k}=1$ 表示 $k\in f(n)$，$0$ 表示 $k\notin f(n)$）：
k=0 k=1 k=2 k=3 k=4 k=5 ...
┌─────┬─────┬─────┬─────┬─────┬─────┐
f(0) │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ ← 即 f(0) = {0,3}
├─────┼─────┼─────┼─────┼─────┼─────┤
f(1) │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ ← 即 f(1) = {}
├─────┼─────┼─────┼─────┼─────┼─────┤
f(2) │ 1 │ 0 │ 1 │ 0 │ 0 │ 0 │ ← 即 f(2) = {0,2}
├─────┼─────┼─────┼─────┼─────┼─────┤
f(3) │ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ ← 即 f(3) = {1,3,4}
├─────┼─────┼─────┼─────┼─────┼─────┤
f(4) │ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ ← 即 f(4) = {0,1,2,4}
├─────┼─────┼─────┼─────┼─────┼─────┤
... │ ... │ ... │ ... │ ... │ ... │ ... │
└─────┴─────┴─────┴─────┴─────┴─────┘
╲ ╲ ╲ ╲ ╲
╲ ╲ ╲ ╲ ╲ ← 对角线上的格子 (k,k)
a₀₀=1 a₁₁=0 a₂₂=1 a₃₃=1 a₄₄=1
第四步（构造”反骨集合” $D$）：定义 \(\boxed{\,D=\{\,a\in A\ :\ a\notin f(a)\,\}\,}\) 即 $D$ 由所有不属于自己像的元素组成。在特征向量的语言里，$D$ 的特征向量就是”把对角线上每一位取反”得到的那一行：
对角线上读出的位串（a₀₀ a₁₁ a₂₂ a₃₃ a₄₄ ...） = 1 0 1 1 1 ...
逐位取反 = 0 1 0 0 0 ...
↓
D 的特征向量 = 0 1 0 0 0 ... ⇒ D = {1} （在此示例中）
第五步（$D\in\mathcal{P}(A)$）：$D$ 是 $A$ 的子集（它的定义就是从 $A$ 里筛元素），所以 $D\in\mathcal{P}(A)$。这一步看似废话，但它保证了 $D$ 是一个”合法的候选像”，从而下一步的”没被映到”才构成对满射的否定。
第六步（$D$ 不在 $f$ 的像中 —— 核心矛盾）：假设 $D$ 在像中，即存在 $a^\in A$ 使 $f(a^)=D$。考察 $a^*$ 是否属于 $D$，只有两种可能，且两种都矛盾：
- *情形 A：$a^\in D$*。由 $D$ 的定义（$D$ 中元素的定义就是”不属于自己的像”），$a^\in D$ 意味着 $a^\notin f(a^)$。但已假设 $f(a^)=D$，所以 $a^\notin D$。矛盾。
- *情形 B：$a^\notin D$。即 $a^\notin f(a^)$。但 $D$ 的定义正是把所有满足 $a\notin f(a)$ 的 $a$ 收进来*，所以 $a^$ 应当属于 $D$。矛盾。
两种情形都矛盾，所以”$D$ 在像中”这个假设是假的，即 $D\notin f(A)$。
第七步（收口）：$D\in\mathcal{P}(A)$ 且 $D\notin f(A)$，说明 $f$ 不是满射。这与”$f$ 是满射”的假设矛盾。既然任何函数 $f:A\to\mathcal{P}(A)$ 都不可能满射，就不存在双射 $A\to\mathcal{P}(A)$，故 $\vert A\vert \neq\vert \mathcal{P}(A)\vert $。结合第二步的 $\vert A\vert \le\vert \mathcal{P}(A)\vert $，得 $\vert A\vert <\vert \mathcal{P}(A)\vert $。$\blacksquare$
【证明机制解说】：$D$ 的定义 $D=\{a:a\notin f(a)\}$ 是整个证明的灵魂，它的构造思想可以用一句话概括：“让 $D$ 在第 $a^$ 个问题上与 $f(a^)$ 唱反调。” 由于 $D$ 被设计为”处处与自己的候选人不同”，它就不可能等于任何 $f(a)$。这是一个自指式 (self-referential) 的构造——它用 $f$ 的像去定义一个新的、必然不在该像中的对象。这正是说谎者悖论（”这句话是假的”）的数学化身，也正是下一讲停机问题证明的同一招。特别值得注意：这个证明没有任何地方用到 $A$ 可数，它对一切集合成立。所以”无穷有很多层”是集合论的普遍现象：$\mathbb{N},\mathcal{P}(\mathbb{N}),\mathcal{P}(\mathcal{P}(\mathbb{N})),\dots$ 一层严格大于一层。
反例（如果适用）：$D$ 的定义必须是”$a\notin f(a)$”而不是“$a\in f(a)$”。若取 $E=\{a:a\in f(a)\}$，这个构造不能推出矛盾：假设 $E=f(a^)$，那么”$a^\in E$”与”$a^\in f(a^)$”是同一句话，两种情形自我一致，得不到矛盾。所以”取反”是本质的。这个反例精确地说明了为什么对角线必须翻转对角元素。
定理 12.8：闭区间 $[0,1]$ 上的实数集不可数，从而 $\mathbb{R}$ 也不可数。
证明策略：反证法 + 对角线论证。假设 $[0,1]$ 可数，则有一个完整列表 $f(0),f(1),f(2),\dots$。我们把每个数写成无穷小数，读对角线得到一串数字，逐位改动得到一个新数 $s$，证明 $s\in[0,1]$ 但不在列表里。与定理 12.7 的结构完全一样，只是”集合的特征向量”换成了”无穷小数的数字序列”。
逐步推导：
第一步（唯一表示的技术准备）：实数的小数表示不唯一：$0.4999\ldots=0.5$（因为 $0.4999\ldots=\frac{4}{10}+\frac{9}{100}+\frac{9}{1000}+\cdots=0.4+\frac{9/100}{1-1/10}=0.4+0.1=0.5$），同理 $0.999\ldots=1$。为了消除歧义，我们规定统一使用”不以 9 结尾”的表示： \(x\in[0,1]\quad\Longrightarrow\quad x=0.d_1d_2d_3\ldots\ \text{且数字序列 }(d_k)\text{ 中不含"从某位起全是 9"}。\) （等价的说法是”不以连续的 9 结尾”或”没有末尾全 9”。）在这个约定下，$(d_k)$ 与 $x$ 一一对应。这条约定是整个证明能站住的地基，绝不能省。
第二步（反证假设）：假设 $[0,1]$ 可数，则存在双射 $f:\mathbb{N}\to[0,1]$（若只是单射而非满射，用”可数”定义配一个满射即可；我们用满射 $f$，因为证明只需满射不成立）。把列表按上述规范表示写出来：
第1位 第2位 第3位 第4位 第5位 第6位 ... （小数点后）
┌──────┬──────┬──────┬──────┬──────┬──────┐
f(0) │ 5 │ 2 │ 1 │ 4 │ 9 │ 3 │ ... = 0.521493...
├──────┼──────┼──────┼──────┼──────┼──────┤
f(1) │ 1 │ 4 │ 1 │ 6 │ 2 │ 9 │ ... = 0.141629...
├──────┼──────┼──────┼──────┼──────┼──────┤
f(2) │ 9 │ 4 │ 7 │ 8 │ 2 │ 7 │ ... = 0.947827...
├──────┼──────┼──────┼──────┼──────┼──────┤
f(3) │ 5 │ 3 │ 0 │ 9 │ 8 │ 1 │ ... = 0.530981...
├──────┼──────┼──────┼──────┼──────┼──────┤
f(4) │ 2 │ 7 │ 3 │ 1 │ 4 │ 1 │ ... = 0.273141...
├──────┼──────┼──────┼──────┼──────┼──────┤
... │ ... │ ... │ ... │ ... │ ... │ ... │
└──────┴──────┴──────┴──────┴──────┴──────┘
╲ ╲ ╲ ╲ ╲ ╲
d₁¹ d₂² d₃³ d₄⁴ d₅⁵ d₆⁶ ← 对角线元素（i 行第 i 位）
对角线读出来： 5 4 7 9 4 1 ...
记作 r = 0.547941... （它本身也是一个 [0,1] 中的实数）
（上式记号 $d_i^{(i)}$ 表示”列表第 $i$ 个数的小数第 $i$ 位”。）
第三步（构造 $s$：逐位变形）：定义新数 $s=0.s_1s_2s_3\ldots$，其第 $k$ 位为 \(\boxed{\,s_k=(d_k^{(k)}+2)\bmod 10\,}\) 也就是把对角线每一位 $d$ 换成 $(d+2)\bmod 10$。在本例中 \(d^{(1..6)}=5,4,7,9,4,1\ \Longrightarrow\ s_{1..6}=7,6,9,1,6,3\ \Longrightarrow\ s=0.769163\ldots\)
第四步（$s$ 是合法的 $[0,1]$ 中的数，且规范表示无歧义）：
- 每个 $s_k\in\{0,1,\dots,9\}$，所以 $s$ 是合法小数。
$s$ 不以 9 结尾吗？ 这正是选择”加 2”而非”加 1”的原因。若某个 $k$ 满足 $d_k^{(k)}=9$，则 $s_k=(9+2)\bmod 10=1\ne 9$；若 $d_k^{(k)}=0$，则 $s_k=2\ne 9$。更一般地，$(d+2)\bmod 10\ne 9$ 当且仅当 $d\ne 7$；也就是说只有当对角位是 7 时 $s_k$ 才可能是 9。但这可能连续发生吗？ 为保证万无一失，官方给的替代方案更干净：把每位换成 $\{1,2,\dots,8\}$ 中的某个数，例如 $s_k=(d_k^{(k)}\bmod 8)+1$。这样 $s_k\in\{1,\dots,8\}$，永远不为 0 或 9，于是既不可能”末尾全 9”、也不可能”末尾全 0”，$s$ 的规范表示无任何歧义。本例中 $d=5,4,7,9\Rightarrow s=6,5,8,2\Rightarrow s=0.6582\ldots$。
我们同时给出两种规则的验算（都保证 $s_k\ne d_k^{(k)}$）： | 对角线位 $d$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:—|:—|:—|:—|:—|:—|:—|:—|:—|:—|:—| | 规则一 $(d+2)\bmod 10$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | | 规则二 $(d\bmod 8)+1$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 2 |
两种规则下均有 $s_k\ne d$（逐行核对即可），这是后一步的要害。
第五步（$s$ 不在列表中 —— 核心矛盾）：假设 $s$ 在列表中，即存在 $n\in\mathbb{N}$ 使 $f(n)=s$。考察两人的第 $n+1$ 位（注意：列表第 $n$ 个数记作 $f(n)$，它的第 $n+1$ 位就是 $d_{n+1}^{(n+1)}$）：
- 一方面，$f(n)=s$ 作为同一个数，其规范表示应当相同，故 $f(n)$ 的第 $n+1$ 位等于 $s_{n+1}$。
- 另一方面，由构造 $s_{n+1}=(d_{n+1}^{(n+1)}+2)\bmod 10\ne d_{n+1}^{(n+1)}$，即 $s_{n+1}\ne f(n)$ 的第 $n+1$ 位。
两者矛盾，所以 $s\ne f(n)$。但 $n$ 是任意的（上面论证对每个 $n$ 都成立），所以 $s$ 不等于列表中任何一个数，即 $s\notin f(\mathbb{N})$。
第六步（收口）：$s\in[0,1]$（第四步）但 $s\notin f(\mathbb{N})$，故 $f$ 不是满射。这推翻了”存在双射 $\mathbb{N}\to[0,1]$”的假设，所以 $[0,1]$ 不可数。
第七步（$\mathbb{R}$ 不可数）：因为 $[0,1]\subseteq\mathbb{R}$，若 $\mathbb{R}$ 可数则其子集 $[0,1]$ 也可数（子集可数：只需把 $\mathbb{R}$ 的枚举限制在 $[0,1]$ 上并去重），这与第六步矛盾。故 $\mathbb{R}$ 不可数。$\blacksquare$
【证明机制解说】：整个证明的”灵光一现”是把”函数在一点上的值”换成”数字在一位上的值”。定理 12.7 里我们比较的是”集合 $D$ 与 $f(a^)$ 在元素 $a^$ 上是否一致”，这里我们比较的是”数 $s$ 与 $f(n)$ 在小数第 $n+1$ 位上是否一致”。抽象结构完全一样：把 $\mathbb{N}$ 当作索引集合，把每个候选对象当作一个”无穷长的信息序列”（比特串或数字串），然后沿着索引 $k$ 修改第 $k$ 项，使新对象在第 $k$ 项上与候选 $k$ 不同。 这就是”对角线方法”的统一定义，也是 Lecture 13 停机问题证明的骨架。
反例（如果适用）：为什么把同样的论证用在 $\mathbb{Q}$ 上会失败？ 假设有人试图证明 $\mathbb{Q}\cap[0,1]$ 不可数，照抄上面的构造：取列表 $f(0),f(1),\dots$（现在都是有理数），读对角线、改位得到 $q$。这个论证不成立，因为改位后的 $q$ 未必是有理数——有理数的小数展开必须是最终循环的 (eventually periodic)，而随意改动对角位几乎必然破坏循环性，于是 $q\notin\mathbb{Q}\cap[0,1]$，我们没能构造出一个”应该在列表中却不在”的元素，矛盾链条从中间断开。这精确地说明了：对角线论证要求构造出的新对象落在原集合内。对 $\mathbb{R}$ 成立，是因为”任意数字序列都定义一个实数”；对 $\mathbb{Q}$ 不成立。这也从反面印证了：$\mathbb{Q}$ 确实可数，它不是漏网之鱼。
定理 12.9：Cantor 集 $C$（在 $[0,1]$ 中反复挖去中间三分之一后剩下的一切点）不可数，且与 $[0,1]$ 等势。由此可推出超越数 (transcendental number) 存在，且”绝大多数”实数是超越数。
证明策略：构造性证明的变体。先用三进制 (ternary) 表示刻画 $C$，得到一个极其简洁的描述（$C$ = 三进制只用 $0$ 和 $2$ 的数），再构造一个从 $C$ 到 $[0,1]$ 的满射。既然 $[0,1]$ 不可数，被它满射投影的 $C$ 也不可数。
逐步推导：
第一步（Cantor 集的构造与”长度归零”的错觉）：从 $[0,1]$ 开始，第 1 次挖去开区间 $(\frac13,\frac23)$，剩 $[0,\frac13]\cup[\frac23,1]$，总长 $\frac23$；第 2 次再对剩下的两段各挖中间三分之一，剩 4 段，总长 $\frac23\cdot\frac23=\frac49$；第 $n$ 次后总长 \(\left(\frac23\right)^n\ \xrightarrow{\ n\to\infty\ }\ 0.\) 具体数值：$n=1$ 时 $0.666667$，$n=2$ 时 $0.444444$，$n=3$ 时 $0.296296$，$n=5$ 时 $0.131687$，$n=10$ 时 $0.017342$，$n=20$ 时约 $3.007\times10^{-4}$。挖去的总长度是 $\sum_{k\ge 1}\frac{2^{k-1}}{3^k}=1$。
- 容易得出的错误结论：”长度变成了 0，所以 Cantor 集是空的。”
- 正确的结论：长度（测度 (measure)）为 0 不等于空集。Cantor 集非空（例如 $\frac13,\frac23,\frac19,\frac{1}{27}$ 等所有区间端点都在里面），而且它不含任何非平凡区间（是完全不连通的），但它的基数与整个 $[0,1]$ 一样大。这是”测度小”与”基数小”完全无关的经典范例。
第二步（三进制刻画）：三进制（trits 取值 $\{0,1,2\}$）下：
- $[0,1]$ 中每个数写成 $0.t_1t_2t_3\ldots$（同样约定不用全 2 结尾的歧义表示；端点需特殊处理，例如把 $\frac13$ 写成 $0.0\overline{2}$ 而不是 $0.1$，把 $\frac23$ 写成 $0.2$）。
- 第 1 次挖掉的中间三分之一 $(\frac13,\frac23)$ 恰好是首位为 1 的数，即 $0.1xxxx\ldots$。
- 第 2 次挖掉的是 $0.01xxxx\ldots$ 与 $0.21xxxx\ldots$，即第二位为 1 的数。
- 第 3 次挖掉第三位为 1 的数……第 $n$ 次挖掉第 $n$ 位为 1 的数。
于是被挖去的点 = 三进制展开中至少有一位为 1 的点，剩下的正是 \(\boxed{\,C=\{x\in[0,1]:\ x\ \text{有一个只含 }0,2\ \text{的三进制展开}\,\}\,}\) 逐项验算两个”意外”的点：
- $\frac14$：$\frac14=0.\overline{02}_3=0.020202\ldots_3$（用等比级数验算：$2\cdot3^{-2}+2\cdot3^{-4}+2\cdot3^{-6}+\cdots=\frac{2/9}{1-1/9}=\frac{2/9}{8/9}=\frac14$ ✓）。数字只有 0 和 2，所以 $\frac14\in C$。
- $\frac{3}{10}$：$0.3$ 的三进制展开为 $0.02200220022002\ldots_3$，同样只含 0 和 2，所以 $\frac{3}{10}\in C$。
第三步（构造从 $C$ 到 $[0,1]$ 的满射 $f$）：对 $x\in C$，取它只含 $0,2$ 的三进制展开 $x=0.t_1t_2t_3\ldots_3$，把每个数字除以 2（即 $0\mapsto0$，$2\mapsto1$），得到二进制小数 \(f(x)=0.\frac{t_1}{2}\frac{t_2}{2}\frac{t_3}{2}\ldots_{\ 2}.\) 例如 $x=0.0220_3\mapsto f(x)=0.0110_2$。
第四步（$f$ 是满射）：任取 $y\in[0,1]$，取它的二进制展开 $y=0.b_1b_2b_3\ldots_2$（$b_k\in\{0,1\}$）。把每位乘以 2 得到三进制数 $x=0.(2b_1)(2b_2)(2b_3)\ldots_3$，其数字只含 $0,2$，故 $x\in C$，且 $f(x)=y$。所以 $f$ 是满射。（$f$ 不是单射——例如 $0.20\overline{2}_3$ 与 $0.22_3$ 会映到同一个二进制数——但满射足够，因为我们只需要”$C$ 至少和 $[0,1]$ 一样大”。）
第五步（收口 $C$ 不可数）：$f:C\to[0,1]$ 满射，故 $\vert C\vert \ge\vert [0,1]\vert $。又 $C\subseteq[0,1]$，故 $\vert C\vert \le\vert [0,1]\vert $。由 Cantor–Bernstein，$\vert C\vert =\vert [0,1]\vert =\vert \mathbb{R}\vert $，$C$ 不可数。$\blacksquare$
第六步（超越数存在 —— 非构造性存在性证明的漂亮范例）：
- 定义：实数 $r$ 是代数数 (algebraic)，若它是某个非零整系数多项式的根；否则叫超越数 (transcendental)。
- 代数数可数：这是定理 12.6 第五步的结论。
- 实数不可数：这是定理 12.8 的结论。
- 于是：若不存在超越数，则 $\mathbb{R}$ = 代数数之集，而右边可数、左边不可数，矛盾。所以必然存在超越数。更强地：$\mathbb{R}\setminus\mathcal{A}$ 不可数（因为可数集从不可数集中挖掉后仍不可数），即几乎所有的实数都是超越数。
这个证明的非构造性值得大书一笔：它没有给出任何一个具体的超越数。它只是把两个可数性事实摆在一起，就断定”一定有”。数学史上，Liouville 在 1844 年构造出第一个超越数，Hermite 在 1873 年证明 $e$ 超越，Lindemann 在 1882 年证明 $\pi$ 超越——这些具体构造都很困难。但基数论证告诉我们，这样的数遍地都是，多到”随便扔一根针都能扎中一个”。更妙的是：此时此刻，你能说出名字的每一个具体实数（$\sqrt2$、$e$、$\pi$、$\ln 2$、$\gamma$……）几乎都是”例外”，而剩下的那个不可数的汪洋大海里的数，我们连命名都做不到——因为名字本身只是有限长的字符串，总共只有可数多个！名字可数，实数不可数，所以绝大多数实数永远无法被命名。 这是本讲最富哲学意味的结论。
【证明机制解说】：Cantor 集这一段展示了”三进制/二进制转换”作为证明工具的威力：把”几何的挖洞过程”翻译成”数字的限制条件”，几何难题立刻变成字符串问题，而字符串问题我们已经有现成的可数性/不可数性工具（定理 12.5、12.7）。这种”换一种表示让问题变形”的手法，与 Lecture 4-6 里”把同余问题换成模 $p$ 的域上运算”、Lecture 7-8 里”把秘密共享换成多项式插值”是同一种数学品味。
与经典问题的联系
1. 为什么计算机科学家必须关心无穷的大小：问题的层次
本讲的直接动机是：我们想知道”问题”是否比”程序”多。设 $\mathcal{F}$ 是所有函数 $g:\{0,1\}^*\to\{0,1\}$ 之集（每个函数代表一个”判定问题”：给定输入串，返回 yes/no）。
- 程序是可数的：一台程序（无论是 Python、C 还是图灵机）最终都表示为有限长的比特串。由定理 12.5，所有有限比特串之集 $\{0,1\}^$ 可数。程序是 $\{0,1\}^$ 的一个子集，故程序可数。
- 函数是不可数的：每个函数 $g:\{0,1\}^*\to\{0,1\}$ 由它在一列穷尽的输入 $\varepsilon,0,1,00,01,\dots$ 上的取值唯一确定，即由一条无穷比特串确定。所有无穷比特串之集 $\{0,1\}^\infty$ 与 $\mathcal{P}(\mathbb{N})$ 一一对应，由定理 12.7 不可数。故 $\mathcal{F}$ 不可数。
结论（鸽笼式论证）：设 $\mathcal{P}$ 为所有程序之集，$\mathcal{F}$ 为所有判定问题之集。每个程序至多计算一个函数（确定型程序的行为完全由源码决定），于是有一个从 $\mathcal{P}$ 到 $\mathcal{F}$ 的函数 $\mathrm{sem}:\mathcal{P}\to\mathcal{F}$（把程序映到它计算的函数）。因为 $\vert \mathcal{P}\vert =\aleph_0<\vert \mathcal{F}\vert $，$\mathrm{sem}$ 不可能满射（满射要求 $\vert \mathcal{P}\vert \ge\vert \mathcal{F}\vert $）。所以必有函数不属于任何程序的像——即存在不可计算的问题 (uncomputable problem)。
ASCII 图景：
程序集 P（可数） 函数集 F（不可数） ┌───┐ ┌─────────────────────────────┐ │ P0│──── sem ───────────────► │ f0 = sem(P0) │ │ P1│──── sem ───────────────► │ f1 = sem(P1) │ │ P2│──── sem ───────────────► │ f2 = sem(P2) │ │ P3│──── sem ───────────────► │ f3 │ │...│ │ ┌────────────────────────┐ │ └───┘ │ │ f* ← 没有任何程序映到这里│ │ 可数多个起点 │ └────────────────────────┘ │ └─────────────────────────────┘ 想象"用可数多个飞镖去打不可数多个靶子"——无论怎么扔，靶子都打不完。这是一次用计数（可数性）证明存在性的示范：我们连那个不可计算的函数长什么样都不知道，却知道它一定存在。与定理 12.9 证明超越数存在的手法完全同构。
2. 计数器论证 vs. 构造性论证：两种”证明不可能”的路径
- 计数路线（本讲）：证明”程序可数、问题不可数”，得到存在不可计算的问题，但指不出是哪一个。
- 对角线路线（下一讲）：直接构造（或指出）一个具体的不可计算问题——停机问题——并给出它不可计算的反证法证明。 两条路线互相印证：计数路线说明”不可计算”是常态（不可计算的函数占了压倒性多数），对角线路线则把其中一个抓出来示众。把这两条合起来看，你就明白”计算机不能做所有事”不是工程局限，而是数学定理。
3. 编码与压缩：为什么”可数”是一把尺子
定理 12.5–12.6 的编码技术（把结构映射为串、把串映射为自然数）在工程上就是序列化 (serialization)：
- Cantor 配对函数 $\pi(i,j)=\frac{(i+j)(i+j+1)}{2}+j$ 是”把二维坐标压成一维下标”的标准手法。它在实际代码里就是”用一个大整数编码一个二维键”（常见于把 $(x,y)$ 坐标存进单一整型键做哈希）。
- 多项式编码（系数二进制 + 分隔符 $2$）就是”把一个结构体序列化成字节流”的思想雏形。
- 一个自然的信息论直觉：既然 $\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$、$\mathbb{N}[x]$ 全部可数，它们之间可以互相编码、互相解码，从而没有哪一个”信息量更大”。而 $\mathbb{R}$ 不可数，意味着实数带的信息量严格更多——这与 Lecture 23 之后（集中不等式、连续分布）要面对的”连续型随机变量无法用有限比特精确表示”这一事实同源。
4. 与编译器和程序分析的联系
编译器会做各种静态分析（判断代码里某变量是否可达、某循环是否有副作用）。本讲 + 下一讲告诉我们：这类分析的”完全版本”必然不可判定（下一讲将用”归约”精确证明）。工程上的应对不是追求完美，而是：(a) 保守近似（能判定的子类判定，其余一律报”不确定/不安全”）；(b) 加超时（模拟 $k$ 步，超了就放弃）。理解”为什么不可能完美”是理解”为什么工程上要这样妥协”的前提。
与其他讲次的关联
- 与 Lecture 0–L03（证明工具箱）：本讲的证明方法全部来自前面。定理 12.1 是直接证明 + 分情形（按奇偶、按正负分类）；定理 12.7、12.8 是反证法 (proof by contradiction)——这是 L02 “证明技巧 II” 里学的技巧第一次被用于”证明不可能”；定理 12.3 的”每个元素迟早被访问到”隐含使用了 L00 关于”前 $k$ 条对角线只有有限多格”的有限性推理；定义与量词（”$f$ 是满射 $\iff (\forall y\exists x)f(x)=y$”）的设置则直接来自 L01 的命题逻辑与谓词逻辑。可以说：前面每一讲都在为这一讲磨刀。
- 与 Lecture 3（Induction）：定理 12.5 中”$\{0,1\}^*$ 的枚举不重不漏”以及 $\{0,1\}^\infty$ 与 $\mathcal{P}(\mathbb{N})$ 的对应，背后的”按长度分层”结构在形式上就是 L03 归纳法的分块思想（把无限过程切成无限多个有限步骤，每步可验证）。定理 12.2 中”前 $s$ 个壳共有 $\frac{s(s+1)}{2}$ 个元素”的求和公式在课堂上通常由 L03 的归纳法证明。
- 与 Lecture 4–L06（模运算、Euclid、RSA）：定理 12.4 依赖最大公约数与最简表示的唯一性——这直接是 L05 “欧几里得算法”的内容。更重要的一层联系：L04–L06 表面上研究有限结构（模 $m$ 的剩余类只有 $m$ 个），但 RSA 的明文空间是 $\{0,1\}^*$ 的有界片段。正是因为明文是有限串（可数），”给每个消息编号”这件事才有意义。
- 与 Lecture 7–L08（Polynomials / Secret Sharing）：定理 12.6 把多项式当作可编码对象，而”一个次数 $d$ 的非零多项式至多有 $d$ 个根”（代数基本定理 (Fundamental Theorem of Algebra) 的弱形式）是 L07 秘密共享方案正确性的基石。同一事实在这里被用来证明”代数数可数”：多项式可数 + 每个多项式有限个根 ⟹ 根的总集可数。
- 与 Lecture 9–L10（Graphs）：图也可以被编码成有限串（顶点数、邻接矩阵按位列出），所以所有有限图的集合可数——这是把定理 12.5 的模板再一次套用。反过来说，如果允许图有可数无穷多个顶点，”所有图之集”就不可数了。这与 L10 中的超立方体（$n$ 维立方体图是有限图）形成对照。
- 与 Lecture 11（Stable Matching）：Gale–Shapley 算法是一个总是终止的程序，所以它计算的函数是可计算的。Stable Matching 的存在性证明（”算法终止时配对照一定是稳定的”）与停机问题形成反差：前者保证终止，后者的核心正是”终止与否不可判定”。
- 与 Lecture 13（Computability）：这是本讲最直接的衔接。下一讲会：
- 用定理 12.5（程序可数）把程序排成 $P_0,P_1,P_2,\dots$；
- 用定理 12.7 的对角线技巧（”翻转对角元素”）证明停机问题不可判定；
- 用”程序可数 vs 函数不可数”（本讲第 1 条经典联系）说明”不可计算的函数多得是”。
- 与 Lecture 14（Counting）及之后：可数性是”无穷版的计数”。L14 教有限集的计数法则（乘法法则、容斥、双射计数），本讲证明 $\vert \mathbb{N}\vert =\vert \mathbb{Q}\vert $ 的”约分去重”与 L14 的”双射计数”是同一件事在无穷上的推广。此外，L14 的计数结论（如 $\binom{n}{k}$）在 L15 概率公理中用来计算等可能样本空间的大小，那里的样本空间都是有限的——本讲正好说明了”为什么概率论默认样本空间有限或可数”（不可数样本空间上”等可能”没有定义）。
关键要点
- 等势的定义是双射，可数是”能用自然数编号”：$\vert A\vert =\vert B\vert \iff$ 存在双射 $A\to B$；$S$ 可数 $\iff$ $S$ 有限或存在双射 $\mathbb{N}\to S$。不要用包含关系判断无穷集的大小——$\mathbb{N}\subsetneq\mathbb{Z}$ 但 $\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert $，无穷集可以和自己的真子集等势（$\vert \mathbb{N}\vert =\vert 2\mathbb{N}\vert $）；可数不等于有限，也不要求”列完”，只要求每个元素被赋予有限的编号且编号不重不漏。这两条定义是本讲一系列反直觉结论（而非矛盾）的根源。
- 对角线枚举的模板：把无穷集切成可数多个有限块（按 $i+j$ 分层、按串长分层、按 $\vert a\vert +b$ 分壳），块间递增、块内定序。这一个模板通吃 $\mathbb{N}\times\mathbb{N}$、$\{0,1\}^*$、$\mathbb{Q}$、$\mathbb{N}[x]$、所有程序、所有证明。别用”行优先”扫描，第一行永远扫不完。
- Cantor 定理：$\vert A\vert <\vert \mathcal{P}(A)\vert $ 对一切集合成立。核心是 $D=\{a\in A:a\notin f(a)\}$：构造一个”处处与自己的候选人唱反调”的对象，使它必然不在任何满射的像中。取”$\notin$”而非”$\in$”是本质的。
- Cantor–Bernstein 定理是最实用的夹逼工具：要证 $\vert A\vert =\vert B\vert $，只需两个方向的单射。用它可以把”造双射”降级成”造单射”，从而允许”良定义 + 单射”的两步验证（定理 12.4、12.6 全靠这一招）。
- 两个层次的无穷，与桥向 L13 的结论：$\vert \mathbb{N}\vert =\vert \mathbb{Z}\vert =\vert \mathbb{Q}\vert =\vert \mathbb{N}\times\mathbb{N}\vert =\vert \{0,1\}^*\vert =\vert \mathbb{N}[x]\vert =\aleph_0$（可数）；$\vert \mathbb{R}\vert =\vert [0,1]\vert =\vert \mathcal{P}(\mathbb{N})\vert =\vert \{0,1\}^\infty\vert =2^{\aleph_0}=\mathfrak{c}$（不可数），且 $\aleph_0<\mathfrak{c}$。程序可数、函数不可数 ⟹ 存在不可计算的函数。
常见误区与注意事项
- 用包含关系代替双射来比较无穷集的大小。”$\mathbb{Z}$ 比 $\mathbb{N}$ 多了无穷多个负数，所以更大”——错。显式双射 $f(x)=x/2$（偶）、$f(x)=-(x+1)/2$（奇）已经证明二者等势。判断无穷集大小只看能否配对，不看谁包含谁。
- 把”可数”理解成”能列完”或”很小”。$\mathbb{Q}$ 在数轴上稠密 (dense)（任意两个有理数间还有有理数），看起来”到处都是”，但可数；$\mathbb{N}\times\mathbb{N}$ 看起来是二维的、比 $\mathbb{N}$”大一个维度”，也可数。“看起来稀疏/稠密/高维”都不是判据，”列不完”也不是不可数的证据。
- 把”每个元素有限”误当成”整体有限”或”整体可数”。$\{0,1\}^*$ 中每个串长度有限，且整体可数（这两件事一致但需要证明）；$\{0,1\}^\infty$ 中每个串长度无限，整体不可数。“有限长”这个词修饰的是元素，不是集合。
- 对角线论证忘了确认新构造的对象属于原集合。在 $\mathbb{R}$ 上改对角位得到的新数一定是实数（所以论证成立）；在 $\mathbb{Q}$ 上改对角位得到的新数未必是有理数（所以论证失败）。每次用对角线，都必须检查”我造出来的东西还在集合里吗？”
- 忘了处理小数的双重表示。$0.4999\ldots=0.5$、$0.999\ldots=1$。若不做规范约定（统一用”不以 9 结尾”的表示，或把新数限制在 $\{1,\dots,8\}$ 内），”$s$ 与 $f(n)$ 第 $n+1$ 位不同 $\Rightarrow$ $s\ne f(n)$”这一步就会站不住。
- 造单射时忘了验证”良定义”与”可唯一解码”。定理 12.4 中 $f(q)=\sigma(\text{$q$ 的最简表示})$，必须说明最简表示唯一（否则 $f(q)$ 会因表示选择而不同）；定理 12.6 的编码必须能唯一解码——去掉分隔符 $2$ 就会让 $f$ 失去单射性（$(5,2,7)$、$(5,27)$、$(52,7)$ 编码撞车）。此外还要留意定理 12.3 的条件是”可数多个”：不可数多个可数集的并可以不可数（$\bigcup_{r\in[0,1]}\{r\}=[0,1]$），用之前先确认下标集合 $I$ 可数。
思考题（带答案）
Q1. 定义 $f:\mathbb{N}\to\mathbb{Z}$ 为 $f(x)=\frac{x}{2}$（$x$ 偶数）、$f(x)=-\frac{x+1}{2}$（$x$ 奇数）。请（a）写出 $f(0),\dots,f(10)$；（b）求 $f(124)$；（c）求 $f^{-1}(-7)$、$f^{-1}(50)$、$f^{-1}(-50)$。
答案
（a）$x$ 从 0 到 10：偶数 $0,2,4,6,8,10$ 分别映到 $0,1,2,3,4,5$；奇数 $1,3,5,7,9$ 分别映到 $-\\frac{2}{2}=-1,-\\frac42=-2,-\\frac62=-3,-\\frac82=-4,-\\frac{10}{2}=-5$。所以序列是 $$0,\ -1,\ 1,\ -2,\ 2,\ -3,\ 3,\ -4,\ 4,\ -5,\ 5.$$ （和"从 0 出发左右横跳"的直观一致。） （b）$124$ 是偶数，$f(124)=124/2=62$。 （c）逆函数为 $f^{-1}(y)=2y$（$y\\ge 0$）、$f^{-1}(y)=-2y-1$（$y<0$）。 - $f^{-1}(-7)$：$y=-7<0$，$f^{-1}(-7)=-2\\cdot(-7)-1=14-1=13$。核对：$13$ 是奇数，$f(13)=-\\frac{14}{2}=-7$ ✓ - $f^{-1}(50)$：$y=50\\ge 0$，$f^{-1}(50)=100$。核对：$f(100)=50$ ✓ - $f^{-1}(-50)$：$y=-50<0$，$f^{-1}(-50)=100-1=99$。核对：$99$ 是奇数，$f(99)=-\\frac{100}{2}=-50$ ✓ **脚本验算输出**：`f(0..10)=0,-1,1,-2,2,-3,3,-4,4,-5,5`；`f(124)=62`；`preimage of -7 = 13, of 50 = 100, of -50 = 99`；在 $[-200,200]$ 上逐点验证 $f$ 为双射通过。Q2. 计算 Cantor 配对函数 $\pi(i,j)=\frac{(i+j)(i+j+1)}{2}+j$：（a）求 $\pi(3,4)$、$\pi(4,3)$、$\pi(0,5)$、$\pi(5,0)$；（b）若 $\pi(i,j)=20$，求 $(i,j)$；（c）若 $\pi(i,j)=100$，求 $(i,j)$；（d）解释为什么 $\pi(3,4)\ne\pi(4,3)$ 对”$\mathbb{N}\times\mathbb{N}$ 可数”的证明是必要的。
答案
（a）逐个代入： - $\\pi(3,4)$：$s=3+4=7$，$\\frac{7\\cdot8}{2}+4=28+4=\\mathbf{32}$。 - $\\pi(4,3)$：$s=7$，$\\frac{7\\cdot8}{2}+3=28+3=\\mathbf{31}$。 - $\\pi(0,5)$：$s=5$，$\\frac{5\\cdot6}{2}+5=15+5=\\mathbf{20}$。 - $\\pi(5,0)$：$s=5$，$\\frac{5\\cdot6}{2}+0=\\mathbf{15}$。 （b）求 $s$ 使 $\\frac{s(s+1)}{2}\\le 20<\\frac{(s+1)(s+2)}{2}$：$\\frac{5\\cdot6}{2}=15\\le 20<21=\\frac{6\\cdot7}{2}$，所以 $s=5$。则 $j=20-15=5$，$i=s-j=0$。故 $(i,j)=\\mathbf{(0,5)}$。 （c）$\\frac{13\\cdot14}{2}=91\\le 100<105=\\frac{14\\cdot15}{2}$，所以 $s=13$。$j=100-91=9$，$i=13-9=4$。故 $(i,j)=\\mathbf{(4,9)}$。 （d）$\\pi$ 要成为**双射**（而不只是满射），它必须把不同的格子送到不同的编号；若 $\\pi(3,4)=\\pi(4,3)$，则 $(3,4)$ 与 $(4,3)$ 两个格子共用一个编号，编号就不再是"每个格子恰好一个门牌号"，于是不能构成 $\\mathbb{N}\\times\\mathbb{N}$ 与 $\\mathbb{N}$ 的双射，只能得到一个满射 $\\mathbb{N}\\to\\mathbb{N}\\times\\mathbb{N}$（方向还反了）。更实质地说：**单射性保证了"去重"不必要**，也保证了枚举不重不漏；若只满射不单射，我们仍能证明可数（因为满射 $\\mathbb{N}\\to S$ 已足以说明 $\\vert S\\vert \\le\\vert \\mathbb{N}\\vert $，可用 Cantor–Bernstein），但证明会多绕一步。而 $\\pi$ 的设计（同一 $s$ 内按 $j$ 递增）恰好让 $\\pi(3,4)=32$、$\\pi(4,3)=31$ 自动错开。 **脚本验算输出**：`pair(3,4)=32, pair(4,3)=31, pair(0,5)=20, pair(5,0)=15`；`unpair(20)=[0,5], unpair(15)=[5,0], unpair(100)=[4,9]`；在 $0\\le i,j\\le 19$ 的 400 个格子上无碰撞，且 $z=0..399$ 上逆函数逐点校验正确。Q3. 判断并说明理由（$[0,1]$ 的循环小数/规范表示请沿用正文约定）：
（a）”$\mathbb{R}$ 不可数，所以 $\mathbb{R}\setminus\mathbb{Q}$（无理数）不可数。” （b）”$\mathbb{Q}$ 可数，所以 $\mathbb{Q}\cap[0,1]$ 也可数。” （c）”$\{0,1\}^\infty$ 不可数，所以 $\{0,1\}^*$（有限串）也不可数。” （d）”因为 $\mathbb{Q}$ 稠密，所以 $\mathbb{Q}$ 不可数。”