哥德爾的兩個(gè)不完備定理是上世紀(jì)邏輯學(xué)中最重要的定理，拜科普讀物所賜，同時(shí)也是受誤解最多的定理。本文試圖講清哥德爾不完備定理到底在說什么并澄清一些誤解。為了不把本文寫成數(shù)理邏輯教材，我會(huì)盡量使用自然語言敘述[0]。

本文第一部分簡單介紹不完備定理的歷史和內(nèi)容。第二部分采用問答體，力求解釋一些常見的問題。其實(shí)第二部分才是本文重點(diǎn)，如果覺得第一部分太枯燥可以直接跳過。

I. 簡介

1. 形式系統(tǒng)

最早的數(shù)學(xué)定理都是用自然語言寫的，但隨著數(shù)學(xué)的內(nèi)涵越來越豐富，自然語言在表達(dá)數(shù)學(xué)概念時(shí)顯得越來越啰嗦（比如本文= =）。為了簡化表達(dá)，數(shù)學(xué)家們開始越來越多地用符號來表達(dá)數(shù)學(xué)概念，這種情況發(fā)展到極端后自然語言被徹底地拋棄，數(shù)學(xué)完全的符號化，這種語言就被稱為形式語言。比如『對任意自然數(shù)n，n都大于等于0』，用一階語言形式化之后變成 ?n∈N.n>=0 。

數(shù)學(xué)家又發(fā)現(xiàn)人的推理過程是可以看做符號變換的。比如『已知命題A，又已知命題A能推出B，那么B成立』這條規(guī)則可以抽象為 A, A→B |- B [1]。這樣一來數(shù)學(xué)證明可以完全變成機(jī)械的符號變換游戲，哪怕你不懂這些符號什么意思，只要你記住規(guī)則，就能證明出一個(gè)個(gè)數(shù)學(xué)定理。這聽起來非常誘人，于是數(shù)學(xué)家制定了形式語言的語法，把符合語法的句子稱為命題，又選出一組命題稱為公理，最后制定了一組推理規(guī)則，這樣給你公理，根據(jù)推理規(guī)則，你就可以推出許多被稱為定理的命題。這套系統(tǒng)就被稱為形式系統(tǒng)。從公理推出定理的過程就被稱為證明，推出命題否定形式的過程自然就被稱為證偽。

仔細(xì)想想，這里面其實(shí)有個(gè)問題：我們怎么確定這套推理系統(tǒng)是對的呢？換句話說，我們怎么知道推出的命題是真命題呢？理論上說，數(shù)學(xué)可以完全無視現(xiàn)實(shí)世界，從任意的公理出發(fā)推出任何命題，但我們還是希望我們研究的數(shù)學(xué)能解決現(xiàn)實(shí)問題，所以我們要確保我們的形式系統(tǒng)確實(shí)是在描述我們想要的數(shù)學(xué)理論。為了解決這個(gè)問題，數(shù)學(xué)家為形式語言建立了語義，換句話說，就是把形式語言的符號翻譯成我們已知的東西[2]，這樣如果推出的命題翻譯過來是錯(cuò)的，那么我們就需要修改推理規(guī)則，直到其語義符合預(yù)期。而符合語義的命題我們就稱為真命題。后來邏輯學(xué)家發(fā)現(xiàn)，一種叫一階語言的形式語言有非常好的性質(zhì)，用一階邏輯表達(dá)的形式系統(tǒng)，不管你給公理什么語義，只要公理都為真，那么所有能推出的命題都是符合這個(gè)語義的真命題[3]，所以現(xiàn)在大部分形式化的數(shù)學(xué)理論都用一階語言表達(dá)，包括目前數(shù)學(xué)的基礎(chǔ)：ZFC公理集合論[4]。

2. 希爾伯特計(jì)劃

既然形式系統(tǒng)這么好，那么能不能把所有數(shù)學(xué)都形式化呢？以后也不用費(fèi)腦子證明了，直接扔給機(jī)器窮舉，一噸噸的數(shù)學(xué)定理就造出來了。

