藍色情懷

哥德爾定理的證明

作者：應行仁

1.背景和內容

在大學時，我聽到一個匪夷所思的定理：哥德爾用數學證明了，數學裡有不能被證明的定理。這充滿矛盾離奇的說法超越了我的想像，但讓我記住了這個名字，一直到幾十年後，有了足夠的基礎，我才瞭解他是怎麼說的，如何證明這個革命性的定理。

現在網際網路可以很方便地得到訊息，從網上很快能瞭解到哥德爾定理（Gödel's Theorem）的嚴謹陳述【1】，但是進一步的解讀往往似是而非，一些推論或反駁多是從字面上的聯想和發揮。這個理論是如此地刺激人，邏輯又很糾纏，遊走在形式和含義的相接之處，最常被誤用和責難。對於數學定理的理解最好是瞭解它的觀念及核心邏輯，這樣才能知道定理陳述的準確含義，才能合乎邏輯地推論。這系列關於哥德爾定理證明的幾篇博文，基本按經典的普及本Ernest Nagel & James Newman《Gödel's Proof》【2】的思路，揉合後續研究的補充。直指基本概念、思路和核心邏輯，引導讀者思考，逐篇細化深入，而不過分拘泥細節的嚴謹性，因為它的正確性已由原來的研究來保證的。希望用四五篇的短文，讓有理工科基礎的讀者能領會精神，數學、計算機和哲學專業瞭解數理邏輯的讀者，能夠消化這個證明。

自從牛頓用物理的直覺，闖進無窮領域裡大膽計算，鑄造出犀利無比的分析工具後，許多人憑藉著直觀想像和聰明，也湧進去推導出許多互相衝突的結論，數學家花了兩百多年的時間，才釐清了分析領域裡的混亂，將整個數學建立在嚴格邏輯，而不是直觀想像的基礎上。歐幾里德幾何一直是科學理論的範本，四條自明性的公理加上一條平行公設，通過邏輯演繹，推導出平面幾何無窮數量的定理。一直到了近代還只有幾何，被認為是具有堅實基礎的數學分支。在這光輝的榜樣下，人們嘗試用這公理化的方法來規範整個數學。人們後來發現歐幾里德也不夠嚴謹，邏輯上的漏洞得以修補，但追到極致，要依賴於“數”的理論。

自然數的算術運算是數學的最基本的內容，自然數的性質曾經被中國先哲看成天道的機密，古希臘人作為宇宙的根本，在笛卡爾的哲學沉思裡，認為我們無法判斷自己是清醒還是幻覺，但在這兩者中，2+3=5都是永遠不變的真理。1889年意大利的數學家Peano用幾條公理（皮亞諾算術公理 Peano arithmetic axiom，簡記為PA）【3】抽象地定義了“自然數”，“相等”，“直接後繼”和數學歸納法的概念，從而能夠用一階邏輯演繹出整個自然數的算術系統，對應著包括通常的加法、乘法、質數等數論的定理。這樣的客觀世界真理，竟可以從一組有限的假設出發，描寫成符號的式子，抽去了客觀世界上的含義，不再依賴它們所代表對象的真實性來驗證，只是用一組固定的操作規則，將字串按照規則變換得出新的字串，便產生出能夠對應於客觀世界真理的表達式。這個機械化的信念吸引了很多數學家。

在這個運動的高潮時，羅素和懷特海在1910-1913年出版了三卷的《數學原理》，他們自信已將全部的數學建立在純邏輯的基礎上，為今後的所有數學打下了堅實的基礎。1920年，當時數學界領軍人物希爾伯特，提出一個計劃，根據《數學原理》的思想，將所有的數學形式化，稱為形式公理系統（formal axiomatic system），在這裡用精確的形式符號語言來敘述數學命題，根據形式邏輯的規則來操作這些字串的變換和生成，稱之為“形式證明”。這個系統如果有完備性（completeness），相容性（consistency），保守性（conservation）和確定性（decidability），數學研究從此不再需要創造性的工作了，一切定理的發現和證明，歸結為在這個形式公理系統下的機械運算。【4】

這個形式公理系統計劃，關鍵的一個環節是相容性的絕對證明。相容性（consistency）指系統不能產生自相矛盾的結論。過去所有科學理論的相容性，實際上並沒有得到過邏輯的證明，結論依賴於客觀的經驗來驗證。客觀的事實是確定的，不矛盾的，這保證了結論的相容性。歐幾里德幾何雖然以公理化的方式，用邏輯推出所有的定理，它依賴這些公理是自明的，即符合直覺，也就是符合實際的空間經驗，所以認為是真理。但這在邏輯上是不完全的。直覺只是經驗的印象，怎麼保證沒有想像之外的事實？希爾伯特用笛卡爾坐標的解析幾何，將歐幾里德幾何的相容性，用代數系統的相容性來保證，但代數系統的相容性該怎麼得到保證？這仍然沒有得到最後的解決。希爾伯特認為必須構建“絕對”的證明，即這個系統的相容性不再借助其他系統來保證，在抽去具體含義的形式化系統中，相信這個只包含邏輯結構和功能的系統，容易在一覽無遺中尋找各個命題字串之間的邏輯規律，而不需要依賴於不可靠的直覺和經驗，從而來證明相容性，這個證明希望只用到有限次推理，每次只用到有限個數學的對象。

1931年，就在大家為這數學畢其功於一役做努力時，25歲的數學家哥德爾發表了一篇論文“論《數學原理》及相關系統的不可判定命題”。讓這雄心勃勃的希爾伯特計劃成為泡影。哥德爾根據《數學原理》構造出一個簡單的包含著皮亞諾算術公理的形式演算系統，稱之為PM。哥德爾定理有兩個結論，這結論對任何包含有自然數加法和乘法的形式公理系統也成立：

