第7章
可数集与不可数集

谈论无穷集合的大小有意义吗？回答是肯定的。但是，我们必须要为一些违反直觉的结果做好准备，诸如上一章中提到的偶数集与所有整数集是大小相同的。

让我们做一个模拟。假设你经营一家拥有67间客房的旅馆 。有一天，旅馆都是空房并且有67位客人想要入住。如果你给每位客人发一把房间钥匙，那么当你给最后一位客人钥匙时刚好发完所有的钥匙。如果钥匙是从0到66的顺序编号的，那么你可以告诉客人去钥匙上数字标示的房间。

现在旅馆已经住满了。第68个来找房间的客人会很不走运。

接下来想象一下，你现在经营的是一家拥有无穷多房间的旅馆，编号为0,1,2,3,…。如果一开始旅馆是空的，同时出现了无穷多的客人 p ₀ , p ₁ ,…，你可以再次给每位客人一把带编号的钥匙，并指示他们去钥匙上数字标识的房间。

现在旅馆住满了，每个房间都有客人入住。假设又新来了一个旅行者，并请求一个房间。如果你说“你可以住 n 号房间”，那么对于任何特定的 n 号房间，新客人都会发现这个房间已经被占用了。然而，在无穷多房间的旅馆里，总是可以多挤一个人的。

告诉入住的每一位客人向大号方向移动一个房间，那么0号房间的客人移动到1号房间，同时被取代的1号房间的客人移动到2号房间，以此类推（见图7.1）。这样新来的旅行者就可以入住0号房间，大家都开心了。如果再新来五个客人，或者十个客人，或者 k （任意有穷数）个客人，可以用同样的办法，即让每个客人向大号方向移动 k 个房间，这样可以将前 k 个房间空出来给新来的客人。

再多做一些。想象一下你有两个无限大的旅馆 G 和 J ，房间编号为非负整数，并且都住满了。现在假设你必须把每个客人都搬到另一家旅馆 H 中，那里的房间编号也是0,1,2,…。你如何在 H 旅馆为来自旅馆 G 和 J 的所有客人安排房间？

告诉 G 旅馆的入住者将他们的房间号加倍（乘以2），然后入住到 H 旅馆的该号房间，这样 G 0房间的客人（指 G 旅馆的0号房间）将入住 H 0， G 1房间的客人将入住 H 2， G 2房间的客人将入住 H 4，以此类推（见图7.2）。现在 H 旅馆所有偶数房间已经住满了，所有奇数房间是空的，于是你可以用 J 旅馆的所有客人来填充奇数房间。 J 旅馆的客人将房间号加倍后再加1，然后搬到 H 旅馆相应的房间： J 0房间的客人将搬到 H 1， J 1房间的客人将搬到 H 3， J 2房间的客人将搬到 H 5，以此类推。可以用类似的方法合并三个或者 k （任意有穷数）个旅馆的客人到一个旅馆。

这些技巧都基于这样的事实，即自然数集合的真子集与所有自然数的集合之间存在双射，就像图6.10中的ℤ和E之间的双射一样。例如，在刚刚的场景中，我们将 N 划分为两个不相交的真子集（偶数和奇数），并在 N 和这些子集中的每一个之间构造双射，第一个是 fG （ n ）=2 n ，第二个是 fJ （ n ）=2 n +1。然后，我们将 G 旅馆 n 号房间的客人移入 H 旅馆的 fG （ n ）号房间，将 J 旅馆 n 号房间的客人移至 H 旅馆的 fJ （ n ）号房间。 fG [ℕ]的像是偶数集合， fJ [ℕ]的像是奇数集合，因此有 fG [ℕ]∩ fJ [ℕ]=∅、 fG [ℕ]∪ fJ [ℕ]=ℕ。每个人都没有重复预订，并且 H 的每个房间都被占用了。

如果一个集合与自然数集之间存在一个双射，我们说这个集合是 可数无穷的 （countably infinite）。这寓意着双射 f : N → S 用一个无穷序列 f （0）, f （1）,…“逐个数遍”某个集合 S 的所有成员，从集合{0,…, n -1}到有穷集合 S 的双射用相同的方式证明了 S 中正好有 n 个元素。在这两种情况下，“计数”必须“数遍” S 的所有元素，也就是说，对于每个 x ∈ S ，存在某个 n ，使得 f （ n ）= x 。