希爾伯特覺得：能！

他暢想了一個(gè)美好的未來，所有的數(shù)學(xué)理論全都用一種形式語言來描述，并且這套系統(tǒng)滿足如下四個(gè)性質(zhì)——

完備性：任意一個(gè)符合這個(gè)形式系統(tǒng)語法的句子，也就是一個(gè)命題，都能證明或證偽。

一致性：這個(gè)系統(tǒng)不會(huì)同時(shí)推出一個(gè)命題和它的否定。

可判定性：如果給定任意定理，可以用算法在有限步內(nèi)判定真?zhèn)巍?/p>

保守性：證明可以不依賴『理想對象』（比如不可數(shù)集合）。

而且更重要的是，這四個(gè)性質(zhì)還要在這個(gè)系統(tǒng)內(nèi)被證明。

這個(gè)想法倒是非常美好，但就在希爾伯特退休后一年，即1931年，哥德爾的兩條不完備定理直接宣判了希爾伯特計(jì)劃的死刑。

3. 哥德爾不完備定理

我們先來看不完備定理說了什么——

第一不完備定理

一個(gè)包含皮亞諾算術(shù)的形式系統(tǒng)如果是一致的那么是不完備的。

第二不完備定理

對于一個(gè)包含皮亞諾算術(shù)的形式系統(tǒng)，該系統(tǒng)的一致性不能在系統(tǒng)內(nèi)部證明。

我先來解釋一下皮亞諾算術(shù)是什么。皮亞諾算術(shù)是一套用一階語言描述的形式系統(tǒng)，它被用來刻畫自然數(shù)以及基本的自然數(shù)算術(shù)，比如加法、乘法和乘方。那『包含皮亞諾算術(shù)的形式系統(tǒng)』是什么意思呢？直觀上理解，就是說從這個(gè)形式系統(tǒng)中，可以推出一組命題，這些命題可以描述自然數(shù)以及算術(shù)。比如ZFC集合論就是包含皮亞諾算術(shù)的系統(tǒng)，你可以用 Φ、{Φ}、{Φ,{Φ}}...來表示1、2、3……，用集合操作來模擬自然數(shù)上的運(yùn)算，所以有些命題是不能在ZFC中證明或證偽的，ZFC也不能證明自己是一致的；再比如圖靈機(jī)也是一個(gè)包含自然數(shù)的形式系統(tǒng)，而停機(jī)問題可以理解為這個(gè)系統(tǒng)里無法被證明和證偽的命題。

哥德爾的兩個(gè)不完備定理直接戳破了希爾伯特的夢想：包含算術(shù)的形式系統(tǒng)不可能完備，而且這個(gè)系統(tǒng)本身的一致性不能在系統(tǒng)內(nèi)被證明。后來圖靈的停機(jī)問題又摧毀了希爾伯特對可判定性的期待。

II. 一些澄清

1. 所有的理論都是不完備的嗎？

顯然不是的。比如平面幾何，你不能從平面幾何推出皮亞諾算術(shù)，因?yàn)槠矫鎺缀问莻€(gè)完備的理論。而且哥德爾給出的『包含皮亞諾算術(shù)』的限制其實(shí)都很強(qiáng)了，給一個(gè)弱得多的限制，理論依然是不完備的。哥德爾提出第一不完備定理后不久，Rosser就給出了一個(gè)更強(qiáng)的（更強(qiáng)的意味著限制更弱）不完備定理：一個(gè)系統(tǒng)只要包含羅賓遜算術(shù)就足以產(chǎn)生不完備性了（羅賓遜算術(shù)只有加法和乘法）。哥德爾當(dāng)時(shí)強(qiáng)調(diào)皮亞諾算術(shù)（原文其實(shí)更模糊，是『基本算術(shù)』），主要是針對希爾伯特計(jì)劃。希爾伯特想把所有數(shù)學(xué)都形式化成一套系統(tǒng)，然后把證明歸結(jié)成基本的自然數(shù)算術(shù)，再在這個(gè)系統(tǒng)內(nèi)證明自然數(shù)算術(shù)是一致的，這樣就完成整個(gè)數(shù)學(xué)的形式化，結(jié)果被哥德爾無情打臉。

