6.1 基数、可数性与基数不等式

第 6 章改变了我们提问的方式。前面的章节发展数系及其运算；现在我们问一 个集合有多大，即使它没有最后一个元素可以数。答案通过函数表达：双射精确 配对两个集合，单射则把一个集合无碰撞地记录在另一个集合中。这样，关于无 限大小的说法也能变得精确。

用来比较集合的函数

设 $f:X\to Y$ 为函数。它的像集为

$$f(X)=\{f(x)\mid x\in X\}\subseteq Y,$$

对 $B\subseteq Y$ 的原像为

$$f^{-1}(B)=\{x\in X\mid f(x)\in B\}.$$

记号 $f^{-1}(y)$ 可以表示单点集 $\{y\}$ 的原像；它不表示逆函数一定存在。 只有双射才有逆函数。

定义

单射、满射与双射

函数 $f:X\to Y$ 称为单射，如果

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2 \qquad (x_1,x_2\in X).$$

因此 $Y$ 中每个元素至多有一个原像。它称为满射，如果

$$\forall y\in Y\;\exists x\in X\text{ 使得 }f(x)=y,$$

等价地说 $f(X)=Y$；陪域中的每个元素都被击中。如果同时是单射与满射，就 称为双射。

陪域很重要。例如 $f:N\to N$，$f(n)=n+1$，是单射而不是满射，因为 $0$ 没有 被击中。若把陪域改成 $N\setminus\{0\}$，同一个规则就成为双射。因此，关于 基数的命题必须同时写清定义域与陪域。

例题

检查三种性质

考虑 $u:\{0,1,2\}\to\{a,b,c,d\}$，其中

$$u(0)=a,\qquad u(1)=c,\qquad u(2)=a.$$

它不是单射，因为 $u(0)=u(2)$ 但 $0\ne2$；它也不是满射，因为 $b$ 与 $d$ 不是输出。这个小例子把两个条件分开：单射关注输出是否重复，满射关注陪域 元素是否遗漏。

相同基数与可数性

定义

相同基数

若存在双射 $f:X\to Y$，就称集合 $X$ 与 $Y$ 有相同基数，并写成

$$|X|=|Y|.$$

被配对的元素不必具有相同性质。把数与有序对配对，与把两列数字配对一样合 法。对有限集合，这个定义与普通数数一致。

概念视角结构

把基数理解为数数与配对

对于有限集合，大小很容易让人联想到清点：把元素一个个数出来。对于任意集合，定义则把这种清点改成配对检验：能否把 $X$ 的每个元素与 $Y$ 的恰好一个元素配对，并且反向也能做到？这就是为什么 $N$ 与偶数自然数 $2N=\{0,2,4,\ldots\}$ 通过 $n\mapsto 2n$ 具有相同基数，尽管 $2N$ 是 $N$ 的真子集。双射记录了相同的大小；真包含本身并不意味着基数严格更小。

定义

有限集合

若某个 $n\in N$ 满足 $|X|=|n|$，其中我们把 $n$ 表示为有限标签集 $n=\{0,\ldots,n-1\}$；当 $n=0$ 时，这表示 $n=\varnothing$，就称 $X$ 为有限集合，并写 $|X|=n$。空集也是有限的，且 $|\varnothing|=0$。

定义

可数与至多可数

在本课程中，如果 $X$ 是有限集合，或者

$$|X|=|N|,$$

就称 $X$ 可数。等价地，若 $X$ 有限或可数无限，就称它至多可数。有 些教材只把无限情形称为 countable，因此“至多可数”可以消除这种约定差异。 不是至多可数的集合称为不可数。

对可数无限集合来说，一个列举是序列 $x_0,x_1,x_2,\ldots$，其中每个元素恰 好出现一次。“恰好一次”同时包含列举的满射性与索引映射的单射性。仅仅写 出一条无限序列还不够；必须说明为什么没有遗漏，也没有重复。

可数集合的明确列举

整数

定理

整数是可数的

$|Z|=|N|$。

设 $N=\{0,1,2,\ldots\}$，定义

$$e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1).$$

这给出序列 $0,1,-1,2,-2,3,-3,\ldots$。

证明。 每个整数或者是 $0$，或者是正整数 $k$，或者是 $k\ge1$ 时的负 整数 $-k$。它们分别出现在索引 $0$、$2k-1$、$2k$ 处，因此 $e$ 是满射。三 种情形的值互不相同，而在正数或负数情形中，显示的索引又唯一确定 $k$，所 以 $e$ 是单射。因此 $e$ 是双射。若 $N$ 从 $1$ 开始编号，只需把索引整体平 移一个单位；基数结论不变。

这个例子体现无限集合的基本惊讶之处：把所有负整数加入 $N$ 并没有产生更大 的基数。比较的是是否存在双射，而不是一个集合是否包含另一个集合。

