（一）

【中文網(wǎng)上深入介紹哥德爾不完備定理的文章很少，我這篇文章寫得很長，花了不少時間打磨它，希望能幫助到愛好數(shù)學(xué)與邏輯的人。文章把理解哥德爾不完備定理分為了五重，建議只是想初步了解的讀者，可以重點(diǎn)看第一重；希望了解一些背景的讀者，可以修煉到第二重；希望較深入理解哥德爾證明思路的讀者，建議修煉到第三重；如果確實(shí)感興趣，希望詳細(xì)了解哥德爾證明過程以及其嚴(yán)謹(jǐn)性的讀者，可以修煉到第四重；如果還想多知道一些知識的讀者，可以練到第五重。——— 作者】

1931年，庫爾特?弗雷德里希?哥德爾（KurtFriedrich G?del）發(fā)表了一篇影響深遠(yuǎn)的論文“On formally undecidablepropositions of Principia Mathematica and related systems I”^[1]（論文的原文是用德文發(fā)表的，這里給出的是英譯名）。今天，我們一般籠統(tǒng)的把論文中提出的定理稱為“哥德爾不完備定理”。80多年過去了，“哥德爾不完備定理”的影響仍然持續(xù)、深遠(yuǎn)，特別是引起了很多非數(shù)學(xué)界人士的興趣，引發(fā)了各種各樣的解讀。很遺憾，有一些解讀是不準(zhǔn)確的，甚至是錯誤的；更為嚴(yán)重的是，有一些人出于對“哥德爾不完備定理”的一知半解，甚至開始懷疑、批判人類的理性，以至于發(fā)展到相信、鼓吹不可知論。近期，我在認(rèn)真研讀了哥德爾論文原文（英譯版，本人實(shí)在是不懂德文）和相關(guān)資料的基礎(chǔ)上，加深了自己的認(rèn)識，同時也很希望盡自己綿薄之力，分享對“哥德爾不完備定理”的理解，厘清對“哥德爾不完備定理”的誤解。

“哥德爾不完備定理”是數(shù)學(xué)、邏輯學(xué)領(lǐng)域的劃時代成果，使人們對于數(shù)學(xué)研究基礎(chǔ)的認(rèn)識更加深刻、準(zhǔn)確，同時它也是現(xiàn)代邏輯史上的重要里程碑。“哥德爾不完備定理”雖然偉大、深刻，但是個人認(rèn)為它并不深奧。對于一個普通人，只要愿意動腦，都可以在一定程度上準(zhǔn)確理解它。當(dāng)今的互聯(lián)網(wǎng)時代，網(wǎng)上有不少對“哥德爾不完備定理”的介紹和解讀；60多年前，兩位美國作家歐內(nèi)斯特·內(nèi)格爾（Ernest Nagel）和詹姆士 R. 紐曼 （James R. Newman）撰寫的的著作《哥德爾證明》更是科普“哥德爾不完備定理”的重要作品。如今網(wǎng)上能看到的中文介紹“哥德爾不完備定理”的文章，絕大部分是轉(zhuǎn)述《哥德爾證明》這本書的內(nèi)容的。不過這本書撰寫太早，有些新的結(jié)論當(dāng)年尚不了解；另外這本書在普及哥德爾證明的時候，更多的是講解背景、思路，并用作者自己的理解來講述哥德爾的證明，個別地方不夠嚴(yán)謹(jǐn)，一些講述方式也不夠準(zhǔn)確。本文則全部基于哥德爾論文的原文來介紹“哥德爾不完備定理”的證明，并適當(dāng)融入一些80多年來新的認(rèn)識和結(jié)論，希望能幫助數(shù)學(xué)、邏輯學(xué)愛好者了解并理解“哥德爾不完備定理”。

為了幫助更多人在各自需要的層面上理解“哥德爾不完備定理”，下面的介紹把理解“哥德爾不完備定理”分為了五重，從對定理的基本含義的理解一直到對核心證明的了解都包括了進(jìn)來。讀者可以像修習(xí)“乾坤大挪移”神功一樣，依照自身內(nèi)力基礎(chǔ)，修煉到適合自己的層面即可。祝愿大家都能練成“哥德爾不完備定理”第五重神功！

第一重：“廬山真面目”——準(zhǔn)確了解“哥德爾不完備定理”

賞玩一塊美玉的時候，首先不應(yīng)該是聽各類專家講這塊玉多么晶瑩剔透、多么價值連城，而應(yīng)該是首先把玉拿出來讓大家看看，有個感性認(rèn)識。在哥德爾的論文中，我們一般所說的“哥德爾不完備定理”（有時候也被叫做“哥德爾第一不完備定理”）是指論文中的定理VI，原文如下：

TheoremVI: For every ω-consistent primitive recursive class κ of formulae, there is aprimitive recursive class-sign r , such that neither forall(v,r) nornot(forall(v,r)) belongs to Conseq(κ) (where v is the free variable of r).

盡量原汁原味的翻譯如下：

定理VI：對于任意一個ω一致_{（第四重）}的原始遞歸公理集合κ，一定存在一個原始遞歸_{（第三重、第四重）}的表達(dá)式r，使得無論是“r總成立”這個命題，還是“r不總成立”這個命題，都不屬于通過κ可推導(dǎo)出來的定理的集合（原文中的Conseq(κ)）。

補(bǔ)充說明一點(diǎn)，哥德爾論文中的κ所代表的公理集合，是指蘊(yùn)含了皮亞諾算術(shù)公理（Peano Axioms）的集合，這是在哥德爾論文的前面明確了的，所以在闡述定理VI時就沒有再特意強(qiáng)調(diào)。

修煉第一重神功的讀者可能會問了“大哥，你說的這些都是啥？”。別擔(dān)心，修煉第一重神功沒那么復(fù)雜。

讓我們先從公理說起，公理其實(shí)就是無需證明而被認(rèn)定為成立的命題。公理體系是指一組公理的集合。通過這些公理和基本的邏輯關(guān)系，可以推導(dǎo)出更多成立的命題，稱為定理。公理體系一般被認(rèn)為發(fā)源于2300多年前歐幾里德撰寫的《幾何原本》。在現(xiàn)代科學(xué)形成的過程中，人們發(fā)現(xiàn)通過定義一組公理再加上合理的邏輯推演，可以證明很多命題或結(jié)論。公理體系是當(dāng)今數(shù)學(xué)研究和科學(xué)研究的基礎(chǔ)，數(shù)學(xué)研究成果就是（或者說在極大的程度上依賴于）一組公理體系的推演，而其它科學(xué)研究除了依賴公理體系進(jìn)行推演外，還需要通過系統(tǒng)的實(shí)驗來進(jìn)行驗證。

