哥德尔不完备定理 哥德尔不完备定理”到底说了些什么？

【中文网上关于哥德尔不完全定理的文章很少。这篇文章写了很久，花了很多时间打磨，希望对热爱数学和逻辑的人有所帮助。本文将对哥德尔不完全定理的理解分为五个部分，并建议只想初步理解的读者可以把重点放在第一部分；想了解一些背景的读者可以练习到第二个层次；想更深入了解哥德尔证明思想的读者建议练习到第三个层次；如果你真的感兴趣，想了解更多哥德尔的证明过程及其严谨性的读者可以实践到第四位；想多了解读者，可以练到第五关。——作者]

1931年，库尔特弗里德里希·哥德尔发表了一篇影响深远的论文《论《数学原理及相关系统I》的形式上不可判定的命题》[1](论文原文以德文发表，英文译名在此给出)。今天我们一般把论文中提出的定理称为“哥德尔不完全定理”。80多年过去了，哥德尔不完全定理的影响仍然是持久而深远的，特别是它引起了许多非数学家的兴趣，引发了各种各样的解释。不幸的是，有些解释是不准确的，甚至是错误的。更严重的是，有些人出于对哥德尔不完全定理的无知，甚至开始怀疑和批判人类的理性，以至于发展到相信和鼓吹不可知论。最近在认真学习哥德尔论文原文(英文翻译，实在不懂德文)和相关资料的基础上，加深了理解，同时也希望尽自己最大的努力分享一下对哥德尔不完全定理的理解，澄清一下对哥德尔不完全定理的误解。

哥德尔的不完全定理是数学和逻辑领域划时代的成就，使人们对数学研究的基础有了更深刻、更准确的认识，也是现代逻辑史上的重要里程碑。哥德尔的不完全定理虽然伟大而深刻，但我个人认为并不深刻。对于一个普通人来说，只要肯动脑，一定程度上就能准确理解。当今互联网时代，网上对哥德尔不完全定理有很多介绍和解释；60多年前，美国两位作家欧内斯特·内格尔和詹姆斯·纽曼所著的《哥德尔证明》是科普中哥德尔不完全定理的重要著作。现在网上能看到的介绍哥德尔不完全定理的中文文章大多转述自《哥德尔的证明》这本书。但是这本书写的太早了，一些新的结论还不知道。另外，这本书在推广哥德尔的证明时，更说明了背景和思路，用作者自己的理解描述了哥德尔的证明。有些地方不够严谨，有些讲述方法不够准确。摘要:在哥德尔论文原文的基础上，介绍了哥德尔不完全定理的证明，并适当融入了80年来的一些新的理解和结论，希望能帮助数学和逻辑爱好者理解和认识哥德尔不完全定理。

为了帮助更多的人在自己的需要中理解哥德尔不完全定理，下面的绪论将哥德尔不完全定理的理解分为五个部分，从理解定理的基本含义到理解核心证明。读者可以根据自己的内力基础练习到自己的水平，就像练习“干坤大挪移”的神力一样。祝大家都能练出哥德尔不完全定理第五魔功！

第一:“庐山真面目”——对“哥德尔不完全定理”的准确理解

在欣赏一块美玉的时候，不要先听各种专家讲这块玉有多晶莹有价值，而是先拿出来给大家看看，有个感性认识。在哥德尔的论文中，我们一般所说的“哥德尔不完全定理”(有时称为“哥德尔第一不完全定理”)指的是论文中的定理六。原文如下:

定理VI:对于每一个ω一致的本原递归类κ的公式，都有一个先验递归类符号r，使得forall(v，r) nornot(forall(v，r))都不属于Conseq(κ)(其中v是r的自由变量)。

尽量翻译成原文，如下所示:

定理六:对于任意一个具有相同ω(四阶)的原始递归公理集κ，必须有一个原始递归表达式R(三阶和四阶)，这样无论是“R总是成立”的命题，还是“R不总是成立”的命题，都不属于可以从κ(原文中的Conseq(κ))推导出的定理集。

补充说明一下，哥德尔论文中κ所代表的公理集是指包含皮亚诺公理的集合，这一点在哥德尔论文之前就已经讲清楚了，所以在阐述定理六时没有特别强调。

练第一魔的读者可能会问:“大哥，你在说什么？”。别担心，练第一个魔法技能没那么复杂。

