6.2 Cantor 定理、连续统与选择公理

整数和有理数都能由自然数逐一列出，但这并未回答：每个无限集合是否都能如此列举？幂集提供了反例的构造方法。对任何候选子集列表，都可以根据各项的成员关系，构造出一个没有列入其中的子集。

幂集与 Cantor 定理

定义 6.2.1

（幂集记号）

对集合 $X$，记号 $2^X$ 表示 $X$ 的所有子集所成的集合，即 $X$ 的幂集。

因此

$$T\in 2^X$$

正是说 $T\subseteq X$。

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

对空集，这个记号已经说明了一个重要的起点：

$$2^\varnothing=\{\varnothing\}.$$

空集只有一个子集，就是空集本身。因此有限集合的计数模式 $|2^X|=2^{|X|}$ 从 $2^0=1$ 开始。下面的定理更强：即使集合不是有限的，仍然可以严格比较集合与其幂集的基数。

构造列表遗漏的子集

设 $f:X\to2^X$ 为 $X$ 的每个元素指定一个子集。要构造 $f$ 遗漏的子集，只需让它对每个 $x$ 都在某个元素上与 $f(x)$ 不同。指标 $x$ 本身就能起到这个作用：当且仅当 $f(x)$ 不含 $x$ 时，把 $x$ 放入新子集。这样，列表的每一项都有一个确定的成员判断与新子集不同。

下面用 $X=\{a,b,c\}$ 作有限示范。每一行记录 $f$ 的一个候选值； $1$ 表示列标题中的元素属于该子集，$0$ 表示不属于。前三行的粗体数字就是对角线上的成员判断。

沿对角线读到 $1,0,1$，逐个反转就得到 $0,1,0$，所以 $T=\{b\}$。它与 $f(a)$ 在 $a$ 处不同，与 $f(b)$ 在 $b$ 处不同，与 $f(c)$ 在 $c$ 处不同。即使其他位置一致，也无法消除这些差异。

对任意集合，同一规则就是 $x\in T$ 当且仅当 $x\notin f(x)$。这条规则为 $X$ 的每个元素确定是否纳入 $T$，无须给 $X$ 安排数字次序，也不涉及逐项扫描完一个无限列表。

Cantor 定理

定理 6.2.2

（Cantor 定理）

设 $X$ 为集合。则

$$|X|\lt |2^X|.$$

证明分两部分。

首先，有单射

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

所以 $|X|\le |2^X|$。例如 $X=\{a,b\}$ 时，这个映射从四个子集 $\varnothing,\{a\},\{b\},\{a,b\}$ 中选中两个；它不必覆盖所有子集。

其次，不存在由 $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|\lt |2^X|$。

当 $X=\varnothing$ 时，幂集有一个元素，从空集出发的函数不可能命中它。因此结论也涵盖空集的情形。

证明透视

满射性用在哪里

等式 $f(y)=T$ 是满射性发挥作用的关键。对角论证没有使用单射性，而是排除了所有由 $X$ 到 $2^X$ 的满射。单点映射则提供严格基数不等式所需的另一部分。

探索对角差异

利用下表追踪每一行在哪个成员判断上不可能等于对角集合。注意区分行的指标与列中的元素。

实数不可数

定理 6.2.3

（实数不可数）

实数集合 $R$ 不可数。特别地，

$$|N|\lt |R|.$$

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

由 Cantor 定理，

$$|N|\lt |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$ 的每个子集（也就是 $2^N$ 的每个元素）送到一个实数。

例题 6.2.4

（把 N 的子集编码成实数）

若

$$S=\{0,2,5,\ldots\},$$

则序列开头为

$$a_0=1,\quad a_1=0,\quad a_2=1,\quad a_3=0,\quad a_4=0,\quad a_5=1.$$

对应的实数开头可写成

$$\phi(S)=\frac13+\frac1{3^3}+\frac1{3^6}+\cdots .$$

部分和非递减且以 $1/2$ 为上界，因此完备性保证实数极限存在。这与 4.6 小数展开与无理数 中由有限近似确定实数的原理相同，无须再转换成十进制。

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

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

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