1. PM如果是相容的（consistent）則是不完備的（incomplete）。
2. PM不能證明自身的相容性（consistency）。

解釋一下這幾個關鍵詞。

相容的（consistent），或者譯為“一致的”或者“自洽的”，意思是說在這個系統裡不能推出互相矛盾的結論。因為，若有一對相反的命題（比如說a=b和a≠b）同時為真，那麼由它們可以合乎邏輯地推出任何命題（為真）。所以數學系統只有是相容的才有價值。相容的系統裡至少有一個命題不能被證明（為真）。

完備性（completeness），指所有的真理（語義上為真的命題），都能在這個系統裡被形式證明（從系統裡的定理或公理，按照形式邏輯的方法通過有限步驟推導出來）。Incomplete有時中文翻譯成“不完備“或者“不完全的”，就是說有些真理不能在這個系統裡被證明。

這是數學裡最具有革命性，也最讓人沮喪的定理，它告訴我們公理化固有的侷限性。哥德爾雖然只證明了在那個包含有PA的簡單PM系統，但是它適用於任何包含自然數加法和乘法的數學系統。又有哪個足夠大的數學系統不包括這算術運算？

哥德爾是數學家和邏輯學者，在琢磨這個提供了嚴謹的形式邏輯基礎，將數學命題形式化的《數學原理》時，他發現了一個秘密，這形式邏輯的操作與算術運算極其相似，如果將形式符號的式子對應於一個自然數，那麼形式邏輯的運算就對應於算術的運算，這系統用形式邏輯來描述算術，但算術也可以來描述形式邏輯的過程，它可以合法地自己來談論自己！這讓人想起“這句話是錯的”這個古老的謊言悖論。那麼我們可以用《數學原理》的規則將“這個公式是不可證明的”，這個談論數學公式的命題，形式化變成系統裡的數學公式，造成一個惡性循環來摧毀這座精巧構建的純潔的大廈。

2. 魔鬼的設計

哥德爾要在形式公理系統裡，放進一個“自我糾纏”的魔鬼，用系統裡的公式表達“這個公式是不可證明的”含義，構造一個不可判定的命題。如果他做到了，這系統若是相容的就是不完備的（這不難推出，讀者可以想一想）。他的想法來自於法國數學家理查德（Jules Richard）1905年的語義悖論。理查德悖論【5】【6】的一個變種是這樣的：

用語言描述一類自然數的算術性質。模仿公理化的方法，從基本概念開始，依定義過的內容來描述新的定義。這些定義的內容總是用有限個字符來表達。比如說，定義了整數，乘除法後，定義“（平方數）是某個整數的自乘”，“（質數）是只能被1和自己整除的數”等等。把這些定義按描述句子的長短和字典順序排列成一個表，這裡每一個定義，在表中的序號是一個自然數。例如“（質數）是只能被1和自己整除的數”的序號是19，“（平方數）是某個整數的自乘”的序號是50。對照定義和它的序號，不外乎有兩種情況：一類是這序號恰好符合定義的描述，例如序號19（它是質數，有定義的性質）；另一類是這序號不具有定義性質的情況，例如50（不是平方數，沒這性質），將這些不具有定義性質序號的數定義為“理查德數”。這樣50是理查德數，19則不是。理查德數是在這系統中有明確數學性質定義的一類自然數，它的定義也可以在這表中，假設它的定義對應著序號n。問：n是不是理查德數？論證一下，若n不符合它所對應的定義，按照理查德數定義的描述，n應該是理查德數，這是說n是符合理查德數定義了，即n符合它所標號的定義，這就和初始的假設矛盾了。

這個悖論說明：即使對自然數的算術性質，用任何語言（包括形式語言）來定義，也可能發生矛盾。這悖論有些疵瑕，但即使這個表長有限，矛盾仍在。重點是它與1901年的羅素悖論有著相同的邏輯結構——self-reference，而羅素悖論與謊言悖論都是因為自我糾纏惹得禍。

羅素和一些人認為：如果把對象語言和討論對象語言的“元語言”區分開來，就可以避免這個糾纏。謊言悖論“這句話是錯的。”在區分後就有了兩層的意思，一個是用對象語言表達的語句，另一個是從元語言角度來討論用對象語言表達的語義，在各自層次裡都是一個簡單的陳述。從元語言層次，這句話的含義，是評判句中“這句話”，指的是對象語言層次的句子錯了，對象語言層次的句子不能評價元語言層次的句子，這就避免了糾纏引起的矛盾。

對於理查德悖論，分清層次後，按照算術的性質描述自然數，只能採用算術公理和算術運算的性質，理查德數的定義採用了有關算術性質的討論，系統序號數和對應定義間的關係，這屬於討論數學性質的“元數學”（Metamathematics）【7】，不是數學層次的語言，所以它不應該出現在這表中。規定它們不能混在一起，就杜絕了這個悖論。

在PM裡，用公理、定義和邏輯符號構成字串的式子描寫了數學，對於這些數學性質的討論，即對於這些字串的討論，諸如“這個命題是否定式的”，“字串x是字串z的證明”，“z是不可證明的”，“PM是相容的”等等，則屬於元數學的範疇。

希爾伯特用精確的形式語言構建的形式公理系統，已經嚴格區分數學和元數學，建立起隔離牆，堵塞了這個漏洞。

哥德爾要把“這個公式是不可證明的”的句子放在系統裡，就必須繞過這堵牆，將這元數學的句子轉換成數學和邏輯的式子。我們來看這該怎麼設計。

