你在这里

哥德尔

主标签

哥德尔

张锦文

(中国科学院软件研究所)

哥德尔,K.F(Godel,Kurt Friedrich)1906年4月28日生于奥匈帝国的布尔诺(今属捷克斯洛伐克);1978年1月14日卒于美国普林斯顿.数学、逻辑学、数学哲学.

哥德尔的父亲在青年时代即从维也纳迁移到兴旺的纺织工业基地布尔诺定居,他富有自力更生的创业精神,后来成了那里一家主要纺织厂的管理方面的领导者.哥德尔的母亲一家由莱茵河地区到布尔诺从事纺织工业,她曾在布尔诺一所法语学校读书,受过较好的教育,她终生对文化事业保持兴趣,她生育了哥德尔兄弟二人,哥德尔的哥哥比他大四岁,后来成了一位放射学家.

哥德尔有一个幸福的童年,但他胆小又爱吵闹,在六七岁时患了急性风湿性关节炎,危害了他的健康,特别是影响了他的心脏.他的才智很早就显露出来了.由于他经常提出各式各样的问题,家里人常称他为“为什么先生”(Mr Why).1912年,他六岁时进入布尔诺的巴黎学校上学.从1916年到1924年,他的学习成绩优秀,特别是在数学、语言和神学方面表现尤为突出.

第一次世界大战直接影响了哥德尔及其家庭,虽然布尔诺地区远离战争前线,但战后,1918年奥匈帝国解体了,出现了新国家:奥地利、捷克斯洛伐克、匈牙利等.1924年哥德尔毕业于布尔诺大学预科,然后到维也纳大学学习.当时,维也纳作为1919年新创立的奥地利共和国的首都,是当时的政治、经济、文化中心.1929年哥德尔成了奥地利的公民.在维也纳大学,哥德尔先学物理,后主攻数学.他参加了以攻读B.罗素(Russell)的专著《数学的哲学导论》(Introduction to mathematical philosophy,1919)为中心的讨论班.在1926—1928年期间哥德尔也参加了维也纳 M.施利克(Schlick)的哲学小组,但他并不赞成逻辑实证论观点,1929年他逐渐离开了这一小组,但他仍与该组成员R.卡纳普(Carnap)保持一般的接触.哥德尔离开石里克小组的主要原因是他已建立了自己的独到的哲学观点.