另外，哥德爾不完備定理其實(shí)還有個(gè)隱藏限制，那就是形式語言的公式集必須是遞歸集合，換言之，你的公式必須可以從有限個(gè)符號經(jīng)過有限步構(gòu)造出來[5]。如果你用像實(shí)數(shù)那么多的符號來表示，哥德爾不完備定理就失效了，但這毫無意義，因?yàn)槿祟悰]辦法寫出這種語言。同樣的，如果你能造出『實(shí)數(shù)計(jì)算機(jī)』，那停機(jī)問題也可以解決了。

2. 那我不用形式語言描述理論，是不是可以避免不完備性？

這么說倒也沒錯(cuò)。哥德爾的證明是先把形式語言編碼成自然數(shù)，然后證明『所有自然數(shù)代表的公式集合』是比『能推出的所有公式的編碼集合』更大的集合[6]，所以總有公式是證明不出來的。如果理論用自然語言描述，自然語言沒有確定的語法，也就無法編碼了。但是如果你不能精確定義語言，你也無法精確定義『證明』、『真』這樣的概念，又怎么保證你證明得對呢？而且用形式語言和用自然語言描述的理論本質(zhì)是一個(gè)東西[7]，這就好比一個(gè)命題不管你用漢語說還是英語說，真假都一樣。所以形式系統(tǒng)的不完備性也可以當(dāng)做直覺上數(shù)學(xué)理論的不完備性。

另外用形式語言可以起到區(qū)分元理論和對象理論的作用。元理論是指描述這個(gè)形式語言的理論，而對象理論是用這個(gè)形式語言來描述的理論。其實(shí)我剛才說『一個(gè)命題不管你用漢語說還是英語說，真假是一樣』是不準(zhǔn)確的，比如『這句話是漢語』這句話，翻譯到英語就是假的，但是這句話其實(shí)是一個(gè)元理論的命題，它描述了寫『這句話是漢語』的語言本身，所以它不是漢語這個(gè)系統(tǒng)內(nèi)的命題。再比如上一段中『哥德爾的證明是先把形式語言編碼成自然數(shù)，然后證明「所有自然數(shù)代表的公式集合」是比「能推出的所有公式的編碼集合」更大的集合』這句話，句中的『證明』和形式系統(tǒng)里的『證明』就不是一個(gè)層面的詞。如果數(shù)學(xué)命題都用自然語言描述，就會(huì)出現(xiàn)很多元理論和對象理論混淆的情況。

3. 哥德爾不完備定理用了哪些公理呢？

根據(jù)哥德爾在他自己的論文On Formally Undecidable Propositions of Principia Mathematica and Related System中所說，他是在羅素和懷特海一起創(chuàng)立的PM形式系統(tǒng)里進(jìn)行證明的[8]，用到的元數(shù)學(xué)概念是自然數(shù)算術(shù)。

4. 不完備定理依賴算術(shù)又說算術(shù)是不完備的，這不是循環(huán)論證嗎？

這得從哥德爾本人的哲學(xué)立場說起。哥德爾是個(gè)柏拉圖主義者，在柏拉圖主義者眼里，數(shù)學(xué)對象都是永恒存在于獨(dú)立于現(xiàn)實(shí)世界的理念世界里的。既然數(shù)學(xué)天然存在，那推理就不是數(shù)學(xué)定理存在的前提，而是發(fā)現(xiàn)數(shù)學(xué)的工具。這就好比人們根據(jù)天王星的軌道偏差推理出海王星的存在，不能說海王星因?yàn)槿说耐评矶嬖?。所以，雖然哥德爾用了算術(shù)知識(shí)來證明不完備定理，但不能說不完備定理依賴算術(shù)而存在。這只表示哥德爾相信他用的知識(shí)是必然正確的，他用這些知識(shí)推理出一個(gè)對數(shù)學(xué)世界普遍成立的規(guī)律。