首先要瞭解什麼是PM中合法的式子。它是按一種形式語言寫的字串。寫過計算機程序的人應該不難理解，因為Basic，C，Java等等，所有計算機語言都是形式語言。

希爾伯特的形式公理系統裡的式子，是按照《數學原理》的思想，用很基本一階謂詞邏輯的形式言語來寫的字串。系統根據演繹規則來操作這個形式語言的字串。

命題邏輯內容大家中學時都學過。謂詞邏輯是命題邏輯的推廣，在命題中可以帶有變量，用謂詞表述變量代表個體的性質和關係，可以用量詞來約束變量，比如說，“存在一個數x，x的自乘等於4”，這裡x是變量，“存在一個數”是量詞，“的自乘等於4”叫謂詞，表達成式子是“∃x(x·x=SSSS0)”，（SSSS0是數4在系統裡的表達），只包含個體謂詞和個體量詞的謂詞邏輯稱為一階謂詞邏輯，簡稱一階邏輯。包含PA的一階邏輯系統稱為一階算術系統。這個大致的解釋，讓不熟悉數理邏輯的讀者能夠想像這些術語。下面假設讀者已經有了數理邏輯的基本知識，這裡通俗地介紹後面要用到一些術語和例子。這些式子只是作為例子，不必記憶。有數理邏輯知識的讀者應該熟悉這些內容。不熟悉的，簡單接受用字串可以表達算術命題的事實，瞭解式子的含義和這些術語，可以略過其他的細節。讀懂這系列科普只需要看懂這些式子表達的意思就行，不需要有深入的知識。（關於數理邏輯的簡介見【8】，詳細可看任何教科書有關“一階謂詞邏輯”部分。）

在這個系統中首先給出一些原始符號，PM包含12個固定符號：～ V →∃ = 0 S （），+ ·和數字變量x，y，…，命題變量p，q，…，謂詞變量P，Q，…等等，以及式子形成規則（syntax），說明怎麼組成合格的字串。這些符合語法規則的字串，稱之為“公式”，如：“~(0=S0)”。系統中有一組初始的公式，稱之為“公理”，兩條變換規則：將公式代入變量的替換規則和三段論推理的分離規則，稱之為“變換規則”。好比計算機解讀程序產生輸出的規則。由幾個公式應用變換規則產生的字串，也是個公式。若是從公理（和已知的定理）開始，由有限次演繹產生的公式，則稱為“定理”，這個過程稱為“形式證明”，簡稱為“證明”。這裡的定理可能很平凡，只要能被形式證明的都是。

PM裡有4個邏輯公理

pVp → p； p → pVq； pVq → qVp； (p → q) → (rVp → rVq)；

將這裡的的“V”解釋成邏輯上的“與”，“→”為“推出”，容易理解這些都是邏輯的規則。它們和變換規則一起，形成邏輯推理能力。

皮亞諾算術（PA）的公理可以表達為下面6個數字公理和一個數學歸納法公理（見【3】）。

~(0=Sx)；Sx=Sy → x=y；x+0=x；x+Sy=S(x+y)；x·0=0；x·Sy=x·y+x；

將這裡的“～”解釋為“否定”，“∃”為“存在一個”，“Sx”為變量x所表示的數的直接後繼數，（想像x+1），其他的按算術中符號的約定，很容易理解這6個公理的含義。但這些含義只是便於理解的手段。形式公理系統不需要理解這些含義來演算，在這個系統中，只需要把這些公式看成沒有意義的字串，按照變換規則來得出新的字串，進行形式性的運算。這些字串並不代表著客觀世界的事物，沒有真假可言，這就是“形式”的意思。

形式公理系統可以操作沒有含義的字串，但是公理集合可以賦予這些字串要描述對象的一種含義，這含義不被用在字串的運算操作上，而建立起稱為定理的字串和描述對象真理間的一一對應關係。公式具有邏輯命題含義時稱為命題，便有了真假之分，當公理被認為是真的，定理便是邏輯為真的命題。一個命題在系統內被證明，即被認為是真的，也就成為了定理。哥德爾1931年論文的命題V中，證明了存在著一個PM定理組成的無窮集合，其中每一條定理如果按照上面對於這些符號的解釋，都表達了一條算術的真理；反之，有個算術真理的無窮集合（屬於“原始遞歸的”，想像所有可以通過有限次算術運算的結果，它包括加法，乘法計算結果，判斷質數等命題），如果這些真理按照上面符號含義的解釋表達成公式，這些公式都是PM的定理。這種無窮多個對應關係，讓你相信這字串的確實具有那種被原始符號和邏輯定義解釋的含義。這個哥德爾關鍵性的結論稱為“對應引理”，它建立起PM定理和數論真理的對應關係。

形式公理系統不需要依賴含義可以獨立存在和演算，但含義的對應讓它易於理解和應用。以後我們在不會混淆時，有時用含義來形容它所對應的那個公式。

我們現在已經瞭解了什麼是PM的公式和它的算術含義。要把討論PM的元數學命題，變成PM裡的命題，就需要建立起一個映射關係，把這個元數學的問題變成算術問題，然後應用“對應引理”表達為PM的公式。這就可以把糾纏的魔鬼引進防衛嚴密的PM殿堂。哥德爾用邏輯推理和算術運算間的一個對應，設計了這個映射。這便是“哥德爾編碼”。

3.哥德爾編碼

公理系統的不可判定命題、相容性和完備性問題是相聯的。系統裡的命題，如果既不可能證明它成立，也不可能證明與之相反的成立，這便是個不可判定的命題。相容的系統，不可能證明相反的一對命題同時成立。完備的系統，必須能夠證明任何一對相反命題，必有一個成立。所以具有不可判定命題的系統，如果是相容的必定是不完備的。