“哥德爾不完備定理”是針對公理體系的一項結(jié)論，它之所以如此偉大且深刻，正是因為它撼動的是一切科學(xué)的研究基礎(chǔ)——公理體系。修煉第一重神功的時候，我們簡要理解“哥德爾不完備定理”說的是：一個足夠復(fù)雜的公理體系（至少蘊(yùn)含了皮亞諾算術(shù)公理），如果它是一致的（相容的，無矛盾的），那么它就是不完備的。這里的完備，指的是“對于任何可在這個公理體系內(nèi)描述的命題，都可以在這個公理體系內(nèi)得到判定，要么是正確的，要么是錯誤的”。

再用大白話解釋一下，就是說，一個沒有矛盾的公理體系內(nèi)，總有一些命題是說不清楚對還是錯的（務(wù)必注意，這是指在這個體系內(nèi)說不清楚，不是說永遠(yuǎn)都說不清楚了）。也許有人說了，既然沒矛盾的公理體系有問題，那就搞個有矛盾的公理體系唄。如果設(shè)想一個公理體系，一會兒告訴我們“1+1=2”，一會兒又告訴我們“1+12”，相信不會再有人把這個公理體系當(dāng)回事。有矛盾的公理體系會導(dǎo)致徹底的無意義和虛無，修煉第二重神功的時候會詳細(xì)闡明這一點(diǎn)。

上述結(jié)論聽起來是比較可怕的，公理體系必須沒有矛盾，可是沒有矛盾的公理體系又會導(dǎo)致出現(xiàn)一些命題說不清楚對錯。于是開始出現(xiàn)了各種各樣的解讀，比如“哥德爾定理告訴了我們數(shù)學(xué)和邏輯的極限，這也幾乎是人類理性的極限。它證明理性不是無所不能的”、“哥德爾定理告訴我們，人類不可能真正認(rèn)識這個世界，永遠(yuǎn)不可能理解宇宙的真理”等等。相信作為人類理性智慧光輝代表之一的哥德爾，如果聽到這些說法，可能也會很無奈吧。

第一，“哥德爾不完備定理”不僅不是所謂人類理性的極限，恰恰相反，它是人類理性智慧的重大成果。它告訴了我們，正是由于有了人類理性的智慧，才有可能認(rèn)識到這樣深刻的結(jié)論。哥德爾是通過構(gòu)造出了一個無法在這個公理體系內(nèi)證明的命題來證明出“哥德爾不完備定理”的。這個命題的內(nèi)容說的正是“命題自身無法在此公理體系內(nèi)被證明”，既然哥德爾已經(jīng)清楚的證明了這一點(diǎn)，說明這個命題毫無疑問是正確的。所以，“哥德爾不完備定理”的證明過程其實(shí)告訴了我們，存在一個可在這個公理體系內(nèi)表達(dá)的正確的命題，但是在這個公理體系內(nèi)卻既不能證明它，也無法證偽它。如果說“哥德爾不完備定理”闡明了什么極限的話，那它闡明的也只是“某類公理體系的極限”，而不是“數(shù)學(xué)、邏輯的極限”，更不是什么“人類理性的極限”。

第二，“哥德爾不完備定理”不僅不會告訴我們“人類不可能真正認(rèn)識這個世界”，反而是在更深刻的層面上告訴了我們?nèi)祟悜?yīng)該如何去認(rèn)識世界、探索真理。譬如在數(shù)學(xué)上，如果發(fā)現(xiàn)一個命題通過現(xiàn)有的方法、公理和定理一直得不到證明，我們就可以嘗試擴(kuò)展現(xiàn)有的方法和公理體系來進(jìn)一步研究；費(fèi)馬大定理、黎曼猜想等命題被稱為“會下金蛋的母雞”就是這個道理。物理學(xué)上，廣義相對論的發(fā)現(xiàn)過程，也是因出現(xiàn)了平直空間中狹義相對論某些推論難以解釋（如高速旋轉(zhuǎn)的圓盤會發(fā)生扭曲），愛因斯坦提出了等效原理并毅然拓展了平直空間的假設(shè)，創(chuàng)建了廣義相對論這個偉大的理論。值得一提的是，哥德爾和愛因斯坦在普林斯頓大學(xué)成為了非常好的朋友。晚年的愛因斯坦曾經(jīng)說過，之所以他每天還會經(jīng)常堅持去辦公室上班，是因為可以在路上和哥德爾聊聊天；而愛因斯坦的去世也曾給哥德爾的情緒以很大打擊。

第三，“哥德爾不完備定理”也沒有給出人類認(rèn)識真理的上限。如果一個命題在某個公理體系內(nèi)無法判定，那也不是意味著這個命題就是無法判定的了。對于這類命題，如果屬于科學(xué)范疇的，可以通過科學(xué)實(shí)驗加以判定，從而擴(kuò)展現(xiàn)有的公理體系，發(fā)現(xiàn)新的科學(xué)規(guī)律；如果屬于數(shù)學(xué)范疇的，可以通過尋找新的數(shù)學(xué)工具、數(shù)學(xué)方法或者數(shù)學(xué)理論來直接拓展現(xiàn)有公理體系，從而準(zhǔn)確的判定這個命題，進(jìn)而擴(kuò)大人類研究的深度和廣度。

還有人了解到，數(shù)學(xué)研究已經(jīng)證明了“不存在一個通用的算法，能夠判定一個給定的命題在某個確定的公理體系內(nèi)是否是可判定的”。由此認(rèn)為既存在著不可判定的命題，又不存在“能夠判定某個命題是否不可判定的方法”，顯然我們沒法準(zhǔn)確認(rèn)識這個世界了。這種觀點(diǎn)是不準(zhǔn)確的。雖然我們的確證明了不存在通用的判定算法，但是人類認(rèn)識世界不是只依靠某組公理體系和確定的邏輯與算法的，人類的思維也不可能只局限在某個或者某組公理體系之內(nèi)。雖然我們無法設(shè)計出一個通用算法，來判定一個命題是否在某個公理體系內(nèi)可判定，但是這并不必然導(dǎo)致我們無法認(rèn)知這個命題。舉個比較簡單的例子，“Goodstein定理”（這個定理相對簡單易懂，修煉到第五重的時候會詳細(xì)說明這個例子）就是一個在皮亞諾公理體系里無法判定的命題，但是在集合論中，利用序數(shù)知識可以非常簡單的證明它。

“哥德爾不完備定理”揭示了公理體系內(nèi)在而深刻的性質(zhì)和固有局限性，告訴我們不要奢望僅僅通過若干組公理出發(fā)，機(jī)械地利用基本邏輯規(guī)則進(jìn)行推導(dǎo)，就能夠?qū)θ康拿}進(jìn)行判定。從這個意義上講，無論是數(shù)學(xué)還是其它科學(xué)，都需要不斷的完善、擴(kuò)充自身的公理體系（或者基本規(guī)律），只有這樣才能不斷認(rèn)知更加深刻復(fù)雜的客觀世界。或者說，哥德爾真正嚴(yán)格證明了這句格言——“科學(xué)研究是永無止境的”。

（二）

第二重：“靜水流深”——“哥德爾不完備定理”的深刻背景