哥德尔的老师、数学家P.富特温勒(Furtwangler)对他有很大的影响.他的导师H.哈恩(Hahn)的研究兴趣主要是现代分析、集合论、拓扑、逻辑、数学基础和科学哲学,在知识背景方面直接影响了哥德尔.但是,哥德尔在确定自己的研究方向时,起重要作用的两个因素是卡纳普的数理逻辑讲演,D.希尔伯特(Hilbert)和W.阿克曼(Ackermann)的专著《理论逻辑原理》(Grundzge der theoretischen Logik,1928).在这本书的1928年版(即第二版)中著者列举了一阶谓词演算的完全性这个未解决的问题.哥德尔把这一问题作为自己的主攻方向.1929年夏季,当时只有23岁的哥德尔肯定地解决了这一问题:证明了一阶谓词演算的完全性定理.由此,在1930年2月他获得了博士学位.随后,他进一步研究希尔伯特方案,希望用有穷方法证明数学形式系统的协调性问题,主要是关于算术、分析和集合论等系统的协调性问题.1930年8月26日哥德尔向卡纳普等人通告了他的不完全性结果,即数论形式系统如果是协调的,则它是不完全的,并且它的协调性在系统内是不可证明的.1930年9月7日哥德尔在柯尼斯堡召开的数学讨论会上第一次正式公布了他的上述结果.同年10月23日在维也纳科学院他也报告了他的上述结果.哥德尔的不完全性结果与希尔伯特的猜想相反,并且从根本原则上否定了希氏方案.希氏学派的主要成员冯·诺伊曼(von Neumann)、P.伯奈斯(Bernays)先后认识到了哥德尔上述结果的巨大的潜在意义,希尔伯特也不得不重新修改了他的方案.从1930年起,哥德尔与冯·诺伊曼、伯奈斯、E.F.策梅罗(Zermelo)、A.塔斯基(Tarski)等著名数理逻辑学家建立良好的关系.冯·诺伊曼出生于匈牙利,比哥德尔仅大三岁,但他当时已在证明论、集合论、分析学和数学物理等方面作出了重要结果,因而名噪一时.伯奈斯是希尔伯特的助手与合作者,策梅罗是集合论公理系统的首创者,塔斯基是波兰逻辑学家,由于他的形式语言真值概念的工作而成名.他们的交流促进了数理逻辑的发展,扩大了这一学科的影响,并使哥德尔开创的方向成了这一学科的主要倾向.在1933年3月经过简短的教学实习,哥德尔出任维也纳大学的无薪水讲师.同年9月30日赴美国讲学,作为普林斯顿高级研究院的客座成员,他报告了他的不完全性结果.同年12月哥德尔在美国数学会年会上报告了“数学基础的现状”. 1934年4月18日哥德尔在纽约哲学学会上的讲演题目是“包含算术的任意形式系统内不可判定命题的存在性”.接着4月20日在华盛顿科学院讲了“数学能够证明协调性吗?”同年5月26日至6月3日乘船返回欧洲.1935年5月在维也纳大学他讲授数理逻辑课程,其间曾于6月19日在蒙格尔的学术讨论会上介绍他的证明长度的论文.1935年9月至12月哥德尔第二次访问美国.10月间他向冯·诺伊曼通报了他的选择公理相对协调性证明.由于健康原因,他向普林斯顿高级研究院辞职回维也纳治病,1936年他主要在治疗疾病.1937年哥德尔在维也纳大学讲授公理集合论课程,并发现了广义连续统假设相对集合论公理协调性证明的关键步骤.

1938年9月20日,哥德尔与安迪(Adele Nimbursky)女士结婚.安迪比哥德尔大六岁,早在1927年哥德尔才21岁时他们就相爱了.安迪是位舞女并且曾经结过婚,对于他们的相爱,哥德尔的父母极力反对.尽管哥德尔的父亲在1929年已病故,他们仍推迟了多年才结婚.婚后半个月,1938年10月6日哥德尔把妻子留在维也纳,独自应邀第三次赴美国讲学,10月15日到达普林斯顿高级研究院.直至12月他都在讲述选择公理、连续统假设相对协调性结果,其间《美国科学院学报》(Proceedings of theNational Academy of Science, U.S.A,24,pp.556—557)宣布 了他的结果.同年12月28日哥德尔在美国数学学会第45届年会上报告了“广义连续统假设的协调性”.1939年《美国科学院学报》(同上,25,PP.220—224)发表了哥德尔的论文“广义连续统假设的协调性证明”(Consistency-proof for the generalized con-tinuum-hypothesis).同年6月14日—20日,哥德尔乘船由美国返回维也纳.虽然,哥德尔当时已解决了几项重大的数学问题,三次应邀赴美国讲学,他已成为世界知名的数理逻辑学家,但他在维也纳大学仍然是一个无薪水的讲师.9月25日他申请晋升为正规的讲师,无人理采.这样,哥德尔就不得不寻找到美国定居的途径了.1940年1月哥德尔偕夫人安迪离开维也纳到美国定居.1938年3月13日希特勒已吞并了奥地利,哥德尔离开纳粹统治下的维也纳使他从此有了一个进行研究工作的安定环境.从此,他再也没有回过欧洲.

