Contents 4 sections
  1. 怎样比较两个无穷集合
  2. 对角线论证
  3. 同一个想法,换一种说法
  4. 留下的问题

怎样比较两个无穷集合

两个有限集合谁大谁小,数一数就知道。无穷集合数不完,Cantor 换了一个不需要「数」的办法:一一对应。

定义 1(等势)

若存在从集合 AA 到集合 BB 的双射(一一对应),就称 AA 与 BB 等势,记作 ∣A∣=∣B∣|A| = |B|。若存在从 AA 到 BB 的单射,就记 ∣A∣≤∣B∣|A| \le |B|。

按这个定义,许多结论初看很奇怪:

  • 正整数和偶数一样多:n↦2nn \mapsto 2n 是双射,尽管偶数只是正整数的「一半」。
  • 正整数和全体整数一样多:按 0,1,−1,2,−2,…0, 1, -1, 2, -2, \dots 的顺序排成一列即可。
  • 正整数和有理数一样多:把正有理数 p/qp/q 排进一张无穷表格,第 pp 行第 qq 列,然后沿着斜线逐条走,跳过已经出现过的值(比如 2/42/4),每个正有理数迟早都会被走到。

能和正整数一一对应的集合叫作可数集,也就是能排成一个无穷长队列 a1,a2,a3,…a_1, a_2, a_3, \dots 的集合。看起来,似乎所有无穷集合都是可数的。

对角线论证

定理 1(Cantor,1891)

区间 (0,1)(0,1) 中的实数不可数。

证明.

用反证法。假设 (0,1)(0,1) 中的实数可以排成一列 x1,x2,x3,…x_1, x_2, x_3, \dots,每个实数都出现在某个位置上。把它们写成十进制小数:

x1=0. a11 a12 a13 a14⋯x2=0. a21 a22 a23 a24⋯x3=0. a31 a32 a33 a34⋯    ⋮\begin{aligned} x_1 &= 0.\,a_{11}\,a_{12}\,a_{13}\,a_{14}\cdots \\ x_2 &= 0.\,a_{21}\,a_{22}\,a_{23}\,a_{24}\cdots \\ x_3 &= 0.\,a_{31}\,a_{32}\,a_{33}\,a_{34}\cdots \\ &\;\;\vdots \end{aligned}

现在沿对角线 a11,a22,a33,…a_{11}, a_{22}, a_{33}, \dots 构造一个新的数 y=0. d1d2d3⋯y = 0.\,d_1 d_2 d_3 \cdots,规则是

dn={5若 ann≠5,6若 ann=5.d_n = \begin{cases} 5 & \text{若 } a_{nn} \ne 5, \\ 6 & \text{若 } a_{nn} = 5. \end{cases}

yy 在 (0,1)(0,1) 中。但对每个 nn,yy 的第 nn 位与 xnx_n 的第 nn 位不同,所以 y≠xny \ne x_n。于是 yy 不在这个列表里,与假设矛盾。

∎

证明里有一个容易忽略的细节:有些实数有两种十进制写法,比如 0.5000⋯=0.4999⋯0.5000\cdots = 0.4999\cdots。如果 yy 恰好是这样的数,「第 nn 位不同」就不足以说明 y≠xny \ne x_n。只有以全 0 或全 9 结尾的小数才有两种写法。这里只用数字 5 和 6 构造 yy,它不含 0 和 9,写法唯一,这个问题就不会出现。

同一个想法,换一种说法

对角线论证的核心是:列表里第 nn 个对象,在第 nn 个位置上被故意避开。把「十进制小数」换成任意集合,就得到一个更一般、也更简洁的定理。

定理 2(Cantor 定理)

对任意集合 AA,不存在从 AA 到其幂集 P(A)\mathcal{P}(A)(AA 的全部子集组成的集合)的满射。因此 ∣A∣<∣P(A)∣|A| < |\mathcal{P}(A)|。

证明.

设 f:A→P(A)f : A \to \mathcal{P}(A) 是任意映射。考虑子集

D={ x∈A:x∉f(x) }.D = \{\, x \in A : x \notin f(x) \,\}.

假设 D=f(a)D = f(a) 对某个 a∈Aa \in A 成立,问:aa 在不在 DD 里?

  • 若 a∈Da \in D,按 DD 的定义 a∉f(a)=Da \notin f(a) = D,矛盾;
  • 若 a∉Da \notin D,即 a∉f(a)a \notin f(a),按定义又应有 a∈Da \in D,矛盾。

所以 DD 不在 ff 的像中,ff 不是满射。另一方面 x↦{x}x \mapsto \{x\} 是单射,故 ∣A∣≤∣P(A)∣|A| \le |\mathcal{P}(A)| 且两者不等势。

∎

集合 DD 就是那条「对角线」:xx 是否属于 DD,恰好和 xx 是否属于 f(x)f(x) 相反。

由 定理 2 立即得到一串越来越大的无穷:

∣N∣<∣P(N)∣<∣P(P(N))∣<⋯|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots

无穷没有最大的。 而且 ∣P(N)∣|\mathcal{P}(\mathbb{N})| 恰好等于 ∣R∣|\mathbb{R}|,这一点要在本系列下一篇里用 Schröder–Bernstein 定理来证明。

留下的问题

在 ∣N∣|\mathbb{N}| 和 ∣R∣|\mathbb{R}| 之间,还有没有别的大小?Cantor 猜测没有,这就是连续统假设。它的结局出人意料:Gödel 在 1940 年证明,从通常的集合论公理(ZFC)出发无法否定它;Cohen 在 1963 年证明,也无法证明它。在 ZFC 里,连续统假设既不能证明,也不能否定。