Limits of Logic: The Gödel Legacy

编者按：本文为认知科学家道格拉斯·侯世达（Douglas Hofstadter）在《逻辑的极限：哥德尔的遗产》（Limits of Logic: The Gödel Legacy）系列活动上的演讲。侯世达是印第安纳大学教授，一九七九年出版的《哥德尔、埃舍尔、巴赫：集异璧之大成》获普利策奖，他以对自指、类比与心智的研究闻名于世。本次演讲不谈哲学后果，只做一件事：用类比把哥德尔不完备性定理的构造从头到尾讲清楚。本文依据现场录音编译整理。

从悖论说起

克里斯塔邀请我来讲哥德尔的时候，我一度想过，或许不只讲哥德尔，还可以讲讲其他那些不可知的东西。但后来我决定，今天上午的报告只谈哥德尔的不完备性定理，尽力给大家一个完整的概览。我不打算多谈它的哲学后果，那些可以留到讨论环节。我只想讲清楚哥德尔究竟做了什么。

正如马库斯在他的报告里说的，哥德尔的灵感来自「这句话是假的」这一类悖论式的陈述。他把这种结构，或者说这种构造，搬进了数学，而且是以一种任何人都不可能预料到的方式搬进去的。我把这次讲座分成了几个所谓的「章」。我也不知道「章」在这里是什么意思，只是觉得这样叫着好玩。

数学符号的诞生

大约四五百年前，数学里几乎没有任何符号，一切都用句子写成。那时连方程这种东西都没有，也没有用字母表示变量或常量的做法。这些都是后来才发明的。我记得是笛卡尔发明了用字母代表数的想法：字母表开头的字母表示常量，末尾的字母表示变量。还有一位苏格兰数学家，名字我忘了，好像叫罗伯特，姓氏记不起来了，他在四五百年前发明了等号。今天很难想象一种完全没有符号的数学，但这恰恰说明我们已经走了很远。

到了十七、十八、十九世纪，数学变得极为形式化。当然，很多工作仍然是用自然语言完成的，就像今天一样。可人们并不清楚究竟什么才算严格，什么不算。欧拉和许多其他人发现了不少看起来悖谬的东西，这些悖论引起了广泛的忧虑：数学推理虽然给人感觉严密而精确，可它到底可靠不可靠？于是人们想把它用某种形式化的方式钉死，好一劳永逸地弄清什么是数学真理。

这是一场短讲座，我不打算总结那段历史。做出贡献的人非常多，我可以列出乔治·布尔、奥古斯都·德摩根、戈特洛布·弗雷格、大卫·希尔伯特、朱塞佩·皮亚诺等等许多人。但我特别想谈的是这两位：阿尔弗雷德·诺思·怀特海和伯特兰·罗素。（这是一张相当滑稽的罗素照片。）他们的巨著《数学原理》（Principia Mathematica）分三卷，于一九一〇年到一九一三年间出版，试图把整个数学形式化，并把它与逻辑统一起来，把数学推理奠基在逻辑和集合论之上。这是一次高尚的尝试。

消灭自指的雄心

他们工作的核心之一，就是想把悖论清除出去。前面说过，悖论让很多人不安。在罗素看来，一切悖论的根源都是自指（self-reference）：能谈论自身的句子，比如「这句话是假的」；或者能包含自身的集合。于是他发展出所谓的类型论（theory of types）。我不打算展开，简单说，那是一种防止自指进入系统的办法，是一座精心构筑的堡垒，目的就是不让自指在系统里冒头。这在当时是极其重要的事。

这是我从书里随手截出来的一页，为的是让大家看看他们那套记法有多扎手。许多年里，他们的这部著作被当作那个梦想的实现：把全部数学奠基在逻辑之上，把它形式化，让它成为一个一劳永逸的精确系统，全部数学都将从《数学原理》里推出来。

但在维也纳，哥德尔对这个目标多少心存疑虑。他觉得这项事业里有什么地方不对劲。我马上会讲他做了什么，但在那之前，我得先谈谈数学推理的本质，谈谈它在《数学原理》里，以及在任何形式系统里，是怎样运作的。

