程 勇

一、導(dǎo)論

在評價(jià)同行的研究成果時(shí)，我們常使用“深刻”這個詞形容成果的“深度”。本文對“深度”的討論限定于數(shù)學(xué)定理。對于何謂“深刻的數(shù)學(xué)定理”，學(xué)界有不同的看法。即使人們對某一定理是否深刻達(dá)成共識，人們對此定理“為何深刻”的理由仍可能有不同的看法。在關(guān)于數(shù)學(xué)定理深度的哲學(xué)討論文獻(xiàn)中，人們討論得最多的四個問題是：（1）對給定的定理，對其是否深刻學(xué)界是否達(dá)成共識？（2）深刻的數(shù)學(xué)定理是否具有某些共同特征？（3）“深度”和其他一些概念間的區(qū)別——如豐富性、重要性、難度、基礎(chǔ)性、解釋力、優(yōu)美性等。（4）數(shù)學(xué)深度是數(shù)學(xué)定理內(nèi)在的客觀特征還是與我們的興趣和能力緊密相關(guān)的？對“數(shù)學(xué)深度”這一概念，我們沒有精確的定義，目前也沒有一個判斷給定數(shù)學(xué)定理是否深刻的被廣泛接受的一般標(biāo)準(zhǔn)。被認(rèn)為深刻的數(shù)學(xué)定理可能具有不同的特征，不同的定理可能有刻畫它們深度的不同標(biāo)準(zhǔn)。雖然我們很難給出一個判定任意給定的定理是否深刻的一般標(biāo)準(zhǔn)，但一個自然的問題是：對于被學(xué)界公認(rèn)為“深刻”的單個數(shù)學(xué)定理，我們能否找到刻畫此定理深度的一些標(biāo)準(zhǔn)，并基于這些標(biāo)準(zhǔn)論證此定理的深度。

哥德爾是20世紀(jì)最偉大的邏輯學(xué)家，他最重要的成果是于1931年發(fā)表的不完全性定理。不完全性定理是20世紀(jì)最重要的深刻發(fā)現(xiàn)之一，是現(xiàn)代邏輯發(fā)展史上重要的里程碑，它對邏輯學(xué)、哲學(xué)、數(shù)學(xué)、理論計(jì)算機(jī)科學(xué)等領(lǐng)域的發(fā)展產(chǎn)生了廣泛、深刻而持久的影響，極大地改變了1931年之后數(shù)學(xué)基礎(chǔ)研究的面貌。不完全性定理被廣泛認(rèn)為是邏輯領(lǐng)域“深刻”的數(shù)學(xué)定理。本文的目標(biāo)不是給出一個判斷數(shù)學(xué)定理是否深刻的一般標(biāo)準(zhǔn)。相反，本文的策略是將不完全性定理作為研究數(shù)學(xué)定理深度的一個案例，希望通過對此案例的深入分析，加深我們對“數(shù)學(xué)深度”這一概念的理解。本文集中于研究這樣兩個關(guān)于不完全性定理深度的方法論問題：刻畫不完全性定理深度的標(biāo)準(zhǔn)是什么，如何基于這些標(biāo)準(zhǔn)論證不完全性定理的深度。基于文獻(xiàn)中的最新研究成果，我們提出三個刻畫不完全性定理深度的標(biāo)準(zhǔn)：成果的影響力、結(jié)論的豐富性、理論的統(tǒng)一性；并基于這些標(biāo)準(zhǔn)論證不完全性定理的深度。在哥德爾不完全性定理發(fā)表90周年之際，我們以此文紀(jì)念，并盡量以非形式的語言向國內(nèi)同行介紹哥德爾之后國際學(xué)界關(guān)于不完全性定理研究的新進(jìn)展。

二、不完全性定理

本節(jié)我們簡要介紹不完全性定理的內(nèi)容及其證明的主要思想。①關(guān)于不完全性定理的經(jīng)典書籍，參見（1） Roman Murawski， Recursive Functions and Metamathematics： Problems of Completeness and Decidability， G?del’s Theorems， Springer Netherlands， 1999； （2） Per Lindstr?m， Aspects of Incompleteness， Lecture Notes in Logic v. 10， 1997； （3） Peter Smith， An Introduction to G?del’s Theorems， Cambridge University Press， 2007。關(guān)于不完全性定理的研究報(bào)告，參見 （1） C. Smoryński， “The Incompleteness Theorems”， in J. Barwise （ed.）， Handbook of Mathematical Logic， North-Holland， Amsterdam， 1977， pp. 821—865； （2） Lev D. Beklemishev， “G?del Incompleteness Theorems and the Limits of Their Applicability I”， Russian Math Surveys， 2010； （3） Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”， The Bulletin of Symbolic Logic， Vol. 27， Issue 2， 2021， pp. 133—167。我們先解釋若干文中用到的概念。一個形式理論包括如下基本構(gòu)件：形式語言、公理、推演規(guī)則。②若未作特殊說明，本文中的理論均指形式理論。形式理論的形式語言包括符號表和公式的形成規(guī)則。符號表包括邏輯符號與非邏輯符號。有限個符號構(gòu)成符號串。公式是一類根據(jù)形成規(guī)則遞歸定義的“有意義”的符號串。公理是一類特殊的公式（包括邏輯公理和非邏輯公理），是此理論中演繹推理的出發(fā)點(diǎn)。推演規(guī)則告訴我們?nèi)绾斡山o定的一些公式推出其他公式。給定理論T及T語言中的公式A，我們可定義何謂“A在理論T中是可證的”（記為TA）： 存在一個有限的公式序列，使得此序列的最后一個公式是A，對此序列中的任意公式B，B或者是理論T的公理，或者是由此序列中公式B前面的公式使用某種推演規(guī)則而得到的。皮亞諾算術(shù)PA，羅賓遜（Robinson）算術(shù)Q和理論R是不完全性研究中三個重要的形式理論。①PA和Q具有相同的語言，它們的非邏輯符號包含一個常元符號0，一個一元函數(shù)符號S，兩個函數(shù)符號+和×。 關(guān)于Q， PA和R的定義參見Yong Cheng， “Finding the Limit of Incompleteness I”， Bulletin of Symbolic Logic， Volume 26， Issue 3—4， December 2020， pp. 268—286。

算術(shù)化是數(shù)理邏輯中的一種重要方法。它的思想是給形式理論的符號表編碼，建立符號和自然數(shù)間的一一對應(yīng)。因有限的自然數(shù)序列可被單個自然數(shù)編碼，我們可建立符號串和自然數(shù)間的一一對應(yīng)。這樣符號串上的關(guān)系和運(yùn)算就可轉(zhuǎn)換為自然數(shù)上的關(guān)系和運(yùn)算。通過算術(shù)化，任何公式或公式序列都可被一個自然數(shù)編碼（稱為哥德爾編碼）。②關(guān)于算術(shù)化方法的技術(shù)細(xì)節(jié)，參見Roman Murawski， Recursive Functions and Metamathematics： Problems of Completeness and Decidability， G?del’s Theorems。

我們稱理論T是遞歸可公理化的，若T公理的哥德爾編碼集是遞歸集（直觀的說，存在一個能行的算法使得任給理論T語言中的公式A，此算法可判定A是否是T的公理）。我們稱理論T是一致的，若不存在公式A使得A和A都在T中可證。我們稱理論T是完全的，若對理論T語言中的任意公式A，或者A在T中可證，或者A在T中可證。我們稱A是T的不可判定命題，若A和A都是在T中不可證的。③因此，理論T是不完全的當(dāng)且僅當(dāng)存在T中的不可判定命題。下文中，若未作特殊說明，我們假設(shè)理論T是Q的遞歸可公理化的一致擴(kuò)充。我們用表示自然數(shù)n在T的語言中所對應(yīng)的項(xiàng)。④每個自然數(shù)都對應(yīng)于PA的語言中的一個項(xiàng)。例如，自然數(shù)0對應(yīng)于算術(shù)語言中的常元符號0，自然數(shù)1對應(yīng)于算術(shù)語言中的項(xiàng)S0，依次類推。給定T語言中的公式φ，我們用表示φ的哥德爾編碼在T的語言中所對應(yīng)的項(xiàng)。

哥德爾在證明不完全性定理時(shí)使用的是羅素—懷特?！稊?shù)學(xué)原理》中的形式系統(tǒng)P，它是基于戴德金—皮亞諾算術(shù)公理及自然數(shù)序列的簡單類型理論。⑤Lev D. Beklemishev， “G?del Incompleteness Theorems and the Limits of Their Applicability I”， Russian Math Surveys， 2010.哥德爾1931年發(fā)表的第一不完全性定理的原始形式是：對任何由形式系統(tǒng)P基礎(chǔ)上增加一遞歸的公理集而形成的具有與P相同語言的形式理論T，若T是ω-一致的，則T是不完全的。哥德爾沒有發(fā)表第二不完全性定理的證明細(xì)節(jié)，而只是宣告了這一結(jié)果：我們無法在系統(tǒng)P內(nèi)證明系統(tǒng)P的一致性。⑥Richard Zach， “Hilbert’s Program Then and Now”， in Philosophy of Logic， Handbook of the Philosophy of Science， 2007， pp. 411—447.不完全性定理的原始表述受囿于很復(fù)雜的系統(tǒng)P及其語言，后人的研究極大地改進(jìn)了此定理的表述形式。下面是現(xiàn)代版本的哥德爾不完全性定理：

