比无穷更大的无穷

对上一节中的函数稍作改造，我们还能得到更加违反直觉的函数。例如，我们可以构造一个从正整数到正有理数的一对一函数，从而说明正整数和正有理数一样多！

方法很简单。取 f（n）为上一节中任意一个把全体正整数映射到全体正整数，并且每一个正整数都被映射过无穷多次的函数。按照如下方式定义g（n）：对于某个n，如果 f（n）的函数值m是第i次被映射到，则令g（n）等于分母为m的所有最简分数从小到大排列后的第i个分数。

比方说，我们取 f（n）为数列1，1，2，1，2，3，1，2，3，4，1，2，3，4，5，…中的第n项。由于 f（8）已经是第三次映射到2了，因此g（8）就等于分母为2的第三个最简分数，即5/2。

于是，g（n）就是一个把全体正整数映射到全体正有理数的函数，并且每个正有理数都被映射且只被映射过一次。这意味着，全体正整数和全体正有理数之间存在一个一一对应的关系，有多少个正整数，就有多少个正有理数！

大家或许会觉得奇怪：正有理数集不但包含了正整数集的所有数，还包含了正整数集没有的数，这两个集合里的元素怎么可能一样多呢？不过，对于一个无穷集合来说，既无重复又无遗漏地映射到一个比自己大的集合，这不是什么稀罕的事。比如，即使乍看上去，正整数集比非负整数集少一个数字 0，但它们之间仍然存在一对一的函数。最简单的例子就是 f（n）＝n-1。

不仅如此，正整数集和全体整数集之间也能一一对应起来。比方说，规定当n为偶数时，当n为奇数时，则有以下对应情况。

注意到，我们之前已经有了一个从正整数到正有理数的一对一函数，因而自然也就有了负整数与负有理数之间一一对应的方法。现在，我们又有了一个从正整数到全体整数的一对一函数，其中全体整数里包括了正整数、0、负整数三个部分，它们各自可以和正有理数、0、负有理数形成一一对应。也就是说，我们可以立即构造出一个复合函数，它能把正整数集一一映射到全体有理数集上。因而，正整数和全体有理数也是一样多的！

可见，在比较无穷集合的大小时，违反直觉的现象太多了。我们必须要给无穷集合谁大谁小下一个严格的定义。

格奥尔格·康托尔（Georg Cantor）是伟大的德国数学家，集合论的创立者，勇敢正视无穷集合的第一人。他提出，在判断无穷集合大小时，我们不应该再着眼于狭义的“元素个数”，而应该采用一种类似于“集合大小规模”的概念。他把这个新的概念叫做“集合的势”。康托尔规定，只要我们有办法把两个集合中的元素一一对应起来，那么这两个集合的大小就是相等的，或者说它们是等势的。按照这种定义，不管是非负整数集，还是全体整数集，甚至是全体有理数集，都和正整数集等势，它们是一组规模相同的无穷集合。

一个集合与正整数集等势，意思就是这个集合中的元素与正整数之间存在一一对应的关系。换句话说，尽管这个集合中的元素有无穷多，但我们能按照某种方式对它们进行排序并编号，用“第一个元素是谁，第二个元素是谁，第三个元素又是谁”的方式把它们一一列举出来。因而，我们给所有与正整数集等势的集合取了一个形象的名字，叫做“可数集”。刚才讨论的非负整数集、全体整数集、全体有理数集都属于可数集的范畴。

像这样的数构成的集合是否可数呢？虽然它们并不是有理数，但它们都是某个整系数多项式方程的解。比方说，就是x²-2＝0的一个解，则是x²-x-1＝0的一个解。我们把所有这样的数叫做“代数数”。代数数不但包括了所有的有理数（因为有理数可以看做一次方程的解），还包括了像一样的怪数，甚至包括了一些高次方程中无法用常规手段表达出来的解。有趣的是，即使是代数数这样庞大的数字群体，仍然属于可数集的范畴，因为我们可以按照一定的顺序把它们依次排列起来。

