哥德尔不完全性定理

如何通俗易懂地阐述哥德尔不完全性定理，恐怕对任何人来说都是个挑战。侯世达用七百多页做到了这件事，其困难可见一斑。

不过，我想通过这篇短短的文章，让更多人了解乃至接受这个定理，看一看外面的世界。

哥德尔定理

对于拥有高中知识的每个人，应该都听说过公理系统。最常见的，莫过于在欧几里得五条公理的基础上构建的整个欧式几何公理系统。从这五条公理出发，可以推出欧式几何的所有定理。

但你有没有想过，在欧式几何体系中，是否所有命题都可被证明或证伪？

大多数人可能会不假思索地回答“是”。但出乎意料的是，存在一些命题，既不能被证明，也不能被证伪。换句话说，它是不可判定的。

这就是哥德尔定理所描述的事情。当然，哥德尔说的更精确和严格，但我们只需要体会其中的思想就够了。

神奇的命题

什么命题具有如此神奇的性质呢？其实就是悖论。我们可以很容易地用自然语言构造出一个悖论，比如：“这句话是假的。”如果这句话为真，那么它的内容又说它是假，互相矛盾。如果这句话为假，那么它的内容说明它不是假的，又互相矛盾。因此这句话既不真又不假，它是个悖论。

然而在数学上如何构造类似的悖论呢？对于任意一个形式系统（你可以认为形式系统就是公理系统），记作TNT，我们构造TNT中的一个命题：“本命题不是TNT中的定理”，记该命题为G，又称哥德尔命题。

对这句话的分析和之前一样。如果G为真，那么G不是TNT中的定理（在形式系统中，定理代表那些可证的命题），于是TNT中出现了不可证的真命题。如果G为假，那么G是TNT中的定理，这是不可能的，假命题不可能被证明。因此结论是G为真，但不可证。

G的提出就直接证明了哥德尔定理。这很直观。但事实没有我们想象的这么简单，哥德尔定理要想成为一条定理，必须有严格的证明过程。而使用模糊的自然语言描述的G，再加上简单的逻辑分析，是不足以支撑一项定理的。

我们需要深入哥德尔的工作，看看他如何巧妙地在形式系统中构造出了这个G。

构造哥德尔命题

哥德尔把关注点放在数论系统上。在当时，数论系统已经是一个被广泛认为比较“完全”的系统。它的完全性体现在，对于任意给出的数论命题，都可以被证明或证伪。当然对于形式化了的数论系统，是有一套描述命题的规则的。这套规则包括我们常见的初等运算、量词逻辑∃∀、自由变量等。

哥德尔命题G的特点在于，它的内部包含对其自身的概括，我们称其为自指。事实上，命题G可以更清晰地描述为：“G不是TNT定理”。因此，构造G的关键在于，如何在命题中包含自身。

假设给定一个命题Q，“Q不是TNT定理”的形式化描述为：~∃a : Proof(a, Q)。其中，a代表形式化的证明过程。该描述的含义是，不存在证明过程a，使得a推导的结果为Q。

举一个最简单的例子，~∃a : Proof(a, 0=-1)是个真命题，而且可以证明，因为0=-1的确不成立。

接下来就遇到了困难，如何才能把~∃a : Proof(a, Q)这个命题带入其自身呢？比如这样？

~∃a : Proof(a, ~∃a : Proof(a, Q))

或者这样？

~∃a : Proof(a, ~∃a : Proof(a, ~∃a : Proof(a, Q)))

在上面的尝试中，我们把命题本身带入S。可问题是，我们永远无法完全展开这个式子，这里面存在无穷递归，除非把它展开成一个无限长的命题。

等等，我们似乎混淆了一些概念。Q是任意一个需要证明的命题，因此我们可以把整个命题本身带入Q。但带入后的命题中再次出现了Q，于是我们再次带入Q。看起来似乎是正确的做法，但实际上Q不可以无限展开，我们混淆了命题在不同层面上的含义。一个命题，当你在它内部思考的时候，它的含义是它真正包含的意义。但同样的命题，当你跳出这个圈子，从外面观察它的时候，它的含义只是一个符号串。也就是说，当我们展开Q的时候，替代Q的命题不应该被当做一个有内含的命题，而只是一个符号串。只有保持这样的观点，命题才能维持其自身含义于同一层，不至于出现一个命题中包含着多个层次的意义。

