哥德爾不完全性定理評析

1、哥德爾不完全性定理評析    形式系統(tǒng)的完全性是指系統(tǒng)的有效公式都是該系統(tǒng)的定理，即該系統(tǒng)的所有有效公式在該系統(tǒng)中都可證，否則就是不完全的。1929年，邏輯學(xué)家哥德爾(Kurt Gdel)證明了一階邏輯系統(tǒng)的完全性，即哥德爾完全性定理。然而，1930年他又證明了算術(shù)系統(tǒng)PA的不完全性：如果形式算術(shù)系統(tǒng)PA是相容的，則必定存在閉公式G及其否定G在此系統(tǒng)中均不可證，即如果PA是相容的，則必定存在閉公式G和G在PA中可表達，但卻不能證明它們是PA定理。這就是哥德爾不完全性定理。根據(jù)語義，如果G在系統(tǒng)PA中是可表達的，那么根據(jù)排中律，G不是真的就是假的，即要么G

2、真要么G真。但是，“可證”與“真”是兩個相似卻根本不同的概念，因為由G或G在PA中為真，不能證明二者之一在PA中必然為真。我們這里首先簡介哥德爾不完全性定理，然后澄清關(guān)于哥德爾不完全性定理的一些認識，并探討哥德爾不完全性定理的價值和意義。哥德爾不完全性定理哥德爾不完全性定理的證明過程精細而繁復(fù)，極具技巧性。它的知識背景是一個形式算術(shù)系統(tǒng)PA，包括一階邏輯系統(tǒng)和五個皮亞諾(G.Peano)公理。在證明中，哥德爾首先通過可表達性、遞歸性和哥德爾數(shù)進行了兩步轉(zhuǎn)換。第一步是給PA的每一符號、公式和證明序列都指定一個不同的自然數(shù)，即哥德爾數(shù)，目的“是為了把關(guān)于形式系統(tǒng)內(nèi)的對象的斷定，轉(zhuǎn)換為關(guān)于自然數(shù)的斷

3、定，也就是說，通過編碼，使得對象理論的好些性質(zhì)都能夠在自然數(shù)中反映出來，尤其是，有關(guān)對象理論的元定理也都可以表示為自然數(shù)的定理”1(P78)。哥德爾數(shù)都是自然數(shù)，反之則不然。第二步轉(zhuǎn)換是第一步的逆過程，是通過可表達性和遞歸性再把關(guān)于自然數(shù)的斷定轉(zhuǎn)換為PA中可表達的公式。設(shè)f是定義在自然數(shù)N上的任一函數(shù)或關(guān)系，m和n都是任意自然數(shù)，則f(m，n)在PA中“可表達”就是“直觀算術(shù)函數(shù)可以通過哥德爾數(shù)翻譯(映射)為PA中的公式”(P97)。但是，任意f在PA中都可表達嗎？哥德爾證明了凡遞歸函數(shù)或關(guān)系在PA中都是可表達的。這兩步轉(zhuǎn)換，先把PA公式轉(zhuǎn)換為自然數(shù)，再把自然數(shù)轉(zhuǎn)換為PA公式，有什么意義呢？前

4、面區(qū)分的兩個概念“可表達”與“可證”有助于這里的理解。第一個轉(zhuǎn)換是把PA的元命題真假斷定轉(zhuǎn)換為自然數(shù)命題的真假斷定，而第二個轉(zhuǎn)換卻是將自然數(shù)命題的真假斷定轉(zhuǎn)換為PA的可表達公式。這樣，經(jīng)過兩步轉(zhuǎn)換，PA就成了其自身的元系統(tǒng)，斷定內(nèi)容有了十分重要的改變：由對命題真假的斷定轉(zhuǎn)換為對可表達性的斷定。這兩步轉(zhuǎn)換對于在不完全性定理的證明中使用自指命題但又避免悖論是十分關(guān)鍵的。在兩步轉(zhuǎn)換之后，哥德爾構(gòu)造了一個自指命題G。這是極為關(guān)鍵的，原因是哥德爾不完全性定理的證明必須在PA中找到一個閉公式G，使得G和G在該系統(tǒng)中都不可證。語義上，G和G必有一真。有一真但又不可證，就意味著PA沒有包容所有真命題，即系統(tǒng)P