先说公理。公理实际上是一个不需要证明就被认为有效的命题。公理系统是指一组公理。通过这些公理和基本逻辑关系，可以推导出更有效的命题，称为定理。公理系统一般认为起源于2300多年前欧几里得写的《几何元素》。在现代科学形成的过程中，人们发现许多命题或结论都可以通过定义一套公理和合理的逻辑推导来证明。公理系统是数学研究和科学研究的基础，数学研究的结果很大程度上是(或依赖于)一组公理系统的推演，而其他科学研究除了公理系统的推演之外，还需要通过系统的实验来验证。

“哥德尔不完全定理”是针对公理系统的结论。它之所以如此伟大和深刻，正是因为它动摇了作为所有科学研究基础的公理体系。在练习第一大魔术时，我们简单理解了哥德尔不完全定理说一个复杂的公理系统(至少包含皮亚诺的算术公理)如果是一致的(相容的，不矛盾的)就是不完全的。这里的完备性是指“任何可以在这个公理系统中描述的命题，都可以在这个公理系统中判断，不是对就是错”。

用白话解释一下，也就是说，在一个没有矛盾的公理系统中，总有一些命题不清楚是对是错(需要注意的是，这意味着在这个系统中不清楚，而不是永远不会清楚)。可能有人说，既然没有矛盾的公理系统有问题，那就来一个有矛盾的公理系统吧。如果你想象一个公理系统，一会儿告诉我们“1+1=2”，一会儿告诉我们“1+12”，相信没有人会把这个公理系统当真。矛盾的公理体系会导致完全的无意义和虚无，这一点在练习第二种神奇力量时会详细阐明。

以上结论听起来很可怕。公理系统一定是没有矛盾的，但是没有矛盾的公理系统会导致一些是非不明的命题。于是各种解释开始出现，比如“哥德尔定理告诉我们数学和逻辑的极限，这几乎是人类理性的极限。它证明了理性不是万能的”，“哥德尔定理告诉我们，人类不可能真正认识世界，永远无法理解宇宙的真理”等等。我相信哥德尔作为人类理性和智慧的杰出代表之一，如果听到这些说法可能会很无奈。

第一，“哥德尔不完全定理”不仅是人类理性的极限，相反，它是人类理性智慧的伟大成就。它告诉我们，正是因为人类的理性智慧，才有可能实现如此深刻的结论。哥德尔通过构造一个在这个公理系统中无法证明的命题，证明了“哥德尔不完全定理”。这个命题的内容是“命题本身在这个公理系统中无法证明”。既然哥德尔已经明确证明了这一点，就说明这个命题无疑是正确的。所以哥德尔不完全定理的证明过程其实告诉我们，有一个正确的命题可以在这个公理系统中表达，但在这个公理系统中既不能证明，也不能证伪。如果说哥德尔的不完全定理澄清了某些界限，那它只是澄清了“某些公理系统的界限”，而不是“数学和逻辑的界限”，更不是“人类理性的界限”。

其次，“哥德尔不完全定理”不仅没有告诉我们“人类不可能真正认识世界”，而是在更深层次上告诉我们人类应该如何认识世界，探索真理。比如在数学中，如果我们发现一个命题还没有被现有的方法、公理和定理证明，我们可以尝试把现有的方法和公理扩展到进一步的研究；正是因为这个原因，费马定理和黎曼猜想被称为“下金蛋的母鸡”。在物理学中，广义相对论的发现过程也是由于狭义相对论的某些推论难以解释(比如一个高速旋转的圆盘会发生扭曲)。爱因斯坦提出了等效原理，果断地扩展了直线空的假设，从而创立了伟大的广义相对论。值得一提的是，哥德尔和爱因斯坦在普林斯顿大学成了非常好的朋友。爱因斯坦晚年曾说过，他之所以经常坚持每天去办公室上班，是因为他可以在路上和哥德尔聊天；爱因斯坦的去世也给了哥德尔的心情很大的打击。

再次，“哥德尔不完全定理”没有给出人类对真理理解的上限。如果一个命题不能在公理系统中判断，并不意味着它不能被判断。对于这类命题，如果属于科学范畴，可以通过科学实验进行判断，从而拓展现有公理体系，发现新的科学规律；如果属于数学范畴，可以通过寻找新的数学工具、数学方法或数学理论，直接拓展现有公理体系，从而准确判断这个命题，进而拓展人类研究的深度和广度。