1940年春,哥德尔到达普林斯顿高级研究院,成了该院的成员.同年普林斯顿大学出版社出版了哥德尔的专著《广义连续统假设的协调性》(The consistency of continuum hypothesis),这是根据他于1938至1939年在普林斯顿高级研究院讲演的原稿整理的,全名应是《选择公理、广义连续统假设与集合论公理的相对协调性》(The consistency of the axiom of choice and of thegeneralized cantinuum-hypothesis with the axioms of set theo-ry).1941年4月他在耶鲁大学的讲演是“在什么意义下直觉主义逻辑是构造的?” (In what sense is intuitionistic logic cons-true tive?)1942年作出了“在有穷类型论中选择公理的独立性证明”(Proof of the independence of the axiom of choice in-finite type theory).1944年发表了“罗素的数理逻辑”(Russell'smathematical logic).1946年在普林斯顿200周年纪念会上就数学问题作了讲演.1947年发表了重要的数学哲学论文“什么是康托尔的连续统问题?”(What is Cantor's continuum problem?)

哥德尔在普林斯顿最亲密的朋友是著名物理学家A.爱因斯坦(Einstein)和数理经济学家O.摩根斯顿(Morgenstern).他们经常散步和闲谈.1948年4月2日他们三人一起到美国移民局,一起取得美国国籍,成为美国公民.哥德尔与爱因斯坦一直是最亲密的朋友,直至爱因斯坦1955年去世.虽然他们两人在性格上有很大的差别,爱因斯坦爱社交,活泼开朗,而哥德尔严肃认真、相当孤独,但是他们都是直接地全心全意地探求科学的本质.1943年后,哥德尔逐渐把注意力转向数学哲学乃至一般的哲学问题.当然他也还不断地关注逻辑结果,比如1958年他研究了有穷方法的扩充,1963年审阅并推荐了P.J.科恩(Cohen)的重要论文“连续统假设的独立性”(The independence of the continuumhypothesis).1973年评述了A.鲁宾逊(Robinson)创立的非标准分析.哥德尔这些工作对数理逻辑的发展都起了重要的作用.

1953年哥德尔晋升为普林斯顿高级研究院的教授.

1951年哥德尔获得爱因斯坦的首次奖,以后多次获得荣誉称号,如哈佛、洛克菲勒等著名大学的荣誉博士、英国皇家学会国外会员、法国研究院的通信成员.哥德尔于1966年还拒绝接受奥地利科学院授予他的荣誉成员称号.1975年9月18日他获得了美国总统奖,当时的总统是福特.

哥德尔妻子安迪于1981年在普林斯顿去世,他们没有子女.

我们曾经指出,哥德尔是亚里士多德(Aristotle)和G.W.莱布尼茨(Leibniz)以来最伟大的逻辑学家.但是,这决不仅仅是由于他的聪明才智所决定的,更重要的是数学、逻辑学发展到20世纪所面临的问题、面临的任务并由此而出现了一大批优秀的逻辑学家,哥德尔是其中最突出的代表.19世纪在微积分基础工作中出现了A.柯西(Cauchy)、K.魏尔斯特拉斯(Weierstrass)、R.戴德金(Dedekind)和G.康托尔(Cantor)这样一批大数学家,他们十分重视数学的逻辑严谨性.G.弗雷格(Frege)又建立适应数学论证的谓词演算,在逻辑学中首次引进全称量词和存在量词的概念.1900年巴黎数学家大会上希尔伯特提出了23个未解决的数学问题,其中第一个问题是康托尔的连续统假设是否成立,第二个问题是算术公理的协调性.他指出,在关于公理系统所能提出的问题中,最为重要的是:证明这些公理不互相矛盾,就是说,以它们为基础而进行的有限步骤的逻辑推演,决不会导致矛盾的结果.1900年前后,先后在康托尔集合论中发现几个令人吃惊的悖论.这样,出现了数学基础的危机,为解决这种危机,L.E.J.布劳威尔(Brouwer)提出了在数学中取消无穷对象、取消数学论证中无限制地使用排中律的直觉主义建议,由此形成了数学基础研究中的直觉主义学派.罗素提出了把数学还原为逻辑,形成了逻辑主义学派.罗素与A.N、怀特海(Whitehead)合著的《数学原理》(Principia mathematica)一书中完全应用了数理逻辑的方法,从一些逻辑概念和数学公理出发实际上推导出很大一部分数学,而这是沿着弗雷格、G.皮亚诺(Peano)的思路开始的.希尔伯特强调数理逻辑在数学基础研究中的巨大作用,但他不赞成逻辑主义,更反对直觉主义.在希尔伯特看来,悖论的根源不在于实无穷,而在于对实无穷的错误认识.希尔伯特认为直觉主义否定实无穷,否定排中律等等,是对数学“这门科学大砍大杀”,就会使数学“失去大部分最宝贵的财富”.希尔伯特及其学派制定了一个保卫数学建立其严谨基础的方案,人们称之为希尔伯特方案.这一方案是要将数学理论进行形式化处理,建立相应的形式公理系统,用有穷方法研究系统的完全性、协调性和判定性等问题.这些形式公理系统共同的逻辑基础是谓词演算,当时已证明了谓词演算的可靠性(或称一致性),即任一逻辑定理在所有的解释(或称赋值)下都是真的(称之为普遍有效的).但是,谓词演算是否具有完全性呢?也就是说,谓词演算中普效命题是否是逻辑定理呢?这是1920年前后人们关注的一未解决的重大问题,直至1928年在前述的希尔伯特与阿克曼的专著第二版中仍然是末获得解决的问题.1929年哥德尔肯定地解决了这一问题,证明了谓词演算的完全性定理.这一结果,对于希尔伯特方案是一有力的支持,因为它表明了希尔伯特所依据的逻辑基础是既可靠又完全的一门独立的数学理论.