第一不完全性定理令T為Q的遞歸可公理化的擴(kuò)充。若T是ω-一致的，則T是不完全的。①我們稱理論T是ω-一致的，若不存在理論T語言中的公式φ（x）使得（x）且對任意的自然數(shù) n，。

第二不完全性定理令T為Q的遞歸可公理化的擴(kuò)充。若T是一致的，則“T的一致性”在T中不可證。②下文中，我們將討論如何在T中表達(dá)T的一致性。

哥德爾第一不完全性定理證明的三個主要思想是：算術(shù)化、可表示性、自指構(gòu)造。假設(shè)理論T是Q的遞歸可公理化的擴(kuò)充。通過算術(shù)化，我們可以建立T的語言中的表達(dá)式和自然數(shù)間的一一對應(yīng)。在此對應(yīng)下，我們可將關(guān)于理論T的系統(tǒng)性質(zhì)的命題轉(zhuǎn)換成關(guān)于自然數(shù)的命題。哥德爾證明了：所有的遞歸關(guān)系都是在Q中可表示的。③例如，我們稱自然數(shù)集上的二元關(guān)系R是在理論T中可表示的，若存在T語言中的公式φ（x，y）使得，若R（m，n）成立，則； 若R（m，n）不成立，則。 我們稱公式φ（x，y）是關(guān)系R的表示公式。因此，關(guān)于理論T的系統(tǒng)性質(zhì)的遞歸關(guān)系是在Q中可表示的，從而在Q中有對應(yīng)的表示公式。這樣，我們可以在Q內(nèi)“談?wù)摗崩碚揟的系統(tǒng)性質(zhì)，這是算術(shù)化思想的本質(zhì)。

下面，我們給出現(xiàn)代版本哥德爾不完全性定理的證明概要。通過算術(shù)化，我們可定義表達(dá)理論T內(nèi)演繹證明的自然數(shù)集上的關(guān)系。例如，我們可定義自然數(shù)集上的如下二元關(guān)系：ProofT（m，n）成立當(dāng)且僅當(dāng)n是編碼為m的公式在T中的一個證明的編碼。 我們可以證明，關(guān)系ProofT（m，n）是遞歸的。因遞歸關(guān)系都在Q中可表示，令PrfT（x，y）是ProofT（m，n）在Q中的表示公式。由證明謂詞PrfT（x，y）我們可定義可證謂詞PrT（x）yPrfT（x，y）。最后，哥德爾構(gòu)造了語句G（稱為哥德爾語句），其斷定自身在T中不可證，即。哥德爾證明了：若T是一致的，則G在T中不可證；若T是ω-一致的，則G也在T中不可證。 因此，則若T是ω-一致的，則T是不完全的。

由可證謂詞我們可定義一致性命題Con。④Con（T）是表達(dá)T的一致性的算術(shù)公式，其表達(dá)的意思是：形如0 ≠ 0的矛盾式在T中不可證。如上構(gòu)造的可證謂詞PrT（x）稱為標(biāo)準(zhǔn)可證謂詞。我們稱由標(biāo)準(zhǔn)可證謂詞PrT（x）構(gòu)造的語句Con（T）為典范一致性命題。本文中，若未作特別說明，我們假定是用Con（T）來表達(dá)理論T的一致性。由標(biāo)準(zhǔn)可證謂詞PrT（x）的性質(zhì)，我們在T中可證明G是等價(jià)于Con（T）。由此，我們得到第二不完全性定理：若T是一致的，則Con（T）在T中不可證。

哥德爾第一不完全性定理的證明假設(shè)T是ω-一致的。羅瑟（Rosser）在1936年改進(jìn)了哥德爾的結(jié)果。羅瑟的證明僅假設(shè)理論T是一致的，而“一致”是比 “ω-一致”更弱的條件。

羅瑟第一不完全性定理若T是Q的遞歸可公理化的一致擴(kuò)充，則T是不完全的。

我們強(qiáng)調(diào)哥德爾和羅瑟的第一不完全性定理間的區(qū)別。下文中，我們用G1表示羅瑟第一不完全性定理，G2表示第二不完全性定理。下面，我們分別基于成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性這三個標(biāo)準(zhǔn)論證不完全性定理的深度。不完全性定理滿足這三個標(biāo)準(zhǔn)的數(shù)學(xué)證據(jù)有很多，限于篇幅，本文我們將只討論關(guān)于這三個標(biāo)準(zhǔn)的最重要的數(shù)學(xué)證據(jù)。

三、成果的影響力

本節(jié)中，基于哥德爾之后人們對不完全性定理的研究成果，我們分析不完全性定理對數(shù)學(xué)基礎(chǔ)、哲學(xué)、經(jīng)典數(shù)學(xué)及理論計(jì)算機(jī)科學(xué)的影響。①事實(shí)上，哥德爾不完全性定理的影響不限于這些領(lǐng)域。限于篇幅，本文的討論集中于這幾個主要的領(lǐng)域。事實(shí)上，深入分析不完全性定理對這里任何一個領(lǐng)域的影響都需要專著的篇幅。這里我們不可能討論不完全性定理對這些領(lǐng)域各個方面的影響，而只能概述不完全性定理對這些領(lǐng)域的影響的主要方面。

不完全性定理對數(shù)學(xué)基礎(chǔ)的影響主要體現(xiàn)在如下五個方面。

第一，不完全性定理揭示了在邏輯和數(shù)學(xué)中普遍存在的不完全性現(xiàn)象。不完全性定理告訴我們?nèi)魏伟銐蛩阈g(shù)信息（如Q）的遞歸可公理化的一致理論都存在不可判定命題（即“遺漏”一些算術(shù)真理）。哥德爾構(gòu)造的不可判定命題是純粹的邏輯構(gòu)造，沒有自然的數(shù)學(xué)含義。在這個意義上，我們可以說哥德爾的證明揭示了PA的邏輯不完全性。在哥德爾之后，一個重要的問題是：PA是否也是數(shù)學(xué)上不完全的？是否存在具有實(shí)在數(shù)學(xué)含義的不可判定的算術(shù)命題（如數(shù)論、組合中的命題）？在哥德爾之后，人們在經(jīng)典數(shù)學(xué)中發(fā)現(xiàn)了很多具有實(shí)在數(shù)學(xué)含義的在PA中不可判定的算術(shù)命題。這些發(fā)現(xiàn)揭示了比一階算術(shù)更強(qiáng)的形式理論（如高階算術(shù)和公理集合論ZFC）的數(shù)學(xué)上的不完全性。例如，哥德爾和柯恩證明了連續(xù)統(tǒng)假設(shè)是獨(dú)立于ZFC的。事實(shí)上，人們在很多數(shù)學(xué)領(lǐng)域中（如分析、代數(shù)、拓?fù)?、?shù)理邏輯等）發(fā)現(xiàn)了大量具有實(shí)在數(shù)學(xué)含義的在ZFC中不可判定的數(shù)學(xué)命題。

第二，不完全性定理在一定意義上揭示了形式化方法（或形式理論）的本質(zhì)局限性。形式化方法是一種在邏輯與數(shù)學(xué)中廣泛使用的方法。不完全性定理揭示了包含Q的遞歸可公理化的一致理論的證明能力的限度。不管理論T有多強(qiáng)，只要T是遞歸可公理化的一致理論且包含足夠的算術(shù)信息（如Q），總存在理論T中的不可判定命題。若命題A在理論T中是不可判定的，我們總可找到比理論T更強(qiáng)的遞歸可公理化的一致理論S使得命題A在S中可證。然而，不完全性定理告訴我們，雖然理論T中的不可判定命題A在理論S中可證，但是理論S仍然存在不可判定命題。因此，不管我們怎么增強(qiáng)理論T，只要T包含足夠的算術(shù)信息，它的任意遞歸可公理化的一致擴(kuò)充都存在不可判定命題。Q是很弱的算術(shù)理論，因此我們可以說不完全性定理揭示了大多數(shù)形式理論的證明能力的限度。

