|
哥德爾 張錦文 (中國科學(xué)院軟件研究所) 哥德爾，K．F(G del，Kurt Friedrich)1906年4月28日生于奧匈帝國的布爾諾(今屬捷克斯洛伐克)；1978年1月14日卒于美國普林斯頓．?dāng)?shù)學(xué)、邏輯學(xué)、數(shù)學(xué)哲學(xué)． 哥德爾的父親在青年時(shí)代即從維也納遷移到興旺的紡織工業(yè)基地布爾諾定居，他富有自力更生的創(chuàng)業(yè)精神，后來成了那里一家主要紡織廠的管理方面的領(lǐng)導(dǎo)者．哥德爾的母親一家由萊茵河地區(qū)到布爾諾從事紡織工業(yè)，她曾在布爾諾一所法語學(xué)校讀書，受過較好的教育，她終生對(duì)文化事業(yè)保持興趣，她生育了哥德爾兄弟二人，哥德爾的哥哥比他大四歲，后來成了一位放射學(xué)家． 哥德爾有一個(gè)幸福的童年，但他膽小又愛吵鬧，在六七歲時(shí)患了急性風(fēng)濕性關(guān)節(jié)炎，危害了他的健康，特別是影響了他的心臟．他的才智很早就顯露出來了．由于他經(jīng)常提出各式各樣的問題，家里人常稱他為“為什么先生”(Mr Why)．1912年，他六歲時(shí)進(jìn)入布爾諾的巴黎學(xué)校上學(xué)．從1916年到1924年，他的學(xué)習(xí)成績優(yōu)秀，特別是在數(shù)學(xué)、語言和神學(xué)方面表現(xiàn)尤為突出． 第一次世界大戰(zhàn)直接影響了哥德爾及其家庭，雖然布爾諾地區(qū)遠(yuǎn)離戰(zhàn)爭前線，但戰(zhàn)后，1918年奧匈帝國解體了，出現(xiàn)了新國家：奧地利、捷克斯洛伐克、匈牙利等．1924年哥德爾畢業(yè)于布爾諾大學(xué)預(yù)科，然后到維也納大學(xué)學(xué)習(xí)．當(dāng)時(shí)，維也納作為1919年新創(chuàng)立的奧地利共和國的首都，是當(dāng)時(shí)的政治、經(jīng)濟(jì)、文化中心．1929年哥德爾成了奧地利的公民．在維也納大學(xué)，哥德爾先學(xué)物理，后主攻數(shù)學(xué)．他參加了以攻讀B．羅素(Russell)的專著《數(shù)學(xué)的哲學(xué)導(dǎo)論》(Introduction to mathematical philosophy，1919)為中心的討論班．在1926—1928年期間哥德爾也參加了維也納 M．施利克(Schlick)的哲學(xué)小組，但他并不贊成邏輯實(shí)證論觀點(diǎn)，1929年他逐漸離開了這一小組，但他仍與該組成員R．卡納普(Carnap)保持一般的接觸．哥德爾離開石里克小組的主要原因是他已建立了自己的獨(dú)到的哲學(xué)觀點(diǎn)． 哥德爾的老師、數(shù)學(xué)家P．富特溫勒(Furtw ngler)對(duì)他有很大的影響．他的導(dǎo)師H．哈恩(Hahn)的研究興趣主要是現(xiàn)代分析、集合論、拓?fù)?、邏輯、?shù)學(xué)基礎(chǔ)和科學(xué)哲學(xué)，在知識(shí)背景方面直接影響了哥德爾．但是，哥德爾在確定自己的研究方向時(shí)，起重要作用的兩個(gè)因素是卡納普的數(shù)理邏輯講演，D．希爾伯特(Hilbert)和W．阿克曼(Ackermann)的專著《理論邏輯原理》(Grundzge der theoretischen Logik,1928)．在這本書的1928年版(即第二版)中著者列舉了一階謂詞演算的完全性這個(gè)未解決的問題．哥德爾把這一問題作為自己的主攻方向．1929年夏季，當(dāng)時(shí)只有23歲的哥德爾肯定地解決了這一問題：證明了一階謂詞演算的完全性定理．由此，在1930年2月他獲得了博士學(xué)位．隨后，他進(jìn)一步研究希爾伯特方案，希望用有窮方法證明數(shù)學(xué)形式系統(tǒng)的協(xié)調(diào)性問題，主要是關(guān)于算術(shù)、分析和集合論等系統(tǒng)的協(xié)調(diào)性問題．1930年8月26日哥德爾向卡納普等人通告了他的不完全性結(jié)果，即數(shù)論形式系統(tǒng)如果是協(xié)調(diào)的，則它是不完全的，并且它的協(xié)調(diào)性在系統(tǒng)內(nèi)是不可證明的．1930年9月7日哥德爾在柯尼斯堡召開的數(shù)學(xué)討論會(huì)上第一次正式公布了他的上述結(jié)果．同年10月23日在維也納科學(xué)院他也報(bào)告了他的上述結(jié)果．哥德爾的不完全性結(jié)果與希爾伯特的猜想相反，并且從根本原則上否定了希氏方案．希氏學(xué)派的主要成員馮·諾伊曼(von Neumann)、P．伯奈斯(Bernays)先后認(rèn)識(shí)到了哥德爾上述結(jié)果的巨大的潛在意義，希爾伯特也不得不重新修改了他的方案．從1930年起，哥德爾與馮·諾伊曼、伯奈斯、E．F．策梅羅(Zermelo)、A．塔斯基(Tarski)等著名數(shù)理邏輯學(xué)家建立良好的關(guān)系．馮·諾伊曼出生于匈牙利，比哥德爾僅大三歲，但他當(dāng)時(shí)已在證明論、集合論、分析學(xué)和數(shù)學(xué)物理等方面作出了重要結(jié)果，因而名噪一時(shí)．伯奈斯是希爾伯特的助手與合作者，策梅羅是集合論公理系統(tǒng)的首創(chuàng)者，塔斯基是波蘭邏輯學(xué)家，由于他的形式語言真值概念的工作而成名．他們的交流促進(jìn)了數(shù)理邏輯的發(fā)展，擴(kuò)大了這一學(xué)科的影響，并使哥德爾開創(chuàng)的方向成了這一學(xué)科的主要傾向．在1933年3月經(jīng)過簡短的教學(xué)實(shí)習(xí)，哥德爾出任維也納大學(xué)的無薪水講師．同年9月30日赴美國講學(xué)，作為普林斯頓高級(jí)研究院的客座成員，他報(bào)告了他的不完全性結(jié)果．同年12月哥德爾在美國數(shù)學(xué)會(huì)年會(huì)上報(bào)告了“數(shù)學(xué)基礎(chǔ)的現(xiàn)狀”． 1934年4月18日哥德爾在紐約哲學(xué)學(xué)會(huì)上的講演題目是“包含算術(shù)的任意形式系統(tǒng)內(nèi)不可判定命題的存在性”．接著4月20日在華盛頓科學(xué)院講了“數(shù)學(xué)能夠證明協(xié)調(diào)性嗎？”同年5月26日至6月3日乘船返回歐洲．1935年5月在維也納大學(xué)他講授數(shù)理邏輯課程，其間曾于6月19日在蒙格爾的學(xué)術(shù)討論會(huì)上介紹他的證明長度的論文．1935年9月至12月哥德爾第二次訪問美國．10月間他向馮·諾伊曼通報(bào)了他的選擇公理相對(duì)協(xié)調(diào)性證明．由于健康原因，他向普林斯頓高級(jí)研究院辭職回維也納治病，1936年他主要在治療疾病．1937年哥德爾在維也納大學(xué)講授公理集合論課程，并發(fā)現(xiàn)了廣義連續(xù)統(tǒng)假設(shè)相對(duì)集合論公理協(xié)調(diào)性證明的關(guān)鍵步驟． 1938年9月20日，哥德爾與安迪(Adele Nimbursky)女士結(jié)婚．安迪比哥德爾大六歲，早在1927年哥德爾才21歲時(shí)他們就相愛了．安迪是位舞女并且曾經(jīng)結(jié)過婚，對(duì)于他們的相愛，哥德爾的父母極力反對(duì)．盡管哥德爾的父親在1929年已病故，他們?nèi)酝七t了多年才結(jié)婚．婚后半個(gè)月，1938年10月6日哥德爾把妻子留在維也納，獨(dú)自應(yīng)邀第三次赴美國講學(xué)，10月15日到達(dá)普林斯頓高級(jí)研究院．直至12月他都在講述選擇公理、連續(xù)統(tǒng)假設(shè)相對(duì)協(xié)調(diào)性結(jié)果，其間《美國科學(xué)院學(xué)報(bào)》(Proceedings of theNational Academy of Science， U．S．A，24，pp．556—557)宣布 了他的結(jié)果．同年12月28日哥德爾在美國數(shù)學(xué)學(xué)會(huì)第45屆年會(huì)上報(bào)告了“廣義連續(xù)統(tǒng)假設(shè)的協(xié)調(diào)性”．1939年《美國科學(xué)院學(xué)報(bào)》(同上，25，PP．220—224)發(fā)表了哥德爾的論文“廣義連續(xù)統(tǒng)假設(shè)的協(xié)調(diào)性證明”(Consistency－proof for the generalized con－tinuum－h(huán)ypothesis)．同年6月14日—20日，哥德爾乘船由美國返回維也納．雖然，哥德爾當(dāng)時(shí)已解決了幾項(xiàng)重大的數(shù)學(xué)問題，三次應(yīng)邀赴美國講學(xué)，他已成為世界知名的數(shù)理邏輯學(xué)家，但他在維也納大學(xué)仍然是一個(gè)無薪水的講師．9月25日他申請(qǐng)晉升為正規(guī)的講師，無人理采．這樣，哥德爾就不得不尋找到美國定居的途徑了．1940年1月哥德爾偕夫人安迪離開維也納到美國定居．1938年3月13日希特勒已吞并了奧地利，哥德爾離開納粹統(tǒng)治下的維也納使他從此有了一個(gè)進(jìn)行研究工作的安定環(huán)境．從此，他再也沒有回過歐洲． 1940年春，哥德爾到達(dá)普林斯頓高級(jí)研究院，成了該院的成員．同年普林斯頓大學(xué)出版社出版了哥德爾的專著《廣義連續(xù)統(tǒng)假設(shè)的協(xié)調(diào)性》(The consistency of continuum hypothesis)，這是根據(jù)他于1938至1939年在普林斯頓高級(jí)研究院講演的原稿整理的，全名應(yīng)是《選擇公理、廣義連續(xù)統(tǒng)假設(shè)與集合論公理的相對(duì)協(xié)調(diào)性》(The consistency of the axiom of choice and of thegeneralized cantinuum－h(huán)ypothesis with the axioms of set theo－ry)．1941年4月他在耶魯大學(xué)的講演是“在什么意義下直覺主義邏輯是構(gòu)造的？” (In what sense is intuitionistic logic cons－true tive？)1942年作出了“在有窮類型論中選擇公理的獨(dú)立性證明”(Proof of the independence of the axiom of choice in－finite type theory)．1944年發(fā)表了“羅素的數(shù)理邏輯”(Russell＇smathematical logic)．1946年在普林斯頓200周年紀(jì)念會(huì)上就數(shù)學(xué)問題作了講演．1947年發(fā)表了重要的數(shù)學(xué)哲學(xué)論文“什么是康托爾的連續(xù)統(tǒng)問題？”(What is Cantor＇s continuum problem？) 哥德爾在普林斯頓最親密的朋友是著名物理學(xué)家A．愛因斯坦(Einstein)和數(shù)理經(jīng)濟(jì)學(xué)家O．摩根斯頓(Morgenstern)．他們經(jīng)常散步和閑談．1948年4月2日他們?nèi)艘黄鸬矫绹泼窬郑黄鹑〉妹绹鴩?，成為美國公民．哥德爾與愛因斯坦一直是最親密的朋友，直至愛因斯坦1955年去世．雖然他們兩人在性格上有很大的差別，愛因斯坦愛社交，活潑開朗，而哥德爾嚴(yán)肅認(rèn)真、相當(dāng)孤獨(dú)，但是他們都是直接地全心全意地探求科學(xué)的本質(zhì)．1943年后，哥德爾逐漸把注意力轉(zhuǎn)向數(shù)學(xué)哲學(xué)乃至一般的哲學(xué)問題．當(dāng)然他也還不斷地關(guān)注邏輯結(jié)果，比如1958年他研究了有窮方法的擴(kuò)充，1963年審閱并推薦了P．J．科恩(Cohen)的重要論文“連續(xù)統(tǒng)假設(shè)的獨(dú)立性”(The independence of the continuumhypothesis)．1973年評(píng)述了A．魯賓遜(Robinson)創(chuàng)立的非標(biāo)準(zhǔn)分析．哥德爾這些工作對(duì)數(shù)理邏輯的發(fā)展都起了重要的作用． 1953年哥德爾晉升為普林斯頓高級(jí)研究院的教授． 1951年哥德爾獲得愛因斯坦的首次獎(jiǎng)，以后多次獲得榮譽(yù)稱號(hào)，如哈佛、洛克菲勒等著名大學(xué)的榮譽(yù)博士、英國皇家學(xué)會(huì)國外會(huì)員、法國研究院的通信成員．哥德爾于1966年還拒絕接受奧地利科學(xué)院授予他的榮譽(yù)成員稱號(hào)．1975年9月18日他獲得了美國總統(tǒng)獎(jiǎng)，當(dāng)時(shí)的總統(tǒng)是福特． 哥德爾妻子安迪于1981年在普林斯頓去世，他們沒有子女． 我們?cè)?jīng)指出，哥德爾是亞里士多德(Aristotle)和G．W．萊布尼茨(Leibniz)以來最偉大的邏輯學(xué)家．但是，這決不僅僅是由于他的聰明才智所決定的，更重要的是數(shù)學(xué)、邏輯學(xué)發(fā)展到20世紀(jì)所面臨的問題、面臨的任務(wù)并由此而出現(xiàn)了一大批優(yōu)秀的邏輯學(xué)家，哥德爾是其中最突出的代表．19世紀(jì)在微積分基礎(chǔ)工作中出現(xiàn)了A．柯西(Cauchy)、K．魏爾斯特拉斯(Weierstrass)、R．戴德金(Dedekind)和G．康托爾(Cantor)這樣一批大數(shù)學(xué)家，他們十分重視數(shù)學(xué)的邏輯嚴(yán)謹(jǐn)性．G．弗雷格(Frege)又建立適應(yīng)數(shù)學(xué)論證的謂詞演算，在邏輯學(xué)中首次引進(jìn)全稱量詞和存在量詞的概念．1900年巴黎數(shù)學(xué)家大會(huì)上希爾伯特提出了23個(gè)未解決的數(shù)學(xué)問題，其中第一個(gè)問題是康托爾的連續(xù)統(tǒng)假設(shè)是否成立，第二個(gè)問題是算術(shù)公理的協(xié)調(diào)性．他指出，在關(guān)于公理系統(tǒng)所能提出的問題中，最為重要的是：證明這些公理不互相矛盾，就是說，以它們?yōu)榛A(chǔ)而進(jìn)行的有限步驟的邏輯推演，決不會(huì)導(dǎo)致矛盾的結(jié)果．1900年前后，先后在康托爾集合論中發(fā)現(xiàn)幾個(gè)令人吃驚的悖論．這樣，出現(xiàn)了數(shù)學(xué)基礎(chǔ)的危機(jī)，為解決這種危機(jī)，L．E．J．布勞威爾(Brouwer)提出了在數(shù)學(xué)中取消無窮對(duì)象、取消數(shù)學(xué)論證中無限制地使用排中律的直覺主義建議，由此形成了數(shù)學(xué)基礎(chǔ)研究中的直覺主義學(xué)派．羅素提出了把數(shù)學(xué)還原為邏輯，形成了邏輯主義學(xué)派．羅素與A．N、懷特海(Whitehead)合著的《數(shù)學(xué)原理》(Principia mathematica)一書中完全應(yīng)用了數(shù)理邏輯的方法，從一些邏輯概念和數(shù)學(xué)公理出發(fā)實(shí)際上推導(dǎo)出很大一部分?jǐn)?shù)學(xué)，而這是沿著弗雷格、G．皮亞諾(Peano)的思路開始的．希爾伯特強(qiáng)調(diào)數(shù)理邏輯在數(shù)學(xué)基礎(chǔ)研究中的巨大作用，但他不贊成邏輯主義，更反對(duì)直覺主義．在希爾伯特看來，悖論的根源不在于實(shí)無窮，而在于對(duì)實(shí)無窮的錯(cuò)誤認(rèn)識(shí)．希爾伯特認(rèn)為直覺主義否定實(shí)無窮，否定排中律等等，是對(duì)數(shù)學(xué)“這門科學(xué)大砍大殺”，就會(huì)使數(shù)學(xué)“失去大部分最寶貴的財(cái)富”．希爾伯特及其學(xué)派制定了一個(gè)保衛(wèi)數(shù)學(xué)建立其嚴(yán)謹(jǐn)基礎(chǔ)的方案，人們稱之為希爾伯特方案．這一方案是要將數(shù)學(xué)理論進(jìn)行形式化處理，建立相應(yīng)的形式公理系統(tǒng)，用有窮方法研究系統(tǒng)的完全性、協(xié)調(diào)性和判定性等問題．這些形式公理系統(tǒng)共同的邏輯基礎(chǔ)是謂詞演算，當(dāng)時(shí)已證明了謂詞演算的可靠性(或稱一致性)，即任一邏輯定理在所有的解釋(或稱賦值)下都是真的(稱之為普遍有效的)．但是，謂詞演算是否具有完全性呢？也就是說，謂詞演算中普效命題是否是邏輯定理呢？這是1920年前后人們關(guān)注的一未解決的重大問題，直至1928年在前述的希爾伯特與阿克曼的專著第二版中仍然是末獲得解決的問題．1929年哥德爾肯定地解決了這一問題，證明了謂詞演算的完全性定理．這一結(jié)果，對(duì)于希爾伯特方案是一有力的支持，因?yàn)樗砻髁讼柌厮罁?jù)的邏輯基礎(chǔ)是既可靠又完全的一門獨(dú)立的數(shù)學(xué)理論． 哥德爾完全性定理在謂詞演算的語法概念與語義概念之間架起了一座橋梁．這里語法概念指形式系統(tǒng)，語義概念指數(shù)學(xué)模型．這就是說，哥德爾定理是在形式系統(tǒng)與數(shù)學(xué)模型之間架起了一架橋梁． 形式系統(tǒng)的一合式公式(或稱命題，也稱語句)集合 S叫做協(xié)調(diào)的，如果此系統(tǒng)內(nèi)不存在一合式公式A，使得從S出發(fā)公式A與A的否定式 A都是可證的．S不是協(xié)調(diào)的就叫它是不協(xié)調(diào)的．一不空集合M及M上定義的關(guān)系、函數(shù)等一起可以構(gòu)成一結(jié)構(gòu)．形式系統(tǒng)的一命題A，在結(jié)構(gòu)M上做解釋，對(duì)于這一解釋而言，命題A經(jīng)解釋后在結(jié)構(gòu)M中是真的，就稱結(jié)構(gòu)M為A的一模型．若S中每一命題經(jīng)解釋后在結(jié)構(gòu)M中都是真的，就稱M是S的一模型．顯然，結(jié)構(gòu)、解釋、模型都是語義概念．依據(jù)上述概念，哥德爾完全性定理是說：對(duì)于謂詞演算的任一命題集合S而言，都有： S是協(xié)調(diào)的當(dāng)且僅當(dāng)S有模型． 這里所講的謂詞演算是一階古典謂詞演算，也稱為狹謂詞演算，“一階”是相對(duì)“高階”而言的，即量詞的變域是個(gè)體域，而不能是謂詞，也不能是函數(shù)詞，“古典”是相對(duì)“直覺主義”或“各種非經(jīng)典或非標(biāo)準(zhǔn)”而言的． 哥德爾完全性定理是當(dāng)代模型論的基本定理之一，由它導(dǎo)出了一系列重要結(jié)果． 還應(yīng)當(dāng)指出，哥德爾完全性定理是對(duì)形式系統(tǒng)的整體特征性定理(而不是系統(tǒng)內(nèi)的形式定理)，這種定理稱之為元定理或元數(shù)學(xué)定理．按照希爾伯特方案和當(dāng)時(shí)人們的思想觀念，元定理應(yīng)局限在有窮方法內(nèi)給出證明，排中律與無窮過程是不能被使用的．然而，這一定理是很強(qiáng)的，用有窮方法是不可能給出證明的．哥德爾看出了這一問題，大膽地采用無窮方法找出問題的答案，給出了定理的證明．對(duì)此，哥德爾曾在致王浩的信中說道，他解決了完全性在于他的哲學(xué)思想先進(jìn)，不拘泥于有窮方法，而并不是他的數(shù)學(xué)技巧比別人高明(見 Wang Hao，F(xiàn)rom mathematics to philosophy)．在哥德爾晚年，王浩是他的最好的朋友之一，他們之間就數(shù)學(xué)基礎(chǔ)和哲學(xué)問題有許多內(nèi)容深刻的交談． 哥德爾不完全性定理是更令人吃驚的．如前指出，不完全性是指形式算系統(tǒng)而言的，也可以說是指皮亞諾算術(shù)系統(tǒng)P而言的．哥德爾證明：如果P是協(xié)調(diào)的，則有一算術(shù)的形式命題A即A為P中一命題)，并且A與 A在P中都不可證明的．這與希爾伯特的猜想完全相反．希爾伯特猜想，不僅形式數(shù)學(xué)系統(tǒng)的基礎(chǔ)邏輯——謂詞演算是完全的，而且每一個(gè)形式數(shù)學(xué)系統(tǒng)也是完全的，特別是皮亞諾算術(shù)系統(tǒng)P也應(yīng)當(dāng)是完全的，它的命題集合總是可以一分為二，一部分是P的定理集合(即其中每一元都是P的定理，不妨把定理集合記為T)，另一部分是P的可駁集合(即其中每一元都是P的否定理，即它的否定式是P的定理，不妨把P的可駁集合記為R)．希爾伯特猜想，系統(tǒng)P的命題集合恰好就是T與R的并集合：T∪R．這就是說，皮亞諾公理系統(tǒng)巳完全刻畫了算術(shù)系統(tǒng)．但是，哥德爾否定了希爾伯特的猜想，從而否定了希爾伯特方案．哥德爾具體地嚴(yán)謹(jǐn)?shù)刈C明了存在一命題A，A和它的否定式 都不在T中，也不在R中．也就是說，P的命題集合不可能按照其元(即命題)是可證可駁的原則分為兩部分，這是一重大的結(jié)果．哥德爾怎樣獲得這一結(jié)果呢？ 為了證明上述定理，哥德爾區(qū)分了形式系統(tǒng)內(nèi)外的幾個(gè)層次和它們間的聯(lián)系．第一步，形式系統(tǒng)的概念是使用無數(shù)學(xué)概念建立起來的．這些元數(shù)學(xué)概念是若干個(gè)符號(hào)的規(guī)定、轉(zhuǎn)換和說明．第二步，是把元數(shù)學(xué)概念通過配數(shù)方法(這一方法也是哥德爾給出的)給出算術(shù)化處理，用自然數(shù)的函數(shù)與關(guān)系把它們描述出來，并證明這些函數(shù)與關(guān)系的機(jī)械性質(zhì)，即它們是遞歸函數(shù)與遞歸關(guān)系．第三步，證明遞歸函數(shù)與遞歸關(guān)系在形式數(shù)論系統(tǒng)內(nèi)都是數(shù)詞可表達(dá)的．哥德爾通過這些精湛的數(shù)學(xué)技巧，從錯(cuò)綜復(fù)雜的聯(lián)系中弄清“命題A在P中是可證的”、“公式序列Г是命題A在P中的一證明”等關(guān)于形式系統(tǒng)P的元數(shù)學(xué)概念都可以算術(shù)化為關(guān)于自然數(shù)間的關(guān)系與函數(shù)．并且它們又都是在P中可表達(dá)的，從而他構(gòu)造了他的定理所要求的命題AP，并得到了上述不完全性定理的證明．由此，哥德爾證明：AP，與 AP在P中都是不可證明的，從語法上講，AP與 AP都是不可證的，而從語義上，AP與 AP必然有一個(gè)是真的(事實(shí)上由哥德爾的構(gòu)造過程可知，AP是真的)．因此，哥德爾第一次澄清了真與可證是兩個(gè)不同的概念．對(duì)于形式系統(tǒng)而言，可證性是一個(gè)較為機(jī)械的思維過程，而真理性則是一個(gè)能動(dòng)的和超窮的思維過程，二者不能混為一談．此外，命題AP對(duì)自己也是有所斷定的，這就反對(duì)了羅素與懷特海關(guān)于命題不能對(duì)自己有所斷定的意見． 上述哥德爾不完全性定理在文獻(xiàn)中常稱為哥德爾第一不完全性定理．哥德爾還證明了另一個(gè)定理，文獻(xiàn)中稱之為第二不完全性定理，這一定理是說，如果系統(tǒng)P是協(xié)調(diào)的，那么它的協(xié)調(diào)性在系統(tǒng)P中是不可證明的．它的證明是通過把“P是協(xié)調(diào)的”這一元數(shù)學(xué)概念加以算術(shù)化，然后在P中形式化，得到它的形式公式可記為“con(P)”．我們?cè)侔训谝欢ɡ淼淖C明，即 (*)“若P是協(xié)調(diào)的，則AP是不可證的” 加以形式化，也就是把(*)的整個(gè)證明在系統(tǒng)P內(nèi)形式化，則我們應(yīng)獲得 (**)P con(P)→AP． 現(xiàn)在，設(shè)P con(P)，這時(shí)，由(**)叫將獲得P AP，這就得到與第一定理相矛盾的結(jié)論．從而就得到了第二定理的證明． 哥德爾的上述結(jié)果對(duì)邏輯學(xué)和數(shù)學(xué)特別是數(shù)學(xué)基礎(chǔ)產(chǎn)生了巨大的影響，使邏輯學(xué)、數(shù)學(xué)基礎(chǔ)學(xué)在新的起點(diǎn)上獲得了新的發(fā)展，揭示了機(jī)械的與非機(jī)械的思維活動(dòng)的基本性質(zhì)，論證了形式系統(tǒng)的邏輯標(biāo)準(zhǔn)與局限性問題，這些都是人類認(rèn)識(shí)史上的重大結(jié)果．對(duì)于機(jī)械的思維活動(dòng)，哥德爾在證明不完全性定理時(shí)，采用了遞歸方法并開展詳盡的論述．根據(jù)J．埃爾布朗(Herbrand)和哥德爾的意見，S．C．克林(Kleene)對(duì)一般遞歸函數(shù)理論作了深入的研究，A．丘奇(Church)建立λ演算理論，A．M．圖靈(Turing)建立另一種機(jī)械性思維過程，以描述算法，現(xiàn)在人們稱之為圖靈機(jī)器．人們很快就證明：上述幾種機(jī)械性思維過程的概念和理論都是等價(jià)的，可以相互轉(zhuǎn)換的．近年來，人們進(jìn)一步發(fā)現(xiàn)了一系列可以相互轉(zhuǎn)換的算法概念與理論，并且愈來愈展現(xiàn)出他們?cè)谟?jì)算機(jī)領(lǐng)域內(nèi)的巨大作用． 關(guān)于連續(xù)統(tǒng)假設(shè)相對(duì)于集合論通常公理系統(tǒng)的協(xié)調(diào)性證明以及在證明過程中所創(chuàng)立的可構(gòu)成性方法，是哥德爾的又一重大貢獻(xiàn)．連續(xù)統(tǒng)問題是康托爾首先提出的，這涉及到無窮集合、無窮基數(shù)中一些根本問題．在許多無窮集合的比較中，以什么為標(biāo)準(zhǔn)呢？康托爾提出按一一對(duì)應(yīng)來區(qū)分集合的“大小”，與自然數(shù)集合有一一對(duì)應(yīng)關(guān)系的集合稱為可數(shù)集合，諸如此種集合的基數(shù)定義為 ，把所有具有基數(shù)為 的集合收集在一起所組成的哪個(gè)集合的基數(shù)為 ，以此類推，可以獲得無窮基數(shù)序列： 其中α為任意的序數(shù)．另一方面，實(shí)數(shù)集合的基數(shù)，也就是自然數(shù)集合的所有子集合所構(gòu)成的哪個(gè)集合的基數(shù)為2，康托爾證明它大于，然而它究竟等于式(1)中哪個(gè)基數(shù)呢？因?yàn)槭?1)是一嚴(yán)格遞增的基數(shù)序列，并且2大于，因此，就有 1878年康托爾猜想式(2)中的等號(hào)應(yīng)當(dāng)成立．也就是說，他猜想： 就是康托爾的連續(xù)統(tǒng)假設(shè)．1883年，康托爾在他的論文“關(guān)于無窮線性點(diǎn)集合(5)”( berunendliche lineare Punktmannigfaltig－keiten 5，Mathematische Annalen，21(1883)，pp 545—586)中，希望不久將能夠公布他的猜想的嚴(yán)格證明．隨后，他還一再聲明將公布他的證明．但是，直至1918年1月6日康托爾去世，他也沒有把他的證明公布于眾．大概是他發(fā)現(xiàn)了原來的證明有錯(cuò)誤而未公開發(fā)表． 1900年夏季在巴黎舉行的第二次國際數(shù)學(xué)家代表大會(huì)上，希爾伯特做了題為《數(shù)學(xué)問題》(Mathematische Probleme， Archivder Mathematik und Physik，Series 3，1，pp．44—63，213—237)的演說，提出了前面曾經(jīng)說過的23個(gè)未解決的問題，向20世紀(jì)的數(shù)學(xué)家們提出挑戰(zhàn)．其中第一個(gè)問題就是“證明連續(xù)統(tǒng)假設(shè)”．他說：“康托爾關(guān)于這種集合的研究，提出了一個(gè)似乎很合理的定理，可是盡管經(jīng)過堅(jiān)持不懈的努力，還是沒有人能夠成功地證明這條定理．這一定理就是：每個(gè)由無窮多個(gè)實(shí)數(shù)組成的系統(tǒng)，亦即實(shí)數(shù)集合R的無窮子集合(或點(diǎn)集合)，或者與自然數(shù)1，2，3，……組成的集合對(duì)等(即有一一對(duì)應(yīng)的關(guān)系)，或者與全體實(shí)數(shù)組成的集合對(duì)等，從而與連續(xù)統(tǒng)(即一條直線上的點(diǎn)的全體)相對(duì)等；因此，就對(duì)等關(guān)系而言，實(shí)數(shù)的無窮子集合只有兩種：可數(shù)集合和連續(xù)統(tǒng)．”他接著又說：“由這條定理，立即可以得出結(jié)論：連續(xù)統(tǒng)所具有的基數(shù)，緊接在可數(shù)集合的基數(shù)之后；所以，這一定理的證明，將在可數(shù)集合與連續(xù)統(tǒng)之間架起一座新的橋梁．”1925年，已經(jīng)63歲、身患多種病的希爾伯特又提出了試圖證明連續(xù)統(tǒng)假設(shè)的大綱，這就是他1926年的論文“論無窮”( ber das Unendiche，Mathematische Annalen，95，pp．161—190)．遺憾的是他的證明有漏洞，證明是錯(cuò)誤的．這一切都表明連續(xù)統(tǒng)問題是很有意義的、難度很大的問題．1934年波蘭學(xué)者W．謝爾品斯基(Sierpinski)出版他的專著《連續(xù)統(tǒng)假設(shè)》(Hypothese du continu)，揭示了在分析數(shù)學(xué)中有12個(gè)數(shù)學(xué)命題與連續(xù)統(tǒng)假設(shè)等價(jià)，有81個(gè)命題是它的直接推論．這就更突出了它的重大意義．對(duì)于這一問題，哥德爾所取得的重大進(jìn)展是連續(xù)統(tǒng)假設(shè)與集合論的通常公理系統(tǒng)(包括選擇公理)是協(xié)調(diào)的，也就是說，集合論的通常的公理系統(tǒng)(包括選擇公理)推不出連續(xù)統(tǒng)假設(shè)的否定式．在證明過程中，哥德爾引進(jìn)了可構(gòu)成集合、可構(gòu)成公理等重要概念．對(duì)于任意一集合S而言，集合S1叫做S的可定義子集合，如果有一公式(x1，…，xn，x)和S的元素a1，…，an，使得 S1=｛x|x∈SΛ(a1，…，am，x)｝ 成立，令S＇為S的所有可定義子集合所組成的集合．令 L0= ， (4．1) La+1=(La)＇， (4．2) 一集合x叫做是可構(gòu)成的，如果存在一序數(shù)α，使得x∈La． 可構(gòu)成公理是說，每一集合都是可構(gòu)成的，常常記做V=L．哥德爾首先證明通常集合論公理(不包括選擇公理)都在L中成立，然后證明，可構(gòu)成公理蘊(yùn)涵選擇公理與連續(xù)假設(shè)．文獻(xiàn)中常把選擇公理記做 AC(Axiom of Choice的縮寫)，連續(xù)統(tǒng)假設(shè)記做CH(Continuum Hypothesis的縮寫)，并且把通常的集合論公理系統(tǒng)理解為策梅羅-弗倫克爾(Zermelo－Fraenkel)系統(tǒng)(通常簡記為ZF，不包括選擇公理，當(dāng)把它理解為包括選擇公理時(shí)，也常記做ZFC)．使用上述記號(hào)，就有 V=L→ACΛCH， (5) 在ZF中可證明．第三步，哥德爾還證明了：V=L在L中成立．從而就得到了選擇公理與連續(xù)統(tǒng)假設(shè)在L中成立．因?yàn)閂=L并非是一真命題，只是在L中真，所以AC與CH也并非真命題，它們只是在L中真．哥德爾的結(jié)果給人們一種寬慰，不會(huì)因?yàn)槭褂眠x擇公理增加不可靠性，也就是說，人們使用ZF公理所建立的數(shù)學(xué)理論沒有矛盾時(shí)，再進(jìn)一步地使用選擇公理，即在使用ZFC時(shí)所建立的數(shù)學(xué)理論也沒有矛盾．哥德爾建立的AC與ZF的相對(duì)協(xié)調(diào)性證明也是一項(xiàng)重大結(jié)果． 哥德爾的結(jié)果還有更廣泛的結(jié)論，這就是在L中不僅CH成立，而且廣義連續(xù)統(tǒng)假設(shè)(Generalized Continuum Hypothesis，?？s寫為GCH)也成立．其中GCH是F．豪斯多夫(Hausdorff)在1908年提出的，對(duì)于任意的序數(shù)a，應(yīng)有等式 成立．事實(shí)上，康托爾在1883年也曾說應(yīng)有 成立．顯然，式(3)與(7)都是式(6)的特殊形式．哥德爾在前邊提到的1940年的專著中證明的是V=L→ACΛGCH．他的結(jié)果較之更為廣泛． 哥德爾創(chuàng)立的可構(gòu)成方法開辟了集合論研究的新方法、新方向，文獻(xiàn)中常稱為內(nèi)模型方法．1940年以后人們對(duì)它進(jìn)行了系統(tǒng)的研究，獲得了極小內(nèi)模型等重要結(jié)果，在這些結(jié)果與方法的基礎(chǔ)上，P．J．科恩(Cohen)1963年創(chuàng)立了力迫方法，證明了廣義連續(xù)統(tǒng)假設(shè)、選擇公理相對(duì)于通常集合論公理的獨(dú)立性結(jié)果．當(dāng)我們用符號(hào)“ ”表示“推不出”時(shí)，哥德爾的定理就是： 而科恩的定理是： 這就是100多年以來，人們對(duì)選擇公理與連續(xù)統(tǒng)假設(shè)的主要結(jié)果．康托爾提出的連續(xù)統(tǒng)的勢到底等于什么呢？或者說，2 到底是無窮基數(shù)序列式(1)中哪一個(gè)呢？這仍然是一個(gè)未解決的重大的數(shù)學(xué)問題．關(guān)于這一點(diǎn)，哥德爾早在1947年的哲學(xué)性論文“什么是康托爾的連續(xù)統(tǒng)問題？”(What is Cantor＇s Continuum prob－lem？)中就指出：“康托爾連續(xù)統(tǒng)問題，不論采取什么哲學(xué)觀點(diǎn)，不可否認(rèn)地至少保持這個(gè)意義：去發(fā)現(xiàn)它是否有一個(gè)答案，如果有，那么是什么答案，是能從所引用的系統(tǒng)中所陳述的公理推導(dǎo)出來的．” “自然，如果按這個(gè)方法解釋，那么(假定公理的協(xié)調(diào)性)對(duì)于康托爾猜測就先驗(yàn)地存在著三種可能性：它是可證明，或者是可否證的，或是不可判定的．” 哥德爾的結(jié)果說明不可能是“否證的”，科恩的結(jié)果說明不可能是被“證明的”，因此，就是“不可判定的”了．哥德爾著重指出，從所采取的集合論公理對(duì)康托爾猜測的不可判定性的證明，“決不是問題的解決”．它仍然是當(dāng)代數(shù)學(xué)的一大難題．這在某種程度可歸之于純數(shù)學(xué)的困難．此外，哥德爾說：“看來這里還含有更深刻的原因，并且只有在對(duì)它們中出現(xiàn)的詞項(xiàng)(如“集合”、“一一對(duì)應(yīng)”，等等)和支配這些詞項(xiàng)的使用的公理的意義進(jìn)行(比數(shù)學(xué)通常作的)更深刻的分析，才能得到這些問題的完全解決．”在哥德爾看來，如果我們所解釋的集合論的原始詞項(xiàng)的意義被認(rèn)為是正確的話，那么就可以得出，集合論的概念和定理描述了某個(gè)完全確定的實(shí)在(即論域)，在其中康托爾猜測必然或者是真的，或者是假的．“因此，從今天所采取的公理得出康托爾猜測的不可判定性，只是意味著這些公理沒有包括那個(gè)實(shí)在的完全描述．”他又說：“可能存在就其證明的結(jié)果來說是如此豐富的其它公理，它照亮整個(gè)領(lǐng)域并產(chǎn)生這樣強(qiáng)有力的解決問題的方法(并且，只要是可能的，甚至可以構(gòu)造地解決它們)，使得不論它們是否是內(nèi)在必須的，至少應(yīng)在如同任何已經(jīng)完全建立的物理理論同等的意義上接受它的．”哥德爾在分析了與連續(xù)統(tǒng)假設(shè)有關(guān)的許多數(shù)學(xué)命題之后指出： “與大量的蘊(yùn)涵連續(xù)統(tǒng)假設(shè)的否定似乎真的命題相反，沒有一個(gè)已知的似乎真的命題蘊(yùn)涵連續(xù)統(tǒng)假設(shè)．”因此，在新的系統(tǒng)中，“有可能否證康托爾猜測”． 哥德爾40年前的論斷，仍然是當(dāng)今集合論學(xué)者關(guān)心的課題．以S．斯拉(Shelab)為代表的一批學(xué)者提出了一條稱為正常力迫的公理，由此可推出 ．但是，正常力迫公理是否具有公理的資格，也是當(dāng)前人們極為關(guān)心的問題． 我們不難看到，哥德爾在“什么是康托爾的連續(xù)統(tǒng)問題”這一哲學(xué)論文中是緊緊抓住連續(xù)統(tǒng)這一難題展開的，他所揭示的觀點(diǎn)對(duì)于數(shù)學(xué)研究是有指導(dǎo)意義的，他的思想極為深刻．哥德爾在他的另一篇哲學(xué)論文“羅素的數(shù)理邏輯”(Russell’s mathematicalIogic，1944)中著重分析了羅素的邏輯思想的發(fā)展，指出了數(shù)理邏輯在實(shí)際發(fā)展中曾采取的方法，“…最重要的簡單類型論和公理化集合論，它們二者至少在這個(gè)范圍內(nèi)是成功的，即它們?cè)试S推導(dǎo)現(xiàn)代數(shù)學(xué)同時(shí)避免一切已知的悖論．但許多跡象只是更加清楚地表明，一些原始的概念尚需進(jìn)一步闡明”．哥德爾進(jìn)一步發(fā)揮了萊布尼茨的思想：“人類將有一種新的工具，同任何視覺工具對(duì)視力的幫助相比，更大大增強(qiáng)推理的能力．”哥德爾等人開創(chuàng)的機(jī)械思想過程的研究和現(xiàn)代計(jì)算機(jī)的結(jié)合正在不斷地發(fā)展著新型的推理工具． 哥德爾的工作還有許多方面有引人注目的創(chuàng)造成果，比如：(1)加速度定理，或稱證明長度定理，在1936年的論文“關(guān)于證明的長度”( ber die L nge von Beweisen)中哥德爾建立了類型、強(qiáng)度都逐一增加的系統(tǒng)：S1，S2，…，Si，Si＋1，…．主要結(jié)果是：在Sn與Sn+1(n∈ω)中都存在諸命題，它們?cè)谙到y(tǒng)Sn與Sn+1中都是可證的．但在Sn+1的證明長度要比Sn中的長度短得多．人們認(rèn)為，這一結(jié)果對(duì)于計(jì)算機(jī)科學(xué)可能產(chǎn)生重要的影響．(2)關(guān)于判定問題的可解情況，哥德爾發(fā)表了論文“對(duì)于理論邏輯判定問題的一個(gè)特別情況”(Ein Spezialfall des Entschei－dungsproblems der theoretischen Logik，1932)和“關(guān)于謂詞邏輯演算的判定問題”(Zum Entscheidungsproblem des logischnFunktionenkalküls，1933)，解決狹謂詞演算中可判定的命題類的最重要表達(dá)形式．所謂狹謂詞演算的判定問題就是要尋找一個(gè)一般的方法，對(duì)于任意給定的命題，我們都可以在有窮步驟內(nèi)判定它是否是可滿足的．1936年，圖靈證明了狹謂詞演算是不可判定的．在圖靈之前，人們一方面尋求可判定的特殊類，一方面尋求歸約類(即將狹謂詞演算的整個(gè)公式類歸約到這一特定的類，如前束范式類就是一個(gè)舊約類)．阿克曼已經(jīng)指出前束詞 歸約類．這就建立了關(guān)于可滿足性的可判定類與歸約類之間的一個(gè)明確 都是歸約類的結(jié)果(參見王浩《數(shù)理邏輯通俗講話》，科學(xué)出版社，1981)．此外，哥德爾還對(duì)直覺主義邏輯等領(lǐng)域有重要工作，這里不一 一列舉了． 綜上，我們不難看出，哥德爾的工作影響和推動(dòng)了數(shù)理邏輯近60年的發(fā)展，使它從較為分散的研究工作擴(kuò)大為獨(dú)立的系統(tǒng)的學(xué)科，并且產(chǎn)生了若干研究分支，對(duì)計(jì)算機(jī)科學(xué)與技術(shù)已經(jīng)產(chǎn)生并將繼續(xù)產(chǎn)生深刻的影響．他作為亞里士多德、萊布尼茨以來的最偉大的邏輯學(xué)家影響將是深遠(yuǎn)的． |
|
|