根据定理6.4，任意两个可数无穷集合之间都存在双射，因为每个集合都与ℕ存在双射。所以说所有可数无穷集具有相同的大小，即ℕ的大小[ℵ0，发音为“阿列夫零（aleph zero/aleph null）”。为其他无穷数集命名并对它们进行算术运算是很有趣的事情，但超出了本书的范围]。

我们已经看到有多个自然数集的子集是可数无穷的，例如，集合ℕ-{0}和非负偶数集。同样，自然数集的有些真超集也是可数无穷的，如集合ℤ。

定理7.1 ℤ是可数无穷集。

证明 ：我们需要“计数”所有的整数，即分配给每个整数一个数字标签0,1,…，且不遗漏任何整数。首先要尝试的可能是将0分配给0，将1分配给1，以此类推，那么我们在没有给负整数分配标签之前，会用尽所有的自然数。因此，我们将从零开始，然后是一个正整数接着一个负整数交替计数，以此类推，顺序是0,+1,-1,+2,-2,…。其双射如图7.3所示。

即 f ：ℕ→ℤ是一个双射，对于任意的 n ∈ℕ，有

即使是ℕ×ℕ（自然数有序对的集合），其大小也不大于ℕ。

定理7.2 ℕ × ℕ是可数无穷的。

证明 ：我们需要找到一种方法，对于 x ， y ∈ℕ，以某种顺序列出所有有序对〈 x ， y 〉，而不遗漏任何一个。我们不能使用最显然的顺序，即列出所有的 x =0的序偶对，然后列出 x =1的序偶对等，因为对于无穷多 x =0的序偶对，我们会用尽所有的自然数，而永远无法到达 x =1的序偶对，或者更高的 x 值的序偶对。

取而代之的是，我们将按照 x + y 的值递增顺序列出所有的序偶对，当 x + y 的值相同时，具有较小 x 的序偶对将优先。对于任意给定的 z ，只有有穷多个序偶对〈 x ， y 〉使得 x + y = z 。因此，这种排序最终会以有穷步到达每个 z ，即每一个序偶对〈 x ， y 〉。与最初假设的顺序不同，如果我们将ℕ×ℕ视为非负整数坐标平面上的点，沿着双射的前几个值，每次行进在一条对角线上，如图7.4所示。我们把求函数的代数式留作练习（见习题7.8）。■

定理7.2非常著名，该问题始于旅馆经理试图将一个客人塞入一个已经住满了客人的无穷旅馆。这意味着可数无穷多个可数无穷旅馆可以合并为一个可数无穷旅馆，用数学语言（见习题7.11）可以做如下描述。

定理7.3 可数多个可数无穷集合的并集是可数的。

一个集合是 可数的 ，如果它是有穷的或者是可数无穷的。如果一个集合是 不可数的 ，那么它不是可数的。

不可数性不是一个很清晰的概念。我们已经看到，有些集合看上去比自然数集合“更大”，但实际上并非如此。什么样的集合可能是无穷不可数的呢？我们没有任何例子，也没有任何明显的理由认为不可数集合的存在。

然而，它确实存在。一个经典的例子是 P （ℕ）——所有自然数集合的集合——是不可数集合。可以肯定的是， P （ℕ）是无穷的，即一个元素的集合{0}，{1}，{2}，…都是 P （ℕ）的成员。因此，可数无穷集{{ n }： n ∈ ^ℕ }是 P （ℕ）的子集。

但是， P （ℕ）的这些成员都是有穷集，是基数为1的集合。幂集 P （ℕ）还包含无穷集合，如正偶数集合{2，4，6，8，10，…}以及ℕ本身。很明显，没有一种聪明的方法能“数遍”所有的自然数的集合，就像我们对ℕ×ℕ所做的那样，按顺序列出每一个集合。

没有方法的原因如下：

对于ℕ的任意子集 S ，由于集合是由其成员决定的，所以可以通过ℕ的每个元素是否属于 S 来定义 S 。对于每个自然数来说，这是一个二选一的问题，因此，我们用第1位表示“是”，用第0位表示“否”。那么，任意子集 S 都可以表示为一个无穷长的位串——可数无穷位串，其中第 n 位表示“自然数 n 是否属于 S ”。例如，集合{1，2，3}可以表示为：

01110000000…

前四位数字之后都是0（第一位是0，是因为0∉{1，2，3}）。所有偶数的集合{0，2，4，6，8，10，…}可以表示为：

10101010101…

1和0将永远交替下去。我们将“ S 表示为无限位字符串”称为一个从自然数到{0，1}上的函数 χ _S ，其中 χ _S （ n ）是位置 n 的位值，位值为1当且仅当 n ∈ S ：

