如何证明双射（请问希尔伯特大旅馆还有空房吗）

作者 | 刘洋洲

来源 | 转自知乎专栏《万物皆数也》，“数学英才”获授权转载，在此感谢！

虽于果核之内，吾亦宇宙之王。——莎士比亚《哈姆雷特》

无限、无穷（infinity），这个词汇本身就透露出其认识路径：无（in-）+ 限（finity）。我们必须对有限加以否定，从而间接地认识“无限”这个概念。

在人类古老的神话中就有无限的影子。无论是古希腊神话中被诸神惩罚的西西弗斯永无止息地把一块巨石推上山顶，还是愚公移山、精卫填海的故事，无限既是对个体有限生命的嘲讽，也是民族延续的坚定信念。我们从未见过无限，可是我们又似乎身处无限的片段之中。

我想西西弗斯每次失败一定是被动了手脚，所以我画成逐渐变大的滚石。

世界上凡是可见的事物中，几乎没有什么不是没有界限的。也许我们会说，时空是无限的，但这也只是假设，没有人能真正验证无限，除非他自己就是无限本身。

Part1通往无限之路

无限是一个不断检验的过程。

1有限的大小

这就好比两只小猴子比谁的桃子多，虽然它们不识数，但是这不妨碍做比较：两猴每次只拿出一个桃子配对，重复这个行为，直到有一方再也拿不出新的桃子，比较终止，还有桃子的猴子获胜。

桃子配对的行为其本质是建立映射（选择公理理保证我们可以将集合元素逐个展示）：

这似乎是比较大小的一种通法：

（集合元素个数比较）设是两个集合，是一映射，表示集合元素个数。

若是满射，则；

若是单射，则；

若是双射(既单又满)，则.

证略。

注意到一个非空有限集无法和自己的真子集建立双射，否则它的元素个数与其真子集的个数相等。这成为有限与无限的分水岭。

2希尔伯特大旅馆

我们最熟悉的无限集应当是自然数集：

注意，我这样画只是为了艺术性。

希尔伯特设想这样一个旅馆，其中的房间编号是全体自然数。假设现已住满房客，忽然来了一个新的旅客，老板说：“不成问题！”他让n号房客换至n+1号房，于是0号房被空了出来，于是新来的房客就可以住进去了。

于是对于有限的新旅客，总可以按照上面的方式一个一个安排入住。那如果来了和房间数“一样多”的旅客呢？我们可以安排原来的房客全部住到偶数房间：，于是奇数号的房间被空了出来，那么这无穷多个房客可以逐一入住：

希尔伯特旅馆的故事，事实上是建立了以下双射：

我们发现：无穷集合可以和自己的真子集建立1-1映射的关系！

自我指涉的无穷

数学上，我们将两个存在双射的集合称为等势。“势”已经超越有限集合元素的个数的概念，可以用来描述无限集元素的“多少”，我们将集合的势记为，于是我们可以将上面的结论简写为：

其余同理。

若无限集满足，我们称是可列的。

3无限的“大小”？

既然讨论无限集合元素个数已经没有意义，那么是否无限集和无限集元素个数“一样多”？或者干脆说任意无限集都是可列的吗？

如果答案是肯定的，那就太无趣了。然而康托尔带给我们巨大的惊喜，无穷居然不止一种！这简直是理性数学世界中最怪诞的狂想！

定理1：实数不可列。

光是区间这个集合就比自然数集更“大”。

证明：反证法。若不然，中的实数和自然数集可以建立双射，有如下列表：

也就是说内的实数可以不重不漏地罗列出来。我们假设上面的小数是规范的二进制表示（其他进制也可以），所谓不规范，就是指：

我们只要构造出一个实数不在上面的列表，就可以得出矛盾。只需定义，且满足关系：

也就是说与上面列表的“对角线”小数在对应数位的小数完全“相反”，要么前者是后者是，要么后者是前者是. 现在我们可以说，就是我们所构造的矛盾：显然它不在这个列表中，因为它与列表中的每行小数，与不相等。

这个奇妙的方法是由康托尔所构造，被称为对角线法。

上面的结论告诉我们

这也就回答了本节最开始的问题，无穷和无穷可能是不一样的。

这里顺便说一下有理数和自然数的关系：

想想有理数如何不重不漏地排列出来？

事实上更让人惊奇的是，，例如时，我可以说直线上的点和平面上的点等势。（建立双射的方法：将平面上的点横纵坐标以二进制表示，然后将两者分别作为奇数位于偶数位，从而合并成为同一个二进制小数。）

4repeat{更上一层楼}

事实上有寻找更大的势的集合的系统方法——幂集。

所谓幂集，就是考虑一个集合的子集所构成的集族。例如集合的幂集为：

我们将集合的幂集记为

事实上，幂集的元素比原集合的元素要多得多。这对于有限集而言是显然的，由组合学的知识可知，一个有个元素的集合的子集个数为

那么对于无限集呢？

定理2：

这个证明十分奇妙，请大家欣赏。

证明：假设存在满射，我们考虑非空子集

我们首先说明的存在性，然后指出其矛盾。如果是空集，则对于任意元素都有，由于是双射，则存在元素满足，但是中还有其他元素，则按照假设也满足，这与是双射矛盾。

由于双射，则存在元素，满足 此时出现矛盾：

，由于的定义，则有；

，符合的性质，于是.

其实这里的的构造也是源于对角线法则。如果集合与其幂集存在双射，则有以下理想排列：

设法构造一个的子集，使不同于中的任何一个。

这样一来，我们就可以不停地迭代了：

我们约定用希伯来字母中第一个字母 （阿列夫aleph）代替上面的序列：

Part2数学就是超越

康托尔仿佛发现了一窝巨大的猛兽家族，它们增长之迅猛，宇宙大爆炸都远远不能形容，它们在数学世界的云端悠闲漫步，被地上的宛如蚂蚁的人类，惊鸿一瞥，而第一个抬头的蚂蚁叫做康托尔。

关于这个方面的内容实在难以在一篇短文中穷尽，惊人的结论与发现使得了解它们的人们浑身战栗：“包含一切集合的集合”不再是一个集合，它是否包含它自己将会导致罗素悖论；连续统假设是说，是否存在新的势介于两者之间？比如

康托尔猜测：否。

而答案出乎了所有人的意料。

大卫·希尔伯特把康托尔的连续统假设列入20世纪有待解决的23个重要数学问题之首。1938年哥德尔证明了连续统假设和公理系统不矛盾。1963年美国数学家保罗·寇恩证明连续统假设和公理系统是彼此独立。因此，连续统假设不能在公理系统内证明其正确性与否。

数学英才

中学生英才计划

数学学科官方公众号

推送数学微慕课和学习资料