5、A是不完全的。最后，哥德爾證明，G與G都是PA的不可證命題，即證明了不完全性定理本身或許有人會問，把自指命題G作為新公理加入PA，形成一個PA的擴充系統(tǒng)PA，PA不就是完全的了？事實并非如此。哥德爾證明，增加一條新公理，并沒有改變遞歸關(guān)系及其表達性，因為按相似的程序，可以在PA中找到另外一個不可證命題G，從而PA也是不完全的。因而，哥德爾不完全性定理又可擴充表述為：對任一足夠豐富的相容的形式系統(tǒng)S，必定存在閉公式G以及G在S中可表達，但卻不能證明它們是否是S定理。這里的“足夠豐富”指系統(tǒng)S必須豐富到包含一階算術(shù)系統(tǒng)PA，它既可以真包含PA又可以等于它，但不能比PA簡單，否則就有可能是完全的。哥

6、德爾還給出了不完全性定理的另一種證明：既然真句子集A不能在PA中得到全部表達，而PA的可證命題集B能夠表達，足見B是A的真子集。因此，存在真命題G在PA中不可證；既然G真，其否定G也應(yīng)當(dāng)在PA中不可證。哥德爾指出，這種證明的缺點是沒有擺出一個不可判定命題，而且其中也要明顯地求助于集合，會引起直覺主義者的異議。但是，沒有一個不可判定命題會讓人缺乏某種實在感，更重要的是，不完全性定理表明公理集合論也是不完全的，如果再用集合來證明不完全性定理，則顯然會出現(xiàn)循環(huán)。哥德爾不完全性定理有一個推論：任一包含一階算術(shù)系統(tǒng)的系統(tǒng)S的相容性，在S自身中都不可證。此推論又稱哥德爾第二不完全性定理，而前述不完全性定理

7、又稱哥德爾第一不完全性定理。對哥德爾不完全性定理的幾種誤讀當(dāng)前，談?wù)摳绲聽柌煌耆ɡ硪殉蔀閷W(xué)界的時髦，遺憾的是，其中有一些討論是在沒有真正理解和把握哥德爾定理的基礎(chǔ)上進行的。第一，有人認為哥德爾完全性定理與不完全性定理中的“完全性”是不同的。例如，糾正對哥德爾定理的幾個誤解一文認為：“哥德爾完全性定理表明一階邏輯是完全的，即對任何一階語言的公式，由可證和是的語義結(jié)論是重合的?！?這一觀點可表示為，特別地，當(dāng)是空集時，有，可見，此“完全性”中的語義有效公式與語形可證公式之間是“當(dāng)且僅當(dāng)”的關(guān)系。但是，哥德爾的完全性是指“是否初始設(shè)定的公理系統(tǒng)和推理規(guī)則事實上能夠得到每一邏輯數(shù)學(xué)命題，或者是否可以

8、想象，在所考慮的系統(tǒng)里可能存在不能得出的真命題”4(P583)，也就是說，哥德爾考慮的完全性是指所有的有效公式是否都可證，應(yīng)該用公式表示為，也即在哥德爾完全性定理中，有效公式與可證公式之間只有“如果那么”的關(guān)系，而不是，即無“一階邏輯系統(tǒng)的可證公式都是該系統(tǒng)的有效公式”之意。其實，“”是指可靠性?？煽啃院屯耆远际切问较到y(tǒng)的重要性質(zhì)，缺少哪一個，形式系統(tǒng)就不完善，但可靠性與完全性不是一回事。不完全性定理的完全性與完全性定理的完全性是一致的，否則就是不完全的。不過，完全與否，是相對于系統(tǒng)而言的。相對于一階邏輯有完全性，而相對于一階算術(shù)系統(tǒng)以及復(fù)雜性超過算術(shù)系統(tǒng)的系統(tǒng)就沒有完全性，即具有不完全性。

9、第二，哥德爾語句會導(dǎo)致悖論嗎？我們經(jīng)?？吹接腥苏撟C哥德爾語句會導(dǎo)致悖論。英國學(xué)者霍金(S.Hawking)極具代表性，他說：“哥德爾定理是用自我指認的方法證明成立的。這種命題會導(dǎo)致悖論。例如，如果一命題真，那么可合乎邏輯地推出其假；如果一命題假，那么可合乎邏輯地推出其真。”5(P25)但是，霍金的這個觀點卻是錯誤的。的確，哥德爾語句與說謊者的悖論句極其相似，但二者卻根本不同。張建軍教授在邏輯悖論研究引論中對此做了清晰的比較和分析，即：L是假的：G在PA中是不可證的。看起來好像G只不過把L中的“假”換成了“在PA中是不可證”，即把一個語義概念換成了語形概念，但是，后者并不像前者那樣導(dǎo)致悖論。要理