有理数

定理

有理数是可数的

有理数集合 $Q$ 至多可数，事实上是可数无限的。

每个正有理数都有唯一的最简表示 $p/q$，其中 $p,q\in\{1,2,3,\ldots\}$ 且 $\gcd(p,q)=1$。把 $p/q$ 放在第 $p$ 行、第 $q$ 列，然后沿有限对角线 $p+q=2,3,4,\ldots$ 扫描。每条对角线内按分子递增扫描（固定任何一种顺序 都可以），只保留互素的数对。开头可以是

$$1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots.$$

例题

为什么有理数的对角扫描有效

例如 $7/5$ 已经是最简形式，位于对角线 $p+q=12$。在第 12 条对角线之前 只有有限条对角线，而第 12 条也只有有限个数对，所以 $7/5$ 会在有限位置 被扫到。另一方面，只保留互素数对意味着两个被记录的数对不可能表示同一个 正有理数：最简表示的唯一性迫使 $(p,q)$ 相同。因此，这个扫描对 $Q_+$ 既是 满的，也是单的。

这个论证同时证明了两个方向。每个正有理数都有最简数对，所以没有遗漏；最 简数对唯一，所以没有重复。若所得列举为 $q_1,q_2,q_3,\ldots$，则

$$0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots$$

列出每个有理数恰好一次。零出现一次，每个非零有理数都有唯一的符号和唯一 的正绝对值。因此 $Q$ 可数。 它不是有限集：包含映射 $n\mapsto n$ 从 $N$ 到 $Q$ 是单射，所以 $Q$ 包含无 限多个互不相同的整数。

图示。对角扫描把二维格点变成一条序列；最简形式条件消除了同一个有理数 的不同表示。

稠密性是另一个性质。有理数与实线的每个非空开区间相交，但对角线程序仍然 能把它们放入一条序列。稠密不等于不可数。

可数集合的乘积

网格论证也给出两个 $N$ 的明确配对。对 $a,b\in N$，令

$$\pi(a,b)=\frac{(a+b)(a+b+1)}2+b.$$

满足固定 $a+b=s$ 的数对形成有限对角线；三角数 $s(s+1)/2$ 正好跳过此前 的对角线。因此 $\pi$ 每个数对恰好列出一次。更形式地，从 $n=\pi(a,b)$ 可以恢复唯一的对角线 $s$，使 $s(s+1)/2\le n\lt(s+1)(s+2)/2$，再得到 $b=n-s(s+1)/2$ 与 $a=s-b$。所以 $\pi:N\times N\to N$ 是双射。

定理

可数三元组仍然可数

$|N\times N\times N|=|N|$。

证明。 定义

$$\Phi(a,b,c)=\pi(\pi(a,b),c)$$

两次使用的 $\pi$ 都是双射，所以它们的合成是从 $N^3$ 到 $N$ 的双射。逆映 射先恢复 $(\pi(a,b),c)$，再恢复 $(a,b)$。这就是“可数乘可数乘可数”仍然 可数的具体含义：有限维网格可以用一串有限对角线扫描。若某个乘积因子为空， 乘积就是空集，因而有限；上面的双射针对的是三个 $N$ 的乘积。

同一个配对也能处理有限个带标签的可数集合。例如用 $(n,i)\mapsto\pi(n,i)$ 把 $(n,0)$ 与 $(n,1)$ 映入 $N$。这个映射是单射，所 以两个 $N$ 的副本可以存放在一个 $N$ 中；在合适的坐标上使用配对映射的逆， 便能恢复标签与原来的数字。这说明无限列举可以吸收有限的额外标记，但并不 表示任意扩张都与原集合等大：仍然必须证明具体映射存在。

更一般地，基数比较可以沿映射传递。若 $X\to Y$ 与 $Y\to Z$ 是单射，合成便 给出 $|X|\le|Z|$；若两个映射都是双射，合成也是双射。这两个简单规则正是本 节整数、有理数与三元组列举背后的映射记账。

基数不等式

定义

基数不等式

对集合 $X$、$Y$，若存在单射 $X\to Y$，就写

$$|X|\le |Y|$$

若 $|X|\le|Y|$ 且 $|X|\ne|Y|$，就写 $|X|\lt|Y|$。

箭头方向不可忽略：从 $X$ 到 $Y$ 的单射说明 $Y$ 有足够多互不相同的位置存放 $X$ 的每个元素，所以定义域是“不更大”的一方。包含映射 $N\to Z$、$n\mapsto n$ 证明 $|N|\le|Z|$，但单凭它不能证明相等。整数的列 举给出反向比较，而前面的明确双射直接给出相等。

例题

陪域有未使用元素的有限比较

