可数集

说明

我们将介绍可数集，不可数集的概念，并研究一些具体的常见集合，比如 $Q$ ， $R$ ， $C$ 。
预备知识：笛卡尔积，映射，集合的交集，并集。

可数集

我们要怎么比较两个集合的所含元素的多少？

对于有限集合，我们只需要数元素的个数，再比较大小即可，但是无限集合之间是否也存在一种比较好的手段，可以比较元素的“多少”呢？
我们发现可以通过映射来定义两个集合谁更“多”一些：如果集合 $A$ 到集合 $B$ 存在单射，就说 $B$ 的“基数”大于等于 $A$ 的“基数”，写作 $| B | \geq | A |$ 。如果集合 $A$ 到集合 $B$ 存在双射，就说它们基数相等，写作 $| A | = | B |$ 。

当谈论的集合是有限集时，集合的基数就是元素的个数；然而当我们谈论无穷集时，基数不是一个确切的数，我们甚至不知道 “ $| A | \leq | B |, | A | \geq | B |$ ” 是否能推出 “ $| A | = | B |$ ”，即如果 $A$ 到 $B$ 有单射， $B$ 到 $A$ 也有单射，这两个集合是否存在双射。

这个问题的答案是一定存在的，我们可以先当定理用着，之后再证明。

总之我们现在有了集合的基数的概念，也就是无穷集的元素的多少，对于初学者来说这将会是一件吃惊的事情：有些无穷集真的比另一些无穷集“多”得多，而有些无穷集虽然在范围上是另一些无穷集的真子集，但是它们一样“多”。

定义

可数集

如果集合 $E$ 可以和正整数集建立双射，则称集合 $E$ 可数。

有些书上把有限集也称为可数集。因为有限集一般是比较简单的情况，所以我们在后面可能不单独拎出来讨论。

整数集

我们会发现整数是和正整数“一样多”的。

整数集

全体整数构成的集合是可数集。

事实上， $A$ 是可数集，按照定义就是说，存在一个双射 $f : N_{+} \to A$ ，使得 $A = {f (n) ∣ n = 1, 2. . .}$ 。

也就是说如果 $A$ 中的元素可以列成一排： $a_{1}, a_{2}, a_{3}, . . .$ ，（要有起点），那么我们就有 $f (n) = a_{n}$ 是满足条件的双射。这是对可数集的一个直观的解释，在很多教材上我们管可数集叫做“可列集”。

我们很容易想到怎么把全体整数的集合列成一排： $0, 1, - 1, 2, - 2, . . .$ 。规范点说，我们构造了一个从正整数集到整数集的双射

f (n) = (- 1)^{n} [\frac{n}{2}]

其中 $[.]$ 表示取整函数。

我们很容易能想到没有比可数集更“小”的无穷集：假设 $A$ 是一个无穷集，我们取 $a_{1} \in A$ ，又当 $a_{n} \in A$ 确定后，取 $a_{n + 1} \in A - {f (1), f (2), . . ., f (n)}$ 。因为 $A$ 是无穷集，所以 $A - {f (1), f (2), . . ., f (n)}$ 总是非空的。
但是我们可能比较难想到一个比可数集“大‘的集合，什么样的集合是用一条无限延申的序列也列不完的呢？

可数集的性质

我们先学习一些可数集的性质，这些如果你无聊自己琢磨可数集的概念，是比较容易想到的。

可数集的并集

设 $F$ 是一组集合，里面有可数个集合，我们写出来就是

F = {F_{1}, F_{2}, F_{3}, . . .}

任意 $F_{n} \in F$ 都是可数集，那么这些（可数多个）可数集的并集

⋃_{n = 1}^{\infty} F_{n}

还是可数集。

我们先看两个更简单的

有限个可数集的并集

$F_{1}, F_{2}, . . ., F_{m}$ 都是可数集，那么它们的并集

⋃_{n = 1}^{m} F_{n}

还是可数集。

类似于我们说明全体整数集是可数集，我们先写出来

F_{1} = {a_{1}, a_{2}, a_{3}, . . .}

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

那么 $F_{1} \cup F_{2} = {a_{1}, b_{1}, a_{2}, b_{2}, . . .}$ 显然是可数集。（这就是我们刚刚证明全体整数集是可数集的方法。）
现在我们知道了两个可数集的并集是可数集，那么 $F_{1} \cup F_{2} \cup F_{3} = (F_{1} \cup F_{2}) \cup F_{3}$ 也可以视作两个可数集 $F_{1} \cup F_{2}$ 和 $F_{3}$ 的并集所以是可数的，这么一来我们可以数学归纳证明任意有限个可数集的并集是可数的。

