集合的等价、基数

符号设定

对于以下的符号和术语，书本和笔记有差异，需要注意：

书本符号/术语	笔记符号/术语
$\mathbf{Q}$	$\mathbb{Q}$
$\overline{\overline{A}}$	$ \| A \| $
完全一一映射	双射
一一映射	单射

集合等价

定义：集合等价

若 $A$ 和 $B$ 集合间存在一个双射，那么就称 $A$ 和 $B$ 等价，记为 $A\sim B$ .

这个关系是一个等价关系，根据抽象代数里面关系的性质很容易导出如下的结论：

定理：等价关系性质

（自反性）对任何集合 $A$ 有 $A\sim A$ .
（交换性）若集合 $A\sim B$ ，则 $B\sim A$ .
（传递性）若 $A\sim B$ 且 $B\sim C$ ，那么 $A\sim C$ .

对于两两不相交集合的并，它们之间的等价关系也是简单的，我们不加证明地给出如下的定理：

定理：不相交集合并的等价关系

设 $\left\lbrace A_\lambda: \lambda\in \Lambda \right\rbrace$ 是一个两两不相交的集合族，$\left\lbrace B_\lambda: \lambda\in \Lambda \right\rbrace$ 也是一个两两不相交的集合族，如果对于任意的 $\lambda \in \Lambda$ 有 $A_\lambda \sim B_\lambda$ ，则
$$ \bigcup\left\lbrace A_\lambda: \lambda\in \Lambda \right\rbrace \sim \bigcup \left\lbrace B_\lambda : \lambda\in \Lambda \right\rbrace$$

有限集、无限集、可数集

下面利用等价的语言来说明集合的有限、无限和可数：
- 如果存在正整数 $n$ 使得集合 $A \sim \left\lbrace 1,2,\cdots,n \right\rbrace$ ，就称 $A$ 为有限集，反之为无限集；
- 特别地，如果 $A\sim \mathbb{N}$ ，就称 $A$ 为可数集.

定理：可数集相关的基本性质

任意无限集必含一个可数子集；
可数集的任意一个无限子集是可数集；
至多可数个可数集的并是可数集；

这里只强调一下最后一个命题，最后一个命题实质上教材上的方法就是对角线方法，只不过没有那么直观，实质上写为如下的数阵的形式：

\[ \begin{array}{cccc} a_1^{(1)} & a_2^{(1)} & a_3^{(1)} &\cdots \\ a_1^{(2)} & a_2^{(2)} & a_3^{(2)} & \cdots \\ a_1^{(3)} & a_2^{(3)} & a_3^{(3)} & \cdots \end{array} \]

数的方法就是走“之”字形，这也就是对角线方法，用同样的方法可以证明 $\mathbb{Q}$ 可数（虽然但是这个命题本身就要更强一些）. $\square$

定理：无限集 + 可数集“个数”不变

设 $A$ 为无限集，$B$ 为至多可数集，则 $A\sim A\cup B$ .

利用上述可数集的并的结论，考虑 $A$ 的可数子集 $A_1$ ，此时有

$A_1\sim A_1\cup B$ （集合对应等价）
$(A-A_1)\cap A_1 = \varnothing$ ，$(A-A_1)\cap (A_1\cup B) = \varnothing$ . （两两不交）

那么有

\[ A = (A-A_1)\cup A_1 \sim (A-A_1)\cup (A_1\cup B) = A\cup B \]

从而命题成立. $\square$

注意

需要注意的是，这里的无限集没有限制可数和不可数，所以在后续也会经常应用到.

连续统势

不可数集与连续统势

既然有可数集，相应地有不可数集，我们来看 $[0,1]$ 区间：

若 $[0,1]$ 可数，则表示为如下的形式：

\[ \left\lbrace a_1,a_2,\cdots,a_n,\cdots \right\rbrace \]

取闭区间 $I_1$，使得 $a_1 \not\in I_1\subset [0,1]$ ，那么可以取 $I_2\subset I_1$ 使得 $a_2\not \in I_2$ ，以此类推可得 $a_n\not\in I_n$ ，并且要求 $\left\lbrace I_n \right\rbrace$ 单调减（更好的方法就是直接对半分）.

根据闭区间套定理，我们可以得到 $\xi\in \prod\limits_{i=1}^\infty I_i$ ，对于任意的 $n$ 有 $\xi \not \in I_n$ ，因此 $\xi \neq a_n$ ，这和 $\xi \in [0,1]$ 是矛盾的. $\square$

