无穷之中的无穷

伽利略·伽利雷(Galileo Galilei)是16世纪意大利伟大的博学家，他第一个提醒我们注意，无限集合和有限集合的性质有着根本上的不同。正如本书第一页所暗示的，如果一个有限集合的元素可以和另一个集合的部分元素配对，那么第一个集合的大小就小于第二个。然而，与此相反，我们可以用这种方法将无限集合与自身的子集(subset)对应起来(这里子集这个术语表示原集合内包含的一个集合)。要理解这一点，我们都不需要超出自然数数列1， 2， 3， 4，…。我们可以轻易地举出这个集合的任意多个子集，它们都形成无限集合，从而与全集形成一一对应的关系(见图8)：奇数1， 3， 5，7，…，平方数1， 4， 9， 16，…，以及不那么明显的素数2， 3， 5， 7，…。并且在每种情况下，其相应的补集(complementary set)，即偶数、非平方数及合数，也都是无穷的。

希尔伯特旅馆(Hilbert Hotel)

大卫·希尔伯特(David Hilbert)是他那个年代最杰出的德国数学家。这家十分奇特的旅馆总是与他的名字联系在一起，它生动地体现了无限集合的奇妙性质。这家旅馆的主要特点是它有无穷多房间，用1， 2， 3，…来编号，还夸下海口，希尔伯特旅馆总是有空房。

一天晚上，这家旅馆却客满了，也就是说每一间房里都住了一位客人。令前台服务员沮丧的是，又一个客人出现了，并要住一间房。幸好经理出手了，他把服务员拉到一边，教他如何处理这种情况，这才避免了尴尬的局面。“让1号房的客人搬到2号房，”他说，“2号房的搬到3号，以此类推。换句话说，我们通知整个旅馆，要求n号房的客人换到n+1号房中，这样1号房就可以空出来给这位客人了!”

因此你看，在希尔伯特旅馆的确总是有空间的。但是到底有多大空间呢？

第二天晚上，服务员面临着一个类似但更加考验人的情形。这一次，一艘载着1729名乘客的太空飞船抵达了，所有人都闹着要在已经客满的旅馆中各自住进一间房。不过前台服务员从前一晚吸取了经验，知道怎样推广之前的方法来应付这个额外的旅行团。他让1号房的人去1730号房，2号房的换到1731号房，如此这般。他发出了通知，要求n号房的客人搬进n+1729号房间。这就让1～1729号房都空了出来，给新来的人入住。我们的服务员为自己独立处理了昨晚问题的新版本感到骄傲——他这么想也是完全合理的。

然而，最后一天晚上，服务员再次面临同样的情况——一家客满的旅馆，但是这次让他惊恐的是，不是仅仅出现了几名额外的客人，而是一辆无限大的星际快车，载着无穷多的旅客，每个自然数都对应一位客人。焦头烂额的宾馆服务员告诉司机，这家旅馆已经满员，看不出有什么办法能容纳车上的全部旅客。他或许可以塞下一两个，甚至也可以是任意有限个数，但绝无可能是无穷多的额外客人。这就是不可能!

一场无限大的骚乱眼看就要爆发，就在这关头，经理再一次及时干预。他深晓伽利略关于无限集合的教导，于是告诉巴士司机：完全没问题，在希尔伯特旅馆，任何人都能有房间。他把惊慌失措的前台接待员叫到一边，又给他上了一课。“我们只需要这样做。”他说，“我们让1号房的住客换进2号房，2号房的换到4号房，3号房的去6号房，以此类推。总体而言，n号房的客人应该搬到2n号房。这样所有奇数号的房就空了出来，无限星际快车的旅客都能入住。完全没有问题!”

似乎一切都在经理的掌控之中。但是，假设一艘飞船有某种技术，使得实数轴的连续统[1](continuum)上的每一点都对应于一位乘客，如果这艘船出现了，那么即便是经理也无能为力。每个小数一个人的话，希尔伯特旅馆就会彻底挤爆。在下一小节我们就会知道原因。

康托尔的比较法

当你第一次思考这些问题的时候，它们可能会让你大吃一惊。不过，有一点并不难接受，无限集合的性质在某些方面或许与有限集合不太一样，其中一例便是它们与自身的某些子集有同样的大小。在19世纪，格奥尔格·康托尔(Georg Cantor)比我们走得远得多。他发现并非所有无限集合都拥有同样多的元素，这个发现出人意料，不过你一旦注意到它，就不难体会其中的含义。