形式系统：公理与无意义的操作

形式系统的想法是这样的：你有一组公理，用一种形式记法写下来，然后用一些叫做推理规则（rules of inference）的东西，按某些形式化的方式去操作它们。我肯定不会细讲这些。这里列出了几条可以用于数论的公理。它们并不是数论的全部公理，只是用来说明问题。我试着帮大家解读一下这种记法，其实这并不太要紧。

倒过来的大写 A 表示「对于所有」。这一条说的是：对于所有的 a，波浪号表示「非」，是否定，大写 S 表示「后继」。所以这一条说：对于所有的 a，a 的后继不等于零。翻译成人话就是：没有哪个数的后继是零。所谓后继，就是加一得到的那个数。这条公理实际上说的是不存在负一，不存在负数。

第二条相当于在定义零的性质：对于所有的 a，a 加零等于 a，零是加法单位元。第三条谈的是加法的本性：对于所有的 a 和 b，a 加上 b 的后继，等于 a 加 b 之后再取后继。这看起来是句相当平凡的话，但有了它，加法就能运转起来。接着一条说，乘以零当然得零。再一条则定义了乘法的实质：a 乘以 b 的后继，等于 a 乘 b 再加上一个 a。这些陈述能让你做很多事。当然还需要别的公理，但我不想细说。

我想强调的是「形式」这个词的意思。今天是计算机时代，人们对机器能操作符号这件事已经习以为常。可在一九一〇年到一九一三年《数学原理》出版的年代，以及之前和之后的几十年里，并没有计算机。虽然那时已经有了巴贝奇（对，是查尔斯·巴贝奇，我近来老是想不起人名），他发明了计算机的概念，并以一种奇妙的方式在理论上发展了它。所以计算机的概念已经有了，当然不是电子的，而是机械的。但在那时，符号可以被形式化地操作，这仍是一个新鲜而陌生的想法。

必须认识到的一点是：这些系统的要义在于，你根本不去理会符号的意义。我刚才说倒 A 表示「对于所有」，波浪号表示「非」，可从某种意义上讲，你在做那些操作的时候，是不应该知道这些符号的意义的。我说过，推理规则允许你从公理推出定理，可这些操作不能考虑任何意义，它们必须无视符号的含义。你只看符号本身，然后说：好，这一串符号具有某种形式，这种形式允许我从它走到另一串符号，至于它们是什么意思，我不知道。这就是形式系统的想法，也是《数学原理》所推行的观念。

两个证明与起伏的红线

我要展示两个证明。我不会解释所用的推理规则，只想让大家看看证明长什么样。这是一个很短的证明，证的是「一加一等于二」，也就是零的后继加上零的后继等于零的后继的后继。证明是这样的：它用到两条公理，然后使用一些推理规则，我不去描述它们，总之是形式化的过程，允许我从这条公理走到它的一个特例，再走到这一步、这一步、这一步。

我唯一想让大家注意的，是我在右边页边画的那条红线。请注意它是来回摆动的：开头是几行长的，然后变得很短，到结尾又稍微变长一点。这只是后面要讲的东西的一点预兆，我只想让各位先留意一下。

第二个证明是「一乘一等于一」。这个证明更长，也更复杂，但从我刚才展示的那组公理和我在这个系统里允许的推理规则出发，它差不多已经是最短的了。我不会逐行讲，对眼下的目的来说那并不重要。我还是想请各位看那条波浪形的线：为了证明一个非常短的符号串，我不得不走过一条路径，途中经过了一些相当长的符号串。最长的是哪一行？就是那一行，比我要得到的结果长得多。

这是思考证明的本性时极其关键的一个事实：从某种意义上说，为了最后得到一个很短的符号串，我们不知道中途要操作的符号串会有多长，也不知道要走多少步。这是无法预先知道的。

罗素的安心

