神奇的希尔伯特旅馆

本文为系列文章 “无穷集的基数” 的第三篇。该系列文章讲述无穷集之间的大小区别，有助于理解后续学习中经常遇到的数学运算。

系列文章：

所需知识：数学归纳法，集合运算

希尔伯特旅馆悖论是一个与无穷集有关的数学悖论，由德国数学家大卫·希尔伯特提出。 网上可以搜到很多相关的文章，建议看看百度百科的（链接放不出来，你懂的）。

悖论里面提及一个拥有 “可数无限多” 个房间的旅馆，这家旅馆所有的房间都已经有客人入住。按常理来说，这家旅馆是无法再接纳新的客人（参考有限个房间的情况），但事实上并非如此：

1. 旅馆还可以接纳有限个新客人；

2. 旅馆还可以接纳 “可数无限多” 个新客人；

3. 旅馆还可以接纳 “可数无限多” 辆客车带来的客人，每辆客车里面有 “可数无限多” 个新客人。

之所以出现这种不符合常识的情况，主要是由 “无穷集基数的定义” 所决定（请参考前面2篇系列文章）。而这里说的 “可数无限多” 指的就是可列集：

定义

与自然数集  对等的集合称为可列集，它的基数记为  。

希尔伯特旅馆悖论所描述的，都是可列集的性质。这篇文章将用数学语言来证明这些性质。

1. 最小的无穷集

对于任意一个可列集  ，由于集合  与自然数集  对等，即存在一一映射  ，使得对任意  都有：

根据映射  ，我们可以把可列集  的所有元素排列出来，成一序列，将任意  放在数列中下标为  的位置上：

反过来，凡是可以把所有元素排成序列的集合  ，必定是可列集。因为上述排列已经将集合  的所有元素与其在序列中位置的下标对应起来，构成从集合  到自然数集  的一一映射。这也许就是 “可列” 集名字的由来。

结论1

一个无穷集合是可列集的充分必要条件是，它的所有元素可以排成序列。

在这里，我们进一步指出，可列集就是最小的无穷集：

定理

每个无穷集必包含一个可列子集。

证明

设集合  为无穷集，则存在  ，而  还是一个无穷集合，因此又存在  ，且  依然是一个无穷集合。

重复以上过程即可见，存在集合：

满足  。由结论1知  是可列集，证毕。

—— 邓东皋、常心怡的《实变函数简明教程》

上面的证明用了数学归纳法，可能不大好接受。

换个角度，上述定理其实说的是，对于任意无穷集  ，自然数集  必然与  的一个子集  对等。根据系列文章《学校有给你讲过无穷集吗？》中关于基数的定义可知：

也就是说：

结论2

可列集的基数是无穷集合里面最小的！

2. 两个可列集的并集

两个可列集的并集，按照希尔伯特旅馆悖论里所描述的方法，依然可以构造自然数集  与该并集的一一映射：

方法1

已知分别有可列集  和  ，按照结论1，可以把它们的所有元素分别排列成以下序列：

我们通过下面这种方法把  和  的元素一起排列成新的序列：

用数学语言来描述的话，就是通过下面的公式，将可列集  和  的所有元素分配到序列  的位置上：

或者反过来，通过下面的公式，将序列  的所有位置分配出去：

方法描述完毕。

任意可列集  和  ，如果  ，则可以通过方法1将  的所有元素排列成序列  ，由结论1可知，  仍然是可列集。

如果  ，去掉重复的元素得到并集  之后，实在没办法通过数学公式描述  与自然数集  的一一映射。不过，并集  明显还是无穷集，由结论2可知，  至少是一个可列集；而序列  仍然可以容纳  的所有元素，这说明  最多也就是一个可列集。因此，两个可列集的并集  只能是可列集。

定理

两个可列集的并集是可列集。

这个定理与希尔伯特旅馆悖论中的第2种情况，说的是同一件事情。还有，既然两个可列集的并集依然是可列集，那 “可列集与有限集的并集” 当然也还是可列集，这就与悖论中的第1种情况相符合。

此外，将两个可列集并集得到的可列集与第3个可列集进行并集，当然还是可列集，所以可以推出，任意有限个可列集的并集还是可列集。

3. 可列个可列集的并集

希尔伯特旅馆悖论中的第3种情况，说的就是可列个可列集的并集，实在是够绕够复杂，数量也实在够多的。

方法2

已知有可列个可列集  ，我们直接把这可列个可列集排成序列：

按照结论1，分别把这些可列集的所有元素排列成以下序列：

我们通过下面这种方法把些可列集的所有元素进行排列： 

排列成新的序列  ：

用数学语言来描述的话，就是通过下面的公式确定  ，将可列集的所有元素  分配到序列  的位置上：

或者反过来，通过下面的公式确定  和  ，将序列  的所有位置分配出去：

方法描述完毕。

能理解这种排列吗？对于可列集的元素  ，在排序时，先排  值小的元素；当  的值相同时，先排  值小的。

对于任意可列个可列集  ，记它们的并集为：

如果可列集  两两不相交，则可以通过方法2将并集  的所有元素排列成序列  ，由结论1可知，并集  仍然是可列集。

如果可列集  存在相交非空的情况，去掉重复的元素得到并集  之后，也是没办法通过数学公式描述并集  与自然数集  的一一映射。类似两个可列集并集的情况，由于并集  仍然是无穷集，由结论2知道，并集  至少是一个可列集；同时，序列  依然可以容纳并集  的所有元素，并集  最多也就是一个可列集。因此，并集  也只能是可列集。

定理

可列个可列集的并集是可列集。

这个定理与希尔伯特旅馆悖论中的第3种情况，说的是同一件事情。

4. 有比可列集大的无穷集吗？

前面我们看到，即使给可列集不停地添加元素，甚至添加可列个可列集那么多个元素，最终得到的集合竟然还是和原来一样大！

我们知道自然数集  是可列集，那究竟有没有比自然数集  大的集合啊？本来庆幸知道可列集是最小的无穷集，到头来才发现原来所有无穷集都一样多？如果所有无穷集都一样多，那相互比较就没有意义，前面系列文章关于基数的定义就没有意义。

幸亏大佬们又出来帮忙，帮我们找到一个比自然数集  更大的集合。欲知后事如何，且听下回分解 。