康托尔要我们考虑以下这个问题。假设我们有一张无限长的数表L，里面有数a1，a2，…，可以把它们看作以小数形式给出的。那么可以写下一个在L中从未出现过的数a。我们只需要让a的小数点后第一位与a1的小数点后第一位不同，小数点后第二位与a2的小数点第二位不同，小数点后第三位与a3的小数点第三位不同，以此类推。这样，我们就构造出了数a，它与列表中任意一个数都不同。这个结论表面上看起来人畜无害，但它导致了一个直接后果，那便是数表L绝对不可能包含所有的数，因为L中缺失了数a。由此可知全体实数的集合，即所有的小数展开式，不能被写在一个列表里。换句话说，实数集与自然数不能像图8里那样建立起一一对应的关系。这条推理链被称为康托尔对角线论证法(Cantor’s Diagonal Argument)，为了构造集合L外面的数a，我们想象了L的小数列表形式(如图9)，并用这个阵列的对角线定义了a。

这里有一些微妙之处。我们或许能把缺失的那个数放在L的开头，这样就能轻易绕过这个困难。这创造出一个更大的列表M，它包含引起麻烦的数a。但是，背后的问题并没有消失。我们可以再一次运用康托尔的构造方法，引入一个崭新的数b，而它不存在于这个新列表M当中。我们当然可以像之前一样，无限次地继续加长现有的列表，然而康托尔的结论依然成立：纵使我们能够不断造出含有之前忽略掉的数的列表，但是永远不可能有那么一张表包含每一个实数。

因此，全体实数的集合在某种意义上比所有正整数的集合大。虽说两者都是无穷的，但是不像偶数可以与自然数列表匹配那样，它们没法配对在一起。的确，假定有一张表包含了区间0～1内所有的数，我们将康托尔的对角线法应用在这个列表上，那么缺失的数a也将位于这个范围内。因此，类比于之前，我们同样可以总结出，任何想列出这个区间的全部元素的尝试都会是徒劳的。我们提起这个事实，是因为很快就要用到它。

我们随意地接受任何可能的小数展开的时候，就打开了通往超越数的大门。那些数超出了能从欧氏几何和普通代数方程产生的数的范围。康托尔的证明告诉我们，超越数是存在的，并且有无穷多个。因为假如它们仅仅组成一个有限的集合，那么它们就可以被放在我们的代数数(非超越数)的表单的开头，这样就产生了一张全体实数的列表，而我们已知这是不可能的。令人惊异的是，我们发现了这些奇怪的数是存在的，却还没有指认出其中的任何一个!仅通过互相比较某些无限集合，我们就揭示了这些数的存在。在我们熟悉的代数数和所有小数展开的集合中间，有着巨大的空隙，而超越数正是填充这些空间的数。用一个天文学的比喻来说，超越数就是数的世界中的暗物质。

从有理数到实数，用数学家们的话来说，我们是从一个集合转到了另一个势[2](cardinality)更大的集合。如果两个集合的元素可以一对一地匹配起来，那么它们就等势。用康托尔的方法可以证明，任何集合的势都小于由它的所有子集组成的集合的势。这对于有限集合来说是显然的：的确，在第5章，我们已经解释了如果一个集合有n个元素，那么可以构造出2n个子集。但是，自然数这个无限集合{1， 2， 3，…}的所有子集组成的集合S到底有多大呢？这个问题不光本身很有趣，我们得到答案的方式也耐人寻味。结论是S确实是不可数的。

罗素悖论

假设反过来，S是可数的，在这种情况下自然数的子集可以按某种顺序列举出来：A1，A2，…。现在，任意一个数n可能是An的元素，也可能不是。让我们考虑由所有不属于集合An的数n所组成的集合A。现在，A是自然数的一个子集(有可能是空集)，于是它应该也在某个时候出现在了之前说的列表里，比方说A =Aj。现在出现了一个无法回答的问题：j是Aj的元素吗？如果答案是“是”，那么由A定义方式，我们可以推出j不是A的元素。但是A = Aj，这自相矛盾。另一种可能的答案是“不是”，j并非Aj的元素，在这种情况下，再一次，通过定义我们推断j是A=Aj的一个元素。于是我们又遇到了矛盾。因为矛盾不可避免，我们的原始假设——自然数的子集能被可数地列举，必为假。的确，这个方法成功证明了任何可数无限集合的子集所组成的集合是不可数的。

