（逻辑学专业论文）哥德尔关于绝对不可判定命题的思想.pdf

摘要 本文主要分为三个部分：第一部分将简单介绍不完全性定理的历史来源以及 证明不完全性定理的大致思路，这部分基础性的知识主要是为后面的两部分重点 问题做好铺垫；第二部分将着重分析哥德尔关于绝对不可判定命题的思想，以及 少数由这些思想所能直接引出的哲学推论。其中将会涉及到以下问题：在何种意 义上数学是不可完全的? 是否存在绝对不可判定的数论命题? 数学中自明的公 理能否包含在有穷规则中? 人类心智与机器相比是什么关系? 绝对不可判定命 题如何支持数学实在论的观点? 第三部分主要考察在上述思想的前提下，绝对不 可判定命题以及不完全性定理的哲学意蕴，即其相应的哲学推论。此外还会涉及 到其他哲学家对绝对不可判定命题以及数学实在论与哥德尔不同的看法。 关键词：绝对不可判定命题、哥德尔、不完全性定理、数学实在论 中图分类号：b 8 1 a b s t r a c t t h ep a p e rc o n s i s t so ft h r e ep a r t s i nt h ef i r s tp a r t ，i tb e g i n sw i t ht h ei n t r o d u c t i o n t o i n c o m p l e t e n e s st h e o r e m sa n dt h eo u t l i n eo fi t sp r o o f ；t h i sb a s i ck n o w l e d g ei s p r e p a r e d f o rt h et w ol a t t e r i m p o r t a n tp a r t s g 6 d e l st h o u g h ta b o u ta b s o l u t e l y u n d e c i d a b l eq u e s t i o n sa n ds o m ep h i l o s o p h i c a ld e d u c t i o nd i r e c t l yl e a db yi tw i l lb e a n a l y z e di nt h es e c o n dp a r t ；a n di ti n v o l v e st h ef o l l o w i n gp r o b l e m s ：i nw h a ts e n s ei s m a t h e m a t i c si n e x h a u s t i b l e ? a r et h e r ea b s o l u t e l yu n d e c i d a b l ep r o p o s i t i o n si nn u m b e r t h e o r y ? c a ne v i d e n ta x i o m si nm a t h e m a t i c si n c l u d e di nf i n i t er u l e s ? w h l ti st h e r e l a t i o n s h i p o fa n dd i f f e r e n c eb e t w e e nh u m a nm i n d sa n dm a c h i n e s ? h o wd o a b s o l u t e l yu n d e c i d a b l eq u e s t i o n ss u p p o r tt h ev i e w o fm a t h e m a t i c sr e a l i s m ? t h et h i r d p a r ti sm a i n l yo nt h ep h i l o s o p h i c a li m p l i c a t i o na n dc o r r e s p o n d i n gd e d u c t i o no f a b s o l u t e l yu n d e c i d a b l eq u e s t i o n sa n di n c o m p l e t e n e s st h e o r e m sb a s e do nt h et h o d g h t s m e n t i o n e da b o v e f u r t h e r m o r e ，i ta l s oi n v o l v e so t h e rp h i l o s o p h e r s v i e w so n a b s o l u t e l yu n d e c i d a b l eq u e s t i o n sa n dm a t h e m a t i c sr e a l i s mw h i c hd i f f e rf r o mg & i e l s k e y w o r d s ：a b s o l u t e l yu n d e e i d a b l eq u e s t i o n ，g , z x l e l ，i n c o m p l e t e n e s st h e o r e m s ， m a t h e m a t i c sr e a l i s m c h i n e s el i b r a r yc l a s s i f i c a t i o n ：b 81 4 习i 士 l 百 哥德尔在数理逻辑领域做出的三大贡献是：证明一阶谓词演算的完全性；证 明算术形式系统的不完全性；证明连续统假设和集合论公理的相对一致性。这些 结果不仅使逻辑学发生了革命，而且对数学、哲学、计算机和认知科学都有非常 重大的影响。其中，1 9 3 1 年哥德尔证明的不完全性定理使数学基础研究发生了 划时代的变化，更是现代逻辑史上很重要的一座里程碑，也最深刻地体现了哥德 尔的数学哲学思想。该定理以及塔斯基的形式语言的真理论、图灵机和判定问题， 被赞誉为现代逻辑科学在哲学方面的三大成果。 8 0 年代后，随着哥德尔生前未公开的手稿的陆续公布，西方学界重新对哥 德尔倾注热情，一大批数学家、逻辑学和哲学家纷纷加盟研究行列，目前已有相 当成果。而在中国逻辑学界，哥德尔研究却一直是一个少有人涉足的艰深领域， 国内学者对哥德尔关于不完全性定理和不可判定命题的思想研究工作仍比较有 限，迄今为止少有对哥德尔思想进行深刻剖析的整体性研究论著面世。这给本文 的撰写带来了一定的困难，也带来了诱人的挑战。本文旨在通过介绍不完全性定 理提出的历史背景与证明思路，以进一步分析、探讨哥德尔有关绝对不可定判命 题的思想及相应的哲学内涵、哲学意蕴。 、 不完全性定理 1 1 不完全性定理的历史来源 1 1 1 世纪之交的数学 在1 9 世纪与2 0 世纪之交，迎来了数学哲学一个百花齐放的时代，关于数学 基础及数学方法合法性在当时的争论，为当代甚至现代的众多数学哲学战线都提 供了主要且坚实的哲学立场。当时的三大主义逻辑主义、形式主义和直觉主 义各有权威领衔，为数学基础给出了不同的哲学立场，在今天，每一种都仍有不 少支持者。夏皮罗( s t e w a r ts h a p i r o ) 借用狄更斯( c h a r l e sd i c k e n s ) 的名言，称 当时的数学在其“最好的时代，也是最坏的时代 。实分析中有力且硕果累累的 发展归功于柯西( a u g u s t i nl o u i sc a u c h y ) 、波尔查诺( b e r n a r db o l z a n o ) 和魏尔 斯特拉斯( k a r lw e i e r s t r a s s ) 等数学家，他们克服了无穷小问题把微积分放在了 一个坚实的基础上。希尔伯特( d a v i dh i l b c r t ) 写道，实复分析是“数学中所竖 立的最艺术最精美的结构 。尽管不需要无穷小或无穷大，这套新理论仍然依赖 于无穷集合( c o l l e c t i o n ) 。按希尔伯特的话说，“数学分析是一场关于无穷的交响 乐”。2 与此同时，在康托的集合论中也存在一个令人振奋的对于无穷的解释。 尽管有这些激动人心的发展，或正是因为它们，人们有一种基础性危机的感 觉。数学似乎是，也应该是所有规律中最精确最确定的，而这时出现了对它的挑 战和质疑，其中尤以罗素悖论带来的危机感和破坏性最为严重。 1 1 2 罗素悖论 逻辑主义的鼻祖弗雷格( g o t t l o bf r e g e ) 为了证明算术是分析的，意图将数 学化归为逻辑，他利用休谟原理及“等数”( 或说一一对应) 概念用逻辑定义了 “数”，继而又定义了后继关系，并最终运用对后继关系的封闭给出了自然数的 定义。然而休谟原理只决定了“f 的数= g 的数”( f 和g 是任意概念) 这种形 式的等同，但无法决定“f 的数= 尤里乌斯凯撒( j u l i u sc a e s a r ) ”这个命题的 6 、 不完全性定理 1 1 不完全性定理的历史来源 1 1 1 世纪之交的数学 在1 9 世纪与2 0 世纪之交，迎来了数学哲学一个百花齐放的时代，关于数学 基础及数学方法合法性在当时的争论，为当代甚至现代的众多数学哲学战线都提 供了主要且坚实的哲学立场。当时的三大主义逻辑主义、形式主义和直觉主 义各有权威领衔，为数学基础给出了不同的哲学立场，在今天，每一种都仍有不 少支持者。夏皮罗( s t e w a r ts h a p i r o ) 借用狄更斯( c h a r l e sd i c k e n s ) 的名言，称 当时的数学在其“最好的时代，也是最坏的时代 。实分析中有力且硕果累累的 发展归功于柯西( a u g u s t i nl o u i sc a u c h y ) 、波尔查诺( b e r n a r db o l z a n o ) 和魏尔 斯特拉斯( k a r lw e i e r s t r a s s ) 等数学家，他们克服了无穷小问题把微积分放在了 一个坚实的基础上。希尔伯特( d a v i dh i l b c r t ) 写道，实复分析是“数学中所竖 立的最艺术最精美的结构 。尽管不需要无穷小或无穷大，这套新理论仍然依赖 于无穷集合( c o l l e c t i o n ) 。按希尔伯特的话说，“数学分析是一场关于无穷的交响 乐”。2 与此同时，在康托的集合论中也存在一个令人振奋的对于无穷的解释。 尽管有这些激动人心的发展，或正是因为它们，人们有一种基础性危机的感 觉。数学似乎是，也应该是所有规律中最精确最确定的，而这时出现了对它的挑 战和质疑，其中尤以罗素悖论带来的危机感和破坏性最为严重。 1 1 2 罗素悖论 逻辑主义的鼻祖弗雷格( g o t t l o bf r e g e ) 为了证明算术是分析的，意图将数 学化归为逻辑，他利用休谟原理及“等数”( 或说一一对应) 概念用逻辑定义了 “数”，继而又定义了后继关系，并最终运用对后继关系的封闭给出了自然数的 定义。然而休谟原理只决定了“f 的数= g 的数”( f 和g 是任意概念) 这种形 式的等同，但无法决定“f 的数= 尤里乌斯凯撒( j u l i u sc a e s a r ) ”这个命题的 6 真值，所以弗雷格并未就此满足，他不光要确定自然数之间的关系，还要确定自 然数的身份( 自然数是什么) 。于是他用概念的外延意图进一步定义自然数：“概 念f 的数是与概念f 等数这个概念的外延。”比如自然数2 是所有恰好包含 两个对象的概念的外延，每副手套、每个人的父母都是自然数2 的一个成员。可 以说，如果上述定义都是正确的话，那么他就解决了数学基础中最核心的那些问 题，然而弗雷格关于概念及其外延的理论中，其中一个决定性的支架基本法 则五后来被证明是有问题的，其陈述如下：“对任意概念f 、g ，f 的外延等于g 的外延当且仅当对任意对象a ，f a 当且仅当g a 。” 1 9 0 2 年，一封来自罗素( b e r t r a n dr u s s e l l ) 的信3 揭露了基本法则五的不一 致。令r 为恰在下述情况对x 成立的概念：“存在概念f ，使x 是f 的外延且f x 为假。”令r 是r 的外延。假设心为真，那么存在概念f ，使得r 是f 的外延且 f r 为假，由基本法则五就可以得出鼢也为假( 因为r 也是r 的外延) 。因此， 如果心为真，那么心为假，所以鼢是假的。接着存在概念f ( 即r ) 使得r 是f 的外延并且f r 为假。所以，根据r 的定义，r 对r 成立，因而黜为真。这 是一个矛盾，所以基本法则五是不一致的。这也就是现在为人们所知的罗素悖论。 弗雷格把罗素悖论视为他的逻辑主义方案的灾难，并且回信给罗素说：“因为没 有了我的法则五，不仅我的算术的基础，而且算术的唯一可能的基础似乎消失 了 4 罗素却不这么想，并且为了解决自己的悖论提出了恶性循环原则和分 枝类型论，还花了大量时间和怀特海( a l f r e dn o r t h 喊t e h e a d ) 一起写了i ：数学 原理，然而这不是一次成功的尝试。此处不再对这些尝试进行更多说明，总之 根据像罗素悖论这样的二律背反，人们甚至不确定集合论是一致的。即使康托解 释说是集合的聚集( c o l l e c t i o n ) 过于庞大以至于不能够全部收集在一个集合中， 而使用所谓“不一致的集群 ( i n c o n s i s t e n tm u l t i t u d e s ) ，也无助于这种危机感。 二律背反引来对数学方法合法性的攻击，引导数学家们给数学方法加上严格的限 制，而这种限制会破坏实分析和复分析。 1 1 3 希尔伯特计划 为了解决这种对数学基础的危机感以及回应对数学方法合法性的攻击，形式 主义的鼻祖希尔伯特提出了希尔伯特计划，并为其确立了一个认识沦目标：“我 的理论的目的是一劳永逸地建立起对数学方法的确信。”5 它将建立在先前公理化 各个数学分支的工作以及像弗雷格这样的逻辑学家在发展严格的逻辑系统的不 朽成就之上：“存在着一条令人满意的道路去避免悖论而不用背叛我们的科 学。帮助我们发现这条道路的要求和态度是这些：( 1 ) 我们要仔细地研究成 果丰硕的定义和演绎方法。我们要看护它们，使它们强健，让它们有用。没有人 能把我们赶出康托为我们创造的乐园。( 2 ) 我们必须在整个数学中为我们的演绎 建立起像存在于普通初等数论中一样的确信，它是无人怀疑的并且矛盾和悖论只 可能因为我们自己的粗心而发生。6 这一计划背后的想法是要仔细严格地形式化 数学的每个分支及其逻辑，然后去研究该形式系统以确认它们是一致的。一致性 在希尔伯特计划以及他的整个理论中占据了重要的位置，他在与弗雷格的通信中 写得非常清楚：“如果那些任意给出的公理以及它们的所有的推论彼此不矛盾 那么他们就是真的且他们所定义的东西存在。这对我来说是真和存在的标准。 从字面上，希尔伯特声称如果一个公理集是一致的，那么它们就是真的且它们说 的东西存在，这与我们在其他领域里的思考方式形成鲜明对比。对希尔伯特来说， 更谨慎的陈述是，一个公理集的一致性足矣使它们构成数学的一个合法分支，一 致性是数学家所需要的全部“真”和“存在。无论如何，在这里“一致性”的 概念已被清晰地表达出来，即使是在更具有哲学意义的情况下。 为了描述希尔伯特计划，我们必须先介绍其核心“有穷元算术”( f m i t a r y a r i t h m e t i c ) 。最需要强调的是，有穷元算术并不被理解为一种无意义的游戏或是 从无意义的公理到其推论的演绎( 像形式主义经常说的那样) 。相反，有穷元算 术的判断是有意义的，它们具有研究对象。有穷元数学的公式包括等式，如“l + 1 = 2 和“1 2 3 4 + 4 3 2 1 = 5 5 5 5 ，以及这些的简单符合，如“l + 2 = 3 并且l + 1 3 ”或甚至“1 0 01 不是质数”，还有包含有界量词的句子，如“存在自然数p 小于10 0 1 ，且p 和p + 2 都是质数”。注意这些句子提到的性质和关系都是能行可 判定的，即存在一种算法( 或计算机程序) 来计算是否具有这些性质和关系，判 断它们是否为真。由于有界量词的界限可以是非常大的，这里涉及一些理想化， 但是在有界量词之下只存在有穷的情况需要考虑，因而这样的命题只意味着计 算，希尔伯特把这种句子称作是有穷元的。 那么有穷元算术的内容是什么? 它为什么具有与数学其他部分不同的地 位? 希尔伯特认为在某种意义上有穷元算术考虑的是所有( 人类) 思维甚至 逻辑演绎的前提( p r e c o n d i t i o n ) 的东西。利用康德的语言，希尔伯特写道， 只是为了一致地思考，“有些东西必须在观念中被给出，即某种逻辑之外的具体 对象，他就像被直接经验到的那样是先于所有思维而被直观到的。为了使逻辑演 绎确定无疑，我们必须能够了解这些对象的每个方面，它们的性质、差别、序列 和相邻( c o n t i g u i t y ) 必须被给出，这些对象本身也必须作为某种不能再归约成其 他任何东西的东西而被给出这是基本的哲学，我发现它是必然的，不仅仅是 对数学，而是对所有科学的思考、理解和交流。 8 他认为有穷元算术的主题对所 有人类思维来说是本质的。在这里我们看到类似康德的想法，这个想法是，为了 思考和推理，我们就不得不使用符号并且以某种或其他种方式操纵它。有穷元算 术可能不是无可挑剔的，或者说对怀疑免疫的，但它是如此确定无疑以至于它就 是人类所可能的前提。不存在什么比有穷元算术更好的，或者说认识论上更可靠 的立脚点。9 要明确的是，有穷元算术只是数学美妙画卷中的( 可能是平凡的) 一小部分， 任何超越有穷元算术的，比如含有无界量词的陈述，以至实分析、复分析、泛函 分析、几何、集合论等等，希尔伯特把它们都称为“理想数学 ，以类比几何学 中的在无穷处的理想点。当然，理想数学一定能作用于有穷元算术。对形式化的 理想数学分支，唯一的严格要求是，人们不能用它导出一个对应于有穷元陈述的 真值为假的公式。假设t 是某个理想数学的一个形式化，并且令q 为任意有穷 元陈述，那么除非q 可以在有穷元算术中被判定为真，否则我们应该不能在t 中导出q ( 的对应公式) 。用当代的术语来说，形式系统t 应该是有穷元算术的 保守扩张( c o n s e r v a t i v ee x t e n s i o n ) 。比如说，令形式化理论t 是一致的，即利用 t 的公理和规则都不可能导出矛盾公式，像“0 0 ”，如果每一个真的有穷元陈 述对应于t 的一条定理且t 使用标准的演绎系统，那么t 的保守性等价于它的 一致性，所以理想数学的要求就是一致性。在这里我们再次看到希尔伯特对一致 性的强调。 要注意的是，如果t 是一个形式化的公理系统，那么“t 是致的”这一陈 述本身是有穷元的，可以利用概括的字母公式化。“t 是一致的”这一陈述有这 样的形式：“如果a 的最后一行是0 0 ，a 不是t 中的一个推理”。希尔伯特计划 9 的最后一步是给出那些完全形式化的数学理论的有穷元的一致性证明。这就是 说，为了使用一个理想数学的理论，我们必须把它形式化，然后用有穷元算术证 明该理论是一致的。一旦对理论t 完成这一步，我们就达到了认识论的目的。 我们有极大的信心，利用t 不会带来矛盾，也不会产生任何错误的有穷元陈述， 这是我们对理想数学理论所能要求的一切。如果t 是康托集合论的形式化，那 么一旦我们拥有了一个有穷元一致性证明，我们就会以极大的确定性知道我们将 不会被赶出那片乐园了。 1 2 不完全性定理及其证明 1 2 1 不完全性定理 1 9 3 0 年，年轻的哥德尔( k u r tg 6 d e l ) 获得博士学位之后，为了获得大学授 课资格，开始沿着希尔伯特方案的路线着手解决希尔伯特第二问题即建立整 个数学的一致性。哥德尔最初是想循着希尔伯特有穷元算术的方案首先建立算术 理论的一致性，然后再建立相对于算术而言实数理论的一致性，但出乎意料的是， 他得到了与希尔伯特预期完全相反的结果，对希尔伯特计划的认识论目的给予了 打击一许多人说是致命的一击。哥德尔首先用一阶谓词逻辑的形式语言表达了 皮亚诺算术( p e a n oa r i t h m e t i c ) ，同时将所形成的算术形式系统记为p a ，然后在 p a 中构造了一个句子p ，并证明了如果p a 是一致的，则p 在p a 中不可证；如 果p a 是一致的，则p 的否定- , p 在p a 中不可证( 其中“一致”是一个比 “一致 略强一点的性质，它要求不存在公式o ( x ) ，使得似0 ) ，m ( 1 ) ，西( 2 ) ，以 及“存在一个自然数x 使m ( x ) 为假”都可证。) ，罗瑟( b a r k l e yr o s s e r ) 在1 9 3 6 年证明可以将一致性的条件弱化为一致性。这样，如果p a 是一致的，则它将 无法“判定 p ，而这样的p 就称为不可判定命题( 即命题和命题的否定都不是 系统的定理) 。于是我们可以得到：“任何足以包含皮亚诺算术的形式系统，如果 它是一致的，就是不完全的( 其中存在不可判定命题) ”。这一结果被称为哥德尔 ( 第一) 不完全性定理，它是2 0 世纪主要的智慧成就之一。 需要注意的是，哥德尔构造的这个句子p 确实具有有穷元陈述的形式( 使用 到用以概括的字母) 。直观地说，p 是“p 在p a 中不可证”这一陈述的公式化。 的最后一步是给出那些完全形式化的数学理论的有穷元的一致性证明。这就是 说，为了使用一个理想数学的理论，我们必须把它形式化，然后用有穷元算术证 明该理论是一致的。一旦对理论t 完成这一步，我们就达到了认识论的目的。 我们有极大的信心，利用t 不会带来矛盾，也不会产生任何错误的有穷元陈述， 这是我们对理想数学理论所能要求的一切。如果t 是康托集合论的形式化，那 么一旦我们拥有了一个有穷元一致性证明，我们就会以极大的确定性知道我们将 不会被赶出那片乐园了。 1 2 不完全性定理及其证明 1 2 1 不完全性定理 1 9 3 0 年，年轻的哥德尔( k u r tg 6 d e l ) 获得博士学位之后，为了获得大学授 课资格，开始沿着希尔伯特方案的路线着手解决希尔伯特第二问题即建立整 个数学的一致性。哥德尔最初是想循着希尔伯特有穷元算术的方案首先建立算术 理论的一致性，然后再建立相对于算术而言实数理论的一致性，但出乎意料的是， 他得到了与希尔伯特预期完全相反的结果，对希尔伯特计划的认识论目的给予了 打击一许多人说是致命的一击。哥德尔首先用一阶谓词逻辑的形式语言表达了 皮亚诺算术( p e a n oa r i t h m e t i c ) ，同时将所形成的算术形式系统记为p a ，然后在 p a 中构造了一个句子p ，并证明了如果p a 是一致的，则p 在p a 中不可证；如 果p a 是一致的，则p 的否定- , p 在p a 中不可证( 其中“一致”是一个比 “一致 略强一点的性质，它要求不存在公式o ( x ) ，使得似0 ) ，m ( 1 ) ，西( 2 ) ，以 及“存在一个自然数x 使m ( x ) 为假”都可证。) ，罗瑟( b a r k l e yr o s s e r ) 在1 9 3 6 年证明可以将一致性的条件弱化为一致性。这样，如果p a 是一致的，则它将 无法“判定 p ，而这样的p 就称为不可判定命题( 即命题和命题的否定都不是 系统的定理) 。于是我们可以得到：“任何足以包含皮亚诺算术的形式系统，如果 它是一致的，就是不完全的( 其中存在不可判定命题) ”。这一结果被称为哥德尔 ( 第一) 不完全性定理，它是2 0 世纪主要的智慧成就之一。 需要注意的是，哥德尔构造的这个句子p 确实具有有穷元陈述的形式( 使用 到用以概括的字母) 。直观地说，p 是“p 在p a 中不可证”这一陈述的公式化。 因此，哥德尔的结果摧毁了用单个形式系统来把握所有算术甚至所有经典数学的 希望。如果某人提出了这样一个可能的形式系统，那么我们可以找到一句句子， 使得该系统无法“判定”它，尽管我们可以知道这旬句子是真的( 如果它是假的 将会导致矛盾) 。然而为所有理想数学找到单个形式系统的梦想并不是希尔伯特 计划的正式( 或必要) 部分，我们所说的打击来自别的地方。 哥德尔对不完全性定理的证明背后的推理可以在给定的形式系统之中重新 演绎。特别地，如果我们能将“在p a 中可证形式化，那么我们可以在p a 中 推出一句表达如下内容的句子： 如果p a 是一致的，那么p 在p a 中不可证。 但正如之前提到的，“p 在p a 中不可证”就是p 。因此，我们可以在p a 中推出 一句事实上如下的句子： 如果p a 是一致的，那么p 。 假设p a 是一致的，并且我们可以证明p a 一致，那么通过上面的句子，我们可 以证明p ，而这与不完全性定理恰恰矛盾。所以如果p a 是一致的，那么我们肯 定不能证明p a 一致。这便是哥德尔的第二不完全性定理。直观地说，它断言了 任何包含皮亚诺算术的一致理论都不能证明自己的一致性。 这一结果的确显示了希尔伯特计划的问题。令p a 为( 理想的) 算术，例如 经典自然数理论的形式化，希尔伯特计划要求对p a 的一致性给出一个有穷元证 明。但是第二不完全性定理就是说，如果p a 确实是一致的，那么p a 一致性的 直接陈述在p a 自身中无法推出，更不用说在p a 的有穷元部分中推出了。同样 的情况也对其他形式系统使用，只要它能包含皮亚诺算术。希尔伯特计划要求对 演绎系统的一致性给出一个有穷元证明，而现在，连在该系统本身中都无法证明 其一致性，更不用说在一个更安全的子系统中了。 哥德尔不完全性定理第一次向世人真正澄清了“真”与“可证 概念的本质 区别。由于一个命题在一个形式系统中可证，就意味着遵循推理规则，能够一步 接着一步地在有穷步骤内完成证明过程。但哥德尔指出，即使限制在皮亚诺算术 这样狭小的数学范围内，要想用形式化的有穷手段证明它的一致性这一真理都是 不可能的。换句话说，任何丰富到足以包含皮亚诺算术的形式系统，至少会遗漏 一个数学真理，数学形式系统不能囊括所有的数学真理。那么，能不能添加更强 的公理扩充原有的系统穷尽所有的数学真理昵? 哥德尔说，不行! 因为，对于新 扩充的系统还会有新的数学真命题在其中不可证，继续扩充，情形依然如此。 实际上，除非你把这种扩张过程持续到超穷，否则这种系统连最简单的算术真理 都不能穷尽。哥德尔本人在谈及不完全性定理时曾说过，“我在数论形式系统中 构造不可判定命题的启发性原则是将可证性和相对应的高度超穷的客观数学真 理概念相区分”。看来，可证数学命题和数学真理之间永远隔着一个超穷距离， 仅仅使用有穷方法甚至没有希望逼近它。正如哥德尔所说，“数学不仅是不完全 的，还是不可完全的”，这一点也恰是哥德尔定理最深刻的哲学意蕴。 1 2 2 不完全性定理的证明 在介绍不完全性定理的证明前，首先要明确几个概念： 哥德尔编码。我们将用它来使合式公式和系统能“谈论 自身。特别地，我 们将用它使系统能表达它的元理论( 可证性) ，用合式公式来表达在系统内什么 是可证的。哥德尔编码的创造和它在此处的应用是哥德尔的两个伟大成就。哥德 尔编码的本质是给形式语言中的符号指派哥德尔数。在不完全性定理的证明中， 哥德尔数将被指派给形式语言中的( 1 ) 每个符号，( 2 ) 有穷符号串( 无论是否 合式公式) ，( 3 ) 符号串的有穷序列( 无论是否证明) 。而且，人们能简单地通过 检视一个数字来知道它是否对应于一个符号、符号串或者符号串序列。在这三者 以及它们对应的哥德尔数之间有一一对应的关系，并且也有简单、能行的办法来 进行相互的转换( 翻译) 。 证明数对。如果每个符号串序列都有对应的哥德尔数，那么必然会有哥德尔 数对应于证明。令n 为一个符号串序列的哥德尔数，m 为一个合式公式( 符号串) 的哥德尔数，我们可以定义一个二元谓词p n m 来表达n 证明了m 。如果n 确实 证明了m ，则p n m 为真。我们将把使p x y 为真的有序数对 称为形式系统s 中的证明数对。有了谓词p x y 我们就可以表达某个合式公式a 不是定理，或者 说在s 中不可证。令a 的哥德尔数为a ，则、( = l x ) p x a 表达的就是没有符号串序 列能证明a ，或者说不存在证明数对以a 为其第二个数字，或者简单地说1 卜a 。 用v x - - 1 p x a 表达也是一样的。一方面来说，这样的表达只是关于数字的，但另一 方面来说，它们也是关于s 的可证性的。我们不能说它们的数论解释是“首要 的，而元理论解释是“次要”的。由于语义由语法决定，它们实际上是等同的。 自指。如果一个合式公式只有一个自由变元，并且我们将这个合式公式自身 的哥德尔数代入这个变元，那么我们实际上使这个合式公式间接地自指了。令 n x 的哥德尔数为n ，断定n n 一方面表达了某个数r l 具有n 这个性质，但它同 样也表达了哥德尔数为1 1 的这个合式公式( 即n x ) 具有n 这个性质，因为n 只 是n x 的一个编码。这种双重含义和间接自指是哥德尔证明的本质。当然b i n 这 个闭语句也是关于n x 这个开语句的，这也让自指更显得间接。为了方便，我们 将哥德尔数为n 的合式公式记为“公式r l 。如果我们想让公式1 1 间接地自指( 让 它的一个闭语句指向自己) ，并且这个公式恰有一个自由变元，那么我们就将n 代入变元，然后我们可以定义个一元谓词q n 作为这个代入后的公式。因此， q n 是将n 代入公式n 中唯一的自由变元后的公式，或者说是一个断言自身的合 式公式。如果p x 的哥德尔数为p ，那么q p 和p p 是等价的。由于q n 自身也有 一个哥德尔数，我们还可以定义一个二元谓词q x y 来表达y 是q x 的哥德尔数。 这样一来，q x y 说的是将x 代入公式x 的自由变元后得到的公式的哥德尔数是y 。 哥德尔的证明简单来说是构造一个合式公式，其含义是“这个公式在s 中不 可证”，然后证明它在s 中是不可判定的，从而证明它是真的。这个公式一方面 是关于数的，另一方面在证明中我们可以看到它断言了自身的不可证性。这个重 要的公式通常称为g ，取了哥德尔的首字母。 哥德尔给出的是一个构造性的证明，他实际地构造了一个不可判定的公式， 也就是g 。为了构造g ，我们首先给出如下公式： 我们称其为f ，因为在它之后g 马上就要出来了。令f 的哥德尔数为f o 直观地 说，f 说的是不存在证明数对 使y 为q z 的哥德尔数。简而言之，公式y 在 s 中不可证，所以q z 在s 中也不可证。现在如果f 能断言自身的不可证性，我 们就能得到g 了。为了让f 自指，我们将f 的哥德尔数代入f 中唯一的自由变 元z 。我们就得n - rq f , 即 g ：13 x 3 y ( p x y a q f y ) 注意f 与g 唯一的不同就是自由变元z 被f 代入了。尽管看上去很平凡，但这就 是著名的句子g ，我们考察一下g 的含义： 1 首先可以清楚的是g - = q f 。我们将f 自身的哥德尔数代入其自由变元，根据定 义，构造出q f ，只是称其为g 罢了。 2 g 实际上说的是不存在证明数对 使y 为q f 的哥德尔数，但q f 就是g 。 3 或者说哥德尔数为y 的合式公式在s 中不可证。 4 而哥德尔数为y 的这个不可证的合式公式就是q f ( 根据q f y 的定义) 或说g ( q f = - g 我们在1 中就说过了) 。 5 因此，g 在s 中不可证，即1 卜g 。 所以g 的含义是( 表达了) g 在s 中不可证! 然而构造出g 是一回事，证明其不可判定性是另外一回事。还记得一个合 式公式是不可判定的，当且仅当它和它的否定在s 中都不可证。我们首先用反证 l - l 法证明g 在s 中不可证。假设g 在s 中可证，那么卜g ，但是g 的含义是1 卜g ( 即我们可以在s 中通过g 得到这个结论的形式化语句) 。这里遇到了一个矛盾， 所以我们的假设( g 可证) 不成立。重要的是要注意到尽管假设g 可证会导致矛 盾，假设g 不可证却不会。如果我们假设g 不可证，那么我们得到1 卜g ，而这 正是g 本身的含义。这是g 和说谎者悖论间重要的( 但不能说是本质的) 差别： 无论你假设说谎者悖论是否成立最终都会导致矛盾。只有我们假设g 可证时_ 才 会导致矛盾，假设其不可证时却不会，这已足够说明它是不可证的。其次我们证 明g 的否定在s 中不可证，同样运用反证法。假设1 g 可证，即卜、g ，记得命 题g 实际上就是1 卜g ，我们通过替换得到卜1 ( 1 卜g ) ，由此可以化成卜g ，这和 我们的假设矛盾。所以g 和，g 在s 中都不可证，它们在s 中都不可判定。 通过表明g 在s 中是不可判定的，哥德尔已经足以显示在s 的结构中有着无 法填补的“漏洞 ，足以显示s 的不完全性。然而通过表明g 是真的，显示的不 光是s 无法判定某些命题，而是s 无法判定某些我们可知为真的命题。我们已经 证明了g 在s 中不可证，由于这正是g 本身的含义，我们可以马上知道它是真 的。这实际上是从它的不可证性证明它的真，没什么比这个更能显示出“真与 “可证 之间的分离，这也是不完全定定理的基本推论之一。我们也可以倒过来 通过g 的真证明其不可证。如果我们假设g 是假的，那么g 可证，因此在s 的 每个模型中都不存在证明数对 使y 为q f 或g 的哥德尔数，所以g 不是可 证的( 不是定理) 为真，这和我们的假设g 是可证的( 是定理) 矛盾：但如果 1 6 我们假设g 为真，则不会导致任何矛盾，只会迷惑而惊奇地认识到g 在s 中既 是真的，又是不可证的。 注意到我们只是在元理论的层面上“证明 g 为真，而不是( 也不可能是) 在s 中，这非常重要。这意味着哥德尔做了一些系统s 做不到的事情，即证明g 的真。因为形式系统和图灵机是同构的，并且s 的不完全性是所有足够强的一致 系统所共有的，对此的一种解读是哥德尔( 或说人类理性) 做的事情没有机器能 够做到。如果确实如此，人类理性确有某些方面是任何机器在原则上都无法达到 的。 哥德尔的第二不完全性定理实际上是第一不完全性定理的重新( 进一步) 演 绎。概略地说，它说的是任何足够强的系统都无法证明自身的一致性，除非它是 不一致的。我们将用到的系统还是在刚才的证明中那个有价值的良构的算术系 统。假设这个系统是一致的，则断定该系统一致性的合式公式将被证明在该系统 中不可证。首先我们要将“s 是一致的 形式化，这可以通过一致性的定义和证 明数对做到，s 是一致的当且仅当其无法导出( 证明) 矛盾，我们只需要在s 中 任取一个矛盾式o ( 假的合式公式) ，假设其哥德尔数为0 ，合式公式_ 13 x p x o 即表达了s 的一致性，我们将其命名为s - c o n 。在第一不完全性定理的证明中自 指的那个合式公式我们还是称作g 。记得g 断定了g 在s 中不可证( - 1 卜g ) 。 此后我们用到的唯一一条新规则是( a - b ) - ( 卜a _ 卜b ) ，这是一条逻辑定理。 1 s - c o n - - , g第一不完全性定理证明中已证 2 i - - s - c o n - 卜g 1 ，( a _ b ) _ ( 卜a - 卜b ) 3 ，卜g第一不完全性定理证明中已证 4 1i - - s c o n2 ，3 ，否后否前式 可以看出这个证明靠的是从一个6 订提中推出g 和1 卜g ( 第1 和第3 步) ， 然而这主要是由于g 的特异性而不是前提的关系。因此，如果算术是一致的， 那么它的一致性不可能由在算术的形式化中可表达的算术推理或甚至元数学推 理所确立。通过表明算术系统不能证明自身的一致性，第二不完全性定理迫使我 们只能非形式化地证明系统a 的一致性，或者只有在系统b 中证明。如果我们 求助于另一个系统b ，我们提供的实际上仅仅是一个“相对一致性的证明 ，它 的合法性完全取决于第二个系统b 的价值，包括一致性。但b 的一致性显然也 有待考察，于是我们必须再求助系统c ( 另一个系统) ，如此反复以至无穷。如 果说哥德尔的第一不完全性定理显示了算术系统不可完全，即无论我们花费多少 时间精力总有些数论真理不可判定；那么第二不完全性定理则显示了我们永远无 法对算术深信不疑。毫不夸张地说，干百年来两个荣耀的数学理想被这两条定理 永远地粉碎了。 1 3 不完全性定理在不同语境下的版本 显然，哥德尔定理与数学家的最初期望相去甚远，因为，一方面人们期望数 学形式系统囊括所有数学真理，一方面又分明知道总有数学真理不可证；一方面 经验和直觉告诉人们数学是一致的不含矛盾的，理性又教导人们算术系统不能证 明它自身的一致性。因此，定理发现之后，人们不得不重新调整自己的思维方式。 著名数学家外尔( h w c y l ) 当时曾就此感慨到，“上帝是存在的，因为数学无疑 是一致的；魔鬼也是存在的，因为我们不能证明这种一致性。”这段话形象地道 出了当时处于两难境遇的数学家的困惑。甚至有人把哥德尔定理的意义进一步引 申：宇宙给了我们一种选择，就人类认知而言，我们要么拥有一本正确的但却是 极不完整的小书，要么拥有一本完整的但缺乏内在和谐的大书，我们可以选择完 整也可以选择和谐，但鱼和熊掌不可得兼。在我们看来，这些说法不过是哥德尔 定理带给人们的某些启示，事实上，哥德尔定理自图灵机概念诞生之后更加凸现 其深刻和意义深远。 3 0 年代，哥德尔、丘奇( a c h u r c h ) 、克林尼( g j k l e e r l e ) 、图灵等一批数 学家丌始对直观的“算法可计算”概念的数学刻画进行探索，相继提出了n 可定 义、递归函数和图灵机概念，并给出了影响广远的丘奇图灵论题：一切算法可 计算函数都是递归函数，一切算法可计算函数都是通用图灵机可计算的函数，或 1 9 者说，每个算法都可在一台通用图灵机上程序化。虽然几种数学刻画是等价的， 但是哥德尔最为赞赏图灵机概念，这其中最为重要的是，图灵机概念第一次澄清 了形式系统的真正内涵形式系统不过是一种产生定理的机械程序，或者说图 灵机的工作程序就是数学家在形式系统中进行工作的程序。有了图灵机概念以后 人们开始期望造出能证明所有数学定理的机器，但是，既然图灵机就等价于形式 系统，那么形式系统的局限就是图灵机的局限。于是，哥德尔的第一不完全性定 理在给出图灵机概念之后就有了如下几种等价说法： ( 1 ) 没有数学形式系统既是一致的又是完全的。 ( 2 ) 没有图灵机能够输出所有的数学真理。 ( 3 ) 数学是算法不可完全的。 ( 4 ) 数学是机器程序不可穷尽的。 ( 5 ) 停机定理没有任何图灵机程序能判定，任给一个程序p 和一套输入i ， 依照这套输入i 运行程序p 时，机器是否能停机。即停机问题是图灵算法不可解 的。由于任何数字计算机都是通用图灵机的特例，因此，停机定理表明，本质上， 计算机的能力是有限的。 1 9 8 5 年，切廷( g j c h a i t i n ) 在算法信息论一书中，给出了算法信息论中的 哥德尔式不可判定命题，并且给出哥德尔定理的算法信息论版本： ( 6 ) 对形式算术系统t 而言，可以找到一个数c t ，它是公理系统t 的信息熵， 即描述或处理这些公理所需要的最小信息量，如果k ( w ) 是字为w 的科尔莫葛 洛夫( a n k o l m o g o r o v ) 复杂性，则t 中切满足k ( w ) c t 的命题在t 中 不可证。 施瓦茨( s c h w a r z ) 曾就这些结果总结过颇具启发的三句话：“希尔伯特认为， 一切事物都是【算法】可知的：哥德尔认为有些事物不是【算法】可知的；切廷认为 只有少部分事物是【算法】可知的”。可见，哥德尔定理确实深刻地变革了我们对 于一致性、完全性、真理、可证性和可计算性之间关系的传统认识。 曾有人问哥德尔，能否把他的定理推广到数学以外。哥德尔尝试给出了一个 自己认为合理的表述：“一个完全不自由的社会( 即处处按统一法则行事的社会) ， 就其行为而言，或者是不一致的，或者是不完全的，即无力解决某些可能是极端 重要的问题，而当社会面临困境时，这种不一致或者不完全都会危机整个社会的 生存。”1 0 1 4 国内外对哥德尔的研究 哥德尔在2 0 世纪上半叶短短十年间( 1 9 2 9 1 9 3 9 ) 就使数理逻辑发生了根本 性变革，他的思想对逻辑学、数学、计算机科学、算法信息论、哲学和认知科学 都产生了深远影响。王浩( w a n gh a o ) 皙将他的工作同弗洛依德的心理学、爱因斯 坦的相对论、玻尔的互补性原理、海森堡的测不准原理、凯恩斯的经济学和d n a 双螺旋结构理论并称2 0 世纪人类思想史上的奠基性贡献。1 9 7 9 年一部美国畅销 书哥德尔艾舍尔巴赫g 6 d e l ，e s c h e r , b a c h ：a ne t e r n a lg o l d e nb r a i d 使逻辑领 域之外的人也对哥德尔发生了空前的兴趣，一时间，“不完全性”、“悖论”、“怪 圈 竟成了一大批科普读物和文学作品中的时髦语汇。人们向往了解哥德尔、更 深刻地理解哥德尔的思想，发掘哥德尔思想中潜在的科学价值。但不完全性定理 的数学外衣令大多数人望而却步，哥德尔的个性更笼罩着层层神秘色彩，而且哥 德尔一生著述甚少，大多数思想记录在手稿、通信和私人谈话中，因此，长期以 来，即使对大多数逻辑界人士来讲哥德尔也是一个难解的谜。直到1 9 8 1 年哥德 尔去世三年后，他的妻子将其遗稿全部捐赠美国普林斯顿研究院，哥德尔手稿中 的一部分内容才开始陆续公布，哥德尔思想巨大冰山的一角才开始慢慢显露，世 人才有可能逐渐更全面地了解哥德尔的生活和工作。于是8 0 年代后西方学界重 新对哥德尔倾注热情，一大批数学家、逻辑学和哲学家纷纷加盟研究行列，目前， 哥德尔研究已经成为具有极大挑战性和诱惑力的课题。 目前西方哥德尔研究虽已有相当成果，但除了王浩等少数工作以外，迄今为 止少有对哥德尔思想进行深刻剖析的整体性研究论著面世。而在中国逻辑学界， 哥德尔研究也一直是一个令人畏惧的艰深领域，即便在哥德尔文集陆续出版、 哥德尔手稿陆续公布的