集合的基数

贡献者： addis; JierPeter

预备知识　映射

　　本文节选自《小时百科系列教材》中的《代数学》，为了良好的阅读体验和完整的讲解内容，建议阅读原书。

1. 引言

　　当我们讨论问题的时候，一定是在围绕某些对象、概念进行的，这些对象或概念就可以构成一个集合。讨论如何计算销售苹果的数量的时候，我们是在整数的集合上讨论运算；绘画一张地图的时候，我们是在坐标点的集合上讨论各点的性质，如地势高低、地形特征等等。原始的集合概念几乎在数学诞生之初就模糊地存在于人们的脑海中了，只是一直以来都局限于原始的直觉，通常是有限的集合，而无穷集合则被认为是不在严谨的数学框架中的。人们一直都没有意识到 “集合” 这一概念有什么深入研究的意义，直到康托尔（Cantor）迈出了探索无穷的第一步。

　　如何研究无穷呢？要回答这个问题，我们首先要回答另一个问题：我们可以对无穷提出什么样的问题？最基本的一个问题自然是：什么叫做无穷？

　　有限的集合，就是所包含的元素数量是有限的。如果 $A$ 是一个有限集合，那么不管 $A$ 含有几个元素，一个，两个，五个，十个，一千零二十四个，我们总能找到一个非负整数来对应 $A$ 的元素数量。也可以这么想象：从 $A$ 中依次拿出元素，拿出的元素不放回；从零开始，每拿一个计数增加一个；当元素全部拿出来的时候，计数的结果就是 $A$ 的元素数量。如果拿的顺序不一样，计数结果会有变化吗？为什么呢¹？

　　我们自然会推想，无限集合就是指元素数量无限。但是我们并没有定义 “无限” 这样一个数字，就没法像有限集合一样赋予一个非负整数作为它的元素数量。怎么严格描述什么是无限呢？方法其实很简单：不论你选择哪一个非负整数 $k$，从集合 $A$ 中拿走 $k$ 个元素以后仍然有剩下的元素，那么我们就说 $A$ 是一个无限集合²。

　　为了方便讨论，我们把集合所包含的元素数量称作基数（cardinal，或势）。用这个术语来说，比较集合的大小就是在比较它们的基数的大小。

　　有限集合非常容易比较大小：给定有限集合 $A$ 和 $B$，同时从两个集合中拿走元素，每次分别拿一个，那么先被拿完的那个集合就比较小；如果同时被拿完，那么两个集合一样大。这也就是整数比大小的原理。

　　从集合中一个一个拿走元素的行为，可以叫做 “计数”、“数数” 等。这种方式可以很好地比较甚至计算有限集合的元素数量，但对于无限集合却束手无策，因为按照无限集合的定义，无论你数了多少个元素出来，依然会有剩下的元素，换句话说，怎么数都数不完，那该怎么办呢？

　　康托尔意识到我们可以用 “一一对应” 的思想来比较集合的数量。这其实就是计数的延伸：如果两个集合之间的元素可以一一对应，即每一个元素都对应对方的唯一一个元素，那么就说这两个集合是相等的。如果无论怎么构造和集合 $A$ 和 $B$ 的对应，总是无法让每个 $B$ 的元素都对应到 $A$ 上，也就是说 $B$ 总有多余元素，那么我们就说 $B$ 是大于 $A$ 的。

　　上述描述看起来很绕口，因此我们引出了 “映射” 的概念，来专门描述集合间的元素对应关系。

2. 可数基数

　　有了映射的概念，我们就可以比较两个集合的元素数量了：如果集合 $A$ 和 $B$ 之间能够建立双射，那么我们就说 $A$ 和 $B$ 的基数相同。对于有限集合，由于我们可以给每个元素进行编号，很容易就能看出 “两个有限集合的基数相同，当且仅当它们的元素数量相同”。我把这段话写成如下定义：

定义 1　