但很多數(shù)學(xué)家認(rèn)為數(shù)學(xué)就是從公理中推出來的，是人類思維的創(chuàng)造。如果站在這個(gè)立場，那哥德爾確實(shí)有循環(huán)論證之嫌：他在算術(shù)里討論了一個(gè)元算術(shù)的性質(zhì)。所以這個(gè)定理更多地被視為哲學(xué)或邏輯學(xué)定理而不是數(shù)學(xué)定理[9]。注意這不是說哥德爾證錯(cuò)了，只是說哥德爾已經(jīng)到數(shù)學(xué)和哲學(xué)之間模糊的邊界了，甚至可以說他是在數(shù)學(xué)外觀察數(shù)學(xué)。至于到底什么是數(shù)學(xué)，現(xiàn)在沒人能回答得了，大部分?jǐn)?shù)學(xué)家也不在乎這個(gè)問題，ZFC作為數(shù)學(xué)基礎(chǔ)已經(jīng)足夠好了，空談主義并不能幫助數(shù)學(xué)家解決實(shí)際問題。順便一提，現(xiàn)在倒是有不少計(jì)算機(jī)科學(xué)家在做數(shù)學(xué)基礎(chǔ)的研究……

一般來說，不管什么哲學(xué)立場，不管討論多么基礎(chǔ)的對象理論，元理論都會(huì)包含一點(diǎn)基本的算術(shù)，否則我們連定義符號、語法都不行，形式化更無從談起。

5. 計(jì)算機(jī)是個(gè)不完備的形式系統(tǒng)，但是人能證出哥德爾不完備定理，是不是說明人腦比計(jì)算機(jī)強(qiáng)？

這是個(gè)廣為流傳的誤解。計(jì)算機(jī)是可以證明哥德爾不完備定理的，Lawrence C. Paulson就用Isabelle這個(gè)軟件證明了哥德爾不完備定理[10]。雖然目前計(jì)算機(jī)只能處理形式化的數(shù)學(xué)，但是你可以先形式化一些基礎(chǔ)的結(jié)論，然后把其他數(shù)學(xué)理論在這個(gè)形式系統(tǒng)里再形式化一遍，最后證明這些形式系統(tǒng)內(nèi)的形式系統(tǒng)有不完備性。順便夾個(gè)私貨，作為物理主義者，我相信人腦理論上是能用圖靈機(jī)模擬的，但是能不能造出來、或者造出來能不能被人理解就不好說了。

6. 物理學(xué)需要數(shù)學(xué)，哥德爾不完備定理是不是意味著我們永遠(yuǎn)無法理解宇宙？

這個(gè)問題不好說。我傾向于認(rèn)為哥德爾不完備定理和物理沒多大關(guān)系。首先，物理定律只是在用數(shù)學(xué)，而不是創(chuàng)造數(shù)學(xué)。假設(shè)你發(fā)現(xiàn)了宇宙最基本的定律，幾個(gè)方程組可以求出一切物理量，那你也不需要用這個(gè)方程組推出自然數(shù)、有理數(shù)等概念，只要它們能描述你觀察到的一切現(xiàn)象就行。再者，宇宙里所有粒子或別的什么基本單元也可能是有限的，你給它們用自然數(shù)編號，哪怕一個(gè)粒子用一個(gè)公式描述，那也是遞歸集，并不會(huì)有不完備性。

注釋

