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

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

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

幂集与 Cantor 定理

定义

幂集记号

对集合 $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$ 开始。下面的定理更强：即使集合不是有限 的，仍然可以严格比较集合与其幂集的基数。

定理

Cantor 定理

设 $X$ 为集合。则

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

证明分两部分。

首先，有单射

$$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|\lt |2^X|$。

这里的矛盾关键在于满射性。单点映射已经给出了 $|X|\le |2^X|$ 所需的单射；我们不需要证明每个子集都是单点集。为了排除 相等，假设有双射，于是每个 $X$ 的子集（包括 $T$）都必须等于某个 $f(y)$。关于 $y$ 是否属于 $T$ 的两种情况穷尽了所有可能。空集的情况也 没有例外：当 $X=\varnothing$ 时，$2^\varnothing$ 有一个元素，而从空集 出发的函数不可能满射到它，因此假设的双射立即失败。

证明透视

Cantor 证明必须完成的两件事

证明有两个彼此独立的任务。单点映射证明 $|X|\le |2^X|$。对角集合则在 坐标 $x$ 处与 $f(x)$ 取相反的成员关系，从而排除相等。在矛盾段落中， $f(y)=T$ 来自满射性；最后的分类只使用 $T$ 的成员定义。

把对角线读成成员关系表

单点映射证明非严格不等式。例如 $X=\{a,b\}$ 时，它从四个子集 $\varnothing,\{a\},\{b\},\{a,b\}$ 中选中两个。对角构造进一步说明， 任何候选映射都不能覆盖全部子集，即使集合无限也一样。

下面用 $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$ 安排数字次序。表格说明构造机制；上面的证明则以完整量词 处理所有集合，包括空集。

探索对角差异

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

上一行下一行k = 0

改变每一行的对角项

f(k)	0	1	2	3	4	5
f(0)	1	0	1	0	1	0
f(1)	1	1	0	1	0	1
f(2)	0	0	1	1	0	0
f(3)	1	0	0	0	1	0
f(4)	0	1	0	0	1	1
f(5)	0	0	0	0	0	0
T	0	0	0	1	0	1

$0\in f(0)$, $0\notin T$; $T\ne f(0)$.

$1$ 表示属于，$0$ 表示不属于。定义 $T=\{n\in\mathbb N:n\notin f(n)\}$。对任意第 $k$ 行，其对角位与 $T$ 在第 $k$ 位恰好相反，所以 $T\ne f(k)$。六列只是有限示意；证明适用于每个自然数，并没有最后一行。

实数不可数

定理

实数不可数

实数集合 $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$ 的每个元素）送到一个实数。

例题

把 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 .$$

证明不需要把它转写成小数展开；只需要知道这个无穷级数确定了一个实数。

为什么用底数 $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$ 的子集给出不同实数。

例题

底数 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 只是询问它们之间更精细的比较，通常公理没 有决定这个问题。因此写证明时，要标出映射方向以及选择或极大性原理的使用。

选择函数与选择公理

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

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

定义

选择函数

设 $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 证明。这里记录这一相对相容性陈述而不在本篇证明它；本篇要掌握 的是准确的选择函数陈述，以及后续构造在哪一步调用了它。

例题

选择函数做什么

设

$$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$。 这是有限族，所以可以一个接一个地写出选择。对没有每个集合的“第一个” 元素可用的无限族，选择公理断言仍存在满足同一成员条件的函数。

满射与基数不等式

定理

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

假设选择公理，若 $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'$，所以这些代 表互不相同，恰好构成单射，而不是原满射的显式逆函数。

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

定理

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

假设选择公理，若 ${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$ 属于并集中的至少一个成员且 $N$ 良序，最小指标存在。映射 $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 引理通过极大元素的存在性表达选择公理。

定义

链

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

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

定义

极大元素

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

$$x\gt m.$$

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

例题

极大比最大弱

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

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

定理

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 集、稠密性与良序， 比较基数与长度、稠密性和次序。