　　如果 $A$ 是有限集合，那么称 $A$ 的元素数量为其基数（cardinal number），记为 $ \left\lvert A \right\rvert $。对于任意集合 $A$ 和 $B$，如果 $A$ 到 $B$ 之间存在一个双射，那么定义 $ \left\lvert A \right\rvert = \left\lvert B \right\rvert $。

　　对于有限集合，基数相同的时候，单射必然是双射——无论你怎么从一个集合到另一个集合进行元素对应，只要保持 “被映射过的元素不再参与映射”，那么最后总能涉及到所有元素，也就是说只要保持单射，最后总能得到满射。

　　但是，对于无限集合，情况就不一样了。考虑全体正整数的集合 $\mathbb{Z}^+$，以及全体正偶数的集合 $2\mathbb{Z}^+$，如果把映射 $f:\mathbb{Z}^+\rightarrow2\mathbb{Z}^+$ 定义为 $f(n)=2n$，那么容易验证 $f$ 是一个双射³，也就是说，$ \left\lvert \mathbb{Z}^+ \right\rvert = \left\lvert 2\mathbb{Z}^+ \right\rvert $，即全体正整数和正偶数的数量是一样的，尽管后者是前者的真子集！这就是无限集合所特有的性质，部分可以等于整体。

定义 2　

　　如果集合 $A$ 到集合 $B$ 存在一个单射，那么记 $ \left\lvert A \right\rvert \leq \left\lvert B \right\rvert $，称作 “$A$ 的基数小于等于 $B$ 的基数”；如果 $A$ 到 $B$ 有一个满射，那么记 $ \left\lvert A \right\rvert \geq \left\lvert B \right\rvert $，称作 “$A$ 的基数大于等于 $B$ 的基数”。⁴

　　根据以上定义，如果 $ \left\lvert A \right\rvert \leq \left\lvert B \right\rvert $ 且 $ \left\lvert A \right\rvert \geq \left\lvert B \right\rvert $，那么就有 $ \left\lvert A \right\rvert = \left\lvert B \right\rvert $。

定义 3　

　　记全体正整数的集合 $\mathbb{Z}^+$ 的基数为 $\aleph_0$，且称任何基数小于等于$\aleph_0$ 的集合为可数集（countable set）。

　　可数集这一定义比较顾名思义。按照可数集、基数以及单射的定义，对于任意可数集 $A$，可以给每个元素挨个分配一个正整数，就好像给它们排序后报数一样，虽然不一定报得完，但是每个元素总可以报一次的。也就是说，可数集是 “可以计数” 的集合，尽管并不一定能数出全部元素，但是只要数下去，任何元素都可以数到。更准确地说，对于可数集 $A$，可以给定数数的规则（从 $\mathbb{Z}+$ 到 $A$ 的满射），使得若随机点出一个 $A$ 的元素，这个元素总能被数到至少一次。

　　我们特地定义了可数集，说明存在不可数的集合。以下所说的幂集就可以用来构造不可数集。

3. 幂集与不可数基数

　　我们已经知道，对于无限集合，部分是可以等于整体的。那么无限集合的无限部分是不是一定能等于整体呢？答案是否定的。这也就是说，无限集合之间是可以严格比大小的，更 “小” 的无限集合永远不能与更 “大” 的无限集合建立双射。

定义 4　

　　给定集合 $A$，记 $2^A$ 为集合 $A$ 的子集的集合，即 $2^A=\{A\text{的子集}\}$。称 $2^A$ 是 $A$ 的幂集（power set）。

　　幂集的概念，就对应我们之前说到的 “把集合本身看成一个元素” 的视角了。如果 $A=\{1,2,3\}$，那么就有 $2^A=\{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, A\}$。注意空集 $\varnothing$ 和 $A$ 本身都是 $2^A$ 的元素，取子集的时候不要忘了空集和集合本身。