哥德爾為什么會想到證明這樣一個“不完備定理”呢？既然已經(jīng)修煉到第二重了，就稍微說的多一點(diǎn)。

（一）數(shù)學(xué)公理化

人們經(jīng)常說，數(shù)學(xué)研究領(lǐng)先其他學(xué)科研究至少200年。其實(shí)在上上個世紀(jì)，也就是19世紀(jì)的時候，數(shù)學(xué)研究就已經(jīng)大幅度超前于其他學(xué)科的研究了。數(shù)學(xué)家以及很多科學(xué)家們越來越意識到數(shù)學(xué)應(yīng)該是一個公理化的系統(tǒng)，它的結(jié)構(gòu)應(yīng)該是這樣的——首先定義一批公理和基本邏輯規(guī)則，然后依據(jù)這些公理和邏輯規(guī)則可以推演出這個體系內(nèi)的無窮多的定理——這就應(yīng)該是理想的數(shù)學(xué)。

倡導(dǎo)并推進(jìn)數(shù)學(xué)公理化的最主要代表人物就是德國數(shù)學(xué)家大衛(wèi)·希爾伯特（David Hilbert），19世紀(jì)和20世紀(jì)最具影響力的大數(shù)學(xué)家之一。希爾伯特的影響力主要體現(xiàn)在他于1900年在巴黎舉行的第二屆國際數(shù)學(xué)家大會上作的題為《數(shù)學(xué)問題》的演講。在這個演講中，希爾伯特提出了23個他認(rèn)為最重要的數(shù)學(xué)問題，而這23個問題至今還在指引著數(shù)學(xué)家的研究方向。

這23個問題中的第2個問題，就是有關(guān)數(shù)學(xué)公理化的。希爾伯特說：“在這些無數(shù)個問題之上，我傾向于確定下面這個問題才是最重要的：這些公理在經(jīng)過有限步驟的推演后是不會導(dǎo)致相互矛盾的結(jié)論的。……也就是說，我們需要一個關(guān)于算術(shù)公理一致性（相容性）的證明。”。

1910～1913年，懷特海（Alfred North Whitehead）和羅素（Bertrand Russell）撰寫的《數(shù)學(xué)原理》（《Principia Mathematica》）的發(fā)表，是數(shù)學(xué)公理化推進(jìn)的又一里程碑事件。《數(shù)學(xué)原理》希望從最基礎(chǔ)的邏輯出發(fā)來定義全部數(shù)學(xué)，試圖構(gòu)建一個宏大的邏輯體系結(jié)構(gòu)，徹底的解決數(shù)學(xué)公理化的問題。我們只要稍微想象一下，就能夠猜到這個過程有多復(fù)雜，特別是羅素還要在這個過程中消除自己發(fā)現(xiàn)的“羅素悖論”（后面會提到）。直到《數(shù)學(xué)原理》第一卷的363頁，才推導(dǎo)出了數(shù)字“1”的定義；第二卷又費(fèi)了很大的力氣，證明了乘法交換律。《數(shù)學(xué)原理》工程浩大，兩位作者只完成了前三卷，覆蓋了集合、基數(shù)、序數(shù)和實(shí)數(shù)的相關(guān)內(nèi)容，雖然對第四卷幾何的基礎(chǔ)做了籌劃，但整個體系結(jié)構(gòu)實(shí)在太過復(fù)雜，兩位作者“才智枯竭”^[2]，實(shí)在無法再寫下去了。

數(shù)學(xué)公理化推進(jìn)的最關(guān)鍵標(biāo)志性事件是1920～1923年間，希爾伯特推動的“希爾伯特計劃”。這個計劃的主要目標(biāo)，是為全部的數(shù)學(xué)提供一個安全的理論基礎(chǔ)。這個計劃對數(shù)學(xué)公理化提出了如下要求：

• 形式化：形式化是希爾伯特提出來的一個關(guān)鍵思想，意思是，所有數(shù)學(xué)應(yīng)該使用用統(tǒng)一的、嚴(yán)格的、無意義的、形式化的語言來表述，并且按照一套嚴(yán)格的、基礎(chǔ)的邏輯規(guī)則來推演。

• 完備性：形式化之后，數(shù)學(xué)里所有的真命題都可以通過上述規(guī)則被證明。

• 一致性：運(yùn)用這一套形式化的表達(dá)和規(guī)則，不可能推導(dǎo)出矛盾。

• 保守性：這是針對形式化而言的，即如果賦予一些形式化的表達(dá)以含義（希爾伯特將這稱為元數(shù)學(xué)），并由此證明了某些結(jié)論，那么必須保證即使不賦予這些含義，依然可以證明同樣的結(jié)論。

• 確定性：可以通過一個算法來確定每一個形式化的命題是真還是假。

對于修煉完成了“哥德爾不完備定理”第一重神功的讀者來說，應(yīng)該會看出上述“希爾伯特計劃”是有問題的。沒錯，之所以我們比大數(shù)學(xué)家希爾伯特還要目光如炬，是因為我們站在哥德爾這個巨人的肩膀上！要知道，在哥德爾的論文發(fā)表之前，甚至是發(fā)表之后的一段時間，主流數(shù)學(xué)家、邏輯學(xué)家們?nèi)匀徽J(rèn)為希爾伯特計劃毫無疑問是正確的，問題只不過是如何給出證明罷了。

（二）一致性（相容性）的重要意義

在詳細(xì)闡述“哥德爾不完備定理”對數(shù)學(xué)公理化特別是“希爾伯特計劃”的影響之前，我們先來談一下“一致性”的重要意義。這里說的“一致性”就是指很多文章或書籍里面說的“相容性”，希爾伯特說的compatibility，哥德爾說的consistency，意思是“無矛盾的”。

在修煉第一重神功的時候，我們談到構(gòu)造一個不一致（不相容、存在矛盾）的公理體系是無意義的。從直覺出發(fā)，我們都清楚，存在矛盾的體系當(dāng)然有問題了。這里，我們給出邏輯上的說明（或者說證明）。

做這件事之前，讓我們先來感謝羅素和懷特海，是他們的艱苦工作成果《數(shù)學(xué)原理》給出了數(shù)學(xué)形式化的基礎(chǔ)。我們正是以此為基礎(chǔ)，來說明一致性的重要意義。另外，了解《數(shù)學(xué)原理》中給出的數(shù)學(xué)形式化的基本表示，也是繼續(xù)修煉第三重、第四重神功的基礎(chǔ)，因為哥德爾就是基于《數(shù)學(xué)原理》中數(shù)學(xué)形式化的表達(dá)來證明“哥德爾不完備定理”的。

由于形式化表達(dá)的符號存在不同的樣式，為避免歧義，本文中數(shù)學(xué)形式化的表達(dá)與哥德爾論文中的樣子保持一致。以下是數(shù)學(xué)形式化的基本原則：