具体怎么做呢？首先，由于每个整系数多项式方程的解的个数都有限（不会超过这个多项式的次数），因此我们只需要找到一种排列这无穷多个多项式的方法即可。最容易想到的方案自然是，按照次数由低到高对多项式排序。这种方案可行吗？不行。x﹢1＝0，x﹢2＝0，x﹢3＝0……都是一次多项式方程，这样的多项式方程有无穷多个。如果按照次数高低给多项式排序，二次多项式将永远也排不上号。

我们可以按照所有系数之和给多项式排序吗？也不行。因为多项式的系数有可能是负的，因而其系数之和可以任意小，根本不存在系数之和最小的多项式。

我们可以按照所有系数的绝对值之和给多项式排序吗？这次似乎有些希望，但细想一下你会发现还是不行。x-2＝0，x²-2＝0，x³-2＝0……它们的系数绝对值之和都是 3。这样的多项式方程有无穷多，并且它们对应着不同的代数数。那些系数绝对值之和更大的多项式，就永远也排不上号了。

我们来总结一下之前种种方案失败的原因：如果只限定次数，系数将有无穷多种选择；如果只限定系数，次数将有无穷多种选择。如果同时对次数和系数加以限定，问题不就解决了吗？因此，我们想到，为何不在所有系数的绝对值之和的基础上，再加上这个多项式的次数，按照这个结果的大小给多项式排序呢？具体地说，定义n次整系数多项式的“复杂程度”为，那么对于任意一个正整数N，复杂程度恰好为N的整系数多项式都只有有限多个。这保证了我们可以顺利地给多项式排序。

下面就是一种给所有整系数多项式方程排序的方法。

（1）总方针：按照多项式的复杂程度值从小到大排序。

（2）如果复杂程度相同，则按照次数由低到高排序。

（3）如果次数也相同，则按照常数项由小到大排序。

（4）如果常数项也相同，则按照一次项系数由小到大排序。

（5）如果一次项系数也相同，则按照二次项系数由小到大排序。

……

现在，我们已经给所有整系数多项式方程找到了一个合适的排列顺序，让每个整系数多项式都有了一个编号。从小到大依次写出第一个方程的解，再依次写出第二个方程的解，再依次写出第三个方程的解……这样便能穷举完所有的代数数。最后，把重复出现的数删去，从而得到了目标数列——每个代数数都恰好出现了一次。代数数与正整数之间也就有了一一对应的关系。或者说，代数数也是可数的。

事实上，建立代数数与正整数的一一对应关系远没有那么复杂。我们还有一种更帅的方法。如果把一个整系数多项式方程中所有的符号都列出来，一共也就只有0、1、2、3、4、5、6、7、8、9、+、-、=、x共14种符号。多项式方程x²-2＝0也就可以简单地看做由符号x、2、-、2、＝、0相连得到的。这样看来，给多项式排序就变得异常简单了。

（1）总方针：按照多项式所含符号个数从少到多排序。

（2）如果多项式所含符号个数相同，按照第一个符号排序。

（3）如果第一个符号也相同，按照第二个符号排序。

（4）如果第二个符号也相同，按照第三个符号排序。

……

同样地，依次写出每个多项式方程的每一个解，再去掉重复的数，我们将得到把正整数一一映射到全体代数数的另一种方案。

那么，数学世界中最为神秘的数学常数π呢？直觉上，某个超级复杂的整系数多项式方程，解出来恰好是x＝π，这是绝对不可能的。正如我们在第19节所述，1882年，德国数学家林德曼证明了，π确实不满足任何整系数多项式方程，即π不是代数数。e≈2.718则是另一个重要的数学常数，它也不是代数数。这是由数学家查尔斯·埃尔米特（Charles Hermite）在1873年首次证明的。我们把这些不是代数数的数都叫做“超越数”。

虽然π和e属于更没规律的超越数，但我们仍能把它算出来。我们可以设计出一套算法，只要给它足够长的时间，它就能计算出π或者e的小数点后任意多位数。我们把这种能够计算到任意精度的数叫做“可计算数”。按照这种定义，整数、有理数、代数数都是可计算数，除此之外，π、e也是可计算数。人们目前尚不知道π﹢e、π-e、πe、π/e、π^e是不是超越数（事实上，人们现在还不知道它们是不是无理数），但不管怎样，它们也都是可计算数。可见，可计算数集合的范围远远超过了之前讲到的整数集、有理数集以及代数数集。然而，下面我们将证明，可计算数仍然是可数的。