　　在上一段的例子里，$ \left\lvert A \right\rvert =3$，而 $ \left\lvert 2^A \right\rvert =8$。集合和幂集的基数之间有什么关系呢？答案是 $ \left\lvert 2^A \right\rvert =2^{ \left\lvert A \right\rvert }$，这也是把幂集记为 $2^A$ 的主要原因。对于有限集合 $A$，显然有 $ \left\lvert 2^A \right\rvert =2^{ \left\lvert A \right\rvert }> \left\lvert A \right\rvert $，那么对于无限集合 $B$ 会怎样呢？都是无限，$ \left\lvert B \right\rvert $ 和 $ \left\lvert 2^B \right\rvert $ 相等吗？

　　答案是否定的，因为不存在 $B$ 到 $2^B$ 的满射，按照定义，这就是说，$ \left\lvert 2^B \right\rvert $ 严格大于 $ \left\lvert B \right\rvert $。

定理 1　

　　给定任意集合（不论是否有限）$B$，则不存在 $B$ 到 $2^B$ 的满射。

　　证明：

　　我们用反证法。任取映射 $f:B\rightarrow 2^B$，反设 $f$ 是满射。

　　在 $2^B$ 中取一个集合 $S$，它的构造如下：如果对于 $b\in B$，有 $b\not\in f(b)$，那么把 $b$ 纳入 $S$ 中。所有这些 “映射结果不包含自己” 的元素构成的集合就是 $S$。这样的 $S$ 存在吗？当然存在，即使所有 $b$ 都是 $f(b)$ 的元素，我们也可以取 $S=\varnothing$。但是根据 $S$ 的定义，没有任何 $b$ 映射到 $S$ 上。因此 $f$ 不可能是满射，得出矛盾——反设条件不成立。

　　即任取映射 $f:B\rightarrow 2^B$，$f$ 一定不是满射。

　　证毕。

　　这个证明很巧妙，如果你是初学者，一定要反复咀嚼，想象多种不同的 $B$ 到 $2^B$ 的映射，看看这个证明是怎么应用到你所想象的任何例子上的，进而理解这个证明是怎么保证对所有集合 $B$、所有映射 $f:B\rightarrow 2^B$ 都成立的——尽管我们无法列举所有情况。

　　幂集的存在，使得不可数集合很容易构建。$\mathbb{Z}$ 是可数集，但是 $2^{\mathbb{Z}}$ 就不可数，因为无法构建 $\mathbb{Z}^+$ 到 $2^{\mathbb{Z}}$ 的满射，也就是说，不管制定什么样的数数规则，总能挑出 $2^{\mathbb{Z}}$ 中的某个元素，它不会被数到。

　　使用幂集，我们很容易构建基数越来越大的集合。我们用归纳的方法来定义最小的一批无穷基数：

定义 5　

　　如果 $ \left\lvert A \right\rvert =\aleph_k$，那么定义 $ \left\lvert 2^A \right\rvert =\aleph_{k+1}$。

　　由于我们已经定义了最小的无穷基数 $\aleph_0$，因此这一方法可以推广出很多更大的无穷基数。当然，还有非常多更大的无穷基数，我们就先不展开了。

　　所有这些无穷基数，如果不做区分的话，都可以用符号 $\infty$ 来指代。要注意的是，$\infty$ 不仅可以指代这些存在的无穷基数，更常使用的场景是表示一种趋向的过程，比如 $\lim_{x\rightarrow +\infty}$ 表示 $x$“越来越大且没有上限”，而不是说 $x$ 越来越接近一个无穷基数——通常，这样的 $x$ 只能取实数值，而没有任何实数是无穷基数。无穷基数只用来表示无穷集合的大小程度。

　　值得一提的是，习惯上有时也会用 $\aleph$ 或者 $\mathfrak{c}$ 来表示 $\aleph_1$，因为这是很特别的一个基数：实数集合的基数。

4. 基数的运算

定理 2　

