反对角线：从理发师悖论到计算机的极限

马耀基

1、理发师悖论

   先看两个著名的悖论。

理发师悖论

村子里有两类人，第一类人自己给自己刮胡子，第二类人不给自己刮胡子。

村里的理发师给自己立了一条规定：他给并且只给第二类人刮胡子。

按这条规定，理发师该不该给自己刮胡子呢？

如果他给自己刮胡子，他属于第一类人，按规定他不应该给自己刮胡子。

如果他不给自己刮胡子，那他属于第二类人，所以他又应该给自己刮胡子。

因此，他给自己刮胡子当且仅当他不给自己刮胡子。

还有个类似的悖论叫书目悖论。

书目悖论

有一些书，它的内容里出现自己的名字，而另一些书则不出现自己的名字。

现在有一本书，它的内容就是收录书的名字。它只包括第二类书的名字，即那些不出现自己名字的书。

这本书要不要把自己收录进去呢？如果它把自己收录进去，按规定它属于第一类书，所以它不应该自己收录进去。而它不把自己收录进去，又可推出它应该把自己收录进去。

2、反对角线方法

这两个悖论本质上是相同的，下面以书目悖论为例，分析这两个悖论产生的原因。

假设一共有四本书，分别是金庸的《碧血剑》《连城诀》《鹿鼎记》《侠客行》。根据它们的内容是否出现书的名字，绘制了下面这个表格。

表格里√表示行里的书出现了相应列的书的名字，X则表示不出现名字。比如第二行第一列是《碧血剑》，其他几列分别是√、X、√、√，表示《碧血剑》这本书里出现了《碧血剑》《连城诀》这两个书名，而《鹿鼎记》《侠客行》这两个名字则没出现。

我们把收录书名的这本书叫《目录书》，因为《碧血剑》这本书出现了自己的名字，所以《目录书》不收录它，《连城诀》没出现自己的名字，所以目录书收录它，由此类推。

《目录书》那一行的符号，实际上是将相应列的对角线上的符号取反，比如对角线上《碧血剑》那一列的符号是√，则《目录书》在相应列上的符号为X，对角线上《连城诀》那一列的符号是X，所以《目录书》在相应列上的符号为√。

可见，目录书必然不同于那四本书里的任何一本，因为它和任何一本最少有一个地方不同。

因为《目录书》也是一本书，所以把它添加到表格的列中。问题是：下表右下角那个方格，应该是√还是X。它是将对角线上的记号取反，现在对角线上的记号就是它自己。自己和自己相反，这是矛盾的。

理发师悖论和书目悖论的根源是这样的：给定一个集合，我们用反对角线方法构造出一个和原集合所有元素都不同的新元素（简称反例），当这个反例又属于原来的集合时，就出现了悖论。

举个假想的例子，我们要画一棵树，使得它和世界上所有的树都不一样。我们把全部的树编号，然后这样设计这棵新树：它在高度上跟1号树不同，叶子数量跟2号不同，树枝长短跟3号不同，……，总之它和每一棵树都最少有一个地方不同。显然，这将是一棵与众不同的树。但画完后我们发现它竟然和某棵树一模一样，咄咄怪事！悖论！

3、罗素悖论及其他

利用反对角线方法，我们可以构造出很多悖论。最有意思的还是数学悖论，因为数学出现悖论事关重大，可能会动摇科学的大厦。最有名的数学悖论可能是英国哲学家罗素发现的悖论了，它实际上也是用反对角线方法构造出来的。    

罗素悖论

集合有两种：自属集和非自属集。自属集是指集合本身是自己的一个元素，而非自属集则相反，自己不能作为自己的元素。比如{1}就是非自属集，因为{1}不是{1}的元素。而非石头集就是自属集，因为非石头集是所有不是石头的东西所组成的集合，而非石头集本身也不是石头，所以它也是非石头集的元素。

所有的非自属集放在一起组成一个集合（简称集合A），请问集合A是自己的元素吗，容易推出如果A属于自己则A不属于自己，如果A不属于自己则A属于自己。

如果用数学语言叙述罗素悖论，则两行就够了。

理查德悖论

理查德悖论和前几个悖论有点不同，前几个悖论如果用表格表示，它第一行和第一列的元素是相同的，比如书目悖论中第一行和第一列都是书名。而理查德悖论不是这样，它要用到编码方法才能构造反例，这个方法在后面会用到。

理查德是一位中学教师，他发现了下面的悖论。

自然数的某些性质可以用有限长的语句描述，比如“能被2整除”，“大于5”等。现在给每个性质分配一个号码，这个号码也是自然数。

有的性质的编号数本身不具有它所编号的性质，这种数称为理查德数。举个例子，假设“能被2整除”这个性质被编为7号，那7就是理查德数，因为它不能被2整除。

