数学是理性的语言，是所有人类发明中最成功的一个，科学的很大一部分是以数学和逻辑为基础的。然而自古希腊时代起，数学在不断突破极限的过程中，也不断发现无法解决的问题。
我曾经对数学产生过一种感觉，感觉我见到了它的所有，比深处更深之处展示在我的面前，那里是无尽的深渊。我看到，正如某个人看到金星凌日——甚或伦敦市长就职游行那样，某个量穿过无限，将它的符号从加变成减。我看到了这是如何发生的，以及为什么背叛不可避免：以及一个步骤如何牵扯到所有其他步骤。这就像是政治。但这发生在晚餐之后，我就随它去了！
——温斯顿·丘吉尔（Winston Churchill，1874—1965）
我一旦理解了这些原则，就永远放弃了对数学的追求；我也不会对自己的半途而废感到后悔，因为我不能让自己的心智在严格论证的习惯之下变得僵硬，这对于道德证据的更细微的感受极具破坏力，而后者决定了我们生活的行为和意见。
——爱德华·吉本（Edward Gibbon，1737—1794）
新数学：标准数学最近被认为是陈旧过时的，因为人们发现多年以来我们一直将数字五倒着写。这导致计数作为从一到十的方法被重新评价。学生们被教授了布尔代数的先进理念，对从前不可解的方程使用威胁报复的手段处理。
——伍迪·艾伦
数学是纯粹理性的象征。科学的很大一部分是以数学和逻辑为基础的。在某种意义上，数学就是理性的语言。它是所有人类发明中最成功的一个。然而正如我们即将看到的那样，它也有自己的局限。
本章第1节介绍了古希腊时代出现的一些局限。第2节包括对伽罗瓦理论的简要介绍，它是现代数学中的全部领域，目的是指出某些问题不可能用通常的方法解决。在第3节中，我们回到使用计算机解决问题的讨论中，并指出数学中的几个问题是无法通过计算解决的——无论是机械计算还是人力计算。第4节讨论了逻辑自我指涉的某些方面，包括哥德尔著名的不完备定理。本章最后对逻辑和公理体系的某些技术和哲学方面进行了讨论。
Churchill（1996，27）。
Gibbon（2001，142）。
Allen（1993，62）。
古典数学的局限
在毕达哥拉斯的追随者们看来，他们的前成员希帕索斯（Hippasus）必须被杀死。他必须被扔进海里，以免他继续亵渎并揭露他们所有的秘密。希帕索斯完全是不理性的！
在古希腊时代的世界，萨摩斯岛的毕达哥拉斯是一个有趣的人物。他生活在公元前6世纪，对古典时代和中世纪的世界都有重大影响。毕达哥拉斯——哲学家，神秘主义者，音乐鉴赏家和宗教领袖——是为了研究数学本身而不是为了它的应用而研究数学的第一人。这让他成为世界上第一个纯数学家。他还发现了音律和谐与数学之间的关系。毕达哥拉斯对哲学和数学的进步产生了巨大的影响。
毕达哥拉斯和他的大批拥趸信奉一条核心教义，他们相信整个世界都被整数或整数的比例支配和描述。这些比例被认为是唯一理智或“有理性的”数字。换句话说，他们不相信我们如今称为无理数的数字。在他们看来，有理数是唯一存在的数字。
在这种世界观下本来一切正常，直到毕达哥拉斯的一个学生出现，他的名字叫梅塔蓬图姆的希帕索斯。希帕索斯思考了一个普通的正方形，它的边长为1，如图9.1所示。
图9.1 拥有无理数斜边的正方形
根据毕达哥拉斯的著名直角三角形定理，我们得到
x2+y2=z2
或
在图9.1的正方形中，x和y的长度都是1。这意味着对角线z的长度是。这本来也没什么，但希帕索斯接着证明了这个常见的数字，2的平方根，它不是一个有理数。这个很容易描述且无处不在的数字是无理数的第一个已知的例子。这对他同时代的人而言是一个令人震惊的结果。在某种程度上，这是对那个时代的数学局限性的第一次违背。
传说毕达哥拉斯和他的追随者对希帕索斯的发现很不安。他们害怕他会将自己的发现透露给其他人，从而暴露他们的信仰的缺陷。这个兄弟会做了唯一一件他们认为可以做的事：他们带上希帕索斯乘船出海，然后在海上把他扔下了船，希望他带着自己的秘密长眠于水底。
目前还不知道希帕索斯用了什么证明方法指出2的平方根是一个无理数。然而有一个非常优雅的证明值得我们思考。这个证明是几何学的，没有很多让人头疼的复杂方程。它是我们已经熟悉的反证法。如果我们（错误地）假设2的平方根是一个有理数，那么我们就会发现矛盾：
2的平方根是有理数⇒矛盾。
如果是一个有理数，那么就会存在两个正整数之比等于2的平方根。让我们假设最小的两个这样的整数是a和b。即，
等式两边同时求平方，得到
两边同时乘以b2，得到
2b2=a2。
让我们从几何学的观点看看这个方程。它意味着存在一个边长为a的大正方形（面积为a2）和两个边长为b的小正方形（每个的面积为b2），且两个小正方形的面积之和正好等于大正方形的面积，如图9.2所示。
图9.2 两个小正方形的面积恰好等于一个大正方形
此外，如果我们假设a和b是最小的这种数字，那就不存在更小的数字令这个命题为真。
当这两个小正方形被放进大正方形时，一定会有一块重叠区域和两块缺失区域，如图9.3所示。
图9.3 更小的正方形
图9.3有两个问题：重叠区域表明我们将同一块区域计算了两次，此外还有两个较小的区域是a方块没有被两个b方块中的任何一个覆盖的区域。要想让大正方形的面积等于两个小正方形面积之和，两个缺失部分的总面积就必须和重叠部分的面积相等，也就是说，两个较小（缺失）正方形的面积必须等于较大（重叠）的正方形。这些正方形肯定比我们最初的正方形小。但是请等一下！我们已经假设我们使用的是令两个小正方形面积之和等于大正方形的最小的数字，但是现在我们却找到了更小的数字。这是一个矛盾。我们对这些数字存在的假设肯定存在问题。结论：2的平方根不是一个有理数。它是一个无理数。
自古典时代以来，许多其他数学问题也挑战了人类的理性。这些问题在中世纪继续被人探索，最终在现代被证明是无法解决的。
图9.4描述了自古典时代以来最著名的三个作图难题。
图9.4 （a）使圆成方，（b）三等分角，以及（c）加倍立方体
问题（a）称为使圆成方（squaring the circle）。给定某个面积一定的圆，要求用一把直尺和一个圆规构造出一个面积与该圆相等的正方形。想要完成这种作图，就必须能构造出与数字π成比例的线段。另一个著名的问题（b）是将一个给定的角分成相等的三份。这个问题称为三等分角（trisecting an angle）。第三个问题（c）称为加倍立方体（doubling the cube），给定某个体积一定的立方体，要求做出一个体积是它两倍的立方体。要构造出这样的立方体，需要先构造出与2的立方根成比例的线段。我们很快就能看到，所有这三种作图都是只使用直尺和圆规无法完成的。
古希腊人称，能够用直尺和圆规构造出来的线段的尺寸对应的数字称为可造数［constructible number，又称欧几里得数（Euclidean number）］。所有正整数都可以这样构造出来。我们可以用这两种工具进行乘法和除法运算，因此全部有理数都是可构造的。不过有些无理数也是可构造的。例如，如果你做出一个边长为1的正方形，那么它的对角线就是2的平方根，这个数字可以构造。
现代数学家定义了一类范围更大的数字，称为代数数（algebraic numbers）。这些数字是下面这种多项式方程的解
anxn+an–1xn–1+…+a2x2+a1x+a0=0
其中所有的系数都是整数。由于每个有理数a/b都是方程
bx–a=0的解，
所以每个有理数都是代数数。已知每个可造数都是代数数。然而代数数比可造数多。例如，2的立方根就不是可造数，但它是代数数，因为它是x3–2=0的解。
然而，并非每个实数都是代数数。不是代数数的实数称为超越数（transcendental numbers）。超越数不是代数方程的解。在某种意义上，这些数字是无法用通常的代数运算描述的。如果一个数字是超越数，那它就不是代数数，更不可能是可造数。很难证明一个数字是超越数。直到1844年，数学家才证明超越数是存在的。然后在1882年，费迪南德·冯·林德曼（Ferdinand von Lindermann，1852—1939）证明了π是超越数。这表明π不可造，因此无法用直尺和圆规使圆成方。三等分角和加倍立方体也已经被证明是不可能的。
已知的超越数很少。也许有人会说既然已知的例子这么少，那么真实存在的超越数也应该很少。但是只要进行简短的计数论证，就能指出这个假设完全是错误的。思考图9.5中数字类型的层级。
图9.5 实数的不同类型
每个代数数都有某个整数多项式方程与之相对应（它是这个方程的解）。使用某种聪明的计数方法（例如我们在第4章第2节中见到的之字形证明或项链证明的方法），就能证明整数多项式方程的集合是可数无限的。这表明代数数的数量只不过是可数无限的。我们知道实数是不可数无限的，因此实数中的超越数也是不可数无限的。看待这一点的另一种方式是，我们能用普通运算描述的数字——代数数——是可数无限的，但是不能用普通运算描述的数字就要多得多。从这里我们就能判断，不可造的形状和数字的数量比可造的形状和数字的数量多得多。
有理数和无理数的区别并不只是古希腊哲学和宗教的主题。今天的我们也可以有类似的讨论。在我们的想象中，世界以某种方式被实数（和复数）描述和控制。这张桌子长5.82252932…米；气温是67.19153228…华氏度；这个球落地所需的时间是5.83245…秒。然而，人类思维不能得到一个完全随机的实数（复数）。我们的大脑是有限的机器，只能处理整数或两个整数的比例（即有理数）。类似地，计算机能够处理的数字类型也是受限的。这种“真实世界”和我们关于“真实世界”所能知道的内容的不对等，正是理性的一种真实的局限。至少有两种方式可以绕过这种局限。首先，我们可以说真实世界是离散的，因此适合用有理数来描述。正如我们在前文中看到的那样，量子力学（第7章第2节）和齐诺的智慧（第3章第2节）向我们保证宇宙是离散的，在普朗克长度、普朗克能量和普朗克时间之外不存在任何信息。因此有理数是描述和理解“真实世界”所需的一切。连接人类/计算机能力和“真实世界”之间差异的另一种方式是意识到虽然我们不能在自己的思维中得到随机实数，但我们仍然能处理这些数字。我不能在自己的头脑中得到π和e的所有小数位的数字，但我可以完美地描述这些数字。π是一个完美圆形（只存在于思维而不存在于真实世界）的周长与其直径之比。另外，为了描述随机实数，我有得到我需要的尽可能多位的数字的方法。从这个意义上说，存在描述实数的方法。我敢肯定关于这个主题的最终意见还没有出现。
几乎可以从这两种构造方式中看出欧几里得的前四条几何公理（见第8章第2节）。
伽罗瓦理论
巴黎。1832年5月29日。一名年轻的男子正在发狂似的写一封长信。他必须写得很快，因为需要写下的东西很多，而他知道自己第二天就会死于非命。这封信是对他的数学研究的总结，他想在为时太晚之前将这些内容全部写在纸上。他在信的最后恳求他的朋友“向（闻名世界的数学家）雅可比或高斯征求他们的公开意见，不是让他们判断这些定理的真实性，而是评价它们的重要性。我希望将来有人能够解决所有这团混乱”。第二天，他为了捍卫对一名女子的爱情参加了一场决斗，结果正如他所预料的，他受了致命的重伤。他被带到当地医院之后只活了一天。据说他最后的遗言是说给他哥哥的：“别哭，阿尔弗雷德！我需要我所有的勇气才能在20岁死掉。”这个年轻人的名字是埃瓦里斯特·伽罗瓦（Évariste Galois），而他的工作将永远是现代数学的重要部分。
这封信里有什么？20世纪最伟大的数学家之一赫尔曼·魏尔（1885—1955）写道：“如果按照它包含的信息的新颖性和深刻性来看，这封信或许是人类所有文献中最重要的写作。”或许魏尔在做这个评价时有些夸张了。不过伽罗瓦的工作中的确包含着对现代数学和物理学至关重要的思想。一个20岁的年轻人能够说出什么如此重要的东西呢？
伽罗瓦出生于1811年，当时法国大革命之后的狂热气氛还没有散去，这让伽罗瓦度过了短暂而悲剧性的一生。他的父亲曾经是巴黎郊外一个小城镇的市长，后来因为一场激烈的政治争端自杀。伽罗瓦是一个满怀激情且心思复杂的年轻人，他的成长过程很不容易。他很年轻的时候就痴迷于数学，以至于荒废了其他学科的学习。他没有考上法国最负盛名的巴黎综合理工学院（École Polytechnique），最终进入了一所二等的学校，但他的聪明才智基本上都被他的老师们误解了。伽罗瓦提交了两篇用来发表的论文，结果都被编辑弄丢了。后来他参与了激进的政治团体，导致自己被学校开除。目前还不清楚这次致命决斗的另一方是谁。引起决斗的女子的身份也未知。如果这位天才没有如此悲剧式地英年早逝的话，他还能完成什么样的工作呢，对这个问题只能猜测了。
伽罗瓦的工作和多项式方程的求解有关。在我们可以理解他的贡献之前，我们必须先研究一些历史。思考下面这个简单的方程：
ax+b=0。
此类方程称为“线性”方程，大多数九年级学生都知道如何求x：
x=–b/a。
更复杂的“二次”方程是下面的形式：
ax2+bx+c=0。
古典时代的人们就已经知道了这种方程的求解方法，而且一直到现在高中学生还在学习使用“二次公式”求二次方程的解。二次方程实际上有两个解：
及
注意这些公式使用了加法、减法、乘法、除法、平方和平方根等计算方式。
那么“三次”方程呢，如
ax3+bx2+cx+d=0？
这种方程的求解存在标准公式吗？16世纪，杰罗拉莫·卡尔达诺指出这个方程有三个解，而且给出了相当复杂的公式。这些公式使用了普通的计算方式，包括平方根和立方根。
继续下去，我们可以对“四次”方程提问：
ax4+bx3+cx2+dx+e=0。
洛多维科·费拉里（Lodovico Ferrari，1522—1565）和尼科洛·丰塔纳·塔尔塔利亚（Niccolò Fontana Tartaglia，1499—1557）发现了这些问题的解。许多读者一定很想知道我们是否会写下这四个可能的解对应的四个公式。与其将它们写下来，不如说这些“四次公式”使用了普通的计算方式，平方根、立方根和四次方根。
那么“五次”方程呢？
ax5+bx4+cx3+dx2+ex+f=0。
事情在这里变得更有趣了。也许有人会觉得存在由普通计算方式和从平方根到五次方根组成的“五次公式”。这是不对的！不存在这样的公式！19世纪初，保罗·鲁菲尼（Paolo Ruffin，1765—1822）和尼尔斯·亨利克·阿贝尔（Niels Henrik Abel，1802—1829）证明了不存在这种使用普通计算方法和方根的普遍性公式。这意味着对于每个a,b,c,d,e和f组成的五次方程，永远都不会存在简单的求解公式。
这是数学局限性的又一个清晰的例子。
一般而言，这个问题是不可解的。然而某些五次方程却存在很容易找到的解。例如，
x5–1=0
有一个解为x=1。
这就是伽罗瓦的工作的核心。他能够使用某个给定五次方程的系数确定该方程是否能用普通运算求解。为了这个目的，伽罗瓦引进了群（group）的概念。群是一种以对称概念为模型的数学结构。伽罗瓦指出了如何将一个群与每个方程关联起来。在这些对称性的帮助下，他能够判断某给定五次方程是否能用普通计算的方法求解。当他对五次方程求解的工作得到理解之后，就立即被用在数学和科学的许多其他领域。
这种描述对称性的概念涉及现代数学、化学和物理学的一次重大革命。现代数学和科学的很大一部分研究的是不同形式的对称性，因此也就是不同类型的群。从这个角度我们终于可以理解魏尔对伽罗瓦的信的重要性的判断：现代数学和科学广泛地使用了伽罗瓦引入的观念。
如果要我们详细地介绍伽罗瓦理论（Galois theory）究竟是如何发挥作用的，我们一定会晕头转向。简要地介绍一下就足够了，这个理论首先描述了数学或物理系统的对称性。建立了这种对称性之后，研究者就要确保这种对称性在不同运算或物理法则下得到保持。一个系统不能违反自身的对称性，这个事实可以看作是对该系统的限制。
我们在上一节见到的不可解决的古典尺规作图问题都可以使用伽罗瓦理论证明不可解决。我们还没有讨论的另外一个问题是某些正多边形（regular polygon）是否可以用尺规作图构造。等边三角形和正方形是可构造的。正五边形呢？任意的正n边形呢？伽罗瓦理论告诉我们哪些正n边形可以使用尺规作图构造出来。所以如果
n=3,4,5,6,8,10,12,15,16,17,20,24,…,257,…或65537,…
那么与之相应的正n边形就是可构造的。相比之下，如果
n=7,9,11,13,14,18,19,21,22,23,或25,…
那么这样的正n边形就是不可构造的。
伽罗瓦理论描述的这种限制性体现在一个很有趣的例子上，就是经典的儿童游戏十五子棋（fifteen-piece puzzl）。这个著名的益智游戏有15个小方块安装在一个4×4的网格里。每次可以移动一个方块。目标是让这些方块按顺序排列，如图9.6的右半部分所示。然而某些开局排列方式无法得到按顺序排列的排列方式。只要简单地交换一下14和15的位置，就无法得到按顺序排列的排列方式。也无法从按顺序排列的排列方式返回到这种最初排列方式。
实际上这些方块可能的排列方式一共有十五的阶乘（15!）种。这些方式中正好有一半称为“偶排列”（even permutations），而另一半称为“奇排列”（odd permutations）。方块普通形式的移动有一种对称性，只能从偶排列变成偶排列，从奇排列变成奇排列。这些现象就是该系统的对称性。在图9.6中，一种排列方式是偶排列而另一种是奇排列，正是因为这个事实，所以无论我们进行多少次规则范围内的移动，都无法从一种排列方式变成另一种排列方式。
图9.6 无法完成的操作
还可以在魔方上看出与伽罗瓦理论有关的不可能性。拿出一个完全拼好的魔方，然后只扭动它的一个角（尽管这违反自然规律）。将它打乱，然后让一个观察力不佳的朋友（没看过这本书的）试着拼回原状。这是不可能完成的。一次扭动就让它无法拼回去，无论用多少步骤也不行。
总之，伽罗瓦的方程理论指出了乘法、除法、乘方和方根等普通计算方式在方程求解中固有的局限性。多年以来，数学家们开发出了使用微积分和无穷方法的其他技术，解决了这些问题中的一部分。所以伽罗瓦理论证明了某些问题无法用特定方式解决。类似地，如果允许使用直尺测量确切的长度，所有正n边形都可以构造出来。对于十五子棋游戏，只要将所有棋子都拿出来，再按照正确的顺序摆回去就很容易解决问题。通过作弊的方式总是能解决魔方问题——也就是将它一块块拆开，再按顺序拼装起来。这些都是绕过伽罗瓦描述的数学局限的简单招式。
法语原文：“Tu prieras publiquement Jacobi ou Gauss de donner leur avis,non sur la vérité,mais sur l’importance des théorèmes.Après cela,il y aura,j’espere,des gens qui trouveront leur profit à déchiffrer tout ce gâchi。”
法语原文：“Ne pleure pas,Alfred! J’ai besoin de tout mon courage pour mourir à vingt ans。”
Weyl（1952，138）。
我们在第8章见过这位天才。他发明了复数，而且是概率论的创建者之一。尽管一生非常悲惨，他仍然做出了巨大的成就。见Penrose（1994）的第5章第5节。
只是为了好玩，下面列出了其中一个求解公式：
为什么高中不教这个立方公式，真是显而易见了！
注意阿贝尔死的时候也很年轻。他也度过了悲剧的一生，在极度贫穷中死去。
无法通过计算解决的计算
想象一下，你找到了一份工作，是在某个建筑承包商手下打工，帮助客户设计他们梦想中的厨房。本来一切顺利，直到某个百万富翁的妻子走进来，想更换她厨房的地板。她不想要样式普通的方砖。她想要完全不同的东西。她想只用圆形。你向她指出圆形没法用，因为会留下无法填充的缝隙（如图9.7所示）。
图9.7 圆形不适合用来拼砖
正五边形呢（图9.8）？
图9.8 正五边形不适合用来拼砖
正五边形也不适合，但你没有放弃，又向她推销正六边形（图9.9）。
图9.9 正六边形很适合用来拼砖
这次没有空隙了。正六边形可以用来给房间拼砖。有些形状管用，有些形状不管用。图9.10展示了其他两种只使用一种形状的拼接方法。
很显然还有许多其他不同的形状可以不留任何缝隙地拼接起来。闻名世界的荷兰画家M.C.埃舍尔（M.C.Escher，1898—1972）制作了一些精彩的蚀刻版画，这些奇怪的形状彼此拼接在一起，不留出一丁点儿缝隙。
图9.10 其他只使用一种形状的拼接方法
思考图9.11中称为迈尔斯图形（Myers shape）的怪异形状。
图9.11 迈尔斯图形
有人也许会觉得形状如此奇怪的拼块不可能不留缝隙地覆盖地板。但是它完全可以做到这一点。如图9.12所示，一点问题也没有。
图9.12 一种使用迈尔斯图形的拼接方式
我们见到的大多数形状在拼接时使用的方法都会让拼接出来的图案自我重复。这种拼接方式被称为周期性的（periodic）。在周期性拼接中，同样的图案一次又一次地出现。然而某些形状拥有不存在重复图案的拼接方式。这种拼接方式被称为非周期性的（nonperiodic）。思考边长为2×1的矩形。这个形状很容易制造出周期拼接。然而我们也可以用这种矩形创造非周期拼接。将两个这样的长方形拼在一起就得到了一个正方形，这种正方形可以垂直或水平放置，如图9.13所示。由于任何图案都可以像这样制造出来，所以制造非周期拼接很容易。
图9.13 非周期拼接的两个例子
我们还可以在非周期性图案的问题上向前再走一步。存在某些形状的组合，当你用它们来拼接时，它们形成的图案永远不会是周期性的。换句话说，这些形状只能拼接出非周期图案。这些形状被称为非周期拼块（aperiodic tiles）。罗杰·彭罗斯（Roger Penrose）发现了两组这样的形状。其中一对是“风筝”和“飞镖”，另一对叫作菱形（rhombuses，见图9.14）。
图9.14 彭罗斯拼块：（a）风筝和飞镖，（b）菱形
这些形状有不同的颜色。当这些形状的拼接方式令相同的颜色对接在一起时，形成的图案就不会是周期性的。图9.15和图9.16就是这些非周期拼接的例子。
图9.15 使用风筝和飞镖的非周期拼接
图9.16 使用菱形的非周期拼接
让我们回到你帮别人拼厨房地板的工作上。如果存在某种方式能将不同形状的组合输入一台计算机，让它告诉我们这些形状能否拼接成一块没有缝隙的大地板（不用考虑边缘问题），那就太妙了。我们将这个接受形状并判断它们是否适合拼接的任务称为拼接问题（tiling problem）。能够解决拼接问题的计算机会对圆形和正五边形回答“否”，对正方形、等边三角形、正六边形、迈尔斯图形、彭罗斯的风筝和飞镖、彭罗斯的菱形回答“是”。这样的计算机程序对你的工作会是巨大的帮助。
哎，可惜的是这样的计算机程序不可能存在！20世纪60年代中期，罗伯特·伯杰（Robert Berger）证明了不存在能够解决拼接问题的计算机。
他证明这一点的方法是指出这个问题比我们在第6章见到的停机问题还难。停机问题问的是某个计算机程序是最终停机还是陷入死循环。如我们所知，任何计算机都不可能解决停机问题。既然拼接问题还要更难，那它也不能被任何计算机解决。
具体地说，可以将任何计算过程转化为一组形状，并使得当且仅当这些计算过程永不停机的时候，这些形状才能拼接出一个平面。也就是说这些形状能够拼接房间地板被等同于计算过程进入死循环。（我们在第6章第3节中见过这种转化过程。）我们可以用图9.17形象化地表示这种一个问题转化（或归约）为另一个问题的过程。
图9.17 将停机问题归约到另一个问题
在这幅示意图中，一个程序从左侧进入，然后转化成一组形状。假设（错误地）存在一台计算机可以判断一组形状能否形成无缝隙的拼接。那么我们就拥有一种方法可以判断某个程序是陷入死循环还是停机。由于我们已经知道没有任何方法能解决停机问题，于是我们就知道没有任何方法能判断拼接问题。
像拼接问题这样的计算机永远无法解决的判定问题叫作不可判定问题（undecidable problems）。虽然这些问题有清晰的定义和客观存在的答案，但任何计算机永远都无法解决它们。
值得强调的是，我们证明拼接问题不可判定的方法是将它归约到停机问题不可判定这个事实上。我们在第6章第2节中指出：
停机问题可判定⇒矛盾。
如图9.17所示，
拼接问题可判定⇒停机问题可判定。
将这两个蕴涵推导结合起来，我们得到
拼接问题可判定⇒矛盾，
因此拼接问题不可判定。
判断一组特定的形状能否用来拼接地板，这只是比停机问题难因而不可判定的众多问题之一。这样的问题还有很多很多，我将查看其中的两个。
我们在上一节看到，鲁菲尼和阿贝尔证明了变量的幂大于等于5的多项式一元方程不存在求解的一般方法。这里有一个与之相关的问题：对于系数为整数且拥有任意多个变量的多项式方程，判断该方程是否存在整数解。我们将只允许求整数解的方程叫作丢番图方程（Diophantine equations）。另外我们不是在寻找该方程的解。相反，我们感兴趣的是某种能够判断是否存在整数解的算法。寻找这种方法的挑战是大卫·希尔伯特在20世纪初向数学界提出的难题之一，后来被称为希尔伯特第十问题（Hilbert’s tenth problem）。
一些例子：
x2+y3=134
有解：x=3和y=5。相比之下，很容易看出方程
x2–2=0
不存在整数解。那么要是复杂的方程呢，如
x4y3z7-23x5y2+45x2=231
存在整数解吗？我不知道。如果某个计算机程序能够解决希尔伯特第十问题就好了。这种程序会将一个丢番图方程当作输入，然后揭示它是否存在任何整数解。
1970年，年仅23岁的俄罗斯数学家尤里·马蒂杰雪维奇（Yuri Matiyasevic）——在马丁·戴维斯（Martin Davis）、希拉里·普特南（Hilary Putnam）、朱丽娅·罗宾逊（Julia Robinson）等前人工作的基础上——最终证明不存在能够解决这个问题的计算机程序。也就是说，任意一个给定的丢番图方程是否有解是不可判定的。
在不触及这个证明方法的真正细节的情况下，让我们试着提供一种直觉感受。大致说来，这些数学家指出对于任何一种既定的计算，都可以设计一个丢番图方程，使得当且仅当这个方程有整数解时，这种计算过程才会停机。使用图9.17表示的话，内部判断机就会是一个丢番图方程判断机。如果存在某种判断该丢番图方程是否有解的方法，那么就存在某种判定停机问题的方法。换句话说，希尔伯特第十问题比停机问题更难。哎，可惜的是没有方法能解决停机问题，因此也就没有方法能解决希尔伯特第十问题。
被指出不可判定的另一个重要问题叫作群的字问题（word problem for groups）。群是我们在上一节遇到的数学家伽罗瓦首先提出的数学结构。这些结构表达了对称性而且无处不在……包括你的卧室。为了对群论形成一种直观的感受，让我们在卧室停留几分钟，思考一张床垫。对床垫的恰当护理方式是每隔几个月将它调整一下方向。实际上一张床垫的重定向有三种基本方式，如图9.18所示。一张床垫可以沿着它的长边翻转（L），沿着短边翻转（S），或者只是简单地旋转一下（R）。
这些不同动作的结合会让床垫回归原位，这表达了床垫的一种对称性。床垫还存在更多重定向的方式。如果S表示沿着短边顺时针翻转，那么S′就可以表示沿着短边逆时针翻转。可以用类似的方法规定L′和R′。建立了这些不同的重定向方式之后，我们可以将它们结合起来，先做一个动作，再接着做另一个动作。例如，先沿着长边翻转床垫（L），然后再旋转一次（R′）。我们将这个动作组合表示为LR′。
图9.18 床垫重定向的三种基本方式
思考某些重定向方式。很显然LL的意思是沿着长边翻转两次。这会让床垫回到原来的位置。类似地，R′R会让床垫先顺时针旋转再逆时针旋转，最终令它回到原来的位置。稍微不那么明显的是，LRS也会让床垫回归原位。（不要为了验证数学结果而去搬动沉重的床垫，别把自己拉伤了。用一本很轻的书就能证明这个结果。）LRL不能让床垫回归原位。经过几分钟的思考，你能看出
SŔŔRRRLLĹSRLLL
也能让床垫回归原位。那么
R ́SLR ́R ́L ́SL ́RLS ́S ́L ́S ́L ́SRLS ́L′R ́LSR呢？
只要有足够的时间和耐心，你实际上可以坐下来判断出床垫是否回到原来的位置。像这样面对一系列操作或者群中的某个字，提问这些操作是否能回到原位的问题，称为该群的字问题。人们发现床垫重定向这个群的字问题是可判定的。也就是说，我们可以坐下来写出一种算法，判断某个给定的字是否令床垫返回原位。其他群也是如此吗？
20世纪50年代中期，俄罗斯数学家彼得·诺维科夫（Pyotr Novikov，1901—1975）和美国数学家威廉·W.布恩（William W.Boone，1920—1983）证明了对于某些特定的群，不存在能解决它们的字问题的算法或计算机。对于这些群而言，字问题是不可判定的。
一旦某些问题被证明不可判定，许多其他问题也可以被证明不可判定。想要指出一个新问题不可判定，只需要指出某个不可判定的问题可以转化为这个问题。如果一个问题比某个已知比停机问题更难的问题还要难，那么就可以说这个问题比停机问题更难。具体地说，由于群论是现代数学和物理学很大一部分内容的核心，所以这些领域里有很多问题是不可判定的。
由于现代物理学的许多方面都以根本性的方式使用群论，而群论中存在许多无法判定的问题，所以现代物理学会有很多无法判定的方面。物理世界中存在任何计算机都无法回答的判定问题。科学的一个方面就是预测或揭示关于物质宇宙的某些特定事实的能力。这种不可判定性意味着可预测性无法实现。然而我们在这里必须谨慎小心。许多物理理论的确能使用群论（以及与不可判定问题有关联的其他数学结构）的语言表达，如果这些数学结构是表达这些理论的唯一方法的话，我们就能正确地声称这些物理理论是不可判定的。然而，某些物理理论可能还存在其他表达方式，而这些表达方式没有不可判定问题的困扰。
几何学就是一个这样的例子。小学生都知道需要做很多基础算术才能在几何学中得到结果。我们将在下一节看到，基础算术存在特定的局限。有人可能会猜测，既然基础算术中存在局限，而几何学是使用基础算术表达的，那么几何学中一定也存在特定的局限。然而这并不是真的！有一些方法不使用基础算术也能表达几何学的基本事实，所以几何学没有这些局限。
当然，有人或许会表示反对，说只是因为某个问题不可判定，并不意味着它超出了人类的能力或超出了理性的范围。就算计算机不能解决这个问题，也可能存在解决它的其他方法。或许人类可以解决某些计算机不能解决的问题。这就让我们回到了人类思维的本质的问题。它是否比一台计算机更强大？人类能完成计算机不能完成的任务吗？我们在思考停机问题时已经在第6章第5节中讨论过这个问题了。虽然我们没有在那一节得到任何确定的结论，但是无论停机问题得到的是什么答案，本节讨论的不可判定问题也将得到同样的答案。
感谢哈伊姆·古德曼–施特劳斯（Chaim Goodman-Strauss）提供图9.10~图9.16。
这个聪明的例子需要感谢哈伊姆·古德曼–施特劳斯的贡献。
用专业术语来说，虽然基础算术是不完备的（incomplete），但基础几何被希尔伯特证明是完备的（complete）。
处理数学的数学
逻辑是理性的语言。它的起源可追溯至古希腊，那里的哲学家们意识到某些推理形式使用了共同的结构。为了理解这种理性的结构，他们研究了这些不断重现的模式。在19世纪，数学家和逻辑学家将目光投向数学证明的结构并研究了它们的模式。他们建立起公理体系，以便将数学放置在牢固的基础上。
一位名叫朱塞佩·皮亚诺（Giuseppe Peano，1858—1932）的意大利逻辑学家创造了一个用来描述自然数基础算术的简单公理体系。这个体系后来被称为皮亚诺算术（Peano arithmetic）。该体系的公理如下：
1.存在一个自然数0。
2.每个自然数a都有一个后继自然数，表示为a+1。
3.不存在任何自然数的后继自然数是0。
4.不同自然数有不同的后继自然数：如果a≠b，那么a+1≠b+1.
5.如果自然数0有某种性质，而且任意自然数a拥有这种性质就意味着a+1也拥有这种性质的话，那么每个自然数都拥有这种性质。
希尔伯特等人指出，这些公理描述了自然数的大部分性质。
逻辑学家更进一步，用符号总结了这些逻辑体系。例如公理2可以写成
∀a∃bb=a+1
而公理4可以用符号写成
∀a∀b（a≠b）→（a+1≠b+1）。
使用这些符号可以将基础算术中的每个命题和证明转化成符号的序列。我们将这种从数学到符号命题的转化称为符号化（symbolization）。
对自我指涉的力量印象深刻的库尔特·哥德尔指出，数学也可以拥有自我指涉。通过将符号语言转化为数学语言，他得以完成相应的逻辑回路，让数学命题谈论自身（见图9.19）。哥德尔的方法为每个逻辑符号、命题和证明都赋予了一个与之对应的数字。既然关于数字的逻辑命题也有数字，我们就有了处理数学的数学，或者讨论数字的数字。逻辑学家埃米尔·波斯特（Emil Post，1897—1954）精妙地这样总结道：“符号逻辑可以说是拥有了自我意识的数学。”
图9.19 令数学自我指涉
这种将逻辑符号、命题和证明转化为数字的过程叫算术化（arithmetization）。虽然哥德尔为逻辑结构赋予数字的具体方式（哥德尔配数）对我们来说并不重要，但我们可以大概了解一下他的一些思想。由于符号的数量是有限的，我们可以为每个符号分配一个数字：对于每个符号x，我们可以分配一个数字“x”。例如“→”=1，“∃”=2，“∀”=3，等等。一旦每个符号都被分配了一个数字，那么作为符号序列的命题就可以分配到一个独一无二的数字，只需要将每个符号作为一个质数的指数，然后将它们相乘即可。例如，
∀a∃bb=a+1
会得到下面这个数字
2“∀”3“a”5“∃”7“b”11“b”13“=”17“a”19“+”21“1”
这个数字中的底数是按顺序排列的质数。这个数字的独特性体现在每个不同的公式都会得到不同的数字。我们可以将这种算术化或者对符号的编号推广到证明层面。既然逻辑证明是若干命题的序列组成的，我们就能为每个证明分配一个独一无二的数字。此外，这些编号是“机械的”，因为对于某个符号、命题或证明，我们很容易找到与其对应的数字。类似地，对于一个数字，我们可以机械地找到与其相对应的逻辑符号、命题或证明。
即使是最小的证明，分配给它的数字也会是巨大无比的。对于较大的命题或证明，这些数字很快就会比宇宙中所有粒子的数量还大。这一点不会对我们造成困扰，因为自然数永远也用不完。何况我们的目的并不是真的去计算这些数。概念很简单，就是每个证明都可以赋予一个数字，令自我指涉成为可能。我们并不关心产生的到底是哪一个数字。
我们在处理基础算术而且我们可以用符号的方式描述某些数字的集合。这需要用到谓词（predicates），谓词就像是函数，以数字作为输入，然后根据该数字是否满足特定的性质输出真或假的结果。例如，判断一个数字是否是偶数的谓词可以写成
Even（x）≡（∃y）（2y=x）。
如果存在自然数y令2乘以y等于x的话，那么这个谓词对x为真。有些谓词有两个变量。判断x是否能整除y的谓词是
Divide（x,y）≡（∃z）（xz=y）。
也就是说，如果存在z令x乘以z等于y，那么x就能整除y。还可以使用谓词构成其他谓词。例如，判断某个数字是否为质数的谓词是
Prime（x）≡x>1∧（∀y）（Divide（y,x）→（y=1∨y=x））。
翻译成日常语言就是，如果x大于1且x只能被1或x本身整除，那么x就是质数。
为了拥有自我指涉，我们需要的最终要素是一种叫作不动点机器（fixed point machine）的东西。这是一种将任意谓词转变成自我指涉的命题的方法。对于只有一个变量的任何谓词F（x），都有逻辑命题C令C等价于F（“C”）。用符号表示为
C≡F（“C”）。
用正常语言描述，C是这样一个命题，它说
“这个逻辑语句拥有性质F（x）”，
或
“我拥有性质F（x）。”
C被称为“不动点”，是因为F（x）被当作一个函数，而一个函数的输出通常和输入是不同的。在这里，输入是“C”，而输出等同于输入。它是“不动的”。这意味着这个语句将谈论自身。如果要详细阐述这种不动点机器是如何奏效以及C实际上是如何构建的话，那我们就离题太远了。只要说这种不动点机器的原理与第4章和第6章中的对角化证明非常相似就足够了。所有这些都是描述自我指涉的方法。
现在让我们使用我们的不动点机器制造一些有趣的逻辑命题。
塔斯基定理（Tarski’s Theorem）
如果我们的目标是使用数学和逻辑得到一个类似说谎者悖论的公式，那么我们可以假设谓词Truth（x）存在，并表示为
Truth（x）≡x是皮亚诺算术中一个真命题的哥德尔配数
使用这个谓词构成：
F（x）≡~Truth（x）.
换句话说，当x是一个不为真的命题的数字时，F（x）为真。将这个F（x）代入我们的不动点机器，得到一个逻辑语句T，
T≡F（“T”）=~Truth（“T”）。
T说T不为真。或者换句话说，我们构成了这样一个逻辑语句，它说“这个逻辑不为真”或者“我是假的”。
这种语句叫作塔斯基语句（Tarski sentence）。让我们分析一下这个逻辑语句。如果这个语句是真的，那么既然它声称自己为假，那么它就是假的。另一方面，如果这个语句是假的，那么既然它声称自己为假，那么它实际上是真的。我们有了货真价实的矛盾。这些矛盾是数学和逻辑的严格世界里不允许出现的！出了什么问题？唯一有问题的部分是假设逻辑谓词Truth（x）存在。
存在Truth（x）⇒矛盾。
既然我们不允许矛盾，我们的结论就只能是Truth（x）不可能存在。也就是说，我们刚刚证明了基础算术的一个局限：它不能判断自己的命题是否为真。对于没有算术的纯逻辑语句，我们用真值表判断一个命题的真伪。但我们在这里处理的不是纯逻辑。我们在这里处理的是数学和逻辑，无法使用真值表。自我指涉给我们带来了限制。
塔斯基语句类似于著名的说谎者悖论。说谎者悖论使用的是日常语言，而这里使用的是严格的逻辑语句。我们可以对日常语言的意义产生怀疑，声称说谎者悖论就像许多其他日常语言中的句子一样是无意义且/或自相矛盾的。但我们对逻辑就必须更加小心了。
哥德尔第一不完备定理（Gödel’s First Incompleteness Theorem）
现在呈现在我们面前的是20世纪数学最著名的定理之一。它表达了数学和逻辑的一种令人震惊的局限性。
塔斯基定理检验的是真值，而这次我们检验的是可证明性。假设存在谓词Prove（y,x），只要“y是哥德尔配数为x的命题的证明的哥德尔配数”，该谓词即为真。
由于我们的语言极为精确，而我们的编号方式又如此机械，这个谓词实际上是存在的。与不存在的真值谓词不同，我们实际上可以坐下来描述证明谓词。大致来说，该谓词必须查看数字y并判断它是某个证明对应的数字。然后它必须核实这个证明实际上证明了数字为x的命题。仔细检查所有步骤会让人极为痛苦，不过许多逻辑学教科书都列出了这个过程。我们只要知道证明谓词不像真值谓词，它真的存在就足够了。
拥有证明谓词之后，我们可以构造出谓词
F（x）≡（∀y）~Prove（y,x）。
也就是说，F（x）意味着每个数字y都不是命题x的证明。换句话说，当且仅当哥德尔配数的逻辑命题x不存在证明时，F（x）才为真。这个F（x）的一个不动点是语句G，令
G≡F（“G”）=（∀y）~证明（y,“G”）。
G说每个数字y都不是G的证明。翻译成日常语言，G说
“这个逻辑命题不可证明”
或
“我是不可证明的”。
这种语句叫作哥德尔语句（Gödel sentence）。让我们来分析一下这个命题。如果G可证明，那么既然该命题说它不可证明，那么我们证明了一个假命题。像皮亚诺算术这样的良好逻辑体系不可以证明假命题。那么让我们假设哥德尔命题不可证明。这正是该语句所说的内容，因此它为真。于是这个命题为真，却不可证明。
我们刚刚指出
哥德尔语句可证明⇒矛盾。
我们可以判断出哥德尔语句不可证明，因此为真。但我们在这里必须小心一点。可能（虽然我向你保证并没有这种可能）皮亚诺算术不是前后一致的，而且可以证明任何事，包括哥德尔语句。虽然我坚信皮亚诺算术的确是前后一致的，但我们仍然必须非常小心地陈述这个假设：
如果皮亚诺算术前后一致，那么哥德尔语句（不可证明且）为真。
我们将在下一节再次回到这个命题。
哥德尔令人惊诧的结果值得思考。在哥德尔之前“显而易见”的观念是，对于算术这样的简单体系，只要为真的命题同时也都是可以证明的。就是说，如果某个命题为真，一定存在它的某种证明。图9.20的左半部分展示的就是这种观念。
图9.20 “显而易见的”观点和正确的观点
哥德尔指出这个观点是错误的。存在一些像G这样虽然为真却不可证明的语句。（我们将在本节末尾看到，G并不是该类型的命题中唯一的例子。）
帕里克定理（Parikh’s Theorem）
罗希特·帕里克（Rohit Parikh）将哥德尔的思想又向前发展了一步，指出证明的性质存在某些奇怪的方面。思考下列谓词：
Prooflen（m,x）≡m是哥德尔配数为x的命题的证明的长度（以符号计）。
对于给定的m和x，不难判断这个谓词的真假：只要检索所有长度为m的证明（这样的证明有很多，但它们的数量是有限的），看看这些证明中的任何一个是否以某个哥德尔配数为x的命题结尾。如果存在这样的证明，那么该谓词为真。否则该谓词为假。
现在设n为一个大数，然后思考谓词：
F（x）≡~（∃m
如果x不存在长度小于n的证明，该谓词为真。将不动点机器代入F（x），我们会得到不动点P
P≡F（“P”）≡~（∃m
即，P等价于这样一个语句，该语句称不存在m
“这个逻辑语句没有比n短的证明”
或
“我没有短的证明”。
我们将这样的逻辑语句称为帕里克语句（Parikh sentence）。
让我们判断一下这个语句是真的还是假的。如果P为假，那么P的（短）证明的确存在。但是在一个前后一致的体系内，怎么可能存在某个假命题的证明呢？所以这个句子不是假的，必须为真。正如我们在哥德尔不完备定理中看到的那样，只是因为一个命题为真，并不意味着它是可证明的。现在让我们思考帕里克语句存在（长）证明的下列相对较短的证明：
如果帕里克语句没有证明，那它肯定也没有短证明。那么我们可以很容易地检查所有比n小的证明，并看出它们之中没有一个能证明P。总结：如果该语句不能被证明，那么我们可以证明它。
这个证明可以在皮亚诺算术中构思，而且相当短。帕里克语句是这样一种语句，它有一个非常长的证明，但也有一个短证明能够证明存在这个长证明。很奇怪，但却千真万确！
Löb悖论
在我们对不动点机器的最后一次使用中，我们将走上极端，证明每个逻辑语句——无论它有多疯狂——都是可证明的。正如我们怀疑已久的那样，我们将指出月亮是用脱脂干酪做成的！
我们已经见到，如果A是一个逻辑命题，那么“A”就是与之对应的哥德尔配数。算术化过程的一个要求是，我们也可以反方向进行这个过程：对于和某个逻辑命题对应的数字x，我们将它对应的逻辑命题称为|x|。如果我们从某个逻辑语句A开始，先得到它的数字“A”，然后再得到这个数字的逻辑语句|“A”|，我们就回到了同一个逻辑语句A。用符号表示为|“A”|=A。
设M［代表月亮（moon）］为任意逻辑语句。我们将证明M总是为真。
思考谓词
F（x）≡|x|→M。
当且仅当与x对应的逻辑语句蕴涵M时，F（x）为真。对这个谓词使用不动点机器。得到不动点
L≡F（“L”）=（|“L”|→M）=（L→M）。
换句话说，L称
“这个逻辑语句蕴涵M”
并被称为Löb语句（Löbsentence）。暂时假设L为真。那么既然L等同于L→M，那么我们的假设蕴涵L→M也为真。既然L和L→M都为真，那么根据演绎推理，M为真。所以通过假设L为真，我们证明了M为真。换句话说，我们证明了L蕴涵M，因此L→M为真。但L→M等同于L。所以L为真。我们的结论是，M——代表月亮是脱脂干酪做成的——为真。
我们刚刚证明了月亮是脱脂干酪做成的。这太荒谬了！哪里出错了？问题之所以出现，是因为我们没有对公式F（x）进行限制，可以对它使用不动点机器。我们在第4章第4节中看到，为了避免罗素的集合悖论，我们必须对概括公理进行限制。我们还在第2章第1节中看到，某些研究者坚持认为，为了避免语言悖论，我们必须坚持句子的层次性。我们必须远离某些样式的句子才能清除悖论。类似地，在这里我们必须限制不动点机器的使用以免证明假命题。这样的限制或许看起来很奇怪，因为不动点机器的证明方法似乎适用于所有F（x）。但我们必须做出这样的限制，以免我们超出理性的边界。
虽然我们是使用皮亚诺算术的语言陈述所有这些局限性的，但这些现象也可以在更具普遍性的意义上描述。皮亚诺算术使用所有普通算术操作将逻辑命题编码和解码为数字。然而还有许多其他体系也可以让我们将命题当作数字，将数字当作命题。一旦任何这种编码方式成为可能，我们就会得到自我指涉和类似的局限。我们值得将哥德尔不完备定理陈述为下面这个广义的形式：
在任何拥有充分的结构、可以编码和解码其中命题的“良好”逻辑系统中，都会存在自我指涉，从而产生局限。具体地说，会存在为真但不可证明的命题。
有些逻辑体系非常“弱”，表现在它们不能编码自己的命题。这些系统不会产生自我指涉方面的局限，因此哥德尔的不完备定理不适用于它们。这些系统被称为是完备的（complete），因为每个为真的命题都有证明。这种完备系统的一个例子是普雷斯布格尔算术（Presburger arithmetic），这种逻辑体系只处理加法，没有足够的能力处理乘法和其他运算。另一个例子是某种只处理基本几何体的逻辑体系，它也没有编码自身命题的足够能力。这里有一点小小的悖论。这些系统弱到不能为自身命题编码，却有能力让所有为真的命题拥有证明。相比之下，有能力编码自身命题的系统却自有其弱点，那就是它存在为真却不能证明的命题。
在这一节，我们描述了一些为真但无法证明的数学命题。有人或许会觉得只有这些少数“病态的”数学命题是有问题的，而大多数“正常的”真数学命题都是可以证明的。计数方面的简短论证会让我们看出，情况并非如此。
思考自然数的所有子集。正如我们在第4章第3节中看到的那样，这些子集一共有不可数无限个。如果S是自然数的一个子集，而x是一个自然数，那么下面这两个数学事实必然有一个为真：
x是S的元素
或
x不是S的元素。
由于自然数拥有不可数无限个子集，所以关于数字的这些事实也有不可数无限个。这些都是数学事实——而不是什么内容可陈述的问题。数学命题是可以用符号表示的数学事实。我们在上文中见到，算术化是数学命题和自然数之间的对应过程。这意味着数学命题的数量是可数无限个。因此数学事实的数量比数学命题多得多。
哥德尔的定理在这个问题上又向前走了一步。他的不完备定理的全部意义就是指出可证明数学命题的集合是所有数学命题的真子集，如图9.21所示。
图9.21 真事实，真命题和可证明的命题
由于每个证明都有一个与其对应的自然数，所以可证明数学命题的集合也是可数无限的。克里斯蒂安·S.卡鲁德（Cristian S.Calude）和其他几名合作者最近证明，即使在所有为真的数学命题中，可证明命题也属于极少数。我们的结论是，虽然数学证明可以证明可数无限多个真命题，但还有多得多的真数学命题和事实是不可证明的，并因此超出了理性思维的范畴。
哥德尔令人震惊的定理是，皮亚诺算术中存在为真但不可证明的语句。虽然哥德尔语句是此类语句的第一个例子，但它总是有一点儿“做作”或“不自然”的感觉，仿佛不是“真正的数学”。我们刚刚已经指出，皮亚诺算术中存在可数无限个为真但不可证明的命题。而且还有更多这样的命题是“自然的”，看起来像“真正的数学”。古德斯坦定理（Goodstein’s theorem）就是一个这样的命题。
先介绍一些背景。任何数字都可以写成2的幂之和。例如，
●19=24+21+1
●87=26+24+21+1
●266=28+23+21
让我们更仔细地看看266。这些指数也可以写成2的幂之和。
266=222+1+22+1+21
现在这个数字完全是用2或更小的数字表示的。这种书写数字的方式叫作“世代性基底2计数法”（hereditary base-2 notation）。我们现在要对266的这种表示方法执行一种过程，该过程一共有两个步骤：
●步骤（a）:将表达式中的基底从2增大为3。
●步骤（b）:从整个数字中减去1。
这会让我们得到
这个数字大约是1038。这个过程可以无限迭代下去，将3换成4：
再次迭代：
我们每次都将基底增加1，然后从整个数字中减去1。正如你所见，这些数字会疯狂地增大。你可以想象，如果你继续这个过程，数字会变得越来越大。真的如此吗？1944年，英格兰数学家鲁宾·古德斯坦（ReubenGoodstein，1912—1985）证明了下面这个不同寻常的定理：
取任何数字，将它写成世代性基底2计数法，然后按照下面两个步骤迭代运算：（a）将所有世代性基底n计数法中的n替换为n+1，然后（b）减去1。最终结果会到达……零！
也就是说，这个数字不会变得越来越大，而是最终——很长很长时间之后——会开始减小，一直减小到零。这太令人吃惊了。在我们进行运算的两个步骤中，一个步骤极大地增加了原来的数字，另一个步骤只不过减去了1。我们的直觉告诉我们，这一系列数字会变得越来越大。我们的直觉是错的！这些数字“最终”会开始减小。这需要极为庞大的迭代次数，但仍然会发生。古德斯坦使用无穷方法和集合论的强大能力证明了这个令人惊诧的定理。1982年，劳丽·柯比（Laurie Kirby）和杰夫·帕里斯（Jeff Paris）证明了这个定理只能用这些无穷方法证明，而且尽管这个定理可以用皮亚诺算术的语言陈述，但它无法在该系统内证明。对这个系统而言，这些数字太大了。所以古德斯坦定理和哥德尔语句一样，它为真，但在皮亚诺算术中不可证明。
这基本上是归纳法，我们在第3章讨论麦粒堆时见到过这种方法。
Post（1941），见Davis（2004，343n12）。
这和我们在第6章做的事非常相似。在那一章，我们为每个程序分配了一个独一无二的数字。在这一章，我们为每个证明分配一个独一无二的数字。目标也是相似的：自我指涉。在面对程序时，我们想让处理数字的程序拥有数字，从而让程序能够处理程序。在这里，我们想让处理数字的数学命题拥有数字，从而让数学命题能够处理数学命题。
我在这里省略了一些细节。哥德尔的结果在一致性和欧米茄一致性（ω-consistency）方面有一点复杂。1936年，约翰·巴克利·罗瑟（John Barkley Rosser，1907—1989）修改了哥德尔语句，得到了如今所称的哥德尔–罗瑟语句（Gö-del-Rosser sentence）。该语句指出了我们希望得到的结果。
在第6章第3节末尾，我指出虽然计算机能完成可数无限多个任务，但还有不可数无限多个任务是计算机无法完成的。在第7章第1节的末尾，我陈述了这样一个论点，科学只能处理可数无限多个现象，但是还存在不可数无限多个现象不能被科学描述。我在这里陈述了与这些结果类似的数学方面的结果。
顺着这些思路，李奥帕德·勒文海姆（Leopold Löwenheim，1878—1957）构思出了后来所称的向下勒文海姆–斯科伦定理（downward Löwenheim-Skolemtheorem）。这个深奥的定理声称，被描述之物不可能比用来描述它的语言更复杂。具体地说，数学中的命题是用符号的有限集合写成的。使用这些符号可以写出可数无限多个可能的命题。现在思考某个拥有不可数无限多个元素的系统。向下勒文海姆–斯科伦定理声称，如果存在使用某种语言谈论这种系统且前后一致的方法，那么那种语言很可能只使用可数无限多个元素谈论这个系统。也就是说，这些公理的目的或许是讨论某种不可数无限的事物，但我们其实不能表明它拥有的元素数量比可数无限更多。这对我们可以描述的内容产生了巨大的限制。
公理和独立性
让我们继续使用哥德尔的第一不完备定理得到更多结果。我们发现哥德尔语句，
“这个逻辑语句不可证明”
是不可证明的，因此为真。我们实际上证明了
“如果皮亚诺算术前后一致，那么哥德尔语句为真”。
这个事实可以形式化并在皮亚诺算术内得到证明。这意味着我们可以用皮亚诺算术的语言写出我们在上一节介绍的内容的证明。这个得到证明的命题可以写成下面的蕴涵关系：
“皮亚诺算术前后一致”→“哥德尔语句为真”。
假设我们可以在皮亚诺算术内证明“皮亚诺算术前后一致”。那么我们就会在皮亚诺算术内有如下推论：
“皮亚诺算术前后一致。”
“皮亚诺算术前后一致”→“哥德尔语句为真。”
“哥德尔语句为真。”
这将会是皮亚诺算术内哥德尔语句为真的证明。但哥德尔语句说这样的证明不可能存在！我们的假设一定出了什么问题。我们做出的唯一陈述是皮亚诺算术可以证明自身的前后一致。这让我们得到了哥德尔第二不完备定理：皮亚诺算术（Peano arithmetic）不能证明自身的前后一致。也就是说，不能使用基础算术证明基础算术是前后一致的。
需要注意到的是，哥德尔第二不完备定理是背负在哥德尔第一不完备定理上得到证明的。第一不完备定理说的是这种蕴涵关系：
哥德尔语句在皮亚诺算术中可证明⇒矛盾。
在这一节，我们指出了下列蕴涵：
“皮亚诺算术前后一致”在皮亚诺算术内可证明⇒哥德尔语句在皮亚诺算术中可证明。
将这两种蕴涵推导结合起来，我们得到
“皮亚诺算术前后一致”在皮亚诺算术内可证明⇒矛盾。
我们刚刚指出“皮亚诺算术前后一致”这个命题不能在皮亚诺算术内证明。但这个命题为真吗？它是否可能为假呢？我们真的要相信这种算术前后不一致吗？会不会有人在将来的某一天证明2+2不等于4？不要怕，亲爱的读者。1935年，格哈德·根岑（Gerhard Gentzen，1909—1945）证明，更强大的公理体系——带有选择公理的策梅洛–弗兰克尔集合论（ZermeloFraenkel set theory with choice，简称ZFC）——的确证明了算术的前后一致。详细地说，由于我们可以在ZFC内理解算术，而且这个体系拥有处理更强大的无限概念的能力，所以它可以证明皮亚诺算术的一致性。换句话说，算术一致性的简单“有限”证明不存在，但是存在它的“无限”证明。根岑证明了如果ZFC前后一致，那么皮亚诺算术也前后一致。这里有个小问题：谁规定ZFC前后一致？
哥德尔第二不完备定理实际上说了更多内容。皮亚诺算术在我们的讨论中并没有什么特别之处。我们说过，哥德尔第一不完备定理对于能够编码自身命题的任何公理体系都适用。通过使用我们在本节开头使用的相同推理过程，我们也可以将哥德尔第二不完备定理推广到能够编码自身命题的任意公理体系。ZFC就是这样一个体系。因此，根据哥德尔第二不完备定理，ZFC不能证明自身的前后一致。
这实在太令人烦恼了！现代数学的大多数内容都可以在ZFC内构思出来。如果能知道ZFC公理体系前后一致，不会发现任何矛盾就好了。哎，可惜ZFC内不存在这样的证明。研究者们构建了能够证明ZFC一致性的其他更强大的公理体系。这些体系同时包括ZFC公理和强有力的“无穷性公理”（axioms of infinitie）。这些新公理不在典型的数学中使用，它们对后者有一种不自然的临时应付之感。和ZFC的普通公理不同，很难判断其他这些公理是否正确。它们不是不证自明的。但是，即使增加了这些强大的新公理，我们也没有得到一个能够证明自身一致性的体系。我们总是必须求助于一个更强大的体系。
我们在上一节见到，古德斯坦定理是一个“自然”“不做作的”数学结果，它超出了皮亚诺算术的证明能力，但它是正确的而且可以在ZFC内证明。与这个结果类似，哈维·弗里德曼（Harvey Friedman）也提出了几个“自然”“不做作”的数学命题，它们超出了NFC的证明能力，但在更强大的体系内则是正确的。
图9.22总结了我们的一些发现。
皮亚诺算术不能证明皮亚诺算术的一致性（consistency of Peano Arithmetic，简称ConPA）。ZFC可以证明皮亚诺算术的一致性，但无法证明ZFC的一致性（ConZFC）。我们总是能构建出可以证明ZFC的更强大的体系，但这些更强大的体系也不能证明自身的一致性。我们可以永远继续下去。这符合本书的中心主题之一：任何自我指涉的系统，无论多么强大，总会在某种程度上受到局限。
图9.22 公理体系的层级
不要担心现代数学或基础算术前后不一致。我向您保证，它们是前后一致的。算术已经出现了几千年，没有人发现过不一致的地方。有数百万人在现代数学的领域内工作，从未发现任何不一致之处。然而，作为数学和科学的基础，逻辑体系的一致性超出了理性的边界，证明这一事实仍然令人感到不安。
在某种意义上，可以将哥德尔定理和它们的推论看作是对公理化方法的一种批评。数学家们总是在寻找公理，以便找到蕴涵所有其他命题的最少最简单的命题。但哥德尔向我们指出，无论增加多少公理，总是会存在缺失的东西。具体地说，总是会存在为真却无法用这些公理证明的命题。很多数学内容可以不使用公理完成。绝大多数数学家不使用公理体系。他们只是遵守自己学到的规则。只有逻辑学家和集合论学家着眼于使用的是什么假设。即便是现代集合论的创始人康托尔也没有使用公理证明自己的定理。相反，策梅洛–弗兰克尔集合论的公理是康托尔完成自己的工作之后构思出来的。康托尔只是使用了自己的直觉。
对公理体系的另一个批评是，集合论学家们似乎在不停地增加公理，制造出越来越强大的超越ZFC的体系。皮亚诺算术和ZFC的普通公理看上去显而易见（如托马斯·杰斐逊和他的同人们所写，“我们认为这些真理是不言而喻的”）。皮亚诺算术的公理规定不同数字拥有不同的后继数，这在任何五岁儿童看来都是显而易见的。ZFC的公理说对于某个存在的集合，它的幂集也存在，这条公理同样显而易见。相比之下，集合论学家使用的某些无穷性定理则并非不言而喻，或者并不显而易见。它们被添加进来是因为它们看上去和其他公理不矛盾，而且能够用来证明特定的定理。有些人可能感觉这像是作弊：我们只是在添加那些我们觉得有用的公理。
另一方面，要是没有公理，我们会在何处？我们可能会一头栽进矛盾之中。虽然不存在足够强大的完备公理体系，但是拥有公理，我们至少可以看到不同体系的层级。我们可以说ZFC比皮亚诺算法更强大，因为我们可以比较它们的公理。数学的力量在于它有公理作为坚实的基础，而不是仅仅基于人类的直觉。
关于本章讨论的数学局限，有一点稍微不够真诚的地方：它们并不是真正的局限，而只是绊脚石。存在绕过它们的方法。对于某个数学系统的每种局限，都存在范围更广、更强大的系统能克服这些局限：
●我们见到无法用一把直尺和一只圆规三等分一个角；然而只要使用一个简单的量角器，这个任务就变得非常容易了。量出这个角的大小，然后除以3。类似地，我们还可以同样轻松地完成使圆成方和加倍立方体。
●伽罗瓦理论判断的是方程在什么情况下无法使用加法、乘法、除法和方根的运算方法求解。然而，以微积分为基础的方法总是可以对这些方程求解。
●哥德尔第一不完备定理说某些命题为真，但在某些有限算术系统内不可证明。但我们看到同样的命题在更强大的系统内可以证明。
●哥德尔第二不完备定理规定，有限算术系统的一致性在该系统内不可证明。根岑指出它们的一致性在更强大的ZFC体系内可证明。
●ZFC的一致性（正如我们在第4章第4节中见到的连续统假设和选择公理）在ZFC内不可证明。然而还存在令它可证明的更大的系统。
●对于比ZFC大的任意系统，都存在该系统内不可证明的命题，但总是会存在更大的系统。
我们将这些局限称为相对局限（relative limitations），与之相对的是在任何数学系统内都无法解决的绝对局限（absolute limitation）。目前存在已知的绝对局限吗？也就是说是否存在这样的数学命题，它们是真的，但无论人类投入多少巧妙的思考也不可能指出它们是真的？需要注意的是，即使的确存在这样的命题，我们也永远不能证明或知道它就是这样一个命题，因为要证明一个不可证明但为真的命题就意味着我们证明了它为真。所以绝对不可证明的问题是我们永远无法证明的问题，而且我们永远不可能知道我们永远不可能证明。这让它们存在与否的问题有些形而上学，因为它们存在与否是一件我们永远不可能知道的事。
与数学局限不同，第6章和第9章第3节讨论的计算局限在某种意义上则是绝对的。我们指出不存在可以解决某些问题的计算机或机械论方法。世上不存在能解决这些问题的已知的更优秀的机器。即使是量子计算机，当它们变成现实之后能做的也不比常规计算机能做的更多。（它们的优势是在常规计算机能做的事情上比后者更快，而不是能解决无法解决的问题。）计算局限的绝对性来自这样一个事实，我们完全知道计算机是什么。相比之下，我们对人类意识和理性的知识仍然是有限的。
哥德尔如是总结了上面两段文字的内容，他假设（a）存在绝对不可解决的问题，或（b）拥有似乎无限巧思能力的人类思维“无限地超越任何有限机器的能力”。换句话说，如果人类思维只是一台机器，那么它就会拥有与机器和有限系统一样的局限。那样的话，就是（a）为真，人类思维也会拥有绝对无法解决的问题。相反，如果人类思维总是能解决任何问题，那么（b）就是真的，人类思维必定比任何有局限的计算机或有限公理体系更强大。
让我们（有些犹豫地）将这两种选择接受为唯二可能的选项。我们应该相信哪一种选项呢？在我看来，当我们越来越了解人类的大脑，认识科学在思维工作原理方面不断取得的进展，我们将别无选择地接受（a），即大脑/思维按照机械的方式工作。人脑大概是整个宇宙中最复杂的机器，而我们距离真正理解人类的工作方式可能还有几百年。然而，就我们已经从大脑工作机制中看出的内容判断，似乎并不存在任何神秘的过程能够赋予人类思维“无限地超越”有限实体过程的能力。人脑的能力存在绝对局限，接受这个观点似乎是合理的，因为任何计算设备和任何实体机器都有绝对局限。即使在纯数学的世界中，也存在理性的局限。
值得思考一个有趣的结果。正如我所说的那样，皮亚诺算术比ZFC弱。换句话说，能够在皮亚诺算术内证明的东西一定能够在ZFC内证明。但是它到底有多弱呢？有人指出，如果你保留ZFC的公理，剔除无穷性公理，那么剩下的系统就和皮亚诺算术等效。（等效的意思是，在一个系统内可以证明的任何东西都可以在另一个系统内证明，反之亦然。）这可以写成ZFC=皮亚诺算术+无穷性公理。由于ZFC可以证明皮亚诺算术的一致性（以及皮亚诺算术内的任何其他真命题），所以它认为接受皮亚诺算术前后一致等同于接受存在处理无限集合的一致性方法。又或者上述等式指出了这样一个事实，如果数学家愿意放弃存在无限集合的观念，所有数学就会和基础算术同样前后一致。
或者我们真的知道吗？计算机科学的一个核心概念是所有不同类型的实体计算设备基本上都能解决相同的问题。有些设备的计算速度比其他设备快，但它们都拥有相同的计算能力。一台设备可计算的问题也可以被另一台设备计算。对我们的讨论而言更重要的是，一台设备永远不可能计算的问题，另一台设备也永远无法计算。这个概念称作邱奇–图灵论题（Church-Turing thesis）。它是一个论题而不是定理，因为它永远无法被证明。我们没有办法证明关于每一台实体设备的论断。但是也许邱奇–图灵论题是错的。或许在遥远的将来，