不可数集

说明

我们这一节介绍不可数集的概念，并给出一些具体例子，此外我们将证明 Schroeder-Bernstein 定理。

不可数集

如果集合 $A$ 是一个无穷集，且它不是可数集，则称 $A$ 是一个不可数集。

这代表不可数集是比可数集“大”很多的存在，存不存在这样的集合呢？

我们知道对于有限集来说，若 $| A | = n$ ，那么 $| P (A) | = 2^{n}$ ，其中 $P (A)$ 是 $A$ 的幂集，它是 $A$ 的所有子集构成的一个集合（我们也把集合的集合叫做集族）。也就是说有限集的幂集永远比它本身“大”，这能否推广到无穷集上呢？

我们考虑正整数集的幂集 $P (N)$ （为了方便以后我正整数集和自然数集都用 $N$ ，大家根据具体情况确定）

P (N) = {A ∣ A \subset N}

假设它是可数集，那么我们可以把 $P (N)$ 中的元素排乘一排

P (N) = {A_{1}, A_{2}, . . . ∣ A_{k} \subset N}

我们还是把这些 $A_{k}$ 的元素都列出来

\begin{array}{cccccc} A_{1} & a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & . . . \\ A_{2} & a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & . . . \\ A_{3} & a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & . . . \\ A_{4} & a_{41} & a_{42} & a_{43} & a_{44} & a_{45} & . . . \\ A_{5} & a_{51} & a_{52} & a_{53} & a_{54} & a_{55} & . . . \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{array}

其中 $a_{i j}$ 都是正整数数，每一行都从大到小排列，我们可以这么记

\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 \\ A_{1} & a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & . . . \\ A_{2} & a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & . . . \\ A_{3} & a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & . . . \\ A_{4} & a_{41} & a_{42} & a_{43} & a_{44} & a_{45} & . . . \\ A_{5} & a_{51} & a_{52} & a_{53} & a_{54} & a_{55} & . . . \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{array}

其中 $a_{i j}$ 等于 1 或者 0，分别表示正整数 $j$ 在或不在集合 $A i$ 中。（这个记法是高中时候，老师证明上面那个幂集元素个数是 $2^{n}$ 用的。）

我们说了，可数集就是能把集合里的元素排成一排，那么不可数集就是不管怎么排，都排不完，也就是有遗漏，现在我们要做的就是找到一个遗漏的 $E \in P (N)$ 它不在这些 $A_{k}$ 中。

我们看一个情况：

\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 \\ A_{1} & 1 & 0 & 1 & 1 & 1 & . . . \\ A_{2} & 0 & 0 & 1 & 0 & 1 & . . . \\ A_{3} & 1 & 0 & 1 & 1 & 0 & . . . \\ A_{4} & 0 & 0 & 1 & 1 & 1 & . . . \\ A_{5} & 1 & 0 & 1 & 1 & 0 & . . . \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{array} (1)

我们刚刚说了这表示 $1 \in A_{1}, 2 \notin A_{1}, 3 \in A_{1}, . . .$ 这其实也是构建了一个双射，把 $A_{k}$ 映射成了一串只有 0 和 1的序列（无限长），我们只要构造一串 0 和 1 的序列，让它和这些 $A_{k}$ 都有不同就行了，我们可以让

B = {b_{1}, b_{2}, b_{3}, . . .}

其中 $b_{k}$ 和 $a_{k k}$ 取不同的数，如果 $a_{k k} = 0$ ，那么 $b_{k} = 1$ ，反则反之。这样这一串序列自然和矩阵（1）对角线上的元素完全相反，也意味着它和所有的 $A_{k}$ 在第 $k$ 位上都是不同的。

不管我们怎么排列 $P (N)$ 成一些 $A_{k}$ ，我们都能用上面的方法构造出一个不在这个排列中的集合 $E \in P (N)$ ，这就说明了 $P (N)$ 是不可列集（不可数集）。

这个方法貌似是 Cantor 提出来的，我们管它叫对角线方法。
熟悉二进制的同学会发现，这个证明告诉了我们实数是不可数的，大家可以自己思考一下。

实数和复数

实数

我们证明实数是不可数集。

实数

实数是不可数集。

我们知道有理数是在实数中稠密的，但是有理数集是可数的，这让我们思考实数比有理数多了哪些结构，我们会考虑实数的确界原理以及和它等价的几个定理。

闭区间套定理

设 $I_{1} \supset I_{2} \supset I_{3} \supset . . .$ 是一个闭区间序列，且任意 $I_{k} \neq \emptyset$ ，则这些闭区间的交集

⋂_{k = 1}^{\infty} I_{k} \neq \emptyset

如果实数是可数的，我们可以把所有实数排成一排： $r_{1}, r_{2}, r_{3}, . . .$ ，我们一定可以这样选取一个非空闭区间序列： $I_{k + 1} \subset I_{k}, r_{k} \notin I_{k}$ 。这时候我们对任一实数 $r_{n}$ 有

r_{n} \notin I_{n} \subset ⋂_{k = 1}^{\infty} I_{k}

所以这个交集应该是空集，这显然和闭区间套定理矛盾了。

因此实数是不可数的，那么复数呢？

不可数集合的幂集

我们首先有一个问题。
所有可数集，我们知道是等势的。那么任意两个不可数集之间是否存在双射呢？

我们刚刚用正整数集的幂集构造了一个比自己“大”的集合，不可数集的幂集是否也比自己大？如果是这样那我们就知道没有基数最大的集合。

不可数集的幂集

若 $A$ 是不可数集， $A$ 与 $P (A)$ 不等势。