更精确地，后面尾项的总和至多为

$$\sum_{n=k+1}^{\infty}\frac1{3^{n+1}} =\frac1{2\cdot 3^{k+1}},$$

严格小于第一个不同项的差距。因此两个实数不可能相等。故 $\phi$ 是单射，从而 $|2^N|\le |R|$。

合并得到

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

所以 $R$ 不可数。

常见错误

（证明只需要单射到 R）

要证明 $|2^N|\le |R|$，不需要 $\phi$ 打到每个实数。只需要不同的 $N$ 的子集给出不同实数。

例题 6.2.5

（底数 3 分离的有限版）

取两个在位置 $k=2$ 首次不同的零一序列。该位置的贡献大小为 $\frac1{27}$。即使后面每一位都朝着抵消方向取值，尾项总和也是

$$\frac1{3^4}+\frac1{3^5}+\cdots=\frac1{54},$$

只有首个差距的一半，所以首次不同不能被抵消。任意首次不同的位置都可用同一个几何级数估计。

连续统假设

假设 — 连续统假设.

连续统假设说：不存在集合 $S$ 使

$$|N|\lt |S|\lt |R|.$$

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

这个猜想的地位非常特殊。连续统假设独立于通常的集合论公理 ZFC。更准确地说，如果 ZFC 是相容的，那么 CH 和它的否定都不能由 ZFC 证明： Godel 的结果给出 ZFC+CH 的相对相容性，Cohen 的 forcing 结果给出 $ZFC+\neg\mathrm{CH}$ 的相对相容性。这些是元数学的相容性结果，不是本课程中对 CH 或其否定的证明。

独立性不表示这句话没有意义，也不表示所有基数命题都无法判定。Cantor 定理和实数不可数性仍是 ZFC 定理；CH 只是询问它们之间更精细的比较，通常公理没有决定这个问题。因此写证明时，要标出映射方向以及选择或极大性原理的使用。

选择函数与选择公理

满射 $f:X\to Y$ 能命中 $Y$ 的每个元素，却未必指定应采用哪一个原像。要构造反方向的单射，我们希望为每个 $y$ 指定纤维 $f^{-1}(y)$ 中的一个元素。每个纤维都非空；额外的问题是，这些各自成立的存在性命题，能否给出一个同时完成所有选择的函数。

对集合族 $S$，所有可能被选出的元素都在它的并集内：

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

定义 6.2.6

（选择函数）

设 $S$ 为一个集合，其元素都是非空集合。$S$ 的选择函数是函数

$$f:S\to \bigcup S$$

使得对每个 $X\in S$ 都有

$$f(X)\in X.$$

选择函数会从族 $S$ 中每一个集合各选出一个元素。对带指标的族 $(A_i)_{i\in I}$，同一件事写成

$$c:I\to\bigcup_{i\in I}A_i,\qquad c(i)\in A_i.$$

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

对于有限族，可以逐次从每个非空集合中选出元素，这只使用 ZF 中普通的存在性和有限步构造。选择公理处理任意的非空集合族，尤其是没有给出一条明确选择规则而又包含无限多个成员的情况。空族本身有唯一的空选择函数；真正的障碍是族中含有空集，因为空集中没有可选元素。

公理 — 选择公理.

设 $S$ 为一个集合，其元素都是非空集合。则 $S$ 有选择函数。

这是公理，不是本课程从其他公理推出的定理。应区分有限次选择与对任意带指标族同时选择：前者可以在 ZF 中逐步完成，后者正是选择公理所保证的范围。

在元数学层面，如果 ZF 是相容的，那么 AC 和它的否定都不能由 ZF 证明。这里记录这一相对相容性陈述而不在本篇证明它；本篇要掌握的是准确的选择函数陈述，以及后续构造在哪一步调用了它。

例题 6.2.7

（选择函数做什么）

设

$$S=\{\{1,2\},\{3,4,5\},\{6\}\}.$$

一个选择函数可以选

$$f(\{1,2\})=1,\qquad f(\{3,4,5\})=4,\qquad f(\{6\})=6.$$

它不一定要选最小元素；只需要从每个非空集合中选一个元素。