这种自指式风格的证明是由伯特兰·罗素(Bertrand Russell)引入的，当时的背景稍有不同，他是为了导出罗素悖论(Russell’s Paradox)。罗素将这个方法应用于“所有不属于自己的集合组成的集合”，他问出了以下令人尴尬的问题：这个集合是否是自身的一个元素？再次，“是”会推出“否”，而“否”会得出“是”，这迫使罗素得出结论，这样的集合不可能存在。

19世纪90年代，康托尔自己就从“所有集合组成的集合”这个思想中发现了一个隐含的矛盾。的确，罗素承认他的悖论受到康托尔工作的启发。无论如何，我们从所有这些讨论中总结出的经验是：不能简单地想象数学集合可以随意引入，对于如何描述集合需要设置一些限制条件。从那以后，集合论学家和逻辑学家一直在为这些悖论造成的后果绞尽脑汁。这些困难最令人满意的解决方案，是现在已经成为标准的ZFC集合论(包含选择公理的策梅罗-弗兰克尔集合理论[3])。

显微镜下的数轴

回到给定的数a和b。再一次，令c为它们的平均值。如果c是无理数，我们就得到了要求的数(无理数)。另一方面，如果c是有理数，设d=c+t，这里t是上一段我们说到的无理数。根据之前的结论，d也是无理数。如果我们让t里面的n足够大，总可以保证d足够接近两个给定数a和b的平均值c，从而也位于它们之间。这样，我们看到无理数同样组成了一个稠密集。就像有理数，我们也可以推知数轴上任意两个数之间有无穷多无理数。

因此，有理数集和它的补集——无理数集，在一方面是类似的(它们在数轴上都是稠密的)，在另一方面却又不同(前者是可数的，后者则不是)。

康托尔三分点集

现在，对于有理数和无理数如何织就整个实数轴，我们已经有了更清晰的认识。有理数组成了一个可数集合，但同时也稠密地填充在数轴上。与之相反，康托尔三分点集(Cantor’s middle third set)是单位区间的一个不可数子集，但却是稀疏分布的。它是如下文的构造的产物。

接下来我们将会有一个令人惊喜的发现。取C中任意数c的三进制形式，将每个2都替换成1，我们就得到了单位区间中某个数的二进制展开式。这在C和I的所有数(写成二进制形式)之间建立了一一对应关系。由此可知，C的势与I相等。由于后者是一个不可数集(由康托尔对角线论证可得)，因此康托尔三分点集不仅是无穷的，还是不可数的。

于是我们就有了一个集合C，从某个意义上讲它的大小可以忽略(测度为0)，但是用另一种方式估计，C又是巨大的，因为它与I——因而与整段实数轴——等势。

另外，与稠密集相去甚远，C是处处不稠密的(nowhere dense)。回忆一下，当我们说一个像有理数这样的集合是稠密的，我们指的是当我们取一个数a时，在a附近的一个小区间里总能找到有理数，不管这个区间有多小我们都能做得到。我们说a的任意邻域(neighbourhood)都包含有理数集的元素。康托尔集拥有完全相反的性质——不属于C的数在数轴上可能从来不会遇上C里的数，前提条件是它们将视野限制于所在位置附近足够狭窄的区域。想要看清这一点，取任一不在C中的数a，于是a的三进制展开式中至少有一个1：a=0.…1…，比如说第n位上的是1。a附近有一个足够小的区间，其中的任意数b的三进制展开式有不止前n位与a的相同，那么所有这些数都不属于怪异的集合C，因为它们的三进制展开式也都包含至少一个1。

另一方面，康托尔集的任何数a也并不会感到太孤独，因为当a观察数轴上任何包含它自己的区间J，不论多么小，a总能在身边的邻居中找到同在C里的元素(也有不在C中的数)。我们可以让给定区间J里的一个数b同时属于C，只需规定b的三进制展开式拥有与a足够多相同的位数，但又不包含1。实际上，J包含有不可数个C的成员。

总结一下，康托尔三分点集C拥有可能有的最大数量的元素，当C的成员左右看去的时候，它们的兄弟姐妹在周围到处可见。然而，对于不属于C的数，C就像不存在一样。在它们的邻域内，看不到一个C中元素的身影，而集合C本身的测度也为0。对它们来说，C几乎什么也不是。