罗素和他的同事怀特海在构建这套理论时，当然是很高兴的。因为很明显，当你用这种记法写下关于整数的陈述，哪怕是相当复杂的陈述，比如表达费马大定理的那个：a 的 n 次方加 b 的 n 次方永远不等于 c 的 n 次方，其中 a、b、c 是正整数，n 大于二。这样的陈述可以用这种记法写出来，而它显然与「这句话是假的」这类悖论式的陈述毫无关系，二者之间的距离要多远有多远。它谈的是整数，而且只谈整数。

再比如哥德巴赫猜想：任何大于或等于四的偶数都是两个素数之和。这个猜想至今没有证明，但人人都相信它是真的。这样一个陈述，同样只涉及素数、加法之类的东西。在一个只谈论整数及其性质的系统里，自指的陈述怎么可能冒出来呢？我相信这一点让罗素非常安心：他的系统显然容不下自指的陈述。

合式公式：可判定的性质

前面已经谈了一点定理，现在我想谈一种叫做合式公式（well-formed formula）的东西，因为它与定理形成鲜明的对照。合式公式说白了就是一个合乎语法的句子，是一个表达了某个陈述的东西。这个陈述可以是真的，也可以是假的，反正它是一个陈述。

来看几个例子。这一个说「一加一等于二」，它恰好是真的。这一个说「零等于一」，它恰好是假的。但二者都是同样合格的合式公式，它们都表达了非真即假的思想，这就是我们需要考虑的全部。这一个表达的是加法交换律；这一个说不存在平方等于二的数 a。诸如此类。如果我把开头的波浪号去掉，它就变成「存在平方等于二的数 a」，这两个同样都是合格的合式公式。

关于合式公式，我想告诉大家的是：判断一个公式，也就是一串符号，是不是合式的，非常容易。有一些规则，基本上就是看它的各个部分，把它拆成更小的部分。比如这一个，我看到它以左括号开头，那就告诉我，后面必须有一个与之配对的右括号。它不必在末尾，但总得在某处，括号必须平衡。果然，这个和这个配对，这个和那个配对。这还不能保证它是合式的，但肯定是合式检验的一部分。

再看这个，这里的符号表示「如果……那么」，也就是蕴涵。念出来是：如果零等于一，那么二加二等于四。这不是什么有趣的陈述，听起来有点傻，但这不是重点。我们能读它，能明白它的意思，而且它是合式的。「零等于一」本身是合式的，「二加二等于四」也是合式的，然后我用一个「如果……那么」把两个陈述连了起来。这也是一种允许的操作：取两个合式公式，造出另一个合式公式。

把公式搭建成合式公式的时候，我做的只有一件事：拿小块拼成大块。仅此而已。所以，要想知道一串符号是不是合式公式，我只需看它的各个部分，把它拆成小部分，再拆成更小的部分，一直拆下去。这是一个完全可预测的合式性检验。

定理：不可预测的性质

与此相对的是定理。要知道一样东西是不是定理，可没这么容易。右边页边那条红线要告诉你的就是这个。定理的定义是：有一个演示、有一个证明的东西。而要知道这一点，你必须在可能的证明中去搜索，可你不知道这场搜索要花多久，也不知道途中涉及的公式会有多长。所以这里有一种不可预测性。相比之下，「判断这个公式是不是合式的要花多久」这个问题里没有任何不可预测的成分，那是一个真正平凡的问题。这个对照极其关键。

我想我已经说过了，不必再重复：合式性的检验，就是递归地把一个可能合式、也可能不合式的符号串拆成部分，再把这些部分继续拆下去，直到最后得出结论：它是合式的，或者它不是。非常直截了当。

这里有一个符号串，它其实是哥德巴赫猜想在这种形式记法里的表达。我大致说说它的意思：对于所有的 a，存在 b 和 c，具有如下性质。这里是二乘以 a 加二。a 最小可以是零，所以 a 加二就是二、三、四、五、六等等，乘以二就是从四开始的任意偶数。它说的是，对于任意这样的偶数，存在 b 和 c，使得这个偶数是二者之和，而右边这部分说的是 b 和 c 都是素数。我不逐个符号解读了，总之这就是哥德巴赫猜想的表达。如前所说，至今不知道它是真是假，尽管人人都相信它是真的。