（1）使用字母（一般使用p、q、r等）表示命題變量，即一個字母表示一個命題；使用如下符號表示特定邏輯（注意，形式化之后的表達(dá)式是無含義的，因此這些符號僅表示某種邏輯關(guān)系）：

～        邏輯“非”；

∨        邏輯“或”；

?    邏輯“推出”，意思是“如果……那么……”；

∧        邏輯“與”；

?x?p   對于任意x，p都成立；

?x?p   存在x使p成立；

（2）組成合理的命題表達(dá)式。譬如，“p∨q”就是一個合理的命題表達(dá)式，而“p∨”就是一個錯誤的表達(dá)式。

（3）兩條變換規(guī)則：一是代入規(guī)則，可以使用其它的命題表達(dá)式對某個命題表達(dá)式中的某個命題變量進(jìn)行全部統(tǒng)一替換；二是分離規(guī)則，其實(shí)就是我們常說的邏輯三段論，已知p和p?q成立，則q成立。

（4）《數(shù)學(xué)原理》提出的四條基本邏輯推演公理：

(p∨p)?p

p?(p∨q)

(p∨q)?(q∨p)

(p?q)?((r∨p)?(r∨q))

大家可能覺得這四條基本邏輯推演公理看起來像是廢話，由此可知《數(shù)學(xué)原理》這本巨著是從多么基礎(chǔ)的邏輯出發(fā)的。不要小看這四條基本推演公理，它們可以推導(dǎo)出難以想象的復(fù)雜的結(jié)論。

好，以上四條數(shù)學(xué)形式化的基本原則敘述完畢，下面開始推出一個邏輯定理：p?(~p?q)。推演過程如下：

根據(jù)第二條推演公理，得到p?(p∨q)；

根據(jù)變換規(guī)則二，設(shè)p成立，則得到如下結(jié)論，

p∨q成立；

在p成立的前提下，設(shè)～p成立（即p不成立），則由∨邏輯的基本含義得到q成立（意思就是，“p或q”成立，且p不成立，那么必然q要成立）；

根據(jù)上述結(jié)果，在p成立的條件下，如果～p也成立，那么q成立。

于是得到上面的邏輯定理p?(~p?q)。注意，這里面q是一個自由的命題變量，根據(jù)基本變換規(guī)則一，可以把任何命題代入q。因此，我們得到了一個重要結(jié)論，如果有一個命題“p”和它的邏輯非“～p”都成立，那么任意命題q都成立。也就是說，有矛盾的公理體系可以推導(dǎo)出任意命題都成立。這就是為什么公理體系必須一致，不一致的公理體系為什么無意義的原因了。

（三）數(shù)學(xué)形式化的目的

在談完了“一致性”的意義后，我們還要再談一下為什么希爾伯特要搞數(shù)學(xué)形式化？希爾伯特是提出數(shù)學(xué)形式化的代表人物，他提出數(shù)學(xué)形式化的目的還是從證明“希爾伯特第2問題”出發(fā)來考慮的。人們之所以篤信公理體系必然是一致的、無矛盾的，其實(shí)是因為人們?nèi)粘Ｑ芯坎?yīng)用的公理體系都是有含義的，都是對應(yīng)著客觀實(shí)體的。人們相信客觀實(shí)體及其規(guī)則是不會發(fā)生矛盾的。這正像我們中國成語“自相矛盾”故事所說的，一個無堅不摧的矛和一個無比堅固的盾在現(xiàn)實(shí)世界是不會同時存在的，只要用這個矛刺一下這個盾，就會有一方露餡。可是我們的公理體系不總是對應(yīng)著存在的客觀實(shí)體，很多情況下（特別是數(shù)學(xué)中）的公理體系對應(yīng)著抽象實(shí)體或者理想實(shí)體（如集合、點(diǎn)、線、面），而且被對應(yīng)的實(shí)體是無窮多的，我們無法通過有限枚舉來證明這些公理體系的一致性。

由此，希爾伯特想到，徹底拋棄（數(shù)學(xué)）公理體系中的含義，構(gòu)造一個形式化的公理體系，這個體系內(nèi)的各種表達(dá)式僅僅具有符號意義。如果能由此證明這樣的公理體系的一致性，那么無論把任何含義賦予這個公理體系時，必然是無矛盾的、一致的了。

正是由于希爾伯特這個想法，以及羅素和懷特海的“身體力行”，才使得哥德爾最終發(fā)現(xiàn)了不完備定理。否則，人們在研究公理體系的時候，總會把它對應(yīng)的含義和其邏輯關(guān)系一起考慮，就不太容易把思路聚焦到公理體系的邏輯本身上面，也就不容易發(fā)現(xiàn)“哥德爾不完備定理”了。

（四）“哥德爾不完備定理”打破了“希爾伯特計劃”么？

最后讓我們再回到“哥德爾不完備定理”，看看哥德爾是如何在數(shù)學(xué)公理化（以及公理體系形式化）的大背景下“釜底抽薪”的。我們先來看“希爾伯特計劃”的幾個要素：

一是形式化。顯然，“哥德爾不完備定理”并沒有反對形式化，而且正是通過《數(shù)學(xué)原理》中公理體系形式化的成果，哥德爾才證明了不完備定理。

二是完備性和一致性。“哥德爾不完備定理”明確指出了公理體系完備性和一致性的矛盾之處，它證明了一致的公理體系（指蘊(yùn)含皮亞諾公理的公理體系，以下類似，不再贅述）必然是不完備的，也就是說，完備性和一致性不可能同時獲得。另外，“哥德爾不完備定理”還有一個推論，一般被叫做“哥德爾第二不完備定理”，它表明公理體系的一致性不能在這個公理體系內(nèi)被推導(dǎo)出來。也就是說，不僅完備性和一致性有矛盾，即使是一致性本身，也不能在公理體系內(nèi)得到證明（這個結(jié)論似乎顯得更可怕）。

三是保守性。事實(shí)上，保守性也不再成立了。在“哥德爾不完備定理”的詳細(xì)證明過程（第四重）和“Goodstein定理”介紹（第五重）中，我們就可以發(fā)現(xiàn)，當(dāng)賦予了某些含義給公理體系之后，原來不可證明的命題變得可證明了。個人認(rèn)為，賦予含義的過程本身就是在擴(kuò)充這個公理體系（個人觀點(diǎn)，可討論）。這也是為什么哥德爾構(gòu)造的forall(v,r)這個命題在《數(shù)學(xué)原理》確定的邏輯基礎(chǔ)和皮亞諾公理體系內(nèi)不可通過形式化的推演而證明，但是卻在哥德爾的論文中被證明了的原因。哥德爾論文中也提到了，provable(x)是他構(gòu)造的46個表達(dá)式中唯一個不能斷言為原始遞歸性質(zhì)的，這說明命題的“可證性”某種意義上是被哥德爾新賦予的含義。

四是確定性。顯然確定性也不成立，因為哥德爾證明了存在某些命題無法證明其真假。而且就算在確定性判斷的“真”和“假”以外加入“不可證明”這一類，也是不成立的。我們前面提到過，沒有一個通用的算法能夠判定任意命題是否不可證。