第三，不完全性定理揭示了“真”和“可證”這兩個概念間的本質(zhì)區(qū)別。在不完全性定理之前，人們普遍認(rèn)為一個數(shù)學(xué)命題為真和其可證是相同的概念。特別地，一個算術(shù)命題為真是指其在算術(shù)的標(biāo)準(zhǔn)模型下為可證①在算術(shù)的標(biāo)準(zhǔn)模型中，論域是自然數(shù)集，常元符號0被解釋為最小的自然數(shù)0，函數(shù)符號S被解釋為自然數(shù)集上的后續(xù)函數(shù)S（n）= n+1， 函數(shù)符號+和×被解釋為自然數(shù)集上的加法和乘法運(yùn)算。，一個算術(shù)命題可證是指其在PA中可證。不完全性定理揭示了“可證”和“真”這兩個概念間的本質(zhì)區(qū)別：在PA中可證的算術(shù)命題都為真，但存在在PA中不可證的算術(shù)真命題。

第四，不完全性定理否定了懷特海—羅素的一種強(qiáng)版本的邏輯原子主義綱領(lǐng)：數(shù)學(xué)可以還原為邏輯。這種強(qiáng)版本的邏輯原子主義綱領(lǐng)包含兩個基本觀點(diǎn)：數(shù)學(xué)語言可還原為邏輯語言，數(shù)學(xué)定理可還原為邏輯證明。邏輯原子主義綱領(lǐng)期望建構(gòu)一種形式系統(tǒng)使得在其中可以形式化全部數(shù)學(xué)理論，且可證明所有的數(shù)學(xué)真命題，從而表明數(shù)學(xué)可還原為邏輯。G1直接否定了這種強(qiáng)版本的邏輯原子主義綱領(lǐng)：不存在一種形式理論在其中可以證明所有的數(shù)學(xué)真理。

第五，不完全性定理對希爾伯特綱領(lǐng)的發(fā)展產(chǎn)生了深刻的影響。希爾伯特綱領(lǐng)的一個主要目標(biāo)是用有限性方法證明數(shù)學(xué)理論的一致性。人們常認(rèn)為G2直接否定了希爾伯特綱領(lǐng)。 然而，學(xué)者們對此有不同的看法。②Michael Detlefsen， “On Interpreting G?del’s Second Theorem”， Journal of Philosophical Logic 8， 1979， pp. 297—313.對于“有限性方法”這個概念，我們沒有精確的定義；對于何謂“有限性方法”，人們有不同的看法。若“用有限性方法證明算術(shù)的一致性”是指算術(shù)的一致性在PA中可證，那么在這種意義上，我們可以說G2直接否定了希爾伯特綱領(lǐng)的這個目標(biāo)。若我們將可數(shù)序數(shù)長度的超窮歸納法也視為“有限性方法”，則根岑（Genzen）的結(jié)果表明，我們可在某種比PA稍強(qiáng)的理論中使用有限性方法證明PA的一致性。因此，G2并非完全否定希爾伯特綱領(lǐng)，而是表明了希爾伯特綱領(lǐng)應(yīng)用范圍的限度（其全局的實(shí)現(xiàn)是不可能的）。在不完全性定理之后，希爾伯特綱領(lǐng)得到了很好的局部實(shí)現(xiàn)。關(guān)于希爾伯特綱領(lǐng)的后續(xù)發(fā)展及其對數(shù)理邏輯（特別是證明論）和數(shù)學(xué)哲學(xué)的影響，文獻(xiàn)中有大量的討論。①相關(guān)的研究文獻(xiàn)很多，這里我們僅選擇最具代表性的文獻(xiàn)：（1） Solomon Feferman， “Hilbert’s Program Relativized： Proof-Theoretical and Foundational Reductions”， The Journal of Symbolic Logic， Vol. 53， No. 2， 1988， pp. 364—384； （2） Simpson G. Stephen， “Partial Realizations of Hilbert’s Program”， The Journal of Symbolic Logic， Vol. 53， No. 2， 1988， pp. 349—363； （3） Richard Zach， “Hilbert’s Program Then and Now”， in Philosophy of Logic， Handbook of the Philosophy of Science， 2007， pp. 411—447。

下面我們討論不完全性定理對經(jīng)典數(shù)學(xué)的影響。不完全性定理是原創(chuàng)性的數(shù)學(xué)成果。一種流行的看法是：不完全性定理的證明使用的是純邏輯的方法，與經(jīng)典數(shù)學(xué)沒有什么關(guān)聯(lián)。在不完全性定理的證明中，哥德爾語句是純粹的邏輯構(gòu)造，沒有實(shí)在的數(shù)學(xué)含義，其表達(dá)的不是關(guān)于自然數(shù)的算術(shù)性質(zhì)，而是關(guān)于算術(shù)形式理論自身的性質(zhì)。在哥德爾之后，一個自然的問題是：我們能否找到具有實(shí)在數(shù)學(xué)含義的不可判定的算術(shù)命題？我們稱由具有實(shí)在數(shù)學(xué)含義的不可判定命題所揭示的不完全性現(xiàn)象為具體不完全性。事實(shí)上，具體不完全性在數(shù)學(xué)中是普遍存在的。在哥德爾之后，人們發(fā)現(xiàn)了很多在PA中不可判定的具有實(shí)在數(shù)學(xué)含義的算術(shù)語句。②例如，Kanamori-McAloon principle， the Kirby-Paris sentence， the Hercules-Hydra game， the Worm principle， the flipping principle等。關(guān)于這些語句的內(nèi)容，參見Andrey Bovykin， “Brief introduction to unprovability”， Logic Colloquium， Lecture Notes in Logic 32， 2006。這些語句的構(gòu)造沒有使用算術(shù)化方法和可證謂詞，但比哥德爾語句更復(fù)雜：哥德爾語句在PA中是等價(jià)于典范一致性命題Con（PA）；而這些語句在PA + Con（PA）中也是不可判定的。③Lev D. Beklemishev， “G?del Incompleteness Theorems and the Limits of Their Applicability I”， Russian Math Surveys，2010.

哈維—弗里德曼（Harvey Friedman）是具體不完全性研究的國際知名專家。他的工作將具體不完全性的研究從一階算術(shù)擴(kuò)充到高階算術(shù)和集合論。在他的關(guān)于具體不完全性的專著“布爾關(guān)系理論與不完全性（Boolean Relation Theory and Incompleteness）”中，他發(fā)現(xiàn)了很多在高階算術(shù)的不同層級中不可證的關(guān)于算術(shù)和分析的數(shù)學(xué)定理的例子。④更多關(guān)于具體不完全性的研究，參見（1） Yong Cheng， Incompleteness for Higher-Order Arithmetic： An Example Based on Harrington’s Principle， Springer series： Springerbrief in Mathematics， Springer， 2019；（2） Harvey M. Friedman， Boolean Relation Theory and Incompleteness， to appear in Lecture Notes in Logic， Association for Symbolic Logic。

和其他數(shù)學(xué)定理不同的是，不完全性定理的影響力并非僅限于數(shù)學(xué)家和邏輯學(xué)家的圈子，它在哲學(xué)中也有廣泛的影響。⑤關(guān)于不完全性定理的正確使用與誤用，參見Torkel Franzen， G?del’s Theorem： An Incomplete Guide to Its Use and Abuse， A. K. Peters， 2005。自其發(fā)表以來，不完全性定理引發(fā)了與其相關(guān)的一些哲學(xué)問題的廣泛而持久的討論：如人類智能與機(jī)器智能的本質(zhì)及其區(qū)別，機(jī)器智能的限度等。限于篇幅，本文無法討論哥德爾的哲學(xué)思想及其對發(fā)現(xiàn)不完全性定理的影響。①關(guān)于哥德爾的哲學(xué)思想，參見王浩的著作：（1） Hao Wang， Reflections on Kurt G?del， The MIT Press， 1990； （2） Hao Wang， A Logical Journey： From G?del to Philosophy， The MIT Press， 1997。這里我們重點(diǎn)討論兩個與不完全性定理緊密相關(guān)的哲學(xué)論題：反機(jī)械主義論題和哥德爾析取論題。

