正确理解哥德尔不完全性定理-

1、第11卷第2期2008年3月 湖南科技大学学报(社会科学版Journal of Hunan University of Science&Technology(Social Science EditionMar.2008逻辑今探正确理解哥德尔不完全性定理陈慕泽(中国人民大学哲学系,北京100872摘 要:借澄清对哥德尔不完全性定理若干误解的机会,以直观与简明的方式阐述哥德尔不完全定理的内容、意义及哥德尔的相关工作。哥德尔不完全性定理包括两个内容:第一,一个不弱于初等数论的形式系统,如果一致,则不完全;第二,这样的形式系统如果一致,则这种一致性在系统内不可证。关键词:哥德尔不完全性定理;不

2、可判定公式;可证;真中图分类号:B813 文献标识码:A 文章编号:1672-7835(200802-0027-04安徽大学学报 2006年第5期刊登了温邦彦的文章 禁止使用自指代命题 ,指出并论证哥德尔不完全性定理证明中存在严重逻辑问题。这一结论及其论证都是不成立的。本文借澄清对哥德尔不完全性定理若干误解的机会,以直观与简明的方式阐述哥德尔不完全定理的内容、意义及哥德尔的相关工作,以期一般读者对这一与 相对论 齐名的逻辑学杰出成果有所了解。哥德尔是20世纪最伟大的数学家和逻辑学家。在逻辑学中的地位,一般都将他与亚里士多德和莱布尼兹相比;在数学中的地位,爱因斯坦把哥德尔的贡献与他本人对物理学的

3、贡献相提并论。1952年6月美国哈佛大学授予哥德尔荣誉理学学位时,称他为 20世纪最有意义的数学真理的发现者 。在哥德尔所发现的被称为 20世纪最有意义的数学真理 当中,最杰出、最具有代表性、最有震撼力的是哥德尔不完全性定理。哥德尔不完全性定理包括两个内容:第一,一个不弱于初等数论的形式系统,如果一致,则不完全;第二,这样的形式系统如果一致,则这种一致性在系统内不可证。上述内容可以较为直观地解释如下。所谓初等数论形式系统,是指用形式化方法构造的算术公理系统。初等数论形式系统,(简称算术系统有三个层面:语法、语义和元理论(称为元数学。语法指算术系统自身的构造。算术系统由为数不多的一些符号及规则构

4、成。在算术系统内部,符号仅仅是符号;公式(包括公理仅仅是合乎规则的符号串;证明仅仅是合乎规则的公式序列。它们都没有涵义。语义指算术系统的解释。经过语义解释后,算术系统中的符号有了涵义,(闭公式成了有内容的算术命题,何谓一个公式真有了确定的标准。算术系统是一致的,是指不存在公式A,A和A(A的否定都可证。算术系统是完全的,是指不存在公式A,A和A都不可证。理解哥德尔不完全性定理,首先要弄清楚算术系统的两个基本概念,一个是 可证 ,另一个是 真 。可证是语法概念。一个公式可证,是指存在它的一个证明,即存在以该公式结尾的一个公式序列,其中每个公式或者是公理,或者是依据规则得到的。判定一个公式是否可证

5、,不涉及任何涵义,例如不涉及该公式经解释后具有什么内容。真是个语义概念。一个公式真,形式地说,是指它经过语义解释后确定为真;直观地说,是指它表达算术真理。因此,一个公式可证与该公式真,不直接相关,更不能直接画等号。收稿日期:2007-11-03作者简介:陈慕泽(1951-,男,上海人,教授,博士生导师,主要从事逻辑研究。当然,数学家的理想目标是:算术系统的可证公式,不多不少,正好等于算术真公式 。所谓不多,是指系统满足可靠性,即可证公式表达算术真理;所谓不少,是指系统满足完全性,即表达算术真理的公式在系统中一定可证。哥德尔不完全性定理的第一个内容恰恰是:这样的系统如果一致,则不满足完全性,即并

6、非任一算术真公式在系统中都可证。哥德尔在系统内构造了一个(闭公式U,并且证明了如果系统是一致的,则U 和U(U 的否定在系统中都不可证。根据排中律,算术公式U 和U 必有一真。证明了U 和U 在系统中都不可证,就是证明了并非任一算术真公式在系统中都可证。证明哥德尔不完全性定理的关键点是公式U 的构造。U 被称为不可判定公式。U 是由系统内的符号(对象语言表达的算术公式,它直接刻画的是自然数的性质与关系,是算术命题;但是,U 能表达元数学命题:公式U 在系统内不可证!这是个神奇的功能。哥德尔的天才创造了这一神奇。一个以形式语言表达的刻画自然数性质或关系的算术公式,何以能表达一个公式是否可证这样的

7、元数学性质?为了做到这一点,哥德尔完成了两个表达转换。第一,把关于算术形式系统的元数学断定(例如一个公式在系统中是否可证,表达为直观算术中关于自然数的断定。哥德尔通过极富创造性的配数法,使形式算术系统中的每个符号、每个公式(符合规则的符号串、每一证明(符合规则的公式序列惟一地对应于一个自然数,这样的自然数称为相应符号、公式或证明的哥德尔数。这样,例如,一个公式A(其哥德尔数记为p 在系统中可证,可表达为存在自然数,它是哥德尔数为p 的公式的证明哥德尔数。 可证 这种元数学性质,就这样表达为自然数之间的关系。第二,把直观算术中关于自然数的断定,表达为形式算术系统中的公式。并非所有关于自然数的断定

8、在形式算术系统中都可表达,只有具有递归性的函数、关系才可表达。在上述工作的基础上,哥德尔在系统中构造了具有以下结构的公式U :y W(p ,y 其中,谓词W(x ,y 表达的含义是:哥德尔数为x 的公式的证明的哥德尔数是y 。因此,U 的含义是:任一自然数都不是哥德尔数为p 的公式的证明的哥德尔数,也就是断定:哥德尔数为p 的公式不可证。奇妙的是,根据U 的特殊结构,公式U 的哥德尔数正是p !也就是说,U 表达的含义是:U 在系统中不可证!不可判定公式U 一旦构造出来,离完成哥德尔不完全性定理的证明就一步之差了。第一步,先证明U 不可证。假设U 可证,则存在作为U 的证明的公式序列,令q 是

9、这一证明序列的哥德尔数,则由定义,W (p ,q 成立。W 是递归谓词,在系统中可表达,因而W(p ,q 在系统中可证。已假设U,即 y W (p ,y 可证,又 y W(p ,y W(p ,q 可证,依据规则,得W(p ,q 可证。继而得:W(p ,q可证,并且W(p ,q 可证,即系统不一致。因此,如果系统一致,则U 可证的假设不成立,即U 不可证。第二步,再证明U 不可证。已证U 不可证。即任一自然数q 都不是U 的证明的哥德尔数,所以对任意自然数q,W(p ,q 成立,根据可表达性,对于任意自然数q,W(p ,q 可证,根据 -一致性y W(p ,y 不可证,即 y W(p ,y 不可

10、证,即U 不可证。这就证明了,如果系统一致,则U 和U 都不可证,即不满足完全性。同样,基于哥德尔配数法和可表达性理论, 初等数论满足一致性 这一元数学命题,可以表达为系统内的一个公式。哥德尔证明了,这一公式在系统内不可证,也就是说,哥德尔证明了,这样的系统如果一致,则这种一致性无法依靠自身得到证明。数学与逻辑结合,或者说数理逻辑发展的一个重要起点,就是数学求助于逻辑来证明自己的一致性。这就是所谓的数学基础问题。从直观算术到算术形式系统和元数学,是数学在逻辑的洗礼下经历的一次脱胎换骨。哥德尔的成果使算术读懂了自己:我想我是一致的,但可惜我不可能(不是尚未能,而是不可能证明这一点;我希望我能证明

11、所有的算术真理,但可惜我不可能(不是尚未能,而是不哥德尔在证明U 不可证 时假设系统满足 -一致性。 -一致性是比一致性更强的条件。罗塞尔证明,相关的证明假设一致性即可。实际的不可判定公式的构造更为复杂,这里讨论的公式U 是它的直观形式。算术形式系统中的可证公式,包括一阶逻辑的有效式。这里约定,算术真公式包括一阶逻辑有效式,即算术真理包括逻辑真理。可能做到这一点。面对哥德尔的成果,科学家的心情是复杂的。数学家魏尔说:上帝是存在的,因为数学是逻辑一致的;但魔鬼也是存在的,因为无法证明这种一致性。各种各样的科学理论在诉说着自己对世界的见解。哥德尔对科学理论说,你了解自己吗?这就是哥德尔留下的振聋发

12、聩的声音。对哥德尔的上述工作自然可以质疑与批评。事实上,早在哥德尔不完全性定理发表时,大数学家冯 诺依曼曾表示严重质疑,在经过相当一段时间的推敲后才确认其正确性。哥德尔不完全性定理获得了众多的高度评价,但批评、疑虑之声也时有出现。这种批评与质疑是正常的。当然,有理由要求,公开发表的此种批评与质疑不应基于对相关基本知识的误解甚至无知。温邦彦先生 禁止使用自指代命题 一文对哥德尔工作的批评涉及以下几个问题。温先生认为,哥德尔所构造的不可判定公式,是一个与说谎者悖论一样的自指代命题。自指代命题违反逻辑基本规律,应当禁止使用。不可判定公式U的含义确实是断定自身不可证。可以推想,哥德尔构造不可判定公式时

13、受到说谎者悖论的启发。但二者有实质区别。第一,作为悖论,说谎者悖论语句A满足以下等式:A=A是谎话也就是说,在 A是谎话 中,可用 A是谎话 来替代A,悖论就是这样产生的。但作为不可判定公式,公式U不满足以下等式:U=U在系统内不可证U是用形式语言表达的系统内的算术公式, U在系统内不可证 是用自然语言表达的元数学命题,二者不能划上等号。也就是说,在 U在系统内不可证 这句话中,不能用 U在系统内不可证 来替代U。U在系统内是否可证?这一问题是成立的; U在系统内不可证 在系统内是否可证?这一问题是不成立的。一般地说,一个用元语言表达的元数学命题A在系统内是否可证,是指:A在系统中是否可表达?

14、如果不可表达,则不存在是否可证的问题;如果可表达,则表达该元数学命题的系统内的公式是什么?这一公式在系统内是否可证?因此, U在系统内不可证 在系统内是否可证?这一问题的正确提法是: U在系统内不可证 在系统内是否可表达?如果可表达,则表达这一元数学命题的系统内的公式是什么?这一公式在系统内是否可证?事实上, U在系统内不可证 在系统内可表达,而表达 U在系统内不可证 的系统内的公式正是U。因此, U在系统内不可证 在系统内是否可证,这一问题的正确解读实际就是 U在系统内是否可证 ?也就是说,不可判定公式并不是温先生所说的自指代命题。第二,说谎者悖论语句可导致悖论,但不可判定公式不导致悖论。说

15、谎者悖论语句A之所以可导致悖论,因为由A真可推出A假,并且由A假可推出A真。但对于不可判定公式U来说,只有假设所在系统满足完全性(即真公式都可证,因而不可证公式都假,才可由U真推出U假。但算术系统是否满足完全性在构造U的当下正是一个悬而未决的问题,事实上这样的系统是不完全的。因此,由U真不能推出U假,即不可判定公式不导致悖论。温先生认为,在上述由U不可证导出U不可证的证明过程中,存在判定U和U可证性的两条标准:第一条标准是U或U的证明序列的哥德尔数是否存在;第二条标准是U和U表达的含义。从U的证明序列的哥德尔数不存在,根据第二条标准,得U可证;又根据第一条标准,可得U不可证。因此,这两条标准是

16、互相矛盾的。依据U的证明序列的哥德尔数不存在,确实可得U不可证;但不能得U可证。温先生的质疑是:U即 y W(p,y,这一公式的含义是:任一自然数都不是哥德尔数为p的公式的证明序列的哥德尔数。而U正是这个哥德尔数为p的公式,因此, U的含义正是 U的证明序列的哥德尔数不存在 。证明了 U的证明序列的哥德尔数不存在 ,不就是证明了U吗?既说证明了 U的证明序列的哥德尔数不存在 ,又说U不可证,岂不自相矛盾?温先生混淆了 证明 有两种含义,一种是系统内的证明,另一种是系统外的证明。系统内的证明之对象是系统中的公式,证明的目标是确定某个公式为系统中的定理,证明的依据只有公理和推理规则。系统外的证明之

17、对象是用元语言(主要是自然语言表达的句子,不是系统内的公式,例如, U 不可证 ,其中U是系统内的公式,但 U不可证 不是系统内的公式,而是用自然语言表达的句子,系统外证明的目标是确定这样的句子的真实性。系统内证明的定理,称为内定理。系统外证明的结论,称为元定理。哥德尔构造了不可判定性公式U,并且证明了在数论形式系统N中,如果N是一致的,则U和?U都不可证。这个证明是系统外的证明。哥德尔定理是元定理。因此,对不可判定公式U,当我们说 证明了U是真命题 ,这个 证明 是指系统外的证明;当我们说 U不可证 ,这个 证明 是系统内的证明;当我们说 证明了一个真命题在系统内不可证(明 ,这一语句中前一

18、个 证明 是指系统外的证明,后一个 证明 是指系统内的证明。这一语句表达的正是证明了系统的不完全性。在系统外证得一个公式是真的,不等于证明了该公式在相关系统中可证。说明这一点,在与温先生的讨论中至关重要。例如,依据真值表方法可以极为方便地证明 A A 是逻辑真命题(重言式,但据此不能直接得出结论: A A 在命题演算系统P中可证。要在系统中证明 A A ,需要构造相应的公式序列,这样的序列称为该公式的证明,其中每一个公式或者是公理,或者是前面的公式,都是依据推理规则所得到的。为了加深印象,不妨把 A A 在命题演算P系统中的证明照录如下:(1 A (A A A公理1(2 (A (A A A (

19、A (A A(A A公理2(3 (A (A A (A A(1(2分离(4 A (A A公理1(5 A A(3(4分离当然,如果证明了命题演算P的完全性,就可以直接根据 A A 是重言式,得出 A A 在系统中可证。命题演算P的完全性的证明是非常复杂的。而在哥德尔定理的证明中,算术形式系统N 的完全性恰恰有待证明(事实上它是不完全的,因此,更不能根据U是真命题,直接得出结论:U在N中可证。温先生感到不解的是:对于任一自然数q,W (p,q可证,不就是对所有自然数q,W(p,q可证吗?,因而不就是 y W(p,y可证吗? 任一 与 所有 难道还有区别?根据对于任一自然数q, W(p,q可证,为什么

20、不能得出 y W(p,y可证?根据什么得出:对于任一自然数q,W(p,q可证?根据两点:第一,U不可证,因而任一自然数都不是其证明的哥德尔数;第二,W是递归谓词,在系统中可表达。W是递归谓词,在系统中可表达,只能保证对于任意一个确定的自然数q,在系统中通过有穷步骤证明W(p,q,但不能保证在有穷步内证明 y W(p,y。递归证明是一种在有限步骤内完成的证明。可以直观地比照这样一个例子:任给一个自然数,我们都可以通过有限步骤的操作证明:存在自然数比它大(事实上只要加1,即只要通过一次后继运算即行;但这并不意味着我们都可以通过有限步骤的操作证明:所有自然数都有自然数比它大。综上所述,温先生未能准确理解和把握形式化理论的一系列基本概念,如未能准确理解和区分公式