哥德尔完全性定理在谓词演算的语法概念与语义概念之间架起了一座桥梁.这里语法概念指形式系统,语义概念指数学模型.这就是说,哥德尔定理是在形式系统与数学模型之间架起了一架桥梁.

形式系统的一合式公式(或称命题,也称语句)集合 S叫做协调的,如果此系统内不存在一合式公式A,使得从S出发公式A与A的否定式`\neg A`都是可证的.S不是协调的就叫它是不协调的.一不空集合M及M上定义的关系、函数等一起可以构成一结构.形式系统的一命题A,在结构M上做解释,对于这一解释而言,命题A经解释后在结构M中是真的,就称结构M为A的一模型.若S中每一命题经解释后在结构M中都是真的,就称M是S的一模型.显然,结构、解释、模型都是语义概念.依据上述概念,哥德尔完全性定理是说:对于谓词演算的任一命题集合S而言,都有:

S是协调的当且仅当S有模型.

这里所讲的谓词演算是一阶古典谓词演算,也称为狭谓词演算,“一阶”是相对“高阶”而言的,即量词的变域是个体域,而不能是谓词,也不能是函数词,“古典”是相对“直觉主义”或“各种非经典或非标准”而言的.

哥德尔完全性定理是当代模型论的基本定理之一,由它导出了一系列重要结果.

还应当指出,哥德尔完全性定理是对形式系统的整体特征性定理(而不是系统内的形式定理),这种定理称之为元定理或元数学定理.按照希尔伯特方案和当时人们的思想观念,元定理应局限在有穷方法内给出证明,排中律与无穷过程是不能被使用的.然而,这一定理是很强的,用有穷方法是不可能给出证明的.哥德尔看出了这一问题,大胆地采用无穷方法找出问题的答案,给出了定理的证明.对此,哥德尔曾在致王浩的信中说道,他解决了完全性在于他的哲学思想先进,不拘泥于有穷方法,而并不是他的数学技巧比别人高明(见 Wang Hao,From mathematics to philosophy).在哥德尔晚年,王浩是他的最好的朋友之一,他们之间就数学基础和哲学问题有许多内容深刻的交谈.