它是合式公式吗？看一眼就行了，花几秒钟你就能确认它是合式的，毫无难度。它是定理吗？那你去证证看。几百年来数学家们的努力都没有得出结果。

由此可见，虽然「合式」和「定理」都是形式性质，都只涉及符号的性质，但一个性质非常简单，可以在可预测的时间内检测出来；另一个则微妙得多，也难以捉摸得多。

总结一下。左边：合式公式是递归地把小块拼在一起搭出来的。这幅图的意思是，你拿小东西拼在一起，就得到大东西，这个搭建过程是单向增长的，而且可以平凡地倒过来，把合式公式拆成部分。右边：定理则不然。只有当存在一个证明、一个演示时，你才知道某样东西是定理。而证明是从公理出发，遵循推理规则，把公理和已经证明的定理组合成新的定理。这个过程可能涉及越来越长的串，然后变短，再变长，再变短，你永远不太清楚自己要往哪儿去，它可能花任何长的时间，而且你没有把握。这就是两种结构之间的巨大反差。

斐波那契数：容易检验的数

现在来谈两类数。这是一个类比，我想借它让各位理解哥德尔构造背后的想法。当然，在座许多人已经懂了，但对不熟悉哥德尔工作的人，这个类比会有帮助。

斐波那契数大家都知道，我只简单提一句：它们是把前两个数相加得到的数列，一加二是三，二加三是五，等等，十三加二十一是三十四。如今人人都很熟悉斐波那契数。假如我给你一个数，比如六百七十二，问它是不是斐波那契数，你不会说「天哪，我根本不知道该怎么算」。你会做的是，把斐波那契数一路生成到这个大小或者接近这个大小，然后说：看来不是，因为下一个已经超过它了，是九百八十七。既然已经越过去了，而斐波那契数永远只增不减，那么既然越过了六百七十二，它就不是。可如果我说的是三百七十七，你正好撞上它，你就会说：是的，它是。所以判断一个数是不是斐波那契数非常容易，这是一个很简单的检验。

素数也类似。六百九十一是素数吗？你用一串数去除它，除到六百九十一的平方根还没有找到因子，你就知道完事了，它是素数；如果中途找到了因子，那它就不是。数有很多性质都可以这样又快又可预测地检验。

柯拉茨数：无法预知路径的数

与之相对的，我要谈一个著名的猜想，柯拉茨（Collatz）在二十世纪三十年代提出的。柯拉茨是一位专攻微分方程的数学家，但他大概会因为这个猜想而不是别的什么被人记住，尽管他是一位出色的数学家。我要用一种与他的原始表述略有不同的方式来陈述它，但二者是等价的，只是从反方向来看同一件事。

从 n 等于一开始，我们总是从一开始。然后有两件事可以做。第一，我们总可以从 n 跳到 2n，也就是说，手里的任何数都可以加倍。第二，如果这个数具有 3k 加 1 的形式，比如七或者二十二，那么我们可以从这个大数跳到 k。比如说，二十二可以跳到七，因为二十二具有 3k 加 1 的形式，它是三乘七加一。二十三不行，因为它不是这种形式；二十四也不行；二十五就可以，可以从二十五跳到八，因为它是这种形式。

好，现在有了这两条规则，可以对手里的数做操作。从一开始，加倍得二，加倍得四，加倍得八，加倍得十六。十六具有 3k 加 1 的形式，所以可以往下跳，跳到五。当然我也可以直接把它加倍，但我决定用另一条规则，跳到五。然后到十，到二十，到四十。瞧，四十又是 3k 加 1 的形式，于是可以往下跳到十三，再往上到二十六，如此等等。我可以在数的集合里走各种路径。问题是：我能到达哪些终点？

这是通往七的最短路径。这是一条很滑稽的路径：我先变大，再变小，再变大，再变小，再变大，再变小，再变大，再变小，再变大，最后终于落到七。这是一条颇为混沌的路径，而它已经是到达七的最短路径了。