设 $A$ 是任意一个不可数集合， $P (A)$ 是它的幂集，如果 $f : A \to P (A)$ 是一个双射，我们就有

P (A) = {f (a) ∣ a \in A}

我们回忆一下之前的对角线方法：我们先假设存在一个双射 $g : N \to P (N)$ ，于是就有

P (N) = {g (n) ∣ n \in N}

然后我们构造了一个这样的自然数的子集 $B$ ：如果 $n \in g (n)$ ，就让 $n \notin B$ ；如果 $n \notin g (n)$ ，就让 $n \in B$ 。
这个方法当然可以构造一个 $A$ 的子集 $E$ ：对任意 $a \in A$ ，如果 $a \in f (a)$ ，就让 $n a \notin E$ ；如果 $a \notin f (a)$ ，就让 $a \in E$ 。显然这和所有的 $f (a)$ 都不同，因此不存在从 $A$ 到 $P (A)$ 的双射（更准确地，不存在满射）。

所以并不是所有不可数集都是等势的，现在我们知道实数集 $R$ 是不可数的，那么实数集作为复数集 $C$ 的子集， $C$ 肯定是不可数的，但是它们两个等势吗？

复数

复数集

复数集和实数集等势。

我们知道复数集可以看出实数集和实数集的笛卡尔积

C = {(a, b) ∣ a, b \in R} = R \times R

可以构造这样的映射 $f$ ：对于任意的 $r \in (0, 1)$ ，写成无穷小数

r = 0. a_{1} b_{1} a_{2} b_{2} a_{3} b_{3} . . .

令 $f (r) = (a, b)$ ，其中

a = 0. a_{1} a_{2} a_{3} . . .

b = 0. b_{1} b_{2} b_{3} . . .

这就构成了一个 $(0, 1)$ 到 $(0, 1) \times (0, 1)$ 的映射。

但是检查之后我们发现有一些问题，首先是对于有限位小数，比如 0.1，存在两种无穷小数表示

0.1 = 0.1000 . . . = 0.0999 . . .

所以不管我们规定这种小数选择哪种表示， $f (0.1)$ 不可能同时取到

z_{1} = (0.1, 0), z_{2} = (0.099 . . ., 0.999 . . .)

不过好消息是这只存在于有限位小数，所以我们可以规定有限位小数只取第一种表达（后面全是 0 ），这样我们就只遗漏了可数个复数也就是说 $(0, 1) \times (0, 1) - f [(0, 1)]$ 是一个可数集。
我们知道如果 $E$ 是一个不可数集， $F$ 是它的一个可数子集，那么 $E - F$ 和 $E$ 还是等势的。所以 $f [(0, 1)]$ 和 $(0, 1) \times (0, 1)$ 是等势的，所以我们可以建立 $(0, 1)$ 到 $(0, 1) \times (0, 1)$ 的满射。
还记得我们之前说过吗？如果 $A$ 到 $B$ 有单射， $B$ 到 $A$ 有单射，那么 $A$ 到 $B$ 有双射。这也是我们待会儿要证明的定理。
综上我们可以证明 $(0, 1)$ 和 $(0, 1) \times (0, 1)$ 等势，这就可以说明 $R$ 和 $C$ 是等势的。（怎么说明？）

Schroeder-Bernstein 定理

设 $A, B$ 是非空集合，如果 $A$ 到 $B$ 存在单射， $B$ 到 $A$ 存在单射，那么 $A$ 到 $B$ 存在双射。

设 $f : A \to B$ 与 $g : B \to A$ 都是单射，我们希望利用它们构造一个从 $A$ 到 $B$ 的双射 $F$ 。我们知道单射在任意子集上的限制还是单射，所以我们希望把 $A$ 分成两个恰当的区域

A = A_{1} ⋃ A_{2}

使得我们可以定义映射

F (x) = {\begin{cases} f (x), & x \in A_{1}; \\ g^{- 1} (x), & x \in A_{2} . \end{cases}

是一个双射。

我们看一下这要求我们如何划分 $A$ ：(i) 首先要使 $g^{- 1} (x)$ 在 $A_{2}$ 上有意义，所以我们要求 $A_{2} \subset g (B)$ ，记 $A_{0} = A - g (B)$ ，就是说 $A_{0} \subset A_{1}$ 。

(ii) 又需要 $F$ 是单射，所以要求对任意的 $x \in A_{1}, y \in A_{2}$ ，有 $f (x) \neq g^{- 1} (y)$ ，这等价于说 $g (f (x)) \neq y$ 。我们不妨记 $h = g \circ f$ ，这其实是说 $h (A_{1}) \cap A_{2} = \emptyset$ ，就是 $h (A_{1}) \subset A_{1}$ ；

(iii) 还需要 $F$ 是满射，所以 $B = f (A_{1}) \cup g^{- 1} (A_{2})$ ，等价于 $g (B) = h (A_{1}) \cup A_{2}$ ，根据 (i) 我们知道这就是说 $A - g (B) = A_{1} - h (A_{1})$ ，就是 $A_{1} = h (A_{1}) \cup A_{0}$ 。

我们考虑 $A$ 的子集族 $F = {E \subset A | h (E) \cup A_{0} \subset E}$ ，这是非空的因为 $A \in F$ 。

不难证明如下几个命题：
(1) $\forall E \in F, h (E) \cup A_{0} \in F$ ;
(2) $\underset{E \in F}{\cap} E \in F$ ;
(3) 令 $E_{0} = \underset{E \in F}{\cap} E$ ，则 $E_{0} = h (E_{0}) \cup A_{0}$ 。
可见 $E_{0}$ 就是我们要找的 $A_{1}$ 。