还有人了解到，数学研究已经证明“在某个公理系统中，不存在可以确定给定命题是否可确定的一般算法”。因此认为存在一个不可判定的命题，不存在“判断一个命题是否可判定的方法”。显然，我们不能准确地认识世界。这个观点不准确。虽然我们确实证明了没有一般的判断算法，但是人类并不是仅仅依靠某一套公理系统和某一套逻辑和算法来理解世界的，人类的思维也不能局限于某一套或某一套公理系统。虽然我们不能设计一个通用的算法来判断一个命题在某个公理系统中是否可以被判断，但这并不一定导致我们无法识别这个命题。举个简单的例子，“Goodstein定理”(这个定理比较简单易懂，练习到第五级的时候会详细解释这个例子)是一个在Piano公理系统中无法判断的命题，但是在集合论中，利用序数知识可以非常简单地证明。

“哥德尔不完全定理”揭示了公理系统的内在深刻性和内在局限性，告诉我们不要指望所有命题都只能从几组公理出发，用基本的逻辑规则机械地推导出来才能判断。从这个意义上说，数学和其他科学都需要不断完善和拓展自己的公理体系(或基本规律)，只有这样才能不断认识到更深刻、更复杂的客观世界。换句话说，哥德尔真实而严格地证明了“科学研究永无止境”这句格言。

二:“深静水流”——“哥德尔不完全定理”的深刻背景

哥德尔为什么会想到证明这样一个“不完全定理”？既然已经到了第二层修炼，就应该多说一点。

哥德尔做的第一件事是用自然数匹配PM中的表达式。在解释“一致性的意义”时，我们专门介绍了PM中的表达式和相应的规则。项目管理中的表达式类似于以下示例:

~(∃z≤x∙(z≠1∧z≠x∧z | x))∧(x & gt；1)(判断X是否素数的PM公式)

Qp (~ pq)(我们已经证明的公式，矛盾系统可以推出任何命题)

哥德尔说，这些表达式是由一些基本符号组成的，是一系列符号；“证明过程”无非是一个表达式的序列，而是一个符号的序列。根据希尔伯特的数学形式化，这些符号、表达式和“证明过程”都是没有意义的。如果有必要，可以给出一些含义来表达一些现象。哥德尔指出，显然这些符号被赋予什么意义与PM系统本身无关，所以哥德尔在这里将这些符号对应于自然数。

所以每个基本符号对应一个自然数，每个表达式对应一个自然数序列，每个“证明过程”对应一个自然数序列。反之，每当给定一个相容的自然数序列，它就可以唯一地对应一个PM表达式；每次给定一个相容的自然数序列时，它可以唯一地对应于一个概率模型证明过程。

进一步地，有了这种对应，对PM表达式或证明过程的一些有意义的判断就可以对应到对某个自然数序列的判断，而这种对自然数序列的判断显然可以利用PM中的表达式来进行。换句话说，通过哥德尔建立的对应关系，我们最终可以用PM表达式来表达有意义的判断。比如，根据预先对应的定义，一个合法表达式对应的自然数序列必须满足一定的规则，显然可以用PM表示，所以我们可以用PM给出一个表达式来表达“某个表达式是否符合”的意思。

由于这种对应(也称为哥德尔对应)对于哥德尔不完全定理的证明至关重要，我们宁愿不厌其烦地给出一个简单的例子，使读者能够准确理解。我们建立了一个类似于哥德尔理论的对应关系，并事先声明这个对应关系只是为了便于理解下面的例子，但实际上这个对应关系不利于证明哥德尔不完全定理。我们建立的对应关系是:PM系统中的所有符合表达式和证明过程都是按照ASCII字符顺序排列，形成一个无穷序列；然后从第一个表达式开始，我们把它对应到自然数1，第二个对应到3，以此类推，直到无穷；然后把所有不符合的表达式按顺序排列，从第一个开始，对应自然数2，4，6，…。这样，PM中的任何表达式和证明过程都对应一个唯一的自然数。我们再定义一个PM表达式，用来判断一个表达式是否符合。设这个表达式为isFm(x)。显然，这种对应下的isFm(x)在PM中应该是“~ (z x = 2z)”(注意PM中的任何数值变量都是0或自然数)。这个表达式其实是判断x是否奇数。如果是，则x对应的表达式是顺应的，否则是不顺应的。所以一个“有意义的表达依从性判断”在PM中表达为一个表达。