你可以看到，如果我把这些数叫做「柯拉茨数」，然后问：某个给定的数是不是柯拉茨数？这可远不像判断斐波那契数那么平凡，因为我不知道到达它的路径会有多长。能到达三吗？这里是检验过程。事实上可以到达三，但如果从一出发把所有可能的路线都试一遍，我会走向各种不同的方向。结果这一条是有希望的路线，可我们事先并不知道该走这一条。

再看二十七，这是一个著名的例子。这是到达二十七的最短路线，它一路往上走，我把这个数标成绿色并放大了，它一直升到九千二百三十二。这就是到达二十七的最短路线：你必须一直升到九千多，才能回头降到二十七。这实在令人吃惊。这里有一幅图，不知为什么底部被裁掉了一点，不过没关系。大家能看到那幅图吧？它先是混沌地跳动，然后猛地冲到那么高，再降下来，再冲高，再降下来，跳来跳去，最后才到达二十七。这是一幅很有意思的图。

所以我要说的是：这不是一种通过递归分解成更小情形来做的检验，而且它不保证成功。如果我问，用这些规则能否到达五百四十二？我们事先不知道要花多久，甚至不知道能不能到达。柯拉茨猜想断言，每一个正整数都能以这种方式到达。这已经检验到了几十亿甚至更远，每个数都行得通，但从来没有被证明。

哥德尔并不知道柯拉茨数，因为它们是在他的工作完成之后才被发明的。但他理解这里面的道理。

哥德尔的洞见：证明本身是数学对象

哥德尔有一个深刻的洞见。在之前的几个世纪里，人们用数来代表各种各样的东西。大家都知道，我指的是科学界的人都知道，可以用方程来模拟物理世界：比方说行星质心的坐标可以看成数，而有一些方程支配着它们随时间的演化。所以人们明白，数可以模拟世界。

而哥德尔看到的是，数，确切地说是整数而不是实数，可以很轻易地模拟一些人们从来没有当作数学对象来看待的东西。在开普勒和牛顿之后，行星沿轨道运行似乎显然是一种数学对象，可以用遵循微分方程的实数来模拟。但罗素和怀特海发明的那种形式系统本身就是一个数学系统，这一点却从来没有人想过。人们不把构造证明的过程看作一个数学过程，不曾用数的眼光去看它。哥德尔认识到的是：符号操作本质上就是一种数学运算，因此可以用整数来建模。

这里有一段巴赫的乐谱。你可以想象把这段乐曲编码成一个非常大的整数。编码的具体方法与眼下的讨论无关，但你可以想象这是办得到的。然后你可以针对那个整数提问，而这些问题实际上就是关于这段乐曲的问题：表面上是在问整数，同时也是在问乐曲。比如：这段曲子有多少个音符？这是一个数学问题，你可以通过查看代表它的那个大整数来回答。曲子的调号是什么？它是不是巴赫写的？这一个就有点难以想象了：一个数学运算，拿到一个大整数，就能告诉你它所代表的曲子是不是巴赫写的。但你可以想象，也许它是一个数学问题。作曲家是哪国人？这就更棘手了。我只是想举出几类你可以想象去问的问题：有些看起来平凡，比如有多少个音符；有些看起来难一些。

现在把同样的做法用到符号串上。哥德巴赫猜想是一串符号，按我刚才的写法，大概有三十来个符号。你可以想象用某种方式把它编码成一个大整数，我马上会解释哥德尔是怎么编码的。假定你有了一个在某种意义上代表这个符号串的大整数，那么你可以问：这个串有多少个符号？这应该是能算出来的。它是不是乘法表里的一个事实，也就是说，它是不是一个单纯的乘法，像二乘二等于四，或者九乘八等于七十二？它表达的是这个，还是别的东西？它是真是假？能不能对这个大整数施加某种数学运算，从而知道它是真陈述还是假陈述？它是不是直接从另一个陈述推出来的？它是不是《数学原理》的定理？如此等等。

哥德尔配数

