【中文網(wǎng)上關于哥德爾不完全定理的文章很少。這篇文章寫了很久，花了很多時間打磨，希望對熱愛數(shù)學和邏輯的人有所幫助。本文將對哥德爾不完全定理的理解分為五個部分，并建議只想初步理解的讀者可以把重點放在第一部分；想了解一些背景的讀者可以練習到第二個層次；想更深入了解哥德爾證明思想的讀者建議練習到第三個層次；如果你真的感興趣，想了解更多哥德爾的證明過程及其嚴謹性的讀者可以實踐到第四位；想多了解讀者，可以練到第五關?！髡遌

1931年，庫爾特弗里德里希·哥德爾發(fā)表了一篇影響深遠的論文《論《數(shù)學原理及相關系統(tǒng)I》的形式上不可判定的命題》[1](論文原文以德文發(fā)表，英文譯名在此給出)。今天我們一般把論文中提出的定理稱為“哥德爾不完全定理”。80多年過去了，哥德爾不完全定理的影響仍然是持久而深遠的，特別是它引起了許多非數(shù)學家的興趣，引發(fā)了各種各樣的解釋。不幸的是，有些解釋是不準確的，甚至是錯誤的。更嚴重的是，有些人出于對哥德爾不完全定理的無知，甚至開始懷疑和批判人類的理性，以至于發(fā)展到相信和鼓吹不可知論。最近在認真學習哥德爾論文原文(英文翻譯，實在不懂德文)和相關資料的基礎上，加深了理解，同時也希望盡自己最大的努力分享一下對哥德爾不完全定理的理解，澄清一下對哥德爾不完全定理的誤解。

哥德爾的不完全定理是數(shù)學和邏輯領域劃時代的成就，使人們對數(shù)學研究的基礎有了更深刻、更準確的認識，也是現(xiàn)代邏輯史上的重要里程碑。哥德爾的不完全定理雖然偉大而深刻，但我個人認為并不深刻。對于一個普通人來說，只要肯動腦，一定程度上就能準確理解。當今互聯(lián)網(wǎng)時代，網(wǎng)上對哥德爾不完全定理有很多介紹和解釋；60多年前，美國兩位作家歐內(nèi)斯特·內(nèi)格爾和詹姆斯·紐曼所著的《哥德爾證明》是科普中哥德爾不完全定理的重要著作。現(xiàn)在網(wǎng)上能看到的介紹哥德爾不完全定理的中文文章大多轉(zhuǎn)述自《哥德爾的證明》這本書。但是這本書寫的太早了，一些新的結論還不知道。另外，這本書在推廣哥德爾的證明時，更說明了背景和思路，用作者自己的理解描述了哥德爾的證明。有些地方不夠嚴謹，有些講述方法不夠準確。摘要:在哥德爾論文原文的基礎上，介紹了哥德爾不完全定理的證明，并適當融入了80年來的一些新的理解和結論，希望能幫助數(shù)學和邏輯愛好者理解和認識哥德爾不完全定理。

為了幫助更多的人在自己的需要中理解哥德爾不完全定理，下面的緒論將哥德爾不完全定理的理解分為五個部分，從理解定理的基本含義到理解核心證明。讀者可以根據(jù)自己的內(nèi)力基礎練習到自己的水平，就像練習“干坤大挪移”的神力一樣。祝大家都能練出哥德爾不完全定理第五魔功！

第一:“廬山真面目”——對“哥德爾不完全定理”的準確理解

在欣賞一塊美玉的時候，不要先聽各種專家講這塊玉有多晶瑩有價值，而是先拿出來給大家看看，有個感性認識。在哥德爾的論文中，我們一般所說的“哥德爾不完全定理”(有時稱為“哥德爾第一不完全定理”)指的是論文中的定理六。原文如下:

定理VI:對于每一個ω一致的本原遞歸類κ的公式，都有一個先驗遞歸類符號r，使得forall(v，r) nornot(forall(v，r))都不屬于Conseq(κ)(其中v是r的自由變量)。

盡量翻譯成原文，如下所示:

定理六:對于任意一個具有相同ω(四階)的原始遞歸公理集κ，必須有一個原始遞歸表達式R(三階和四階)，這樣無論是“R總是成立”的命題，還是“R不總是成立”的命題，都不屬于可以從κ(原文中的Conseq(κ))推導出的定理集。

補充說明一下，哥德爾論文中κ所代表的公理集是指包含皮亞諾公理的集合，這一點在哥德爾論文之前就已經(jīng)講清楚了，所以在闡述定理六時沒有特別強調(diào)。

練第一魔的讀者可能會問:“大哥，你在說什么？”。別擔心，練第一個魔法技能沒那么復雜。

先說公理。公理實際上是一個不需要證明就被認為有效的命題。公理系統(tǒng)是指一組公理。通過這些公理和基本邏輯關系，可以推導出更有效的命題，稱為定理。公理系統(tǒng)一般認為起源于2300多年前歐幾里得寫的《幾何元素》。在現(xiàn)代科學形成的過程中，人們發(fā)現(xiàn)許多命題或結論都可以通過定義一套公理和合理的邏輯推導來證明。公理系統(tǒng)是數(shù)學研究和科學研究的基礎，數(shù)學研究的結果很大程度上是(或依賴于)一組公理系統(tǒng)的推演，而其他科學研究除了公理系統(tǒng)的推演之外，還需要通過系統(tǒng)的實驗來驗證。

“哥德爾不完全定理”是針對公理系統(tǒng)的結論。它之所以如此偉大和深刻，正是因為它動搖了作為所有科學研究基礎的公理體系。在練習第一大魔術時，我們簡單理解了哥德爾不完全定理說一個復雜的公理系統(tǒng)(至少包含皮亞諾的算術公理)如果是一致的(相容的，不矛盾的)就是不完全的。這里的完備性是指“任何可以在這個公理系統(tǒng)中描述的命題，都可以在這個公理系統(tǒng)中判斷，不是對就是錯”。

用白話解釋一下，也就是說，在一個沒有矛盾的公理系統(tǒng)中，總有一些命題不清楚是對是錯(需要注意的是，這意味著在這個系統(tǒng)中不清楚，而不是永遠不會清楚)?？赡苡腥苏f，既然沒有矛盾的公理系統(tǒng)有問題，那就來一個有矛盾的公理系統(tǒng)吧。如果你想象一個公理系統(tǒng)，一會兒告訴我們“1+1=2”，一會兒告訴我們“1+12”，相信沒有人會把這個公理系統(tǒng)當真。矛盾的公理體系會導致完全的無意義和虛無，這一點在練習第二種神奇力量時會詳細闡明。

以上結論聽起來很可怕。公理系統(tǒng)一定是沒有矛盾的，但是沒有矛盾的公理系統(tǒng)會導致一些是非不明的命題。于是各種解釋開始出現(xiàn)，比如“哥德爾定理告訴我們數(shù)學和邏輯的極限，這幾乎是人類理性的極限。它證明了理性不是萬能的”，“哥德爾定理告訴我們，人類不可能真正認識世界，永遠無法理解宇宙的真理”等等。我相信哥德爾作為人類理性和智慧的杰出代表之一，如果聽到這些說法可能會很無奈。

第一，“哥德爾不完全定理”不僅是人類理性的極限，相反，它是人類理性智慧的偉大成就。它告訴我們，正是因為人類的理性智慧，才有可能實現(xiàn)如此深刻的結論。哥德爾通過構造一個在這個公理系統(tǒng)中無法證明的命題，證明了“哥德爾不完全定理”。這個命題的內(nèi)容是“命題本身在這個公理系統(tǒng)中無法證明”。既然哥德爾已經(jīng)明確證明了這一點，就說明這個命題無疑是正確的。所以哥德爾不完全定理的證明過程其實告訴我們，有一個正確的命題可以在這個公理系統(tǒng)中表達，但在這個公理系統(tǒng)中既不能證明，也不能證偽。如果說哥德爾的不完全定理澄清了某些界限，那它只是澄清了“某些公理系統(tǒng)的界限”，而不是“數(shù)學和邏輯的界限”，更不是“人類理性的界限”。