丢番图方程

不过，当我们往反方向走时，产生了一条富有趣味的研究路线。我们要求不仅方程的系数是整数，并且解也得是整数。这里举一个经典的例子。

一个装着蜘蛛和甲虫的盒子里有46条腿，问两种生物各有多少只？这个小小的谜题可以用试错法轻松解决，但是仔细观察下面两点，我们可以学到些东西。第一，它可以被一个方程来表示6b+8s=46。第二，我们只对这个方程的某些种类的解感兴趣，即甲虫(b)和蜘蛛(s)的数量都是整数的解。一般来说，当我们只限定于搜寻特殊类型的解时，相应的方程组就被称作丢番图方程(Diophantine equation)。通常情况下我们要找的是整数或是有理数解。

要求解本例中这样的线性丢番图方程，有一个简单的方法。首先，将方程除以系数的最大公因数。在这个例子中，系数是6和8，因此它们的最大公因数是2。消去这个公因数2之后，我们得到一个等价的方程——也就是说一个有同样解的方程：3b+4s=23。如果做完这次除法之后，右侧不再是整数，那就表明该方程没有整数解，我们可以就此罢手。下一步骤是取系数当中的一个(通常用最小的那个，因为这样最简单)，并将方程用它的倍数来表达。这里最小的系数是3，我们的方程可以写成3b+3s+s=(3×7)+2。整理后我们得到s=(3×7)-3b-3s+2。这样做的目的在于揭示出s有3t+2这样的形式，这里t是某个整数。将s=3t+2代入我们的方程，整理出b的表达式。我们得到

3b+4(3t+2)=23→3b=15-12t→b=5-4t.

现在，我们有了丢番图方程完备的整数解：b=5-4t，s=3t+2。t选择任意一个整数值都给出一组解，而所有整数解都具有这样的形式。

当然，我们的原始问题还有附加的限制条件，即b和s两者都大于等于0，因为不存在负数个蜘蛛或者甲虫。因此，只有两种可行的t值，t=0或t=1。这给了我们两组可能的解，5只甲虫和2只蜘蛛，或者1只甲虫和5只蜘蛛。假如我们对原题咬文嚼字，认为两种生物都必须有不止一只[6]，那么我们便得到传统的答案：5只甲虫和2只蜘蛛。

这种类型的问题称作线性的(linear)，因为它所涉及方程的图像由排成一条直线的无穷多个点组成。丢番图问题则是要找到这条直线上的栅格点(lattice points)，也就是那些两个坐标值都是整数的点。或者，如果我们只允许正数解，则只能是在第一象限里面的栅格点。

然而，一旦我们允许方程中出现平方和更高次方，对应的问题的性质会变得更加多样化和有趣。在这种类型中的一个经典问题上我们已经获得了完整的解，那就是找出所有的勾股数[7](Pythagorean triple)：满足a2+b2=c2的正整数a，b，c。当然，得名勾股数是因为你可以用这三个正数作为边长画出一个直角三角形。典型的例子是(3， 4， 5)三角形。给定任意勾股数，我们只需要将它们乘上任一正整数，就能得到更多的勾股数，因为勾股方程依然成立。例如，我们可以将刚才的例子翻倍，得到(6， 8， 10)这组数。不过，这给出的是一个相似三角形，它和原来那个有一模一样的比例关系，因为改变的只是整体尺寸而不是形状。给定第一个三角形，我们只需用原来单位的一半来测量边长，就可以使三角形的尺寸数值变为之前的两倍，也就得到了第二组勾股数。但是，也有本质上不一样的勾股数，比如(5， 12， 13)和(65， 72， 97)。

所以，要描述所有的勾股数，只需要描述最大公因数为1的所有三元素组(a， b， c)就行了，因为一切其他的勾股数都仅仅是这些的放大版。方案如下。取任意一对互质的正整数m和n，其中一个为偶数。假设m表示两者中大的那个数。构造三元数a=2mn， b=m2-n2及c=m2+n2。那么这三个数a，b，c就给出一组勾股数(这里用代数可以轻松验证)，并且这三个数没有公因数(也不难检验)。上面的三个例子就可以这样得到。在第一个例子里取m=2和n=1，第二个里取m=3和n=2，而最后一种情况我们有m=9，n=4。要检验反过来的命题需要更多努力：任何勾股数都可以用这种方法来生成，只需取合适的m和n的值；另外，这样的表示法还是唯一的，于是两对不同的(m，n)不可能产生同样的勾股数(a，b，c)。