那么他是怎么做的呢？（这是一张哥德尔与一位身份不明的农民的合影。）哥德尔把符号串映射到大整数，利用的是这样一个事实：任何整数都可以唯一地分解为素因数。六是二的一次方乘以三的一次方，二十五是五的平方，三十七本身是素数，它已经是自己的分解。

再看一个比较大的整数，一千七百。把它分解，得到二的平方乘以五的平方乘以十七。这就是它的素因数分解。现在看这些素数的指数。从头数到最大的那个素数十七，中间的素数是二、三、五、七、十一、十三、十七。在这个分解里，每一个素数都有一个指数，其中大多数是零：二的指数是二，三的指数是零，五的指数是二，七的指数是零，十一的指数是零，等等。于是我就有了一个由这个大整数编码的小整数序列。

这正是哥德尔看到的：一个大整数可以代表一列小整数，而且是任意长的一列小整数。于是，他把怀特海和罗素在《数学原理》里做的一切，重新表述成对大整数的一系列运算。不再把它看成对符号串的操作，而是看成对大整数的操作。

举一个例子，看看哥德尔怎样把一个符号串编码成大整数。我选的是前面的第一条公理：对于所有的 a，a 的后继不等于零，也就是说没有负数。数一数它有几个符号：一、二、三、四、五、六、七、八，八个符号。那么我们就取前八个素数，分别取不同的幂。我在这里写的是二的「倒 A」次方。这看起来可能不像一个整数，但你可以把倒 A 想成火星文里的一个数字，这不过是火星记法而已：倒 A 在火星记法里也许是七，小写 a 也许是九。这里每一个符号其实都是火星记法里的一个整数。所以我这样做的时候，只不过是在造一个大整数，仅此而已。而如果我想知道它是为哪个公式造的，只需把这个大整数分解，看指数序列，就能一个符号一个符号地拼出我编码进去的那个串。

哥德尔就是用这种办法把符号串编码成大整数的。这里产生了一种歧义：这个大整数是数吗？是。它是公式吗？从某种意义上说也是。它是一个可以进行数学计算的公式，因为它代表着这个公式。如果我们是在那些允许从一个串走到另一个串、从一个数走到另一个数的形式操作的语境里处理它，那么它就可以被看成一个公式，只是用一种滑稽的记法写出来的公式。

屏幕上这个整数，实际上代表《数学原理》的一条公理。它很大，因为那条公理是一个复杂的陈述，需要很多符号，而且这里用的是哥德尔本人的编码系统。做「哥德尔配数」（Gödel numbering）有很多办法，其他办法可以简单得多，我只是觉得看到一个大整数代表着《数学原理》的一条公理很有意思。你可以通过分解它来确认这一点。分解可能要花些时间，但一旦分解出来，就能逐个符号地准确还原出这条公理说了什么。

不过，要弄清它是不是定理，就是另一回事了。当然，如果你认出它是公理，那就完事了。可一般来说，给你一个整数，不一定是这一个，随便哪一个整数，它代表的是不是一个合式公式？这是一个很容易的问题。你只要看指数，还原出公式，你知道怎么把它拆开。而且你甚至可以绕过还原成《数学原理》记法这一步，直接对整数本身进行操作：可以有一些规则告诉你怎样把这个整数拆成更小的部分，再拆成更小的部分，从而告诉你这个整数是否代表一个合式公式。这同样是机械的，而且与拆解符号串并问它是否合式的过程是同构的。这是同一个问题，只是换了一种记法来问。

定理数像柯拉茨数

那么，一个给定的整数代表的是不是一个定理？这就没有明显的办法知道了，因为证明就像曲曲折折的柯拉茨路径。这是本次讲座最关键的幻灯片之一。这里是一个证明，证的是加法交换律，最后一行说：对于所有的 d 和 c，c 加 d 等于 d 加 c。它从公理出发，运用推理规则。这个证明相当长，其实已经很短了，但就我们的目的而言算是相当长，而且中途需要一些相当长的陈述。为了推出加法交换律，这是一条崎岖的路。最后我们确实推出来了，但请注意：我们事先不知道这个证明会有多长，也不知道中间阶段的那些串会有多长。这是两个完全未知的东西。