借用代数数可数性的第二种证明方法，我们可以很快给全体可计算数制定一个排序方案。我们可以选用某种计算机编程语言来描述可计算数的计算方法，那么所谓的计算方法，说白了也就是由标准美式键盘上的95种字符（包括小写字母、大写字母、数字以及各种符号）组成的一段程序代码。我们把所有可能的代码按照代码长度排序，长度相同者按第一个字符排序，第一个字符也相同则按第二个字符排序，以此类推。这将列举出所有可能的程序代码，从而也将列举出所有可能的可计算数。因此，可计算数集合也是可数的。

有没有什么数是不可计算的呢？答案是肯定的。在第 40 节的末尾，我们讲到了蔡廷常数，它就是一个典型的不可计算数。不过，它虽然不可计算，但却有一个明确的定义，可以用数学语言清晰地定义出来。我们把所有这样的数都叫做“可定义数”。

可定义数不但包含我们平常经常使用的整数和有理数，也包含代数数、可计算数，甚至还包含一些不可计算数（例如蔡廷常数）。事实上，历史上一切被数学家研究过的数，不管是已发表的还是未发表的，不管是已命名的还是未命名的，不管是能算出来的还是不能算出来的，都是可定义数。这是一个异常庞大的数集。不过，它仍然是可数的。

为了证明这一点，只需要注意到，一个数的定义，无非是用数字、字母和标点符号组成的一段英文文本。我们把所有能够用来定义一个数的英文文本找出来，按照文本的长度由短到长排序（长度相同者按照之前的方法处理）。因此，所有可定义数组成的集合也是可数的，可定义数和正整数之间存在一一对应的关系。

看到这里，想必大家会有一个疑问：讲了半天，究竟有没有不可数的无穷集合呢？换句话说，我们能找到比正整数集规模更大的无穷吗？

答案是肯定的。康托尔发现，不可数的集合是存在的。例如，所有介于0和1之间的实数就是不可数的。你不能从小到大对（0，1）区间内的所有实数进行排序，因为不存在“第一个正实数”。你也不能按照小数展开的长度对所有实数进行排序，因为很多数都是无限小数，它们永远排不上号。事实上，康托尔用一种非常巧妙的方法证明了，任何方案都不能把正整数和（0，1）区间内的实数一一对应起来。

证明的思路是，先假设我们已经按照某种方案将（0，1）区间内的所有实数列成了一张表，然后再说明，这张表其实并没有包含所有的实数。

现在，假设我们已经把所有（0，1）区间内的实数按照某种顺序排列为a₁，a₂，a₃，…。这里面的每个数都可以表达为形如“零点几几几几几……”的无限小数（如果是有限小数，可以在其后面添加数字0，把它变成无限小数）：

a₁＝ 0.314 159 2653…

a₂＝ 0.8080808080…

a₃＝ 0.6700000000…

a₄＝ 0.2222222222…

a₅＝ 0.6180339887…

a₆＝ 0.1234343434…

……

下面我们构造一个新的实数，它也属于（0，1）区间，但却不在这张列表里。让这个实数的小数点后第一位不等于a₁的第一位，第二位不等于 a₂的第二位，等等，总之要让这个实数的小数点后第n位不等于 a_n的第n位。那么，这个新实数将有别于上面那个列表中的任何一个数，因为它和列表里的任意一个数都有至少一位是不同的。因此，我们永远不可能把所有0到1之间的实数一个也不少地排成一列。

注意，在上述证明过程中，“实数区间”这个条件用在了哪里。我们当然也可以假设（0，1）区间内的有理数被排成了序列a₁，a₂，a₃，…，也可以像刚才那样构造出一个数，它不等于序列中任何一个数。不过，我们构造出的这个数不见得仍然是有理数，因此这和假设并不矛盾。但在证明实数区间不可数时，我们构造出来的数的确是本应该在列表中的数，这才是“实数区间”这个条件发挥作用的地方。

这是证明（0，1）区间内所有实数不可数最传统、最经典的方法。不过，作为实数理论中的一个基本结论，它还有很多不同证明。我想在这里介绍另一种同样漂亮的证明，这是由马修·H.贝克（Matthew H.Baker）在2008年提出的。