相应的立方和更高次的方程却没有解：对于任何指数n≥3，没有正整数组x，y和z满足xn+yn=zn。这就是著名的费马大定理(Fermat’s Last Theorem)。未来它可能被称作怀尔斯定理，因为它是由安德鲁·怀尔斯爵士[8](Sir Andrew Wiles)在20世纪90年代最终证明的。甚至是在立方的情况下，这也是一个非常困难的问题，这是由欧拉首先解决的。不过，可以相对简单地证明两个四次方数之和不可能是一个平方数(因此当然不可能是一个四次方)。并且这就足以将原来的问题简化为指数n是一个素数p的情况(意思是如果我们对所有素指数的情况解决了这个问题，便可以立即得到一般的结论)。确实，在19世纪的时候，指数n为所谓的正则素数(regular prime)的情形得到了证明。然而，要实现问题的完全解决，还得等到怀尔斯解答了一个叫作谷山-志村猜想[9](Shimura-Taniyama Conjecture)的深刻问题之后。

斐波那契和连分数

回忆一下斐波那契发现的数列，1， 1， 2， 3，5， 8， 13， 21，…，我们在第5章中进行了介绍。从这个数列中取一对相邻的数，将它们的比写成1加上一个分数。现在，如果我们“埃及化”这个分数，也就是反复地让分数部分的分子分母同除以分子，就会出现一个引人注目的规律。比方说

我们得到了一个仅含有1的多层分数，并且随着计算持续进行，选出的这对相邻数之前的每对斐波那契数的比值会依次出现。这样的现象每次都会发生：正是由于这些数的定义，每个斐波那契数都比下一个的两倍要小，因而相除之后会得到商1，余数则是前一个斐波那契数。你也许想起来，相邻斐波那契数的比值趋近于黄金分割比——τ，这说明τ是仅由1构成的连分数的极限值。

从这个过程中产生的连分数本身就有重要意义。当用有理数来近似任意一个无理数y的时候，我们会自然地使用y的小数表示。这非常适用于一般的计算，但是在数学上，依附于一个特定的底数却不太自然。本质问题在于，我们能多好地用分母相对较小的分数来逼近y。有没有一种办法，能找到一系列的分数，既能高精度逼近y同时又保持较小的分母，在这两个矛盾的要求中取得最佳平衡？答案就在于一个数的连分数表达形式，并通过越来越多层的截断实现这一目的。

黄金分割比所提供的这个特殊例子打开了一条新的思路，即我们也许能表示其他的无理数，当然不是用有限的连分数(它们自己显然是有理数)，而是用无穷连分数。但是，怎样才能产生一个数a的连分数呢？为了看清这个过程，读者朋友可能需要容许我玩一个小小的代数上的把戏，下面就是做法。

接下来我们得到

在用有理数对无理数的逼近中，连分数的重要性在于所谓的收敛子[12](convergent)，即原始数的有理数近似，它们是通过截取某一层以前的连分数表达式，再求出相应的有理数来得到的。它们代表了对原始数的最优近似，也就是说任何更好的近似的分母都将比收敛子的分母大。黄金分割比的收敛子是斐波那契比值。由于τ的连分数表达式中每一项都是1，这些比值收敛的速度被尽可能地延缓了。出于这个原因，没有比τ更难用有理数逼近的数了，而斐波那契比值是你能取得的最佳结果。

[1]　通常称实数集(直线上点的集合)为连续统。

[2]　有时也称基数。

[3]　恩斯特·策梅罗(Ernst Friedrich Ferdinand Zermelo)，德国数学家。亚伯拉罕·弗兰克尔(Abraham Fraenkel)，以色列数学家。

[5]　在三进制中，0.1可用0.0222…表示。

[6]　在英文原题中，“蜘蛛”和“甲虫”都使用了复数形式的名词，即它们各自不止一只。

[7]　勾股数或称商高数或毕氏数。

[8]　安德鲁·怀尔斯爵士(Sir Andrew Wiles)，英国数学家，居于美国。

[9]　谷山丰和志村五郎，均为日本数学家。

[10]　又称最简分数。

[11]　该符号表示向下取整。

[12]　又称渐进分数。