请注意这与柯拉茨数的感觉多么相似。如果我们不把这些东西看成串，而是看成整数，因为记住，它们可以编码成整数，那么我们做的事在本质上完全一样：拿一些比较小的整数，用各种方法进行数学操作，得到一些非常大的整数（相当于那个九千二百三十二），继续操作，得到另一些大整数，最后终于得到我们想要的那个东西。

这就是哥德尔看到的：某样东西是不是定理，这个问题潜在地极其复杂，而它是不是合式公式，则不是一个复杂的问题。

所以，合式公式数，也就是通过哥德尔配数代表合式公式的那些数，就像斐波那契数，很容易检验。定理数，也就是代表《数学原理》定理的那些数，就没这么简单，它们更像柯拉茨数。换一种说法：要造出合式公式对应的数，你只需沿着一条从小整数到大整数的路径往上走，仅此而已，这是一条单调递增的路径。定理数则不是单调递增的路径，它以混沌的方式来回跳跃。

合式公式数通过哥德尔映射与合式公式同构，通向合式公式数的路径是单调的，因而也是单调乏味的，没什么意思。定理数与定理同构，可通向定理的路径不可预测，定理数也一样。这只是在重申前面说过的话：通向定理数的路径是不可预测的曲折之路。

可证性进入算术

哥德尔于是证明了：「定理数」这个概念在数学上的精确程度，与「素数」这个概念不相上下。素数显然是一个数学概念，对吧？它无非是问：把这个数分解时，在一和它自身之间能不能找到因子？这是一个纯粹的数学概念。哥德尔证明的是，「是一个定理数」同样是一个完完全全的数学概念。

你是这样开始的：先宣布某一组数是定理数。是哪些呢？代表公理的那些数。公理按定义全都是定理，所以公理数全都是定理数，它们是直接给定的。你被告知：这五个，或者这十个，反正有多少条公理就有多少个，这些数都是定理数。然后你被给予一些形式规则，允许你操作这些数，从它们造出新的数，有时更大，有时更小，但总之是新的数。这些数就叫定理数。它们与柯拉茨数一样是数学的，与素数一样是数学的，与斐波那契数一样是数学的。

哥德尔所做的，就是把关于可证性的讨论带进了《数学原理》所处理的论域。《数学原理》处理的是什么？是关于整数的陈述。这个整数是不是素数？这个整数是不是柯拉茨数？是不是斐波那契数？是不是合式公式数？这些全是数学问题。这个整数是不是定理数？这也是一个数学问题。然而，它在密码的意义上说的是：这个特定的定理，这个特定的串，是不是定理？当你问「这是不是一个定理数」的时候，你实际上是在问「这个串是不是《数学原理》的定理」。

所以，尽管罗素和怀特海一直以为自指在他们的系统里不可能出现，哥德尔却借着哥德尔配数这匹特洛伊木马，把自指偷运了进去。因为一旦有了与《数学原理》里的结构同构地运作的数，你就能用数来谈论《数学原理》的全部结构。

哥德尔句 G：真而不可证

我不打算详细解释他是怎么做到的，但他不仅把「定理数」的概念引入了《数学原理》系统本身，还写下了一个非常特殊的串，表达如下的陈述：某个特定的整数 G 不是定理数。记住，「定理数」只是一个数学概念，这就像说「整数六百四十一不是素数」一样。顺便说一句，那句话是假的，六百四十一是素数，不过这无关紧要，它就是一个数学陈述。「整数 G 不是定理数」也是如此。

然而，结果发现，整数 G 恰恰就是表达这个陈述的那个串所对应的数。这就是哥德尔的公式。它用《数学原理》的记法说：这个小写的 G 不是定理数。它说这个数具有某种数论性质，而在这么说的同时，它也在说，这个数所代表的公式不是定理。而碰巧，那个公式恰恰就是这个陈述本身。所以他真的构造出了一个陈述，这个陈述说自己不是定理。这就是马库斯放在屏幕上的那句话：这个陈述不可证。