有的性质的编号数本身具有它所编号的性质，这种称为非理查德数。假如“大于5”这个性质被编码为10，则10就是非理查德数。

可见，理查德数和非理查德数，也可用有限长的语句描述，它们本身也应该有编号。假设“是理查德数”这个性质的编号为n，现在问n是不是理查德数？容易得到：

如果n是理查德数，则它不是理查德数。如果n不是理查德数，则它是理查德数。

贝里悖论

一位叫贝里的图书管理员也提出了一个悖论，罗素称这是理查德悖论天才般的简化。它是这样的：

考虑“不能用少于100个汉字描述的最小正整数”这句话。

假设这句话描述了一个数，则这个数是不能用少于100个汉字描述的，但这句话本身少于100个字，矛盾。所以它没有描述这个数。

假设这句话没有描述一个数，这又与事实不符，因为它确实描述了一个数。

4、反对角线方法的应用

我们在最后一部分再讨论如何解决这些悖论，这部分先讨论反对角线法在无穷集合上的应用。无穷集合理论是德国数学家康托创建的，也是他先把反对角线方法用到这个理论上。无穷集合有很多有趣的性质，数学家希尔伯特曾用无穷旅馆的例子来说明它们：

设想一家旅馆，里面有无限个房间，所有的房间都客满了。这时来了一位新客。按照日常的经验，旅馆客满就安排不下新的客人了，但无穷旅馆不一样。旅馆主人把1号房间的旅客移到2号房间，2号房间的旅客移到3号房间，3号房间的旅客移到4号房间等等，这样继续移下去。就这样无中生有般空出了1号房间，新客人就被安排住进了这个空房间。

把客人安排进旅馆，本质上是给每人分配一个不同的自然数。所有的客人组成了一个无穷集合，加进来一个客人还是无穷集合。这两个无穷集合每个元素都能分配一个不同号码，即这两个集合的元素都能和自然数形成一一对应，用数学的话来说这两个无穷集合都是可数的。

那是不是任意一个无穷集合都是可数的呢？下面来讨论这个问题。

   定理1：可以给每个整数都分配一个不同的自然数号码，即整数是可数的

看起来不可能做到，因为整数有正有负，按照定义自然数就是正整数，它只是整数的一部分。但细想这件事不难，把所有的整数按下列顺序排序：

0，1，—1，2，—2，3，—3，……

排第一位的分配号码 1，第二位的分配2，第三位的分配3，……，这样问题就解决了。

用专业的话，整数集和自然数集的元素能形成一一映射。整数虽然包含了自然数，但严格来说两者是一样多的，因为按照数学定义，两个集合的元素一样多，就是指两者的元素能建立一一对应。

定理2：不可能给每个自然数集合分配一个不同的自然数号码

假设可以做到，那么我们用S₁、S₂、S₃……来表示这些集合。把它们按顺序排列，用下面的表格来表示它们的元素，其中√表示相应列的数字是相应行那个集合的元素，X则相反。比如S₁包括1和3，不包括2和4。

我们可用反对角线方法构造出一个新的集合，这个集合和表格里所有的集合都不相同。而按照假设，所有的自然数集合都在表格里了，矛盾。

所以假设错误，我们无法给每个自然数集合都分配不同的号码。

   上面的证明可以推广：任一集合都无法和它的幂集的元素形成一一映射。

定理3：不可能给每个实数分配一个不同的自然数号码

只要证明无法给[0,1)之间的实数分配不同的号码就行了。

假设可以做到，那将它们排列如下：a₀、a₁、a₂、a₃、a₄、a₅……。

每个小数都可以用无穷小数表示，比如0.1=0.100000……，后面全是0。所以序列中的每个数可以展开如下（下面的每一个a_mn都是0到9中的一个数）：

用反对角线方法构造新的小数D，D的每一位小数都和对角线上的元素不同，这样得到的D不同于序列中的任一个小数。而D又在[0,1)之间，矛盾。所以不能给[0,1)的实数分配不同的号码，所以不可能给每个实数分配不同的号码。（注释1）

想一想，实数可以按自然数顺序排序的假设在证明中起到了什么作用？能不能把证明定理3的方法用于证明有理数不可能分配不同的号码，即定理2不成立，为什么？

定理4：存在无法用计算机计算的函数

首先说明，可计算、可用计算机计算、可用程序计算这些概念在这里是同一个意思。（注释2）另外，为了简单，我们这里考虑的函数，变量都是自然数。

我们知道计算机能做很多运算，比如能进行加法运算。进行加法运算实际上是计算z=x+y这个函数。一个计算z=x+y的程序，就是输入x和y的值，输出z的值，即如果输入2和3，它就输出5，输入3和4，它就输出7。函数z=x+y是二元函数，其中x、y是自变量，z是因变量。又比如，函数y=x²也是可以计算的，这个函数是一元函数，x是自变量，y是因变量。