現(xiàn)有文獻(xiàn)中有不少關(guān)于不完全性定理對“人類心智是否可機(jī)械化”這一哲學(xué)問題的影響的討論。②（1） Krajewski Stanislaw， “On the Anti-Mechanist Arguments Based on G?del Theorem”， Studia Semiotyczne， Vol. 34， No. 1， 2020，pp. 9—56； （2） Yong Cheng， “G?del’s Incompleteness Theorem and the Anti-Mechanist Argument： Revisited”， Studia Semiotyczne， Vol. 34， No. 1， 2020， pp. 159—182.反機(jī)械主義論題認(rèn)為人類心智是不可機(jī)械化的。單獨(dú)個體的心智能力是很有限的，這里我們不是考慮單獨(dú)個體的心智能力，而是考慮理想化的人類心智本質(zhì)上可以做什么。人類心智包括很多維度，這里我們僅考慮人類心智的數(shù)學(xué)輸出，即人類心智所能認(rèn)識的數(shù)學(xué)真理。圖靈提出了一種計(jì)算模型：圖靈機(jī)，并通過此模型給出“可機(jī)械化”概念一種精確的數(shù)學(xué)刻畫。反機(jī)械主義論題可更精確的表述為：人類心智的數(shù)學(xué)輸出超越任何圖靈機(jī)的數(shù)學(xué)輸出。這里，我們不討論“人類心智是否可機(jī)械化”這個一般的哲學(xué)問題，而僅討論不完全性定理與反機(jī)械主義論題間的關(guān)聯(lián)。對G1的一種流行解釋是：G1蘊(yùn)涵反機(jī)械主義論題。文獻(xiàn)中有不少基于不完全性定理的支持反機(jī)械主義論題的論證，其中最著名的是盧卡斯（Lucas）論證和彭羅斯（Penrose）論證。③（1） J. R. Lucas， “Minds， Machines， and G?del： A Retrospect”， in Machines and thought： The legacy of Alan Turing， Volume 1 （P. J. R. Millican and A. Clark， editors）， Oxford： Oxford University Press， 1996； （2） Roger Penrose， The Emperor’s New Mind： Concerning Computeres， Minds， and the Laws of Physics， Oxford： Oxford University Press， 1989.盧卡斯論證在文獻(xiàn)中被廣泛的批評。④（1） Solomon Feferman， “G?del， Nagel， Minds， and Machines”， The Journal of Philosophy， CVI（4）， pp. 201—219， 2009； （2） Paul Benacerraf， “God， the Devil and G?del”， The Monist 51， 1967， pp. 9—32.彭羅斯提出一個比盧卡斯論證更復(fù)雜精細(xì)的支持反機(jī)械主義論題的論證。⑤Roger Penrose， Shadows of the Mind： A Search for the Missing Science of Consciousness， Oxford： Oxford University Press， 1994.彭羅斯論證是文獻(xiàn)中被廣泛討論、仔細(xì)分析的支持反機(jī)械主義論題的最復(fù)雜、最有前景的一個論證。⑥（1） Per Lindstr?m， “Remarks on Penrose’s New Argument”， Journal of Philosophical Logic， 35，2006， pp. 231—237； （2） Stewart Shapiro， “Mechanism， Truth， and Penrose’s New Argument”， Journal of Philosophical Logic， XXXII（1） 2003， pp. 19—42.文獻(xiàn)中最新研究表明，認(rèn)為G1蘊(yùn)涵反機(jī)械主義論題的論證是源于對不完全性定理的某些誤解。⑦（1） Krajewski Stanislaw， “On the Anti-Mechanist Arguments Based on G?del Theorem”， Studia Semiotyczne， 2020； （2） Yong Cheng， “G?del’s Incompleteness Theorem and the Anti-Mechanist Argument： Revisited”.現(xiàn)今絕大多數(shù)哲學(xué)家和邏輯學(xué)家認(rèn)為盧卡斯論證和彭羅斯論證及其變體都不是令人信服的。然而，人們在對盧卡斯論證和彭羅斯論證的錯誤根源的認(rèn)識上存在分歧。克拉耶夫斯基（Krajewski）在最近的文章中詳細(xì)討論了基于不完全性定理的反機(jī)械主義論證的歷史，仔細(xì)分析了盧卡斯論證和彭羅斯論證的問題所在，并得出“G1并非蘊(yùn)涵反機(jī)械主義論題”的結(jié)論。①Krajewski Stanislaw， “On the Anti-Mechanist Arguments Based on G?del Theorem” . 更多關(guān)于不完全性定理與反機(jī)械主義論題間的關(guān)系的討論，參見：（1） Peter Koellner， “On the Question of Whether the Mind Can Be Mechanized Part I： From G?del to Penrose”， Journal of Philosophy， Volume 115， Issue 7， 2018， pp. 337—360； （2） Peter Koellner， “On the Question of Whether the Mind can be Mechanized Part II： Penrose’s New Argument”， Journal of Philosophy， Volume 115， Issue 9， 2018， pp. 453—484。

哥德爾本人并不認(rèn)為不完全性定理蘊(yùn)涵反機(jī)械主義論題，盡管他相信人類心智是不可機(jī)械化的，且可認(rèn)識所有的數(shù)學(xué)真理。哥德爾相信，與圖靈機(jī)相比，人類心智的獨(dú)特之處在于它能提出新公理，建構(gòu)新的數(shù)學(xué)理論。基于他的理性樂觀主義，哥德爾相信人類心智能夠認(rèn)識所有的算術(shù)真理。然而，哥德爾承認(rèn)，他既不能給出“人類心智不可機(jī)械化”的令人信服的論證，也不能給出“不存在絕對不可判定命題”的令人信服的論證。哥德爾認(rèn)為，從不完全性定理他至多可得出如下一個更弱的結(jié)論［稱為哥德爾析取論題（GD）］：若人類心智是可機(jī)械化的，則存在絕對不可判定命題（即人類心智無法認(rèn)識的數(shù)學(xué)命題）。②哥德爾在1951年的講演中提出析取論題，他寫道：“如下的析取命題是不可避免的：或者人類心智超越任何有限的機(jī)器，或者存在絕對不可判定問題（這兩個析取支命題都成立也是可能的，因此嚴(yán)格意義上有三種可能性）”。參見Kurt G?del， “Some Basic Theorems on the Foundations of Mathematics and Their Implications”， in Collected Works， Volume III： Unpublished Essays and Lectures， pp. 304—323， Oxford： Oxford University Press， 1951。在哥德爾看來，GD是可由不完全性定理推導(dǎo)出來的有哲學(xué)意義的數(shù)學(xué)定理。③更多關(guān)于GD的討論，參見研究文集：Leon Horsten and Philip Welch， G?del’s Disjunction： The Scope and Llimits of Mathematical Knowledge， Oxford： Oxford University Press， 2016。

