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

簡體     傳統

---

　　中圖分類號：B813　　文獻標識碼：A　　文章編號：1672-7835(2008)02-0027-04
　　《安徽大學學報》2006年第5期刊登了溫邦彥的文章《禁止使用自指代命題》，指出并論證哥德爾不完全性定理證明中存在嚴重邏輯問題。這一結論及其論證都是不成立的。本文借澄清對哥德爾不完全性定理若干誤解的機會，以直觀與簡明的方式闡述哥德爾不完全定理的內容、意義及哥德爾的相關工作，以期一般讀者對這一與“相對論”齊名的邏輯學杰出成果有所了解。
　　哥德爾是20世紀最偉大的數學家和邏輯學家。在邏輯學中的地位，一般都將他與亞里士多德和萊布尼茲相比；在數學中的地位，愛因斯坦把哥德爾的貢獻與他本人對物理學的貢獻相提并論。1952年6月美國哈佛大學授予哥德爾榮譽理學學位時，稱他為“20世紀最有意義的數學真理的發現者”。在哥德爾所發現的被稱為“20世紀最有意義的數學真理”當中，最杰出、最具有代表性、最有震撼力的是哥德爾不完全性定理。
　　哥德爾不完全性定理包括兩個內容：第一，一個不弱于初等數論的形式系統，如果一致，則不完全；第二，這樣的形式系統如果一致，則這種一致性在系統內不可證。
　　上述內容可以較為直觀地解釋如下。
　　所謂初等數論形式系統，是指用形式化方法構造的算術公理系統。初等數論形式系統，(簡稱算術系統)有三個層面：語法、語義和元理論(稱為元數學)。
　　語法指算術系統自身的構造。算術系統由為數不多的一些符號及規則構成。在算術系統內部，符號僅僅是符號；公式(包括公理)僅僅是合乎規則的符號串；證明僅僅是合乎規則的公式序列。它們都沒有涵義。
　　語義指算術系統的解釋。經過語義解釋后，算術系統中的符號有了涵義，(閉)公式成了有內容的算術命題，何謂一個公式真有了確定的標準。
　　算術系統是一致的，是指不存在公式A，A和A(A的否定)都可證。算術系統是完全的，是指不存在公式A，A和A都不可證。
　　理解哥德爾不完全性定理，首先要弄清楚算術系統的兩個基本概念，一個是“可證”，另一個是“真”。
　　可證是語法概念。一個公式可證，是指存在它的一個證明，即存在以該公式結尾的一個公式序列，其中每個公式或者是公理，或者是依據規則得到的。判定一個公式是否可證，不涉及任何涵義，例如不涉及該公式經解釋后具有什么內容。
　　真是個語義概念。一個公式真，形式地說，是指它經過語義解釋后確定為真；直觀地說，是指它表達算術真理。
　　因此，一個公式可證與該公式真，不直接相關，更不能直接畫等號。
　　當然，數學家的理想目標是：算術系統的可證公式，不多不少，正好等于算術真公式①。所謂不多，是指系統滿足可靠性，即可證公式表達算術真理；所謂不少，是指系統滿足完全性，即表達算術真理的公式在系統中一定可證。哥德爾不完全性定理的第一個內容恰恰是：這樣的系統如果一致，則不滿足完全性，即并非任一算術真公式在系統中都可證。哥德爾在系統內構造了一個(閉)公式U，并且證明了如果系統是一致的，則U和U(U的否定)在系統中都不可證。根據排中律，算術公式U和U必有一真。證明了U和U在系統中都不可證，就是證明了并非任一算術真公式在系統中都可證。
　　證明哥德爾不完全性定理的關鍵點是公式U的構造。
　　U被稱為不可判定公式。U是由系統內的符號(對象語言)表達的算術公式，它直接刻畫的是自然數的性質與關系，是算術命題；但是，U能表達元數學命題：公式U在系統內不可證！這是個神奇的功能。哥德爾的天才創造了這一神奇。
　　一個以形式語言表達的刻畫自然數性質或關系的算術公式，何以能表達一個公式是否可證這樣的元數學性質？為了做到這一點，哥德爾完成了兩個表達轉換。
　　第一，把關于算術形式系統的元數學斷定(例如一個公式在系統中是否可證)，表達為直觀算術中關于自然數的斷定。
　　哥德爾通過極富創造性的配數法，使形式算術系統中的每個符號、每個公式(符合規則的符號串)、每一證明(符合規則的公式序列)惟一地對應于一個自然數，這樣的自然數稱為相應符號、公式或證明的哥德爾數。這樣，例如，一個公式A(其哥德爾數記為p)在系統中可證，可表達為存在自然數，它是哥德爾數為p的公式的證明哥德爾數。“可證”這種元數學性質，就這樣表達為自然數之間的關系。
　　第二，把直觀算術中關于自然數的斷定，表達為形式算術系統中的公式。并非所有關于自然數的斷定在形式算術系統中都可表達，只有具有遞歸性的函數、關系才可表達。
　　在上述工作的基礎上，哥德爾在系統中構造了具有以下結構的公式U②：
　　yW(p，y)其中，謂詞W(x，y)表達的含義是：哥德爾數為x的公式的證明的哥德爾數是y。因此，U的含義是：任一自然數都不是哥德爾數為p的公式的證明的哥德爾數，也就是斷定：哥德爾數為p的公式不可證。奇妙的是，根據U的特殊結構，公式U的哥德爾數正是p！也就是說，U表達的含義是：U在系統中不可證！
　　不可判定公式U一旦構造出來，離完成哥德爾不完全性定理的證明就一步之差了。
　　第一步，先證明U不可證。
　　假設U可證，則存在作為U的證明的公式序列，令q是這一證明序列的哥德爾數，則由定義，W(p，q)成立。W是遞歸謂詞，在系統中可表達，因而W(p，q)在系統中可證。已假設U，即yW(p，y)可證，又yW(p，y)→W(p，q)可證，依據規則，得W(p，q)可證。繼而得：W(p，q)可證，并且W(p，q)可證，即系統不一致。因此，如果系統一致，則U可證的假設不成立，即U不可證。
　　第二步，再證明U不可證。
　　已證U不可證。即任一自然數q都不是U的證明的哥德爾數，所以對任意自然數q，
　　W(p，q)成立，
　　根據可表達性，對于任意自然數q，
　　W(p，q)可證，
　　根據ω-一致性③
　　yW(p，y)不可證，即
　　yW(p，y)不可證，即
　　U不可證。
　　這就證明了，如果系統一致，則U和U都不可證，即不滿足完全性。
　　同樣，基于哥德爾配數法和可表達性理論，“初等數論滿足一致性”這一元數學命題，可以表達為系統內的一個公式。哥德爾證明了，這一公式在系統內不可證，也就是說，哥德爾證明了，這樣的系統如果一致，則這種一致性無法依靠自身得到證明。
　　數學與邏輯結合，或者說數理邏輯發展的一個重要起點，就是數學求助于邏輯來證明自己的一致性。這就是所謂的數學基礎問題。從直觀算術到算術形式系統和元數學，是數學在邏輯的洗禮下經歷的一次脫胎換骨。哥德爾的成果使算術讀懂了自己：我想我是一致的，但可惜我不可能(不是尚未能，而是不可能)證明這一點；我希望我能證明所有的算術真理，但可惜我不可能(不是尚未能，而是不可能)做到這一點。
　　面對哥德爾的成果，科學家的心情是復雜的。數學家魏爾說：上帝是存在的，因為數學是邏輯一致的；但魔鬼也是存在的，因為無法證明這種一致性。
　　各種各樣的科學理論在訴說著自己對世界的見解。
　　哥德爾對科學理論說，你了解自己嗎？
　　這就是哥德爾留下的振聾發聵的聲音。
　　對哥德爾的上述工作自然可以質疑與批評。事實上，早在哥德爾不完全性定理發表時，大數學家馮·諾依曼曾表示嚴重質疑，在經過相當一段時間的推敲后才確認其正確性。哥德爾不完全性定理獲得了眾多的高度評價，但批評、疑慮之聲也時有出現。這種批評與質疑是正常的。當然，有理由要求，公開發表的此種批評與質疑不應基于對相關基本知識的誤解甚至無知。
　　溫邦彥先生《禁止使用自指代命題》一文對哥德爾工作的批評涉及以下幾個問題。
　　溫先生認為，哥德爾所構造的不可判定公式，是一個與說謊者悖論一樣的自指代命題。自指代命題違反邏輯基本規律，應當禁止使用。
　　不可判定公式U的含義確實是斷定自身不可證。可以推想，哥德爾構造不可判定公式時受到說謊者悖論的啟發。但二者有實質區別。
　　第一，作為悖論，說謊者悖論語句A滿足以下等式：
　　A=A是謊話
　　也就是說，在“A是謊話”中，可用“A是謊話”來替代A，悖論就是這樣產生的。但作為不可判定公式，公式U不滿足以下等式：
　　U=U在系統內不可證
　　U是用形式語言表達的系統內的算術公式，“U在系統內不可證”是用自然語言表達的元數學命題，二者不能畫上等號。也就是說，在“U在系統內不可證”這句話中，不能用“U在系統內不可證”來替代U。U在系統內是否可證？這一問題是成立的；“U在系統內不可證”在系統內是否可證？這一問題是不成立的。一般地說，一個用元語言表達的元數學命題A在系統內是否可證，是指：A在系統中是否可表達？如果不可表達，則不存在是否可證的問題；如果可表達，則表達該元數學命題的系統內的公式是什么？這一公式在系統內是否可證？因此，“U在系統內不可證”在系統內是否可證？這一問題的正確提法是：“U在系統內不可證”在系統內是否可表達？如果可表達，則表達這一元數學命題的系統內的公式是什么？這一公式在系統內是否可證？事實上，“U在系統內不可證”在系統內可表達，而表達“U在系統內不可證”的系統內的公式正是U。因此，“U在系統內不可證”在系統內是否可證，這一問題的正確解讀實際就是“U在系統內是否可證”？
　　也就是說，不可判定公式并不是溫先生所說的自指代命題。
　　第二，說謊者悖論語句可導致悖論，但不可判定公式不導致悖論。
　　說謊者悖論語句A之所以可導致悖論，因為由A真可推出A假，并且由A假可推出A真。但對于不可判定公式U來說，只有假設所在系統滿足完全性(即真公式都可證，因而不可證公式都假)，才可由U真推出U假。但算術系統是否滿足完全性在構造U的當下正是一個懸而未決的問題，事實上這樣的系統是不完全的。因此，由U真不能推出U假，即不可判定公式不導致悖論。
　　溫先生認為，在上述由U不可證導出U不可證的證明過程中，存在判定U和U可證性的兩條標準：第一條標準是U或U的證明序列的哥德爾數是否存在；第二條標準是U和U表達的含義。從U的證明序列的哥德爾數不存在，根據第二條標準，得U可證；又根據第一條標準，可得U不可證。因此，這兩條標準是互相矛盾的。
　　依據U的證明序列的哥德爾數不存在，確實可得U不可證；但不能得U可證。溫先生的質疑是：U即yW(p，y)，這一公式的含義是：任一自然數都不是哥德爾數為p的公式的證明序列的哥德爾數。而U正是這個哥德爾數為p的公式，因此，U的含義正是“U的證明序列的哥德爾數不存在”。證明了“U的證明序列的哥德爾數不存在”，不就是證明了U嗎？既說證明了“U的證明序列的哥德爾數不存在”，又說U不可證，豈不自相矛盾？
　　溫先生混淆了“證明”有兩種含義，一種是系統內的證明，另一種是系統外的證明。系統內的證明之對象是系統中的公式，證明的目標是確定某個公式為系統中的定理，證明的依據只有公理和推理規則。系統外的證明之對象是用元語言(主要是自然語言)表達的句子，不是系統內的公式，例如，“U不可證”，其中U是系統內的公式，但“U不可證”不是系統內的公式，而是用自然語言表達的句子，系統外證明的目標是確定這樣的句子的真實性。系統內證明的定理，稱為內定理。系統外證明的結論，稱為元定理。哥德爾構造了不可判定性公式U，并且證明了在數論形式系統N中，如果N是一致的，則U和？U都不可證。這個證明是系統外的證明。哥德爾定理是元定理。
　　因此，對不可判定公式U，當我們說“證明了U是真命題”，這個“證明”是指系統外的證明；當我們說“U不可證”，這個“證明”是系統內的證明；當我們說“證明了一個真命題在系統內不可證(明)”，這一語句中前一個“證明”是指系統外的證明，后一個“證明”是指系統內的證明。這一語句表達的正是證明了系統的不完全性。
　　在系統外證得一個公式是真的，不等于證明了該公式在相關系統中可證。說明這一點，在與溫先生的討論中至關重要。
　　例如，依據真值表方法可以極為方便地證明“A→A”是邏輯真命題(重言式)，但據此不能直接得出結論：“A→A”在命題演算系統P中可證。要在系統中證明“A→A”，需要構造相應的公式序列，這樣的序列稱為該公式的證明，其中每一個公式或者是公理，或者是前面的公式，都是依據推理規則所得到的。為了加深印象，不妨把“A→A”在命題演算P系統中的證明照錄如下：
　　(1)A→((A→A)→A)　　公理1
　　(2)(A→((A→A)→A))→((A→(A→A))→(A→A))　　公理2
　　(3)(A→(A→A))→(A→A)　(1)(2)分離
　　(4)A→(A→A)　　公理1
　　(5)A→A　　(3)(4)分離
　　當然，如果證明了命題演算P的完全性，就可以直接根據“A→A”是重言式，得出“A→A”在系統中可證。命題演算P的完全性的證明是非常復雜的。而在哥德爾定理的證明中，算術形式系統N的完全性恰恰有待證明(事實上它是不完全的)，因此，更不能根據U是真命題，直接得出結論：U在N中可證。
　　溫先生感到不解的是：對于任一自然數q，W(p，q)可證，不就是對所有自然數q，W(p，q)可證嗎？，因而不就是yW(p，y)可證嗎？“任一”與“所有”難道還有區別？根據對于任一自然數q，W(p，q)可證，為什么不能得出yW(p，y)可證？
　　根據什么得出：對于任一自然數q，W(p，q)可證？根據兩點：第一，U不可證，因而任一自然數都不是其證明的哥德爾數；第二，W是遞歸謂詞，在系統中可表達。W是遞歸謂詞，在系統中可表達，只能保證對于任意一個確定的自然數q，在系統中通過有窮步驟證明W(p，q)，但不能保證在有窮步內證明yW(p，y)。遞歸證明是一種在有限步驟內完成的證明。可以直觀地比照這樣一個例子：任給一個自然數，我們都可以通過有限步驟的操作證明：存在自然數比它大(事實上只要加1，即只要通過一次后繼運算即行)；但這并不意味著我們都可以通過有限步驟的操作證明：所有自然數都有自然數比它大。
　　綜上所述，溫先生未能準確理解和把握形式化理論的一系列基本概念，如未能準確理解和區分公式和公式的含義、公式的真和可證、系統內的公式和系統外的斷定、系統內的證明和系統外的證明、內定理和元定理，以及何為遞歸，等等，這使得他有志于從事的對哥德爾不完全性定理的批判性研究缺乏必要的基礎，其結論與論證之不成立也是自然的。
　　注釋：
　　①算術形式系統中的可證公式，包括一階邏輯的有效式。這里約定，算術真公式包括一階邏輯有效式，即算術真理包括邏輯真理。
　　②實際的不可判定公式的構造更為復雜，這里討論的公式U是它的直觀形式。
　　③哥德爾在證明“U不可證”時假設系統滿足ω-一致性。ω-一致性是比一致性更強的條件。羅塞爾證明，相關的證明假設一致性即可。
湖南科技大學學報：社科版湘潭27～30B3邏輯陳慕澤20082008
哥德爾不完全性定理/不可判定公式/可證/真
On Correct Understanding of the Godel’s Incompleteness Theorem　　CHEN Mu-ze借澄清對哥德爾不完全性定理若干誤解的機會，以直觀與簡明的方式闡述哥德爾不完全定理的內容、意義及哥德爾的相關工作。哥德爾不完全性定理包括兩個內容：第一，一個不弱于初等數論的形式系統，如果一致，則不完全；第二，這樣的形式系統如果一致，則這種一致性在系統內不可證。
作者：湖南科技大學學報：社科版湘潭27～30B3邏輯陳慕澤20082008
哥德爾不完全性定理/不可判定公式/可證/真

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

驗證：