其次，“哥德爾不完全定理”不僅沒有告訴我們“人類不可能真正認識世界”，而是在更深層次上告訴我們?nèi)祟悜撊绾握J識世界，探索真理。比如在數(shù)學中，如果我們發(fā)現(xiàn)一個命題還沒有被現(xiàn)有的方法、公理和定理證明，我們可以嘗試把現(xiàn)有的方法和公理擴展到進一步的研究；正是因為這個原因，費馬定理和黎曼猜想被稱為“下金蛋的母雞”。在物理學中，廣義相對論的發(fā)現(xiàn)過程也是由于狹義相對論的某些推論難以解釋(比如一個高速旋轉(zhuǎn)的圓盤會發(fā)生扭曲)。愛因斯坦提出了等效原理，果斷地擴展了直線空的假設，從而創(chuàng)立了偉大的廣義相對論。值得一提的是，哥德爾和愛因斯坦在普林斯頓大學成了非常好的朋友。愛因斯坦晚年曾說過，他之所以經(jīng)常堅持每天去辦公室上班，是因為他可以在路上和哥德爾聊天；愛因斯坦的去世也給了哥德爾的心情很大的打擊。

再次，“哥德爾不完全定理”沒有給出人類對真理理解的上限。如果一個命題不能在公理系統(tǒng)中判斷，并不意味著它不能被判斷。對于這類命題，如果屬于科學范疇，可以通過科學實驗進行判斷，從而拓展現(xiàn)有公理體系，發(fā)現(xiàn)新的科學規(guī)律；如果屬于數(shù)學范疇，可以通過尋找新的數(shù)學工具、數(shù)學方法或數(shù)學理論，直接拓展現(xiàn)有公理體系，從而準確判斷這個命題，進而拓展人類研究的深度和廣度。

還有人了解到，數(shù)學研究已經(jīng)證明“在某個公理系統(tǒng)中，不存在可以確定給定命題是否可確定的一般算法”。因此認為存在一個不可判定的命題，不存在“判斷一個命題是否可判定的方法”。顯然，我們不能準確地認識世界。這個觀點不準確。雖然我們確實證明了沒有一般的判斷算法，但是人類并不是僅僅依靠某一套公理系統(tǒng)和某一套邏輯和算法來理解世界的，人類的思維也不能局限于某一套或某一套公理系統(tǒng)。雖然我們不能設計一個通用的算法來判斷一個命題在某個公理系統(tǒng)中是否可以被判斷，但這并不一定導致我們無法識別這個命題。舉個簡單的例子，“Goodstein定理”(這個定理比較簡單易懂，練習到第五級的時候會詳細解釋這個例子)是一個在Piano公理系統(tǒng)中無法判斷的命題，但是在集合論中，利用序數(shù)知識可以非常簡單地證明。

“哥德爾不完全定理”揭示了公理系統(tǒng)的內(nèi)在深刻性和內(nèi)在局限性，告訴我們不要指望所有命題都只能從幾組公理出發(fā)，用基本的邏輯規(guī)則機械地推導出來才能判斷。從這個意義上說，數(shù)學和其他科學都需要不斷完善和拓展自己的公理體系(或基本規(guī)律)，只有這樣才能不斷認識到更深刻、更復雜的客觀世界。換句話說，哥德爾真實而嚴格地證明了“科學研究永無止境”這句格言。

二:“深靜水流”——“哥德爾不完全定理”的深刻背景

哥德爾為什么會想到證明這樣一個“不完全定理”？既然已經(jīng)到了第二層修煉，就應該多說一點。

哥德爾做的第一件事是用自然數(shù)匹配PM中的表達式。在解釋“一致性的意義”時，我們專門介紹了PM中的表達式和相應的規(guī)則。項目管理中的表達式類似于以下示例:

~(?z≤x?(z≠1∧z≠x∧z | x))∧(x & gt；1)(判斷X是否素數(shù)的PM公式)

Qp (~ pq)(我們已經(jīng)證明的公式，矛盾系統(tǒng)可以推出任何命題)