为了能够在命题中讨论其它命题而不造成混淆，哥德尔发明了一种巧妙的方法，称为哥德尔配数法。简单来说，就是对每个字符分配一个特定的整数，整个命题以无歧义的方式把这些整数串起来，得到一个超长的整数。如果你学过编程，可以把哥德尔配数当做对每个字符进行Unicode编码。如此一来，对~∃a : Proof(a, Q)的每个字符进行哥德尔配数\u007e、\u2203、\u0061、\u0020、\u003a、\u0020、\u0050、\u0072、\u006f、\u006f、\u0066、\u0028、\u0061、\u002c、\u0020、\u0051、\u0029，再把这些数字串起来，得到007e220300610020003a002000500072006f006f006600280061002c002000510029。现在，我们用一个超长的整数（十六进制）表示了上面的命题，如果把该整数作为Q重新带入上面的命题，会发生什么？

仍旧需要提醒大家，此刻，长整数虽然代表了一个命题，但我们必须把它按照整数对待，而不必顾及它内部的含义。在TNT系统中，整数的表示方式为S…0(若干个S)。有多少个S，就表示多大的整数。现在可以带入了，我们得到~∃a : Proof(a, S…0(007e220300610020003a002000500072006f006f006600280061002c002000510029个S))。

忙活了这么久，也许大家已经忘记了我们到底在做什么。回顾前一节，我们其实是想要构造一个哥德尔命题G：“G不是TNT定理。”我们成功了吗？如果你仔细看看~∃a : Proof(a, S…0)这句话，很遗憾，我们并没有成功。因为S…0表示的是~∃a : Proof(a, Q)这个定理，而不是~∃a : Proof(a, S…0)本身。这种做法似乎又绕进了一个死胡同，无论如何都不能在命题中表示自己。

我们需要更强力的手段。

摧毁一切的利刃

再来思考为什么上面的方式不行。因为Q被替换成了上一时刻的命题，在替换的同时，整个命题也变了。显然，这样的替换太过死板，我们需要一种灵活的替换，能够随着整个命题的变化而变化的替换。

很容易想象，不应该使用Q作为替换的变量，而应该在Q内部提供一个自由变量。比如，这样一个带自由变量b的命题：Statement(b)。用这个命题代替前面用到Q的地方，得到：~∃a : Proof(a, Statement(b))。

现在把整个命题带入b，如果，我是说如果，Statement(b)恰好也能得到带入后的整个命题，那么带入后的整个命题就是我们苦苦寻找的哥德尔命题G。

显然，这样的Statement(b)是整个命题的同构，它们具有相同的性质。当把整个命题带入b时，从抽象的层面来看，其实是把一个命题带入其自身的自由变量中。如果我们让Statement(b)也具有这样的性质，当传入一个带自由变量的命题b时，Statement(b)把b带入b中的自由变量，得到的命题恰好是整个命题带入b后的结果！

我们再用符号的形式解释一遍上面那段话。对于一个含一个自由变量的命题B：~∃a : Proof(a, Statement(b))。将B带入自由变量b，得到命题G：~∃a : Proof(a, Statement(B))。此时，G就是哥德尔命题。这是因为，根据我们前面对Statement(b)的定义，它是把b带入b中的自由变量后得到的命题。在这里就是把B带入B后得到的命题，而这恰好就是我们生成G所采取的操作，因此Statement(B)就是G。

当然，这里还留有一个疑问，Statement(b)存在吗？答案是肯定的。对于任意一个含一个自由变量的命题b，我们很容易得到Statement(b)。举个例子，给定一个命题b：a=S0。其中a是自由变量。对b进行哥德尔配数，得到0061003d00530030。该数在TNT中的符号表示为S…0(0061003d00530030个S)。将S…0带入a，得到S…0=S0，这就是Statement(b)。显然，这里的Statement(b)是假命题。

云销雨霁

终于，我们成功得到了哥德尔命题。从而也就验证了哥德尔定理。

得知这个定理是非常震撼的，它似乎意味着数学大厦的不完美。但也大可不必惊慌，因为哥德尔命题并不常见，它更像一个刻意构造出来的东西，仅仅用来解读数学的本质。

哥德尔的发现启发了图灵证明停机问题，并对以后的人工智能领域产生了深远影响。这是后话。

笔者水平有限，短短的一篇文章的确很难把哥德尔定理讲清楚。如果读到这里的同学仍然对哥德尔定理抱有兴趣，推荐读一读《哥德尔、艾舍尔、巴赫：集异璧之大成》这本书，会看到一片新天地。

参考资料

《哥德尔、艾舍尔、巴赫——集异璧之大成》 侯世达
如何简单清晰地解释哥德尔不完备定理？ LLLBK