哥德尔不完全性定理是更令人吃惊的.如前指出,不完全性是指形式算系统而言的,也可以说是指皮亚诺算术系统P而言的.哥德尔证明:如果P是协调的,则有一算术的形式命题A即A为P中一命题),并且A与`\neg A`在P中都不可证明的.这与希尔伯特的猜想完全相反.希尔伯特猜想,不仅形式数学系统的基础逻辑——谓词演算是完全的,而且每一个形式数学系统也是完全的,特别是皮亚诺算术系统P也应当是完全的,它的命题集合总是可以一分为二,一部分是P的定理集合(即其中每一元都是P的定理,不妨把定理集合记为T),另一部分是P的可驳集合(即其中每一元都是P的否定理,即它的否定式是P的定理,不妨把P的可驳集合记为R).希尔伯特猜想,系统P的命题集合恰好就是T与R的并集合:T∪R.这就是说,皮亚诺公理系统巳完全刻画了算术系统.但是,哥德尔否定了希尔伯特的猜想,从而否定了希尔伯特方案.哥德尔具体地严谨地证明了存在一命题A,A和它的否定式`\neg`都不在T中,也不在R中.也就是说,P的命题集合不可能按照其元(即命题)是可证可驳的原则分为两部分,这是一重大的结果.哥德尔怎样获得这一结果呢?

为了证明上述定理,哥德尔区分了形式系统内外的几个层次和它们间的联系.第一步,形式系统的概念是使用无数学概念建立起来的.这些元数学概念是若干个符号的规定、转换和说明.第二步,是把元数学概念通过配数方法(这一方法也是哥德尔给出的)给出算术化处理,用自然数的函数与关系把它们描述出来,并证明这些函数与关系的机械性质,即它们是递归函数与递归关系.第三步,证明递归函数与递归关系在形式数论系统内都是数词可表达的.哥德尔通过这些精湛的数学技巧,从错综复杂的联系中弄清“命题A在P中是可证的”、“公式序列Г是命题A在P中的一证明”等关于形式系统P的元数学概念都可以算术化为关于自然数间的关系与函数.并且它们又都是在P中可表达的,从而他构造了他的定理所要求的命题AP,并得到了上述不完全性定理的证明.由此,哥德尔证明:AP,与`\neg`AP在P中都是不可证明的,从语法上讲,AP与`\neg`AP都是不可证的,而从语义上,AP与`\neg`AP必然有一个是真的(事实上由哥德尔的构造过程可知,AP是真的).因此,哥德尔第一次澄清了真与可证是两个不同的概念.对于形式系统而言,可证性是一个较为机械的思维过程,而真理性则是一个能动的和超穷的思维过程,二者不能混为一谈.此外,命题AP对自己也是有所断定的,这就反对了罗素与怀特海关于命题不能对自己有所断定的意见.

上述哥德尔不完全性定理在文献中常称为哥德尔第一不完全性定理.哥德尔还证明了另一个定理,文献中称之为第二不完全性定理,这一定理是说,如果系统P是协调的,那么它的协调性在系统P中是不可证明的.它的证明是通过把“P是协调的”这一元数学概念加以算术化,然后在P中形式化,得到它的形式公式可记为“con(P)”.我们再把第一定理的证明,即

(*)“若P是协调的,则AP是不可证的”

加以形式化,也就是把(*)的整个证明在系统P内形式化,则我们应获得

(**)Pcon(P)→AP

现在,设Pcon(P),这时,由(**)叫将获得PAP,这就得到与第一定理相矛盾的结论.从而就得到了第二定理的证明.

哥德尔的上述结果对逻辑学和数学特别是数学基础产生了巨大的影响,使逻辑学、数学基础学在新的起点上获得了新的发展,揭示了机械的与非机械的思维活动的基本性质,论证了形式系统的逻辑标准与局限性问题,这些都是人类认识史上的重大结果.对于机械的思维活动,哥德尔在证明不完全性定理时,采用了递归方法并开展详尽的论述.根据J.埃尔布朗(Herbrand)和哥德尔的意见,S.C.克林(Kleene)对一般递归函数理论作了深入的研究,A.丘奇(Church)建立λ演算理论,A.M.图灵(Turing)建立另一种机械性思维过程,以描述算法,现在人们称之为图灵机器.人们很快就证明:上述几种机械性思维过程的概念和理论都是等价的,可以相互转换的.近年来,人们进一步发现了一系列可以相互转换的算法概念与理论,并且愈来愈展现出他们在计算机领域内的巨大作用.