哥德爾說，這些表達式是由一些基本符號組成的，是一系列符號；“證明過程”無非是一個表達式的序列，而是一個符號的序列。根據(jù)希爾伯特的數(shù)學形式化，這些符號、表達式和“證明過程”都是沒有意義的。如果有必要，可以給出一些含義來表達一些現(xiàn)象。哥德爾指出，顯然這些符號被賦予什么意義與PM系統(tǒng)本身無關，所以哥德爾在這里將這些符號對應于自然數(shù)。

所以每個基本符號對應一個自然數(shù)，每個表達式對應一個自然數(shù)序列，每個“證明過程”對應一個自然數(shù)序列。反之，每當給定一個相容的自然數(shù)序列，它就可以唯一地對應一個PM表達式；每次給定一個相容的自然數(shù)序列時，它可以唯一地對應于一個概率模型證明過程。

進一步地，有了這種對應，對PM表達式或證明過程的一些有意義的判斷就可以對應到對某個自然數(shù)序列的判斷，而這種對自然數(shù)序列的判斷顯然可以利用PM中的表達式來進行。換句話說，通過哥德爾建立的對應關系，我們最終可以用PM表達式來表達有意義的判斷。比如，根據(jù)預先對應的定義，一個合法表達式對應的自然數(shù)序列必須滿足一定的規(guī)則，顯然可以用PM表示，所以我們可以用PM給出一個表達式來表達“某個表達式是否符合”的意思。

由于這種對應(也稱為哥德爾對應)對于哥德爾不完全定理的證明至關重要，我們寧愿不厭其煩地給出一個簡單的例子，使讀者能夠準確理解。我們建立了一個類似于哥德爾理論的對應關系，并事先聲明這個對應關系只是為了便于理解下面的例子，但實際上這個對應關系不利于證明哥德爾不完全定理。我們建立的對應關系是:PM系統(tǒng)中的所有符合表達式和證明過程都是按照ASCII字符順序排列，形成一個無窮序列；然后從第一個表達式開始，我們把它對應到自然數(shù)1，第二個對應到3，以此類推，直到無窮；然后把所有不符合的表達式按順序排列，從第一個開始，對應自然數(shù)2，4，6，…。這樣，PM中的任何表達式和證明過程都對應一個唯一的自然數(shù)。我們再定義一個PM表達式，用來判斷一個表達式是否符合。設這個表達式為isFm(x)。顯然，這種對應下的isFm(x)在PM中應該是“~ (z x = 2z)”(注意PM中的任何數(shù)值變量都是0或自然數(shù))。這個表達式其實是判斷x是否奇數(shù)。如果是，則x對應的表達式是順應的，否則是不順應的。所以一個“有意義的表達依從性判斷”在PM中表達為一個表達。

當然，除了表達“表達式是否符合”，還應該表達“一個表達式是否可以在PM系統(tǒng)中證明”。哥德爾把這個表達式設置為可證(x)，他表示自然數(shù)(或者自然數(shù)序列，或者自然數(shù)序列的序列，在練習第四重的時候，你會看到哥德爾用了一個巧妙的方法使這些序列都成為唯一的自然數(shù))。X對應的表達式是否可以在PM系統(tǒng)中

最后強調(diào)哥德爾在PM中的表達式對應的是自然數(shù)，這不是哥德爾研究自然數(shù)或數(shù)論所做的，而是哥德爾提出的一種構造特殊PM表達式的方法。通過將PM表達式映射到自然數(shù)，利用PM系統(tǒng)固有的表達自然數(shù)之間關系的能力，可以達到將PM中的命題引入自身的目的。

如果Rq(q)能被證明，則意味著可證明(Rq(q))為真，這顯然意味著Rq(q)也為真。根據(jù)公式1，~可證明(Rq(q))也成立，“~可證明(Rq(q))”、“可證明(Rq(q))換句話說，如果PM是一致系統(tǒng)，那么只有Rq(q)是不可證明的。