[0] 寫完本文我深刻地體會(huì)到用任何自然語言來描繪數(shù)學(xué)都是蒼白無力的，這也算是Quine的翻譯不確定性的體現(xiàn)吧。這里推薦幾本教材：郝兆寬、楊睿之、楊躍的《數(shù)理邏輯》（支持國產(chǎn)教材，而且確實(shí)寫得很棒），Ebbinghaus的Mathematical Logic, 2nd Edition（很好懂，內(nèi)容涉及很廣，適合開闊眼界），Enderton的A Mathematical Introduction to Logic, 2nd Edition。

[1] P|-p表示給定公式集P，根據(jù)推理規(guī)則一定能推理出公式p，換句話說，給定公式集P肯定能證明公式p。另一個(gè)相似的符號是“|=”，P|-p表示對所有能使P中公式都為真的語義，也都能使p為真，換句話說，不管你怎么翻譯，P和p的真假都是一致的（這個(gè)一致就是漢語里一致的意思，不是邏輯里一致性的意思）。

[2] 選取不同的數(shù)學(xué)基礎(chǔ)，可以把語言翻譯到不同的數(shù)學(xué)對象上。由于目前ZFC是大多數(shù)數(shù)學(xué)家公認(rèn)的基礎(chǔ)理論，所以標(biāo)準(zhǔn)語義都把變量翻譯到一個(gè)被稱為論域的集合上，把函數(shù)和關(guān)系符號翻譯成論域上的函數(shù)和關(guān)系，這樣的標(biāo)準(zhǔn)語義也被稱為模型。研究標(biāo)準(zhǔn)語義的理論被稱為模型論，比較經(jīng)典的教材是C.C.Chang和H.J.Keisler的Model Theory（沒看過）；以及David Marker的Model Theory: An Introduction（例子特別多，強(qiáng)推）。比較著名的非標(biāo)準(zhǔn)語義是高階邏輯的Henkin語義，是一種代數(shù)語義。

[3] 這個(gè)性質(zhì)叫soundness，用符號表示是：給定一個(gè)公式集P，如果P|-p那么P|=p。反過來的性質(zhì)叫completeness：給定一個(gè)公式集P，如果P|=p那么P|-p。注意這個(gè)completeness不是哥德爾不完備定理里的incompleteness的反義詞。一階語言，或者說一階邏輯，又有soundness又有completeness。

[4] 想學(xué)習(xí)集合論，我強(qiáng)推Kenneth Kunen的Set Theory: An Introduction to Independence Proofs，時(shí)不時(shí)地會(huì)講講哲學(xué)背景，非常有趣。Thomas Jech的Set Theory太形式化了，第一次看會(huì)非常痛苦……

[5] 遞歸集是指『某元素是否存在于該集合中』可以用算法判斷出來的集合。至于什么叫『算法』，[0]里提到的數(shù)理邏輯教材都有講。另一個(gè)相似的概念是遞歸可枚舉集，指在集合中的元素可以用算法判斷出來，但判斷元素不在集合中可能會(huì)讓算法死循環(huán)。

[6] 前者是遞歸可枚舉集，后者是遞歸集。哥德爾寫證明那年還沒有遞歸可枚舉集這樣的概念，但是意思是一樣的。后來圖靈搞出圖靈機(jī)把可計(jì)算函數(shù)直觀化，哥德爾高度贊賞了他的工作。

[7] 這么說其實(shí)不是很準(zhǔn)確，極端的形式主義者會(huì)認(rèn)為只有形式化的數(shù)學(xué)才是數(shù)學(xué)。

[8] 原文是德語，這個(gè)題目是B. Meltzer翻譯的論文的題目。根據(jù)哥德爾的敘述，當(dāng)年最火的兩個(gè)形式系統(tǒng)一個(gè)是PM，一個(gè)是ZF。

[9] 語出哲學(xué)家R. B. Braithwaite在B. Meltzer翻譯的On Formally Undecidable Propositions of Principia Mathematica And Related Systems前言。

[10] Paulson L C. A machine-assisted proof of G?del’s incompleteness theorems for the theory of hereditarily finite sets[J]. The Review of Symbolic Logic, 2014, 7(3): 484-498.