（逻辑学专业论文）论哥德尔不完全性定理及其哲学意义.pdf

论哥德尔不完全性定理及其哲学意义 论哥德尔不完全性定理及其哲学意义 摘要：本文首先简要介绍了逻辑学家哥德尔的生平、不完全性定理的 梗概以及国内对此定理的研究情况，继而给出了不完全性定理的一个 简单的证明；最后结合哥德尔不完全性定理提出的背景、引起的争论、 在数学上的专门结论和影响以及哥德尔本人的某些哲学见解，详细阐 述了这一定理的哲学意义。 关键词：哥德尔不完全性定理形式系统哲学意义 o ng s d e l s i n c o m p l e t e n e s s t h e o r e m sa n dt h e i r p h i l o s o p h i c a l m e a n i n g s a b s t r a c t ：t h i sp a p e rf i r s t l yi n t r o d u c e sl o g i c i a ng s d e lb i o g r a p h i c a ln o t e s ， a na b s t r a c tf o r mo fi n c o m p l e t e n e s st h e o r e m sa n ds t u d ys i t u a t i o n so f t h e s et h e o r e m s i no u r c o u n t r y b e f o r ei t g r a n t s ab r i e f p r o o f o f i n c o m p l e t e n e s st h e o r e m s l a s t l yl i n k i n g t h e b a c k g r o u n d o f i n c o m p l e t e n e s s t h e o r e m st h a tg s d e l p u t f o r w a r d ，i s s u e s o n i n c o m p l e t e n e s st h e o r e m s ，i m p a c t sa n dc o n s e q u e n c e so fi n c o m p l e t e n e s s t h e o r e m si nm a t h e m a t i c sa n dm a t h e m a t i c a lp h i l o s o p h ya n dg s d e l s p h i l o s o p h i c a ls t a n d p o i n t s ，i te x p o u n d s d e t a i l e dp h i l o s o p h i c a lm e a n i n g so f i n c o m p l e t e n e s s t h e o r e m s k e y w o r d s ：g s d e l i n c o m p l e t e n e s s t h e o r e m s f o r m a ls y s t e m p h i l o s o p h i c a lm e a n i n g 2 论吁德尔4 i 完全性定理及其哲学意义 封二 图2 ：瀑布，毛里茨康奈利尔艾舍尔( 1 8 9 8 1 9 7 2 ) 作( 石板画，1 9 6 1 ) 。 转引自哥德尔艾舍尔巴赫集异璧之大成p 1 6 。 论哥德尔不完全性定理及其哲学意义 一导论 ( 一) 哥德尔生平 库尔特哥德尔( k u r tg s d e l ，1 9 0 6 4 ，2 8 1 9 7 8 1 1 4 ) 生于摩拉维亚的布尔诺 城，原属捷克，1 9 2 9 年加入奥地利国籍，后来在二战时移居美国。童年时候， 曾患轻度的焦虑性神经官能症及急性风湿热，这对他一生的生活和工作都有波 及，并且终生健康状况很差，厌恶旅行。从青少年时起就喜欢数学、物理、哲学 和神学。在1 9 2 6 年，经数学老师哈恩介绍加入维也纳小组的活动，他的见解却 与维也纳小组其他成员从来都不合，初读维特根斯坦的逻辑哲学论，深不以 为然。在晚年喜欢莱布尼茨和胡塞尔的著作，而不大喜欢康德的观点( 特别是数 学方面的观点) 。1 9 2 8 年在维也纳大学听了布劳维尔的演说以后，更加热爱数学。 受其启发，隐约知道数学不可穷尽。同年，希尔伯特在波伦亚发表演说，明确提 出数学系统本身的完全性与一致性问题，并把初等逻辑的完全性和可判定性作为 悬而未决的问题提出，1 9 3 0 年夏天，哥德尔证明了初等逻辑的完全性，并发现 了“算术真”与“可证性的”区别，得到不完全性定理的组合论形式，同时指出 了第二不完全性定理的证明思路。这是哥德尔2 4 岁的事情，从那时起，哥德尔 在数理逻辑学界引起广泛的注目。移居美国以后，他研究重点日益转向集合论以 及哲学方面，写了许多有关它们的文章来阐述自己的集合论以及哲学思想。1 9 7 8 年在美国逝世，在逻辑史上，许多人把他和亚里士多德以及莱布尼茨并列，推为 逻辑发展史上里程碑式的人物和不世出的天才。在某种意义上，哥德尔不完全性 定理在不同领域都有不严格然而十分有趣的对应物：在音乐上，是约塞巴赫 的赋格曲，在绘画方面，是艾舍尔的画作，而在小说领域，我认为是阿根廷作家 豪尔赫路易斯博尔赫兹的小说交叉小径的花园。因此，哥德尔的这个定 理不仅在数学或逻辑上意义重大，而且是一个十分有趣的“主题”。( 这方面，有 兴趣的读者可参见美国作家侯世达的哥德尔爱舍尔巴赫集异璧之大成 以及博尔赫兹的奇幻体小说交叉小径的花园，这里就不再进一步分析了) 。 ( 二) 不完全性定理简介 我们知道哥德尔关于一阶逻辑有一个完全性定理，它是说，一阶逻辑是完全 的，即经过预定语义解释的一阶逻辑真理都是本系统的可证公式。哥德尔不完全 性定理是说一阶形式算术不满足这个要求。它的严格表述是1 ： 定理1 ( 第一不完全性定理) 存在一个算术语句a ，a 和 a 在p a 中都不可证。 定理2 ( 第二不完全性定理) 如果p a 是一致的，那么p a 的一致性不能在p a 中证明。 4 论哥德尔叫；完全性定理发其哲学意义 定理1 有几个等价的表述： ( a ) 存在一个算术语句a ，a 在算术标准模型j 1 = 中为真，但 a 在p a 中不可证。 ( b ) 存在p a 的可数模型1 2 ，u 与j i 不是初等等价的。 ( c ) p a 的全体闭定理所组成的集合不是极大一致集。 定理2 是定理1 的推论，我们这里不详细讨论它，稍后，我们要详细地分析它。 现在，主要解释一下定理1 以及它的几个等价的表述。我们需要一点模型论的知 识。所谓模型，是相对一个形式语言而言的。假设我们的语言l = ，那么它的模型是一个四元序对：u = 。我们通常把某一模型取作标准模型，与此模型同构的模型都是 标准模型，而与此模型不同构的模型都是非标准模型。所谓同构，指的是两个模 型之间存在一个双射( 一一对应) 。这样看来，上面的定理1 和( a ) 的等价性是 显然的。对于( b ) ，它是说p a ( p e a n o s a r i t h m e t i c ) 存在一个不同于标准模型的 可数模型u ，对任意句子并非中p a ，j i 由当且仅当u 卜由，即他们所满足的 p a 的句子集不相同。对于( c ) ，它是说p a 的闭公式集中的定理集仍可扩充，设 p a 的闭定理集为t ，则对存在闭公式o ，p a 且并非巾t 则t u o ) 仍然 和谐，这就是说存在p a 无法判定的句子巾，并且。和 巾在p a 中都不可证。 因此，上面的几种说法是等价的。以下我们采取哥德尔原来的表述，纯粹是从技 术上的方便考虑。 对于任一个形式系统s 来说，按这个定理，在系统内构造不可判定命题的方 法是给定的，它依赖下面三个条件2 ： ( 1 ) 公理系统s 是真正形式的。 ( 2 ) s 足够丰富 ( 3 ) s 是一致的。 ( 1 ) 是说公理系统s 是本质上涉及变项的，所谓本质上涉及变项就是把常项看 作变项的一种代入，研究它的主目是变项的一般情况。公理系统和形式系统是有 很大区别的。以后我们可以看到s 是真正形式的这个条件对我们的目的来说是一 个必要条件。这个条件结合( 2 ) ，我们便能够在系统内部展开一个元数学命题。 ( 2 ) 具体的意思是说，s 丰富到足够展开一个适量的数论命题，如果s 没有如 此丰富，我们不可能够构造出一个具有元数学意味的命题。下面我们将看到，我 们必须把元语言的句子翻译成对象语言的句子。这是对对象语言表达力的要求。 ( 3 ) 的意思是假设性的，因为如果s 不一致，那么我们可以推出任意公式，我 们不会再费神去证明其完全性，那样的系统从它可以推出任意公式而言是平凡 的。 论哥德尔不完! ；! 性定理及其哲学意义 对于这三个条件，无疑是必要条件，但是如何才能表明它们也是充分条件， 我知之甚少，即就不完全性定理而言，是否只有一阶形式算术恰好才具有不完全 性? 由以上的讨论，我们现在来看定理2 它既可以看作定理1 的推论，又可以 看作定理1 的一个判据：p a 是一致的这个命题在系统内部可表达但无法在p a 内 予以证明。 ( 三) 本文的初衷及目的 在国内，大多数对哥德尔不完全性定理的研究不是很细致、彻底。张家龙先 生曾对不完全性定理作过评论3 ，但我对他是否从这个定理引出他的评论表示怀 疑，在我看来，他对其哲学意义的评论并非很切题。康宏逵对此定理也有零星的 评论，不过，他的话只是站在数学家( 逻辑学家) 的立场对哲学家表示愤慨的一 种声音，而且是对哲学的混乱状况抱着激进态度的一种声音。另外，郭世铭、叶 峰、和昂扬先生对此也有少量评论1 ，这些评论是在论述这个定理的证明时自然 而然阐发的，较少哲学意味。刘晓力教授以哥德尔工作的全面研究为目的的书出 版了5 ，也许只是复述了王浩的某些见解而非发挥、推广、深化它们。我要承认， 评价哥德尔又要绕过王浩的意见非常难，即使在国外他也是这方面的权威人物。 想要评价哥德尔全部的工作就更是如此。而王浩本人对不完全性定理的评论被淹 没在对哥德尔哲学观点发挥的烟雾之中。国外的情况，我不太清楚怎样，感觉是 关于哥德尔不完全性定理专门数学方面以及人工智能和技术学的研究较多，强调 其数学的一面，而忽略了其哲学的一面。最近一本介绍哥德尔生平的传记逻辑 人生也是如此。这大概因为哥德尔历来被人当作科学家而非哲学家。近年来， 由于哥德尔的一些哲学思想渐为人所知，情况才有所改变。 和他们相比，我想仅仅就不完全性定理谈一谈我的看法，而不想对哥德尔 全部的工作予以评价，这既是专业所限又超出我的能力。不过，即使为了这个目 的，也要把这一定理放在哥德尔本人以及他那个时代的学术氛围和背景下考虑。 如果我在技术上有某些不足之处，请读者原谅并指出来，以期改正。虽然如此， 我还是期望这些不足之处能由后面关于不完全性定理的哲学分析所补救。 对哥德尔的研究通常被认为是数理逻辑学家的事情，和哲学能够联系起来 的成果相对稀少。一方面，是由于他本人的哲学见解“并未达到可以系统阐述的 地步”( 王浩语) ；另一方面，人们往往把哲学意蕴和专门数学推论与影响混淆在 一起。我之所以认为不完全性定理在数学方面的推论不同于其哲学意义，是因为 数学方面的解释更为严格和精确，而哲学方面的意义相对较为广泛、自由，就表 达来说也是后者的方式更自由。 在这篇文章中，我严格区分了两个方面，( 一) 哥德尔本人的哲学见解与他 论哥德尔不完全性定理及其哲学意义 工作的哲学意义的区别和联系；在何种意义上，我们可以说他的见解只发挥了他 所谓的“科学助探器”的作用；在何种意义上，可以说是他的哲学见解只是他工 作的一个广义后承和外推；( 二) 不完全性定理的专门数学推论和影响以及其哲 学意蕴的区别与联系。这两方面都十分困难，一定意义上，我们必须冒犯错误的 风险。 我始终认为对科学的评价是哲学分内之事，并不仅仅是科学家和专门历史学 家的义务。这可能和专业畸变6 有关吧。哲学和各门科学的关系并不像从前那样 紧密了，但是由于哲学的题材极其广泛，它和科学的理论部分仍然有相通之处， 就像我将要指出的那样，正是每一门科学都发展了一门自己的元科学，并把这种 元科学也包括在科学这个一般概念中，才造成了哲学和科学的对立，以至科学一 度( 甚至相当长的时间内) 使哲学大受冷落。 在本文中我将采取朴素实在论的立场，这也是一种“元立场”，这纯粹是为 了叙述的方便。这不能解释为我对于哥德尔或其他人的实在论有完全或部分的同 意。 至于哥德尔不完全性定理的证明，7 0 多年过去了，后人并未找到本质上与原 来证明方法不同的证明。中文的证明也是如此。莫斯托夫斯基和奎因利用塔尔斯 基定理所作的证明7 ，在我看来最为简单、易懂，涉及的技术性的工作较少。下 面我大致上就采取这个形式来证明。对我们来说，理解不完全性定理的意义也许 更加重要，不过，定理证明的某些细节也许会有助于我们的这种理解。 二哥德尔不完全性定理 哥德尔在1 9 3 1 年把他的证明和“说谎者悖论”联系起来，即把一个古老的 哲学悖论转化为数学上的说法，为简便和便于理解起见，我们先来看哥德尔不完 全性定理的一个抽象形式 ( 一) 哥德尔定理的抽象形式 对于每个可应用哥德尔论证的形式语言l ，应至少包括如下内容： 1 令e 为语言l 的表达式的可数的集合，其中e 的元素都是l 中合式的表 达式。 2 令s 为语言l 的句子的集合，s 的元素是l 中的句子且s 是e 的子集。 3 令p 为l 中可证句子的集合，p 的元素是l 中的可证句子且p 是s 的子集。 4 令r 为l 中的可驳句子的集合，r 的元素是l 中可驳句子且r 是s 的子集。 5 令h 为l 中的谓词的集合，h 的元素是l 中的谓词。 6 令t 为l 中真句子的集合，t 的元素是l 中的真句子。 7 对每一个表达式e 和每一个自然数n ，一个函数由给它们指派一个 表达式e ( n ) 。函数需要受下例条件的约束：对于任何一个谓词h 和自然数n ， 论哥德尔小完全性定理及其哲学意义 表达h ( n ) 是一个句子。我们这里应用了塔尔斯基的真句子的概念，我们以后 就会发现真与可证的定义明显不同 现在，我们来说一下在l 中可表达意昧着什么。在l 中可表达性这个概念涉 及到真句子集t ，而和p 以及r 无关。下面我们提到的“数”都是指“自然数”。 我们说一个谓词h 对n 是真的或者说n 满足h 当且仅当h ( n ) 是一个真句子( 或 者说h ( n ) 是集合t 的一个元素) 。一个表达h 的集合意指，对于这个集合的所 有数r l ，n 满足h 。因此，对任意数集a ，h 表达集合a 当且仅当对每一个n a ， h ( n ) t n a 。下面我们再引入几个我们后面证明需要的定义： 定义l 。一个形式系统是正确的，如果它的每个可证句子是真的，而每个可 驳句子是假的。 这就说明p 是t 的子集，我们现在对一个足够丰富的形式系统l 来考虑：如 果l 是正确的，则l 中存在一个不能证明的真句子。 定义2 一个集合a 可称之为在l 中可表达的，如果a 确实被l 中某些谓词 所表达( 见上文关于“在l 中可表达的”说明) 。 关于这个定义的说明：既然在l 中仅仅存在可数多个表达，那么l 中就仅仅 存在有限或可数多个谓词，但是由康托尔定理，我们知道，存在不可数多个自然 数的集合，因此，并非每个自然数的集合都能在l 中表达。 定义3 哥德尔数我们称下列指派为哥德尔数字化：我们让g 为双射函数， 它指派给表达式e 一个自然数g ( e ) ，g ( e ) 称之e 的为哥德尔数。通过这个方 程g ( e ) ，我们把元数学的句子翻译成系统里的句子，为了技术上的方便，我们 总假设每个数都是一个表达式的哥德尔数，现在，每个数n 对应唯一的一个表达 式，即表达式的哥德尔数是唯一的。我们用e n 来表达哥德尔数是n 的一个表达 式，因此，我们有g ( e n ) = n 。 定义4 对角化表达e n ( n ) 称之为e n 的对角化。如果e n 是一个谓词，那 么它的对角化将是一个句子，这个句子是真的当且仅当谓词e n 被它自己的歌德 尔数所满足。对任意n ，我们用d ( n ) 来表示e n 的哥德尔数，d ( n ) 称之为我 们系统的对角化方程。如果集合”是满足如下条件的集合：对任何自然数集合a ， 对任意数n ，当且仅当d ( n ) a 则n a + ，因此，下式成立 n a + h d ( r 1 ) a( 由定义可知) 有了以上的定义和准备，我们可得到哥德尔不完全性定理的一个抽象形式。 我们让p 是可证句子的哥德尔数的集合，对任意自然数集合a ，令a 为a 的补集， 那么我们将能够证明：如果集合，+ 是可表达的并且l 是正确的，那么存在l 的一 个真句子，这个句子在l 中不可证明( 这里我们用，表示p 的补集) 。 我们证明这个命题如下：假设l 是正确的，9 + 是在l 中可表达的，用h 表示 论哥德尔不完全性定理发其哲学意义 在l 中表达，+ 的一个谓词，用h 表示h 的哥德尔数，用g 表示h 的对角化( 例如 句子h ( h ) ) 。我们由h 在l 中表达y + 知，对任意数n ，h ( n ) 是真的当且仅当n ，+ ，既然这个式子对所有数都成立，那么它对一个特别的数h 也成立，因此我 们以h 代n ( 这称之为对角化论证) 。；而且我们有等价式：h ( h ) 是真的一h 9 + 那么 h 9 + 一d ( h ) ，”1d ( h ) y 但是d ( h ) 是h ( h ) 的哥德尔数， y h ( h ) 在l 中可证，并且1d ( h ) 有等价式： ( 因为h 是h 的哥德尔数) ：因此d ( h ) y h ( h ) 在l 中不可证；那么我们 h ( h ) 是真的一h ( h ) 在l 中不可证。 这就意味着h ( h ) 是真的且在l 中不可证或者h ( h ) 是假的且在l 中可证， 由l 是正确的系统可知，后一析取支是假的，所以我们就证明了h ( h ) 是真的 且在l 中不可证。 其实我们这旱省略了几个条件，这些条件是： l 对于任何可在l 中表达的集合a ，那么”在l 中也是可表达的。 2 对于任何可在l 中表达的集合a ，集合a 在l 中也是可表达的。 3 集合p 在l 中是可表达的。 我们能够显示，这些条件是满足的。这样我们就证明了在l 中存在真且不可 证的句子。这是不完全性定理的一个抽象形式，它的证明用到了塔尔斯基的真的 概念，康托尔的对角化思想。下面，我们按这个思路给出这个定理具体证明。 ( 二) 不完全性定理的证明 1 形式算术( p e a n o sa r i t h m e t i c ) 我们用以下形式化公理来表述一阶形式算术： ( 1 ) 逻辑公理( 模式) a la - b - a a 2 ( a b c ) 一( a b ) 一( a c ) a 3 ( 1a b ) 一( a 一 b ) 一a a 4v x a a ( x t ) ( t 为任意项) a 5a v x a ( x 不在a 中自由出现) a 6v x ( a ，b ) - v x a ，v x b a 7t ：t ( t 为任意项) a 8s = t s ( s ) = s ( t ) ( 8 ，t 是任意项，s 为后继函数) a 9s ：8 一t = t 一s = t s = t ( s 、t 、s 、t 为任意项) a io8 ：s 一t = t 一s + t = s + t 论哥德尔h i 完全性定理及其哲学意义 a 1 18 ：s 一t = t 一s t = s t 分离规则( m p ) 由a 和a b 得到b v 概括规则 a v x a 算术公理( 模式) p a l0 s ( x ) p a 2s ( x ) = s ( y ) 一x = y p a 3x + o = x p a 4x + s ( y ) = s ( x + y ) p a 5x 0 = 0 p a 6x s ( y ) = x y + x p a ta ( 0 ，x l ，x n ) 八( v x a ( x ，x l ，x n ) - - a ( s ( x ) ，x l ，x n ) ) 一v x a ( x ，x 1 ，x n ) 2 几个定义 定义1 公式的复杂度( d e g r e e ，简称为度) 原子公式的度为零 任意a ，b ，若他们的度分别为d 1 、d 2 ，则1a 的度为d l + l ，公式a b 的度为d l + d 2 + l 对任意变元x ，v x a 的度为d 1 + 1 。 定义2 序列对任意b 2 ，我们定义函数x ( d b y 是以b 为基的序列，且 x ( d b y = x b ”+ y ，其中n = l ( y ) = 十进制数y 的长度。 我们能够表明对任意b 2 ，关系x ( d b y = z 是算术可表达的。( 我们用“+ ”和“” 定义幂运算) 定义3 算术集合和关系对任意公式f ( x 1 ) ( 仅有x 1 在f 中自由出现) ，我们说 f ( x 1 ) 表达了集合a 当且仅当对所有的数n ， f ( n ) 是真的一n a ( 我们就用通常的自然数n 来表示n ，例如，4 - 0 7 7 ) 。 我们说f ( x l ，x n ) 表达了n 元组( k l ，k n ) 的集合，当且仅当 f ( k l ，k n ) 是真的一r ( k l ，k n ) 说明：这里的算术系统假定已经定义了幂运算 x o b y o b z 是左结合的，即x o b y o b z = ( x o b y ) o b z 。 我们能表明x l ( d b x 2 ( d b ( d b x n = y 是算术可表达的。 3 哥德尔数字化 我们知道算术句子谈论的只是数，不是表达式，通过给每个表达式分配一个 哥德尔数，我们就能够间接地谈论表达式了。在这罩我们用奎因改进的方法来进 论卧德尔小完全性定理及其哲学意义 行哥德尔数字化。奎因用s l ，s 2 ，s 9 来使他的语言公式化，然后对复杂表 达s i l ，s i 2 ，s i n 指派i l ，i 2 ，i n 他们的哥德尔数( 如$ 2 s 3 s 1 指派数 字2 3 1 ) 。我们用这个方法来进行哥德尔数字化，用1 3 进制的数来取代l o 进制 的数，因为我们所用的语言有1 3 种不同的符号，这样也是为了技术上的便利。 取“n ”、“e ”、“6 ”表示1 3 进制的数1 0 、1 1 、1 2 ，我们可以给我们系统 的13 种符号配上以下哥德尔数： 0 ( ) f v1 一v = # l023456789n6 在任意符号串中，我们用每个符号相应的1 3 进制数字来表示，例如第4 个、第 6 个、第7 个前后相接的符号串，它的歌德尔数是4 6 7 = 4 13 2 + 6 - 1 3 + 7 。对任意 n 0 ，我们用e n 表示其歌德尔数是n 的表达式。这样，对于”的任意串，它 的歌德尔数为o 。我们定义e o 为“7 ”，我们用表达式意指这1 3 个符号的任意 串，并且这1 3 个符号的任意串不会以“”开始，除非出现“”紧跟着“ 的情况。 对任意表达式e x 和e y ，e x e y 表示e x 后紧跟着e y 所组成的符号串。根据哥 德尔数字化的规则，其哥德尔数为x 0 1 3 y 。我们之所以选择“0 ”作为“7 ”的 哥德尔数是因为：对任意数n ( 它的表示也是n ) ，有一个哥德尔数，我们考虑到 对n 的数字化是n 的一个算术方程，亦即数n 的表示n 由“0 ”和“7 ”组成； 例如，3 = 0 7 ，显然，它的哥德尔数是1 3 3 ，一般情况我们有：n 的表示= 1 3 n 0 4 塔尔斯基定理 ( 1 ) 对角化和哥德尔句子 如果我们用t 表示p a 的真句子的集合，这个集合t 能够用自然数的集合良好地 定义，但它不是算术的，亦即真句子的集合t 是算术不可表达的，这就是塔尔斯 基定理。 从这个定理出发，我们立刻有：对任意数集a ，存在一个它的哥德尔句子。 证明如下：h ( n ) 是真的一n 舻，则h ( h ) 是真的一h 舻，则h 舻一d ( h ) a ，因此，h ( h ) 是真的一d ( h ) a ，故有a 存在一个哥德尔句子并且d ( h ) 是它的哥德尔数( 这个句子就是h ( h ) ) 。 5 公理系统的算术化 我们现在来证明可证公式的哥德尔数的集合是算术可表达的集合。 ( 1 ) 准备( 几个定义) x b b y , - + x = y v ( x 0 a ( | z y ) ( j w y ) ( p o w b ( w ) 八( x w ) g b z = y ) ( x 开始y ) 论哥德尔小完全性定理发其哲学意义 p o w b ( x ) 一j n ( x = b “) ( 9x e b y x = y v ( jz y ) ( z o b x = y ) ( x 结束y ) x p b y 一( jz y ) ( z e b y a x p b z ) ( x 是y 的部分) x l o b x 2 0 b o b x n p b y * - ( 刍z y ) ( x l o b o b x n = z 八z p b y ) 由以上等价式可知：上述关系都是算术可表达的。我们把- ix p b y 表示成x - p b y ， 而x 1x 2 x n p b y 用x 1 0 1 3 x 2 0 1 3 x n p y 表示。把j x ( ( x y ) 八( 一一) ) 缩写 成 ( | x y ) ( ) 而把v x ( ( x y ) 一( 一) ) 缩写成( v x y ) ( - - - ) ( 2 ) 有限序列的定义 我们用“ f ”表示其它1 2 个符号形成的表达序列，n 元组( x l 。x 2 ，x r ) 的形式对应物为# x l # x 2 = i # x n # ，它的哥德尔数称为一个序列数。我们让 k 1 1 表示数n 的集合，而且在n 中6 不出现，那么所有在其中不出现“# ”的符 号的表达在k 11 中都有一个它的哥德尔数( 包括变元、数字表示项和公式，这些 所谓“有意义的表达式”) 。对k 1 1 中任意有限数字串( a l ，a 2 ，a n ) ，我们 指派6a l 6a 26 ，6a n6 为序列( a 1 ，a 2 ，a n ) 的序列数。我们称x 是一 个序列数，如果x 是k 11 中任意元素序列的序列数。我们用s e q ( x ) 柬表示x 是一个序列数。用“x y ”表示“x 是某个序列的序列数的成员，并且这个序列 的序列数为y ”( 例如，对任意k 1 1 中的变元x 1 ，x 2 ，x n ，如果y = 6x l 6 x 26 6x n6 ，那么x y 当且仅当x = x l 或者x = x 2 或者x = x n ) 。用“x y z ”表示如下关系：x ，y 是一个序列的序列数的成员，并且x 在这个序列中的第 一次出现比y 在这个序列中的出现早，z 为这个序列的序列数。”这样我们有下 列结果： s e q ( x ) 、x y ，x y z 是算术可表达的。因为 s e q ( x ) h 6b x 八6e x 八6 x 八- 16 6p x 八( v y 一x ) ( 6 o y p x 一6b y ) x 是以6 开始，以6 结束，并且6 x 弗且56 不是x 的一部分并且对任意y x 如果出现60 y 开始x 的情况，我们就让6 开始y ，也就是说“”符号是左结合 的。 x y h s e q ( y ) 八6x 6p y 八 6p x y 是某一序列的序列数，并且6 x6 是y 的一部分，并且6 不是x 的一部分。 x y z + 斗x z 八y z ( 王w z ) ( w b z 八x w 八- 3y w ) x z ，并且y z ，并且存在w z 使得w 开始z ，x z 和并非y z 。 ( 3 ) 形式化序列 类似地，我们有以下定义： r t ( x ，y ，z ) 当且仅当z = x y 或z = x + y 或z = x7 或z - x e y ( x 的y 次幂) 1 2 论哥德尔币完全性定理及其哲学意义 r f ( x ，y ，z ) 当且仅当z _ 1x 或z = x y 或z = v v i x 那么对于，我们定义：对于某一序列的一个成员x i ，我们用形式化关系来表 示x i 是一个变元或是一个数字表示或是一个较早的成员x j ，x k 使得r t ( x j ， x k ，x i ) 成立。这样我们就详细定义了x 是一个项当且仅当存在项的形式化序 列，x 是这个项的序列的一个成员。对于公式我们也有类似的定义：序列x 1 ， x 2 ，x n 为一个公式的形式化序列，如果对任意i n ，x 是一个原子公式或 存在j ，k ( j ，k i ) 使得r f ( x j ，x k ，x i ) 成立，那么表达x 是一个公式当且 仅当存在公式的形式化序列，在这些公式序列中x 是一个成员。 ( 4 ) p a 句法的算术化 在上面我们曾用“e x ”表示一个哥德尔数为x 的表达。对于任意序列e x l ，e x 2 ， e x n ，其中x 1 ，x 2 ，x n 在k 1 l 这个集合中，我们用( e x l ，e x 2 ，e x n ) 的哥德尔数来表示数字序列( x l ，x 2 ，x n ) 的序列数( 它也是“# e x l 耙x 2 # ，# e x n f ”的哥德尔数) 。我们用p e ( x ) 表示e ( x ) 是p a 的可证公式， 用r e ( x ) 表示e ( x ) 是p a 的可驳公式，这两个谓词都是算术可表达的。 对于任何数x ，y 我们把e x e y ，- 3e x ，ex + e y ，ex e y ，e x ey ，e x e e y ( 表示幂关系) ex 以及e x = e y 的哥德尔数分别写成x y ，- 1x ，x + y ， x y ，x y ，x 。y ( 注释：这表示x 的y 次幂) ，s ( x ) ，x = y 。当然我们可以用 s ( x ) 定义出“+ ”、“”后，再定义出幂关系。这样它们就都是算术可表达 的( 例如，( x y ) 可写成2 x s y 3 ) 。下面列出的条件也是算术可表达的： s b ( x ) e x 是一个符号串的子串 ( v y x ) ( y p x 一5 p y ) “5 ”是“，”的哥德尔数，我们用它作为v 的下标。 v a r ( x ) e x 是一个变元 ( | y x ) ( s b ( y ) 八x = 2 6 y 3 ) n u m ( x ) e x 是一个数字的数字表示 p o w l 3 ( x ) 即x 的数字表示等于1 3 的x 次幂。 刚( x ，y ，z ) 关系r t ( e x ，e y ，e z ) 成立 z = x + y v z - - x y v z = s ( x ) v z - - x o y s e q t ( x ) e x 是项的形式化序列 s e q ( x ) 八( v y ex ) ( v a r ( y ) v ( n u m ( y ) v ( | z ，w y x ) r 1 ( z ，w ，y ) ) t m ( x ) e x 是一个项 j y ( s e q ( y ) 八x y ) f 0 ( ) e x 是原子公式 论哥德尔小完全性定理及其哲学意义 ( 习y x ) ( | z x ) ( t i n ( y ) 八t m ( z ) 八( x = - - ( y = z ) v x = ( y z ) ) ) g e n ( x ，y ) 对某些变元w ，e t = v w e x ( j z y ) ( v a r ( z ) 八y = g z x ) r 2 ( x ，y ，z ) r f ( e x ，e y ，e z ) 成立 z - - - - ( x v ) v z = - - ix v g e n ( x ，z ) s e q f ( x ) e x 是一个公式的形式化序列 s e q ( x ) ( v y x ) ( f 0 ( y ) v ( jz ，w y x ) r 2 ( z ，w ，y ) ) f m ( x ) e x 是一个公式 j v ( s e ( y ) x y ) a ( x ) e x 是p a 的一个公理( 我们以a 1 为例，其余类似可得) ( 丑y x ) ( j z x ) ( 竹_ n ( y ) 八f m ( z ) x = ( y 一( z y ) ) ) m p ( x ，y ，z ) e z 是e x 和e y 经过分离规则得到的。 y 2 一z d e r ( x ，y ，z ) e z 是由分离规则得到或者由v 一概括规则得到的。 m p ( x ，y ，z ) v g e r l ( x ，z ) p f ( x ) e x 是p a 的一个证明 s e q ( x ) 八( v y x ) ( a ( y ) v ( jz ，w a 的所有后承集) 。 这就不难解释，为何就一阶逻辑来说，维特根斯坦也抱类似的观点。我们为了形 式而牺牲了内容，这算是我们所付出的代价吧。 f 是“真”与可证的平凡区分导致了不完全性定理以及塔尔斯基定理。促进 了形式语义学方面的研究。这似乎也论证了“真理与可证与否”关系不如人们想 象的那样密切，即真理不依赖我们对他们的认识而存在。我相信正是这个结论使 哥德尔坚定了他的柏拉图主义的立场。至于他在此以前是否也抱有类似的观点， 我知道的不多。从他所浣某种哲学观点可以作为科学研究的助探器来看，也许他 丌始就相信柏拉图主义是似真的，有了这样判据以后，他的这种立场变得“强硬” 起来。 ( 二) 实在论 本节开首提到过，自柏拉图以来，在数学家、逻辑学家中间抱有柏拉图主义 的人已经不多了。在哲学上，柏拉图主义依旧有影响。有趣的是，在哲学家中间， 大家都小心谨慎地回避着形而上学问题，在数学家、逻辑学家那里( 特别是在数 学哲学领域) ，人们的注意力却开始向形而上学方面倾斜。哲学家似乎能够指出 每一个学说、信念的可疑和不足之处，因而缺乏勇气和理由相信某种学说。一方 面他们用认识论、方法论、语言分析来搪塞，一方面他们把形而上学问题当作无 意义的问题抛弃掉。他们满足于在各种理论之间安静地摇摆，总之，怀疑论蔚然 成风。而对于另外一些人，由于他们实际工作的缘故，他们自然而然地走进了哲 学。这样的例子很多，比如，爱因斯坦、哥德尔等等。由于长久地探求他们工作 的本性、意义，他们已经参与了哲学家的工作。 哥德尔本人的见解有多少是他工作的“后承”，多少是他自己信念的产物， 并不十分清楚。王浩说他是“在数学上客观主义或概念实在主义”，这个观点包 括以下两点：其一排中律对真理概念有效。其二数学客体类、函数、概念存在。 应该说他的这个观点在现代学者身上很少见。对于排中律的极度信赖已经由布劳 维尔所破坏，如果原则上没有一个方法显示或直接给出的证明，对一个命题无法 说真或假。实在论则争辩说，目前不能判定不等于永远不能判定，不能判定也不 论哥德尔不完全性定理及其哲学意义 等于没有真值。构造主义( 直觉主义的一个真部分) 则认为我们只能承认已经被 构造的东西，哥德尔提出一个判据说，在数学证明及其结论问题上的意见相同能 够显示数沦的客观性，当然，如果我们承认了这一点，那么看来我们也要承认数 学客体的客观性。在这一点上，哥德尔求助于直觉，把对数学客体的直觉和物理 的知觉相比较，只是给予一个较低的确实度罢了。他只在构造主义能增强结论的 显然性上彳承认构造主义。 如果我们承认哥德尔是对的，那么关于这些客体性质的争论即使不会使客观 性本身荡然无存，至少也构成了对它的一个否定判据。并且还可以指出一点，用 数论来说明客观主义的正确性是不恰当的。因为数论之所以被人接受据说靠的就 是客观性，这无疑是循环论证。实在论有它无法克服的困难。而构造主义的困境 在上文我已经提到过( 见本文第1 8 页) 。 王浩指出哥德尔的实在主义超出了数学的范围。它甚至认为人类具有和这种 直觉相对应的肉体器官。这一点他依靠的也是直觉( 关于这一点如何是真的，并 无任何可信的证明) 。我认为，是时间的相继，才把人思维的高阶性显露出来( 这 里所谓的高阶性是指，反思的无穷性) 。在物理上极短的时间内，人停留在条件 反射和动物的直接性上，只有反思、只有有时闽反思，人才把自己的生命活动与 生命本身分开，时间开始转动了，对象化也开始了，而我们的知识不过是这种对 象化的结果罢了。这种区分纯粹是对时间的体会，我们对今天之领会就是我们对 今天以前所有日子的领会( 试比较集合论中n = 0 ，1 ，n 一1 ) 这种表达的含义吧) 。 这种体会仅仅是在我们体会它的意义上才和生命有关，因而这种体会对我们也许 并无好处，我们把生命本身对象化为生命活动并研究它们，我们自身就分裂成一 个两重东西的综合物。这一点可以看作我们精神开始分裂不管是理论的还是 实际的这种分裂的先兆。 哥德尔希望他的工作能自然地引到这个结论，又想说明这个结论是超出他的 工作，因而独立于他的工作。尽管他举了很多例子，但是这和上帝存在的证明一 样，只使愿意相信的人信服了，并没有使不愿相信的人信服。他并没有在哲学中 找到他需要的东西，他老是说，“作为精密理论的哲学”是可能的，可是我们目 前并不知道一点可能的暗示。 哥德尔真诚地相信存在与物质分离的心、来世、上帝。像亚罩士多德那样雄 心勃勃地列举了一些概念试图构造公理化的哲学，我不知道这种规范或者规训哲 学的努力是否有重大意义，但是我觉得分明做不到。对于哪些概念才是基本概念， 我们没有统一的意见。其次，用少数有限概念就能够把生活公理化，即哲学能够 被有限公理化吗? 且不说这个构想的还原论色彩。第三，即使以上这些都做到了， 我们的公理理论刻画的是不是我们的实在世界，如果我们刻画的是所有可能的世 论异j _ 德尔小完争性定】= ! ! 及其哲学意义 界，那么我们将无法挑出我们所在的这个世界，因为，任何可能的区分在我们构 造公理理论时已经考虑到了。那么我们所构造的理论的价值何在? 柏拉图主义为人所反驳是它的超验性，在那里，人的直觉之烛只发出暗淡的 微光，可靠性要求它给出更加令人信服的证据，来说明自己( 直觉) 是似真的。 哥德尔的这个立场既是他工作的后承( 我们上文作过说明，不完全性的证明是如 何导致实在论的) ，又是他信念的结果。 除此，不完全性定理还和另外一些有趣的问题相联系，我们这就转向它们。 ( 三) 人心与机器的问题 哥德尔不完全性定理由于涉及到形式化和公理化，证明了形式系统的概念不 能捕捉住公理系统直观的真理的概念，加之图灵的工作，使这一定理更明显地和 某种机械主义以及技术学( 主要是计算机和人工智能) 相联系起来。 机械主义初期大多指幼稚的唯物主义，但这个概念的另一个含义是“可计算 的”或“递归的”。这个定理和计算机方面联系起来的正是“判定问题”、“机械 地可核查程序”以及计算的复杂性问题。例如，希尔伯特第十问题，有没有机 械程序来判定任意给定刁番图( d i o p h a n t u s ) 方程是否有解。通过递归论的研究， 哥德尔不完全性定理就和图灵机停机问题，以及机械计算性的概念、刁番图方程 解的问题联系起来了。就计算的复杂性而言，哥德尔定理表明，存在具有高度复 杂性的、不能由计算机程序生成的数：就计算机程序而占，哥德尔定理说，存在 一个计算机程序p ，使得：如果p 是一个f 确程序，那么在应用p 时，p 产生一 个被p 遗漏的真理；就刁番图方程解的问题而言，哥德尔定理宣布，存在一个没 有解的刁番图方程，但是没有数学理论能够证明这一点；根据蔡汀基于复杂性的 关于随机数的定义( 如果计算一个数最短程序的长度不比这个数本身短，那么这 个数就是随机的( r a n d o m ) 。) ，因此哥德尔定理的另一种说法是，存在一个不可 计算的数，它的二进制对应于无穷多个能行随机的算术事实，换句话来说就是， 存在无穷多个带有确切答案的算术问题，不能利用任何公理化形式系统找到它们 的解，它们不可能对应于任何形式系统的定理。而图灵停机问题是不完全性定理 的另一个等价表述：对于任何判定所有图灵机程序是否停机的图灵机程序p ，都 存在一个程序p 和输入数据d ，使p 不能判定处理数据d 时，p 是否会停机。 哥德尔根据艾尔布朗建议引进的一般递归函数的概念，后来证明它就是图灵 可计算函数类的概念。相对于这个概念，哥德尔不完全性定理就获得了它的广阔 的应用范围。对于每一个这样的系统而言，能够表明判定问题不可解。不完全性 定理就是说存在系统不能判定的问题。不过，他并没有说某个命题是绝对不可判 定的，这涉及到我们所接受的判定方法、判定的理论复杂度以及实践上的复杂度。 这一点清楚了，我们就不再把精力浪费在寻找一般的判定程序上。这个定理对我 论哥德尔不完全性定理及其哲学意义 们工作和研究都具有指导意义。 完全形式系统的方法是方法的“纯粹性”理想的完满体现。一个完全的系统 对其中的定理有一个可以用机械核查的证明。哥德尔不完全性定理说，丰富达到 初等数论的形式系统以后，这个方法便不是纯粹的。一般我们认为，完全的演绎 系统是表达力和演绎力相当的系统，演绎并不推出“理论上的新东西，而仅仅是 心理上的新东西”“。保真原则要求在结论不能强于前提，用一句通俗的话来说 就是，一个体重i 0 0 斤的女人不可能生出2 0 0 斤的孩子来。如果表达力超出了演 绎力的要求，就会产生不可判定命题。 这个定理本身并不蕴涵人心胜过机器这个结论。人心能够是非递归的程序 吗? 这个问题直接决定人心是否胜过机器。哥德尔认为加上两个假设便可证明人