如果~Rq(q)可以證明，說明~Rq(q)是真的。根據(jù)公式1，~(~可證(Rq(q))為真，即可證(Rq(q))可證，即Rq(q)為真。這次Rq(q)和~Rq(q)都是真的。因此，如果PM一致，~Rq(q)無法證明。

綜上所述，只要PM是Rq(q)命題的一致公理系統(tǒng)，它在PM中既不能被證明，也不能被證明。換句話說，在項目管理系統(tǒng)中，可表達的命題Rq(q)不清楚對錯。

通過上面的簡單分析，我們得到“哥德爾第二不完全定理”，簡單地表述為“一個包含皮亞諾公理的公理系統(tǒng)，在這個公理系統(tǒng)中不能證明它的一致性”。

對于愿意學習的讀者，可能還會有各種各樣的疑問？有人可能會問，哥德爾的映射PM表達式對自然數(shù)有什么用，如何用這種方式表達像可證(x)這樣有意義的命題？有人可能會問，你第一次練習的時候說的“ω一致性”和“原始遞歸”到底是什么意思？可能有些讀者會問，第三種介紹的證明思路不就是一個嚴格的證明過程嗎，為什么要培養(yǎng)第四種呢？對于需要解決這些問題的讀者，請和我一起練習第四種魔力。

第五:“洞察過去與現(xiàn)在”——拓展“哥德爾不完全定理”的相關知識

就像金庸的小說《屠龍記》一樣，連創(chuàng)作者都沒有修煉到最高境界。我也不敢說自己培養(yǎng)了第五種魔力。所以這部分有點簡單，只說兩個方面。

(一)“哥德爾不完全定理”的例子

自1931年哥德爾提出不完全性定理以來，人們逐漸相信了復雜公理系統(tǒng)的不完全性。80年來，人們逐漸發(fā)現(xiàn)了越來越多的哥德爾不完全定理的例子，其中最著名的是“選擇公理和連續(xù)統(tǒng)假設是集合論中的不確定命題”。1963年，美國數(shù)學家保羅·寇恩最終證明了這一點，并解決了希爾伯特的23個問題中的第一個，這也是哥德爾的貢獻。

那么有沒有直接符合哥德爾論文條件的例子呢？也就是皮亞諾公理體系中的不確定命題？1982年，人們發(fā)現(xiàn)了算術命題的第一個例子——古德斯坦定理，它不屬于哥德爾結構，在皮亞諾公理體系中不能被證明或證偽。

古德斯坦定理說古德斯坦序列在有限步內(nèi)會收斂到0。

Goodstein序列是這樣的:首先選擇一個正整數(shù)g1，例如，設g1=18，然后寫成2的冪和(18 = 24+ 21)，然后也寫出大于2的指數(shù)。如果重寫后的表達式中有大于2的指數(shù)，那么繼續(xù)把這樣的數(shù)寫成2的冪，直到所有的數(shù)都小于或等于2，最后得到，

g1=22^2+21

這種寫法叫做遺傳基數(shù)2記法。G2就是用這種寫g1的方法把所有的2都變成3，然后從新數(shù)中減去1，就是，

g2=33^3+31-1

注意，這是一個非常大的數(shù)字，大約是7.6×1012。繼續(xù)，以3的冪的形式寫g2，直到?jīng)]有大于3的數(shù)，然后用4代替3，所得數(shù)減1得到g3。通過類比，我們可以通過連續(xù)計算得到一個級數(shù)。這個系列就是古德斯坦系列。

讓我們以g1=18為例，看看這個系列的前幾項:

g1=22^2+21=18

g2=33^3+31-1=33^3+2×30=7.6×1012

g3=44^4+2×40-1=44^4+40=1.3×10154

g4=55^5+50-1=55^5=1.9×102184

單看這些項，我們肯定會認為這個級數(shù)以極快的速度發(fā)散到無窮。事實上，這個系列將在有限的步驟中收斂到0。

古德斯坦定理是一個容易理解的算術命題，其證明可以通過集合論、良序定理、超限序數(shù)等理論和知識來完成。一般的思路是利用超限序數(shù)ω構造一個與Goodstein級數(shù)平行的級數(shù)。這個新數(shù)列的每一項都不小于Goodstein數(shù)列的對應項，而且這個新數(shù)列是遞減的，經(jīng)過有限步后必然收斂到0。