從上面這些要素來看，除了公理形式化沒有問題外，其他要素都存在問題，要么互相矛盾，要么根本不成立。從這個意義上講，“希爾伯特計劃”確實(shí)被打破了，這也是當(dāng)年“哥德爾不完備定理”最重大且最直接的影響。

“哥德爾不完備定理”發(fā)表時，希爾伯特還在世，面對這個偉大成果，大數(shù)學(xué)家希爾伯特也只能退讓，不過只是略微退讓。畢竟哥德爾只是在某一個范疇內(nèi)（皮亞諾公理體系+原始遞歸性質(zhì)）構(gòu)造出了一個在公理體系內(nèi)不可證明的命題，剔除這個范疇之后，結(jié)果又會是怎么樣的呢（第五重）？

無論怎樣，我們必須指出希爾伯特“為全部的數(shù)學(xué)提供一個安全的理論基礎(chǔ)”這個目標(biāo)并沒有被打破，通過不斷擴(kuò)展公理體系，我們?nèi)匀豢梢詾閿?shù)學(xué)提供一個越來越安全的基礎(chǔ)，只不過這個公理體系結(jié)構(gòu)看起來要從原來的“有限”變?yōu)椤盁o限”了^[3]。

（三） 

第三重：“驚鴻一瞥”——“哥德爾不完備定理”的概要證明思路

首先恭喜開始修煉第三重神功的讀者，相信你們已經(jīng)對“哥德爾不完備定理”有了足夠的理解了，現(xiàn)在我們開始進(jìn)入到“哥德爾不完備定理”的證明思路中。

哥德爾在25歲就發(fā)表了這篇偉大的論文，但是哥德爾這個人卻是一個很謹(jǐn)慎細(xì)致的人，他知道自己這篇論文可能帶來的影響，因此他非常擔(dān)心別人沒有讀懂它，或者引發(fā)什么誤會。為此，在這篇論文的第一部分Introduction中，哥德爾概括但細(xì)致地給出了整個證明的思路。

不過，在我們理解哥德爾的證明思路之前，讓我們先從更簡單、更易懂的方式入手來逐步進(jìn)入狀態(tài)。

（一）悖論式語言

喜歡搞點(diǎn)邏輯類腦筋急轉(zhuǎn)彎的讀者可能了解一些悖論式的語言，譬如“這句話是謊話”。這句話到底對不對呢？如果說它對，那么它就真的是謊話了，既然是謊話，那么顯然是不對的；如果說它不對，就意味著它不是真話而是謊話，顯然它又對了。對可以推演出不對，不對卻可以推演出對，這種語言可以稱之為“悖論式語言”。由此，我們可以給出一個結(jié)論，能用語言表達(dá)的語句中，一定存在既不能說明它對也不能說明它錯的句子。于是我們可以說，語言體系的邏輯表達(dá)是不完備的。

如果有人以為這就證明了“哥德爾不完備定理”，那未免太天真了。這種邏輯悖論在幾千年前就被人們發(fā)現(xiàn)了，如果像希爾伯特、羅素等大數(shù)學(xué)家、邏輯學(xué)家連這個問題都搞不定，還有什么資格去推進(jìn)數(shù)學(xué)公理化和公理體系形式化呢？

其實(shí)，這種悖論式語言在《數(shù)學(xué)原理》所定義的形式化公理體系中是無法表達(dá)的。設(shè)這句話（看作一個命題）為X，那么“這句話是謊話”就應(yīng)該表達(dá)為“~X”。而悖論式語言需要把“~X”定義成X自己，也就是讓“X=(~X)”，這是無論如何也不可能通過《數(shù)學(xué)原理》中的四條基本邏輯推演公理推演得到的結(jié)論。所以，這種悖論式語言只能證明“人類的語言體系邏輯表達(dá)不完備”，而并不能證明“公理體系不完備”。但是，這個思路和哥德爾的證明是有著相通之處的。

（二）羅素悖論

如果小時候?qū)?shù)學(xué)與邏輯感興趣，也許會記得那個“只給不給自己理發(fā)的人理發(fā)”的理發(fā)師？這個悖論其實(shí)就是羅素悖論，只不過為了讓人容易理解，把抽象的羅素悖論給改頭換面了一下。羅素悖論是集合論中的一個經(jīng)典悖論，我們把若干具有同一性質(zhì)的對象劃分為一個類，類中的這些對象被稱為類的元素，當(dāng)然，某些情況下類里面的元素也可能是一個類。現(xiàn)在我們設(shè)計某一種性質(zhì)P(x)= x?x ，也就是說具有性質(zhì)P的對象不是自身的元素。那么，滿足性質(zhì)P的類為A={x|x?x}。此時，如果我們想判定A這個類是否是A自身的元素時，悖論就出現(xiàn)了，如果A∈A，根據(jù)性質(zhì)P，得到A?A；如果A?A，那么A就滿足性質(zhì)P，則A∈A。

羅素悖論是不能僅僅歸因于語言表達(dá)的不嚴(yán)謹(jǐn)?shù)模聦?shí)上這是一個實(shí)實(shí)在在的悖論，是關(guān)于類的公理體系必須要解決的問題。后來，人們修改了類的內(nèi)涵公理，并提出了一個新的概念——集合。集合是能夠成為某一個類的元素的那種類。由此，我們把類分成了兩種，一種是集合，另外一種是真類（不能成為任何類的元素的類）。由于羅素悖論與“哥德爾不完備定理”的證明沒有直接關(guān)系，因此本文不再討論它了，有興趣的讀者可以自行深入了解。

之所以在這里談到了羅素悖論，是因為希望讀者知道，當(dāng)公理體系引發(fā)了悖論之后，人們馬上就會通過定義新的概念、提出或者修改公理來完善它。可是，當(dāng)哥德爾的證明也構(gòu)造出了類似悖論的命題之后，人們寧可接受這個命題是不可證明的，也沒有試圖通過修補(bǔ)公理體系來解決這個問題。因為通過哥德爾的方法構(gòu)造的這類命題，使得人們無論定義多少個概念、補(bǔ)充或修補(bǔ)多少個公理，也無法消除它。

（三）哥德爾證明思路

哥德爾的證明思路和前面那些制造悖論的思路類似，都是要把命題自身引入到命題之中。區(qū)別在于哥德爾既不是利用了某種語言的不嚴(yán)謹(jǐn)，也不是簡單地把命題變量直接代入到自身，而是嚴(yán)格按照公理體系形式化的要求，一絲不茍地把命題自身引入到這個命題之中，其論證過程天衣無縫、無懈可擊！

需要說明的是，哥德爾的證明所使用的公理體系是基于《數(shù)學(xué)原理》中提出的形式化的公理體系，哥德爾在論文中把這個公理體系稱為PM（Principia Mathematica），我們在后面也會沿用這個名字。