10、解其緣由，主要是要理解我們前面對語義概念“真”與語形概念“可證”“不可證”所做的區(qū)分。設(shè)L是假的可得L真，再設(shè)L為真可得L是假的，這就得到了悖論。循此思路，如果我們設(shè)G是假的，即“G在PA中是不可證的”是假的，那么可得G在PA中可證為真，這就意味著G是PA中的真理，這樣就從G假推出了G真；但是，如果設(shè)G真，即“G在PA中是不可證的”，由此卻推不出G假，因為G在PA中不可證并不意味著G一定為假。可見，由哥德爾語句G得不出悖論。第三，哥德爾不完全性定理表明心勝于機器嗎？哥德爾和他的工作越來越受人垂青，與計算機和人工智能的發(fā)展有關(guān)。“他最著名的定理表明了數(shù)學(xué)的不可窮盡性，確定了形式系統(tǒng)(或計算機程序

11、)的局限性，所以與心是否勝過機器這個膾炙人口的問題有了關(guān)系”6(P184)。持“心勝于機器”觀點者認為，既然哥德爾不完全性定理表明復(fù)雜的形式系統(tǒng)中存在該系統(tǒng)內(nèi)不能判定的公式，而人心卻可以憑借直覺判斷出該公式的真假，那么就表明人心勝過機器。與此相似，哥德爾本人也曾提倡“理性主義的樂觀主義”，他的推理也與上面相似：人的理性不會一面提出理性不能回答的問題一面又堅持只有理性才能回答這些問題，可見，沒有人心不可判定的問題；但數(shù)學(xué)系統(tǒng)已經(jīng)極其完善，因此人心勝過機器。但是，哥德爾后來承認他的定理沒有了結(jié)心勝過機器的問題6(P185)。之所以如此，是因為哥德爾不完全性定理一方面表明了形式系統(tǒng)的局限性，即任一足

12、夠復(fù)雜的形式系統(tǒng)都有在其自身不可證的真命題，但另一方面，它也顯示了形式系統(tǒng)的巨大威力：低層次的不可證命題可以在高一層次中得到形式證明。可見，哥德爾不完全性定理并沒有直接表明人心是否勝過機器。之所以會產(chǎn)生“心勝于機器”的論點，可以說是因為無視哥德爾不完全性定理所顯示的形式系統(tǒng)巨大威力的結(jié)果。結(jié)語哥德爾不完全性定理影響深遠，它直接摧毀了希爾伯特(D.Hilbert)最初設(shè)想的數(shù)學(xué)目標，使元數(shù)學(xué)擺脫了虛幻的目標而走上了健康發(fā)展道路。哥德爾定理處在整個邏輯學(xué)的中心地位?！案绲聽柦淌诘墓ぷ饕呀?jīng)引起現(xiàn)代邏輯的革命，從數(shù)學(xué)上也從哲學(xué)上大大提高了它的重要性。他所做的數(shù)學(xué)與哲學(xué)出奇地意味深長，美，超脫宿怨。在邏

13、輯的一切現(xiàn)有分支里，他的工作都是基礎(chǔ)和生命力”6(p34)。哥德爾在證明不完全性定理中使用的一些概念，如真、可表達、可證、有效、哥德爾數(shù)、遞歸等，現(xiàn)在都是邏輯學(xué)中的基本概念；哥德爾定理的一些思想促成了一些分支學(xué)科的大發(fā)展，如遞歸論，證明論等。當(dāng)前，國際上已將哥德爾不完全性定理贊譽為現(xiàn)代邏輯科學(xué)在哲學(xué)方面的三大成果之一(另兩個為塔斯基的形式語言的真理論和圖靈機與判定問題)。最新的事例足以說明不完全性定理的深遠影響。2004年，英國學(xué)者霍金發(fā)表文章哥德爾與物理學(xué)的終極，放棄了其研究了多年的終極性萬有理論：萬有理論不存在，永遠找不到這種理論。霍金說，他是在仔細重新研讀了哥德爾不完全性定理后，才改變了自己的觀點，哥德爾定理“很明顯”表明萬有理論是不可能實現(xiàn)的?！緟⒖嘉墨I】1朱水林.哲理的沉思：哲人科學(xué)家哥德爾M.福州：福建教育出版社，1999。2張建軍.邏輯悖論研究引論M.南京：南京大學(xué)出版社，2002。4Kurt Gdel. The completeness of the axi