6.1.2-6.3 Cantor 定理、连续统与选择公理

上一篇笔记用双射和单射比较集合大小。这一篇从本章第一个真正的大集合定理 开始：Cantor 定理。它说明任何集合都严格小于它的幂集。

这个结果立即给出实数不可数的证明。同一段讲义随后引入两个基础性命题： 连续统假设与选择公理。本课程不证明它们背后深层的元数学结果，但会清楚说 明它们在理论中扮演什么角色。

幂集与 Cantor 定理

记号 $2^X$ 带有提示性：若 $X$ 有 n 个元素，则幂集有 $2^n$ 个子集。 Cantor 定理说的不只是有限情况，而是对所有集合都成立。

证明分两部分。

首先，有单射

$$X\to 2^X,\qquad x\mapsto \{x\}.$$

所以 $|X|\le |2^X|$。

其次，不存在由 $X$ 到 $2^X$ 的双射。反设 $f:X\to 2^X$ 是双射。定义对角 集合

$$T=\{x\in X\mid x\notin f(x)\}.$$

因为 $T$ 是 $X$ 的子集，所以 $T\in 2^X$。若 f 是满射，便存在 $y\in X$ 使

$$f(y)=T.$$

现在考虑 y 是否属于 $T$。

• 若 $y\in T$，则按 $T$ 的定义有 $y\notin f(y)=T$，矛盾。
• 若 $y\notin T$，则按 $T$ 的定义有 $y\in f(y)=T$，同样矛盾。

两种情况都不可能。因此不存在双射 $X\to 2^X$，所以 $|X|<|2^X|$。

对角线实验

下面的互动组件是用来辅助证明，而不是替代证明。可用它观察 $T$ 为什么必 然会与每一个尝试列出的子集不同。

图示。对角集合通过反转对角线上的隶属判断而成，所以不可能等于候选列表中任何一行。

实数不可数

讲义的证明使用 Cantor 定理，以及一个由 $2^N$ 到 $R$ 的单射。

由 Cantor 定理，

$$|N|<|2^N|.$$

所以只需证明

$$|2^N|\le |R|.$$

给定子集 $S\subseteq N$，用一个由 0 和 1 组成的序列来编码它：

$$a_n= \begin{cases} 1, & n\in S,\\ 0, & n\notin S. \end{cases}$$

然后定义

$$\phi(S)=\sum_{n=0}^{\infty}\frac{a_n}{3^{n+1}}\in [0,1].$$

这把 $N$ 的每个子集送到一个实数。

为什么用底数 3 而不是 2？讲义使用底数 3，是为了避免两个不同的 零一序列被后面的尾项抵消。

若 $S\ne S'$，令 k 为两个对应序列第一次不同的位置。在第 k 位，两个 和式相差

$$\frac1{3^{k+1}}.$$

后面所有项加起来可能造成的抵消量比这个主要差距还小。因此两个实数不可能 相等。故 $\phi$ 是单射，从而 $|2^N|\le |R|$。

合并得到

$$|N|<|2^N|\le |R|,$$

所以 $R$ 不可数。

连续统假设

在知道 $R$ 比 $N$ 大之后，这是一个自然猜想：也许可数无限基数与实数基数 之间没有中间大小。

讲义强调，这个猜想的地位非常特殊。连续统假设独立于通常的集合论公理 ZFC。 Godel 在 1940 年证明它与 ZFC 相容；Cohen 在 1963 年使用 forcing 证明它 的否定也与 ZFC 相容。因此它不能从标准公理中被证明，也不能从标准公理中 被否证。

对本课程而言，重点不是证明这些元数学结果，而是知道：基数问题很快会进入 “公理是否足够”的层面。

选择函数与选择公理

在陈述选择公理之前，讲义先定义一个由集合组成的集合的并集：

$$\bigcup S=\{x\mid \exists X\in S\text{ such that }x\in X\}.$$

选择函数会从族 $S$ 中每一个集合各选出一个元素。

如果 $S$ 含有空集，就不可能有选择函数，因为空集中没有元素可选。因此定 义必须假设 $S$ 的成员都是非空集合。

这是公理，不是定理。讲义指出，如同连续统假设一样，它的真伪不能由其他集 合论公理决定。

满射与基数不等式

要证明它，需要构造单射 $g:Y\to X$。

对每个 $y\in Y$，纤维

$$f^{-1}(y)\subseteq X$$

非空，因为 f 是满射。令

$$S=\{f^{-1}(y)\mid y\in Y\}.$$

这是 $X$ 的非空子集所成的集合。由选择公理，可从每个纤维选一个元素。定 义

$$g(y)=\text{在 }f^{-1}(y)\text{ 中被选出的元素}.$$

则 $g:Y\to X$ 是单射。若 $g(y)=g(y')$，同一个 $X$ 中元素同时落在两个纤 维里，所以

$$f(g(y))=y \qquad\text{且}\qquad f(g(y'))=y'.$$

由 $g(y)=g(y')$ 得 $y=y'$。

这解释了前面的提醒：由满射推出反方向基数不等式，在需要同时从无限多个纤 维中选代表时，会用到选择公理。

可数个可数集合的并仍可数

讲义用满射组织证明。由于每个 $A_n$ 可数，可选满射

$$f_n:N\to A_n.$$

若 $A_n$ 有限，可把最后一个元素不断重复，仍得到由 $N$ 到 $A_n$ 的满射。 选择公理用来同时选出整族映射 ${f_n}$。

定义

$$F:N\times N\to A,\qquad F(n,m)=f_n(m).$$

这是满射：并集中任何元素都属于某个 $A_n$，因此会被相应的 $f_n$ 打到。

最后，$N\times N$ 可数，证明方式与 $Q$ 可数的对角线方法类似。因此存在 满射

$$N\to N\times N.$$

合成后得到满射 $N\to A$，所以 $A$ 可数。

链、极大元素与 Zorn 引理

指定页的最后一部分陈述 Zorn 引理；它与选择公理等价。

极大元素不一定大于所有其他元素。这不同于最大元素；最大元素需要满足 $m\ge x$ 对所有 $x\in X$ 成立。

本课程把它作为基础工具陈述。完整证明属于更进阶课程；但现在应该先准确读 懂其中的词：偏序、链、链的上界，以及极大元素。

常见错误与细节

快速检查

练习

相关笔记

可先读 6.1 基数、可数性与基数不等式 和 2.2 函数与关系。 下一个课程段落开始讨论区间；这篇笔记则完成 Chapter 6.1-6.3 所需的大集 合基础。