我们把和 $[0,1]$ 等价的集合成为有连续统势，如果 $A$ 具有连续统势，记为 $|A| = c$ .

现在我们考虑能否寻找到一个对应关系使得我们能研究它的结构.

$n$ 元数列

对于每一个 $[0,1]$ 当中的数，我们总能将其写为一个无限小数：

\[ a = 0.a_1a_2a_3\cdots a_n\cdots \]

如果本来为有限的小数，只需要在后续加无穷多个 $0$ 即可.

那么此时我们就能写为：

\[ a = \sum\limits_{k=1}^\infty \frac{a_k}{10^k} \]

我们就建立了一个一一对应关系，也就是

\[ f: a\in [0,1] \to \left\lbrace a_1,a_2,\cdots,a_n,\cdots \right\rbrace \]

其中右侧的 $a_k\in \left\lbrace 0,1,\cdots,9 \right\rbrace$ .

我们给出如下的定义：

定义：$n$ 元数列

若数列 $\left\lbrace a_k \right\rbrace_{k\geqslant 1}$ 的项仅仅由 $0,1,\cdots,n-1$ 这 $n$ 个数构成，则称该数列为一个 $n$ 元数列.

如果仅有有限项不为 $0$ ，那么称为有限 $n$ 元数列.
反之，则为无限 $n$ 元数列.

我们刚刚实质上已经说明了 $10$ 元数列的全体与 $[0,1]$ 是等价的，也就是有连续统势. 那么对于 $n (n\geqslant 2)$ 元是不是也一致？

事实上考虑下面的式子即可：

\[ a = \sum\limits_{k=1}^\infty \dfrac{a_k}{n^k} \]

严格证明参照书本，基本就是有限项夹逼，从第一位开始得到：

\[ \sum\limits_{i=1}^m \frac{k_i-1}{n^i} < x \leqslant \sum\limits_{i=1}^{m-1}\frac{k_i-1}{n^i} +\frac{k_m}{n^m} \]

取极限即可.

提示：更为直观的理解方式

一个最直观的理解方式，就是直接看作 $n$ 进制下实数的小数表示. $n=10$ 就是我们最熟悉的十进制.

首先根据无限集并可数集的“个数”不变，可以知道 $[0,1]\sim (0,1)$ .
同时，在合适的双射下，我们能发现 $\mathbb{R}\sim (0,1)$ ，例如双射 $f(x) = \dfrac{1}{1+ \mathrm{e}^{-x}}$ . 因此 $\mathbb{R}$ 也具有连续统势.

连续统势集合的直积

我们因而有推广的想法：$\mathbb{R}^n$ 是否具有连续统势？我们可以借助先前的 $n$ 元数列来印证这一点. 考虑到 $\mathbb{R}^2 = \mathbb{R}\times \mathbb{R}$ ，不妨证明下面这个更强的命题：

定理：可数个连续统势的直积仍有连续统势

至多可数个有连续统势的集合的直积具有连续统势.

为简单起见，考虑二元数列，我们设 $X_n$ 为二元数列的全体，其直积可以写为

\[ X = \prod_{n=1}^\infty X_n \]

那么对于 $x\in X$ ，可以写为

\[ x = (x_1,x_2,\cdots,x_n,\cdots) \]

其中 $x_i$ 为一个二元数列，设为

\[ x_i = (x_1^{(i)},x_2^{(i)},\cdots,x_n^{(i)},\cdots) \]

因此我们考虑将其映射为一个新的二元数列，此时我们仍然套用对角线方法：

\[ \begin{array}{cccc} x_1^{(1)} & x_2^{(1)} & x_3^{(1)} &\cdots \\ x_1^{(2)} & x_2^{(2)} & x_3^{(2)} & \cdots \\ x_1^{(3)} & x_2^{(3)} & x_3^{(3)} & \cdots \end{array} \]

利用对角线方法走“之”字形可以得到

\[ f(x) = \left\lbrace x_1^{(1)},x_2^{(1)},x_1^{(2)},x_1^{(3)},x^{(2)}_2,\cdots \right\rbrace \]

首先，$f$ 显然为单射，而对于已经确定的一个二元数列，我们将其沿之字形排好，同样能得到一个对应的 $x$ ，从而 $f$ 为双射. $\square$