（1）建立命題表達(dá)式與自然數(shù)的對應(yīng)（哥德爾對應(yīng)）

哥德爾做的第一件事是把PM中的表達(dá)式和自然數(shù)對應(yīng)起來。我們在講解“一致性的重要意義”的時候，專門介紹了PM中的表達(dá)式和相應(yīng)規(guī)則。PM中的表達(dá)式就類似下面的這些例子：

~ (?z≤x ? (z≠1∧z≠x∧z|x))∧(x>1)    （判斷x是否為質(zhì)數(shù)的PM公式）

?q?p?(~p?q)         （我們證明過的公式，矛盾的體系可推出任何命題）

哥德爾說，這些表達(dá)式都是由一些基本符號組成的，是一組符號序列；而“證明過程”無非就是一組表達(dá)式組成的序列，是符號組成的序列的序列。按照希爾伯特的數(shù)學(xué)形式化思路，這些符號、表達(dá)式和“證明過程”都是無意義的，如果需要，可以賦予某種含義來表達(dá)一些現(xiàn)象。哥德爾指出，顯然把這些符號賦予什么含義是與PM體系本身無關(guān)的，因此在這里哥德爾把這些符號對應(yīng)為自然數(shù)。

于是，每一個基本符號都對應(yīng)于一個自然數(shù)，每一個表達(dá)式則對應(yīng)于一個自然數(shù)序列，每一個“證明過程”都對應(yīng)于一個自然數(shù)序列的序列。反過來，每當(dāng)給出一個合規(guī)的自然數(shù)序列，就可以唯一的對應(yīng)一個PM表達(dá)式；每給出一個合規(guī)的自然數(shù)序列的序列，就可以唯一的對應(yīng)一個PM證明過程。

再深入一步，有了這種對應(yīng)后，就可以把一些對PM表達(dá)式或者證明過程的有含義性的判斷對應(yīng)成對于某一個自然數(shù)序列的判斷，而這類對自然數(shù)序列的判斷顯然又可以使用PM中的表達(dá)式來進(jìn)行。換句話說，通過哥德爾建立的對應(yīng)，我們終于可以使用PM表達(dá)式來表達(dá)有含義的判斷了。比如，根據(jù)事先對應(yīng)關(guān)系的定義，一個合法的表達(dá)式對應(yīng)的自然數(shù)序列一定滿足某種規(guī)則，這種規(guī)則顯然可以在PM中表達(dá)，于是我們就可以在PM中給出一個表達(dá)式，用來表達(dá)“某個表達(dá)式是否合規(guī)”這個含義。

由于這種對應(yīng)（也被稱為哥德爾對應(yīng)）對于“哥德爾不完備定理”的證明非常關(guān)鍵，我們寧可不厭其煩地再舉個很簡單例子來使讀者能夠準(zhǔn)確理解它。我們建立一種類似哥德爾說的對應(yīng)關(guān)系，事先聲明，我們建立的這個對應(yīng)關(guān)系僅僅是為了容易理解下面的例子，實(shí)際上這個對應(yīng)關(guān)系并不利于證明“哥德爾不完備定理”。我們建立的對應(yīng)關(guān)系為，把PM體系中的全部合規(guī)表達(dá)式以及證明過程按照ASCII字符順序排列，形成一個無限長的序列；然后從第一個表達(dá)式開始，我們把它對應(yīng)到自然數(shù)1，第二個對應(yīng)3，以此類推，直至無窮；然后再把全部不合規(guī)的表達(dá)式排列好順序，從第一個開始，分別對應(yīng)到自然數(shù)2、4、6、……。這樣，PM中的任意表達(dá)式及證明過程都對應(yīng)著唯一的自然數(shù)。我們再定義一個PM表達(dá)式，這個表達(dá)式用來判斷某個表達(dá)式是否合規(guī)，設(shè)這個表達(dá)式為isFm(x)。顯然，這種對應(yīng)關(guān)系下的isFm(x)在PM中應(yīng)為“~(?z ? x=2z)”（注意PM中的任意數(shù)字變量都是0或自然數(shù)），這個表達(dá)式實(shí)際是判斷x是否為奇數(shù)，如果是，則對應(yīng)x的表達(dá)式合規(guī)，否則不合規(guī)。于是，一個“表達(dá)式是否合規(guī)的有含義的判斷”被表示為PM中的一個表達(dá)式了。

當(dāng)然，除了表示“表達(dá)式是否合規(guī)”外，也應(yīng)該還可以表示“某個表達(dá)式是否在PM體系內(nèi)可以證明”，哥德爾把這種表達(dá)式設(shè)為provable(x)，他表示自然數(shù)（或自然數(shù)序列，或自然數(shù)序列的序列，修煉第四重時會看到，哥德爾采用一種巧妙的方法把這些序列們都對應(yīng)為唯一的自然數(shù)了）x對應(yīng)的表達(dá)式是否可在PM體系內(nèi)證明。

最后，再強(qiáng)調(diào)一點(diǎn)，哥德爾把PM中的表達(dá)式對應(yīng)為自然數(shù)，并不是哥德爾為了研究自然數(shù)或者數(shù)論而做的什么工作，而是哥德爾為了構(gòu)造某種特殊的PM表達(dá)式而提出的方法。通過把PM表達(dá)式映射為自然數(shù)，再利用PM體系自身本來具備的表達(dá)自然數(shù)間關(guān)系的能力，來實(shí)現(xiàn)把PM中的命題引入自身的目標(biāo)。

（2）構(gòu)造一個特殊的命題表達(dá)式

哥德爾定義，“在PM命題表達(dá)式中，只有一個自然數(shù)類型的自由變量的那種表達(dá)式稱為class-sign（考慮到這只是哥德爾起的一個名字，就不翻譯了）”，比如“x>10”、“?z?z<x”、“?y<x,z<x? ~(x=y?z)”等等，這些都是class-signs，都只有一個自由變量x且x是一個自然數(shù)。

下面，我們給每個class-sign分配一個序號，并設(shè)第n個class-sign為R_n。當(dāng)我們把某個自然數(shù)k代入到某個class-sign的變量時，得到的表達(dá)式記為R_n(k)。例如，若R₉是“?z?z<x”，那么R₉(8)就是“?z?z<8”，R₉(9)就是“?z?z<9”。

再設(shè)provable(R)表示R這個命題表達(dá)式可以在PM中被證明（前面已經(jīng)提到了）。大家知道，有些表達(dá)式是可以在PM體系中證明的，比如“3<9”、“~(x>10∧x<8)”，有些表達(dá)式是不可證明的，比如“3>9”、“(x>10∧x<8)”。因此，provable(3<9)為真，provable(x>10∧x<8)為假。

然后，我們定義一個集合K，K={n|～provable(R_n(n))}。也就是說，K是這樣一組自然數(shù)的集合，集合中的元素n使得R_n(n)不可證（注意這里面的R_n(n)是把命題表達(dá)式R的序號帶入到它的自由變量中得到的表達(dá)式）。