定义 $r:\{1,2,3\}\to\{a,b,c,d\}$ 为 $r(1)=b$、$r(2)=d$、$r(3)=a$。它是单射，所以 $|\{1,2,3\}|\le|\{a,b,c,d\}|$。它不是满射，因为 $c$ 没有被使用，这正 是严格不等式可能出现的原因。

定理

基数不等式具有偏序结构

基数上的关系 $\le$ 具有自反性、传递性和反对称性。因此 $\lt$ 具有非自反性 和传递性。

证明。 恒等映射 $id_X:X\to X$ 是单射，所以有自反性。若 $f:X\to Y$、$g:Y\to Z$ 都是单射，则 $g\circ f$ 也是单射：合成后的输出相等 先给出 $f$ 的输出相等，再给出输入相等，所以有传递性。反对称性正是下面的 Cantor-Bernstein 定理。最后，因为 $|X|=|X|$，不可能有 $|X|\lt|X|$；结合 $\le$ 的传递性即可得到严格不等式的传递性。

不存在一个以所有集合为元素的集合。假设有这样的全集，就可以构造 Russell 类型的自指成员关系而得到矛盾。因此，这里的 $\le$ 不是定义在某个 以“所有集合的集合”为定义域的全局关系；偏序性质只针对我们选定、正在比较 的一族集合，或由它们表示的那一族基数。这个限定只是基础层面的记账，不会 改变上面的映射或证明。

满射 $X\to Y$ 直观上表示 $Y$ 不比 $X$ 大，但要把它转成 $Y\to X$ 的单射， 就要为每个 $y\in Y$ 选择一个原像。下一篇笔记会讨论这个选择问题；本节直 接使用单射与双射，不额外假设选择函数。

Cantor-Bernstein：把两个单射拼起来

定理

Cantor-Bernstein 定理

若 $f:X\to Y$ 与 $g:Y\to X$ 都是单射，则 $|X|=|Y|$。

这个定理即使两个单射都不是满射，也能构造双射。令

$$A_0=X,\qquad B_0=g(Y),$$

并递归定义

$$A_{n+1}=g(f(A_n)),\qquad B_{n+1}=g(f(B_n)).$$

由于 $g(Y)\subseteq X$，这些集合满足

$$A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq A_2\supseteq B_2\supseteq\cdots.$$

这些包含关系可以归纳得到：先有 $A_1\subseteq B_0$，再有 $B_{n+1}\subseteq A_{n+1}$；而前一步的 $A_n\subseteq B_{n-1}$ 又给出 $A_{n+1}\subseteq B_n$。若 $X$ 或 $Y$ 为空，两个单射的存在会迫使两个集合 都为空，唯一的空映射就是所需双射；下面的构造也涵盖这个情形。

层 $A_n\setminus B_n$ 是使用 $f$ 的部分；其余点位于 $g(Y)$ 中，在那里使用 $g$ 在像集上的逆。

证明。 首先 $g\circ f:X\to X$ 是单射。对每个 $n$，它把 $A_n\setminus B_n$ 双射到 $A_{n+1}\setminus B_{n+1}$。单射性给出不重复性。 若 $z\in A_{n+1}\setminus B_{n+1}$，可写成 $z=g(f(x))$ 且 $x\in A_n$；若 $x\in B_n$，则 $z\in g(f(B_n))=B_{n+1}$，矛盾。因此 $x\in A_n\setminus B_n$，从而得到满射性。

定义 $h:X\to Y$：

$$h(x)= \begin{cases} f(x),&x\in A_n\setminus B_n\text{ 对某个 }n,\\ g^{-1}(x),&x\notin A_n\setminus B_n\text{ 对所有 }n \end{cases}$$

这里 $g^{-1}$ 指双射 $g:Y\to g(Y)$ 的逆，而不是整个 $X$ 上的逆。第二种情 形确实有定义：不在任何层中的点不可能在零层 $A_0\setminus B_0=X\setminus g(Y)$ 中，所以它属于 $g(Y)$。层彼此不交，因 此 $h$ 定义良好。

证明单射性。若 $h(x_1)=h(x_2)$，且两点都在层中，则由 $f$ 单射得 $x_1=x_2$；若两点都在第二种情形，则由 $g^{-1}$ 单射得相等。若情形混合， 不妨设 $x_1\in A_n\setminus B_n$，且 $h(x_2)=g^{-1}(x_2)$。等式给出 $x_2=g(f(x_1))$，由层之间的双射性可知 $x_2\in A_{n+1}\setminus B_{n+1}$，这与第二种情形矛盾。

证明满射性。任取 $y\in Y$，令 $x=g(y)\in X$。若 $x$ 不在任何层中，则 $h(x)=g^{-1}(x)=y$。否则 $x\in A_n\setminus B_n$。它不可能在零层，因为 零层是 $X\setminus g(Y)$ 而 $x\in g(Y)$，所以 $n\ge1$。层之间的双射性给出 $x'\in A_{n-1}\setminus B_{n-1}$，满足 $g(f(x'))=x=g(y)$。由 $g$ 单射得 $f(x')=y$，所以 $h(x')=y$。故 $h$ 是满射，也是双射，$|X|=|Y|$。整个构造 只使用给定的 $f$ 与 $g$，没有使用选择函数。