證明了集合論中的Goodstein定理簡單易懂。但是當我們在Piano公理系統(tǒng)中研究這個命題的時候，神奇的事情發(fā)生了。1982年，勞里·柯比和杰夫·帕里斯發(fā)現(xiàn)這個定理在皮亞諾公理體系下是不可證明的。這個定理只是哥德爾不完全定理的一個典型例子。

前面說過，哥德爾的不完全性定理是通過構造一個不可驗證的算術命題來證明的。但是，隨著我們練習了第五魔功，我們清楚地知道，哥德爾構造的這個算術命題幾乎不可能直接表達，因為做起來太復雜了。所以哥德爾只是通過構造方法證明了不可證明命題的存在。直到古德斯坦定理的發(fā)現(xiàn)，我們終于可以在皮亞諾公理體系中看到一個不確定的算術命題。Goodstein定理簡單易懂，計算過程清晰，但在Piano的公理體系中無法證明，想想就覺得很神奇。所以我們更應該佩服哥德爾的偉大貢獻。

(2)有一致完整的公理體系

關于哥德爾不完全定理，我們討論了這么多，估計大家無疑都相信了這個定理。在這里，我們要再次提醒大家，哥德爾不完全定理有一個前提條件，那就是“包含鋼琴公理系統(tǒng)”。也就是說，不是任何一致的公理系統(tǒng)都是不完整的。那么，真的存在一致完整的公理體系嗎？答案是肯定的。

我可以為這里的每個人即興創(chuàng)作一個公理系統(tǒng):

這個公理系統(tǒng)只有兩個數(shù)字0和1，只有一個二進制運算“+”。它的三個公理如下。

(1)0+0=0

(2)0+1=1+0=1

(3)1+1=0

公理系統(tǒng)已經(jīng)建立。

這個公理系統(tǒng)極其簡單，在這個系統(tǒng)中能表達的命題都可以證明(比如1+1+1+0=1)，而且這個公理系統(tǒng)必須是一致的，“ω一致”。

事實上，如果一個公理系統(tǒng)比較簡單，不能承受哥德爾對應中的最小編碼要求，那么這個公理系統(tǒng)的一致性和完備性之間是否存在矛盾，就不屬于哥德爾定理所覆蓋的范疇。對于一些簡單的公理系統(tǒng)，可以證明它們是一致的、完備的。當然，我構建的公理系統(tǒng)太簡單了，根本沒有用。在實際數(shù)學中，有一個系統(tǒng)叫做預伯格算法(Presburger algorithm)。因為不包括乘法，所以其實是一致的，完整的。有興趣可以通過Google詳細了解。

另外，如果一些復雜的公理不足以定義自然數(shù)，那么即使這樣的公理包含自然數(shù)，也可能不受哥德爾不完全定理的約束。比如Taskey證明了實數(shù)和復數(shù)理論都是一致的、完備的一階公理系統(tǒng)，雖然都包含自然數(shù)；再比如，著名的歐氏幾何，在補充了平行公理和實數(shù)理論之后，也是一個一致完整的一階公理系統(tǒng)。

《哥德爾不完全定理》確實很棒，但不需要神化。它有它的前提條件，有它的適用范圍，當然也有劃時代的偉大貢獻！

結論

至此，五大神通都已修煉完畢?！案绲聽柌煌耆ɡ怼笔莿潟r代的成就，也是哥德爾一生中唯一的重大研究成果。作為一名數(shù)學家和邏輯學家，哥德爾一生取得了如此巨大的成就，這是值得的。作為讀者，如果能通過這個培養(yǎng)過程，真正理解和領會哥德爾的不完全定理，我認為值得花時間去閱讀和思考。

[1]哥德爾論文的英文版可以在http://www.research.ibm.com/people/h/hirzel/papers/canon·00-goedel.pdf的網(wǎng)上找到。

[2]我實在不忍心這樣形容羅素和懷特海。參見維基百科的《https://zh.m.wikipedia.org/zh-hans/數(shù)學原理》，了解“智力枯竭”這一表述

[3]參見http://blog.sciencenet.cn/blog-320682-969874.html科學網(wǎng)張銀生先生的博客

本文來自趙科學網(wǎng)博客:

鏈接地址:http://blog.sciencenet.cn/blog-409681-1067019.html