如果在PM裡，能構造出這樣一個自相矛盾的命題：若證明它成立，等同於證明相反的命題也成立。它就是個不可判定的命題。就證明了“哥德爾不可判定定理”，或者根據上面簡單的推論就有“哥德爾不完備性定理”。

“這個命題是不可證明的”這句話，如果能放在PM裡，它便在證明時自相矛盾。但這句話是元數學的命題。我們必須用一個映射，將這命題變換成PM裡自涉的（self-referent）算術命題。歌德爾先用編碼將PM裡的公式一一映射成自然數（哥德爾數），這個數就好比是身份證的號碼，唯一代表著那個公式，從公式角度來看這個數就是它自己。這個公式裡如果包含了這個數和它的含義，就能夠談論自己。這一篇介紹這個哥德爾編碼。

前面說過，形式公理系統裡的公式是由一組原始字符，按照形成規則構成的字串，編碼就是將字串一一映射成一個自然數，稱為哥德爾數。我們來看哥德爾是怎麼編碼的（這基本按哥德爾1931年論文的版本）。

包含著皮亞諾算術公理的形式公理系統PM，有12個固定符號，分別對應著哥德爾數如下：

公式在表中符號的含義解釋下，具有邏輯和數學命題的含義，哥德爾“對應引理”證明了PM中原本只具有形式的定理，對應著其數學含義下的數論真理。不難看出，如果不再定義數字符號，n個S的字串SSS…SSS0的含義是自然數n，這字串稱為數n在PM的表達。

繼續說編碼的規則。自然數變量x，y，z，…的哥德爾數分別是13，17，19，…依序對應著大於12的質數。命題變量p，q，r，…的哥德爾數是13²，17²，19²，…依序對應著大於12的質數的平方。謂詞變量P，Q，R，…的哥德爾數是13³，17³，19³，…依序對應著大於12的質數的立方。

公式的編碼是一組質數冪的乘積，這組質數的個數與公式中的字符數相等，從2開始依序列出前幾個的質數，它的指數對應著相應位置上公式符號的哥德爾數。舉例來說：

公式“∃x(x=Sy)”這裡8個字符對應的哥德爾數依序是4，13，8，13，5，7，17，9，這公式的哥德爾數按照編碼規則便是2⁴3¹³5⁸7¹³11⁵13⁷17¹⁷19⁹，它是一個很大的自然數。

形式證明是由幾個公式組成的序列，序列中每一個公式如果不是公理或已知的定理，都必須是由序列裡前面的公式按變換規則生成的，證明的結果是序列中最後一個公式。形式證明的編碼也與公式的編碼規則類似，只不過其指數是對應著次序上公式的哥德爾數，舉例來說：

從“每個數有個後繼數”用替換規則證明“零有一個後繼數”，可以表示為兩個公式的序列：“∃x(x=Sy)；∃x(x=S0)”第一個公式的哥德爾數為m，第二個為n時，這個形式證明的哥德爾數是：2ᵐ3ⁿ，也是一個自然數。更細緻的解釋見內格爾和紐曼《哥德爾證明》【9】。

按照這樣的編碼，每一個公式或證明對應著一個哥德爾數。根據算術基本定理，每一個自然數可以分解成唯一的質數冪的乘積，依照質數指定的位置和其指數對應的字符或公式，哥德爾數可以解碼出對應的公式或證明。這個編碼規則建立起公式或證明，與（一部分）自然數的一一映射。每個哥德爾數通過這個一一映射，擁有它所對應字串的訊息。

既然公式和證明的所有訊息都在對應的哥德爾數上，那麼討論公式和證明，這些談論字串性質的元數學問題，便是一個數論的命題，就可能把它用公式表達出來【2】。比如一個元數學的命題說：“~(0=S0)”是個否定式的命題。也就是判斷它的第一個符號是“~”。這是個用自然語言表達的元數學命題，首先把它轉化成數論的命題，然後用PM裡的公式來表達。⁰¹²³⁴⁵⁶⁷⁸⁹

這個公式的哥德爾數是2¹3⁸5⁶7⁵11⁷13⁶17⁹，符號“~”的哥德爾數是1，公式的第一個符號是“~”，對應著公式的哥德爾數是2的1次方的因子。記這個數為a，那麼這個元數學命題對應的數論命題是：“a整除於2，且a不能整除於4。”前面說到，自然數a在PM裡表達是有a個S的字串“SSS…SSS0”，“a整除於2”等價於“存在著一個數x，有a=2·x”，可以表示為：∃x(SSS…SSS0=x·SS0)，這個數論命題不難用PM裡的公式表示為：

~(~∃x(SSS…SSS0=x·SS0)V(∃x)(SSS…SSS0=×·SSSS0))；

這個直觀的例子顯示元數學上的命題，是怎樣映射成PM裡的公式。

現在考慮證明中要用到的一個重要元數學命題：“公式序列X證明了公式Z”。我們知道在形式證明的公式序列裡的公式有個的順序規則，與公理、已知的定理、變換規則及被證明公式的對應有關。所謂的“證明”就是有限次地從前面的公式遞推出後面的公式，這叫做遞歸。將公式對應成數後，“證明”就是這些數間的遞歸函數。假定公式序列X的哥德爾數是x，公式Z的哥德爾數是z。從這些關係不難想像出自然數x和z之間的算術關係，將這個算術關係記為“dem(x, z)”。

哥德爾在論文中用了極大的努力證明了這個dem(x,z)是數x和z之間的“原始遞歸關係”，所以它可以形式地表示成一個PM的公式【10】，記為“Dem(x, z)”。我們已經將元數學的命題“X證明了Z”，映射成PM的公式Dem(x, z)。這完成了這一篇文章的目標。