科爾納（Koellner）對GD的分析是現(xiàn)有文獻(xiàn)中對此論題的最全面精確的分析?？茽柤{認(rèn)為，要精確的討論GD并證明不完全性定理蘊(yùn)涵GD，首先得在恰當(dāng)?shù)男问嚼碚撝行问交疓D?？茽柤{構(gòu)造了理論DTK，在DTK中形式化GD，并證明了如下結(jié)果：（1）GD在DTK中可證；（2）盧卡斯論證和彭羅斯論證在DTK中都不成立；（3）GD的兩個析取支命題“人類心智不可機(jī)械化”和“存在絕對不可判定命題”在DTK中對應(yīng)的形式化命題在DTK中都不可證。④（1） Peter Koellner， “On the Question of Whether the Mind Can Be Mechanized Part I： From G?del to Penrose”； （2） Peter Koellner， “On the Question of Whether the Mind can be Mechanized Part II： Penrose’s New Argument”.

最后，我們簡要討論不完全性定理對理論計(jì)算機(jī)科學(xué)的影響。理論計(jì)算機(jī)科學(xué)研究計(jì)算的能力和限度。不完全性定理的證明中包含若干可計(jì)算性理論的重要想法。哥德爾在證明不完全性定理中使用的原始遞歸函數(shù)和算術(shù)化方法是理論計(jì)算機(jī)科學(xué)研究中兩種很重要的工具。原始遞歸函數(shù)概念是在哥德爾之后發(fā)展起來的遞歸論這一數(shù)理邏輯分支的基礎(chǔ)概念和理論基石之一。算術(shù)化方法的思想是用自然數(shù)來給形式理論的一些語法對象如項(xiàng)、公式、證明等編碼。算術(shù)化方法在理論計(jì)算機(jī)科學(xué)研究中是一種很關(guān)鍵且有用的技術(shù)。在理論計(jì)算機(jī)科學(xué)中，否定性結(jié)果構(gòu)成一種重要和獨(dú)特的傳統(tǒng)。不完全性定理是否定性結(jié)果的一個范例。在不完全性定理之后，人們發(fā)現(xiàn)了很多邏輯中的重要否定性結(jié)果，如塔斯基真不可定義定理、連續(xù)統(tǒng)假設(shè)獨(dú)立性定理等。在理論計(jì)算機(jī)科學(xué)中，否定性結(jié)果的一個典型例子是圖靈停機(jī)問題不可判定性定理。圖靈停機(jī)問題和不完全性定理也有緊密的關(guān)聯(lián)。更多關(guān)于不完全性定理對理論計(jì)算機(jī)科學(xué)的影響的討論，參見研究文集《哥德爾與數(shù)學(xué)基礎(chǔ)：真的視野》。①M(fèi)atthias Baaz et al. （eds.）， Kurt G?del and the Foundations of Mathematics： Horizons of Truth， Cambridge： Cambridge University Press， 2014.

四、結(jié)論的豐富性

本節(jié)我們從結(jié)論的豐富性的標(biāo)準(zhǔn)論證不完全性定理的深度。本文中，定理結(jié)論的豐富性是指此定理及其證明可派生出的肯定性或否定性結(jié)果的多樣性。我們從如下三個方面論證不完全性定理的結(jié)論豐富性：不完全性定理的不同證明，不完全性定理的可推廣性（在何種程度上不完全性定理可被推廣），不完全性定理成立的限度（在何種情形下不完全性定理不成立）。

不完全性定理結(jié)論的豐富性的第一個標(biāo)志是證明方法的多樣性。哥德爾之后，人們發(fā)現(xiàn)了很多不完全性定理的不同證明。若存在一個能行的算法將不可判定命題顯式地構(gòu)造出來，我們稱G1的證明是構(gòu)造性的。G1的非構(gòu)造性證明僅斷定不可判定命題的存在，但沒有能行地將此不可判定命題顯式地構(gòu)造出來。我們稱G1的證明具有羅瑟特征，若它的證明僅需假設(shè)T是一致的，而不需假設(shè)更強(qiáng)的結(jié)論（如T是ω-一致的）。

我們可依據(jù)如下特征對文獻(xiàn)中的不完全性定理的不同證明進(jìn)行分類：使用證明論方法、使用遞歸論方法、使用模型論方法、使用算術(shù)化方法，使用對角線引理、使用邏輯悖論、使用構(gòu)造性證明、具有羅瑟特征、使用柯爾莫哥洛夫（Kolmogorov）復(fù)雜性、構(gòu)造有實(shí)在數(shù)學(xué)含義的不可判定命題。②Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”.不完全性定理的一種證明可能具有若干以上特征。以上這些特征都不是證明不完全性定理的必要條件：我們既可找到具有這些特征的不完全性定理證明的例子，也可找到不具有這些特征的不完全性定理證明的例子。哥德爾第一不完全性定理的證明具有如下特征：使用了算術(shù)化等證明論方法，沒有直接使用對角化引理、證明是構(gòu)造性的、不具有羅瑟特征、哥德爾語句類似于說謊者悖論中的說謊者語句，哥德爾語句沒有實(shí)在的數(shù)學(xué)內(nèi)容。不完全性定理的這些不同的證明方法揭示了不同領(lǐng)域間的關(guān)聯(lián)：證明論、遞歸論、邏輯悖論、模型論、柯爾莫哥洛夫復(fù)雜性、數(shù)論等。

不完全性定理結(jié)論的豐富性的第二個標(biāo)志是它具有多種推廣形式。G1和G2都既可推廣到PA的擴(kuò)充理論也可推廣到PA的子理論。不完全性定理這些豐富的推廣形式揭示了不完全性定理的解釋力量和廣泛的可應(yīng)用性。這里我們簡要給出G1的兩類推廣形式的例子。

第一，G1也可推廣到一些非遞歸可公理化但算術(shù)可定義的一致理論。①下面我們定義算術(shù)語言下公式的算術(shù)層級。有界公式（Σ0或Π 0公式）是由原子公式僅使用命題聯(lián)結(jié)詞和有界量詞（形如x≤y或x≤y）構(gòu)造而成。Σn + 1公式是等價(jià)于xφ的公式，其中φ是Π n公式。Π n + 1公式是等價(jià)于xφ的公式，其中φ是Σn公式。我們稱理論T是Σn可定義的，若存在Σn公式φ（x）使得n是T中某一公理的哥德爾編碼當(dāng)且僅當(dāng)φ（）在算術(shù)的標(biāo)準(zhǔn)模型中為真。我們稱理論T是算術(shù)可定義的，若對某一自然數(shù)n，T是Σn 可定義的。G1告訴我們，PA的任意遞歸可公理化的一致擴(kuò)充都是不完全的。但在一定條件下，這一結(jié)論可推廣到PA的一些非遞歸可公理化但算術(shù)可定義的擴(kuò)充理論。②（1） Makoto Kikuchi and Taishi Kurahashi， “Generalizations of G?del’s Incompleteness Theorems for Σn-definable Theories of Arithmetic”， Rew. Symb. Logic， 10（4）， 2017， pp. 603—616； （2） Saeed Salehi and Payam Seraji， “G?del-Rosser’s Incompleteness Theorem， Generalized and Optimized for Definable Theories”， Journal of Logic and Computation， Volume 27， Issue 5， 2017， pp. 1391—1397.

第二，通過解釋的概念，G1可推廣到很多具有不同語言的一致理論。③解釋的概念給我們提供了一種比較不同語言下理論的強(qiáng)度的方法。給定理論T和S，T在S中的一個解釋是從T的公式集到S的公式集的一個轉(zhuǎn)換函數(shù)，使得T的公理在此轉(zhuǎn)換函數(shù)下對應(yīng)的公式在S中可證。關(guān)于解釋概念的精確定義，參見Albert Visser， “Can We Make the Second Incompleteness Theorem Coordinate Free?”， Journal of Logic and Computation， 21（4）， 2011， pp. 543—560.我們可定義G1對一致理論T成立當(dāng)且僅當(dāng)對任意遞歸可公理化的一致理論S，若T在S中可解釋，則S是不完全的。我們知道G1對PA成立。我們可證明G1對很多解釋度比PA弱的理論也成立。④我們稱理論T在解釋度意義上比理論S弱，若T在S中可解釋，但S在T中不可解釋。例如，G1對Q和R都成立。理論R在解釋度意義上比Q弱，人們常認(rèn)為理論R是使得G1成立的在解釋度意義上的最弱理論。事實(shí)上，G1對很多在解釋度意義上比理論R弱的理論也成立。⑤關(guān)于更多使得G1成立的解釋度比PA弱的理論及解釋度比R弱的理論的例子，參見Yong Cheng， “Finding the Limit of Incompleteness I”。

G2也有多種推廣形式，這里我們僅舉兩個典型例子。⑥關(guān)于G2的推廣形式的更多例子，參見Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”。首先，我們可通過解釋的概念推廣G2。一個經(jīng)典的結(jié)論是：不存在遞歸可公理化的一致理論T使得Q + Con（T）在T中可解釋。由此可得，對任意遞歸可公理化的一致理論T，若Q在T中可解釋，則G2對T成立：即Con（T）在T中不可證。其次，洛布（L?b）定理是G2的一種重要推廣形式：對Q的任意遞歸可公理化的一致擴(kuò)充理論T，對任意標(biāo)準(zhǔn)可證謂詞PrT（x）和公式φ，若→ φ，則。由此可得，G2對T成 立。

最后，我們討論關(guān)于不完全性定理的否定性結(jié)果：不完全性定理成立的限度。對不完全性定理成立范圍的研究揭示了不完全性定理可應(yīng)用性的限度，極大地更新了我們對不完全性定理的可應(yīng)用范圍的理解，提供了論證不完全性定理的結(jié)論豐富性的數(shù)學(xué)新證據(jù)。

我們先討論G1成立的限度。首先，很多一致的理論是完全的。①例如，如下理論是完全的：稠密無端點(diǎn)的線性序理論， 給定特征的代數(shù)閉域理論， 實(shí)閉域理論等。其次，一種算術(shù)理論是否完全與理論的語言有關(guān)。在語言L（0，S，+，×）中，PA是不完全的。但在語言L（0，S），L（0，S，＜）和L（0，S，＜，+）中分別存在遞歸可公理化的完全的算術(shù)理論。②Herbert B. Enderton， A Mathematical Introduction to Logic （2nd ed.）， Boston， MA： Academic Press， 2001.關(guān)于G1是否成立與理論的語言的關(guān)系，我們作如下幾點(diǎn)說明：第一，包含足夠的關(guān)于算術(shù)的信息對于證明G1是必要的。例如，歐幾里得幾何不是關(guān)于算術(shù)而是關(guān)于點(diǎn)、線、面的理論，塔斯基證明了歐幾里得幾何是完全的。第二，包含關(guān)于算術(shù)的乘法信息對于證明G1是必要的。若一種理論只包含關(guān)于算術(shù)的加法信息而不包含關(guān)于算術(shù)的乘法信息，其可能是完全的。例如：普雷斯堡（Presburger）算術(shù)是關(guān)于算術(shù)的加法的理論，但其是完全的。③Roman Murawski， Recursive Functions and Metamathematics： Problems of Completeness and Decidability， G?del’s Theorems， Springer Netherlands， 1999， 定理3.2.2。

我們知道，G1對Q的某些算術(shù)可定義的一致擴(kuò)充成立。但并非Q的所有算術(shù)可定義的一致擴(kuò)充都是不完全的。④關(guān)于Q的某些算術(shù)可定義的完全擴(kuò)充的例子，參見Saeed Salehi and Payam Seraji，“ G?del-Rosser’s Incompleteness Theorem， Generalized and Optimized for Definable Theories”。我們已知很多使得G1成立的在解釋度意義上比R弱的理論。當(dāng)前的一個前沿問題是：是否存在使得G1成立的解釋度意義上的極小理論。⑤Yong Cheng， “Finding the Limit of Incompleteness I”.

下面我們討論G2成立的限度。無論在數(shù)學(xué)或哲學(xué)上，G2與G1本質(zhì)上是不同的。它們的區(qū)別在于：對于G1，要證明一種理論是不完全的，僅需證明存在一個不可判定命題即可，我們并不關(guān)心此命題的內(nèi)容（此命題并不必須是關(guān)于此理論的系統(tǒng)性質(zhì)）。而對于G2，我們要證明T的一致性在T中不可證，就需恰當(dāng)?shù)男问交癟的一致性”這個概念。因此，對于G2，我們需關(guān)心如何在T中表達(dá)T的一致性。我們稱G2對理論T成立，若“T的一致性”在T中不可證。然而，這個定義是模糊的。G2對理論T是否成立取決于我們?nèi)绾卧赥中形式化“T的一致性”。我們稱這一現(xiàn)象為G2的內(nèi)涵性問題。在我們可不使用算術(shù)化和可證謂詞等純邏輯方法來構(gòu)造有實(shí)在數(shù)學(xué)含義的不可判定命題的意義上，我們可以說G1是外延性的。然而，G2是內(nèi)涵性的，與G1有本質(zhì)的區(qū)別。如我們下面將討論的，G2對理論T是否成立取決于很多因素。現(xiàn)有文獻(xiàn)中有不少關(guān)于G2的內(nèi)涵性問題的討論。①（1） Volker Halbach and Albert Visser， “Self-reference in Arithmetic I”， Review of Symbolic Logic 7（4）， 2014， pp. 671—691； （2） Volker Halbach and Albert Visser， “Self-Reference in Arithmetic II”， Review of Symbolic Logic 7（4）， 2014， pp. 692—712； （3） Albert Visser， “Can We Make the Second Incompleteness Theorem Coordinate Free?”.

