“哥德尔不完备定理”到底说了些什么？——（一）

已有 45376 次阅读 2017-7-18 18:50 |个人分类:科学|系统分类:科普集锦| 数学, 逻辑, 哥德尔, 不完备定理

“哥德尔不完备定理”到底说了些什么？——（一）

【中文网上深入介绍哥德尔不完备定理的文章很少，我这篇文章写得很长，花了不少时间打磨它，希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定理分为了五重，建议只是想初步了解的读者，可以重点看第一重；希望了解一些背景的读者，可以修炼到第二重；希望较深入理解哥德尔证明思路的读者，建议修炼到第三重；如果确实感兴趣，希望详细了解哥德尔证明过程以及其严谨性的读者，可以修炼到第四重；如果还想多知道一些知识的读者，可以练到第五重。

——— 作者】

1931年，库尔特∙弗雷德里希∙哥德尔（KurtFriedrich Gödel）发表了一篇影响深远的论文“On formally undecidablepropositions of Principia Mathematica and related systems I”^[1]（论文的原文是用德文发表的，这里给出的是英译名）。今天，我们一般笼统的把论文中提出的定理称为“哥德尔不完备定理”。80多年过去了，“哥德尔不完备定理”的影响仍然持续、深远，特别是引起了很多非数学界人士的兴趣，引发了各种各样的解读。很遗憾，有一些解读是不准确的，甚至是错误的；更为严重的是，有一些人出于对“哥德尔不完备定理”的一知半解，甚至开始怀疑、批判人类的理性，以至于发展到相信、鼓吹不可知论。近期，我在认真研读了哥德尔论文原文（英译版，本人实在是不懂德文）和相关资料的基础上，加深了自己的认识，同时也很希望尽自己绵薄之力，分享对“哥德尔不完备定理”的理解，厘清对“哥德尔不完备定理”的误解。

“哥德尔不完备定理”是数学、逻辑学领域的划时代成果，使人们对于数学研究基础的认识更加深刻、准确，同时它也是现代逻辑史上的重要里程碑。“哥德尔不完备定理”虽然伟大、深刻，但是个人认为它并不深奥。对于一个普通人，只要愿意动脑，都可以在一定程度上准确理解它。当今的互联网时代，网上有不少对“哥德尔不完备定理”的介绍和解读；60多年前，两位美国作家欧内斯特·内格尔（Ernest Nagel）和詹姆士 R. 纽曼 （James R. Newman）撰写的的著作《哥德尔证明》更是科普“哥德尔不完备定理”的重要作品。如今网上能看到的中文介绍“哥德尔不完备定理”的文章，绝大部分是转述《哥德尔证明》这本书的内容的。不过这本书撰写太早，有些新的结论当年尚不了解；另外这本书在普及哥德尔证明的时候，更多的是讲解背景、思路，并用作者自己的理解来讲述哥德尔的证明，个别地方不够严谨，一些讲述方式也不够准确。本文则全部基于哥德尔论文的原文来介绍“哥德尔不完备定理”的证明，并适当融入一些80多年来新的认识和结论，希望能帮助数学、逻辑学爱好者了解并理解“哥德尔不完备定理”。

为了帮助更多人在各自需要的层面上理解“哥德尔不完备定理”，下面的介绍把理解“哥德尔不完备定理”分为了五重，从对定理的基本含义的理解一直到对核心证明的了解都包括了进来。读者可以像修习“乾坤大挪移”神功一样，依照自身内力基础，修炼到适合自己的层面即可。祝愿大家都能练成“哥德尔不完备定理”第五重神功！

第一重：“庐山真面目”——准确了解“哥德尔不完备定理”

赏玩一块美玉的时候，首先不应该是听各类专家讲这块玉多么晶莹剔透、多么价值连城，而应该是首先把玉拿出来让大家看看，有个感性认识。在哥德尔的论文中，我们一般所说的“哥德尔不完备定理”（有时候也被叫做“哥德尔第一不完备定理”）是指论文中的定理VI，原文如下：

TheoremVI: For every ω-consistent primitive recursive class κ of formulae, there is aprimitive recursive class-sign r , such that neither forall(v,r) nornot(forall(v,r)) belongs to Conseq(κ) (where v is the free variable of r).

尽量原汁原味的翻译如下：

定理VI：对于任意一个ω一致_{（第四重）}的原始递归公理集合κ，一定存在一个原始递归_{（第三重、第四重）}的表达式r，使得无论是“r总成立”这个命题，还是“r不总成立”这个命题，都不属于通过κ可推导出来的定理的集合（原文中的Conseq(κ)）。

补充说明一点，哥德尔论文中的κ所代表的公理集合，是指蕴含了皮亚诺算术公理（Peano Axioms）的集合，这是在哥德尔论文的前面明确了的，所以在阐述定理VI时就没有再特意强调。

修炼第一重神功的读者可能会问了“大哥，你说的这些都是啥？”。别担心，修炼第一重神功没那么复杂。