为什么粗分层会遗漏元素

单凭集合 $A_n$ 不能记录在哪里可以使用 $g$ 的逆。 令 $A=\bigcap_{n\ge0}A_n$。第一个简化构造在每个差集 $A_n\setminus A_{n+1}$ 以及 $A$ 上都使用 $f$。这些部分穷尽 $X$， 所以这个构造其实就是

$$h_1(x)=f(x)\qquad(x\in X).$$

第二个构造为

$$h_2(x)=\begin{cases} f(x),&x\in A_n\setminus A_{n+1}\text{ 对某个 }n,\\ g^{-1}(x),&x\in A. \end{cases}$$

由于 $A\subseteq A_1\subseteq g(Y)$，逆映射这一分支有定义， 但定义良好还不足以保证双射。取 $X=Y=N$、$f(n)=n+1$、$g(n)=n$。 此时 $A_n=\{n,n+1,\ldots\}$ 且 $A=\varnothing$，两个构造都给出 $h_1(n)=h_2(n)=n+1$，从而遗漏 $0$。已证明的构造使用 $B_n$ 分层， 保留了这两个简化方案丢失的信息：逆映射分支在哪里可用，以及两个分支 怎样避免输出碰撞。

常见错误与细节

常见错误

一个单射只给出一个方向的不等式

单射 $X\to Y$ 只证明 $|X|\le|Y|$，不证明相等。相等需要双射，或两个方向的 单射再应用 Cantor-Bernstein 定理。

常见错误

满射不等于单射

满射允许多个输入映到同一个输出；单射则允许陪域中有元素未被击中。请检查正 确的量词条件。

常见错误

最简形式是 Q 证明的一部分

若没有互素条件，$1/1$、$2/2$、$3/3$ 会重复表示同一个有理数。网格虽然可数， 但所写列举也必须是单射。

思考检查

哪一个方向的映射证明 $|X|\le|Y|$？它必须保持什么？

写出定义域、陪域以及碰撞条件。

解答 · 答案

单射 $f:X\to Y$ 证明 $|X|\le|Y|$。它保持不同性的意义是 $f(x_1)=f(x_2)$ 必须推出 $x_1=x_2$；它不必击中 $Y$ 的每个元素。

思考检查

为什么对角线列举会列出每个正有理数？

使用最简形式与有限的 $p+q$。

解答 · 答案

每个正有理数都有唯一的最简数对 $(p,q)$。该数对位于有限对角线 $p+q$ 上， 而扫描会到达每一条有限对角线。

思考检查

Cantor-Bernstein 的定义为什么同时需要 $B_n$ 与 $A_n$？

解答 · 答案

$B_0=g(Y)$ 保证不在任何层中的点属于 $g(Y)$，所以 $g^{-1}$ 有定义。 此外，$g\circ f$ 把 $A_n\setminus B_n$ 映满 $A_{n+1}\setminus B_{n+1}$。因此，若两个分支的输出相同，逆映射分支的 点就必须落在某一层中，与它的分支条件矛盾。

练习

思考检查

给出从 $N$ 到 $Z$ 的明确双射，并证明它既是单射又是满射。

解答 · 引导解答

使用 $e(0)=0$、$e(2k-1)=k$、$e(2k)=-k$（$k\ge1$）。零、每个正整数 $k$ 和每个负整数 $-k$ 分别在指标 $0$、$2k-1$、$2k$ 处出现，所以是满射。 这三类值互不相交，而且每个公式都唯一确定 $k$，所以也是单射。

思考检查

用配对映射 $\pi(a,b)=\frac{(a+b)(a+b+1)}2+b$ 直接证明 $|N\times N\times N|=|N|$。

解答 · 引导解答

先证明 $\pi$ 可逆：恢复唯一的对角线 $s=a+b$，再恢复 $a,b$。复合映射 $\Phi(a,b,c)=\pi(\pi(a,b),c)$ 是两个双射的合成，所以是从三元组乘积到 $N$ 的双射。

思考检查

Cantor-Bernstein 证明中，为什么第二种情形的 $g^{-1}(x)$ 有定义？

解答 · 引导解答

零层是 $X\setminus g(Y)$。不在任何层中的点不在这个集合中，所以它属于 $g(Y)$，而 $g:Y\to g(Y)$ 的逆在那里有定义。

相关笔记

可先阅读2.2 函数与关系， 了解像集、原像、单射、满射与逆函数；然后继续阅读 6.2 Cantor 定理、连续统与选择公理。