我們稱公式φ（x）是理論T公理集的表示公式，若對任意的自然數(shù)n，PA當(dāng)且僅當(dāng)n是T的某一公理的編碼。若未作特殊說明，下文中我們作如下假設(shè)：（1）理論T是Q的遞歸可公理化的一致擴(kuò)充；（2）我們使用典范一致性命題Con（T）表達(dá)理論T的一致性；（3）我們默認(rèn)使用哥德爾編碼法；（4）我們使用的可證謂詞是標(biāo)準(zhǔn)可證謂詞；（5）理論T公理集的表示公式是Σ1公式。

基于文獻(xiàn)中關(guān)于不完全性的研究，下面我們說明G2對理論T是否成立取決于如下因素：（1） 理論T的選擇；（2） 表達(dá)一致性的方式；（3） 可證謂詞的選擇；（4） 編碼方法的選擇；（5） 理論T公理集的表示公式的復(fù)雜性②指此表示公式在算術(shù)層級中的復(fù)雜性（如是Σ1公式還是Π 1公式）。。

對這些因素作兩點(diǎn)說明：第一，這些因素間不是完全相互獨(dú)立的，但它們強(qiáng)調(diào)的側(cè)重點(diǎn)有所不同。例如，給定一種表達(dá)一致性的模式，選擇不同的可證謂詞也導(dǎo)致不同的表達(dá)一致性的方式。但（2）強(qiáng)調(diào)的是表達(dá)一致性的整體方式，而不是具體可證謂詞的選擇。而（3）強(qiáng)調(diào)的是具體可證謂詞的選擇。第二，當(dāng)我們討論G2是否成立是如何取決于某種因素時(shí)，我們是假定其他的因素以我們?nèi)缟霞僭O(shè)的方式保持不變，而僅討論此種因素的變動是如何影響G2是否成立的。以因素（2）為例，當(dāng)我們說G2對理論T是否成立取決于表達(dá)一致性的方式時(shí)，我們是說：假設(shè)T是Q的遞歸可公理化的一致擴(kuò)充，使用的是標(biāo)準(zhǔn)可證謂詞和哥德爾編碼法且T公理集的表示公式是Σ1公式，不同于典范一致性命題的表達(dá)一致性的方式可能會導(dǎo)致G2不成立。

下面我們簡要討論G2是否成立是如何取決于以上五個因素的。③關(guān) 于G2的 內(nèi) 涵 性 問 題 的 詳 細(xì) 討 論，參 見Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”。第一，G2對理論T是否成立取決于理論T的選擇。若理論T并非包含足夠多的關(guān)于算術(shù)的信息，則G2可能不成立：T的一致性在T中可證。例如，威拉德（Willard）研究G2對理論T不成立的邊界情形，并構(gòu)造了一些算術(shù)理論，它們不能證明后續(xù)函數(shù)是全函數(shù)，但可證明自身的一致性。④（1） D. E. Willard， “Self-verifying Axiom Systems， the Incompleteness Theorem and Related Reflection Principles”， Journal of Symbolic Logic， 66（2）， 2001， pp. 536—596； （2） D. E. Willard， “A generalization of the Second Incompleteness Theorem and Some Exceptions to It”， Ann. Pure Appl. Logic， 141（3）， 2006， pp. 472—496.

第二，G2對理論T是否成立取決于表達(dá)一致性的方法。何謂一個理論的一致性命題？不同學(xué)者有不同的看法。在研究文獻(xiàn)中，我們常用理論T語言中的算術(shù)語句表達(dá)T的一致性。然而，仍存在不同于典范一致性命題的表達(dá)一致性的方法使得G2不成立：在這種表達(dá)方式下，其對應(yīng)的一致性命題在理論T中可證。①Kurahashi Taishi， “Rosser Provability and the Second Incompleteness Theorem”， Symposium on Advances in Mathematical Logic 2018 Proceedings， 2020.

第三，G2對理論T是否成立取決于可證謂詞的選擇。維瑟（Visser）論證道，一致性命題不是一個絕對的概念，而是與可證謂詞的選擇有關(guān)。②Albert Visser， “The Second Incompleteness Theorem： Reflections and Ruminations”， in Leon Horsten and Philip Welch （eds.）， G?del’s Disjunction： The Scope and Limits of Mathematical Knowledge， Oxford： Oxford University Press， 2016.我們知道G2對標(biāo)準(zhǔn)可證謂詞成立，即理論T的典范一致性命題在T中不可證。然而，對于非標(biāo)準(zhǔn)可證謂詞，G2可能不成立。一種重要的非標(biāo)準(zhǔn)可證謂詞是羅瑟可證謂詞，其是羅瑟在證明G1時(shí)引入的。③關(guān)于羅瑟可證謂詞的定義，參見Roman Murawski， Recursive Functions and Metamathematics： Problems of Completeness and Decidability， G?del’s Theorems， Springer Netherlands， 1999。我們可證明，用羅瑟可證謂詞表達(dá)的一致性命題在理論T中可證。④即若PrT（x）是羅瑟可證謂詞，則其對應(yīng)的一致性命題在T中可證。

第四，G2對理論T是否成立取決于編碼方法的選擇。格拉布邁爾定義了一類可接受的編碼方法，并證明了G2對這類可接受的編碼方法是成立的；然而，格拉布邁爾指出，若一種編碼方法是不可接受的，則G2可能不成立。⑤Grabmayr Balthasar， “On the Invariance of G?del’s Second Theorem with Regard to Numberings”， The Review of Symbolic Logic， Vol. 14， Issue 1， March 2021， pp. 51—84.

最后，G2對理論T是否成立取決于理論T公理集的算術(shù)復(fù)雜性。給定理論T公理集的表示公式，我們可定義其對應(yīng)的可證謂詞和一致性命題。我們已知，若理論T公理集的表示公式是Σ1公式，則其對應(yīng)的一致性命題在T中不可證。若理論T的公理集具有不同復(fù)雜性的表示公式，則在此種表示公式下，G2可能不成立，即其對應(yīng)的一致性命題可能在T中可證。例如，費(fèi)弗曼構(gòu)造了理論T公理集的一個復(fù)雜性為Π1的表示公式，使得其對應(yīng)的一致性命題在T中可證，即G2不成立。⑥Solomon Feferman， Arithmetization of Mathematics in a General Setting， Fundamenta Mathematicae， Vol. 49， 1960， pp. 35—92.

五、理論的統(tǒng)一性

下面，我們從理論統(tǒng)一性的標(biāo)準(zhǔn)論證不完全性定理的深度。理論的統(tǒng)一性是指建立起的不同領(lǐng)域理論間的關(guān)聯(lián)。下面我們從如下方面說明不完全性定理的理論統(tǒng)一性：經(jīng)典數(shù)學(xué)與元數(shù)學(xué)（證明論）間的關(guān)聯(lián)；不完全性與不可判定性理論間的關(guān)聯(lián)；不完全性與邏輯悖論間的關(guān)聯(lián)；不完全性與可證性邏輯間的關(guān)聯(lián)；不完全性與真的形式理論間的關(guān)聯(lián)。