基于上述定義，必然存在一個命題表達(dá)式S(n)，它表示n∈K，而且顯然這個表達(dá)式是一個class-sign。既然S也是一個class-sign，那么S也必然有一個對應(yīng)的序號，設(shè)這個序號為q，則S就是R_q。如果我們把R_q的序號q帶入到R_q中，就得到了表達(dá)式R_q(q)，這應(yīng)該是一個可以在PM中表達(dá)的表達(dá)式。

最后，我們來考察表達(dá)式R_q(q)和~R_q(q)是否可以證明。根據(jù)上面的定義，我們可以得到下面的結(jié)論：

R_q(q) ? S(q) ? q∈K ? ~provable(R_q(q))  …………………  （式1）

如果R_q(q)可以證明，意味著provable(R_q(q))為真，顯然意味著R_q(q)也為真，根據(jù)（式1）可得到~provable(R_q(q))也為真，發(fā)生了“~provable(R_q(q))”和“provable(R_q(q))”同時為真的情況，也就是PM不一致了。換句話說，如果PM是一個一致的體系，那么只有R_q(q)不可證。

如果~R_q(q)可以證明，意味著~R_q(q)為真，根據(jù)（式1）得到~(~provable(R_q(q)))為真，也就是provable(R_q(q))為真，即R_q(q)可以證明，也即R_q(q)為真。這次又發(fā)生了R_q(q)與~R_q(q)同時為真的情況。于是，如果PM一致，那么~R_q(q)也不可證。

綜上，對于R_q(q)這個命題，只要PM是一個一致的公理體系，那么在PM中既不能證明它，也不能否證它。換句話說，在PM體系之內(nèi)，可表達(dá)的命題R_q(q)說不清楚對錯。

（3）進(jìn)一步的分析

哥德爾在論文中明確提到，這種構(gòu)造思路是來源于兩個有名的悖論——理查德悖論（Richard-antinomy）和說謊者悖論（liar-antinomy），后者就是我們最前面說到的“這句話是謊話”的悖論，而前者則與哥德爾的構(gòu)造有類似之處，感興趣的讀者可以自行了解。

哥德爾證明的一個關(guān)鍵點(diǎn)，就是把“真”、“假”與“可證明”及“不可證明”區(qū)分開來了。這里談到的可證明與否都是指在PM體系之內(nèi)。我們?nèi)粘Ｉ钆c工作中，經(jīng)常把“真假”與“是否可證明”等同起來，認(rèn)為“真?可證明”，“假?不可證明”。其實(shí)，“真假”與“是否可證明”的嚴(yán)格關(guān)系應(yīng)該是“可證明?真”、“假?不可證明”，但是它們的逆命題卻不成立，也就是說“真命題未必可證明”，同時“不可證明的也未必就是假命題”。

前面我們給出了~R_q(q)和R_q(q)都是不可證明的論斷，但這并不意味著R_q(q)的真假不確定。其實(shí)我們看一下（式1），就可以得到，R_q(q) ? ~provable(R_q(q))，也就是說，命題R_q(q)說的其實(shí)是“R_q(q)不可證”，或者說，R_q(q)說的是“自己不可證”。那么根據(jù)我們前面的論斷，R_q(q)確實(shí)是不可證的，也就是說R_q(q)這個命題為真。大家沒有必要為此而感到驚訝，前面我們說了，哥德爾清晰的區(qū)分了“可證與否”與“真假”的關(guān)系，真命題不一定可證。

（4）再進(jìn)一步分析——哥德爾第二不完備定理

哥德爾在論文的Introduction部分中介紹了自己的證明思路之后，特別指出，在詳細(xì)的對R_q(q)為真這個結(jié)論進(jìn)行分析時，會得出一個奇怪的結(jié)論——關(guān)于公理體系一致性證明的奇怪結(jié)論，哥德爾說將在論文的定理XI中進(jìn)行討論。

哥德爾論文中的定理XI就是我們今天常說的“哥德爾第二不完備定理”。

由前面的論證過程可知，當(dāng)PM體系一致的時候，可以得到結(jié)論“R_q(q)不可證”，也就是“R_q(q)為真”。這里面并沒有附加任何別的條件。因此，根據(jù)前面的論證，我們得到，

“PM體系一致”?R_q(q)

可我們知道，R_q(q)是不可證的。也就是說，“PM體系一致”也應(yīng)該是不可證的，否則如果“PM體系一致”可證，那么就可以推出R_q(q)，這與R_q(q)不可證矛盾。（嚴(yán)格的講，這樣的說法是不準(zhǔn)確的，他沒有證明“PM體系一致”?R_q(q)是可在PM體系中推導(dǎo)出來的。修煉第四重時會給出哥德爾更嚴(yán)格的證明過程。）

通過上面的簡單分析，我們得到了“哥德爾第二不完備定理”，簡單表述為“一個蘊(yùn)含了皮亞諾公理的公理體系，其一致性是不能在這個公理體系內(nèi)得到證明的”。

以上就是哥德爾不完備定理的證明思路，對于絕大部分?jǐn)?shù)學(xué)愛好者，修煉到這里應(yīng)該滿意了。因為修煉到第三重之后，已經(jīng)比較深入的理解了“哥德爾不完備定理”的證明思路，足夠準(zhǔn)確、全面的理解了“哥德爾不完備定理”的意義。

對于愿意學(xué)習(xí)的讀者，可能仍然會有各種疑問？有人會問，哥德爾把PM表達(dá)式對應(yīng)到自然數(shù)，到底有什么用，是怎么通過這種方式表達(dá)出provable(x)之類的有含義的命題的？也有人會問，修煉第一重的時候說到的“ω一致”和“原始遞歸”到底是什么意思？可能還有讀者會問，第三重介紹的證明思路難道不是一個嚴(yán)格的證明過程么，為什么還要修煉第四重？對于需要解開這些疑問的讀者，請你們和我一起，開始修煉第四重神功吧。

（四）

https://blog.sciencenet.cn/blog-409681-1067025.html

（五）

第五重：“洞見古今”——拓展了解“哥德爾不完備定理”的相關(guān)知識

正像金庸小說《倚天屠龍記》中的乾坤大挪移神功一樣，連創(chuàng)作者都沒有修煉到最高層。本人也一樣，完全不敢說自己修煉成了第五重神功。因此，這部分內(nèi)容略簡單，只談兩個方面。

（一）“哥德爾不完備定理”的實(shí)例

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

那么有沒有直接符合哥德爾論文條件下的實(shí)例呢？也就是在皮亞諾公理體系中不可確定的命題？1982年，人們發(fā)現(xiàn)了第一個不屬于哥德爾構(gòu)造的、在皮亞諾公理體系內(nèi)無法證明也無法證偽的算術(shù)命題實(shí)例——Goodstein定理。

Goodstein定理說的是，Goodstein數(shù)列一定會在有限步收斂到0。

