（一）

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

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

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

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

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

賞玩一塊美玉的時(shí)候，首先不應(yīng)該是聽各類專家講這塊玉多么晶瑩剔透、多么價(jià)值連城，而應(yīng)該是首先把玉拿出來(lái)讓大家看看，有個(gè)感性認(rèn)識(shí)。在哥德爾的論文中，我們一般所說(shuō)的“哥德爾不完備定理”（有時(shí)候也被叫做“哥德爾第一不完備定理”）是指論文中的定理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：對(duì)于任意一個(gè)ω一致_{（第四重）}的原始遞歸公理集合κ，一定存在一個(gè)原始遞歸_{（第三重、第四重）}的表達(dá)式r，使得無(wú)論是“r總成立”這個(gè)命題，還是“r不總成立”這個(gè)命題，都不屬于通過(guò)κ可推導(dǎo)出來(lái)的定理的集合（原文中的Conseq(κ)）。

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

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

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

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

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

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

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

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

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

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

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

（二）

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

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

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

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

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

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

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

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

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

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

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

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

• 確定性：可以通過(guò)一個(gè)算法來(lái)確定每一個(gè)形式化的命題是真還是假。

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

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

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

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

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

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

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

～        邏輯“非”；

∨        邏輯“或”；

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

∧        邏輯“與”；

?x?p   對(duì)于任意x，p都成立；

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

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

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

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

(p∨p)?p

p?(p∨q)

(p∨q)?(q∨p)

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

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

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

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

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

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

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

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

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

最后讓我們?cè)倩氐健案绲聽柌煌陚涠ɡ怼?，看看哥德爾是如何在?shù)學(xué)公理化（以及公理體系形式化）的大背景下“釜底抽薪”的。我們先來(lái)看“希爾伯特計(jì)劃”的幾個(gè)要素：

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

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

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

四是確定性。顯然確定性也不成立，因?yàn)楦绲聽栕C明了存在某些命題無(wú)法證明其真假。而且就算在確定性判斷的“真”和“假”以外加入“不可證明”這一類，也是不成立的。我們前面提到過(guò)，沒(méi)有一個(gè)通用的算法能夠判定任意命題是否不可證。

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

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

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

（三） 

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

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

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

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

（一）悖論式語(yǔ)言

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

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

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

（二）羅素悖論

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

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

之所以在這里談到了羅素悖論，是因?yàn)橄Ｍx者知道，當(dāng)公理體系引發(fā)了悖論之后，人們馬上就會(huì)通過(guò)定義新的概念、提出或者修改公理來(lái)完善它?？墒?，當(dāng)哥德爾的證明也構(gòu)造出了類似悖論的命題之后，人們寧可接受這個(gè)命題是不可證明的，也沒(méi)有試圖通過(guò)修補(bǔ)公理體系來(lái)解決這個(gè)問(wèn)題。因?yàn)橥ㄟ^(guò)哥德爾的方法構(gòu)造的這類命題，使得人們無(wú)論定義多少個(gè)概念、補(bǔ)充或修補(bǔ)多少個(gè)公理，也無(wú)法消除它。

（三）哥德爾證明思路

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

需要說(shuō)明的是，哥德爾的證明所使用的公理體系是基于《數(shù)學(xué)原理》中提出的形式化的公理體系，哥德爾在論文中把這個(gè)公理體系稱為PM（Principia Mathematica），我們?cè)诤竺嬉矔?huì)沿用這個(gè)名字。

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

哥德爾做的第一件事是把PM中的表達(dá)式和自然數(shù)對(duì)應(yīng)起來(lái)。我們?cè)谥v解“一致性的重要意義”的時(shí)候，專門介紹了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)         （我們證明過(guò)的公式，矛盾的體系可推出任何命題）

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

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

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

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

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

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

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

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

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

再設(shè)provable(R)表示R這個(gè)命題表達(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)為假。

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

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

最后，我們來(lái)考察表達(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))”同時(shí)為真的情況，也就是PM不一致了。換句話說(shuō)，如果PM是一個(gè)一致的體系，那么只有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)同時(shí)為真的情況。于是，如果PM一致，那么~R_q(q)也不可證。

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

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

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

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

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

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

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

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

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

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

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

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

以上就是哥德爾不完備定理的證明思路，對(duì)于絕大部分?jǐn)?shù)學(xué)愛好者，修煉到這里應(yīng)該滿意了。因?yàn)樾逕挼降谌刂螅呀?jīng)比較深入的理解了“哥德爾不完備定理”的證明思路，足夠準(zhǔn)確、全面的理解了“哥德爾不完備定理”的意義。

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

（四）

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

（五）

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

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

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

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

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

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

Goodstein數(shù)列是這樣的：首先選取一個(gè)正整數(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

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

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

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²¹⁸⁴

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

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

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

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

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

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

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

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

（1）0+0=0

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

（3）1+1=0

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

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

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

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

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

結(jié)語(yǔ)

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

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

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

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

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