函数 χ _S 称为 S 的 特征函数 （characteristic function）（ χ 是希腊字母chi，发音为kiye）。

我们将采用 对角线 （diagonalization）法证明集合 P （ℕ）是不可数的。对角线法是一种特殊的反证法。它证明某类对象——ℕ和 P （ℕ）之间的双射是不存在的。证明过程为假设存在这样的双射，并证明它不是双射，因为它“漏掉”了一个集合，即我们用假设的双射 b ：ℕ→ ^P （ℕ）构造一个集合 S ⊆ℕ不是 b 的任何自变量的值。因为假设存在一个双射 b ，会导致结论： b 根本不是双射，从而没有这样的 b 存在。

定理7.4 P （ℕ）是不可数的。

证明 ：为了推出一个矛盾，我们假设 P （ℕ）是可数的。然后我们可以通过双射 b ：ℕ→ P （ℕ）对 P （ℕ）中的集合进行编号，即每个集合编号为 b （ n ），其中 n 为某个自然数。为了便于命名，对于每个 n ，令 S _n = b （ n ），因此 P （ℕ）={ S ₀ ， S ₁ ， S ₂ ，…}。

为了便于说明，我们用它们的特征函数来表示这些集合。因此，我们可以画一张方法图，给出ℕ的子集，设 S ₀ =0101010101…、 S ₁ =1110000000…，下一个是所有偶数的集合，即 S ₂ =0101010101…。每个可能的集合 S ⊆ℕ都会在这个顺序中的某个位置。因此，如果我们将特征函数作为无穷矩阵的行，将得到下图。

现在，我们构造一个新的集合 D ，它的特征函数是这个矩阵对角线的补（complement）。为了区别起见，用灰色标识对角线上的数字。 D 的第0位是 S ₀ 位0的补。因为 S ₀ 以0开始， D 的第0位将是1； S ₁ 的第1位为1，因此 D 的第1位将为0； S ₂ 的第2位为1，因此 D 的第2位将为0。以这种方式继续下去， D 的第 i 位数字是对集合 S _i 的第 i 位取相反数。因此，在示例中的 D 是以100…（011…的补）开始的。

以这样的方式构造的 D 不可能与 S ₀ 相同，因为 D 的位0与 S ₀ 相应位是互补的。同样，对于任意的自然数 i ， D 不等于 S _i ，因为 D 与 S _i 在第 i 个位置上有不同的数字，即 D 在对角线与行相交的位置上不同于每一行。因此， D 不同于任何 S _i ，它不会出现在 P （ℕ）所有成员（假设）的列表中。

这是一个矛盾。概括一下（不参照上图）：已知我们有一个ℕ的所有子集 S ₀ ， S ₁ ， S ₂ ，…的枚举，集合 D 是一个完美的自然数集合，命名 D ={ i ： i ∉ S _i }。那么对于每个 d ∈ℕ， D = S _d 是不可能的。因为假设 d 是一个自然数，使得 D = S _d ，那么

d ∈ D 当且仅当 d ∈ S _d （因为 D=S _d ）

当且仅当 d ∉ D （因为 D ={ i ： i ∉ S _i }）

从而有 d ∈ D 当且仅当 d ∉ D ，这是一个矛盾。所以 D 不是任何 S _i ，这与假设“每一个整数集合都是 S _i 之一”相矛盾。故不存在双射ℕ→ P （ℕ），即 P （ℕ）是不可数的 。■

我们说过，如果两个集合之间存在双射，那么它们的大小是相同的。现在可以给出集合之间“小于”的定义了：如果从第一个集合到第二个集合存在单射，但不存在满射（因此它们之间没有双射），那么就说第一个集合 小于 第二个集合（或者说第二个集合 大于 第一个集合）。对于有穷集合，这些定义是适合的，即如果| A |＜| B |，则有集合 A 小于集合 B 。由定理7.4可得，从ℕ到 P （ℕ）不存在满射，但肯定存在单射。例如，函数 f ：ℕ→ P （ℕ），其中对于每一个 n ∈ℕ， f （ n ）={ n }，我们就可以说 P （ℕ）大于ℕ。

因此，存在不可数个自然数的集合。类似地，任意可数无穷集有不可数个子集，例如有不可数个偶数子集。只要ℕ和集合 S 之间存在双射，那么 S 就有不可数个子集。

然而，有穷自然数集合是 可数的 。

定理7.5 ℕ的所有有穷子集的集合是可数的。