Goodstein數(shù)列是這樣的：首先選取一個正整數(shù)g₁，比如設(shè)g₁=18，然后把它寫成2的次冪之和的形式（18 = 2⁴+ 2¹），再把大于2的指數(shù)也寫成2的次冪的形式，如果改寫后得到的表達(dá)式中還有大于2的指數(shù)，則再繼續(xù)把這樣的數(shù)字寫成2的次冪的形式，直到所有出現(xiàn)的數(shù)字都小于等于2，最后得到，

g₁=2^{2^2}+2¹

這種寫法叫Hereditary Base 2 Notation。g₂是把g₁的這種寫法中所有的2都換成3，得到的新數(shù)字再減1，也就是，

g₂=3^{3^3}+3¹-1

注意到這是個非常大的數(shù)，約等于7.6×10¹²。再繼續(xù)下去，把g₂寫成3的次冪的形式，一直到不出現(xiàn)大于3的數(shù)字，然后把3換成4，得到的數(shù)再減1，就得到了g₃。以此類推，不斷計算下去，就得到了一個數(shù)列，這個數(shù)列就是Goodstein數(shù)列。

下面我們以g₁=18為例，看看數(shù)列的前幾項：

g₁=2^{2^2}+2¹=18

g₂=3^{3^3}+3¹-1=3^{3^3}+2×3⁰=7.6×10¹²

g₃=4^{4^4}+2×4⁰-1=4^{4^4}+4⁰=1.3×10¹⁵⁴

g₄=5^{5^5}+5⁰-1=5^{5^5}=1.9×10²¹⁸⁴

只看這幾項，我們一定會認(rèn)為這個數(shù)列以極快的速度發(fā)散到無窮。事實(shí)上，這個數(shù)列會在有限步驟收斂到0。

Goodstein定理是一個容易看懂的算術(shù)命題，其證明可以通過集合論、良序定理以及超限序數(shù)等理論和知識來完成。大概思路就是使用超限序數(shù)ω構(gòu)造一個與Goodstein數(shù)列平行的數(shù)列，這個新數(shù)列的每一項都不小于Goodstein數(shù)列的對應(yīng)項，且這個新數(shù)列是遞減的，必然在有限步后會收斂到0。

Goodstein定理在集合論中的證明過程不長，簡單易懂。但是當(dāng)我們在皮亞諾公理體系內(nèi)研究這個命題的時候，神奇的事情發(fā)生了。1982年，Laurie Kirby和Jeff Paris發(fā)現(xiàn)，這個定理在皮亞諾公理體系下是不可證的。這個定理正好是哥德爾不完備定理的一個典型例證。

我們前面說過，哥德爾不完備定理是通過構(gòu)造出一個不可證的算術(shù)命題來證明的。可是，作為已經(jīng)修煉到第五重神功的我們，清楚的知道，哥德爾構(gòu)造的這個算術(shù)命題我們幾乎不可能直接的表達(dá)出來，因為太復(fù)雜、做不到。所以，哥德爾只是通過構(gòu)造方法證明了不可證命題的存在性。直到Goodstein定理的發(fā)現(xiàn)，我們終于可以見到一個皮亞諾公理體系內(nèi)不確定的算術(shù)命題的樣子了。Goodstein定理簡明易懂，計算過程明確，但是在皮亞諾公理體系居然無法證明，想想都覺得神奇。由此，我們應(yīng)該更加欽佩哥德爾的偉大貢獻(xiàn)了吧！

（二）是存在既一致且完備的公理體系的

我們討論了這么多關(guān)于哥德爾不完備定理的內(nèi)容了，估計大家已經(jīng)毫無疑問地堅信這個定理了。在此，還是要再一次提醒大家，哥德爾不完備定理是有前提條件的，那就是“蘊(yùn)含皮亞諾公理體系”。也就是說，并不是任何一致的公理體系都不完備。那么，真的存在既一致又完備的公理體系么？答案是肯定的。

我在這里可以給大家即興構(gòu)建一個公理體系：

這個公理體系只有兩個數(shù)字0和1，只有一種二元運(yùn)算“+”，其三條公理如下，

（1）0+0=0

（2）0+1=1+0=1

（3）1+1=0

公理體系構(gòu)建完畢。

這個公理體系極為簡單，在這個體系內(nèi)可表達(dá)的全部命題都可以證明（比如1+1+1+0=1），而且這個公理體系肯定是一致的，也是“ω一致”的。

其實(shí)，一個公理體系如果比較簡單，不能承載哥德爾對應(yīng)中起碼的編碼要求，那么這個公理體系的一致性與完備性是否存在矛盾就不屬于哥德爾定理覆蓋的范疇了。對于一些簡單的公理體系，是可以證明其既一致又完備的。當(dāng)然，我構(gòu)造的公理體系太簡單了，以至于一點(diǎn)用處也沒有。在實(shí)際的數(shù)學(xué)中，有一種叫做Presburger arithmetic（Presburger算術(shù)）的體系，因不包括乘法，所以其實(shí)是既一致又完備的，感興趣的話可以Google之以詳細(xì)了解。

另外，對于一些也很復(fù)雜的公理體系，如果其不足以定義自然數(shù)，哪怕這樣的公理體系包含了自然數(shù)，也可能不受“哥德爾不完備定理”的約束。比如，塔斯基（Tarski）證明了實(shí)數(shù)和復(fù)數(shù)理論都是一致且完備的一階公理體系，雖然它們都包括了自然數(shù)；再比如，著名的歐幾里德幾何在補(bǔ)充了平行公理和實(shí)數(shù)理論之后，也是一個一致且完備的一階公理化系統(tǒng)。

“哥德爾不完備定理”確實(shí)偉大，但是也用不著神化，它有它的前提條件，有它的適用范圍，當(dāng)然，也同樣有著劃時代的偉大貢獻(xiàn)！

結(jié)語

到此，五重神功全部修煉完畢。“哥德爾不完備定理”是一個劃時代的偉大成就，也是哥德爾一生唯一的一個重大研究成果。作為一個數(shù)學(xué)家、邏輯學(xué)家的哥德爾，一生能做出這樣一個偉大的成就，值了。作為讀者，如果通過這個修煉過程，能夠真正深入了解并理解了“哥德爾不完備定理”，我想，也值回大家花費(fèi)在閱讀和思考上的時間了吧。

[1] 網(wǎng)上能查到的哥德爾論文的英譯版，網(wǎng)址：https://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf

[2] 本人實(shí)在不忍心這樣描述羅素和懷特海，“才智枯竭”這個說法參見維基百科https://zh.m.wikipedia.org/zh-hans/數(shù)學(xué)原理

[3] 參見張寅生先生在科學(xué)網(wǎng)的博客，https://blog.sciencenet.cn/blog-320682-969874.html

本文來自趙昊彤科學(xué)網(wǎng)博客：
鏈接地址：https://blog.sciencenet.cn/blog-409681-1067019.html