网站开发有啥作用,企业网站建设立项报告,php做网站访问记录,网页设计实训报告总结与收获来源#xff1a; 赵昊彤科学网博客链接地址#xff1a;http://blog.sciencenet.cn/blog-409681-1067019.html 【编者按#xff1a;不知为何#xff1f;一直不相信已有的数理、物理、生理、心理、管理……能够研究好人机融合智能系统。究其因#xff0c;需要出现新的数/物… 来源 赵昊彤科学网博客链接地址http://blog.sciencenet.cn/blog-409681-1067019.html 【编者按不知为何一直不相信已有的数理、物理、生理、心理、管理……能够研究好人机融合智能系统。究其因需要出现新的数/物/心理逻辑和哥德尔。有些经典是偶然的但有些经典却是必然的。美不一定是漂亮在甲骨文里美就是羊大真不一定是事实善不一定是同情人工智能不一定是聪明智慧则一定不是聪明。】一【中文网上深入介绍哥德尔不完备定理的文章很少我这篇文章写得很长花了不少时间打磨它希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定理分为了五重建议只是想初步了解的读者可以重点看第一重希望了解一些背景的读者可以修炼到第二重希望较深入理解哥德尔证明思路的读者建议修炼到第三重如果确实感兴趣希望详细了解哥德尔证明过程以及其严谨性的读者可以修炼到第四重如果还想多知道一些知识的读者可以练到第五重。——— 作者】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多年前欧几里德撰写的《几何原本》。在现代科学形成的过程中人们发现通过定义一组公理再加上合理的逻辑推演可以证明很多命题或结论。公理体系是当今数学研究和科学研究的基础数学研究成果就是或者说在极大的程度上依赖于一组公理体系的推演而其它科学研究除了依赖公理体系进行推演外还需要通过系统的实验来进行验证。“哥德尔不完备定理”是针对公理体系的一项结论它之所以如此伟大且深刻正是因为它撼动的是一切科学的研究基础——公理体系。修炼第一重神功的时候我们简要理解“哥德尔不完备定理”说的是一个足够复杂的公理体系至少蕴含了皮亚诺算术公理如果它是一致的相容的无矛盾的那么它就是不完备的。这里的完备指的是“对于任何可在这个公理体系内描述的命题都可以在这个公理体系内得到判定要么是正确的要么是错误的”。再用大白话解释一下就是说一个没有矛盾的公理体系内总有一些命题是说不清楚对还是错的务必注意这是指在这个体系内说不清楚不是说永远都说不清楚了。也许有人说了既然没矛盾的公理体系有问题那就搞个有矛盾的公理体系呗。如果设想一个公理体系一会儿告诉我们“112”一会儿又告诉我们“112”相信不会再有人把这个公理体系当回事。有矛盾的公理体系会导致彻底的无意义和虚无修炼第二重神功的时候会详细阐明这一点。上述结论听起来是比较可怕的公理体系必须没有矛盾可是没有矛盾的公理体系又会导致出现一些命题说不清楚对错。于是开始出现了各种各样的解读比如“哥德尔定理告诉了我们数学和逻辑的极限这也几乎是人类理性的极限。它证明理性不是无所不能的”、“哥德尔定理告诉我们人类不可能真正认识这个世界永远不可能理解宇宙的真理”等等。相信作为人类理性智慧光辉代表之一的哥德尔如果听到这些说法可能也会很无奈吧。第一“哥德尔不完备定理”不仅不是所谓人类理性的极限恰恰相反它是人类理性智慧的重大成果。它告诉了我们正是由于有了人类理性的智慧才有可能认识到这样深刻的结论。哥德尔是通过构造出了一个无法在这个公理体系内证明的命题来证明出“哥德尔不完备定理”的。这个命题的内容说的正是“命题自身无法在此公理体系内被证明”既然哥德尔已经清楚的证明了这一点说明这个命题毫无疑问是正确的。所以“哥德尔不完备定理”的证明过程其实告诉了我们存在一个可在这个公理体系内表达的正确的命题但是在这个公理体系内却既不能证明它也无法证伪它。如果说“哥德尔不完备定理”阐明了什么极限的话那它阐明的也只是“某类公理体系的极限”而不是“数学、逻辑的极限”更不是什么“人类理性的极限”。第二“哥德尔不完备定理”不仅不会告诉我们“人类不可能真正认识这个世界”反而是在更深刻的层面上告诉了我们人类应该如何去认识世界、探索真理。譬如在数学上如果发现一个命题通过现有的方法、公理和定理一直得不到证明我们就可以尝试扩展现有的方法和公理体系来进一步研究费马大定理、黎曼猜想等命题被称为“会下金蛋的母鸡”就是这个道理。物理学上广义相对论的发现过程也是因出现了平直空间中狭义相对论某些推论难以解释如高速旋转的圆盘会发生扭曲爱因斯坦提出了等效原理并毅然拓展了平直空间的假设创建了广义相对论这个伟大的理论。值得一提的是哥德尔和爱因斯坦在普林斯顿大学成为了非常好的朋友。晚年的爱因斯坦曾经说过之所以他每天还会经常坚持去办公室上班是因为可以在路上和哥德尔聊聊天而爱因斯坦的去世也曾给哥德尔的情绪以很大打击。第三“哥德尔不完备定理”也没有给出人类认识真理的上限。如果一个命题在某个公理体系内无法判定那也不是意味着这个命题就是无法判定的了。对于这类命题如果属于科学范畴的可以通过科学实验加以判定从而扩展现有的公理体系发现新的科学规律如果属于数学范畴的可以通过寻找新的数学工具、数学方法或者数学理论来直接拓展现有公理体系从而准确的判定这个命题进而扩大人类研究的深度和广度。还有人了解到数学研究已经证明了“不存在一个通用的算法能够判定一个给定的命题在某个确定的公理体系内是否是可判定的”。由此认为既存在着不可判定的命题又不存在“能够判定某个命题是否不可判定的方法”显然我们没法准确认识这个世界了。这种观点是不准确的。虽然我们的确证明了不存在通用的判定算法但是人类认识世界不是只依靠某组公理体系和确定的逻辑与算法的人类的思维也不可能只局限在某个或者某组公理体系之内。虽然我们无法设计出一个通用算法来判定一个命题是否在某个公理体系内可判定但是这并不必然导致我们无法认知这个命题。举个比较简单的例子“Goodstein定理”这个定理相对简单易懂修炼到第五重的时候会详细说明这个例子就是一个在皮亚诺公理体系里无法判定的命题但是在集合论中利用序数知识可以非常简单的证明它。“哥德尔不完备定理”揭示了公理体系内在而深刻的性质和固有局限性告诉我们不要奢望仅仅通过若干组公理出发机械地利用基本逻辑规则进行推导就能够对全部的命题进行判定。从这个意义上讲无论是数学还是其它科学都需要不断的完善、扩充自身的公理体系或者基本规律只有这样才能不断认知更加深刻复杂的客观世界。或者说哥德尔真正严格证明了这句格言——“科学研究是永无止境的”。二第二重“静水流深”——“哥德尔不完备定理”的深刻背景哥德尔为什么会想到证明这样一个“不完备定理”呢既然已经修炼到第二重了就稍微说的多一点。一数学公理化人们经常说数学研究领先其他学科研究至少200年。其实在上上个世纪也就是19世纪的时候数学研究就已经大幅度超前于其他学科的研究了。数学家以及很多科学家们越来越意识到数学应该是一个公理化的系统它的结构应该是这样的——首先定义一批公理和基本逻辑规则然后依据这些公理和逻辑规则可以推演出这个体系内的无穷多的定理——这就应该是理想的数学。倡导并推进数学公理化的最主要代表人物就是德国数学家大卫·希尔伯特David Hilbert19世纪和20世纪最具影响力的大数学家之一。希尔伯特的影响力主要体现在他于1900年在巴黎举行的第二届国际数学家大会上作的题为《数学问题》的演讲。在这个演讲中希尔伯特提出了23个他认为最重要的数学问题而这23个问题至今还在指引着数学家的研究方向。这23个问题中的第2个问题就是有关数学公理化的。希尔伯特说“在这些无数个问题之上我倾向于确定下面这个问题才是最重要的这些公理在经过有限步骤的推演后是不会导致相互矛盾的结论的。……也就是说我们需要一个关于算术公理一致性相容性的证明。”。19101913年怀特海Alfred North Whitehead和罗素Bertrand Russell撰写的《数学原理》《Principia Mathematica》的发表是数学公理化推进的又一里程碑事件。《数学原理》希望从最基础的逻辑出发来定义全部数学试图构建一个宏大的逻辑体系结构彻底的解决数学公理化的问题。我们只要稍微想象一下就能够猜到这个过程有多复杂特别是罗素还要在这个过程中消除自己发现的“罗素悖论”后面会提到。直到《数学原理》第一卷的363页才推导出了数字“1”的定义第二卷又费了很大的力气证明了乘法交换律。《数学原理》工程浩大两位作者只完成了前三卷覆盖了集合、基数、序数和实数的相关内容虽然对第四卷几何的基础做了筹划但整个体系结构实在太过复杂两位作者“才智枯竭”[2]实在无法再写下去了。数学公理化推进的最关键标志性事件是19201923年间希尔伯特推动的“希尔伯特计划”。这个计划的主要目标是为全部的数学提供一个安全的理论基础。这个计划对数学公理化提出了如下要求形式化形式化是希尔伯特提出来的一个关键思想意思是所有数学应该使用用统一的、严格的、无意义的、形式化的语言来表述并且按照一套严格的、基础的逻辑规则来推演。完备性形式化之后数学里所有的真命题都可以通过上述规则被证明。一致性运用这一套形式化的表达和规则不可能推导出矛盾。保守性这是针对形式化而言的即如果赋予一些形式化的表达以含义希尔伯特将这称为元数学并由此证明了某些结论那么必须保证即使不赋予这些含义依然可以证明同样的结论。确定性可以通过一个算法来确定每一个形式化的命题是真还是假。对于修炼完成了“哥德尔不完备定理”第一重神功的读者来说应该会看出上述“希尔伯特计划”是有问题的。没错之所以我们比大数学家希尔伯特还要目光如炬是因为我们站在哥德尔这个巨人的肩膀上要知道在哥德尔的论文发表之前甚至是发表之后的一段时间主流数学家、逻辑学家们仍然认为希尔伯特计划毫无疑问是正确的问题只不过是如何给出证明罢了。二一致性相容性的重要意义在详细阐述“哥德尔不完备定理”对数学公理化特别是“希尔伯特计划”的影响之前我们先来谈一下“一致性”的重要意义。这里说的“一致性”就是指很多文章或书籍里面说的“相容性”希尔伯特说的compatibility哥德尔说的consistency意思是“无矛盾的”。在修炼第一重神功的时候我们谈到构造一个不一致不相容、存在矛盾的公理体系是无意义的。从直觉出发我们都清楚存在矛盾的体系当然有问题了。这里我们给出逻辑上的说明或者说证明。做这件事之前让我们先来感谢罗素和怀特海是他们的艰苦工作成果《数学原理》给出了数学形式化的基础。我们正是以此为基础来说明一致性的重要意义。另外了解《数学原理》中给出的数学形式化的基本表示也是继续修炼第三重、第四重神功的基础因为哥德尔就是基于《数学原理》中数学形式化的表达来证明“哥德尔不完备定理”的。由于形式化表达的符号存在不同的样式为避免歧义本文中数学形式化的表达与哥德尔论文中的样子保持一致。以下是数学形式化的基本原则1使用字母一般使用p、q、r等表示命题变量即一个字母表示一个命题使用如下符号表示特定逻辑注意形式化之后的表达式是无含义的因此这些符号仅表示某种逻辑关系 逻辑“非”∨ 逻辑“或”⇒ 逻辑“推出”意思是“如果……那么……”∧ 逻辑“与”∀x∙p 对于任意xp都成立∃x∙p 存在x使p成立2组成合理的命题表达式。譬如“p∨q”就是一个合理的命题表达式而“p∨”就是一个错误的表达式。3两条变换规则一是代入规则可以使用其它的命题表达式对某个命题表达式中的某个命题变量进行全部统一替换二是分离规则其实就是我们常说的逻辑三段论已知p和p⇒q成立则q成立。4《数学原理》提出的四条基本逻辑推演公理(p∨p)⇒pp⇒(p∨q)(p∨q)⇒(q∨p)(p⇒q)⇒((r∨p)⇒(r∨q))大家可能觉得这四条基本逻辑推演公理看起来像是废话由此可知《数学原理》这本巨著是从多么基础的逻辑出发的。不要小看这四条基本推演公理它们可以推导出难以想象的复杂的结论。好以上四条数学形式化的基本原则叙述完毕下面开始推出一个逻辑定理p⇒(~p⇒q)。推演过程如下根据第二条推演公理得到p⇒(p∨q)根据变换规则二设p成立则得到如下结论p∨q成立在p成立的前提下设p成立即p不成立则由∨逻辑的基本含义得到q成立意思就是“p或q”成立且p不成立那么必然q要成立根据上述结果在p成立的条件下如果p也成立那么q成立。于是得到上面的逻辑定理p⇒(~p⇒q)。注意这里面q是一个自由的命题变量根据基本变换规则一可以把任何命题代入q。因此我们得到了一个重要结论如果有一个命题“p”和它的逻辑非“p”都成立那么任意命题q都成立。也就是说有矛盾的公理体系可以推导出任意命题都成立。这就是为什么公理体系必须一致不一致的公理体系为什么无意义的原因了。三数学形式化的目的在谈完了“一致性”的意义后我们还要再谈一下为什么希尔伯特要搞数学形式化希尔伯特是提出数学形式化的代表人物他提出数学形式化的目的还是从证明“希尔伯特第2问题”出发来考虑的。人们之所以笃信公理体系必然是一致的、无矛盾的其实是因为人们日常研究并应用的公理体系都是有含义的都是对应着客观实体的。人们相信客观实体及其规则是不会发生矛盾的。这正像我们中国成语“自相矛盾”故事所说的一个无坚不摧的矛和一个无比坚固的盾在现实世界是不会同时存在的只要用这个矛刺一下这个盾就会有一方露馅。可是我们的公理体系不总是对应着存在的客观实体很多情况下特别是数学中的公理体系对应着抽象实体或者理想实体如集合、点、线、面而且被对应的实体是无穷多的我们无法通过有限枚举来证明这些公理体系的一致性。由此希尔伯特想到彻底抛弃数学公理体系中的含义构造一个形式化的公理体系这个体系内的各种表达式仅仅具有符号意义。如果能由此证明这样的公理体系的一致性那么无论把任何含义赋予这个公理体系时必然是无矛盾的、一致的了。正是由于希尔伯特这个想法以及罗素和怀特海的“身体力行”才使得哥德尔最终发现了不完备定理。否则人们在研究公理体系的时候总会把它对应的含义和其逻辑关系一起考虑就不太容易把思路聚焦到公理体系的逻辑本身上面也就不容易发现“哥德尔不完备定理”了。四“哥德尔不完备定理”打破了“希尔伯特计划”么最后让我们再回到“哥德尔不完备定理”看看哥德尔是如何在数学公理化以及公理体系形式化的大背景下“釜底抽薪”的。我们先来看“希尔伯特计划”的几个要素一是形式化。显然“哥德尔不完备定理”并没有反对形式化而且正是通过《数学原理》中公理体系形式化的成果哥德尔才证明了不完备定理。二是完备性和一致性。“哥德尔不完备定理”明确指出了公理体系完备性和一致性的矛盾之处它证明了一致的公理体系指蕴含皮亚诺公理的公理体系以下类似不再赘述必然是不完备的也就是说完备性和一致性不可能同时获得。另外“哥德尔不完备定理”还有一个推论一般被叫做“哥德尔第二不完备定理”它表明公理体系的一致性不能在这个公理体系内被推导出来。也就是说不仅完备性和一致性有矛盾即使是一致性本身也不能在公理体系内得到证明这个结论似乎显得更可怕。三是保守性。事实上保守性也不再成立了。在“哥德尔不完备定理”的详细证明过程第四重和“Goodstein定理”介绍第五重中我们就可以发现当赋予了某些含义给公理体系之后原来不可证明的命题变得可证明了。个人认为赋予含义的过程本身就是在扩充这个公理体系个人观点可讨论。这也是为什么哥德尔构造的forall(v,r)这个命题在《数学原理》确定的逻辑基础和皮亚诺公理体系内不可通过形式化的推演而证明但是却在哥德尔的论文中被证明了的原因。哥德尔论文中也提到了provable(x)是他构造的46个表达式中唯一个不能断言为原始递归性质的这说明命题的“可证性”某种意义上是被哥德尔新赋予的含义。四是确定性。显然确定性也不成立因为哥德尔证明了存在某些命题无法证明其真假。而且就算在确定性判断的“真”和“假”以外加入“不可证明”这一类也是不成立的。我们前面提到过没有一个通用的算法能够判定任意命题是否不可证。从上面这些要素来看除了公理形式化没有问题外其他要素都存在问题要么互相矛盾要么根本不成立。从这个意义上讲“希尔伯特计划”确实被打破了这也是当年“哥德尔不完备定理”最重大且最直接的影响。“哥德尔不完备定理”发表时希尔伯特还在世面对这个伟大成果大数学家希尔伯特也只能退让不过只是略微退让。毕竟哥德尔只是在某一个范畴内皮亚诺公理体系原始递归性质构造出了一个在公理体系内不可证明的命题剔除这个范畴之后结果又会是怎么样的呢第五重无论怎样我们必须指出希尔伯特“为全部的数学提供一个安全的理论基础”这个目标并没有被打破通过不断扩展公理体系我们仍然可以为数学提供一个越来越安全的基础只不过这个公理体系结构看起来要从原来的“有限”变为“无限”了[3]。三 第三重“惊鸿一瞥”——“哥德尔不完备定理”的概要证明思路首先恭喜开始修炼第三重神功的读者相信你们已经对“哥德尔不完备定理”有了足够的理解了现在我们开始进入到“哥德尔不完备定理”的证明思路中。哥德尔在25岁就发表了这篇伟大的论文但是哥德尔这个人却是一个很谨慎细致的人他知道自己这篇论文可能带来的影响因此他非常担心别人没有读懂它或者引发什么误会。为此在这篇论文的第一部分Introduction中哥德尔概括但细致地给出了整个证明的思路。不过在我们理解哥德尔的证明思路之前让我们先从更简单、更易懂的方式入手来逐步进入状态。一悖论式语言喜欢搞点逻辑类脑筋急转弯的读者可能了解一些悖论式的语言譬如“这句话是谎话”。这句话到底对不对呢如果说它对那么它就真的是谎话了既然是谎话那么显然是不对的如果说它不对就意味着它不是真话而是谎话显然它又对了。对可以推演出不对不对却可以推演出对这种语言可以称之为“悖论式语言”。由此我们可以给出一个结论能用语言表达的语句中一定存在既不能说明它对也不能说明它错的句子。于是我们可以说语言体系的逻辑表达是不完备的。如果有人以为这就证明了“哥德尔不完备定理”那未免太天真了。这种逻辑悖论在几千年前就被人们发现了如果像希尔伯特、罗素等大数学家、逻辑学家连这个问题都搞不定还有什么资格去推进数学公理化和公理体系形式化呢其实这种悖论式语言在《数学原理》所定义的形式化公理体系中是无法表达的。设这句话看作一个命题为X那么“这句话是谎话”就应该表达为“~X”。而悖论式语言需要把“~X”定义成X自己也就是让“X(~X)”这是无论如何也不可能通过《数学原理》中的四条基本逻辑推演公理推演得到的结论。所以这种悖论式语言只能证明“人类的语言体系逻辑表达不完备”而并不能证明“公理体系不完备”。但是这个思路和哥德尔的证明是有着相通之处的。二罗素悖论如果小时候对数学与逻辑感兴趣也许会记得那个“只给不给自己理发的人理发”的理发师这个悖论其实就是罗素悖论只不过为了让人容易理解把抽象的罗素悖论给改头换面了一下。罗素悖论是集合论中的一个经典悖论我们把若干具有同一性质的对象划分为一个类类中的这些对象被称为类的元素当然某些情况下类里面的元素也可能是一个类。现在我们设计某一种性质P(x) x∉x 也就是说具有性质P的对象不是自身的元素。那么满足性质P的类为A{x|x∉x}。此时如果我们想判定A这个类是否是A自身的元素时悖论就出现了如果A∈A根据性质P得到A∉A如果A∉A那么A就满足性质P则A∈A。罗素悖论是不能仅仅归因于语言表达的不严谨的事实上这是一个实实在在的悖论是关于类的公理体系必须要解决的问题。后来人们修改了类的内涵公理并提出了一个新的概念——集合。集合是能够成为某一个类的元素的那种类。由此我们把类分成了两种一种是集合另外一种是真类不能成为任何类的元素的类。由于罗素悖论与“哥德尔不完备定理”的证明没有直接关系因此本文不再讨论它了有兴趣的读者可以自行深入了解。之所以在这里谈到了罗素悖论是因为希望读者知道当公理体系引发了悖论之后人们马上就会通过定义新的概念、提出或者修改公理来完善它。可是当哥德尔的证明也构造出了类似悖论的命题之后人们宁可接受这个命题是不可证明的也没有试图通过修补公理体系来解决这个问题。因为通过哥德尔的方法构造的这类命题使得人们无论定义多少个概念、补充或修补多少个公理也无法消除它。三哥德尔证明思路哥德尔的证明思路和前面那些制造悖论的思路类似都是要把命题自身引入到命题之中。区别在于哥德尔既不是利用了某种语言的不严谨也不是简单地把命题变量直接代入到自身而是严格按照公理体系形式化的要求一丝不苟地把命题自身引入到这个命题之中其论证过程天衣无缝、无懈可击需要说明的是哥德尔的证明所使用的公理体系是基于《数学原理》中提出的形式化的公理体系哥德尔在论文中把这个公理体系称为PMPrincipia Mathematica我们在后面也会沿用这个名字。1建立命题表达式与自然数的对应哥德尔对应哥德尔做的第一件事是把PM中的表达式和自然数对应起来。我们在讲解“一致性的重要意义”的时候专门介绍了PM中的表达式和相应规则。PM中的表达式就类似下面的这些例子~ (∃z≤x ∙ (z≠1∧z≠x∧z|x))∧(x1) 判断x是否为质数的PM公式∀q∙p⇒(~p⇒q) 我们证明过的公式矛盾的体系可推出任何命题哥德尔说这些表达式都是由一些基本符号组成的是一组符号序列而“证明过程”无非就是一组表达式组成的序列是符号组成的序列的序列。按照希尔伯特的数学形式化思路这些符号、表达式和“证明过程”都是无意义的如果需要可以赋予某种含义来表达一些现象。哥德尔指出显然把这些符号赋予什么含义是与PM体系本身无关的因此在这里哥德尔把这些符号对应为自然数。于是每一个基本符号都对应于一个自然数每一个表达式则对应于一个自然数序列每一个“证明过程”都对应于一个自然数序列的序列。反过来每当给出一个合规的自然数序列就可以唯一的对应一个PM表达式每给出一个合规的自然数序列的序列就可以唯一的对应一个PM证明过程。再深入一步有了这种对应后就可以把一些对PM表达式或者证明过程的有含义性的判断对应成对于某一个自然数序列的判断而这类对自然数序列的判断显然又可以使用PM中的表达式来进行。换句话说通过哥德尔建立的对应我们终于可以使用PM表达式来表达有含义的判断了。比如根据事先对应关系的定义一个合法的表达式对应的自然数序列一定满足某种规则这种规则显然可以在PM中表达于是我们就可以在PM中给出一个表达式用来表达“某个表达式是否合规”这个含义。由于这种对应也被称为哥德尔对应对于“哥德尔不完备定理”的证明非常关键我们宁可不厌其烦地再举个很简单例子来使读者能够准确理解它。我们建立一种类似哥德尔说的对应关系事先声明我们建立的这个对应关系仅仅是为了容易理解下面的例子实际上这个对应关系并不利于证明“哥德尔不完备定理”。我们建立的对应关系为把PM体系中的全部合规表达式以及证明过程按照ASCII字符顺序排列形成一个无限长的序列然后从第一个表达式开始我们把它对应到自然数1第二个对应3以此类推直至无穷然后再把全部不合规的表达式排列好顺序从第一个开始分别对应到自然数2、4、6、……。这样PM中的任意表达式及证明过程都对应着唯一的自然数。我们再定义一个PM表达式这个表达式用来判断某个表达式是否合规设这个表达式为isFm(x)。显然这种对应关系下的isFm(x)在PM中应为“~(∃z ∙ x2z)”注意PM中的任意数字变量都是0或自然数这个表达式实际是判断x是否为奇数如果是则对应x的表达式合规否则不合规。于是一个“表达式是否合规的有含义的判断”被表示为PM中的一个表达式了。当然除了表示“表达式是否合规”外也应该还可以表示“某个表达式是否在PM体系内可以证明”哥德尔把这种表达式设为provable(x)他表示自然数或自然数序列或自然数序列的序列修炼第四重时会看到哥德尔采用一种巧妙的方法把这些序列们都对应为唯一的自然数了x对应的表达式是否可在PM体系内证明。最后再强调一点哥德尔把PM中的表达式对应为自然数并不是哥德尔为了研究自然数或者数论而做的什么工作而是哥德尔为了构造某种特殊的PM表达式而提出的方法。通过把PM表达式映射为自然数再利用PM体系自身本来具备的表达自然数间关系的能力来实现把PM中的命题引入自身的目标。2构造一个特殊的命题表达式哥德尔定义“在PM命题表达式中只有一个自然数类型的自由变量的那种表达式称为class-sign考虑到这只是哥德尔起的一个名字就不翻译了”比如“x10”、“∃z∙zx”、“∀yx,zx∙ ~(xy∙z)”等等这些都是class-signs都只有一个自由变量x且x是一个自然数。下面我们给每个class-sign分配一个序号并设第n个class-sign为Rn。当我们把某个自然数k代入到某个class-sign的变量时得到的表达式记为Rn(k)。例如若R9是“∃z∙zx”那么R9(8)就是“∃z∙z8”R9(9)就是“∃z∙z9”。再设provable(R)表示R这个命题表达式可以在PM中被证明前面已经提到了。大家知道有些表达式是可以在PM体系中证明的比如“39”、“~(x10∧x8)”有些表达式是不可证明的比如“39”、“(x10∧x8)”。因此provable(39)为真provable(x10∧x8)为假。然后我们定义一个集合KK{n|provable(Rn(n))}。也就是说K是这样一组自然数的集合集合中的元素n使得Rn(n)不可证注意这里面的Rn(n)是把命题表达式R的序号带入到它的自由变量中得到的表达式。基于上述定义必然存在一个命题表达式S(n)它表示n∈K而且显然这个表达式是一个class-sign。既然S也是一个class-sign那么S也必然有一个对应的序号设这个序号为q则S就是Rq。如果我们把Rq的序号q带入到Rq中就得到了表达式Rq(q)这应该是一个可以在PM中表达的表达式。最后我们来考察表达式Rq(q)和~Rq(q)是否可以证明。根据上面的定义我们可以得到下面的结论Rq(q) ⇔ S(q) ⇔ q∈K ⇔ ~provable(Rq(q)) ………………… 式1如果Rq(q)可以证明意味着provable(Rq(q))为真显然意味着Rq(q)也为真根据式1可得到~provable(Rq(q))也为真发生了“~provable(Rq(q))”和“provable(Rq(q))”同时为真的情况也就是PM不一致了。换句话说如果PM是一个一致的体系那么只有Rq(q)不可证。如果~Rq(q)可以证明意味着~Rq(q)为真根据式1得到~(~provable(Rq(q)))为真也就是provable(Rq(q))为真即Rq(q)可以证明也即Rq(q)为真。这次又发生了Rq(q)与~Rq(q)同时为真的情况。于是如果PM一致那么~Rq(q)也不可证。综上对于Rq(q)这个命题只要PM是一个一致的公理体系那么在PM中既不能证明它也不能否证它。换句话说在PM体系之内可表达的命题Rq(q)说不清楚对错。3进一步的分析哥德尔在论文中明确提到这种构造思路是来源于两个有名的悖论——理查德悖论Richard-antinomy和说谎者悖论liar-antinomy后者就是我们最前面说到的“这句话是谎话”的悖论而前者则与哥德尔的构造有类似之处感兴趣的读者可以自行了解。哥德尔证明的一个关键点就是把“真”、“假”与“可证明”及“不可证明”区分开来了。这里谈到的可证明与否都是指在PM体系之内。我们日常生活与工作中经常把“真假”与“是否可证明”等同起来认为“真⇔可证明”“假⇔不可证明”。其实“真假”与“是否可证明”的严格关系应该是“可证明⇒真”、“假⇒不可证明”但是它们的逆命题却不成立也就是说“真命题未必可证明”同时“不可证明的也未必就是假命题”。前面我们给出了~Rq(q)和Rq(q)都是不可证明的论断但这并不意味着Rq(q)的真假不确定。其实我们看一下式1就可以得到Rq(q) ⇔ ~provable(Rq(q))也就是说命题Rq(q)说的其实是“Rq(q)不可证”或者说Rq(q)说的是“自己不可证”。那么根据我们前面的论断Rq(q)确实是不可证的也就是说Rq(q)这个命题为真。大家没有必要为此而感到惊讶前面我们说了哥德尔清晰的区分了“可证与否”与“真假”的关系真命题不一定可证。4再进一步分析——哥德尔第二不完备定理哥德尔在论文的Introduction部分中介绍了自己的证明思路之后特别指出在详细的对Rq(q)为真这个结论进行分析时会得出一个奇怪的结论——关于公理体系一致性证明的奇怪结论哥德尔说将在论文的定理XI中进行讨论。哥德尔论文中的定理XI就是我们今天常说的“哥德尔第二不完备定理”。由前面的论证过程可知当PM体系一致的时候可以得到结论“Rq(q)不可证”也就是“Rq(q)为真”。这里面并没有附加任何别的条件。因此根据前面的论证我们得到“PM体系一致”⇒Rq(q)可我们知道Rq(q)是不可证的。也就是说“PM体系一致”也应该是不可证的否则如果“PM体系一致”可证那么就可以推出Rq(q)这与Rq(q)不可证矛盾。严格的讲这样的说法是不准确的他没有证明“PM体系一致”⇒Rq(q)是可在PM体系中推导出来的。修炼第四重时会给出哥德尔更严格的证明过程。通过上面的简单分析我们得到了“哥德尔第二不完备定理”简单表述为“一个蕴含了皮亚诺公理的公理体系其一致性是不能在这个公理体系内得到证明的”。以上就是哥德尔不完备定理的证明思路对于绝大部分数学爱好者修炼到这里应该满意了。因为修炼到第三重之后已经比较深入的理解了“哥德尔不完备定理”的证明思路足够准确、全面的理解了“哥德尔不完备定理”的意义。对于愿意学习的读者可能仍然会有各种疑问有人会问哥德尔把PM表达式对应到自然数到底有什么用是怎么通过这种方式表达出provable(x)之类的有含义的命题的也有人会问修炼第一重的时候说到的“ω一致”和“原始递归”到底是什么意思可能还有读者会问第三重介绍的证明思路难道不是一个严格的证明过程么为什么还要修炼第四重对于需要解开这些疑问的读者请你们和我一起开始修炼第四重神功吧。四http://blog.sciencenet.cn/blog-409681-1067025.html五第五重“洞见古今”——拓展了解“哥德尔不完备定理”的相关知识正像金庸小说《倚天屠龙记》中的乾坤大挪移神功一样连创作者都没有修炼到最高层。本人也一样完全不敢说自己修炼成了第五重神功。因此这部分内容略简单只谈两个方面。一“哥德尔不完备定理”的实例1931年哥德尔提出了不完备定理以来人们逐步相信了复杂公理体系的不完备性。80多年来人们也逐渐发现了越来越多的哥德尔不完备定理的实例最著名的就是“选择公理和连续统假设是在集合论中不能确定的命题”1963年美国数学家保罗∙科恩最终证明了这一点解决了希尔伯特23个问题中的第1个问题这其中也有着哥德尔的贡献。那么有没有直接符合哥德尔论文条件下的实例呢也就是在皮亚诺公理体系中不可确定的命题1982年人们发现了第一个不属于哥德尔构造的、在皮亚诺公理体系内无法证明也无法证伪的算术命题实例——Goodstein定理。Goodstein定理说的是Goodstein数列一定会在有限步收敛到0。Goodstein数列是这样的首先选取一个正整数g1比如设g118然后把它写成2的次幂之和的形式18 24 21再把大于2的指数也写成2的次幂的形式如果改写后得到的表达式中还有大于2的指数则再继续把这样的数字写成2的次幂的形式直到所有出现的数字都小于等于2最后得到g122^221这种写法叫Hereditary Base 2 Notation。g2是把g1的这种写法中所有的2都换成3得到的新数字再减1也就是g233^331-1注意到这是个非常大的数约等于7.6×1012。再继续下去把g2写成3的次幂的形式一直到不出现大于3的数字然后把3换成4得到的数再减1就得到了g3。以此类推不断计算下去就得到了一个数列这个数列就是Goodstein数列。下面我们以g118为例看看数列的前几项g122^22118g233^331-133^32×307.6×1012g344^42×40-144^4401.3×10154g455^550-155^51.9×102184只看这几项我们一定会认为这个数列以极快的速度发散到无穷。事实上这个数列会在有限步骤收敛到0。Goodstein定理是一个容易看懂的算术命题其证明可以通过集合论、良序定理以及超限序数等理论和知识来完成。大概思路就是使用超限序数ω构造一个与Goodstein数列平行的数列这个新数列的每一项都不小于Goodstein数列的对应项且这个新数列是递减的必然在有限步后会收敛到0。Goodstein定理在集合论中的证明过程不长简单易懂。但是当我们在皮亚诺公理体系内研究这个命题的时候神奇的事情发生了。1982年Laurie Kirby和Jeff Paris发现这个定理在皮亚诺公理体系下是不可证的。这个定理正好是哥德尔不完备定理的一个典型例证。我们前面说过哥德尔不完备定理是通过构造出一个不可证的算术命题来证明的。可是作为已经修炼到第五重神功的我们清楚的知道哥德尔构造的这个算术命题我们几乎不可能直接的表达出来因为太复杂、做不到。所以哥德尔只是通过构造方法证明了不可证命题的存在性。直到Goodstein定理的发现我们终于可以见到一个皮亚诺公理体系内不确定的算术命题的样子了。Goodstein定理简明易懂计算过程明确但是在皮亚诺公理体系居然无法证明想想都觉得神奇。由此我们应该更加钦佩哥德尔的伟大贡献了吧二是存在既一致且完备的公理体系的我们讨论了这么多关于哥德尔不完备定理的内容了估计大家已经毫无疑问地坚信这个定理了。在此还是要再一次提醒大家哥德尔不完备定理是有前提条件的那就是“蕴含皮亚诺公理体系”。也就是说并不是任何一致的公理体系都不完备。那么真的存在既一致又完备的公理体系么答案是肯定的。我在这里可以给大家即兴构建一个公理体系这个公理体系只有两个数字0和1只有一种二元运算“”其三条公理如下10002011013110公理体系构建完毕。这个公理体系极为简单在这个体系内可表达的全部命题都可以证明比如11101而且这个公理体系肯定是一致的也是“ω一致”的。其实一个公理体系如果比较简单不能承载哥德尔对应中起码的编码要求那么这个公理体系的一致性与完备性是否存在矛盾就不属于哥德尔定理覆盖的范畴了。对于一些简单的公理体系是可以证明其既一致又完备的。当然我构造的公理体系太简单了以至于一点用处也没有。在实际的数学中有一种叫做Presburger arithmeticPresburger算术的体系因不包括乘法所以其实是既一致又完备的感兴趣的话可以Google之以详细了解。另外对于一些也很复杂的公理体系如果其不足以定义自然数哪怕这样的公理体系包含了自然数也可能不受“哥德尔不完备定理”的约束。比如塔斯基Tarski证明了实数和复数理论都是一致且完备的一阶公理体系虽然它们都包括了自然数再比如著名的欧几里德几何在补充了平行公理和实数理论之后也是一个一致且完备的一阶公理化系统。“哥德尔不完备定理”确实伟大但是也用不着神化它有它的前提条件有它的适用范围当然也同样有着划时代的伟大贡献结语到此五重神功全部修炼完毕。“哥德尔不完备定理”是一个划时代的伟大成就也是哥德尔一生唯一的一个重大研究成果。作为一个数学家、逻辑学家的哥德尔一生能做出这样一个伟大的成就值了。作为读者如果通过这个修炼过程能够真正深入了解并理解了“哥德尔不完备定理”我想也值回大家花费在阅读和思考上的时间了吧。[1] 网上能查到的哥德尔论文的英译版网址http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf[2] 本人实在不忍心这样描述罗素和怀特海“才智枯竭”这个说法参见维基百科https://zh.m.wikipedia.org/zh-hans/数学原理[3] 参见张寅生先生在科学网的博客http://blog.sciencenet.cn/blog-320682-969874.html未来智能实验室是人工智能学家与科学院相关机构联合成立的人工智能互联网和脑科学交叉研究机构。未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