关于连续统假设相对于集合论通常公理系统的协调性证明以及在证明过程中所创立的可构成性方法,是哥德尔的又一重大贡献.连续统问题是康托尔首先提出的,这涉及到无穷集合、无穷基数中一些根本问题.在许多无穷集合的比较中,以什么为标准呢?康托尔提出按一一对应来区分集合的“大小”,与自然数集合有一一对应关系的集合称为可数集合,诸如此种集合的基数定义为,把所有具有基数为的集合收集在一起所组成的哪个集合的基数为,以此类推,可以获得无穷基数序列:

其中α为任意的序数.另一方面,实数集合的基数,也就是自然数集合的所有子集合所构成的哪个集合的基数为2,康托尔证明它大于,然而它究竟等于式(1)中哪个基数呢?因为式(1)是一严格递增的基数序列,并且2大于,因此,就有

1878年康托尔猜想式(2)中的等号应当成立.也就是说,他猜想:

就是康托尔的连续统假设.1883年,康托尔在他的论文“关于无穷线性点集合(5)”(Uberunendliche lineare Punktmannigfaltig-keiten 5,Mathematische Annalen,21(1883),pp 545—586)中,希望不久将能够公布他的猜想的严格证明.随后,他还一再声明将公布他的证明.但是,直至1918年1月6日康托尔去世,他也没有把他的证明公布于众.大概是他发现了原来的证明有错误而未公开发表.

1900年夏季在巴黎举行的第二次国际数学家代表大会上,希尔伯特做了题为《数学问题》(Mathematische Probleme, Archivder Mathematik und Physik,Series 3,1,pp.44—63,213—237)的演说,提出了前面曾经说过的23个未解决的问题,向20世纪的数学家们提出挑战.其中第一个问题就是“证明连续统假设”.他说:“康托尔关于这种集合的研究,提出了一个似乎很合理的定理,可是尽管经过坚持不懈的努力,还是没有人能够成功地证明这条定理.这一定理就是:每个由无穷多个实数组成的系统,亦即实数集合R的无穷子集合(或点集合),或者与自然数1,2,3,……组成的集合对等(即有一一对应的关系),或者与全体实数组成的集合对等,从而与连续统(即一条直线上的点的全体)相对等;因此,就对等关系而言,实数的无穷子集合只有两种:可数集合和连续统.”他接着又说:“由这条定理,立即可以得出结论:连续统所具有的基数,紧接在可数集合的基数之后;所以,这一定理的证明,将在可数集合与连续统之间架起一座新的桥梁.”1925年,已经63岁、身患多种病的希尔伯特又提出了试图证明连续统假设的大纲,这就是他1926年的论文“论无穷”(Uber das Unendiche,Mathematische Annalen,95,pp.161—190).遗憾的是他的证明有漏洞,证明是错误的.这一切都表明连续统问题是很有意义的、难度很大的问题.1934年波兰学者W.谢尔品斯基(Sierpinski)出版他的专著《连续统假设》(Hypothese du continu),揭示了在分析数学中有12个数学命题与连续统假设等价,有81个命题是它的直接推论.这就更突出了它的重大意义.对于这一问题,哥德尔所取得的重大进展是连续统假设与集合论的通常公理系统(包括选择公理)是协调的,也就是说,集合论的通常的公理系统(包括选择公理)推不出连续统假设的否定式.在证明过程中,哥德尔引进了可构成集合、可构成公理等重要概念.对于任意一集合S而言,集合S1叫做S的可定义子集合,如果有一公式(x1,…,xn,x)和S的元素a1,…,an,使得

S1={x|x∈SΛ(a1,…,am,x)}

成立,令S'为S的所有可定义子集合所组成的集合.令

L=Φ, (4.1)