证明 ：注意，有穷集合特征函数的位串只有有限多个1，从某一点开始，所有的位都是0。因此，我们可以在最后一个1之后将位串截断，并按照长度递增的顺序列出这些有穷位串，对于相同长度的位串使用标准字典序。空集是有穷的，并且由于它的特征函数表示为000…，在这种情况下，没有最后一个1。我们称为“空位串”，用 λ （希腊字母lambda）表示。这样，我们可以列举所有的有穷集合，如图7.5所示。■

这种通过长度递增，并对相同长度的位串按字母顺序排列的位串排序方式称为 字典序 （lexicographic order）。

如果有可数个自然数的有穷集和不可数个自然数集，那么有多少个自然数集合的集合？正如我们将看到的那样，自然数集合的集合要比自然数集合多。众所周知， 超穷基数 （transfinite cardinal）的基本理论远远超出了本书的内容。我们只对定理7.4进行泛化。

我们可能已经注意到， P （ S ）大于 S ，不仅适用于 S 是可数无穷集，也适用于 S 是有穷集。两个元素的集合有四个子集，三个元素的集合有八个子集，以此类推。这种模式也适用于最小的集合：一个元素的集合有两个子集，零元素的集合则有一个子集（空集没有元素，但是有一个子集，即空集）。

因此我们得到一个泛化的模式，即每个集合拥有比元素数更多的子集数。对角线证明法很好地表明对于任意的集合 A ，无论 A 是有穷的、可数无穷的还是无穷不可数的，都有 P （ A ）大于 A 。

定理7.6 A 和 P ( A )之间存在单射，但不存在双射，因此对于任意的集合 A ，有 P ( A )大于 A 。

证明 ：映射 g ： A → ^P （ A ），使得对于任意的 x ∈ A ，有 g （ x ）={ x }，是一个从 A 到 P （ A ）的单射。为了证明不存在双射，再次使用反证法。假设存在一个双射 f ： A → ^P （ A ），定义集合 D ={ a ∈ A ： a ∉ f （ a ）}，即 D 是 P （ A ）的元素，由 A 中所有 a 不在集合 f （ a ）中的元素构成。当 A 是自然数集合ℕ时， D 正好是定理7.4的证明中定义的集合。

由于 f 是一个双射， D 是 P （ A ）的一个成员，所以存在 A 的某个成员被这个双射映射到 D 。我们称这个元素为 d ，所以 f （ d ）= D 。

因为 f （ d ）= D ={ a ∈ A ： a ∉ f （ a ）}，我们已知对于任意的 a ∈ A ， a ∈ f （ d ）当且仅当 a ∉ f （ a ）。

对特殊情况 a = d 应用该命题，有 d ∈ f （ d ）当且仅当 d ∉ f （ d ）。这是不可能的，从而产生了矛盾。因此，不存在双射。■

所以， P （ A ）是大于 A 的，并且 任意集合拥有比元素数更多的子集数 。

可数和不可数无穷集的概念对计算机科学家来说非常重要，因为计算机能够计算的集合是可数的。任何算法都只能使用有穷字符集中提取的有限数量的字符，因此所有算法的集合都可以按字典序排列，是可数的。

然而，所有函数的集合是不可数的（习题7.12给出了一个特定的不可数函数集合的示例）。因此，有些函数（事实上，有不可数个函数）与任何算法都不对应。任何算法都无法计算的函数称为 不可计算函数 （uncomputable function）。

计算机科学中有许多有趣的问题，人们希望可以通过算法来解决，但事实证明是不可计算的。例如， 停机问题 （haltingproblem）：给定算法对于已知输入是否会在有限步骤后停机，或者会永远运行下去而不停机。停机问题被判定为计算不可解是AlanTuring的学术贡献，从而带来了计算机科学领域的诞生 。

一旦认识到所有计算机程序的集合（从而所有算法的集合）是可数的，而所有函数的集合是不可数的，便可证明有些问题一定是不可计算的。

本章小结

• 无穷集可以与其真子集具有相同的大小。

• 当集合与自然数集具有相同的大小，则称集合是 可数无穷的 ，即集合与ℕ之间存在双射。

• 所有可数无穷集具有相同的大小。

• 一个集合是 可数的 ，当它是有穷的或者可数无穷的；如果不是，则称为 不可数的 。

• 集合ℕ×ℕ是可数无穷的，等价于可数个可数无穷集的并集是可数无穷的。

• 自然数的幂集 P （ℕ）是不可数的。可以用反证法来证明：将 对角线法 应用于集合的 特征函数 。

