第三章：可数集与不可数集
在集合论与拓扑学中，区分无穷集合的大小（即“基数”或“势”）是极为重要的。并非所有的“无穷”都是相等的，本章将严格定义可数性，探讨可数集的运算性质，并通过 Cantor 对角线法则揭示不可数集的存在性，最终引出基数与连续统假设。
1. 可数集的基本定义
首先，我们需要严格定义集合的“大小”类别，特别是对无穷集合进行分类。
定义 3.1 (有限、无穷与可数)
-
有限集 (Finite Set)：若集合 \(S\) 是空集 \(\emptyset\)，或存在自然数 \(n \in \mathbb{N}_{\ge 1}\) 以及双射 \(f: S \to \{1, 2, \dots, n\}\)，则称 \(S\) 为有限集。
-
无穷集 (Infinite Set)：若集合 \(S\) 不是有限集，则称其为无穷集。
-
可数无穷集 (Countably Infinite Set)：若存在一个双射 \(f: S \to \mathbb{N}\)（其中 \(\mathbb{N}\) 为自然数集），则称 \(S\) 为可数无穷集。
-
可数集 (Countable Set)：如果一个集合是有限的，或者它是可数无穷的，我们统称其为可数集。
作为最基本的例子，整数集 \(\mathbb{Z}\) 是可数无穷集。我们可以显式地构造一个从 \(\mathbb{Z}\) 到 \(\mathbb{N}\) 的双射 \(f: \mathbb{Z} \to \mathbb{N}\) 如下：
该映射将整数序列 \(0, 1, -1, 2, -2, \dots\) 一一对应到自然数序列 \(1, 2, 3, 4, 5, \dots\) 上。
2. 可数集的等价刻画
为了在实际应用中更方便地判断一个集合是否可数，我们有以下等价条件。
定理 3.1 (可数集的等价条件)
设 \(B\) 为任意非空集合，则以下三个命题是等价的（TFAE）：
-
(1) \(B\) 是可数集。
-
(2) 存在从自然数集 \(\mathbb{N}\) 到 \(B\) 的满射 \(f: \mathbb{N} \to B\)。
-
(3) 存在从 \(B\) 到自然数集 \(\mathbb{N}\) 的单射 \(g: B \to \mathbb{N}\)。
定理 3.1 的证明
(1) \(\implies\) (2)： 若 \(B\) 是可数的，它要么是有限的，要么是可数无穷的。 若 \(B\) 是可数无穷的，由定义存在双射 \(h: B \to \mathbb{N}\)，其逆映射 \(h^{-1}: \mathbb{N} \to B\) 显然是满射。 若 \(B\) 是有限的，设 \(B = \{b_1, b_2, \dots, b_k\}\)。我们可以构造满射 \(f: \mathbb{N} \to B\) 如下：
(2) \(\implies\) (3)： 已知存在满射 \(f: \mathbb{N} \to B\)。对于每一个 \(b \in B\)，其原像集 \(f^{-1}(\{b\}) \subseteq \mathbb{N}\) 必定是非空的。 根据自然数集的良序原理 (Well-Ordering Principle)，非空自然数子集必定存在最小元素。 因此，我们可以定义映射 \(g: B \to \mathbb{N}\) 为：
若 \(b_1 \neq b_2\)，由于函数 \(f\) 的单值性，对应的最小原像必定不同，因此 \(g\) 是一个单射。
(3) \(\implies\) (1)： 已知存在单射 \(g: B \to \mathbb{N}\)。这意味着 \(g\) 是 \(B\) 到其像集 \(S = g(B) \subseteq \mathbb{N}\) 的双射。 因此，只需证明自然数集的任意子集 \(S \subseteq \mathbb{N}\) 必定是可数集。
假设 \(S\) 不是有限集。我们希望构造一个双射 \(\varphi: \mathbb{N} \to S\)。利用良序原理进行递归定义：
令 \(S_0 = S\)。
定义 \(\varphi(0) = \min S_0\)。
对于 \(i \ge 1\)，令 \(S_i = S \setminus \{\varphi(0), \varphi(1), \dots, \varphi(i-1)\}\)。
由于 \(S\) 是无穷集，\(S_i\) 永远非空。定义 \(\varphi(i) = \min S_i\)。
显然，这样构造出的 \(\varphi\) 将 \(\mathbb{N}\) 一一对应地映射到了 \(S\) 上，因此 \(S\) 是可数无穷集。 \(\square\)
3. 可数集的运算性质
可数集在基本集合运算（如取子集、有限笛卡尔积、可数并集）下具有极强的封闭性。
定理 3.2 (可数集的封闭性)
-
(i) 可数集的任意子集依然是可数集。
-
(ii) 可数个可数集的并集依然是可数集。
-
(iii) 有限个可数集的笛卡尔积依然是可数集。
运算性质的证明
(i) 的证明： 设 \(A\) 是可数集，\(S \subseteq A\)。由于 \(A\) 可数，存在单射 \(g: A \to \mathbb{N}\)。将 \(g\) 限制在 \(S\) 上，得到 \(g|_S: S \to \mathbb{N}\)，这显然也是单射。由定理 3.1 可知 \(S\) 可数。
(ii) 的证明： 设 \(I\) 为可数指标集，且对每个 \(i \in I\)，\(A_i\) 均为可数集。我们需要证明 \(\bigcup_{i \in I} A_i\) 是可数集。 由于 \(I\) 可数，存在满射 \(g: \mathbb{N} \to I\)。 对于每一个 \(i \in I\)，由于 \(A_i\) 可数，存在满射 \(f_i: \mathbb{N} \to A_i\)。 定义一个新的映射 \(\Phi: \mathbb{N} \times \mathbb{N} \to \bigcup_{i \in I} A_i\) 如下：
显然，由于 \(g\) 遍历了所有指标，且 \(f_{g(m)}\) 遍历了集合中的所有元素，\(\Phi\) 必定是一个满射。 只要我们能证明 \(\mathbb{N} \times \mathbb{N}\) 是可数的（存在从 \(\mathbb{N}\) 到 \(\mathbb{N} \times \mathbb{N}\) 的满射），复合映射即证明了并集的可数性。
引理：\(\mathbb{N} \times \mathbb{N}\) 是可数的。 构造映射 \(H: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)，定义为：
由算术基本定理（素数分解的唯一性），若 \((m, n) \neq (m', n')\)，则 \(2^m \cdot 3^n \neq 2^{m'} \cdot 3^{n'}\)。因此 \(H\) 是单射。由定理 3.1 知 \(\mathbb{N} \times \mathbb{N}\) 可数。这就完成了 (ii) 的证明。
(iii) 的证明： 通过归纳法，只需证明两个可数集 \(A, B\) 的笛卡尔积 \(A \times B\) 是可数集即可。 已知存在满射 \(f_A: \mathbb{N} \to A\) 和 \(f_B: \mathbb{N} \to B\)。构造映射 \(F: \mathbb{N} \times \mathbb{N} \to A \times B\) 为 \(F(m, n) = (f_A(m), f_B(n))\)。这显然是满射。因为 \(\mathbb{N} \times \mathbb{N}\) 可数，故 \(A \times B\) 也是可数的。 \(\square\)
典型应用：正有理数集 \(\mathbb{Q}^+\) 是可数的。因为我们可以构造一个满射 \(f: \mathbb{N}_{\ge 1} \times \mathbb{N}_{\ge 1} \to \mathbb{Q}^+\)，定义为 \((a, b) \mapsto \frac{a}{b}\)。由于 \(\mathbb{Q}^+\) 是可数的，推而广之，整个有理数集 \(\mathbb{Q}\) 也是可数的。
4. 不可数集与 Cantor 对角线法则
并非所有的无穷集都是可数的。无穷个可数集的笛卡尔积通常会导致“不可数”的爆发。
考察集合 \(S = \{0, 1\}\)，定义 \(S^{\mathbb{N}}\) 为所有从 \(\mathbb{N}\) 到 \(\{0, 1\}\) 的函数的集合，等价于所有由 0 和 1 构成的无穷序列的集合。
定理 3.3 (Cantor 对角线法则)
无穷序列空间 \(S^{\mathbb{N}} = \{0, 1\}^{\mathbb{N}}\) 是不可数集。
Cantor 对角线法则的证明
采用反证法。假设 \(S^{\mathbb{N}}\) 是可数的。 那么存在一个双射 \(\varphi: \mathbb{N} \to S^{\mathbb{N}}\)。这意味着我们可以将所有由 0 和 1 构成的无穷序列排成一个列表：
其中所有的 \(x_{ij} \in \{0, 1\}\)。
现在，我们构造一个新的序列 \(y = (y_1, y_2, y_3, \dots) \in S^{\mathbb{N}}\)，使得 \(y\) 不在上述任何一个位置上。构造规则如下（即针对对角线元素取反）：
由于 \(y\) 是由 0 和 1 构成的无穷序列，必然有 \(y \in S^{\mathbb{N}}\)。 但是，对于任意的整数 \(n \in \mathbb{N}\)，序列 \(y\) 与序列 \(\varphi(n)\) 在第 \(n\) 个位置上的元素是不一样的（因为 \(y_n = 1 - x_{nn} \neq x_{nn}\)）。
这意味着 \(y \neq \varphi(n)\) 对一切 \(n\) 恒成立。 这就打破了 \(\varphi\) 是满射的假设。矛盾！因此，\(S^{\mathbb{N}}\) 必定是不可数的。 \(\square\)
注记：通过二进制展开可以建立 \(\{0, 1\}^{\mathbb{N}}\) 到实数区间 \([0, 1]\) 的映射，从而严格证明了实数集 \(\mathbb{R}\) 是不可数集。
5. Cantor 定理与基数理论
进一步抽象，我们可以比较任意集合与其幂集（所有子集构成的集合）之间的大小。对于集合 \(A\)，其幂集记为 \(\mathcal{P}(A)\)。对于自然数集，不难发现 \(\mathcal{P}(\mathbb{N})\) 与 \(\{0, 1\}^{\mathbb{N}}\) 之间存在一一对应关系（通过特征函数）。
定理 3.4 (Cantor 定理)
对于任意集合 \(A\)，不存在从 \(A\) 到其幂集 \(\mathcal{P}(A)\) 的满射，同时也就不存在从 \(\mathcal{P}(A)\) 到 \(A\) 的单射。
Cantor 定理的证明
采用反证法。假设存在满射 \(g: A \to \mathcal{P}(A)\)。 对于任意元素 \(a \in A\)，\(g(a)\) 是 \(\mathcal{P}(A)\) 中的一个元素，即 \(A\) 的一个子集。 我们构造一个“病态”的集合 \(B\)：
显然 \(B \subseteq A\)，所以 \(B \in \mathcal{P}(A)\)。 由于 \(g\) 是满射，必然存在某个元素 \(b \in A\) 使得 \(g(b) = B\)。
现在我们提出一个问题：元素 \(b\) 是否属于集合 \(B\)？
-
若 \(b \in B\)：根据 \(B\) 的定义，必须有 \(b \notin g(b)\)。但 \(g(b) = B\)，即 \(b \notin B\)，矛盾！
-
若 \(b \notin B\)：即 \(b \notin g(b)\)。同样根据 \(B\) 的定义，满足此条件的元素必在 \(B\) 中，即 \(b \in B\)，矛盾！
无论哪种情况都会导致逻辑崩溃（这类似于罗素悖论的构造）。因此，不存在这样的满射。 \(\square\)
5.1 基数与连续统假设 (Cardinality and Continuum Hypothesis)
基于单射与双射，我们定义集合的基数 (Cardinality) 关系：
- 相等：若存在双射 \(A \to B\)，记作 \(\text{Card}(A) = \text{Card}(B)\) 或 \(|A| = |B|\)。
- 严格小于：若存在单射 \(A \to B\)，且不存在双射 \(A \to B\)，记作 \(\text{Card}(A) < \text{Card}(B)\)。
我们用 \(\aleph_0\)（阿列夫零）表示可数无穷集的基数（即 \(\text{Card}(\mathbb{N})\)）。 由 Cantor 定理，我们可以构造出无穷尽的、越来越大的基数序列：
其中实数集的基数被称为连续统基数 \(\mathfrak{c}\)，并且已知 \(\mathfrak{c} = \text{Card}(\mathcal{P}(\mathbb{N})) = 2^{\aleph_0}\)。因此 \(\aleph_0 < 2^{\aleph_0}\)。
连续统假设 (Continuum Hypothesis, CH)： Cantor 提出了一个著名的问题：是否存在一个集合 \(X\)，它的基数严格介于自然数集和实数集之间？即是否存在 \(X\) 满足：
连续统假设猜想“不存在这样的集合”。现代集合论已证明，连续统假设在标准 ZFC 公理系统中既不能被证明，也不能被证伪（即它是独立于 ZFC 系统的）。