可数个有限集的并集

设 $F$ 是一组集合，里面有可数个集合，我们写出来就是

F = {F_{1}, F_{2}, F_{3}, . . .}

任意 $F_{n} \in F$ 都是有限集集，那么这些（可数多个）可数集的并集

⋃_{n = 1}^{\infty} F_{n}

还是可数集。

这个证明更简单了，先列完 $F_{1}$ 的元素（有限个），再列 $F_{2}$ 的元素，以此类推，可以把并集的元素列出来。

回到可数个可数集的情况。我们也试着把它们的元素列出来，我们似乎需要一个无限延申的矩阵：

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

我们应该怎么证明这些 $a_{i j}$ 是可数的呢？

第一种方法，我们还是找一个方式把它们排列出来，大家应该玩过贪吃蛇吧，如果我们把这些 $a_{i j}$ 想象成食物，你要操控贪吃蛇从 $a_{11}$ 出发，不回头的把所有食物吃完，你会怎么吃？

\begin{matrix} a_{11} & \to a_{12} & a_{13} & \to a_{14} & . . . \\ ↓ & ↑ \\ a_{21} & \leftarrow a_{22} & a_{23} & a_{24} & . . . \\ ↓ & ↑ \\ a_{31} & \to a_{32} & \to a_{33} & a_{34} & . . . \\ a_{41} & a_{42} & a_{43} & a_{44} & . . . \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

我们发现顺着箭头，可以把这些 $a_{i j}$ 给排成一列，因此它们是可数的。

第二种方法，我们看看能不能把这个矩阵，做一些分割（分块），把它变成我们前面证明的两种更简单的情形。
把它变成有限个可数集貌似行不通，但是能不能把它变成可数个有限集呢？

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

我们把 $a_{i j}, i \leq 4, j \leq 4$ 的区域框起来，这是一个正方形，我们管它叫 $A_{4}$ ，类似的我们可以把 $a_{i j}, i \leq 5, j \leq 5$ 的区域叫做 $A_{5}$ ，我们就得到了一个增长的正方形序列，这些（显然是可数个）正方形的并集就是整个矩阵，而这些正方形每一个都是有限的。这就把这个矩阵变成了可数个有限集的并集，根据我们前文的证明它是可数的。

可数集的笛卡尔积

运用同样的方法我们可以证明，有限个可数集的笛卡尔积也是一个可数集。

可数集的笛卡尔积

若 $A, B$ 是可数集，则它们的笛卡尔积 $A \times B$ 也是可数集。

复习一下笛卡尔积的概念。

笛卡尔积

若 $A, B$ 是非空集合，笛卡尔积 $A \times B$ 是这样一个集合：

A \times B = {(a, b) ∣ a \in A, b \in B}

其中 $(a, b)$ 是有序对。

现在我们有可数集

A = {a_{1}, a_{2}, a_{3}, . . .}

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

所以

A \times B = {(a_{i}, b_{j}) ∣ i, j \in N_{+}}

我们记 $c_{i j} = (a_{i}, b_{j})$ ，那么又可以把所有元素列成一个无限延申的矩阵，就回归到上文的证明了。

据此我们可以证明有理数集是可数的。

有理数集

有理数集 $Q$ 是可数的。

我们证明全体正有理数的集合是可数的。
任取 $q \in Q$ ，把 $q$ 写成既约分数的形式（这是唯一的） $q = \frac{m}{n}$ ，我们可以建立一个映射 $f : Q \to N \times N$ 如下：

f (q) = f (\frac{m}{n}) = (m, n)

我们知道这是一个单射所以 $Q$ 和 $N \times N$ 的一个无穷子集等势（存在双射），又知道 $N \times N$ 是可数集，可数集的无穷子集显然也是可数集（为什么？），所以 $Q$ 也是可数集。

（如果 $A$ 和 $B$ 等势， $B$ 和 $C$ 等势，那么 $A$ 和 $C$ 等势。所以如果一个集合和一个可数集等势，那它就和正整数集等势所以可数）

我们可能觉得和自然数比起来，有理数多得多，毕竟我们在实数那一节证明了有理数的稠密性，任何两个实数之间都存在有理数，而自然数是很”稀疏“的，但是它们竟然可以一一对应。

我们可以想一想哪些集合是不可数的，也就是比自然数”多得多“？

下一篇
不可数集