學習計算機的讀者可能疑惑，為什麼要這麼麻煩地編碼？這質疑有道理。哥德爾證明這個定理時在1931年，那時候還沒有計算機，哥德爾在編碼、遞歸函數、可表達性等問題上都做了開創性的貢獻。這裡介紹哥德爾編碼，是沿著哥德爾原來證明的軌跡，瞭解這個經常會被人們提及的內容。現代的計算機實踐經驗，已經在人們頭腦裡形成了新的直觀，對計算機理論有更多瞭解的，更能落實到這些直觀背後充分的理論根據。有了這些直觀，理解這些就很容易了。PM裡的公式和證明，可以用任何一種編碼（比如說Unicode）變成0和1的字串，也就是一個自然數了。這個自然數也可以通過解碼得出原來的公式和證明。這就建立起一一映射。這時候同樣可以通過遞歸函數理論，將上述的“證明”語句表達為PM裡的公式Dem(x, z)。也可以想像寫一個程序，解碼自然數x得出一個公式序列來，然後驗證這序列是可以遞推出自然數z解碼所得的公式，把這個程序用PM裡形式語言寫出來，便是個PM裡的公式。

總之，我們可以把“X證明了Z”，映射成PM的公式Dem(x, z)。注意，表示式“Dem(x,z)”實際上不是PM裡的式子，它只是一個方便的記號，聯繫了兩個哥德爾數的變量x和z在一個公式裡，我們用來代表PM裡那個非常長的公式。

怎麼在這個Dem(x, z)代表的公式裡做到自我糾纏，這個技巧將在下一篇的核心證明裡介紹。

4. 核心證明

這篇介紹哥德爾證明的核心邏輯。你需要的不再是補充知識，而是澄明心思，清晰頭腦，來跟上證明的思路。

哥德爾有一套計算可形式化的“原始遞歸函數”理論，將元數學裡的命題：“哥德爾數為x的公式序列，是哥德爾數為z公式的形式證明”，對應著算術計算，映射成PM裡的公式。這個帶有自然數變量x和z的公式簡記為Dem(x, z)。

PM裡的公式原來只是無意義的字串，無關真假，能夠用演繹規則，從公理和其他定理產生出來的公式，稱為定理，這個過程稱為形式證明。將一些符號解釋成邏輯關係，賦予公理真值，一些公式便有了邏輯的含義，稱為命題，定理便是邏輯上為真的命題。將一些符號解釋為算術符號，哥德爾的“對應引理”通過PA公理，建立起數論真理和算術命題的對應關係，因此賦予了這些公式的數學含義。元數學是在PM上層談論公式性質和關係的語言。

這裡將不時地在元數學和PM兩邊說道、對應，你必須留意這一點，才不會被繞暈了。以後除非強調，元數學命題裡談到“證明”都是指在PM裡的形式證明，有時也略去哥德爾數對應的說明，簡略地說成：“x是z的證明”。這兩個範疇間命題間的映射是形式與語義間的關係，對兩邊相同的邏輯運算保持著形式和語義的對應關係。

哥德爾用Dem(x, z)，構造一個PM的公式G，它表達元數學的命題“公式G在PM內是不能被形式證明的。”

在構造新公式前，還需要介紹一個關於哥德爾數的函數表達式。假如在哥德爾數為k的公式中，有個自然數變量y（哥德爾數是17），將自然數k的PM表達（SSS…SSS0）代入這公式中所有y變量出現的地方，這個新公式的哥德爾數記為sub(k, 17, k)。

哥德爾努力顯示這個置換操作是可計算的，sub(k,17, k)是原始遞歸函數，它對應的PM字串的表達式，記為Sub(k, 17, k)。比如說k對應的公式是“∃x(x=Sy)”，代入後的新公式Sub(k, 17, k)是“∃x(x=SSSS…SSS0)”（這裡SSSS…SSS0有k+1個S），它的哥德爾數是sub(k, 17, k)。

在Dem(x, z) 前加一個存在的量詞(∃x)Dem(x, z)，對應著元數學裡“存在著一個x，它是z的證明”，簡言之，“z是可證的”。其否定式 ~(∃x)Dem(x, z) 對應著“z是不可證的”。

將哥德爾數函數sub(y, 17, y) 代入~(∃x)Dem(x, z)中的z，有

「公式1：~(∃x)Dem(x, Sub(y, 17, y))」

這PM公式直接的含義是數學命題：“不存在著一個哥德爾數x，它滿足dem(x, sub(y, 17,y))的算術關係。”它對應著元數學裡的命題：“哥德爾數為sub(y, 17,y)的公式是不可證的。”

設公式1所對應的哥德爾數是n，這是一個確定的自然數，將它代入公式1的變量y，便有

「公式G：~(∃x)Dem(x, Sub(n,17, n))」

記哥德爾數 g = sub(n, 17,n)，這也是一個確定的自然數。公式G對應著元數學裡的命題：“哥德爾數為g的公式是不可證明。”

這g對應著哪個公式？sub(n,17,n) 是置換操作後新公式的哥德爾數。這新公式是將哥德爾數為n的公式（即公式1）裡的變量y用n代入，這正是公式G！公式G的哥德爾數是g。

因此，公式G對應著元數學裡的命題：“公式G是不可證明的。”公式～G即(∃x)Dem(x, Sub(n,17, n)) 則對應著元數學裡的命題：“公式G是可證明的。”