• 任意可数无穷集的幂集都是不可数的。

• 如果存在从 A 到 B 的单射但没有从 A 到 B 的满射（因此没有双射），则集合 A 小于集合 B ，并且 B 大于 A 。

• 先按长度排序，对于相同长度的字符串，按字母顺序排序，这样的字符串顺序称为 字典序 。在 字典序 中的前几个位串是 λ ，0，1，00，01，10，11，000…。

• 对于每个集合 S ，无论是有穷、可数还是不可数的，都有 P （ S ）大于 S ，即每个集合具有的子集比元素多。

习题

7.1 如果两个集合之间存在双射，则它们具有相同的大小。证明存在无穷多个不同大小的无穷集，即至少有可数无穷多个无穷集，其中不存在具有相同大小的两个集合。

7.2 由罗马字母表{ a ，…， z }中的字母构成的有限长度字符串的集合是可数的还是不可数的？为什么？

7.3 Johnny对定理7.4的证明持怀疑态度。他认为对角线法确实产生了一个自然数集合 D ，它不在原始列表 S ₀ ， S ₁ ，… 中。然而，他声称，新的集合可以通过将所有索引上移1，并在开始时滑动新的集合到列表开头来将新集合纳入列表中。也就是说，Johnny希望为每个 i ∈ℕ设置 T _i = S _i ，并设 T ₀ = D 作为新构建的集合。现在，他声称，在 T ₀ ， T ₁ ，… 列表中，所有的自然数集合都被列举出来了。请问他的论点有什么问题？

7.4 给出无穷集合 A 和 B 的例子，其中| A - B |等于：

（a）0。

（b） n ，其中， n 为大于0的整数。

（c）| A |，其中| A |=| B |。

（d）| A |，其中| A |≠| B |。

7.5 以下哪些项是可能的？举例说明或解释不可能的原因。

（a）两个不可数集合的差是可数的。

（b）两个可数无穷集合的差是可数无穷的。

（c）可数集的幂集是可数的。

（d）有穷集合的并集是可数无穷的。

（e）有穷集合的并集是不可数的。

（f）两个不可数集合的交集是空集。

7.6 使用对角线法证明[0，1]区间的实数集合是不可数的。 提示 ：任意实数都可以用0=0.000…～1=0.999之间的无穷小数表示。但是要注意，某些实数有多个小数表示方式。我们使用定理7.4的证明方法，而不是简单地依赖于该结果。

7.7 （a）证明0和1之间的实数有序对与该区间的实数一样多，即存在双射 f :[0,1]×[0,1]↔[0,1]。 提示 ：将实数表示为小数，如习题7.6所示。

（b）扩展上一问的结果，给出非负实数有序对和非负实数之间的双射。

7.8 图7.4展示了一个双射函数 f ：ℕ→ ^ℕ ×ℕ。给出逆函数 f ^-1 ：ℕ×ℕ→ ^ℕ （这也是一个双射）的代数式表示。（我们要求的是 f ^-1 ：ℕ×ℕ→ ^ℕ 而不是 f ：ℕ→ ^ℕ ×ℕ，因为它是两者中比较简单的一个。）

7.9 在下列每种情况下，说明集合是否为有穷、可数无穷还是不可数的，并解释原因。

（a）所有书籍的集合，其中“书”是由大写或小写罗马字母、阿拉伯数字、空格符号和下面的11个标点符号组成的有穷序列：

；　，　．　＇　：　　-（　）　!　?　＂

（b）少于50万个符号的书籍的集合。

（c）书的有穷集合的集合。

（d）大于0且小于1的所有无理数的集合。

（e）可以被17整除的数的所有集合的集合。

（f）偶质数所有集合的集合。

（g）所有“2的幂集”的集合。

（h）从ℚ到{0，1}上所有函数的集合。

7.10 下述问题涉及定理7.5及其证明。

（a）为什么不能通过按大小顺序枚举ℕ的有限子集来进行证明？

（b）给出一个不同的证明：通过“元素和”的顺序枚举ℕ的有穷子集，并对和相同的集合指定顺序。

（c）为什么这个新的证明不能推广到证明ℕ的所有子集的集合是可数的情况？

7.11 证明定理7.3。

7.12 （a）证明所有函数 f ：{0，1}→ ^ℕ 的集合是可数的。

（b）证明所有函数 f ：ℕ→{0，1}的集合是不可数的。 KMrJxQi7On4EsO1fuYH0XSYR5P64/uct8JRj+UZaUOPOQ1URgNWb7C6H74ELKNSN