“哥德尔不完备定理”到底说了些什么?——(一) 【中文网上深入介绍哥德尔不完备定理的文章很少,我这篇文章写得很长,花了不少时间打磨它,希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定理分为了五重,建议只是想初步了解的读者,可以重点看第一重;希望了解一些背景的读者,可以修炼到第二重;希望较深入理解哥德尔证明思路的读者,建议修炼到第三重;如果确实感兴趣,希望详细了解哥德尔证明过程以及其严谨性的读者,可以修炼到第四重;如果还想多知道一些知识的读者,可以练到第五重。 ——— 作者】 1931 年,库尔特∙弗雷德里希∙哥德尔(KurtFriedrich Gdel)发表了一篇影响深远的论文“On formally undecidablepropositions of Principia Mathematica and related systems I” (论文的原文是用德文发表的,这里给出的是英译名)。今天,我们一般笼统的把论文中提出的定理称为“哥德尔不完备定理”。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+1 2” ,相信不会再有人把这个公理体系当回事。有矛盾的公理体系会导致彻底的无意义和虚无,修炼第二重神功的时候会详细阐明这一点。 上述结论听起来是比较可怕的,公理体系必须没有矛盾,可是没有矛盾的公理体系又会导致出现一些命题说不清楚对错。于是开始出现了各种各样的解读,比如“ 哥德尔定理告诉了我们数学和逻辑的极限,这也几乎是人类理性的极限。它证明理性不是无所不能的 ”、“ 哥德尔定理告诉我们,人类不可能真正认识这个世界,永远不可能理解宇宙的真理 ”等等。相信作为人类理性智慧光辉代表之一的哥德尔,如果听到这些说法,可能也会很无奈吧。 第一,“哥德尔不完备定理”不仅不是所谓人类理性的极限,恰恰相反,它是人类理性智慧的重大成果。它告诉了我们,正是由于有了人类理性的智慧,才有可能认识到这样深刻的结论。哥德尔是通过构造出了一个无法在这个公理体系内证明的命题来证明出“哥德尔不完备定理”的。这个命题的内容说的正是“命题自身无法在此公理体系内被证明”,既然哥德尔已经清楚的证明了这一点,说明这个命题毫无疑问是正确的。所以,“哥德尔不完备定理”的证明过程其实告诉了我们,存在一个可在这个公理体系内表达的 正确 的命题,但是在这个公理体系内却既不能证明它,也无法证伪它。如果说“哥德尔不完备定理”阐明了什么极限的话,那它阐明的也只是“某类公理体系的极限”,而不是“数学、逻辑的极限”,更不是什么“人类理性的极限”。 第二,“哥德尔不完备定理”不仅不会告诉我们“人类不可能真正认识这个世界”,反而是在更深刻的层面上告诉了我们人类应该如何去认识世界、探索真理。譬如在数学上,如果发现一个命题通过现有的方法、公理和定理一直得不到证明,我们就可以尝试扩展现有的方法和公理体系来进一步研究;费马大定理、黎曼猜想等命题被称为“会下金蛋的母鸡”就是这个道理。物理学上,广义相对论的发现过程,也是因出现了平直空间中狭义相对论某些推论难以解释(如高速旋转的圆盘会发生扭曲),爱因斯坦提出了等效原理并毅然拓展了平直空间的假设,创建了广义相对论这个伟大的理论。值得一提的是,哥德尔和爱因斯坦在普林斯顿大学成为了非常好的朋友。晚年的爱因斯坦曾经说过,之所以他每天还会经常坚持去办公室上班,是因为可以在路上和哥德尔聊聊天;而爱因斯坦的去世也曾给哥德尔的情绪以很大打击。 第三,“哥德尔不完备定理”也没有给出人类认识真理的上限。如果一个命题在某个公理体系内无法判定,那也不是意味着这个命题就是无法判定的了。对于这类命题,如果属于科学范畴的,可以通过科学实验加以判定,从而扩展现有的公理体系,发现新的科学规律;如果属于数学范畴的,可以通过寻找新的数学工具、数学方法或者数学理论来直接拓展现有公理体系,从而准确的判定这个命题,进而扩大人类研究的深度和广度。 还有人了解到,数学研究已经证明了“不存在一个通用的算法,能够判定一个给定的命题在某个确定的公理体系内是否是可判定的”。由此认为既存在着不可判定的命题,又不存在“能够判定某个命题是否不可判定的方法”,显然我们没法准确认识这个世界了。这种观点是不准确的。虽然我们的确证明了不存在通用的判定算法,但是人类认识世界不是只依靠某组公理体系和确定的逻辑与算法的,人类的思维也不可能只局限在某个或者某组公理体系之内。虽然我们无法设计出一个通用算法,来判定一个命题是否在某个公理体系内可判定,但是这并不必然导致我们无法认知这个命题。举个比较简单的例子,“Goodstein定理”(这个定理相对简单易懂,修炼到第五重的时候会详细说明这个例子)就是一个在皮亚诺公理体系里无法判定的命题,但是在集合论中,利用序数知识可以非常简单的证明它。 “哥德尔不完备定理”揭示了公理体系内在而深刻的性质和固有局限性,告诉我们不要奢望仅仅通过若干组公理出发,机械地利用基本逻辑规则进行推导,就能够对全部的命题进行判定。从这个意义上讲,无论是数学还是其它科学,都需要不断的完善、扩充自身的公理体系(或者基本规律),只有这样才能不断认知更加深刻复杂的客观世界。或者说, 哥德尔真正严格证明了这句格言——“科学研究是永无止境的” 。
自指 本语句由汉字组成。本语句由字母组成。这两句话都涉及自指,前面一句话真,后面一句话假。 本语句是假的。这句话真还是假呢?从它真可以推出它是假的,从它是假可推出它是真。所以不管它是真是假,都导出矛盾。 上面的讨论看起来只是语言游戏,与数学无关。因为这些语句都涉及自指,而数学似乎不存在这样的问题。 80 多年前,逻辑学家哥德尔发明了一种技术,使得数学也能出现自指。 哥德尔是通过对数学表达式取名实现自指的。通过一个简单的例子来阐述他的思想。 L : L 是假的 冒号左边的 L 表示“ L 是假的”这句话的名字是 L 。所以这句话也出现了自指,和“本语句是假的”是同一个意思。 编码 这里介绍哥德尔给数学符号和命题取名字的方法。他考虑的是算术系统。哥德尔设计了一种编码方法,给每个数学符号和数学表达式分配一个唯一的号码,这个号码是一个自然数。而一个号码最多只能对应一个符号或表达式,也有可能不是编码。通过他的方法,还可以给数学证明编码,因为数学证明实际上是表达式的序列。 给出一个表达式,我们能算出它的编码,反过来,给出编码我们也能求出表达式。而这些编码就是我们所说的名字。 给定编码方法后,表达式的名字是确定的,而不是像前面日常语言的例子那样,可以随意规定名字。为了方便,还是通过日常语言例子类比来说明数学上的自指。 ____ 由汉字组成。 把 M 填入空格,得到这句话: M 由汉字组成。这句话的名字究竟是 M 、 N 还是别的什么东西呢,这不是由我们随意规定的,而是通过计算确定的。 如果我们能找到某个名字填到空格,使得这句完整的话的名字刚好就是我们填上的名字,我们就说这句话是自指的。 自指定理 在数学上能实现自指吗?或者问,对于任意一种数学性质 Φ ,是否存在某个数 t ,使得 Φ (t) 的编码是 t 。 答案是肯定的。我们通过如下方法构造 t 。 先引入函数 S(x, y) 。 举例说明 S(m, n) 是什么意思。 m 是某个表达式的编码,比如 A(x) ,而 A(x) 只有一个自由变元 x 。将 n 代入 A(x) 得 A( n ) , A( n ) 的编码就是 S(m, n) 的函数值。 将 s(x, x) 代入 Φ (x) 得 Φ (s(x, x)) 。设 Φ (s(x, x)) 的编码为 p ,将 p 代入 Φ (s(x, x)) 得 Φ (s( p , p )) 。可得到, s( p , p ) 正好是 Φ (s( p , p )) 的编码。 所以 s( p , p ) 就是我们要找的 t 。 自指定理的具体表述是这样的: 对任意含有唯一自由变元的公式 Φ (x) ,存在 ψ ,使得 ψ ↔ Φ (‘ψ’) 是定理,其中 ‘ψ’ 是 ψ 的哥德尔编码。 从上面的讨论可得, Ψ 就是 Φ (s( p , p )) (因为 Φ (s( p , p )) ↔ Φ (s( p , p )) , s( p , p ) = ‘ Φ (s( p , p )) ’,所以 Φ (s( p , p )) ↔ Φ (‘ Φ (s( p , p )) ’ ) 。 说明 1 、上面并非对自指定理严格的证明,只是对其思路的大概说明。在证明中,涉及到形式语言,语法和语义等不同的概念,上面并没有严格区分这些。 2 、上面说的数学性质 Φ , Φ 是类似于 ___3 这样的式子。把某个数,比如 5 代入 Φ 得, 5 3 。有些 Φ 比较复杂,它可理解成“是定理”这一类关于数学命题的性质。 3 、既然数学可以实现自指,那么“本语句是假的”这句话是否会出现在数学中。答案是不能,因为假这概念无法在数学中定义。这是塔斯基定理的内容。 4 、 有人把“ L : L 是假的”误解成“ L = L 是假的”,从而感到困惑,因为左边是 L ,而右边是 L 是假的,比左边多三个字,怎么可能相等呢。 两者确实不相等,左边是右边的名字,就像你和你的名字不相等一样。如果确实要用等号,应该这样理解: L 是假的 =L 是假的 所以 L 是假的 = “ L 是假的”是假的 这里用“ L 是假的”表示 L 是假的这句话的名字,它是一个整体,不能理解成比 L 是假的还多一个双引号。
悲剧 Tragedy 按:最近两天的博文有滑向“顽固派”的危险,经慎重考虑,兄弟我决定“整风”向“革命派”至少是“改良派”靠拢,遂翻出这篇旧文贴出来。 敬告读者:其中涉及数学、元数学(metamathematics)、数理逻辑、证明论,点到即止(一些表述可能比较模糊,之所以壮着胆子写了,是想提供普朗克量子论诞生同期数学演化背景),若有对数学相关细节有兴趣,请参阅相关专家“科普”,鄙人主要讲物理故事 ...... 哥德尔定理部分,推荐应行仁老师的科普系列:《哥德尔定理的证明》 http://blog.sciencenet.cn/blog-826653-689727.html 三体问题部分,我 在文末 追加一个附注——附注来自我的好友张任宇博士( http://blog.sciencenet.cn/u/philipzhang ) 不过在戏台上罢了,悲剧将人生的有价值的东西毁灭给人看…… ——鲁迅 《坟·再论雷峰塔的倒掉》 鲁迅先生给“悲剧”下的“定义”是审美层面的,是悲剧的外向性( extraversion )。悲剧还具有一种内向性( introversion ),即——存在( existence or being )在时间中不可避免地走向毁灭。 序幕·混沌 《易》曰:君子慎始,差若毫厘,缪以千里。 ——《礼记·经解》 悲剧之所以不断地产生,原因之一就是它来的时候总是静悄悄…… 1889 年,那个几何作图考 0 分,但文笔一流的 儒勒·昂立·庞加莱 Jules Henri Poincar e (1854~1912) 从诺贝尔的“绯闻情敌”——米塔—列夫勒手上领走了瑞典国王奥斯卡二世( Oscar II )悬赏的 2500 瑞典克朗( Swedish Krona )与一枚金质奖章。 很多人都说出身法国显赫世家的庞加莱是个“天才”,那简直是太“客气”了,在数学与物理学之城里,满大街都是“天才”!与莱布尼兹、马赫、罗素一样,我们名之以“全才”——“全面的天才”!在“全”这一方面,他虽无法“空前”(亚里士多德的阴影),但注定已经“绝后”。 所谓“全”者,就是一出手便能数学、物理、天文以及未来的生命科学种种一网打尽。 1887 年,大学时代数学还不错的奥斯卡二世在一帮数学家怂恿下发起了一场数学竞赛,其中的一道题目是牛顿、拉普拉斯时代的“遗物”—— N 体问题( N-body problem )的求解。 杞国有人忧天地崩坠,身亡所寄,废寝食者 …… ——列子 《列子·天瑞》 “忧天地崩坠”的行为在中国是愚蠢的化身之一,但是,“杞人”若托生欧洲倒是有可能跻身一流智者的行列——自牛顿万有引力定律建立,天体系统稳定性的问题就成了一把高悬头顶的“达摩克利斯之剑”( The Sword of Damocles )。简而言之,在知道日、月、地三者存在相互吸引的作用后,人们就开始思考一系列与切身利益相关的问题: 月球会不会撞地? 地球会不会被拉向太阳? 地球会不会被甩出太阳轨道? …… “天地崩坠”从上古神话一下变成了与身家性命相关的未来,这个“未来”可能十分遥远,但决不能不考虑。所以,在不知何时而至的“末日审判”( Last Judgement )的恐惧阴影下,精确掌握天体系统中某个星体的位置变化便自然地成为了数学、物理以及天文学研究的一个重要方向。这个方向被抽象为一个普遍的数学或力学问题,即 N 体问题。当 N=2 时,称二体问题( two-body problem ),比如日地关系、地月关系已经由牛顿本人获得了完美的精确解了。 那么下一步,就是 N=3 的三体问题( three-body problem )——不就是多引入了个质点( particle )吗?有什么大不了的,“兵来将挡,水来土掩”! 牛顿确实是这么想的。但是,这一次“名垂青史”、“光耀后世”的不是他,而是“ N=3 ”! 拉格朗日、拉普拉斯、泊松、雅可比( Carl Gustav Jacob Jacobi )……“数理骑士团”史上最华丽阵容前赴后继,沉沙折戟,纷纷带着伟大的失败灰头土脸地去见了牛顿,数学家们终于明白“ 2 ”与“ 3 ”之间并不是只差了一个“ 1 ” …… 凭君莫话封侯事,一将功成万骨枯。 ——曹松 《已亥岁》 失败是成功之母,这句话有一个“精细结构”( fine structure )——别人的失败是自己的成功之母!就像热力学第一、第二定律的建立,必然是以无数“永动机”( perpetual motion )美梦的破灭为前提,“先烈”们壮志未酬,重任已经“历史地”落在了庞加莱肩上。 与前人不同,站在同一个舞台,庞加莱极好地进入一个快被遗忘的角色——天体力学的先驱开普勒。 当没完没了的的圆圈都不能拟合出天体的轨道时,你就必须彻底地,果断地,甚至是狂妄地抛弃它们!——“一条走不通的路,就等于不存在”,这是悄悄流传的隐秘版“开普勒定律”。 即使把三体问题抽象至两个有限质量的质点与一个无限小质量(小到无法对两个有限质量实施力学上的影响)的质点,我们所面临的仍然是一组“壮观的”微分方程( differential equation )。初中数学老师告诉我们,一组代数方程( algebraical equation )可解的充分必要条件是独立方程个数等于未知量个数,当未知量个数多于独立方程个数时,方程组就是不定方程( indeterminate equation )组,它的解就会有无数个。类似地,对微分方程组而言,我们也希望找到一些不变量( invariant )来减少“未知量”,以使问题简化至我们可以获得精确解的程度,牛顿以及他忠实的追随者们就是这么干的,结果我们都知道了。 而捧走奖金和奖牌的庞加莱完成了三项工作,虽然他并没有在传统意义上最终解决“三体问题”或“ N 体问题”,但是这三项工作无疑是具有里程碑意义的。首先它足以安抚 “极其有限的大众”(必须承认,就算是在欧洲,能达“杞人忧天”境界的亦非凡人)——太阳系是稳定的,其次“三体问题”作为一个“下金蛋的母鸡”的潜质已经被充分的挖掘出来了: 其一,庞加莱证明当 N 大于 2 时,微分方程组不存在统一的首次积分( uniform first integral ,只与时间、坐标、速度有关的代数首次积分)。一言以蔽之,就是“三体”乃至“ N 体”无法用传统的首次积分方法求解。 其二,庞加莱开发出了一套全新分析工具,工具名略(不好意思,正如杨振宁老先生的调侃“数学家的语言有时太‘干燥’”,我没怎么看懂)……这些方法不仅促成了对“ N 体问题”中天体轨道的定性研究,还构成了全新的现代数学或力学分支微分方程与微分动力系统( Differentiable Dynamical Systems )的核心。笼统地讲,就是庞加莱在探讨“ N 体问题”的过程中开拓出了一个全新的数学方向。 其三,庞加莱用他的数学“放大镜”第一次揭示了自然界最广泛且最隐蔽的性质——初始条件敏感依赖。也就是说,即使是一个遵循牛顿力学的系统,若初始条件作细微变化——“差若毫厘”,也会使得最终的结果有天壤之别——“缪以千里”。物理学在严格的牛顿力学框架下预测未来的信心受到了毁灭性打击。 “君子慎始”——庞加莱最终将他第三个发现小心翼翼地封存起来,他似乎意识到了什么…… Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas? 一只巴西蝴蝶轻轻拍打翅膀导致德克萨斯的一场龙卷风吗? ——马尔里斯 P . Merilees 为 E. N. 洛伦兹 E . N . Lorenz 演讲拟定的标题 大约 70 年后,被庞加莱雪藏的发现有了一个通俗且时髦的新名字——混沌( chaos )。 混沌,可怕的混沌! 圣殿里,教皇宝座上的牛顿面容憔悴——残阳如血,西风凛冽,在概率与统计的第一轮冲击中摇摇欲坠的经典物理大厦已经到了崩溃的边缘…… 三国式悲剧·确定性的丧失 董卓作乱,汉室倾颓。曹操矫诏,一十八镇诸侯会盟讨贼。平原县令刘备也来“凑个热闹”…… 1900 年 8 月 8 日,还是法兰西的巴黎。 索邦大学( Sorbonne )报告厅,第二届国际数学家大会( the International Congress of Mathematicians )会场掌声雷动。在万众瞩目中,哥廷根学派全盛时期的掌门人、数学家中的“无冕之王”、“数学界的亚历山大” 大卫·希尔伯特 David Hilbert (1862~1943) 受大会主席庞加莱邀请,从容走上主席台—— 先生们! Who of us would not be glad to lift the veil behind which the future lies hidden…… 我们中有谁会不乐于去揭开隐匿的未来面前那层面纱…… 在这篇名为《数学问题》( Mathematical Problems MATHEMATICAL PROBLEMS.pdf )的传世演讲中,希尔伯特一口气提出了 23 个有待解决的数学难题。除去其中照顾徒弟的“私心”、吞并物理学的“野心”外,“希尔伯特问题”( Hilbert ’ s problems )作为即将到来的 20 世纪数学发展的指路明灯是当之无愧的。 理性的先锋队——数学军团,迅速集结到了王者的旗帜。旌旗翻飞,兵强马壮,几何、代数、分析三大主力志得意满,各路干将擦掌摩拳,只待倾巢而出,直捣黄龙。 23 道命令已经下达,数理帝国新一轮开疆拓土的壮丽征程已是箭在弦上,不得不发! …… 纪录片必须在这里打住,拉普拉斯妖的超强性能明显实效了。这令人热血沸腾的景象既不是过去的结果,也不是未来的原因。恰恰相反,我们之所以对巴黎“盛会”有上述印象,正是因为站在 100 年后的回望——辉煌的结局造就传奇的开端! 讨董联军的盟主是“四世三公”的袁绍,不是“汉孝景帝玄孙”的刘备! 与会者质量都不怎么样!——会后,希尔伯特如是说。实际上,孤独的王者只当场下达了 10 道命令。杂乱无章的会议秩序、被迫中断的演讲、冷淡的听众反应……这一切怎么配得上数理十字军的誓师大会,怎么配得上神圣东征号角吹响前的序曲? 数学并不一定是数学家生活的全部。对与会的大部分数学精英而言,他们如此费尽周折地齐聚巴黎,除了回望古典数学的往昔峥嵘,展望 20 世纪的美好明天,还有一个彼此心照不宣的内心冲动——塞纳河畔的“别样风情”,时尚之都巴黎,那纸醉金迷的“夜生活”! 这个夜晚,位于巴黎北部蒙马特高地( Montmartre )的“红磨坊”( Moulin Rouge )几乎化为索邦大学报告厅的翻版,风姿绰约的法兰西舞娘“有幸”成为来自五湖四海的数学家们的“忠实听众”。在美人、佳酿、法式香吻、靡靡之音的环饲中,以风流倜傥闻名的希尔伯特无疑成为了最引人注目的明星,早晨的失落与挫败感在这个夜晚一扫而空。流光闪烁的舞池内,妖艳的女郎连声惊呼——原来,“数学之王”的舞步,可以和他在解决难题时展示的数学技巧一样,令人眼花缭乱,啧啧称奇…… 当然,“亚历山大”不会永久流连在“温柔乡”。希尔伯特没有停止他的脚步,他还有自认更崇高的使命——数学本身的“合法性”! 在牛顿纪元后的两百年里,人类认知疆域的立宪大会早已通过了一条明晰的不成文法——一切自然科学合法性的标杆是数学。这是科学教皇牛顿以来赋予数学的世俗权威,是经典时代所有纯粹数学家享受他们精神优越感的资本。 1897 年,第二次数学危机的硝烟尚未散尽,第三次数学危机( the third crisis of mathematics )又携翻天覆地之威,气势汹汹地杀将而来。继贝克莱主教的“无穷小量”之后,德国疯子康托尔( Georg Ferdinand Ludwig Philipp Cantor )的“集合论”( set theory )荣升第三任幽灵。这一次的暴风雨来得更猛烈,数学自身的合法性遭遇了其诞生以来前所未有的毁灭性打击。 话说天下大势,分久必合,合久必分 …… ——罗贯中 《三国演义》 一片混乱中,由于数学基础的认识分歧,数学军团走向分裂,形成各自为政,相互攻伐的三路大军——赤壁一战之后,三足鼎立之势已成: “魏”——以逼疯康托尔的利奥波德·克罗内克( Leopold Kronecker ,康托尔的老师 )、庞加莱、布劳威尔( Luitzen Egbertus Jan Brouwer )等为首的直觉主义学派( School of I ntuitionism ):欲革旧立新,改天换地。颇有经验批判主义大师马赫老先生遗风,十分亲近经验色彩浓厚的自然科学,以“存在即被构造”拒绝一切形而上的无穷与无限,不接受亚里士多德的逻辑排中律,甚至(比如克罗内克)高擎毕达哥拉斯“教主”大纛,连无限不循环的无理数都不承认。 “吴”——以文理通吃的贝特兰·罗素、皮亚诺( Giuseppe Peano )、弗雷格 ( Friedrich Ludwig Gottlob Frege ) 、怀特海( Alfred North Whitehead )等为首的逻辑主义学派( School of Logicism ):以还原论色彩的“数学 = 逻辑 + 符号”保“江东”——数理逻辑之全土,徐图天下。在旁人看来,这帮分裂势力不仅没有灭火,反而大有风助火势之举,必欲将乱世进行到底而后快。他们可以花上 300 多页的篇幅去给出 1 的“严格”定义;可以弄出了个令数学家头痛至今的“罗素悖论”( Russell ’ s Paradox ),其通俗版为“理发师悖论”——一个只给不给自己理发的人理发的理发师是否应给自己理发? “蜀”——以力挺康托尔的哥廷根掌门希尔伯特为首的形式主义学派( School of Formalism ):古典正统余脉,根红苗正。恪守形而上传统“价值观”,不以经验较真理之短长,唯无矛盾者为真,唯相容性( compatibility )为真。 三国纷争,生灵涂炭。当此乱世,最忧心忡忡的莫过于以“汉室宗亲”自居的“刘皇叔”——希尔伯特。为标榜正统,刘备的西南割据政权从来以“汉”为国号,而不会自称为“蜀”,这个习惯性称谓则是篡汉的魏政权之“发明”(吴政权在较长时期内仍然承认“汉”的正统地位)。希尔伯特本人也并不以“形式主义者”自居,这顶帽子恰是“夙敌”罗素和布劳威尔给他扣上去的,意在削弱其古典数学的正统地位,而希尔伯特深知“汉贼不两立”,欲正纲纪,必先讨“国贼”——直觉主义! 身兼“刘备”、“诸葛亮”双重角色的希尔伯特历经十余年艰辛,终于定出“北伐方略”——希尔伯特纲领( Hilbert ’ s Program )。与逻辑主义者的信仰类似,希尔伯特极端推崇欧几里德的《原本》范式,试图把整个数学建立在一组抽象而兼容的公理系统基础上,通过对公理系统的演绎推算扩展出数学的全貌。那么数学自身的“合法性”就有了具体的含义,即公理系统的无矛盾性或相容性。“纲领”为新时代的数学家们提出了一个崇高的战略任务—— 去证明这种相容性,捍卫数学神圣的“合法性”! 至于“兵出子午谷,直取长安”还是“六出祁山,绕道雍凉”的具体战术进程,希尔伯特选择较稳妥的后者。他主张先“屯兵汉中”——将古典数学公理化,其二“袭取祁山九寨以为根基”——将公理化成果用纯符号表述以实现彻底的形式化,其三“巩固雍凉,威慑秦川”——规避“无穷”风险,在有限步骤构造“元数学”( metamathematics ),待时机成熟便“下长安,破洛阳,汉室可兴”——以元数学证明形式系统的相容性,形式系统“合法”则古典数学“合法”! 出师未捷身先死,长使英雄泪满襟。 ——杜甫 《蜀相》 1930 年 1 月 23 日,年届七旬的希尔伯特在哥廷根迎来盛大的退休典礼——白帝城的那一夜,刘备把江山社稷托孤于诸葛亮;五丈原的秋风中,孔明把汉室生机交付与姜伯约。在“恨不能临阵讨贼”的痛苦中,老人发表了自己作为数学家的临别告白……时光一去 80 年,我们还能清晰地听见老人饱含深情的最后一声呐喊: We must know, We will know! 我们必须知道,我们必将知道! 作为古典“四大名著”之首的《三国演义》,其魅力在于散发着一种浸透了历史苍凉感的永恒悲剧性,罗贯中用恢弘大气的笔触渲染了一幅令后人唏嘘不已的史诗画卷——寄托了文人士子理想与正义的蜀汉政权之命运,是诗化的历史,是从坎坷走向辉煌,从胜利走向毁灭…… 几乎就在希尔伯特动情演讲的时候,他对数学规划的乐观远景戛然而止。 “柏拉图”悄悄地回来了…… 来自“维也纳小组”——“恩斯特·马赫学会”的 库尔特·哥德尔 Kurt Gödel (1906~1978) 一位 25 岁的奥地利逻辑学家、数学家、哲学家(将来还要友情客串物理学家),携带史无前例的摧毁性以一个恐怖魔鬼的狰狞面目出现在他陷入混战的同行面前。 洞穴阴影再次来袭…… 1931 年,人类理性进程中最具颠覆性的重量级论文《 论〈数学原理〉及有关系统中的形式不可判定命题 》( On Formally Undecidable Propositions of Principia Mathematica and Related Systems )在维也纳公开发表。从题目上看,数学“柏拉图”的意图十分明显,他的关注焦点放在了怀特海与罗素合著的逻辑主义“圣经”——《数学原理》( Principia Mathematica )与希尔伯特的形式系统;从内容上看,哥德尔成功地解决了 1900 年提出的“希尔伯特第 2 问题”——算术公理的相容性( The compatibility of the arithmetical axioms )证明…… 但是,希尔伯特怎么也高兴不起来,因为哥德尔的结果与数学之王的预想南辕北辙—— 相容性?——哥德尔扶正他的黑框眼镜——根本不可能! 从算术公理系统开始,一夜之间,“火烧连营七百里”——烈火熊熊中,希尔伯特纲领灰飞烟灭! 四周光明骤然黯淡,数学家猛然发现自己仍然身处阴暗的洞穴。他们惊恐万分,洞口被两头穷凶极恶的“畜牲”把住了去路,那是冥府的门神,一对恐怖的地狱之犬——赛博拉斯( Cerberus ): 一头叫“哥德尔不完备性第 1 定理”( The Gödel ’ s Incompleteness Theorem I ): 任一足以包含自然数算术的形式系统,如果是相容的,则它一定存在一个不可判定命题,即存在某一个命题 A 使 A 与 A 的否定在该系统中皆不可证。 另一头叫 “哥德尔不完备性第 2 定理”( The Gödel ’ s Incompleteness Theorem II ): 在真的但不能由公理来证明的命题中,包括了这些公理是相容(无矛盾的)这一论断本身。也就是说,如果一个足以包含自然算术的公理系统是相容的,那么这种相容性在该系统内是不可证明的。 数学家们战战兢兢,徒然任两头恶犬狂吠……阴影中,哥德尔(他当然也在洞穴里面!)依旧平静: 你是叙拉古的阿基米德, 再严密的防守, 也必然存在破绽; 你是不列颠的牛顿, 再精妙的构思, 也不能杜绝漏洞。 接受现实吧, 我的“亚历山大”, 有些事情, 我们永远也无法知道! 数学、逻辑、或者说人类伟大的理性,它的确定性已然终结! 顺便说一句,“命题 A ”学名“哥德尔命题”( Gödel ’ s proposition ),它后来作为主角参演了一部卖座的好莱坞( Hollywood )大片,名字叫 The Matrix (矩阵),中文译名《黑客帝国》…… 1900 ·无可奈何花落去 无可奈何花落去…… ——晏殊 《浣溪沙》 在很多人模糊的印象中,牛顿王朝的崩溃时间被设定于公元 1905 ,而“物理学编年史”中记载是这样的: 牛顿王朝 Newtonian Dynasty ( 1687~1900 ) 终点,公元 1900 。 在人类理性之域,这是值得铭记的一年: 4 月 27 日,伦敦,开尔文勋爵发表演讲,他为物理学家指明了“乌云”; 8 月 8 日,巴黎,希尔伯特发表演讲,他为数学家下达了“命令”; 8 月 25 日,八国联军占领北京的第 9 天,叫嚷“上帝死了!”的德意志疯子尼采死了,但是这并不意味着“上帝复活了!” …… 现在,时间: 12 月 14 日;地点:柏林。 中规中矩的柏林洪堡大学( Humboldt Berlin University )教授、普鲁士科学院( Prussian Academy of Sciences )院士 马克斯·卡尔·恩斯特·路德维希·普朗克 Max Karl Ernst Ludwig Planck (1858~1947) 这位上课从不带讲稿,也从来不会有口误的讲台“老资格”,今天竟有些紧张,像一个初次参加论文答辩的学术新兵,怀着忐忑不安的心情走上了柏林物理学会( The Berlin Physical Society ,即今天的德国物理学会)的例会讲台。 从台下的座位到讲台不过几步的路程,普朗克竟然好像走了很多个世纪…… 科学的历程,往往是抽象理论与具体经验的长途赛跑。有的时候,在纸上推公式的数学家或理论物理学家走到了前面;也有时候,在瓶瓶罐罐与机器轰鸣中的实验员或工程师迎头超越。在工业革命如火如荼的年代,无数科学的果实就诞生在蒸汽笼罩的技术喧嚣之中。 在冶金工厂里,某位细心的工程师偶然发现了一个有意思的现象:熟练的冶炼工人可以通过炉火的颜色大致判断锅炉的温度。这种不需要借助任何精密仪器的经验估计激起了他的兴趣,后来他把这个有趣的发现分享给了专注于热力学或辐射学( radiology )的物理学家朋友。 经过物理学家必要的数学抽象与物理简化,我们有了一个新的物理学模型( physical model )——黑体或绝对黑体( black body or absolute black body )。这是一种奇妙的“物体”,它像土财主痴迷金币那样贪婪地吸收一切投射到它的能量,一点都不反射( reflection ),所以我们形容它就像土财主的心一样,是完完全全、不带杂质的黑色。但是,再高明的“葛朗台”( Grandet )也拦不住自己的财产一点一滴地悄悄溜走,黑体吸收的能量最终要以热辐射的形式返还给外界。 普朗克的授业恩师基尔霍夫( Gustav Robert Kirchhoff )教授研究发现,“守财奴”的“资产外流”是有一定数学规律的——黑体辐射( Black body radiation )的能力只与其辐射波长(炉火颜色)和温度(锅炉温度)有关。但是,基尔霍夫并没有给出具体的辐射谱( radiation s pectra ),即辐射能力、波长、温度三者之间的定量数学关系,后续工作只有交与后人完成。 1896 年,德国物理学家维恩( Wilhelm Carl Werner Otto Fritz Franz Wien )从热力学出发,结合一些特殊假设给出了一个比较令人满意的黑体辐射数学关系——维恩公式( Wien ’ s Formula )。次年的精确实验表明,维恩公式在辐射的短波(炉火颜色偏蓝紫)区域与实测数据吻合十分完美,但在长波(炉火颜色偏红橙)区域出现了明显偏离趋势。 4 年后,在德国佬面前从来不甘落后的英国人奋起直追,以定量分析之精准闻名学界的世袭贵族瑞利男爵( John William Strutt , Baron Rayleigh ,第 2 任卡文迪许实验室主任)与在天文学领域造诣颇深的金斯( James Hopwood Jeans )先后在麦克斯韦经典电动力学( e lectrodynamics )与玻尔兹曼经典统计力学的基础上推导出了一个理论基础更扎实的数学关系——瑞利—金斯公式( Rayleigh - Jeans ’ Formula )。但自然确实是太幽默了,在数学的可怕折磨中诞生的瑞利—金斯公式并不比“德国版”的维恩公式好到哪里去,它在长波区域倒是很符合实验数据,但到了短波区域…… 一贯喜欢开玩笑的保罗·埃伦费斯特惊呼——天哪,紫外灾难( ultraviolet catastrophe )! 我们惊恐地发现,辐射谱上瑞利—金斯曲线奔向了无穷大——当一个物理学理论预言现实中的某个物理量会变成无穷大时,就证明该理论失效了! 其实维恩与瑞利—金斯两个公式所遇到的问题,对今天的“科学家”来说已经习以为常了。在今天,面对同一组实验数据, 10 位“科学家”撰写的 10 篇“论文”可以有 11 种解释,而其中任何一种解释只要能与部分数据相吻合就完事大吉了;更何况,面同一组样品, 10 个“实验员”可以搞出 12 套数据(我承认:我就在实验室里遇到过这种情况)。初始条件敏感依赖、蝴蝶效应( The Butterfly Effect )、混沌无处不在,天气、室温、心情、股票、电影、足球赛、 NBA ……太多因素影响结果了,总而言之,没什么大不了的! 但在 110 年前,这可是个足以引发经典物理帝国全境恐慌的大事! 首先,我们需要在逻辑上确认两个事实:第一,黑体辐射实验现象的可靠性与实验数据的精确性不容置疑;第二,不要怀疑诺贝尔物理学奖得主维恩( 1911 )、瑞利( 1904 )以及没有得奖的金斯(很遗憾……)三位杰出物理学家的“智商”——数学推导,特别是在小数点后第 3 位发现整个一族惰性气体元素( element of inert gases ,诺贝尔物理学奖的获奖原因)的瑞利男爵一贯持有实验精密与数学严谨的好名声! 对福尔摩斯来说,当所有可能情况都被排除以后,剩下的那个“最不可能”的情况就是真相!——所有物理学家都必须面对一个惨不忍睹的事实: 牛顿缔造的经典物理大厦之基座隐藏着一条极深的裂痕! 这条裂痕触及到了一个已经发酵成“废话”的“常识”—— Nature does nothing in jumps ! 自然界从来不飞跃! 莱布尼兹语气很坚定,这是他和牛顿极少的几个共识之一。因为没有这个前提,他的微积分,牛顿的流数术都成了一叠废纸!我们的自然具有连续性( continuity ),就像“ 1 ”与“ 2 ”之间的间隔是“无限”( infinitude ),一个物体的运动以及度量运动的能量不存在最小的单位,其值应当想怎么小,就怎么小。 8 个月前,睿智的英国老“气象员”开尔文就预报了“晴空”边界的两朵“乌云”,其中之一便是:在能量连续前提下,麦克斯韦—玻尔兹曼能量均分定理( the Maxwell-Boltzmann doctrine regarding t he partition of energy )在热力学中遇到的困难。 历史给两种人留下了载入史册的机会:一种是不知不觉的蠢人,一个极其愚蠢而不自知的选择往往就改变了决定无数人命运的历史走向,这一点,因滑铁卢( Waterloo )惨败幽居圣赫勒拿岛的拿破仑在回忆到他“亲爱的”格鲁希元帅( Marshal Crouchy )时,深有感触;另一种是冷静而理性的智者,他们充分明白自己的一举一动在历史中的分量,所以他们往往显得小心谨慎,甚至有些畏首畏尾…… 两个月前的 10 月 19 日,普朗克教授向物理学会提交了自己对黑体辐射的研究论文。在这篇论文中,普朗克“巧妙地”利用“内插法”( i nterpolation )将维恩公式与瑞利公式(金斯修正在 1905 年)中各自“合理”的部分“拼接”起来,形成了即吻合长波,又符合短波的普朗克公式( Planck ’ s Formula )。 但这种“庸俗”的数学技巧“卖弄”既不能服众,也不能满足普朗克自己,他必须给出自己公式的物理学解释—— 讲台上的普朗克一遍又一遍地深呼吸,他想尽量克制住自己的颤抖,至于这种颤抖是来自紧张,还是兴奋,他自己也不知道。 在台下听众焦灼的目光中,在例会主席不耐烦的催促下,普朗克下意识整理了一下领结,最后深吸一口气,咽下唾液,开始宣读他的论文…… 提问:普朗克教授,您的意思是……能量的辐射不是连续的,而是像粒子那样一份一份的……就像您命名的……“量子”( quantum )? 回答:呃……从辐射公式的理论推导这个角度考虑,我想,是这样的…… 远日衔山,神情麻木的牛顿指着眼前一片模糊在烟尘中的废墟,转向了气喘吁吁的普朗克—— 看,你的杰作! 我有罪, 我有罪, 我有罪, …… 听众们议论纷纷,普朗克默默走下讲台,一股强烈的负罪感油然而生——人类的艺术自此多了一种戏剧模式——普朗克式悲剧( Planck ’ s Tragedy ),一个人将用自己余生的全部精力去实现自我否定…… 热力学第二定律告诉我们,自然界的一切自发过程都是不可逆的。某些事一旦发生,除了上帝(祂死了!),无论用什么办法都不能消除它的影响。当躲在书斋里的普朗克教授绞尽脑汁地寻找妙法扼杀“怪胎”时,历史启动量子纪元…… 三体问题附注 : Oscar II的原始声明:“ Given a system of arbitrarily many mass points that attract each according to Newton’s law, under the assumption that no two points ever collide, try to find a representation of the coordinates of each point as a series in a variable that is some known function of time and for all of whose values the series converges uniformly.” 这句话意思是对于任意一个符合牛顿万有引力的(有限)粒子系统,假定任意两个粒子(视为质点) 不会相撞,给出每一个粒子运动轨迹的坐标表示,该表示的自由变量为 时间的级数,而且这些级数在全空间一致收敛。只要给出一致收敛的级数解,就解 决了n体问题。 Poincare发表在Acta Math.上的论文并未证明这个问题究竟是可解还是 不可解,但是伟大的Poincare给出了一种划时代的方法:常微分方程定性理论并为理解 动力系统(esp. Hamilton系统)提供了大量全新而深刻的思想。 1887年,Brun在Acta上 发表了一篇文章,证明对n体问题只有10个首次积分,但他的证明有一些地方过不 去。Poincare坚信这是对的,并在其获得Oscar奖的文章里,严格证明了这样一个结 论:除了已知的十个首次积分外,n体问题不存在只与时间,位置和速度相关的代数 首次积分。i.e.要想通过首次积分降维的方法解出n大于等于3的n体问题是不可能的,但这 并不意味着,n体问题不可解,只是意味着n体问题不能用首次积分的方法得到。但 是,Oscar问题明确说明了,应该用级数的形式给出解。事实上常微分方程解的存在 唯一定理告诉我们,n体问题的解存在且唯一。真正对n体问题作出肯定回答的是两个 人:K. Sunderman(n = 3) 和一个中国人Qiudong Wang(n大于等于4) . 他们分别给出了 在全空间上一致收敛的幂级数解(除去一个使得系统发生碰撞的初始条件的零测集后)。 历史记住了没有解出Oscar问题的Poincare但忘记了Sunderman和Wang,这充分的嘲笑 的Brower对构造证明的坚持。那个构造性的幂级数解,除了让我们看出有解之外,什 么也没有告诉我们,其实Sunderman和Wang的结果不比常微分方程解的存在唯一性定 理更深刻。这两个幂级数解收敛速度太慢,这使得它们甚至根本没有数值计算的意义。 数百万项以后才可能比较接近真实解,这使得初值条件的微小扰动都可能带来巨大的 误差,此即混沌。从Weierstrass设置的第一道问题的本意来说,Sunderman比Poincare更应该获得Oscar Prize,但是如果我们站在21世纪回顾这些历史,Poincare的工作才真正理解了这个问题。参考 http://en.wikipedia.org/wiki/Henri Poincare%C3%A9 K. Sunderman, Memoir′e sur le probl′em des trois corps, Acta Mathematica 36(1912), 105-179. Q. Wang, The globa solution of the n-body problem, Celestial Mechanics, 50(1991), 73-88. F. Diacu, The solution of the n-body problem, Mathematical Intelligencer, 18(1996), 66-70. PS: 在这里祝大家中秋节快乐,兄弟我想发起个活动——“中秋夜,看明月”,你要不看它就不在那儿了哦! Why?——你懂的!
(3)哥德尔不完备定理和它们的证明思路 对这个证明一直也没有太大兴趣。因为争论,刚刚浏览了一本书《哥德尔证明》,作者是欧内斯特·内格尔(Ernest Nagel)和 詹姆士 R. 纽曼 (James R. Newman)。这本书写得非常浅显清楚,有兴趣的朋友可以下载。 必须指出,哥德尔不完备定理和“数学的真理性”没什么关系,所以拿出逻辑命题来扯毫无必要。而郑波尽博主提出用哥德尔定理来充计算机科学的当家花旦,只说明我们的计算机科学家离真正的生生不息的信息时代距离遥远。而程代展老师说:“ 任何数学体系均有它既不能证明也不能证伪的命题 。”,则实在是夸大了哥德尔的工作。 书接上回,言归正传。 数理逻辑的目标,是建立推理的自动化过程,即把我们的推理过程变成计算机的运算过程。这一点正好和数学家们想通过演算的方式来建立一般化的定理证明的目标相契合-1931年,显然不是一个可以真正建立机器证明的时代。 “事实上,这正是二十世纪初在数学家们心中的普遍信念必然会存在某种固定的,严格的规则集合,用一个完全不用思考的自动机,能够完全机械地产生所有的数学真理。数学家们为什么会相信这个?因为他们是证明概念的信奉者,而在十九世纪,证明概念的焦点变得越来越清晰,所谓一个证明似乎就是在一个形式公理系统内部进行严格符号操作而得到的必然结果。”(见《哥德尔证明》一书)把数学推导过程变成算数演算过程,是信念似的东西,在1900年,Hilbert在其著名的23个问题中,第六条甚至雄心勃勃地提出将物理学体系公理化。 这是个我们比较容易理解的想法:一个学科的体系,最基础的基石是一些公理-它们在非数学的学科也被称为定律,然后借助一些基本概念,采用形式逻辑进行推导,就可以得到这些个公理盖含的所有定理。这一点在欧式几何中体现得既清楚又美妙。虽然我们并不确知一个学科的所有定理-它们也许有无穷多-但是我们可以在公理的基础上进行证明,换言之,我们就剩下了 定理证明 的工作。进而言之,如果我们能够将证明过程变成算算术,变成加减乘除,只要不是无限多步运算,自是妙不可言。 但是,这个想法在1931年被哥德尔打破了。哥德尔证明了以下两个被统称为“哥德尔不完备性定理”的定理(摘自wikipedia中文版): 【定理一】任何 相容 的 形式体系 ,只要蕴涵 皮亚诺算术公理 ,就可以在其中构造在体系中既不能 证明 也不能否证的命题(即体系是不完备的)。 Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete . In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory (Kleene 1967, p. 250). (wikipedia上英文比较清楚,但是要需要解释的太多,就不翻译了) 【定理二】任何 相容 的 形式体系 ,只要蕴涵 皮亚诺算术公理 ,它就不能用于证明它本身的相容性。 For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T includes a statement of its own consistency then T is inconsistent. (wikipedia上英文比较清楚,但是要需要解释的太多,就不翻译了) 这里,必须解释一下几个概念: 形式化:不论公理和定理,它们都是用断言或者命题表述的。这些断言和命题,我们都要把它们写成公式,这是命题的形式化;而推导的规则,我们也要将它们形式化,变成公式,这是规则的形式化。 形式体系:是从一组公理出发,通过形式化的推导办法(就是把“依靠逻辑推理的数学证明过程”变成“算算术”),生成了若干定理,由这些公理和定理合起来构成的整个体系叫形式体系。特别需要强调的,是我们先会假定这些公理或者定律,是“真”的。而如果我们使用形式化的推导办法,主要是推出“真”的定理。换言之,我们说这些形式化的推导是“保真”的。 相容性:相容性是从公理出发,指依靠形式化的推导办法(就是把“依靠逻辑推理的数学证明过程”变成“算算术”),我们不能推出有一个定理既是“真的”,而与此定理相反的断言也是“真的”。比如在某个形式化的断言表明“陈安歌唱得好”是真的,那么另一个形式的断言表明“陈安不是歌唱得好”,则这个关于陈安的形式体系就是"不相容"的,也可以说这个形式体系是没有“一致性”的。 完备性:如果不用集合论,这个解释比较复杂。简单地说,就是如果在一个形式体系中存在一个关于某个断言的"真""假"判断,也就应该存在一个形式上含义相反的断言的"真""假"判断。比如,在一个形式体系中如果存在“蒋科学是吃素的”的“真”“假”判断,就应该存在“蒋科学不是吃素的”的“真”“假”判断,否则这个形式体系就是不完备的。 皮亚诺算数公理:是一组关于自然数的生成规则的公理,很容易查到,就不讲了。 关于哥德尔定理的证明,非常纷繁复杂,来回绕圈,据说当他证明完了,只有几十个人能看懂。我也没找到原稿,也不准备去“看懂”。这里只是简单说说他的证明办法。某个使用了皮亚诺算数公理的形式体系,其生成过程所用到的规则也会被形式化(否则我们就没办法让机器自动化了),而那些形式化了的规则,变成了"算术",我们称为“元数学”。既然这个“元数学”是“算术”,当然就变成了包含皮亚诺算术公理的形式体系。哥德尔巧妙地利用了要处理的形式体系和“元数学”上的形式体系,构造了一个悖论。最后利用这个悖论,给出了他的证明。 有兴趣的朋友可以参考我给出的书。 行文至此,就可以明白,我为什么说: (1)形式化的公理体系含有内在的矛盾性(哥德尔对悖论的利用)。 (2)哥德尔的理论是关于形式化的公理体系的,是数学上的一个分支,与“数学的真理性”没什么关系;扯“数学的真理性”不要来扯数理逻辑。 (3)有很多学计算机的,从事信息行业的朋友,估计就没几个人关心这么个钻牛角尖的定理。所以这定理远远谈不上是个当家花旦。 (4)可以清楚地看出,定理的成立是靠“皮亚诺算术公理”的,所以程代展老师把事说大了。而且,百度一下就知道,欧式几何公理系统在一阶逻辑下就是相容且完备的。 (敬请期待下一篇。) 哥德尔不完备定理证明流程.pdf ----------------------------讨论----------------------------------- 对研讨有意义的回复(1) SN20111212 2013-2-24 18:24 此文和其它先发表的有关博文所讨论问题的出典如下: B. A. W. Russell, "The Principles of Mathematics," Cambridge University Press, 1903. A. N. Whitehead and B. A. W. Russell, "Principia Mathematica," 3 volumes, Cambridge University Press, 1910-1913. (通称PM) B. A. W. Russell, "The Philosophical Importance of Mathematical Logic," The Monist,Volume 23, Issue 4, Pages 481-493, October 1913. 关于介绍哥德尔不完全性定理的现代专业书籍,到amazon上去大概很容易找到,恕不一一列举了。 关于所讨论问题的最早,最好的中文文献,本人认为是: 王浩,“数理逻辑通俗讲话”,科学出版社,1981. 王宪钧,“数理逻辑引论”中的第三篇,北京大学出版社,1982. 你至少先认真读读上面两篇中文文献,就自然能够了解到哥德尔不完全性定理的来龙去脉,认识到其内涵远比通常那些不求甚解的胡乱解释深刻的多。 ---------------- 【作者说明】关于罗素的文献,网上没有搜到,但是找到一篇介绍罗素思想的PDF,如下。其中特别谈到了罗素悖论和罗素对一阶逻辑的贡献。 Russell, Bertrand - Reader.pdf