我們已經把自我糾纏鑲進了公式G！噓一口氣，慢慢消化這個公式和對應的含義。然後往下看這證明的辯駁。如果細心推敲，你可能會有些疑惑，這很正常，需要慢慢消化。哥德爾的證明手法很不尋常。當大數學家馮·諾依曼得知哥德爾證明時大為讚賞，細究之後，兩次宣佈找出了證明中的錯誤，後來他又兩次修正了自己的錯誤。他慚愧地看到自己由這個插曲，輕易地改變了關於數學絕對真理的看法，而且相繼改變了三次。

哥德爾用反證法證明在PM裡，公式G是不可判定的。假如公式G可證，這件事的元數學陳述是：“公式G是可證明的”，~G對應的正是這句話，說明它是可證的。反過來，假如~G是定理，這公式對應的元數學命題“公式G是可證明的”為真，這元數學的判斷是：PM裡可以證明公式G，即公式G是定理。因此，公式G是定理，當且僅當公式~G是定理。【注】

PM是相容時，這種情況是不允許的，所以上述導致矛盾的假設都不成立。G和~G在PM裡都不可證，也就是不可判定的。

G是不可證明的事實，說明元數學描寫G的命題是真理，它對應著這公式G的含義為真。PM裡一個表達真理的公式G，不能在PM裡被證明，說明PM是不完備的。這（在元數學裡）就證明了：

「定理1：PM如果是相容的（consistent）則是不完備的（incomplete）。」

在相容的PM裡不可能判定G的真假，所以哥德爾這個定理有時叫做“不可判定定理”。

是不是在PM裡加上這個不可判定的命題作為公設，系統擴張後就可以讓它完備起來？哥德爾說，這是不可能的！加上新的公理，按照相同的邏輯，還可以證明有新的不可判定的命題。這讓公理化的原始設想完全落空。這定理簡單的推論是：數論裡有無窮多個真理不能用初等方法（數論裡的公理和定理）來證明，不斷引進數論外的定理後，總是還有不能用形式邏輯證明的數論真理。所以古老數論難題的解決，常常意味著帶來新方法的突破。

下面證明：相容性是不可能在PM裡證明的。回顧一下“相容性”的含義，它說：系統裡一個命題和它的否定不能同時是定理。這是數學系統無矛盾性的要求。如果不是這樣，在系統裡就可以證明任何的命題成立。所以“相容性”等價於“系統存在著一個命題，它是不可證明的。”

我們構造一個新的公式

「公式A：(∃z)~(∃x)Dem(x, z)」

這個公式對應著元數學的直接解讀是：“存在著一個公式z，不存在著公式序列x是它的證明”；即“有一個公式，它是不可證明的”，即“PM是相容的”。

公式G是否也有類似的解讀呢？它的直接元數學的解讀是：“公式G是不可證明的。”，我們已經從元數學證明：命題G是真的。它是真的又不能在PM裡證明，這正是“PM是不完備的”的意思。所以，公式G的另一個解讀是：“PM是不完備的。”

元數學裡的定理1說：如果PM是相容的，則PM是不完備的。對應著PM裡的公式：

(∃z)~(∃x)Dem(x, z) → ~(∃x)Dem(x, Sub(n, 17, n))

也就是說，如果我們能夠在PM裡證明它是相容的，(∃z)~(∃x)Dem(x, z)公式為真，按照上式和PM裡三段論推理的分離規則，推出~(∃x)Dem(x, Sub(n,17, n))為真，即在PM裡證明了公式G，這與公式G在PM裡是不可證的事實相矛盾，所以公式A不能在PM裡被證明。

這就有了

「定理2：PM不能證明自身的相容性（consistency）。」

【注】這裡沿用了【9】裡PM公式與元數學對應關係的簡化證明思路。這裡的定理1是J Barkley Rosser 1936年證明在相容條件下的較強結果。實際上這不是哥德爾1931年的證明。哥德爾證明的是：如果PM是ω-相容的（ω-consistent），則是不完備的。

“ω-相容的”的定義是：對於算術謂詞P，“(∃x)P(x)”和每一個自然數k的“~P(k)”不能同時為真。而“相容的”則是：對於任何命題p和~p 不能同時為真。“ω-相容的”是個較強的要求，它能夠推出“相容的”條件。“ω-相容的”的定義裡“~(∃x)P(x)”（不存在著一個數有這性質）和每一個自然數k “~P(k)”（每一個自然數都沒有這性質）在語義理解上是同一回事，但在形式系統裡，因為沒有一個能處理無限的規則（希爾伯特計劃中有限主義的限制），所以不能把它們看成是一樣的。

哥德爾的實際證明邏輯如下：

假設G可證，這說明有個PM公式序列是G的證明，設這個公式序列的哥德爾數為k，這元數學命題對應著數論命題 dem(k, g)，已知g = sub(n, 17, n)，所以有 dem(k, sub(n, 17, n))，它陳述了一個算術的事實，表示為PM的公式 Dem(k, sub(n, 17, n))，這說明它是PM裡的定理。有一個具體的數k滿足這關係，邏輯上說明存在著一個數x滿足這關係，也就是 (∃x)Dem(x, sub(n,17, n)) 能夠被證明，這公式是~G。這說明從G可證，可以推出它否定形式~G也可證。從而，如果PM是相容的，G在PM裡不可證。

假設~G在PM裡可證。如果G不可證，也就是對於所有的k，dem(k, g) 都不是事實的，即~dem(k,sub(n, 17, n))都是真的，所以 ~Dem(k, Sub(n, 17, n)) 對每一個的自然數k都是個定理，~G可證意味著 (∃x)Dem(x, Sub(n, 17, n)) 是PM裡的定理，如果PM是ω-相容的，這是不可能的。從而，如果PM是ω-相容的，~G在PM裡不可證。