我又加了一小条：这是同一个断言，只是有两种理解方式。「某个数具有某种数论性质」，以及「某个公式不是《数学原理》的定理」，二者是完全相同的陈述。

后果：真与可证分道扬镳

这是我最后一张幻灯片，让我以谈谈这个构造的一些后果来结束，不是全部后果，只是其中一些。

这个构造造出了一个谈论自身的陈述。而这恰恰是让罗素心中充满恐惧的东西。在他看来，自指是一切悖论的根源，他费尽心力确保它不成为《数学原理》的一部分。而哥德尔却借着哥德尔配数这匹特洛伊木马，真的把它带进了《数学原理》内部。

哥德尔造出的陈述说自己不可证。我们来想一想。假设它是可证的，那么它就是一个假陈述，因为它说的是自己不可证。可如果它是可证的，就意味着一个假陈述可以被证明。这太可怕了。我们不希望有任何假陈述是可证的，那将是《数学原理》的毁灭。没有人相信会有假陈述可证。所以我们必须回头撤销那个假设，也就是它可证的假设。于是它不是可证的。可这正是它所说的！它说的正是自己不可证。这样一来，它说的是真的，而正是因为这个缘故，它不可证。

这几乎像一个真正的悖论：它不可证的确切原因，就在于它是真的。这与数学家们所期望的恰恰相反。他们希望可证性与真理是同义词。而这个串不可证的确切原因，竟然是它为真。非常非常奇怪。

这个构造表明，《数学原理》里存在真而不可证的陈述。但它并不只适用于《数学原理》，而是适用于任何具有这种结构的系统。它不依赖于《数学原理》的任何细节，不依赖于它用的具体公理，也不依赖于它用的具体推理规则。它唯一依赖的，是存在一些公理和一些推理规则这个想法。它表明，在任何丰富到足以容纳数论真理的系统里，都存在真而不可证的陈述。

你可以把这个陈述作为新公理加进去，但这无济于事。因为那是一个新系统，有一组新的公理，你只要对这个稍大一点的系统再施行一遍哥德尔的程序，就又得到一个真而不可证的串。你可以这样永远进行下去。所以漏洞有无穷多个，而且不可能被系统地全部填补。

不可判定性侵入常规数学

我想说的最后一件事是，近几十年来的研究表明了一点。哥德尔的陈述说的是某个数具有某种性质，可这看起来是一种非常人为的性质，它是用哥德尔造出来的那套映射构造出来的。人们可能觉得这种公式实在太深奥了，即便这类东西存在，它们也远离任何数学家真正会去谈论的东西。但事实证明，完全不是这样。

约翰·康威（John Conway）及其同事证明了：如果把柯拉茨问题看作一族问题中的一个，这族问题都是那种类型的，基本上就是对整数做乘除、这样上上下下地走。我不打算精确定义这一族问题，但你可以想象：柯拉茨问题常被称为「3n 加 1 问题」，你可以想象一个「5n 加 1 问题」，或者「5n 加 2 问题」之类的。把所有这类问题放在一起考虑，已经证明其中存在一些问题，由于哥德尔式的原因而不可判定。也就是说，哥德尔构造被包含在其中：可以证明哥德尔构造等价于某个柯拉茨型的问题。而这是一类极其正常的数论问题，一点也不显得晦涩、怪异、非数学或者人为，它是一种非常自然的数学问题。

同样已经证明的是，存在不可判定的丢番图方程（Diophantine equations）。丢番图方程大致是这样的形式：一些整数取一些幂的和，等于另一些整数取一些幂的和。这是一种非常非常简单、基本的代数方程，而其中存在不可判定的例子。

所以，哥德尔工作的一个后果是：一些形式极为标准的数学问题，已经被证明是不可判定的。不可判定性并不只栖身于遥远怪异的角落，而是侵入了非常标准的构造。这是一个真正令人震惊、也有几分令人恐惧的想法。我就讲到这里。