哥德爾不完全性定理的證明使用了數(shù)學(xué)和邏輯的方法。例如，在哥德爾的證明中，他使用了如中國剩余定理和素?cái)?shù)唯一表示定理之類的數(shù)論方法，以及如算術(shù)化、可表示性、自指構(gòu)造之類的元數(shù)學(xué)方法。前面我們指出，在哥德爾之后，人們發(fā)現(xiàn)了很多具有實(shí)在數(shù)學(xué)含義的在PA中不可判定的算術(shù)命題。之前的討論強(qiáng)調(diào)通過純邏輯方法構(gòu)造的不可判定命題與具有實(shí)在數(shù)學(xué)內(nèi)容的不可判定命題間的區(qū)別。我們知道，哥德爾語句的構(gòu)造使用了算術(shù)化方法，而具有實(shí)在數(shù)學(xué)內(nèi)容的不可判定命題如佩爾斯—哈靈頓（Pairs-Harrington）語句的構(gòu)造沒有使用算術(shù)化方法。但一個有趣、令人驚訝的事實(shí)是，前面我們給出的具有實(shí)在數(shù)學(xué)內(nèi)容的不可判定命題實(shí)際上是等價(jià)于某種可通過算術(shù)化方法來表示的元數(shù)學(xué)命題。①Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”.這一事實(shí)揭示了經(jīng)典數(shù)學(xué)中的具有實(shí)在數(shù)學(xué)含義的不可判定命題與元數(shù)學(xué)的算術(shù)命題間的關(guān)聯(lián)。

最后，我們簡要地討論不完全性定理與不可判定性理論、邏輯悖論、可證性邏輯及真的形式理論間的關(guān)聯(lián)。哥德爾的工作和可計(jì)算性理論以及不可判定性理論間有緊密的關(guān)聯(lián)。哥德爾的證明中包含了可計(jì)算性理論中一些重要思想的萌芽：如算術(shù)化方法、原始遞歸函數(shù)等。算術(shù)化方法和遞歸函數(shù)在遞歸論的發(fā)展中扮演了重要的角色。我們稱理論T是實(shí)質(zhì)不可判定的，若T的遞歸可公理化的一致擴(kuò)充都是不可判定的。②一理論是不可判定的，若此理論的定理的編碼集不是遞歸集。我們稱理論T是實(shí)質(zhì)不完全的，若T的遞歸可公理化的一致擴(kuò)充都是不完全的。我們可證明，理論T是實(shí)質(zhì)不可判定的當(dāng)且僅當(dāng)T是實(shí)質(zhì)不完全的。這表明，完全性/不完全性與可判定性/不可判定性之間是緊密關(guān)聯(lián)的。我們可通過停機(jī)問題的不可判定性證明G1和G2。這些都表明了不完全性定理和不可判定性理論間的緊密關(guān)系。

當(dāng)前關(guān)于不完全性定理的研究揭示了不完全性定理是與邏輯悖論緊密相關(guān)的。哥德爾指出：“任何認(rèn)識論上的悖論都可用來構(gòu)造一個不可判定命題”。③Solomon Feferman et al. （ed.）： Kurt G?del’s Collected Works （Vol. 1）， New York and Oxford： Oxford University Press， 1995， pp. 145—195.哥德爾語句使用的是“證明”概念，而說謊者悖論中的說謊者語句使用的是語義“真”概念。哥德爾語句可被看作一種形式化版本的說謊者語句（用“可證”概念取代“真”概念）。除了說謊者悖論，還有很多其他的邏輯悖論可通過恰當(dāng)?shù)男问交挥脕碜C明不完全性定理：如貝瑞（Berry）悖論、格林靈—納爾遜（Grelling-Nelson）悖論、意外考試悖論、亞布洛（Yablo）悖論等。④Yong Cheng， “Current Research on G?del’s Incompleteness Theorem”.這些研究證實(shí)了哥德爾如上關(guān)于不完全性與邏輯悖論間的關(guān)聯(lián)的觀點(diǎn)。

作為對角化引理的應(yīng)用，不完全性定理的一個重要的結(jié)論是塔斯基真不可定義定理。令算術(shù)可證集是所有在PA中可證的算術(shù)語句組成的集合，算術(shù)真語句集是所有在算術(shù)的標(biāo)準(zhǔn)模型中為真的算術(shù)語句組成的集合。不完全性定理揭示了算術(shù)可證集是算術(shù)真語句集的真子集。由塔斯基真不可定義定理，算術(shù)真語句集在算術(shù)的標(biāo)準(zhǔn)模型中是不可定義的。算術(shù)可證集在算術(shù)的標(biāo)準(zhǔn)模型中是可定義的，但不是遞歸集。維瑟由塔斯基真不可定義定理給出G2的一個非自指性證明。①Albert Visser， “From Tarski to G?del： or， How to Derive the Second Incompleteness Theorem from the Undefinability of Truth without Self-reference”， Journal of Logic and Computation， Volume 29， Issue 5， 2019， pp. 595—604.這些研究揭示了不完全性定理與塔斯基真不可定義定理間的關(guān)聯(lián)。

可證性邏輯是研究不完全性及算術(shù)的元數(shù)學(xué)的一種重要且有用的工具。歷史上，可證性邏輯的起源與不完全性定理緊密相關(guān)，如亨金（Henkin）問題、可導(dǎo)性條件、洛布定理。在這種意義上，我們可以說不完全性定理是連接一階算術(shù)和模態(tài)邏輯的一種橋梁。算術(shù)解釋的概念為我們提供了一種建立可證性邏輯和算術(shù)的元數(shù)學(xué)的關(guān)聯(lián)的重要工具。②算術(shù)解釋是模態(tài)公式集到一階算術(shù)語句集的函數(shù)。關(guān)于算術(shù)解釋的精確定義，參見George Boolos， The Logic of Provability， Cambridge University Press， 1993。令人驚訝的是，可證性邏輯GL和GLS的索洛維（Solovay）算術(shù)完全性定理刻畫了算術(shù)可證集和算術(shù)真語句集間的區(qū)別。令T是Q的Σ1-可靠的遞歸可公理化的擴(kuò)充。③我們稱算術(shù)理論T是Σ1-可靠的，若任何在T中可證的Σ1公式在算術(shù)的標(biāo)準(zhǔn)模型中都為真。GL的索洛維算術(shù)完全性定理告訴我們：對任意的模態(tài)公式A，A在GL中可證當(dāng)且僅當(dāng)對任意的算術(shù)解釋f，f（A）在PA中可證。GLS的索洛維算術(shù)完全性定理告訴我們：對任意的模態(tài)公式A，A在GLS中可證當(dāng)且僅當(dāng)對任意的算術(shù)解釋f，f（A）在算術(shù)的標(biāo)準(zhǔn)模型中為真。

我們知道不完全性定理（特別是G2）的證明取決于可證謂詞的性質(zhì)。可證性邏輯是關(guān)于可證謂詞的性質(zhì)的邏輯。不同的可證謂詞可能對應(yīng)不同的可證性邏輯。基于不同可證性謂詞的可證性邏輯揭示了不同可證性謂詞的性質(zhì)。可證性邏輯給我們提供了一種理解不完全性的新視角和重要的工具。

六、對本文分析的一些討論

基于上文對不完全性定理的深度的分析，本節(jié)我們進(jìn)一步討論與數(shù)學(xué)定理的深度相關(guān)的一些問題。