因此，如果PM是ω-相容的，G是不可判定的。不可判定的命題，根據排中律，G和~G必有一真，但在PM裡都不能證明它們，所以PM是不完備的。

5. 殊途同歸

哥德爾定理說：不存在著一個自洽的形式公理系統，能夠有效地證明這裡面所有的算術真理。這個系統的無矛盾性，也不可能在系統裡被證明。

哥德爾定理被很多地方傳述引用，表面看來是不同的說法。從上一篇的證明中，可以看出之間的聯繫。我們先談內部的論斷再談外面的同類。

首先，這是針對所有包含算術的形式公理系統。形式公理系統，指用形式化的一階謂詞邏輯來描述公式、命題和證明。這些邏輯演繹通常都用在自然語言表達的數學證明中，只是用符號形式化後更加明確嚴密，涉及到無限時十分謹慎和限制。這系統的提法，有的說包含“皮亞諾算術（PA）的公理”或說“一階算術”，其實指的都是同一個東西。PA是最早研究的算術公理，是能夠用一階謂詞表達的公理。包含了加法和乘法的形式公理系統，必須含有算術的公理。哥德爾雖然只在PM上證明了他的定理，很容易看到，他的結論也適用於所有包含了算術更大的系統。

“相容的”（consistent，或譯為“一致的”或者“自洽的”）是數學系統最基本的要求，說明這個系統推出的結論不會自相矛盾。在科學發展的初期，研究都是基於直覺和經驗，邏輯偶爾點綴其間只為理解內容，人們並不擔心這個問題。隨著微積分踏進了無窮的領域，悖論頻現，數學家們看著這迅速增長的系統憂心忡忡，唯恐有朝一日發現，這只是場終歸會自相矛盾的遊戲，推理出來的怕只是一面之詞。為此，相容性的證明便提到日程來。

完備性（completeness，或譯為“完全的”）則是要說明這個系統功能足夠強大，對系統中的問題都能給個答案。這是第二位的期望。希爾伯特領導的形式公理化運動，希望如同形式邏輯系統一樣，用形式化的方式，為數學建造一個嚴謹、清晰、相容且完備的系統。

凡是用反證法證明的，都要在相容的系統假設下才能得到結論。不相容的系統，任何命題都能得證，這是平凡的完備。在相容的系統中，不完備性與存在著不可判定的命題等價。所以哥德爾的第一個定理，稱“不完備性定理”或“不可判定定理”。

有時哥德爾定理的表述中的條件是“ω-相容的”而不是“相容的”。“ω-相容的”在邏輯上是比“相容的”更強的要求。從前者可以推出後者。這是“每一個自然數都沒有這性質”和“不存在著一個數有這性質”兩者語義的差異，大多數人的理解，它們是相同。但是在形式系統中，因為沒有一個能處理無限的規則，形式推理跨不過這個間隙。所以哥德爾的證明是用“ω-相容的”來表述。定理中“相容的”表述，是J Barkley Rosser在1936年證明的更好的結果。

為什麼希爾伯特計劃不包含著能夠處理無限的規則？這要從“有限主義”的影響講起。上個世紀初，一系列涉及到無窮的悖論將數學家弄得焦頭爛額，有限的都是堅實可靠的，對無窮看法的分歧引起對數學基礎的爭論。因為無窮超越了想像，羅素提出將數學歸結為邏輯，稱為邏輯主義。與之對立的是直覺主義。最早的是克羅內克，他反對康托爾的實無窮，只接受整數，認為自然數是上帝創造的，直覺上清楚的。其他都是人造的，例如無理數沒有一個構造方法或判定準則，不能用有限的步驟來確定，是可疑的。彭加勒嘲笑邏輯主義，認為這是將數學建立在無限的同語反覆上，反對不能用有限個個體來定義的概念，用選擇公理逐一從無限集合中選擇是不可理解的。布勞威爾認為數學的基礎只能建立在構造性的程序上，正確性和可靠性的決定是靠直覺而不是經驗和邏輯。反對將有限經驗總結的排中律推向無限的領域。布勞威爾和外爾只接受像數學歸納法那樣，敘述進行中狀態的潛無窮，反對像無窮集合和無理數那樣，作為實體的實無窮。這個爭論造成數學研究的分裂和混亂，直覺主義的主張將導致一批經典數學和數學分析的大部分成果失效，希爾伯特出自保衛無窮領域革命的成果，用行政手段壓制了直覺主義。但是有限主義的疑慮，畢竟還是產生了影響，在希爾伯特計劃裡有兩個原則，一是“形式化”，定義和推理拋棄了符號和規則之外的東西，形式地進行，這讓數學清晰且嚴謹。這個形式公理化的思想被歷史認同了。第二個是“有限化”，迷惘於由無窮產生的悖論，以及疑慮只憑邏輯思考不能驗證之事的真實性，他希望有效的證明只用有限的步驟，每一步只涉及到有限個數學的對象。全稱命題表達的規律對每一個對象都必須能夠驗證，存在的判斷必須能給出一個特定的對象。有限制地在元數學上使用數學歸納法等等。【2】這些規則相當於原始遞歸的方法，被用在絕大多數能夠被人認可的數學證明中。哥德爾看到“有限化”的侷限性，他的定理說明，如此侷限的系統必定是不完備的，甚至連自身的無矛盾性都不能證明。雖然他的證明不否定在PM之外的可能性，但對於不能映射到PM系統的“有限化”證明，還沒有人知道是什麼概念。【13】

哥德爾定理之後，人們關心的是，我們能夠證明系統的相容性嗎？有完備的系統嗎？

