1.5 无限集

有限集与基数

若 $S$ 与 $\{1,\dots ,n\}$ 一一对应，称为有限集，其基数记为 $|S|=\mathrm{Card}(S)=n$。允许 $n=0$，空集的基数为零。不是有限集的集合称为无限集。

例 1.9 · 函数集的基数

从 $S$ 到 $T$ 的全部函数组成的集合记为 $T^S$。若 $|S|=s$、$|T|=t$ 都有限，则

$$|T^S|=t^s.$$

每个输入有 $t$ 种输出选择，共有 $s$ 个输入。例 1.7 的特征函数对应给出 $2^S\cong \{0,1{\}}^S$，有限时两者基数都是 $2^s$。

康托尔证明，无限也可以严格处理，并具有不同的大小以及相应的超限算术。

可数集

本章沿用原书约定：与 $\mathbb{N}=\{1,2,3,\dots \}$ 一一对应的集合称为可数无限集，简称可数集；有限集另列。其他文献可能把有限集也包括在“可数”之内。

若有双射 $f:S\to \mathbb{N}$，就可以列出 $s_i=f^{-1}(i)$，得到 $s_1,s_2,\dots$。

例 1.10 · 整数可数

定义 $f:\mathbb{Z}\to \mathbb{N}$：$f(0)=1$，对 $n>0$，$f(n)=2n$、$f(-n)=2n+1$。于是

$$0,1,-1,2,-2,\dots$$

枚举了全部整数，$f$ 是双射。

被引用 1 次

• 1.5 无限集把有理数写成约分后的 …，其中 …、…。它与 … 的一个无限子集一一对应。由例 1.10、定理 1.2 和定理 1.1，得到结论。

定理 1.1 · 可数集的子集

可数集的每个子集或者有限，或者可数。

被引用 2 次

• 1.5 无限集把有理数写成约分后的 …，其中 …、…。它与 … 的一个无限子集一一对应。由例 1.10、定理 1.2 和定理 1.1，得到结论。
• 1.5 无限集一旦证明区间 … 不可数，因其包含于 …，定理 1.1 就保证 … 也不可数。

证明

设 $S=\{s_1,s_2,\dots \}$，$S^{\prime }$ 是无限子集。按原序列的顺序，依次选出属于 $S^{\prime }$ 的第一项、下一项等，得到 $s_1^{\prime },s_2^{\prime },\dots$。每个属于 $S^{\prime }$ 的元素都有有限的原序号，最终都会被列出；映射 $s_i^{\prime }\mapsto i$ 给出到 $\mathbb{N}$ 的双射。

定理 1.2 · 可数集的乘积

两个可数集的笛卡尔积仍然可数。

被引用 1 次

• 1.5 无限集把有理数写成约分后的 …，其中 …、…。它与 … 的一个无限子集一一对应。由例 1.10、定理 1.2 和定理 1.1，得到结论。

证明

若 $S=\{s_i\}$、$T=\{t_j\}$，把 $(s_i,t_j)$ 排列成无限二维表格。沿 $i+j$ 依次增大的对角线遍历，就能把所有有序对排成序列，而且每对只出现一次。

图 1.1 · 可数集乘积的枚举路径。

推论 1.3 · 有理数可数

有理数集 $\mathbb{Q}$ 可数。

被引用 1 次

• 第一章 · 集合与结构本章按原书 1.1–1.7 分节，涵盖全部 15 个编号例子、6 个编号结果（含推论 1.3）、16 道编号习题及 8 道随文练习。中文采用忠于数学内容的整理译文；英文保留原文讨论并修复 OCR。顶部…

证明

把有理数写成约分后的 $n/m$，其中 $n\in \mathbb{Z}$、$m\in \mathbb{N}$。它与 $\mathbb{Z}\times \mathbb{N}$ 的一个无限子集一一对应。由例 1.10、定理 1.2 和定理 1.1，得到结论。

对任意实数 $x<y$，存在有理数 $q$ 使 $x<q<y$，所以 $\mathbb{Q}$ 在 $\mathbb{R}$ 中稠密。实数有可数稠密子集，并不意味着实数整体可数。

不可数集与对角论证

既不有限也不可数的集合称为不可数集；它无法与自然数集的任一子集一一对应。

定理 1.4 · 可数集的幂集不可数

若 $S$ 可数无限，则 $2^S$ 不可数。

被引用 1 次

• 1.5 无限集原书把 … 中的数写为二进制展开 …，并与 … 对应，从而使用定理 1.4 得出不可数性。

证明 · 康托尔对角法

写 $S=\{s_1,s_2,\dots \}$。每个子集 $U$ 对应一个二进制序列：$s_i\in U$ 时 ${ϵ}_i=1$，否则为 $0$。

假设全部子集可列为 $U_1,U_2,\dots$，并把相应序列排列成表格 $({ϵ}_{ij})$。构造新序列

$${ϵ}_i^{\prime }=1-{ϵ}_{ii}.$$

新序列在第 $i$ 位与第 $i$ 个序列不同，因而不等于表中任何序列，却仍然定义 $S$ 的一个子集。矛盾。

定理 1.5 · 实数不可数

实数集 $\mathbb{R}$ 不可数。

被引用 1 次

