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

第 6 章开始时，问题的角度有所改变。前面几章主要构造和研究特定的数系； 这一章问的是更一般的问题：如果集合很大，尤其是无限集合，我们应该怎样比 较它们的大小？

对有限集合来说，逐个数元素已经足够。对无限集合来说，更稳定的方法是研究 函数。双射表示两个集合的元素可以完全一一配对；单射表示一个集合可以不撞 车地编码到另一个集合里。

相同基数

这个定义刻意不要求两个集合的元素有相同性质。元素可以完全不同；真正重要 的是能否把 $X$ 的每个元素配到 $Y$ 的唯一元素，而且 $Y$ 的每个元素也都被 配到。

对有限集合来说，这与普通的数数一致。如果一个集合可以与 n 个标签组成 的集合双射，便说它有 n 个元素。

因此 |X| 不应被理解为任何集合都自动对应一个普通数字。它表示 $X$ 的 大小，即基数。有限集合的基数可用自然数表示；无限集合的基数则需要透过映 射来比较。

可数与不可数

所以，一个可数无限集合的元素可以排成一列而不遗漏、不重复：

$$x_0,x_1,x_2,\ldots$$

至于 $N$ 从 0 还是 1 开始，只影响索引写法，不影响可数性的本质。

整数是可数的

讲义要求证明

$$|N|=|Z|.$$

核心想法是：所有整数可以排成一条无限序列。

这个例子说明无限集合的第一个现象：即使 $Z$ 看起来比 $N$ 多出很多元素， 两者仍然可以有相同基数。

有理数是可数的

讲义先处理正有理数。只要能列举 $Q_+$，便可以再把正有理数、负有理数和 零交错列出，从而列举整个 $Q$。

每个正有理数在最简形式下可写成

$$\frac{p}{q},$$

其中 $p,q\in N$ 为正，并且没有大于 1 的公因子。把这个分数放在第 p 行、第 q 列的无限表格里，然后按对角线

$$p+q=2,\quad p+q=3,\quad p+q=4,\quad \ldots$$

依次扫过，只记录最简分数。

图示。对角扫描不是装饰，而是将正有理数的二维格点转成一条序列的机制。

这为什么给出 $Q_+$ 的列举？

• 它是满的：每个正有理数都有某个最简表示 p/q，所以必定出现在表格中。
• 它不重复：只用最简形式，便不会把 1/1、2/2、3/3 当成不同有理数。

有了 $Q_+$ 的列举

$$q_1,q_2,q_3,\ldots,$$

便可列出

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

因此 $Q$ 可数。

用单射比较基数

双射判断基数是否相等。若要比较可能不相等的大小，讲义使用单射。

单射 $X\to Y$ 的意思是：$Y$ 有足够位置为 $X$ 的每个元素放置互不相同的 编码。这正是基数版本的“小于或等于”。

基数不等式具有偏序性质

讲义中的证明结构如下。

自反性。 恒等映射

$$id_X:X\to X$$

是单射，所以 $|X|\le |X|$。

传递性。 若 $f:X\to Y$ 与 $g:Y\to Z$ 都是单射，则合成

$$g\circ f:X\to Z$$

也是单射。因此 $|X|\le |Y|$ 且 $|Y|\le |Z|$ 蕴含 $|X|\le |Z|$。

反对称性。 这正是 Cantor-Bernstein 定理的内容。

Cantor-Bernstein 定理

换句话说，如果 $X$ 可以单射到 $Y$，而 $Y$ 也可以单射到 $X$，那么二者实 际上有相同基数。这句话直观上很合理，但无限集合情况下的证明并不只是有限 集合论证的直接翻版。

讲义给出一个证明梗概。设

$$f:X\to Y,\qquad g:Y\to X$$

为单射。由于 g 把 $Y$ 嵌入 $X$，像集 g(Y) 可视为放在 $X$ 里的一份 $Y$ 的副本。证明构造 $X$ 的一串巢状子集

$$A_0\supset B_0\supset A_1\supset B_1\supset\cdots$$

其中

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

并且

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

映射 $g\circ f:X\to X$ 将每一层差集

$$A_n\setminus B_n$$

双射到下一层差集

$$A_{n+1}\setminus B_{n+1}.$$

最后要构造的双射 $h:X\to Y$ 分段定义如下：

$$h(x)= \begin{cases} f(x), & x\in A_n\setminus B_n\text{ for some }n,\\ g^{-1}(x), & \text{otherwise.} \end{cases}$$

这个构造的重点不是“一眼看出”双射，而是两个单射提供了足够结构，可以把 $X$ 分成适当部分，再逐部分定义真正的双射。

辅助比较实验

下面的互动组件只是辅助正式语言。可用它分辨双射、单射、两边单射分别在说 什么，再回到上面的定义与定理。

常见错误与细节

快速检查

练习

相关笔记

可先读 2.2 函数与关系， 特别是单射、满射、双射与偏序的部分。然后接着读 6.1.2-6.3 Cantor 定理、连续统与选择公理。