设想A和B两个人在实数区间（0，1）上玩一个游戏。首先，A在（0，1）区间选一个数a₁，然后 B在区间（a₁，1）里选一个数b₁。接着，A在（a₁，b₁）区间选一个数 a₂，然后B在区间（a₂，b₁）里选一个数b₂……总之，A只能选取越来越大但不能比B选的数更大的数，B只能选取越来越小但不能比A选的数更小的数。两人轮流按规则选数，这些数将从两侧出发不断向中间靠拢。可以看到，序列a₁，a₂，a₃，…是一个单调递增的有界序列，因此游戏无限进行下去，序列a₁，a₂，a₃，…最终会收敛到某一个实数c。游戏进行前，A和 B约定区间（0，1）的一个子集S，规定如果最后c在S中，A胜，否则B胜。

一个有趣的事实是，如果S是可数集，B 肯定有必胜策略。如果集合S是可数的，那么B就可以把集合S里的数排列成一个序列s₁，s₂，s₃，…。B的目标就是让序列a₁，a₂，a₃，…的极限不等于序列s₁，s₂，s₃，…中的任一个数。考虑B的这样一个游戏策略：当B第i次选数时，如果选s_i合法，那么就选它（这样序列a₁，a₂，a₃，…就不能收敛到它了）；如果选s_i不合法，那就随便选一个合法的数（反正序列a₁，a₂，a₃，…已经不可能收敛到s_i了）。这种策略就可以保证 A 选出的数列的极限不是集合S里的任一个数。

接下来就是神奇的一刻了。假如A和B约定好的集合S就是整个实数区间（0，1），那么B显然不可能获胜；但如果（0，1）是可数集，B是有必胜策略的。于是我们就知道了，（0，1）是不可数集。

既然连（0，1）区间都不可数，整个实数集R当然也就是不可数的了。有趣的是，我们可以在（0，1）区间和整个实数集R之间建立一一对应的关系，从而说明（0，1）区间和实数集R是同一级别的无穷集合，正如正整数集和有理数集是同一级别的无穷集合一样。比如函数，它是一个从（0，1）区间到实数集R的一对一函数，这就证明两个集合是等势的。利用图1所示的几何方法，我们也能马上看出，如果两根线条的长度不同，它们上面的点也能一一对应起来。即使其中一根线条无限长，我们同样能找到一一对应的方法。我们把所有和（0，1）区间等势的集合都叫做“C势集”。

图1

现在，我们已经有了两种规模不同的无穷：以正整数集为代表的可数集（包括整数集、有理数集、代数数集、可计算数集、可定义数集），以（0，1）区间为代表的C势集（包括任意长的连续实数区间，甚至是整个实数集R）。这是两个尺度完全不一样的无穷。与可数集比起来，C势集真的是非常非常大的集合。

有理数集是可数的，但实数集是不可数的，这样我们便可得到一种无理数存在性的非构造性证明。事实上，在全体实数中，几乎所有的数都是像一样的无理数，有理数仅仅是实数中微不足道的一部分。

类似地，由于代数数是可数的，而实数集不可数，因而我们可以立即推出超越数的存在性。事实上，几乎所有的数都是像π、e那样的超越数，代数数只占实数集中零星的一部分。

同理，由于可计算数是可数的，而实数集不可数，因而实数集中必然存在不可计算数。事实上，几乎所有的数都是像蔡廷常数一样的不可计算数，相比之下，可计算数实在是少得可怜。

同理，由于可定义数是可数的，而实数集不可数，因而在实数集中一定存在不可定义数。

那么，在数学历史上，谁发现了第一个不可定义数呢？答案是，从没有人发现过不可定义的数，以后也不会有人找到不可定义的数。因为不可定义数是无法用语言描述的，我们只能用非构造的方式证明不可定义数存在，但却永远没法找出一个具体例子来。

在实数当中，几乎所有的数都是不可定义的。数学家们所研究的数，只是实数世界中的沧海一粟。不过，数学家们也不会损失什么。每一个值得研究的数一定都有着优雅漂亮的性质，这些性质就已经让它成为了能够被定义出来的数。