La+1=(La)', (4.2)

一集合x叫做是可构成的,如果存在一序数α,使得x∈La.

可构成公理是说,每一集合都是可构成的,常常记做V=L.哥德尔首先证明通常集合论公理(不包括选择公理)都在L中成立,然后证明,可构成公理蕴涵选择公理与连续假设.文献中常把选择公理记做 AC(Axiom of Choice的缩写),连续统假设记做CH(Continuum Hypothesis的缩写),并且把通常的集合论公理系统理解为策梅罗-弗伦克尔(Zermelo-Fraenkel)系统(通常简记为ZF,不包括选择公理,当把它理解为包括选择公理时,也常记做ZFC).使用上述记号,就有

V=L→ACΛCH, (5)

在ZF中可证明.第三步,哥德尔还证明了:V=L在L中成立.从而就得到了选择公理与连续统假设在L中成立.因为V=L并非是一真命题,只是在L中真,所以AC与CH也并非真命题,它们只是在L中真.哥德尔的结果给人们一种宽慰,不会因为使用选择公理增加不可靠性,也就是说,人们使用ZF公理所建立的数学理论没有矛盾时,再进一步地使用选择公理,即在使用ZFC时所建立的数学理论也没有矛盾.哥德尔建立的AC与ZF的相对协调性证明也是一项重大结果.

哥德尔的结果还有更广泛的结论,这就是在L中不仅CH成立,而且广义连续统假设(Generalized Continuum Hypothesis,常缩写为GCH)也成立.其中GCH是F.豪斯多夫(Hausdorff)在1908年提出的,对于任意的序数a,应有等式

成立.事实上,康托尔在1883年也曾说应有

成立.显然,式(3)与(7)都是式(6)的特殊形式.哥德尔在前边提到的1940年的专著中证明的是V=L→ACΛGCH.他的结果较之更为广泛.

哥德尔创立的可构成方法开辟了集合论研究的新方法、新方向,文献中常称为内模型方法.1940年以后人们对它进行了系统的研究,获得了极小内模型等重要结果,在这些结果与方法的基础上,P.J.科恩(Cohen)1963年创立了力迫方法,证明了广义连续统假设、选择公理相对于通常集合论公理的独立性结果.当我们用符号“”表示“推不出”时,哥德尔的定理就是:

而科恩的定理是:

这就是100多年以来,人们对选择公理与连续统假设的主要结果.康托尔提出的连续统的势到底等于什么呢?或者说,2到底是无穷基数序列式(1)中哪一个呢?这仍然是一个未解决的重大的数学问题.关于这一点,哥德尔早在1947年的哲学性论文“什么是康托尔的连续统问题?”(What is Cantor's Continuum prob-lem?)中就指出:“康托尔连续统问题,不论采取什么哲学观点,不可否认地至少保持这个意义:去发现它是否有一个答案,如果有,那么是什么答案,是能从所引用的系统中所陈述的公理推导出来的.”

“自然,如果按这个方法解释,那么(假定公理的协调性)对于康托尔猜测就先验地存在着三种可能性:它是可证明,或者是可否证的,或是不可判定的.”

哥德尔的结果说明不可能是“否证的”,科恩的结果说明不可能是被“证明的”,因此,就是“不可判定的”了.哥德尔着重指出,从所采取的集合论公理对康托尔猜测的不可判定性的证明,“决不是问题的解决”.它仍然是当代数学的一大难题.这在某种程度可归之于纯数学的困难.此外,哥德尔说:“看来这里还含有更深刻的原因,并且只有在对它们中出现的词项(如“集合”、“一一对应”,等等)和支配这些词项的使用的公理的意义进行(比数学通常作的)更深刻的分析,才能得到这些问题的完全解决.”在哥德尔看来,如果我们所解释的集合论的原始词项的意义被认为是正确的话,那么就可以得出,集合论的概念和定理描述了某个完全确定的实在(即论域),在其中康托尔猜测必然或者是真的,或者是假的.“因此,从今天所采取的公理得出康托尔猜测的不可判定性,只是意味着这些公理没有包括那个实在的完全描述.”他又说:“可能存在就其证明的结果来说是如此丰富的其它公理,它照亮整个领域并产生这样强有力的解决问题的方法(并且,只要是可能的,甚至可以构造地解决它们),使得不论它们是否是内在必须的,至少应在如同任何已经完全建立的物理理论同等的意义上接受它的.”哥德尔在分析了与连续统假设有关的许多数学命题之后指出:

“与大量的蕴涵连续统假设的否定似乎真的命题相反,没有一个已知的似乎真的命题蕴涵连续统假设.”因此,在新的系统中,“有可能否证康托尔猜测”.

哥德尔40年前的论断,仍然是当今集合论学者关心的课题.以S.斯拉(Shelab)为代表的一批学者提出了一条称为正常力迫的公理,由此可推出.但是,正常力迫公理是否具有公理的资格,也是当前人们极为关心的问题.

我们不难看到,哥德尔在“什么是康托尔的连续统问题”这一哲学论文中是紧紧抓住连续统这一难题展开的,他所揭示的观点对于数学研究是有指导意义的,他的思想极为深刻.哥德尔在他的另一篇哲学论文“罗素的数理逻辑”(Russell’s mathematicalIogic,1944)中着重分析了罗素的逻辑思想的发展,指出了数理逻辑在实际发展中曾采取的方法,“…最重要的简单类型论和公理化集合论,它们二者至少在这个范围内是成功的,即它们允许推导现代数学同时避免一切已知的悖论.但许多迹象只是更加清楚地表明,一些原始的概念尚需进一步阐明”.哥德尔进一步发挥了莱布尼茨的思想:“人类将有一种新的工具,同任何视觉工具对视力的帮助相比,更大大增强推理的能力.”哥德尔等人开创的机械思想过程的研究和现代计算机的结合正在不断地发展着新型的推理工具.

哥德尔的工作还有许多方面有引人注目的创造成果,比如:(1)加速度定理,或称证明长度定理,在1936年的论文“关于证明的长度”(Uber die Lange von Beweisen)中哥德尔建立了类型、强度都逐一增加的系统:S1,S2,…,Si,Si+1,….主要结果是:在Sn与Sn+1(n∈ω)中都存在诸命题,它们在系统Sn与Sn+1中都是可证的.但在Sn+1的证明长度要比Sn中的长度短得多.人们认为,这一结果对于计算机科学可能产生重要的影响.(2)关于判定问题的可解情况,哥德尔发表了论文“对于理论逻辑判定问题的一个特别情况”(Ein Spezialfall des Entschei-dungsproblems der theoretischen Logik,1932)和“关于谓词逻辑演算的判定问题”(Zum Entscheidungsproblem des logischnFunktionenkalküls,1933),解决狭谓词演算中可判定的命题类的最重要表达形式.所谓狭谓词演算的判定问题就是要寻找一个一般的方法,对于任意给定的命题,我们都可以在有穷步骤内判定它是否是可满足的.1936年,图灵证明了狭谓词演算是不可判定的.在图灵之前,人们一方面寻求可判定的特殊类,一方面寻求归约类(即将狭谓词演算的整个公式类归约到这一特定的类,如前束范式类就是一个旧约类).阿克曼已经指出前束词


归约类.这就建立了关于可满足性的可判定类与归约类之间的一个明确

都是归约类的结果(参见王浩《数理逻辑通俗讲话》,科学出版社,1981).此外,哥德尔还对直觉主义逻辑等领域有重要工作,这里不一 一列举了.

综上,我们不难看出,哥德尔的工作影响和推动了数理逻辑近60年的发展,使它从较为分散的研究工作扩大为独立的系统的学科,并且产生了若干研究分支,对计算机科学与技术已经产生并将继续产生深刻的影响.他作为亚里士多德、莱布尼茨以来的最伟大的逻辑学家影响将是深远的.