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

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

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

幂集与 Cantor 定理

定义

幂集记号

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

因此

T\in 2^X

正是说 $T\subseteq X$ 。

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

定理

Cantor 定理

设 $X$ 为集合。则

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

证明

为什么这是对角线论证

对角线实验

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

Cantor 对角集合构造

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

边读边试

建立 Cantor 的对角集合

这个工具把 Cantor 对角论证变成表格，显示为什么任何列表都不能包含所有子集。

n	f(n)	n in f(n)?	n in T?
0	{0, 2, 4}	是	否
1	{0, 1, 3, 5}	是	否
2	{2, 3}	是	否
3	{0, 4}	否	是
4	{1, 4, 5}	是	否
5	{}	否	是

T = {3, 5}

这张有限表只示范规则。正式证明中，T = {n in N : n notin f(n)} 会在第 n 行恰好不同于 f(n)，所以任何列表都不可能包含 N 的所有子集。

实数不可数

定理

实数不可数

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

|N|<|R|.

证明使用 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$ 的每个子集送到一个实数。

例题

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

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

合并得到

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

所以 $R$ 不可数。

常见错误

证明只需要单射到 R

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

连续统假设

定理

连续统假设

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

|N|<|S|<|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$ 的选择函数是函数

f:S\to \bigcup S

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

f(X)\in X.

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

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

定理

选择公理

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

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

例题

选择函数做什么

设

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

一个选择函数可以选

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

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

满射与基数不等式

定理

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

若 $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'$ 。

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

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

定理

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

若 ${A_n}_{n\in N}$ 是一个可数族，而每个 $A_n$ 都可数，则

A=\bigcup_{n\in N} A_n

可数。

下面用满射组织证明。由于每个 $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$ 可数。

常见错误

可数并不等于任意并

这个定理处理的是可数族 ${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>m.

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

例题

极大比最大弱

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

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

定理

Zorn 引理

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

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

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

常见错误与细节

常见错误

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

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

常见错误

不要混淆极大与最大

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

常见错误

不要隐藏选择公理的角色

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

快速检查

在 Cantor 定理中，对角集合 T 是什么？

用 x 是否属于 f(x) 来表述。

解答

答案

快速检查

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

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

解答

答案

快速检查

选择函数选的是什么？

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

解答

答案

练习

快速检查

证明单点映射 x -> {x} 是单射。

假设两个单点集合相等。

解答

引导解答

快速检查

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

使用满射的定义。

解答

引导解答

快速检查

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

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

解答

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

MATH1090：集合论

幂集与 Cantor 定理

幂集记号

Cantor 定理

为什么这是对角线论证

对角线实验

建立 Cantor 的对角集合

实数不可数

实数不可数

把 N 的子集编码成实数

证明只需要单射到 R

连续统假设

连续统假设

选择函数与选择公理

选择函数

选择公理

选择函数做什么

满射与基数不等式

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

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

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

可数并不等于任意并

链、极大元素与 Zorn 引理

链

极大元素

极大比最大弱

Zorn 引理

常见错误与细节

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

不要混淆极大与最大

不要隐藏选择公理的角色

快速检查

在 Cantor 定理中，对角集合 T 是什么？

答案

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

答案

选择函数选的是什么？

答案

练习

证明单点映射 x -> {x} 是单射。

引导解答

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

引导解答

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

引导解答

相关笔记

本节掌握 checkpoint

先备知识

本单元重点词汇

Premium learning add-ons

本系列更多笔记