• 1.5 无限集定理 1.5 的论证有技术漏洞：以无限个 … 结束的二进制展开，可能与以无限个 … 结束的展开表示同一个数，例如

证明 · 原书的二进制论证及其待修补处

原书把 $[0,1]$ 中的数写为二进制展开 $0.{ϵ}_1{ϵ}_2\cdots$，并与 $2^{\mathbb{N}}$ 对应，从而使用定理 1.4 得出不可数性。

**这一直接对应并非双射：**二进制展开存在 $0.0111\dots =0.1000\dots$ 这样的重复。原书习题 1.11 要求修补这一技术漏洞。本页面保留这条论证的任务结构，并不把有漏洞的步骤作为完整证明。

一旦证明区间 $[0,1]$ 不可数，因其包含于 $\mathbb{R}$，定理 1.1 就保证 $\mathbb{R}$ 也不可数。

例 1.11 · 康托尔集

在 $[0,1]$ 中取那些存在只使用数字 $0$、$2$ 的三进制展开的数，得到康托尔集 $C$。也可以从 $[0,1]$ 中删去中间开三分之一 $(1/3,2/3)$，再删去剩余每段的中间开三分之一，如此无限继续。

图 1.2 · 前四次删除后的区间。

每个 $0$–$1$ 序列 $({ϵ}_i)$ 唯一地给出 $C$ 中的点 ${\sum }_{i\ge 1}2{ϵ}_i{3}^{-i}$，所以 $C$ 与 $2^{\mathbb{N}}$ 一一对应，是不可数的；但它又是无处稠密的。将所有三进制数字 $2$ 换成二进制数字 $1$ 得到的实数对应并非单射，须区分“二进制序列”和“具有重复展开的实数”。

这种结构不只是数学奇观，与物理有关的非线性映射也会自然产生类似集合。

连续统假设与选择公理

上述无限实数子集，要么可数，要么与整个实数集等势。康托尔猜想不存在介于自然数与实数之间的基数，这就是连续统假设。

哥德尔证明，在相关公理体系一致的前提下，加入连续统假设不会导致矛盾；科恩后来证明其否定也具有相应的相对一致性。因此，连续统假设在 ZFC 中独立，不能仅用 ZFC 公理证明或否证。这里的独立性陈述都带有公理体系一致的前提。

选择公理

对一族非空集合 $\mathcal{S}=\{S_i\mid i\in I\}$，存在选择函数

$$f:I\to \bigcup \mathcal{S},qquadf(i)\in S_i(i\in I).$$

有限族的选择可由 ZF 证明；对可数族的选择也需要额外公理，不能由每次有限选择直接推出。原书把可数族的情况也称为正确，此处补充这一逻辑区别。选择公理在 ZF 中独立，而在通常数学实践中非常有用。

虽然实数是许多物理理论的基础，不同集合论公理所导致的差异尚未在本章的物理应用中产生决定性的困难。原书认为，选择公理虽方便，其对物理的必要性仍值得思考。它常以如下等价形式出现。

定理 1.6 · 佐恩引理

设 $(P,\le )$ 是非空偏序集，且每个全序子集（链）在 $P$ 中都有上界，则 $P$ 有极大元。

链中的任意两元素都可比较。上界 $x\in P$ 要满足链中的所有 $y$ 都有 $y\le x$。极大元 $z$ 的意思是不存在不同于 $z$ 的 $y$ 满足 $z\le y$；它不必大于所有元素，须与最大元区分。

证明说明 · 本章未给出

原书没有证明佐恩引理，而是指出它与选择公理等价，并把读者引向 Halmos [4] 与 Kelley [6]。这里保留这一说明，不补写原书没有提供的证明。

习题

习题 1.11 · 修补二进制论证

定理 1.5 的论证有技术漏洞：以无限个 $1$ 结束的二进制展开，可能与以无限个 $0$ 结束的展开表示同一个数，例如

$$0.01101111\dots =0.01110000\dots .$$

修补这一问题，得到完整证明。

被引用 1 次

• 1.5 无限集这一直接对应并非双射：二进制展开存在 … 这样的重复。原书习题 1.11 要求修补这一技术漏洞。本页面保留这条论证的任务结构，并不把有漏洞的步骤作为完整证明。

习题 1.12 · 无处稠密性

证明康托尔集无处稠密。

习题 1.13 · 全体实函数的基数

使用康托尔对角论证，证明全体函数 $f:\mathbb{R}\to \mathbb{R}$ 无法与 $\mathbb{R}$ 一一对应，并说明其基数严格大于实数集。

习题 1.14 · 单调函数的不连续点

若 $f:[0,1]\to \mathbb{R}$ 单调不减，且 $f(0)=0$、$f(1)=1$，证明其不连续点构成至多可数的集合。

被引用 2 次

• 1.1 集合与逻辑对象本身可以是集合。有些集合论体系要求所有对象都是集合；在物理讨论中，也常允许温度、速度等“原子对象”。列举法适用于有限集或可数无限集，但无法列出全部实数；第 1.5 节的康托尔对角论证会说明这一点。
• 第一章 · 集合与结构把集合理解为“对象的汇集”属于朴素集合论。罗素发现，过于宽泛的集合构造会产生自指矛盾。严格公理体系可以规避这些问题。本书主要使用朴素的语言，但这并不使集合论的基础问题失去意义：第 1.5 节还会讨论它…