指标记号还可以把同一例子写得更清楚。令 $I=\{1,2,3\}$，$A_1=\{1,2\}$，$A_2=\{3,4,5\}$，以及 $A_3=\{6\}$。上面的选择定义了定义域为 $I$ 的函数：

$$c(1)=1,\qquad c(2)=4,\qquad c(3)=6.$$

逐个指标检查即可：$c(1)\in A_1$、$c(2)\in A_2$、$c(3)\in A_3$。这是有限族，所以可以一个接一个地写出选择。对没有每个集合的“第一个” 元素可用的无限族，选择公理断言仍存在满足同一成员条件的函数。

满射与基数不等式

定理 6.2.8

（在选择公理下，满射给出反方向的基数不等式）

假设选择公理，若 $f:X\to Y$ 是满射，则

$$|X|\ge |Y|.$$

要证明它，需要构造单射 $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'$。

原来的满射仍可能多对一；选择函数只为每个目标取一个原像。不同纤维互不相交，因为共同元素经 $f$ 映射会给出 $y=y'$，所以不同目标的代表互不相同。

等式 $f\circ g=id_Y$ 说明 $g$ 是 $f$ 的右逆。它未必是双侧逆函数，因为 $g\circ f=id_X$ 并不一定成立。若 $f$ 本身是双射，每个纤维就只有一个元素，此时 $g$ 正是通常的逆函数。

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

定理 6.2.9

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

假设选择公理，若 ${A_n}_{n\in N}$ 是一个可数族，而每个 $A_n$ 都可数，则

$$A=\bigcup_{n\in N} A_n$$

可数。

若 $A=\varnothing$，空函数立即给出到 $N$ 的单射。现在假设 $A$ 非空。由于每个 $A_n$ 可数，对每个指标 $n$ 都存在单射

$$i_n:A_n\to N.$$

当 $A_n=\varnothing$ 时，唯一的空函数就是这样的单射。这里使用选择公理同时选出整族单射 ${i_n}$，包括这些空成员的情况。这里需要选择的是整族见证映射；这并不是说任意多个不可数集合的可数并会变成可数。

定义

$$h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)),$$

其中

$$n(x)=\min\{n\in N\mid x\in A_n\}.$$