根据这个命题，可以判断：

$\mathbb{R}^n$ 都是具有连续统势的.
实数列的全体是由可数个 $\mathbb{R}$ 直积得到的，因此实数列全体也是具有连续统势的.

解题提示

这个命题提供了一个构造映射的方法，这也是第一章习题 T22 (ii) 的灵感来源.

基数的比较

集合基数的夹逼

定理：集合等价的夹逼

设 $A_0,A_1,A_2$ 是三个集合，满足
$$ A_2 \subset A_1 \subset A_0 $$
若 $A_0 \sim A_2$ ，则 $A_0\sim A_1$.

详细证明参考教材. （注意其中构造集合列的方法） $\square$

集合基数的偏序关系与 Bernstein 定理

下面引入集合基数的比较符号 $\leqslant$ ，一般而言，如果 $|A|\leqslant|B|$ ，就说明 $A$ 与 $B$ 的一个子集等价. 那么此时集合基数之间的比较具有什么性质就需要我们进行思考：

定理：集合基数比较为偏序关系

集合基数的比较 $\leqslant$ 为偏序关系，也就是说满足如下性质：

$\forall A, |A|\leqslant |A|$ .
$|A|\leqslant |B|$ 且 $|B| \leqslant |C|$ ，则 $|A|\leqslant |C|$ .
若 $|A|\leqslant |B|$ 且 $|B|\leqslant |A|$ ，则 $|A|=|B|$ . (Bernstein 定理)

其中最后一个定理最为重要，因为它给了我们一个简单的方法来证明集合基数相等. （类似于 $A \subset B$ 和 $B \subset A$ 能证明 $A=B$）.

证明：
(1)
由于 $A \sim A$ 显然，从而 $|A|\leqslant |A|$ .

(2)
设 $A\sim B_1$ ，其中 $B_1 \subset B$ ，$B\sim C_1$ ，$C_1\subset C$ ，那么考虑集合对映射的限制即可得到 $A\sim C_2$ ，$C_2 \subset C_1 \subset C$ .

(3) Bernstein 定理
由于 $|A|\leqslant |B|$ ，有

\[ A\sim B_1 , B_1 \subset B \]

由于 $|B|\leqslant |A|$ 有

\[ B \sim A_1 , A_1 \subset A \]

那么此时由于 $B_1 \subset B$ 有

\[ B_1 \sim A_2 , A_2 \subset A_1 \]

故 $A\sim A_2$ ，由于 $A_2 \subset A_1 \subset A$ ，此时 $A\sim A_1 \sim B$ . 故 $|A| = |B|$ . $\square$

对于 $\leqslant$ ，如果已经确定 $A$ 和 $B$ 不等价且 $|A|\leqslant |B|$ ，那么就记为 $|A|<|B|$ .

对于集合 $A$ ，如果 $|A| = n$ ，那么建立在 $A$ 上的集族 $\mathcal{A}$ 满足 $|\mathcal{A}| = 2^n$ ，对于基数 $\mu$，相应集族的基数同样记为 $2^ \mu$ ，我们下面需要考虑的是：是否恒有 $\mu< 2^\mu$ ？

定理：不存在基数最大的集

\[ \mu< 2^\mu \]

首先对于 $\mathcal{A}$ ，考虑子集 $\left\lbrace \left\lbrace x \right\rbrace : x\in A\right\rbrace$ 即可证明 $A$ 与 $\mathcal{A}$ 的子集等价，从而 $|A|\leqslant \mathcal{A}$ . 下面证明两者不等价.

反证法：假设等价，则存在 $f: A \to \mathcal{A}$ 为双射，那么此时 $x\in A$ 时， $f(x)\subset A$ .

令

\[ A^* = \left\lbrace x\in A: x\not\in f(x) \right\rbrace \]

它的存在性是怎么保证的？

事实上，这个集合的存在性是由公理集合论保证的.

由于 $A^* \subset A$ ，那么由于 $f$ 为双摄，存在 $x^*$ 使得 $f(x^*) = A^*$ ，现在进行讨论：

若 $x^*\in A^*$ ，那么 $x^* \not \in f(x^*) = A^*$ ，矛盾；
若 $x^*\not \in A^*$ ，那么 $x^* \in f(x^*) = A^*$ ，也矛盾；
因此这就说明 $A$ 和 $\mathcal{A}$ 不可能等价，从而证毕. $\square$