当然，除了表达“表达式是否符合”，还应该表达“一个表达式是否可以在PM系统中证明”。哥德尔把这个表达式设置为可证(x)，他表示自然数(或者自然数序列，或者自然数序列的序列，在练习第四重的时候，你会看到哥德尔用了一个巧妙的方法使这些序列都成为唯一的自然数)。X对应的表达式是否可以在PM系统中

最后强调哥德尔在PM中的表达式对应的是自然数，这不是哥德尔研究自然数或数论所做的，而是哥德尔提出的一种构造特殊PM表达式的方法。通过将PM表达式映射到自然数，利用PM系统固有的表达自然数之间关系的能力，可以达到将PM中的命题引入自身的目的。

如果Rq(q)能被证明，则意味着可证明(Rq(q))为真，这显然意味着Rq(q)也为真。根据公式1，~可证明(Rq(q))也成立，“~可证明(Rq(q))”、“可证明(Rq(q))换句话说，如果PM是一致系统，那么只有Rq(q)是不可证明的。

如果~Rq(q)可以证明，说明~Rq(q)是真的。根据公式1，~(~可证(Rq(q))为真，即可证(Rq(q))可证，即Rq(q)为真。这次Rq(q)和~Rq(q)都是真的。因此，如果PM一致，~Rq(q)无法证明。

综上所述，只要PM是Rq(q)命题的一致公理系统，它在PM中既不能被证明，也不能被证明。换句话说，在项目管理系统中，可表达的命题Rq(q)不清楚对错。

通过上面的简单分析，我们得到“哥德尔第二不完全定理”，简单地表述为“一个包含皮亚诺公理的公理系统，在这个公理系统中不能证明它的一致性”。

对于愿意学习的读者，可能还会有各种各样的疑问？有人可能会问，哥德尔的映射PM表达式对自然数有什么用，如何用这种方式表达像可证(x)这样有意义的命题？有人可能会问，你第一次练习的时候说的“ω一致性”和“原始递归”到底是什么意思？可能有些读者会问，第三种介绍的证明思路不就是一个严格的证明过程吗，为什么要培养第四种呢？对于需要解决这些问题的读者，请和我一起练习第四种魔力。

第五:“洞察过去与现在”——拓展“哥德尔不完全定理”的相关知识

就像金庸的小说《屠龙记》一样，连创作者都没有修炼到最高境界。我也不敢说自己培养了第五种魔力。所以这部分有点简单，只说两个方面。

(一)“哥德尔不完全定理”的例子

自1931年哥德尔提出不完全性定理以来，人们逐渐相信了复杂公理系统的不完全性。80年来，人们逐渐发现了越来越多的哥德尔不完全定理的例子，其中最著名的是“选择公理和连续统假设是集合论中的不确定命题”。1963年，美国数学家保罗·寇恩最终证明了这一点，并解决了希尔伯特的23个问题中的第一个，这也是哥德尔的贡献。

那么有没有直接符合哥德尔论文条件的例子呢？也就是皮亚诺公理体系中的不确定命题？1982年，人们发现了算术命题的第一个例子——古德斯坦定理，它不属于哥德尔结构，在皮亚诺公理体系中不能被证明或证伪。

古德斯坦定理说古德斯坦序列在有限步内会收敛到0。

Goodstein序列是这样的:首先选择一个正整数g1，例如，设g1=18，然后写成2的幂和(18 = 24+ 21)，然后也写出大于2的指数。如果重写后的表达式中有大于2的指数，那么继续把这样的数写成2的幂，直到所有的数都小于或等于2，最后得到，

g1=22^2+21

这种写法叫做遗传基数2记法。G2就是用这种写g1的方法把所有的2都变成3，然后从新数中减去1，就是，

g2=33^3+31-1

注意，这是一个非常大的数字，大约是7.6×1012。继续，以3的幂的形式写g2，直到没有大于3的数，然后用4代替3，所得数减1得到g3。通过类比，我们可以通过连续计算得到一个级数。这个系列就是古德斯坦系列。

让我们以g1=18为例，看看这个系列的前几项:

g1=22^2+21=18

g2=33^3+31-1=33^3+2×30=7.6×1012

g3=44^4+2×40-1=44^4+40=1.3×10154

g4=55^5+50-1=55^5=1.9×102184

单看这些项，我们肯定会认为这个级数以极快的速度发散到无穷。事实上，这个系列将在有限的步骤中收敛到0。

古德斯坦定理是一个容易理解的算术命题，其证明可以通过集合论、良序定理、超限序数等理论和知识来完成。一般的思路是利用超限序数ω构造一个与Goodstein级数平行的级数。这个新数列的每一项都不小于Goodstein数列的对应项，而且这个新数列是递减的，经过有限步后必然收敛到0。

证明了集合论中的Goodstein定理简单易懂。但是当我们在Piano公理系统中研究这个命题的时候，神奇的事情发生了。1982年，劳里·柯比和杰夫·帕里斯发现这个定理在皮亚诺公理体系下是不可证明的。这个定理只是哥德尔不完全定理的一个典型例子。

前面说过，哥德尔的不完全性定理是通过构造一个不可验证的算术命题来证明的。但是，随着我们练习了第五魔功，我们清楚地知道，哥德尔构造的这个算术命题几乎不可能直接表达，因为做起来太复杂了。所以哥德尔只是通过构造方法证明了不可证明命题的存在。直到古德斯坦定理的发现，我们终于可以在皮亚诺公理体系中看到一个不确定的算术命题。Goodstein定理简单易懂，计算过程清晰，但在Piano的公理体系中无法证明，想想就觉得很神奇。所以我们更应该佩服哥德尔的伟大贡献。

(2)有一致完整的公理体系

关于哥德尔不完全定理，我们讨论了这么多，估计大家无疑都相信了这个定理。在这里，我们要再次提醒大家，哥德尔不完全定理有一个前提条件，那就是“包含钢琴公理系统”。也就是说，不是任何一致的公理系统都是不完整的。那么，真的存在一致完整的公理体系吗？答案是肯定的。

我可以为这里的每个人即兴创作一个公理系统:

这个公理系统只有两个数字0和1，只有一个二进制运算“+”。它的三个公理如下。

(1)0+0=0

(2)0+1=1+0=1

(3)1+1=0

公理系统已经建立。

这个公理系统极其简单，在这个系统中能表达的命题都可以证明(比如1+1+1+0=1)，而且这个公理系统必须是一致的，“ω一致”。

事实上，如果一个公理系统比较简单，不能承受哥德尔对应中的最小编码要求，那么这个公理系统的一致性和完备性之间是否存在矛盾，就不属于哥德尔定理所覆盖的范畴。对于一些简单的公理系统，可以证明它们是一致的、完备的。当然，我构建的公理系统太简单了，根本没有用。在实际数学中，有一个系统叫做预伯格算法(Presburger algorithm)。因为不包括乘法，所以其实是一致的，完整的。有兴趣可以通过Google详细了解。

另外，如果一些复杂的公理不足以定义自然数，那么即使这样的公理包含自然数，也可能不受哥德尔不完全定理的约束。比如Taskey证明了实数和复数理论都是一致的、完备的一阶公理系统，虽然都包含自然数；再比如，著名的欧氏几何，在补充了平行公理和实数理论之后，也是一个一致完整的一阶公理系统。

《哥德尔不完全定理》确实很棒，但不需要神化。它有它的前提条件，有它的适用范围，当然也有划时代的伟大贡献！

结论

至此，五大神通都已修炼完毕。“哥德尔不完全定理”是划时代的成就，也是哥德尔一生中唯一的重大研究成果。作为一名数学家和逻辑学家，哥德尔一生取得了如此巨大的成就，这是值得的。作为读者，如果能通过这个培养过程，真正理解和领会哥德尔的不完全定理，我认为值得花时间去阅读和思考。

[1]哥德尔论文的英文版可以在http://www.research.ibm.com/people/h/hirzel/papers/canon·00-goedel.pdf的网上找到。

[2]我实在不忍心这样形容罗素和怀特海。参见维基百科的《https://zh.m.wikipedia.org/zh-hans/数学原理》，了解“智力枯竭”这一表述

[3]参见http://blog.sciencenet.cn/blog-320682-969874.html科学网张银生先生的博客

本文来自赵科学网博客:

链接地址:http://blog.sciencenet.cn/blog-409681-1067019.html