哥德爾不完全性定理的科學推理意義

哥德爾不完全性定理的科學推理意義

N09A1000-0763(2010)02-0015-06哥德爾(KurtGdel，1906-1978)是美國著名數(shù)學家，他于1931年發(fā)表了形式數(shù)論系統(tǒng)的不完全性定理(Gdel’sincompletenesstheorem)。它包括第一定理：形式數(shù)論系統(tǒng)和它的任意協(xié)調的擴充系統(tǒng)里，都有不含自由變元的公式(即閉公式)A使得A和它的否定式┐A都不是定理；第二定理：形式數(shù)論系統(tǒng)的協(xié)調性的證明不可能在形式數(shù)論系統(tǒng)中實現(xiàn)。或把它描述為：如果對自然數(shù)理論形式化而獲得的系統(tǒng)是相容的，則該系統(tǒng)必包含一邏輯公式A，使得A和它的否定┐A在系統(tǒng)中都不能證明。這個定理不僅表明，作為自然數(shù)理論的公理而言，通常的公理系統(tǒng)是不完全的，而且在有窮觀點下表明對自然數(shù)理論的形式化系統(tǒng)，在相容性范圍內無論怎樣添加公理，它仍然是不完全的。哥德爾不完全性定理的發(fā)表，立即震驚了世界數(shù)壇，其中尤其要提到偉大數(shù)學家馮·諾意曼的反應。馮·諾意曼在20世紀20年代后期，參與了希爾伯特的元數(shù)學計劃，發(fā)表了幾篇關于證明部分數(shù)學公理無矛盾性的論文。哥德爾不完全性定理發(fā)表后，馮·諾意曼中止了這方面的研究。他幾次親自驗證了這條定理，對哥德爾出色的成就表示完全折服，在1931年秋季普林斯頓討論班上，馮·諾意曼本該報告自己的重要工作，但他卻沒有這樣做，他利用此機會認真介紹了哥德爾的這個成果，大力加以肯定和贊揚，哥德爾不完全性定理是很有份量的，它開辟了數(shù)理邏輯的新紀元，使數(shù)理邏輯形成一門獨立的科學。我們知道，所謂形式系統(tǒng)，即用形式符號對直觀數(shù)學系統(tǒng)的模擬。為了使證明嚴格化，為了使數(shù)學對象能夠概括更多的模型，人們力圖機械地判定哪些合式公式串是證明，哪些不是，這就要用到形式系統(tǒng)，因為它有公理集和由包括公理在內的已知定理產生新定理的推理規(guī)則集，因而形式系統(tǒng)的完全性說明其中的形式推理完全地反映了通常的演繹推理，這就決定了形式系統(tǒng)的推理價值。哥德爾定理揭示了形式系統(tǒng)最重要的特性——抽象性、協(xié)調性和完全性的內在機理，也給人們用推理作為工具來認識“無限”帶來了深層次的思考和提供了一些很有意義的思路。哥德爾獲得不完全性定理是有精湛的數(shù)學技巧的，他證明了不完全性定理并深刻地研究了所用的推理方法。我們知道，數(shù)學家最關心的事之一就是公理系統(tǒng)的無矛盾性和完全性。所謂的完全性就是，如果在每個結構中均可滿足的那些閉公式在一個邏輯體系中都是可證的，則稱該邏輯系統(tǒng)是完全的。也就是說，每一個真的邏輯數(shù)學命題都可以由這個公理系統(tǒng)導出，亦即可證。哥德爾證明第一定理，首先，他覺得：形式系統(tǒng)的概念是用元數(shù)學(metamathematics)概念建立起來的，這些元數(shù)學概念是若干個符號的規(guī)定、轉換與說明。這里所說的元數(shù)學是與希爾伯特方案(Hilbert’sProgram)相聯(lián)的?！翱茖W思想是科學以前的思想的發(fā)展?！盵1]哥德爾的許多工作和杰出成就，是他從研究希爾伯特的思想開始的。把數(shù)學的各個分支和研究領域分別進行形式化處理，建立相應的形式系統(tǒng)，并與邏輯演算相結合，形成各門形式化的數(shù)學公理系統(tǒng)，它們都是符號系統(tǒng)，在那里，每一數(shù)學定理都可在相應的形式系統(tǒng)中表示出來，并能從語法上得到證明。建立在對這樣的形式數(shù)學系統(tǒng)給出工具并進行研究的有窮邏輯和(不含無窮對象的)初等數(shù)論，這樣的邏輯與數(shù)論稱為元數(shù)學(元數(shù)學又稱為證明論。它的研究對象是數(shù)學證明本身。它研究數(shù)學的最基本活動——證明的合理性問題)。用元數(shù)學去研究形式數(shù)學系統(tǒng)內的協(xié)調性、完全性問題，哥德爾進行算術化處理是巧妙地通過哥德爾配數(shù)法進行的。關于哥德爾配數(shù)法，這是哥德爾推理證明極重要的訣竅。這里，他使用了“算術化”的方法。對于任一公式都可以配給它一確定的自然數(shù)，反過來，這種自然數(shù)都唯一地對應一公式，即公式與自然數(shù)之間有一一對應關系。研究一個形式系統(tǒng)實際上就是研究可數(shù)個對象的集合。哥德爾認為：“一個系統(tǒng)的公式……從外觀上看是原始符號的有窮系列……不難嚴格地陳述，哪些原始符號的系列是合適公式，哪些不是。類似地，從形式觀點看來，證明也只不過是一串公式的有窮序列?！盵2]“哥德爾配數(shù)法”就是給每個對象配上一個數(shù)，以此來研究原形式系統(tǒng)的性質。給公式所配的自然數(shù)，就叫做該公式的哥德爾數(shù)，而證明是由公式序列組成的，因而對每個公式的證明也可配上唯一的一個哥德爾數(shù)。這樣，哥德爾把元數(shù)學概念通過哥德爾配數(shù)法給出算術化處理，用自然數(shù)的函數(shù)與關系把它們描述出來，并證明這些函數(shù)與關系的機械性質，即它們都是遞歸關系。這里，以自然數(shù)為變元，取值也是自然數(shù)的所謂“遞歸的”數(shù)論函數(shù)，即原始遞歸函數(shù)(后來，作為原始遞歸函數(shù)的自然推廣，哥德爾定義并發(fā)展了一般遞歸函數(shù)理論)。定義域為自然數(shù)集合并取值為自然數(shù)的函數(shù)t，如果對于任一自然數(shù)n都可在有窮步內機械地獲得它的值f(n)，則稱f為一遞歸函數(shù)。當一關系的特征函數(shù)為一遞歸全函數(shù)時，就稱這一關系為遞歸關系。接下去，哥德爾證明遞歸函數(shù)與遞歸關系在形式系統(tǒng)P中都是可表達的。他成功地使用遞歸函數(shù)將元數(shù)學算術化這個有效方法引進數(shù)學基礎中。哥德爾善于抓住問題中心的技巧甚至影響到愛因斯坦，愛因斯坦在普林斯頓與哥德爾結識后，他在數(shù)學中很快就可以辨認出什么是中心問題了。當然，明了了哥德爾怎樣展開對定理的證明，也應探究哥德爾怎么構造出他的定理中所要求的命題A：有一形式命題A，使得A與┐A在此系統(tǒng)內部都是不可證明的。要構造出此命題，需要梳理極其錯綜復雜的聯(lián)系，并且弄清這些聯(lián)系。比如，要將“命題A在P中是可證的”、“公式序列L是命題A在P中的一證明”等這樣一些關于形式系統(tǒng)P的元數(shù)學概念都可以算術化為關于自然數(shù)間的函數(shù)與關系等弄清楚，是不容易的。哥德爾獨到的思路是區(qū)分系統(tǒng)內外的幾個層次和它們間的聯(lián)系，而著手點是從考慮數(shù)學分析的協(xié)調性問題開始的。在考慮分析的協(xié)調性時，哥德爾是先用有限主義的算術證明算術的協(xié)調性，再用算術的協(xié)調性證明分析的協(xié)調性，也就是說，他不是直接去證分析的協(xié)調性，而是分兩步走。這個明智之舉使他在去證明算術的協(xié)調性時很快就得到了相反的結果，從而構造出不完全性定理。哥德爾不完全性定理命題構造和定理證明的數(shù)學技巧，是精湛的。這些成果，在科學推理上意義重大。首先，人們看到了，不完全性定理揭示了完全性與協(xié)調性之間遇到了麻煩，而協(xié)調性本身又是用“推出”說明的。一個公式的集合具有協(xié)調性，是指沒有公式A使得A和┐A都能從這個集合中的公式形式地推出。推理是由一個或幾個已知判斷(前提)推出未知判斷(結論)的思維形式。這是由已知進入到未知的方法，是探尋新結果的方法，因而是極重要的思維形式。然而，因為事物的復雜性情況的差異，它決定了人們進行推理時所依據的前提被人們所了解和掌握程度不同，并且新判斷所得出的結論深刻程度也不同，所以不同的推理的難度是不一樣的，甚至相差十分大。哥德爾不完全性定理使人們碰到了兩不可的情景：在形式系統(tǒng)中完全性與協(xié)調性不可同時兼顧。兩可、兩不可的情景是人們思維深層次的矛盾和推理結果可能淪入的窘境，可取的思想方法不是避免和擺脫，而是設法改進情景。哥德爾不完全性定理在數(shù)學界公認否定了希爾伯特方案的某些設想，但它開辟的卻是另一番富有生機的新生長點?？茖W史上不乏這樣的事實：前進吧，你就會有信心！沿著正確的思路慣性地操作(推理)下去，在普遍性的范圍內陸續(xù)取得成效，然后再回過頭來，不少原先很難解決的問題隨之迎刃而解。在科學推理中，往往要對兩種“情景”尤加重視，即初始條件和邊界條件。事件以某一時刻為開始的初始運動狀態(tài)，叫做初始條件；而受周圍環(huán)境影響的邊界實際狀況則稱為邊界條件。推理的起始狀態(tài)之確立和推理過程進行的邊界條件之改進，對科學研究和科學創(chuàng)新是很有意義的?？疾臁皵z動”和采取“逼近”，是人們通常采用的手段。我們這里說“改進情景”正是這個意思。要達到的目標明確，但證明推理過程遭到困難，其重要的一種思路就是改進情景。哥德爾不完全性定理給了我們這種啟示。哥德爾本人對此也是十分重視的。1930年夏天，哥德爾開始研究證明分析學的協(xié)調性問題。他發(fā)現(xiàn)：希爾伯特想要通過有窮主義的方法來直接證明分析學的協(xié)調性是不可思議的。他總的認為，我們應該把這個困難分解成幾個部分，以便使每一部分能夠變得更容易克服。在這個特殊情況下，他的計劃是通過有窮主義的數(shù)論來證明數(shù)論的協(xié)調性，然后用數(shù)論來證明分析學的協(xié)調性，在這里，我們可以假定數(shù)論不僅是協(xié)調的，而且是真的。他當時給自己提出的問題是分析學對于數(shù)論的相對協(xié)調性，這個問題對于有窮主義數(shù)論的某些不確定的概念來說是獨立的。[5]當數(shù)學上出現(xiàn)一些重大發(fā)現(xiàn)時，它貌似與以往的某些定理甚至是公理發(fā)生了沖突，但它并不是要完全否定、擯棄或推翻原有的定理、公理或者方案，而往往是將原有的那些數(shù)學成果、結論作為有條件的東西保留在知識的長河之中?？茖W推理是講究前提條件的，對前提條件進行情景改進然后再進行正確推理，往往會得到珍貴的副產品，比如，哥德爾原先是在系統(tǒng)為ω協(xié)調的(英為ω-consistent，德為ω-widerspruchsfrei)假定之下證明這條定理的。這個條件，對形式系統(tǒng)而言，比簡單協(xié)調性條件更強。但是，J.B.Rosser則對情景作了改變，他成功地用簡單協(xié)調性代替了更強的ω協(xié)調性[6]。又比如，進一步限制不使用解析中的輔助手段(如無理數(shù)和無窮級數(shù))的自然數(shù)的理論“純數(shù)論”，我們便可以得到較弱的自然數(shù)理論，它們的協(xié)調性可不必使用直到ε。為止超限歸納法這種特殊論證，而使用有窮方法便可以推理證明。同時，用逐步逼近也是一種可考慮的思想方法。數(shù)學發(fā)展史表明，在命題的證明推理過程中，往往會得到一些非常重要的新發(fā)現(xiàn)，有時甚至會有數(shù)學新工具的創(chuàng)造；原定的目標有時不一定理想地達到或較快地達到，但證明推理過程中所得到的或先得到的副產品卻是十分有價值的。其次，我們著重來談“無限”。隨著人的認識的深化，對“無限”的認識愈來愈顯得實在和重要了?？茖W實踐很自然地招引人們把注意力吸引到：在科學認識上，如何通過有限來認識無限；在科學方法上，如何通過有限的手段把握無限。具體說來，人們如何運用推理來認識和把握“無限”呢？它的可能性和方法是怎樣的呢？無限(無窮)即沒有窮盡，它是相對有限(有窮)而言的。在數(shù)學中，有無窮大、無窮小：一個變量在變化過程中其絕對值永遠大于任意大的已定正數(shù)，這個變量叫做無窮大(無限大)；一個變量在變化過程中其絕對值永遠小于任意小的已定正數(shù)，即以零為極限的變量，這個變量叫做無窮小(無限小)。還有無窮序列、無窮集合、無窮序數(shù)、無窮基數(shù)等。而關于無窮過程，人們把無窮作為一個逼近的目標，可逐步逼近而永遠不能達到，叫潛無窮；把無窮作為一個完成了的總體，通過思維能夠把握的，叫實無窮。在極限理論中，大于零小于任意實數(shù)的無窮序列無窮小和大于任意正實數(shù)的無窮序列無窮大，都是潛無窮概念。在非標準分析中，通過邏輯證明，存在一個大于零小于一切實數(shù)的無窮小量，就是實無窮概念。一個集如由無限多個元素組成，這樣的集就叫做無限集。我們知道，要對事物和命題進行證明，有依據事實的、經驗的，也有用嚴格數(shù)學的、非經驗的推理方法。在處理包含無窮多個數(shù)學對象的集合時，象涉及到所謂“一切的”、“全部的”、“所有的”這樣情景時，工具、手段的采用就非常重要了?！皵?shù)學無窮的觀念已經起著舉足輕重的作用，沒有它便沒有科學”。[7]在自然科學中，我們面對的對象是許多有關于無限性的事實；在數(shù)學中，我們必須處理包含無窮多個數(shù)學對象的集合。在自然科學中，人們在摸索一般規(guī)律時往往會從“經驗歸納法”出發(fā)，從特殊到一般；而用嚴格邏輯或數(shù)學推理來證明定理卻大不一樣?！霸跀?shù)學上，一個規(guī)律或一個定理，只有當它能表示為某些已被認為是正確的假設的邏輯的必然結果時，才算是被證明?！盵8]在通過有限的步驟去證明無限時，必須十分明了要從任意有限多個(哪怕是非常多個非常多個)的情形中去得出一個正確的一般規(guī)律，一定要保證“邏輯的必然結果”，因為即使是“任意有限多個”，充其量也是“合理的假說”，還不是“邏輯的必然結果”。一個規(guī)律或一個定律的確定，講究的是它要普遍地成立，因而，推理證明的前提和步驟必須嚴格遵守。那么，數(shù)學上的無窮是不是可以被認識的呢？這是認識論上的問題。實際上，無窮是人們對大量相繼性過程的反復構造中通過外推的思維建立起來的。人們可以通過理性思維的能力相對地把握某一無窮集合的特征，這就是說無窮是可以相對地被認識的。但是，想要通過理性把無窮個客體一一都認識出來，這是不可能的。對無窮客體的認識只能是個逐步推進的過程，而這個過程又是永遠不會完結的。無窮是既可被認識又不可絕對被認識的這種辯證法，讓數(shù)學家們有信心地尋找解決的辦法和工具，比如，把“代數(shù)和”的概念應用于一個收斂的無窮級數(shù)，建立起一個全稱的無窮概念利用排中律來認識無窮，這些手段，是正確的、有效的。數(shù)學上的無窮和哲學上的無窮是不完全一樣的，它們既不同又相聯(lián)系，要把握這些，數(shù)學家的哲學素養(yǎng)往往是很重要的?！盁o論如何，哲學也給科學提供了一些有價值的積極概念，……哲學家反過來也從專門科學采納了比從日常思維采納的任何東西更健全的基礎?！聦嵣?，每一個哲學家都擁有他自己的私人科學觀，每一個科學家擁有他的私人哲學?！盵9]明了這些，我們來闡述哥德爾不完全性定理在證明推理上的意義就會更加深刻。哥德爾不完全性定理本身以及哥德爾對不完全性定理的證明，在科學推理上都有重要意義。首先，哥德爾不完全性定理給人們在認識和處理無窮上啟迪了寶貴的思路：當完全性與可證明發(fā)生沖突時，可以改變論證推理的方式。我們知道，數(shù)學家們都希望，任何真語句都一定可以在某個公理系統(tǒng)范圍內得到確立。但哥德爾定理的一個推理是：不僅沒有一個公理系統(tǒng)足以包含全部數(shù)學，而且也沒有一個公理系統(tǒng)足以包含任何一個有意義的數(shù)學分支，因為任何這樣的公理系統(tǒng)都是不完全的。在系統(tǒng)內存在不可證明的語句(它的概念屬于該系統(tǒng))，但是人們可以通過非形式的論證來證明它是真的——實際上這非形式的論證是通過元數(shù)學的邏輯實現(xiàn)的。哥德爾在獲得不完全性定理時，還研究了所用的方法，從而得出另一個十分重要的結果：設S為包含自然數(shù)理論的形式化系統(tǒng)(在有窮觀點下)，如果S是相容的，則只利用S中可形式化的論證不可能證明S的相容性。這就是說，例如，要從有窮觀點來證明自然數(shù)理論的形式化系統(tǒng)的相容性，就不能不用到一些有窮觀點容許的形式化自然數(shù)理論所不容許的某些論證。按照這種思路在純數(shù)論的相容性的證明中，必須使用純數(shù)論以外的某種論證推理方法，如使用直到ε。為止的超限歸納法。還有，純數(shù)論相容性的證明推理方法也還不限于超限歸納法，例如哥德爾利用了“自然數(shù)域上有窮類型的可計算函數(shù)”而對自然數(shù)論的相容性給出了另外一種證明[10]。其次是哥德爾配數(shù)法。哥德爾數(shù)及其哥德爾的配數(shù)方法，是哥德爾給出的，其思想精髓就是從“一一對應”的方法出發(fā)來進行后面的推理的。如上所述，對于給定的任一公式，都可以配給一確定的自然數(shù)，反過來這種自然數(shù)都唯一地對應一公式，而證明是由公式序列組成的，這樣，對于每個公式的證明來說，也可配上唯一的一個哥德爾數(shù)，因而“一一對應”使得哥德爾數(shù)在證明推理的過程中發(fā)揮著重要作用?！耙灰粚钡姆椒慈ズ孟窈唵?，但思想卻很深刻?！皥猿职炎C明的嚴格性作為完善地解決問題的一種要求，是完全必要的，并且，正是追求嚴格化的努力驅使我們去尋求比較簡單的推理方法，因而嚴格化與簡單性原則是統(tǒng)一的。”[11]此外，哥德爾的高明之處還在于他又通過這些數(shù)反過來看原來形式系統(tǒng)的性質?！八枷肽軌虍a生思想”[12]。他的成功確實可以給人們帶來許多推理證明方法上的啟示。在研究哥德爾不完全性定理的科學推理意義時，有兩件事是值得一提的。其一是：中國古代著名的數(shù)學家劉徽在注釋《九章算術·商功》“陽馬術”時，在充分肯定和靈活運用數(shù)學推理進行數(shù)學證明的過程中曾深沉地發(fā)出感嘆：“數(shù)而求窮之者，謂以情推，不用籌算。”[13]其二是著名數(shù)學家布勞威“搞清楚直觀上確定的不及數(shù)學上證明的時候，哥德爾用他的不完全性定理證明了直觀上確定的勝過數(shù)學的證明”[14]。為什么劉徽意味深長地說到要用“情推”？為什么哥德爾會說到“直觀上確定的勝過數(shù)學的證明”？為什么這些數(shù)學大師在嚴格證明推理得出偉大成果時發(fā)出這樣的感嘆呢？這里，涉及到形式與形象、實際與抽象、現(xiàn)實與原型及模型、經驗與證明等諸多關系問題。眾所周知，在數(shù)學上成立的東西，只有當它已從邏輯的推理上嚴格地被證明了的時候。在數(shù)學上，不僅數(shù)學的概念是抽象的、思辨的，而且數(shù)學的方法也是抽象的、思辨的。要推理證明，需用抽象的形式化語言，比如，數(shù)學符號和數(shù)學符號系統(tǒng)就是抽象的形式化語言，它對數(shù)學本身的存在和發(fā)展十分重要，“常常是由于缺乏能夠說清楚真正實質的符號，數(shù)學的某個領域就得不到發(fā)展。典型的例子就是代數(shù)學：為了寫出‘一般的’代數(shù)方程式，從丟番圖到維耶特和萊布尼茨用了整整三個世紀；……·為了使無窮小的計算獲得一個確定的形式，用了整整100年。這里的主要原因是，在牛頓和萊布尼茨以前，還沒有提出導數(shù)和微分這些新的概念的方便符號，還不能十分清楚地分辨這些概念”。[15]抽象性、形式化體現(xiàn)了數(shù)學的力量，也是一種數(shù)學美。不過，另一方面，它也帶來了危險，“當一個數(shù)學學科遠離它的經驗本源繼續(xù)發(fā)展的時候，或者更進一步，如果它是第二代和第三代，僅僅間接地受到來自‘現(xiàn)實’的思想所啟發(fā)，它就會遭到嚴重危險的困擾。它變得越來越純粹地美學化，……這門學科將沿著阻力最小的途徑發(fā)展，……換句話說，在距離經驗本源很遠很遠的地方，或者在多次‘抽象的’的近親繁殖之后，一門數(shù)學學科就有退化的危險?！盵16]馮·諾意曼認為：“每當?shù)搅诉@種地步時，在我看來，唯一的藥方就是為重獲青春而返本求源，重新注入多少直接來自經驗的思想。”[17]昂利·彭加勒也說：“我希望審查的是，邏輯原則一旦被承認，人們是否真的能夠證明——我不說發(fā)現(xiàn)——所有的數(shù)學真實性而不重新訴諸直覺。”[18]這層思想，在哥德爾不完全性定理的提出過程和這個定理本身，揭示得頗為徹底。哥德爾說：“我在數(shù)學的形式系統(tǒng)中構造不可判定數(shù)論命題的直觀試探原理是與‘可證性’相對立的‘客觀數(shù)學真理’的高度超限概括(這里我說明了直觀性的論證，通過它我達到了不完全性定理這個結果)?！备绲聽柾黄屏藬?shù)學界和邏輯學界長期普遍認為的僅當能用有限的元數(shù)學加以解釋或證明為是正確時才算作是有意義的觀念，不將元數(shù)學的可證性與客觀數(shù)學真理對立起來，而是既看到數(shù)學形式化的重要，又看到數(shù)學直觀的重要，既強調形式的理性思維，又重視直接認識真理的能力，他把這稱為“直觀性的證明”。通過它，他得到了不完全性定理的結果；而不完全性定理本身，也蘊含了這個深邃的思想。這種既講究抽象的證明推理手段又把握“直觀的”、“具體的”思想方法，在菲利克斯·克萊因那兒也受到重視。[19]“抽象化”、“形式化”、“情推”、“直觀上確定的”、“返本求源”、“直觀性論證”，這些都從不同側面反映了數(shù)學思想和數(shù)學方法的特點，健全的數(shù)學思維應當既要講求形式化并運用形式規(guī)則去推導而給出數(shù)學真理，而且要訓練出具有不經過邏輯推理就直接認識真理的能力。元數(shù)學論證的推理和“直觀性論證”的推理(包括“情推”)都不應偏廢。對于給定的形式系統(tǒng)而言，可證性是一個較為機械的思維過程，而它的真理性則是一個能動的和超窮的思維過程，哥德爾揭示了機械的與非機械的思維活動的基本性質，對涉及到理論協(xié)調的邏輯標準與局限性問題有了論證，這項工作是人類科學認識史上的重要結果，意義的確十分重大。把數(shù)學理論形式化，構造形