這答案都是肯定的。邏輯系統的相容性很平凡，因為公理都是重言式，定理也是重言式了。其否定命題一定不是定理。對於包含算術的公理系統，哥德爾定理只說，在系統裡不能證明其相容性，並不排斥在系統外的證明。PM的相容性，在1936年由甘岑（Gerhard Gentzen）用“超限歸納法”證明了。大多數數論邏輯家並不懷疑這個證明的正確性，但這個證明用的不是“有限的”方法，不能映射到PM中，超出了希爾伯特“絕對證明”的規定。人們最關心的是實數理論（數學分析）的無矛盾性，五十年代，日本學者將甘岑的工作推廣到高階謂詞演算來探索，1967年，日本高橋元男用非構造的方法證明了數學分析子系統的相容性，由於這證明不是構造性的，數學分析的相容性至今還沒有得到有效的證明。【13】

很多系統不是完備的，這並不奇怪。例如，歐幾里德幾何在缺乏平行公設時，顯然不是完備的。關鍵是經過擴充後，有沒有可能讓它完備化。一階形式邏輯推理系統，比如說群論等一階系統，可以是既相容又完備的系統。哥德爾在他的1929年博士論文，證明了一階謂詞邏輯的完備性定理。【11】但他的算術形式系統不完備性定理，杜絕了以擴充來完備它的希望。

在一階集合論的ZF系統中，由於可以定義自然數，所以也是不完備的。存在著不可判定的命題與不完備性是等價的。不從哥德爾定理出發，哥德爾1940年和Cohen1960年代的工作合起來，證明了連續統假設在ZFC集合公理系統中是不可判定的，選擇公理在ZF集合公理系統中也是不可判定的。1982年美國帕裡斯、哈林頓、弗裡德曼相繼在有限組合理論中找到既不能肯定也不能否定的關於自然數的命題。【1】【11】時至今日，人們用不同的方法，構造性了在現有系統中不可判定的一些命題，哥德爾定理得到了很好的驗證。

哥德爾的貢獻在科學史上是罕見的，他以一人之力在短短的幾年內，對一階邏輯系統的完備性，數論和分析形式系統的完備性，選擇公理的相容性等中心問題作出明確的解答。科學在長期演化中，某種思想到了一定時期必定成熟。1931年哥德爾發表了不完備性定理。幾乎在同一個時間，波蘭邏輯學家塔斯基（Tarski）在1931年送交了《形式化語言中的真理概念》論文。【14】塔斯基從理論語義學或邏輯語義學角度研究形式語言，回答了類似哥德爾的問題。塔斯基認為真理的定義，所要求滿足的條件是“形式上正確、實質上充分”，這後者表達為，對於理論中所有句子的一個T範式（Schema T）：φ ↔ T<φ>。就PM系統而言，這範式說：數學命題可證，當且僅當這命題在數學上是正確的。他同樣構造一個自我糾纏的例子，證明了塔斯基定理：任何包含一階算術的理論，如果有T範式，它是不相容的。

1936年英國數學家圖靈研究抽象的計算模型，發表了圖靈機的理論。圖靈機是等價於任何有限邏輯數學過程的終極強大的邏輯機器。現代的電子計算機也可以看作是通用的圖靈機。圖靈機的停機問題是：能否有個程序判斷任意一個程序，它是否在有限的時間內結束運行。他同樣也是構造出一個自我糾纏的例子，證明這是不可能的。【16】塔斯基定理和圖靈停機不可判定，都與哥德爾不完備性定理等價，相互間可以推證。

哥德爾的不完備性定理，塔斯基的形式語言真理論，圖靈機和停機判定問題，被稱為現代邏輯科學在哲學方面的三大成果。這分別在數學形式系統，語義學和計算領域，研究數學證明能力，語言表達能力和機器計算能力，他們都應用和發展了遞歸理論，研究在有限或向無限進行中的邏輯推理，所（不）能到達的極限。

無窮超越了人類理解的極限。在芝諾的悖論裡，阿基裡斯一直無法在邏輯上超越烏龜。【17】幾千年來人類智力的進步解答了一部分的困惑，但它在不斷被征服後，又屹立在那裡，就像他們間的距離只是縮小而不是消除。每個人可能會有個夢中情人，現實中人們只可能在有限的時間裡，接觸到有限的人中搜尋，也許是終生無緣相遇。人們在潛無窮和實無窮的邏輯鴻溝兩邊相望，沒有一座橋樑跨越。有限化的證明、計算和語言表達站在潛無窮這一邊，自我糾纏無休止的自詰，意味著實無窮。難道這告訴我們：邏輯永遠無法跨越潛無窮到達實無窮？

【1】Wikipedia，Gödel's incompleteness theorems
【2】《Gödel's Proof》by Ernest Nagel andJames Newman, NYU Press, 2001, 2nd edition
【3】Wikipedia，Peano axioms
【4】Wikipedia，Hilberts program
【5】維基百科，理查德悖論
【6】Wikipedia，Richard’s paradox
【7】Wikipedia，Metamathematics
【8】數理邏輯、謂詞邏輯、一階邏輯和公理系統
【9】內格爾和紐曼《哥德爾證明》
【10】數論中有不可數多的命題，而PM只能有可數個式子，所以並非所有的數論命題都能表達成PM裡的公式。哥德爾證明了原始遞歸函數可以表達成PM裡的公式。
【11】哥德爾不完全性定理(朱水林) 
【12】Gödel's proof summary
【13】數理邏輯的發展
【14】張祥龍，塔斯基對於“真理”的定義及其意義
【15】SEP Self-reference
【16】維基百科，停機問題
【17】應行仁科學網博文，阿基裡斯與烏龜的悖論解決了嗎？