无法计算的函数，是指不存在这样的程序：当输入自变量的值时，程序总是输出这个函数的因变量的值。

我们给所有的计算机程序分配自然数号码（或叫编码），就像每个人都有不同的身份证号码一样，每个程序也有不同的号码。这里编码的不单是指现在世界上存在的所有程序，而是指理论上所有可能的程序，这样的程序数量显然是无限的。（注释3）

程序能够编码，这是需要严格的证明的。这里省略证明，我们直接接受这个结论。

因为所有的程序都是可以编码的，所以所有计算一元函数的程序也可以编码。现在将所有计算一元函数的程序编号，将这些它们记为P₁，P₂，P₃，……P_n，……，每个程序对应着一个可计算函数。这些程序对应了所有可计算的一元函数，因为按前面的定义，能计算的函数就是能用程序计算的，而所有计算一元函数的程序都在这里了，所以可计算的一元函数也全在这里。

现在反对角线法构造函数d：

d(n)=2，如果P_n(n)=1，

d(n)=1，如果P_n(n)≠1，或者P_n(n)无定义。

（P_n(n)=1，表示当输入为n时，程序P_n的输出是1。）

函数d与任何一个程序所计算的函数都不同，所以它是任何一个程序不能计算的。

容易证明，如果d是可计算的将导致矛盾。假设它是可计算的，则计算它的程序必然分配有号码，假设是s，则函数d就是程序P_s计算的函数，P_s(s)的值是什么？按照定义，如果P_s(s)=1，d(s)≠1，但程序d就是程序P_s，所以矛盾。同样，如果P_s(s) ≠1，也有矛盾。

这里能够构造出无法计算的函数d，本质原因是函数的数量比程序多。

5、进一步的讨论

反对角线方法，是从一个给定集合构造新元素（即反例）的方法。当这个反例又属于原来的集合时，就出现了悖论。

那怎么解决悖论呢？有人认为反例实际上不存在，比如在理发师悖论和书目悖论中，符合规则的理发师和目录书不存在。但这个方法不能用于罗素悖论，因为对任意一个性质，所有符合这个性质的元素就组成一个集合，这叫概括原则。解决罗素悖论有两种主要思路。第一种思路是不允许数学命题出现自指，从而无法构造反例。罗素自己采用了这种思路，他认为自指会出现恶性循环，所以禁止自指，在此基础上他建立了类型论。另一种思路是将反例排除在原集合之外。比如有的人不承认概括原则，认为把所有非自属集放在一起不是一个集合，所以构造出来的反例不是原来集合中的元素，因此不构成悖论。按这种思路，数学家策墨罗重新规定了成为集合的一些条件，建立了公理集合论，这理论里不会出现罗素悖论。

使用反对角线法构造悖论关键在两点：1、能够构造反例，2、反例属于原集合的一员。

要构造反例，必须先知道对角线上的值，所以必须要知道表格中第一行的元素和第一列的元素。如果第一行和第一列不仅元素相同而且排列顺序相同，我们一定能构造出反例。理发师悖论、书目悖论、罗素悖论都是这样，比如书目悖论中，第一行和第一列都是那些书名且顺序相同。如果第一行和第一列的元素不同，第一行的元素是自然数，比如理查德悖论，这时第一列的元素必须能够按自然数顺序排列（即可数的），才能构造反例。比如构造不可计算的函数d时，要用到对角线P_n(n)的函数值，这需要先给程序编号才知道P_n是什么，不知道P_n就无法构造反例。

在上文证明定理2、3、4时，先假设第一列的元素是可数的，然后构造反例出现矛盾，从而推出假设是错的。这里假定了数学不会出现矛盾。实际上在建立公理集合论后，人们还没有在数学上发现矛盾。

有时候虽然能构造反例，但反例不属于原集合的一员，就不会出现矛盾。比如将所有有理数排列，然后用反对角线法构造一个反例，但由于我们不能保证这个反例就是有理数，因此不能用反对角线法证明有理数不可数。

注释：

1、这里的证明是不严格的。因为同一个小数有不同的表示方法，比如0.100000……=0.099999……。用反对角线方法构造出来的D，看上去虽然和序列中的任一个小数不同，但不能保证它们就不是相同的小数。不过对上面的证明稍作修改，就可以弥补这个漏洞。

2、这篇文章说的计算机是指图灵机，我们现在所用的计算机本质上都是图灵机。按照丘奇图灵命题，可计算函数和图灵机可算的函数这两个概念是等价的。

3、不同的程序，功能可以是相同的。比如程序A，对输入的变量先加1，再加2，然后将结果输出。程序B则是先加2，再加1。程序A和B是不同的，所以它们分配到的号码是不同的，但是功能相同。

相关文章

说谎者悖论：从鳄鱼难题到数学证明的极限