因为 $x$ 属于并集，指标集非空；自然数的良序性保证最小指标存在。这一归纳法推论的证明见 6.3 区间、Cantor 集、稠密性与良序。映射 $h$ 是单射：若 $h(x)=h(x')$，第一坐标给出 $n(x)=n(x')=n$，第二坐标再给出 $i_n(x)=i_n(x')$，而 $i_n$ 的单射性推出 $x=x'$。

最后，$N\times N$ 的对角枚举给出单射 $N\times N\to N$，与 $h$ 合成便得到单射 $A\to N$。先列 $(0,0)$，再列坐标和为 $1$、$2$ 等的点，每个点都在有限阶段出现；空成员不贡献并集元素。指标集与每个成员都必须可数，否则不可数的指标集单点族或一个不可数成员都可能使并集不可数。

常见错误

（可数并不等于任意并）

这个定理处理的是可数族 ${A_n}$。它不是说任意多个可数集合的并都必定可数。

链、极大元素与 Zorn 引理

Zorn 引理通过极大元素的存在性表达选择公理。

定义 6.2.10

（链）

设 $X$ 为偏序集合。子集 $S\subseteq X$ 称为链，如果它是全序子集：对任意 $a,b\in S$，都有

$$a\le b \qquad\text{或}\qquad b\le a.$$

定义 6.2.11

（极大元素）

元素 $m\in X$ 称为极大元素，如果不存在 $x\in X$ 使得

$$x\gt m.$$

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

例题 6.2.12

（极大比最大弱）

在偏序集合中，两个元素可能不可比较。如果二者互不在对方之上，它们都可能在某个小集合中是极大元素，但没有任何一个是最大元素。

因此，“极大”的意思是“不能再往上延伸”，不是“支配所有元素”。

定理 6.2.13

（Zorn 引理）

选择公理等价于以下命题：

若 $X$ 是非空偏序集合，且 $X$ 中每一条链都有一个属于 $X$ 的上界，则 $X$ 有极大元素。

本课程把它作为基础工具陈述，完整证明属于更进阶课程。量词不能倒置：它不是说每个子集都有最大元素，也不要求一个元素给整个偏序集作上界；对每条链 $C\subseteq X$，存在可能依赖于 $C$ 的 $u\in X$，使每个 $c\in C$ 都有 $c\le u$，从而至少有一个元素不能再严格向上延伸。

一个有限例子是按包含关系排列 $E=\{1,2,3\}$ 的真子集。链 $\varnothing\subset\{1\}\subset\{1,2\}$ 在这个偏序中的一个上界是 $\{1,2\}$，而 $\{1,2\}$ 是极大元素，因为再加入剩余元素就不再是真子集。它却不是最大元素：$\{1,3\}$ 与它不可比较。这个小例子把一般引理所用的两个术语区分开来。

常见错误与细节

常见错误

（不要把 Cantor 定理只当作有限算术）

有限集合中 $2^n\gt n$ 很熟悉；Cantor 定理更强，因为它对所有集合，包括无限集合，都成立。

常见错误

（不要混淆极大与最大）

最大元素要大于或等于每个元素。极大元素只要求没有更大的元素在它上方。在偏序中，二者不同。

常见错误

（不要隐藏选择公理的角色）

从无限多个非空集合中各选一个元素，正是选择公理要保证的步骤。

快速检查

快速检查

（为什么从 $2^N$ 到 $R$ 的单射使用底数 3？）

考虑第一个不同的位置，以及后面尾项可能造成的影响。

解答 · 答案

底数 $3$ 令第一个不同项的大小大于后面所有尾项可能造成的总抵消量。因此两个不同的零一序列不会定义出同一个实数。

快速检查

（选择函数选的是什么？）

请同时提到集合族和被选元素。

解答 · 答案

对集合族 $S$ 中每个非空集合 $X$，选择函数选出一个元素 $f(X)\in X$。

快速检查

（为什么 Cantor 矛盾需要满射性？）

指出产生 $f(y)=T$ 的那一步。

解答 · 答案

对角集合 $T$ 是 $X$ 的子集，因此是 $2^X$ 的元素。满射性保证 $2^X$ 的每个元素都是某个 $f(y)$，所以存在 $y\in X$ 使 $f(y)=T$。若没有满射性，$T$ 可能在 $f$ 的像之外，矛盾就无法开始。

练习

快速检查

（证明单点映射 $x\mapsto\{x\}$ 是单射。）

假设两个单点集合相等。

解答 · 引导解答

若

$$\{x_1\}=\{x_2\},$$

则左边单点集合的唯一元素等于右边单点集合的唯一元素，所以 $x_1=x_2$。因此 $x\mapsto \{x\}$ 是单射。

快速检查

（解释为什么满射 $f:X\to Y$ 会使每个纤维 $f^{-1}(y)$ 非空。）

使用满射的定义。

解答 · 引导解答

满射表示对每个 $y\in Y$，都存在 $x\in X$ 使 $f(x)=y$。这正是说 $x\in f^{-1}(y)$，所以该纤维非空。

快速检查

（为带指标族 $(A_i)_{i\in I}$ 写出选择函数的完整陈述。）

说明定义域、陪域和成员条件。

解答 · 引导解答

若每个 $A_i$ 都非空，选择函数是

$$c:I\to\bigcup_{i\in I}A_i$$

并且对每个 $i\in I$ 都有 $c(i)\in A_i$。

快速检查

（在 Zorn 引理中，为什么不能只谈最大元素？）

回想这里的顺序是偏序，不一定是全序。

解答 · 引导解答

在偏序中，有些元素可能不可比较。最大元素必须在所有元素之上，未必存在。 Zorn 引理在其假设下保证的是极大元素：没有严格更大的元素在它上方。

相关笔记

可先读 6.1 基数、可数性与基数不等式 和 2.2 函数与关系。继续阅读6.3 区间、Cantor 集、稠密性与良序，比较基数与长度、稠密性和次序。