　　 基数计算第一法则 对于集合 $B\subseteq A$，有 $ \left\lvert B \right\rvert \leq \left\lvert A \right\rvert $。

定理 3　

　　 基数计算第二法则 对于基数 $a, b, c$，如果 $a\leq b\leq c$ 且 $a=c$，那么 $a=b=c$。

　　然后，我不加证明地给出第三法则，请用自行用 Venn 图加以理解：

定理 4　

　　 基数计算第三法则 对于集合 $A, B$，有 $ \left\lvert A\cup B \right\rvert + \left\lvert A\cap B \right\rvert = \left\lvert A \right\rvert + \left\lvert B \right\rvert $。

　　为了继续描述接下来的计算法则，在这里给出一个定义：

定义 6　

　　对于集合 $A, B$，记 $ \left\lvert B^A \right\rvert = \left\lvert B \right\rvert ^{ \left\lvert A \right\rvert }$，以及 $ \left\lvert A\times B \right\rvert = \left\lvert A \right\rvert \times \left\lvert B \right\rvert = \left\lvert A \right\rvert \left\lvert B \right\rvert $。

　　对于有限的基数，以上法则和定义都是众所周知的了。我们要研究的是无穷基数的运算。因此以下计算法则都是描述无穷基数的运算的。以下不加证明地给出一些无穷基数的计算法则，对证明感兴趣的读者可以参阅《集合论基础》 [1]。

定理 5　

　　 基数计算第四法则 对于无穷基数 $\mathfrak{a}, \mathfrak{b}$，如果 $\mathfrak{a}\geq\mathfrak{b}$，那么 $\mathfrak{a}\times\mathfrak{b}=\mathfrak{a}$。

定理 6　

　　 基数计算第五法则 对于无穷基数 $\mathfrak{a}, \mathfrak{b}$，如果 $\mathfrak{a}>\mathfrak{b}$，那么 $\mathfrak{a}^\mathfrak{b}=\mathfrak{a}$；否则，$\mathfrak{a}^\mathfrak{b}=2^\mathfrak{b}$。

　　利用这些计算法则，我们可以讨论无穷基数之间的一些运算规律了，特别是不可数无穷基数们。这就是逻辑和智慧的力量，以有限的生涯来理解无限的存在。

1. ^ 结果当然不会有变化，但 “为什么” 似乎没那么容易回答。当然，如果你熟悉 ZFC 公理的推演或者熟悉了本节的内容，应该可以给出严谨的解释，不过我们目前可以默认这是成立的。
2. ^ 有的理论里也会定义 “无限” 这一存在，比如复平面的无穷远点，但那个实际上是拓扑空间的一点紧化的结果。在打基础的阶段，应该扎实理解 “无限” 是一种性质而不是一个存在，比如此处，无限集合是指具有 “拿走有限多元素后都还有剩余” 这一性质的集合。对这一基本概念理解扎实以后，才能更准确地涉及 “无穷” 的各种概念，包括 “无穷远点” 和 “一点紧化” 等。
3. ^ 检查一下，每个正偶数都被映射到了（满射），并且只被映射了一次（单射）。
4. ^ 如果 $A$ 到 $B$ 存在一个单射，那么反过来 $B$ 到 $A$ 一定存在一个满射。方法很简单，如果 $f:A\rightarrow B$ 是单射，那么可以构造 $g:B\rightarrow A$，使得对于 $b\in f(A)$，有 $g(b)=f^{-1}(b)$，然后随便挑一个 $a\in A$，让剩下的所有 $B-f(A)$ 中的元素都映射到 $a$ 上，这样 $g$ 就是满射了。同样地，如果 $A$ 到 $B$ 存在一个满射，那么 $B$ 到 $A$ 存在一个单射；不过对于任意集合，这个单射的存在性依赖于选择公理。

[1] ^ A. Shen, N. K. Vereshchagin, 陈光还译，集合论基础，高等教育出版社，2013年