第一，基于現(xiàn)有文獻(xiàn)，我們沒有一個判斷數(shù)學(xué)定理是否深刻的一般標(biāo)準(zhǔn)。我們對“深刻”一詞沒有精確的定義，“數(shù)學(xué)深度”是個模糊的概念。一個自然的問題是：本文提出的分析論證不完全性定理深度的三個標(biāo)準(zhǔn)是否也可被看作判斷數(shù)學(xué)定理是否深刻的一般標(biāo)準(zhǔn)呢？成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性，這三個特征中的任何單個特征都不是判斷一個數(shù)學(xué)定理是否深刻的充分條件。例如，有影響力的成果未必被公認(rèn)為是深刻的，結(jié)論豐富的定理也未必被公認(rèn)為是深刻的。關(guān)于成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性是不是判斷一個數(shù)學(xué)定理是否深刻的必要條件，文獻(xiàn)中是有爭議的。本人傾向于認(rèn)為這些特征都是判斷一個數(shù)學(xué)定理是否深刻的必要條件。一個深刻的數(shù)學(xué)定理應(yīng)具有這些特征，盡管人們在論證數(shù)學(xué)定理具有這些特征時(shí)可能使用不同的數(shù)學(xué)證據(jù)。一個支持這種觀點(diǎn)的證據(jù)是：到目前為止，我們還沒有發(fā)現(xiàn)一個不具有這些特征的數(shù)學(xué)定理被公認(rèn)為是深刻的。另一個自然的問題是：雖然單個特征不是判斷數(shù)學(xué)定理是否深刻的充分條件，但成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性這三個特征的合取是否為判斷一個數(shù)學(xué)定理是否深刻的充分條件？對此，我們是不清楚的，雖然我們認(rèn)為對于分析論證不完全性定理的深度而言，這三個特征已經(jīng)足夠。即使定理的深度僅可由成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性來刻畫，我們可以比較具有這些特征的不同定理的深度嗎？在本人看來，很難有一個統(tǒng)一的方法去比較不同數(shù)學(xué)定理的深度，雖然我們有可能比較兩個十分相近的定理的深度。我們提出的三個標(biāo)準(zhǔn)（成果的影響力、結(jié)論的豐富性、理論的統(tǒng)一性）是定性而非定量的。關(guān)于影響力的大小、結(jié)論豐富性的程度及理論統(tǒng)一性的程度，我們無法有精確的界定。即使不同的定理都具有成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性這些特征，我們對這些特征的分析論證及其使用的證據(jù)也是不同的。因此，我們很難提出一個比較不同數(shù)學(xué)定理深度的一般方法。①對于數(shù)學(xué)定理的一些具體特征如定理的證明強(qiáng)度，我們可有一般的方法比較不同數(shù)學(xué)定理的這些特征。例如反推數(shù)學(xué)研究數(shù)學(xué)定理的證明所需的公理的強(qiáng)度，反推數(shù)學(xué)提供了一種比較不同數(shù)學(xué)定理的證明強(qiáng)度的一般方法。

第二，定理的深度不是定理內(nèi)在的本質(zhì)特征，而是關(guān)于這個定理的研究實(shí)踐的特征。數(shù)學(xué)定理的某些特征是定理內(nèi)在的客觀特征，如結(jié)論的語法復(fù)雜性、定理的邏輯強(qiáng)度等。但數(shù)學(xué)定理的深度刻畫的是主體對數(shù)學(xué)定理的認(rèn)知評價(jià)。因此，定理深度的評估與人們對定理的認(rèn)知理解水平有關(guān)。在這種意義上，我們可以說定理的深度不是定理與生俱來的內(nèi)在特征，而是在對此定理的研究實(shí)踐中學(xué)術(shù)共同體對此定理達(dá)成共識的學(xué)術(shù)評價(jià)。

第三，定理的深度具有歷史性和時(shí)間性。人們之前認(rèn)為深刻的定理隨著時(shí)間的推移可能不再被認(rèn)為是深刻的。例如，在古希臘時(shí)代，人們認(rèn)為“正方形的對角線的長度不是有理數(shù)”是個深刻的定理，然而，在今天這個定理被認(rèn)為證明太簡單而不再被認(rèn)為是深刻的。一個定理的深度被廣泛接受和認(rèn)同通常是幾代學(xué)者對此定理研究的結(jié)果。一個定理剛發(fā)表時(shí)人們可能并未充分意識到此定理的深刻含義從而不被廣泛認(rèn)為是深刻的，然而其在后續(xù)研究實(shí)踐中可能被廣泛認(rèn)為是深刻的。以不完全性定理為例，在哥德爾之后通過對不完全性定理的深入研究，人們才逐步全面的認(rèn)識到不完全性定理成果的影響力、結(jié)論的豐富性和理論的統(tǒng)一性。哥德爾發(fā)表不完全性定理時(shí)可能他自己都沒意識或預(yù)想到不完全性定理會對數(shù)學(xué)基礎(chǔ)、哲學(xué)、經(jīng)典數(shù)學(xué)和理論計(jì)算性科學(xué)產(chǎn)生如此重要、廣泛和持久的影響；不完全性定理會有如此多的不同證明和推廣形式，揭示出如此多的不同領(lǐng)域間的關(guān)聯(lián)統(tǒng)一性，第二不完全性定理是否成立會取決于這么多的因素。在今天，不完全性定理的證明是本科高年級邏輯教材中的標(biāo)準(zhǔn)內(nèi)容。哥德爾之后關(guān)于不完全性的一些研究在技術(shù)上比哥德爾的證明更加復(fù)雜（如關(guān)于具體不完全性的研究）。哥德爾之后人們對不完全性定理的研究已極大地更新和深化了我們對不完全性的理解，人們對不完全性定理理解的深度和廣度已超過了哥德爾時(shí)代對此定理的理解。因此，若不完全性定理的深度僅與哥德爾的初始證明有關(guān)，而與哥德爾之后對此定理的研究實(shí)踐無關(guān)，則我們可能不再認(rèn)為不完全性定理是深刻的。最后，一個定理成果的影響力、結(jié)論的豐富性及理論的統(tǒng)一性都取決于對此定理的研究實(shí)踐的發(fā)展水平。然而，研究實(shí)踐是沒有限度的；隨著研究的深入，人們會發(fā)現(xiàn)關(guān)于不完全性定理成果的影響力、結(jié)論的豐富性及理論統(tǒng)一性的更多數(shù)學(xué)證據(jù)。

第四，對數(shù)學(xué)定理的深度評價(jià)不應(yīng)僅基于個體的興趣和認(rèn)知水平。因不同的個體對數(shù)學(xué)定理的深度可能有不同的判斷。對同一個定理，有些人可能認(rèn)為它是深刻有趣的，而其他人卻可能不這樣認(rèn)為。對數(shù)學(xué)基礎(chǔ)感興趣的數(shù)學(xué)家更容易認(rèn)為不完全性定理是深刻的；而對數(shù)學(xué)基礎(chǔ)沒有興趣的數(shù)學(xué)家可能不認(rèn)為不完全性定理是深刻的。雖然個體對一個數(shù)學(xué)定理是否深刻可能有不同的看法，但對一個學(xué)術(shù)共同體而言，對定理深度的認(rèn)識是可能達(dá)成共識的，從而可能是客觀的。數(shù)學(xué)定理的深度應(yīng)由定理所在領(lǐng)域的學(xué)術(shù)共同體來評價(jià)，而不是由所有的學(xué)術(shù)共同體來評價(jià)。例如，不完全性定理的深度不應(yīng)由拓?fù)鋵W(xué)家來評價(jià)，而應(yīng)主要由數(shù)理邏輯學(xué)家來評價(jià)。本文中對不完全性定理成果的影響力、結(jié)論的豐富性和理論統(tǒng)一性的分析都是基于研究文獻(xiàn)中對不完全性定理研究的數(shù)學(xué)證據(jù)，而不是基于個人的偏好和興趣，盡管我們對文獻(xiàn)中關(guān)于不完全性定理的研究成果的知識是有限的，且因限于篇幅本文給出的數(shù)學(xué)證據(jù)也是有限的。從這個意義上，我們可以說本文對不完全性定理深度的分析論證是客觀的。

下面我們描述一個判定給定的數(shù)學(xué)定理是否深刻的實(shí)際程序。給定某領(lǐng)域X中的數(shù)學(xué)定理A，A是否深刻可由領(lǐng)域X中國際上最頂尖的專家組成的學(xué)術(shù)委員會來判定——學(xué)術(shù)委員會可先確定判定此定理A是否深刻的達(dá)成共識的標(biāo)準(zhǔn)（如本文提出的影響力、豐富性和統(tǒng)一性標(biāo)準(zhǔn)），再根據(jù)這些標(biāo)準(zhǔn)集體判定定理A是否深刻。

關(guān)于數(shù)學(xué)定理的深度，有很多問題值得后續(xù)研究：如刻畫數(shù)學(xué)定理深度的一般標(biāo)準(zhǔn)，比較不同定理深度的方法及其可行性，數(shù)學(xué)定理深度的客觀性，數(shù)學(xué)定理的深度和其他對象（如證明、論文、項(xiàng)目、哲學(xué)命題等）的深度之間的區(qū)別、純邏輯定理的深度與純數(shù)學(xué)定理的深度的區(qū)別等。本文探討的是不完全性定理的數(shù)學(xué)深度，至于不完全性定理是否有哲學(xué)深度（若有的話）以及它的哲學(xué)深度表現(xiàn)在哪些方面，這些有待進(jìn)一步研究。

本文中，我們將不完全性定理作為研究數(shù)學(xué)定理深度的一個案例。我們研究刻畫不完全性定理深度的標(biāo)準(zhǔn)，以及基于這些標(biāo)準(zhǔn)如何論證不完全性定理的深度。基于文獻(xiàn)中最新研究成果，我們提出刻畫不完全性定理深度的三個標(biāo)準(zhǔn)：成果的影響力、結(jié)論的豐富性及理論的統(tǒng)一性，并論證了不完全性定理滿足這三個標(biāo)準(zhǔn)。希望本文對不完全性定理的深度的分析，能提供我們分析“數(shù)學(xué)深度”的新視角。