让我们先从公理说起，公理其实就是无需证明而被认定为成立的命题。公理体系是指一组公理的集合。通过这些公理和基本的逻辑关系，可以推导出更多成立的命题，称为定理。公理体系一般被认为发源于2300多年前欧几里德撰写的《几何原本》。在现代科学形成的过程中，人们发现通过定义一组公理再加上合理的逻辑推演，可以证明很多命题或结论。公理体系是当今数学研究和科学研究的基础，数学研究成果就是（或者说在极大的程度上依赖于）一组公理体系的推演，而其它科学研究除了依赖公理体系进行推演外，还需要通过系统的实验来进行验证。

“哥德尔不完备定理”是针对公理体系的一项结论，它之所以如此伟大且深刻，正是因为它撼动的是一切科学的研究基础——公理体系。修炼第一重神功的时候，我们简要理解“哥德尔不完备定理”说的是：一个足够复杂的公理体系（至少蕴含了皮亚诺算术公理），如果它是一致的（相容的，无矛盾的），那么它就是不完备的。这里的完备，指的是“对于任何可在这个公理体系内描述的命题，都可以在这个公理体系内得到判定，要么是正确的，要么是错误的”。

再用大白话解释一下，就是说，一个没有矛盾的公理体系内，总有一些命题是说不清楚对还是错的（务必注意，这是指在这个体系内说不清楚，不是说永远都说不清楚了）。也许有人说了，既然没矛盾的公理体系有问题，那就搞个有矛盾的公理体系呗。如果设想一个公理体系，一会儿告诉我们“1+1=2”，一会儿又告诉我们“1+12”，相信不会再有人把这个公理体系当回事。有矛盾的公理体系会导致彻底的无意义和虚无，修炼第二重神功的时候会详细阐明这一点。

上述结论听起来是比较可怕的，公理体系必须没有矛盾，可是没有矛盾的公理体系又会导致出现一些命题说不清楚对错。于是开始出现了各种各样的解读，比如“哥德尔定理告诉了我们数学和逻辑的极限，这也几乎是人类理性的极限。它证明理性不是无所不能的”、“哥德尔定理告诉我们，人类不可能真正认识这个世界，永远不可能理解宇宙的真理”等等。相信作为人类理性智慧光辉代表之一的哥德尔，如果听到这些说法，可能也会很无奈吧。

第一，“哥德尔不完备定理”不仅不是所谓人类理性的极限，恰恰相反，它是人类理性智慧的重大成果。它告诉了我们，正是由于有了人类理性的智慧，才有可能认识到这样深刻的结论。哥德尔是通过构造出了一个无法在这个公理体系内证明的命题来证明出“哥德尔不完备定理”的。这个命题的内容说的正是“命题自身无法在此公理体系内被证明”，既然哥德尔已经清楚的证明了这一点，说明这个命题毫无疑问是正确的。所以，“哥德尔不完备定理”的证明过程其实告诉了我们，存在一个可在这个公理体系内表达的正确的命题，但是在这个公理体系内却既不能证明它，也无法证伪它。如果说“哥德尔不完备定理”阐明了什么极限的话，那它阐明的也只是“某类公理体系的极限”，而不是“数学、逻辑的极限”，更不是什么“人类理性的极限”。

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

第三，“哥德尔不完备定理”也没有给出人类认识真理的上限。如果一个命题在某个公理体系内无法判定，那也不是意味着这个命题就是无法判定的了。对于这类命题，如果属于科学范畴的，可以通过科学实验加以判定，从而扩展现有的公理体系，发现新的科学规律；如果属于数学范畴的，可以通过寻找新的数学工具、数学方法或者数学理论来直接拓展现有公理体系，从而准确的判定这个命题，进而扩大人类研究的深度和广度。

还有人了解到，数学研究已经证明了“不存在一个通用的算法，能够判定一个给定的命题在某个确定的公理体系内是否是可判定的”。由此认为既存在着不可判定的命题，又不存在“能够判定某个命题是否不可判定的方法”，显然我们没法准确认识这个世界了。这种观点是不准确的。虽然我们的确证明了不存在通用的判定算法，但是人类认识世界不是只依靠某组公理体系和确定的逻辑与算法的，人类的思维也不可能只局限在某个或者某组公理体系之内。虽然我们无法设计出一个通用算法，来判定一个命题是否在某个公理体系内可判定，但是这并不必然导致我们无法认知这个命题。举个比较简单的例子，“Goodstein定理”（这个定理相对简单易懂，修炼到第五重的时候会详细说明这个例子）就是一个在皮亚诺公理体系里无法判定的命题，但是在集合论中，利用序数知识可以非常简单的证明它。

“哥德尔不完备定理”揭示了公理体系内在而深刻的性质和固有局限性，告诉我们不要奢望仅仅通过若干组公理出发，机械地利用基本逻辑规则进行推导，就能够对全部的命题进行判定。从这个意义上讲，无论是数学还是其它科学，都需要不断的完善、扩充自身的公理体系（或者基本规律），只有这样才能不断认知更加深刻复杂的客观世界。或者说，哥德尔真正严格证明了这句格言——“科学研究是永无止境的”。

转载本文请联系原作者获取授权，同时请注明本文来自赵昊彤科学网博客。
链接地址：http://blog.sciencenet.cn/blog-409681-1067019.html