>>>  史地研究雜志方面文獻收集  >>>

簡體     傳統

---

　　中圖分類號：B81　　文獻標識碼：A　　文章編號：1006-5261(2008)02-0034-03
　　形式系統的完全性是指系統的有效公式都是該系統的定理，即該系統的所有有效公式在該系統中都可證，否則就是不完全的。1929年，邏輯學家哥德爾(Kurt Gdel)證明了一階邏輯系統的完全性，即哥德爾完全性定理。然而，1930年他又證明了算術系統PA的不完全性：如果形式算術系統PA是相容的，則必定存在閉公式G及其否定G在此系統中均不可證，即如果PA是相容的，則必定存在閉公式G和G在PA中可表達，但卻不能證明它們是PA定理。這就是哥德爾不完全性定理。
　　根據語義，如果G在系統PA中是可表達的，那么根據排中律，G不是真的就是假的，即要么G真要么G真。但是，“可證”與“真”是兩個相似卻根本不同的概念，因為由G或G在PA中為真，不能證明二者之一在PA中必然為真。
　　我們這里首先簡介哥德爾不完全性定理，然后澄清關于哥德爾不完全性定理的一些認識，并探討哥德爾不完全性定理的價值和意義。
　　1　哥德爾不完全性定理
　　哥德爾不完全性定理的證明過程精細而繁復，極具技巧性。它的知識背景是一個形式算術系統PA，包括一階邏輯系統和五個皮亞諾(G.Peano)公理。在證明中，哥德爾首先通過可表達性、遞歸性和哥德爾數進行了兩步轉換。
　　第一步是給PA的每一符號、公式和證明序列都指定一個不同的自然數，即哥德爾數，目的“是為了把關于形式系統內的對象的斷定，轉換為關于自然數的斷定，也就是說，通過編碼，使得對象理論的好些性質都能夠在自然數中反映出來，尤其是，有關對象理論的元定理也都可以表示為自然數的定理”[1](P78)。哥德爾數都是自然數，反之則不然。
　　第二步轉換是第一步的逆過程，是通過可表達性和遞歸性再把關于自然數的斷定轉換為PA中可表達的公式。設f是定義在自然數N上的任一函數或關系，m和n都是任意自然數，則f(m，n)在PA中“可表達”就是“直觀算術函數可以通過哥德爾數‘翻譯’(映射)為PA中的公式”[２](P97)。但是，任意f在PA中都可表達嗎？哥德爾證明了凡遞歸函數或關系在PA中都是可表達的。
　　這兩步轉換，先把PA公式轉換為自然數，再把自然數轉換為PA公式，有什么意義呢？前面區分的兩個概念“可表達”與“可證”有助于這里的理解。第一個轉換是把PA的元命題真假斷定轉換為自然數命題的真假斷定，而第二個轉換卻是將自然數命題的真假斷定轉換為PA的可表達公式。這樣，經過兩步轉換，PA就成了其自身的元系統，斷定內容有了十分重要的改變：由對命題真假的斷定轉換為對可表達性的斷定。這兩步轉換對于在不完全性定理的證明中使用自指命題但又避免悖論是十分關鍵的。
　　在兩步轉換之后，哥德爾構造了一個自指命題G。這是極為關鍵的，原因是哥德爾不完全性定理的證明必須在PA中找到一個閉公式G，使得G和G在該系統中都不可證。語義上，G和G必有一真。有一真但又不可證，就意味著PA沒有包容所有真命題，即系統PA是不完全的。最后，哥德爾證明，G與G都是PA的不可證命題，即證明了不完全性定理本身
　　或許有人會問，把自指命題G作為新公理加入PA，形成一個PA的擴充系統PA′，PA′不就是完全的了？事實并非如此。哥德爾證明，增加一條新公理，并沒有改變遞歸關系及其表達性，因為按相似的程序，可以在PA′中找到另外一個不可證命題G′，從而PA′也是不完全的。因而，哥德爾不完全性定理又可擴充表述為：對任一足夠豐富的相容的形式系統S，必定存在閉公式G′以及G′在S中可表達，但卻不能證明它們是否是S定理。這里的“足夠豐富”指系統S必須豐富到包含一階算術系統PA，它既可以真包含PA又可以等于它，但不能比PA簡單，否則就有可能是完全的。
　　哥德爾還給出了不完全性定理的另一種證明：既然真句子集A不能在PA中得到全部表達，而PA的可證命題集B能夠表達，足見B是A的真子集。因此，存在真命題G在PA中不可證；既然G真，其否定G也應當在PA中不可證。哥德爾指出，這種證明的缺點是沒有擺出一個不可判定命題，而且其中也要明顯地求助于集合，會引起直覺主義者的異議。但是，沒有一個不可判定命題會讓人缺乏某種實在感，更重要的是，不完全性定理表明公理集合論也是不完全的，如果再用集合來證明不完全性定理，則顯然會出現循環。
　　哥德爾不完全性定理有一個推論：任一包含一階算術系統的系統S的相容性，在S自身中都不可證。此推論又稱哥德爾第二不完全性定理，而前述不完全性定理又稱哥德爾第一不完全性定理。
　　2　對哥德爾不完全性定理的幾種誤讀
　　當前，談論哥德爾不完全定理已成為學界的時髦，遺憾的是，其中有一些討論是在沒有真正理解和把握哥德爾定理的基礎上進行的。
　　第一，有人認為哥德爾完全性定理與不完全性定理中的“完全性”是不同的。例如，《糾正對哥德爾定理的幾個誤解》一文認為：“哥德爾完全性定理表明一階邏輯是完全的，即對任何一階語言的公式φ，φ由Γ‘可證’和φ是Γ的‘語義結論’是重合的。”[3]這一觀點可表示為
　　，
　　特別地，當Γ是空集時，有
　　，
　　可見，此“完全性”中的語義有效公式與語形可證公式之間是“當且僅當”的關系。但是，哥德爾的完全性是指“是否初始設定的公理系統和推理規則事實上能夠得到每一邏輯數學命題，或者是否可以想象，在所考慮的系統里可能存在不能得出的真命題”[4](P583)，也就是說，哥德爾考慮的完全性是指所有的有效公式是否都可證，應該用公式表示為
　　，
　　也即在哥德爾完全性定理中，有效公式與可證公式之間只有“如果……那么”的關系，而不是，即無“一階邏輯系統的可證公式都是該系統的有效公式”之意。其實，“”是指可靠性。可靠性和完全性都是形式系統的重要性質，缺少哪一個，形式系統就不完善，但可靠性與完全性不是一回事。
　　不完全性定理的完全性與完全性定理的完全性是一致的，否則就是不完全的。不過，完全與否，是相對于系統而言的。相對于一階邏輯有完全性，而相對于一階算術系統以及復雜性超過算術系統的系統就沒有完全性，即具有不完全性。
　　第二，哥德爾語句會導致悖論嗎？我們經常看到有人論證哥德爾語句會導致悖論。英國學者霍金(S.Hawking)極具代表性，他說：“哥德爾定理是用自我指認的方法證明成立的。這種命題會導致悖論。例如，如果一命題真，那么可合乎邏輯地推出其假；如果一命題假，那么可合乎邏輯地推出其真。”[5](P25)但是，霍金的這個觀點卻是錯誤的。的確，哥德爾語句與說謊者的悖論句極其相似，但二者卻根本不同。張建軍教授在《邏輯悖論研究引論》中對此做了清晰的比較和分析，即
　　L：L是假的：
　　G：G在PA中是不可證的。
　　看起來好像G只不過把L中的“假”換成了“在PA中是不可證”，即把一個語義概念換成了語形概念，但是，后者并不像前者那樣導致悖論。要理解其緣由，主要是要理解我們前面對語義概念“真”與語形概念“可證”“不可證”所做的區分。設L是假的可得L真，再設L為真可得L是假的，這就得到了悖論。循此思路，如果我們設G是假的，即“G在PA中是不可證的”是假的，那么可得G在PA中可證為真，這就意味著G是PA中的真理，這樣就從G假推出了G真；但是，如果設G真，即“G在PA中是不可證的”，由此卻推不出G假，因為G在PA中不可證并不意味著G一定為假。可見，由哥德爾語句G得不出悖論。
　　第三，哥德爾不完全性定理表明心勝于機器嗎？哥德爾和他的工作越來越受人垂青，與計算機和人工智能的發展有關。“他最著名的定理表明了數學的不可窮盡性，確定了形式系統(或計算機程序)的局限性，所以與心是否勝過機器這個膾炙人口的問題有了關系”[6](P184)。持“心勝于機器”觀點者認為，既然哥德爾不完全性定理表明復雜的形式系統中存在該系統內不能判定的公式，而人心卻可以憑借直覺判斷出該公式的真假，那么就表明人心勝過機器。與此相似，哥德爾本人也曾提倡“理性主義的樂觀主義”，他的推理也與上面相似：人的理性不會一面提出理性不能回答的問題一面又堅持只有理性才能回答這些問題，可見，沒有人心不可判定的問題；但數學系統已經極其完善，因此人心勝過機器。但是，哥德爾后來承認他的定理沒有了結心勝過機器的問題[6](P185)。之所以如此，是因為哥德爾不完全性定理一方面表明了形式系統的局限性，即任一足夠復雜的形式系統都有在其自身不可證的真命題，但另一方面，它也顯示了形式系統的巨大威力：低層次的不可證命題可以在高一層次中得到形式證明。可見，哥德爾不完全性定理并沒有直接表明人心是否勝過機器。之所以會產生“心勝于機器”的論點，可以說是因為無視哥德爾不完全性定理所顯示的形式系統巨大威力的結果。
　　3　結語
　　哥德爾不完全性定理影響深遠，它直接摧毀了希爾伯特(D.Hilbert)最初設想的數學目標，使元數學擺脫了虛幻的目標而走上了健康發展道路。
　　哥德爾定理處在整個邏輯學的中心地位。“哥德爾教授的工作已經引起現代邏輯的革命，從數學上也從哲學上大大提高了它的重要性。他所做的數學與哲學出奇地意味深長，美，超脫宿怨。在邏輯的一切現有分支里，他的工作都是基礎和生命力”[6](p34)。哥德爾在證明不完全性定理中使用的一些概念，如真、可表達、可證、有效、哥德爾數、遞歸等，現在都是邏輯學中的基本概念；哥德爾定理的一些思想促成了一些分支學科的大發展，如遞歸論，證明論等。當前，國際上已將哥德爾不完全性定理贊譽為現代邏輯科學在哲學方面的三大成果之一(另兩個為塔斯基的形式語言的真理論和圖靈機與判定問題)。
　　最新的事例足以說明不完全性定理的深遠影響。2004年，英國學者霍金發表文章《哥德爾與物理學的終極》，放棄了其研究了多年的終極性萬有理論：萬有理論不存在，永遠找不到這種理論。霍金說，他是在仔細重新研讀了哥德爾不完全性定理后，才改變了自己的觀點，哥德爾定理“很明顯”表明萬有理論是不可能實現的。
天中學刊駐馬店34～36B3邏輯賈國恒20082008
不完全性/真/可表達/可證
　　incompleteness/true/expressible/provable
Comment on Gdel's Incompleteness TheoremGdel's incompleteness theorem is getting more and more attention, but some solutions are wrong, need to be cleared off. Gdel's incompleteness theorem lies in the core of the whole logic, has important promotion roles on many subjects, and is even the source of some subjects.
哥德爾不完全性定理越來越受到人們的垂青和重視，但有些卻是錯解，需要予以澄清。哥德爾不完全性定理是整個邏輯學的中心，對其他許多學科也有重大的促進作用，甚至是有些學科的發端。
作者：天中學刊駐馬店34～36B3邏輯賈國恒20082008
不完全性/真/可表達/可證
　　incompleteness/true/expressible/provable

網載 2013-09-10 21:42:55

驗證：