趙曉玉

1 引言

作為20 世紀邏輯學最為重要的成就之一，1930 年，哥德爾證明了關于遞歸可枚舉理論的哥德爾不完全性定理1對幾個說法略作說明：哥德爾第一不完全性定理指哥德爾證明的第一不完全性定理，哥德爾第二不完全性定理與此類似，哥德爾不完全性定理是哥德爾第一不完全性定理和哥德爾第二不完全性定理的概括；把哥德爾第一不完全性定理推廣到非遞歸枚舉理論上得到的定理稱之為推廣的哥德爾第一不完全性定理，推廣的哥德爾第二不完全性定理與此類似，推廣的哥德爾不完全性定理是推廣的哥德爾第一不完全性定理和推廣的哥德爾第二不完全性定理的概括；第一不完全性定理是哥德爾第一不完全性定理和推廣的哥德爾第一不完全性定理的概括，第二不完全性定理與此類似，不完全性定理是哥德爾不完全性定理和推廣的哥德爾不完全性定理的概括。。

定理1(哥德爾第一不完全性，1930).設T是包含羅賓森算術（Q）的、遞歸可枚舉的理論。如果T是ω-一致的，那么存在一個Π1的語句ρ使得且。

定理2(哥德爾–羅瑟第一不完全性，1936).設T是包含Q 的、遞歸可枚舉的理論。如果T是一致的，那么存在一個Π1的語句ρ使得且。

定理3(哥德爾第二不完全性，1930).設T是包含皮亞諾算術（PA）的、遞歸可枚舉的理論。如果T是一致的，那么T不能證明自身一致性。

一個十分自然的問題便由是而生：哥德爾不完全性定理能否推廣到非遞歸可枚舉理論上？對此，已有一些研究成果。關于推廣的哥德爾第一不完全性定理，

(1) 1975 年，R.G.Jeroslow 在[12，定理2]中證明了：如果T是包含PA 的、?2-可定義的、一致的理論，那么T不是Π1-完全的。

(2) 1977 年，P.Hájek 在[8]中首先推廣了Jeroslow 的結果：如果T是包含PA的、?n-可定義的、一致的理論，那么T不是Πn?1-完全的。并同時證明了另外兩個結果：如果T是包含PA 的、Πn-可定義的、n-一致的理論，那么T不是Πn?1-完全的；如果T是包含PA 的、Πn-可定義的、n-一致的理論，那么T不是Πn-決定的。

(3) 2016 年，S.Salehi 和P.Seraji 在[20]中進一步推廣了Jeroslow 和Hájek 的工作，從而把哥德爾第一不完全性定理推廣到了更一般的非遞歸可枚舉理論上，但其推廣工作并不十分充分。下文第3 節(jié)會對此進行清晰回顧，并就其關鍵定理給出更簡潔易讀的新證明，同時額外證明2 組結果。

關于推廣的哥德爾第二不完全性定理，2018 年，我和Seraji 在[3]中進行了更一般的推廣，但這部分工作也不充分。下文第4 節(jié)會對此進行簡單回顧，并就其關鍵定理給出可讀性更強的新證明，同時額外證明2 組結果。為了對哥德爾不完全性定理進行更充分的推廣，下文第2 節(jié)會將哥德爾不完全性定理涉及的一致性、語法完全性、ω-一致性、相對于N的可靠性、相對于N的完全性、可定義性等元理論性質推廣成更一般的形式，并對其性質進行深入研究。

第4 節(jié)所證推廣的哥德爾第二不完全性定理都是有關Γ-可靠性的，而哥德爾第二不完全性定理卻是涉及一致性的，那么是否存在涉及一致性的推廣的哥德爾第二不完全性定理？下文第5 節(jié)將著重研究這個問題，并給出2 組可證自身一致性的理論。

哥德爾不完全性定理自被證明以來，在數學、哲學、計算機科學、物理學乃至宗教信仰等相關哲學問題上都產生了不同程度的影響。那么推廣的哥德爾第二不完全性定理被證明以后，會對這些哲學影響造成什么樣的改變？下文第6 節(jié)會基于推廣的哥德爾不完全性定理，從對形式化方法局限的反駁、對反機械主義的支持、對數學家地位的辯護等三個方面重新審視這些哲學影響。

現在給出一些基本的記號、概念和命題，詳見[9，19，23]。

記號1(算術語言、算術模型和算術片段).算術語言的非邏輯符號為S，+，×，0，其等詞符號為；無歧義的情況下，既用n表示閉項Sn0，也用n表示某個自然數；x≤y被定義為?z(z+x?y)；關于皮亞諾算術PA 和羅賓森算術Q的公理，詳見[19，第106 和234 頁]；N=(N，S，+，×，≤，0)是標準算術模型；

引理1.設m，n ∈N。

定理4(Σ1-完全性).設T是包含Q 的理論。任給Σ1語句?，如果N??，那么T ??。

記號2(語法的算術化).是?的哥德爾編碼；公式caxmT(x)意為“x是有窮個T公理的合取”，而且caxmT(x)∈Σn當且僅當axmT(x)∈Σn；pf(y，x)是意為“在只有邏輯有效式作為公理的公理系統(tǒng)中y是x的證明”的?0公式；pbT意為“x在T中是可證的”；?(x)是由x解碼后前綴?得到的公式；Σn公式Σn-true(x)和Πn公式Πn-true(x)在N中分別定義{是Σn語句 且}和{是Πn語句 且}（詳見[9，Corollary 1.76]）。

引理2(不動點).設T是包含Q 的理論，?(x)是只含有自由變元x的公式。則存在某個語句ρ使得。其中ρ稱為?(x)的不動點。

定義3.設T是理論，Γ 是公式集。稱Γ 是遞歸的，如果是遞歸的；稱Γ 是遞歸可枚舉的，如果是遞歸可枚舉的，否則稱Γ 是非遞歸可枚舉的；稱T是可公理化的，如果存在某個語句集Γ 使得T={? | ?是語句且Γ??}；稱T是遞歸可公理化的，如果存在某個遞歸的語句集Γ 使得T={?|?是語句 且Γ??}。

2 推廣的元理論性質

在哥德爾–羅瑟第一不完全性定理2 和哥德爾第二不完全性定理3 中，都要求理論T是一致的，如下的Γ-一致性便是一致性的推廣。

定義4(Γ-一致性).設T是理論，Γ 是一個語句集。稱T是Γ-一致的，如果T+Γ 是一致的；否則，稱T不是Γ-一致的。

哥德爾–羅瑟第一不完全性定理2 中的“不完全”是如下語法意義上的不完全。

定義5(完全性).設T是理論。稱T是（語法）完全的，如果任給語句?都有或或；否則，稱T是（語法）不完全的。

如哥德爾–羅瑟第一不完全性定理2 所述，使得理論T不完全的語句是Π1的。為方便說明使得理論T不完全的語句的復雜度，定義如下概念。

定義6(Γ-決定性).設T是理論，Γ 是一個語句集。稱T是Γ-決定的，如果任給語句? ∈Γ 都有或或T ???；否則，稱T不是Γ-決定的。

注1.哥德爾–羅瑟第一不完全性定理2 中的理論T不是Π1-決定的。

引理3.設T是理論。

(1) 如果T是Σn+1-決定的，那么T是Σn-決定的且Πn-決定的；

(2) 如果T是Πn+1-決定的，那么T是Σn-決定的且Πn-決定的；

(3)T是Σn-決定的當且僅當T是Πn-決定的；

(4) 如果T是完全的，那么T是Σn-決定的且Πn-決定的。

在哥德爾第一不完全性定理1 中，要求理論T是ω-一致的：稱T是ω-一致的，如果不存在公式?使得：(1)對某個ψ(x)有?=?xψ(x)，(2)T ??xψ(x)，(3) 任給m ∈N 都有T ??ψ(m)。實際上，由于使得理論T不完全的語句是Π1的，這個條件可以被弱化成：不存在? ∈Σ1使得上述三個條件都成立。G.Kreisel 稱這個條件為1-一致性（[13]），即如下n-一致性的特殊情形。

定義7(n-一致性).設T是理論，n ∈N。稱T是n-一致的，如果不存在? ∈Σn使得：(1)對某個ψ(x)有?=?xψ(x)，(2)T ??xψ(x)，(3)任給m ∈N 都有T ??ψ(m)；否則稱T不是n-一致的。

引理4.設n>0 且T是理論。

(1) 如果T是n-一致的，那么T是一致的；

(2) 如果T是(n+1)-一致的，那么T是n-一致的；

(3) 如果T是ω-一致的，那么T是n-一致的且一致的。

注2.引理4 說明，ω-一致性是一致性的推廣，而n-一致性是ω-一致性和一致性的推廣。

任給?，如果PA??都有N??。為方便表述類似于PA 的這種元理論性質，引入以下概念：

定義8(相對于N的可靠性).設T是理論。稱T（相對于N）是可靠的，如果，任給語句?如果T ??則N??；否則，稱T（相對于N）是不可靠的。

類似地，相對于N的可靠性也可以進行推廣。

定義9(相對于N的Γ-可靠性).設T是理論，Γ 是一個語句集。稱T（相對于N）是Γ-可靠的，如果，任給語句? ∈Γ 如果T ??則N??；否則，稱T（相對于N）是Γ-不可靠的。

引理5.設T是理論。

(1) 如果T是Σn+1-可靠的，那么T是Σn-可靠的且Πn-可靠的；

(2) 如果T是Πn+1-可靠的，那么T是Σn-可靠的且Πn-可靠的；

(3) 如果T是Σn-可靠的，那么T是Πn+1-可靠的，從而也是Πn-可靠的。

(4) 如果T是可靠的，那么T是Σn-可靠的且Πn-可靠的。

證明.只證(3)。假設? ∈Πn+1滿足：對某個θ ∈Σn有?=?xθ(x) 并且T ??。則任給m ∈N 都有T ?θ(m)。再由Σn-可靠性可知，任給m ∈N 都有N?θ(m)。因此N??xθ(x)，即N??。

從哥德爾–羅瑟第一不完全性定理2 和哥德爾第二不完全性定理3 的表述上看，相對于N的Γ-可靠性看似是無關緊要的概念，實際上與Γ-一致性、n-一致性聯系緊密。

引理6.設T是理論。

(1)T是可靠的當且僅當T是Th(N)-一致的當且僅當N?T；

(2)T是Σn-可靠的當且T是Πn(N)-一致的；

(3)T是Πn-可靠的當且僅當T是Σn(N)-一致的。

證明.只證(2)。(?)根據緊致性只需證：任給? ∈Πn(N)，T+?是可滿足的。令? ∈Πn(N)，則?? ∈Σn且。根據Σn-可靠性可知，因此T+?是一致的，亦即可滿足的。

(?)假定T不是Σn-可靠的，則存在某個? ∈Σn使得T ??且。于是N???且?? ∈Πn，從而T+Πn(N)???。而由T ??可知T+Πn(N)??，這與T是Πn(N)-一致的矛盾。

引理7.設T是理論。

(1) 任給n ∈N，如果T是Σn-可靠的，那么T是n-一致的；

(2) 任給n ≥3，如果T是n-一致的，那么T不一定是Σn-可靠的；

(3) 任給n ∈N，如果T是n-一致的且Σn?1-完全的，那么T是Σn-可靠的。進一步令T包含Q，則

(4)T是Σ2-可靠的當且僅當T是2-一致的；

(5)T是Σ1-可靠的當且僅當T是1-一致的；

(6)T是Σ0-可靠的當且僅當T是一致的。

證明.(1)設對某個ψ ∈Πn?1有?=?xψ(x)∈Σn且T ??xψ。根據Σn-可靠性可知N??xψ(x)，從而對某個m ∈N 有N?ψ(m)，所以(m)。又由于?ψ(m)∈Σn?1且T是Σn-可靠的，因此(m)。

(2)實際上，有更強的結論：ω-一致性推不出Σ3-可靠性（[11，Theorem 19]）。

(3)假設? ∈Σn滿足：對某個θ ∈Πn?1有?=?xθ(x)且(x)。根據n-一致性可知：對某個m ∈N 有(m)。又由于?θ(m)∈Σn?1，因而根據Σn?1-完全性可得(m)，即N?θ(m)。因此N?xθ(x)。

(4)–(6)由(1)可知只需證(?)，而這由(3)和T的Σ1-完全性易得。

注3.根據引理6 和7(6)可知，Γ-可靠性也是一致性的推廣。

在哥德爾第二不完全性定理3 中，要求T是一致的，結論是T不能證明“T是一致的”，因而T是不完全的。又因為“T是一致的”可以轉化為N中的真語句，所以這里“不完全”的含義實際上是如下意義的語義不完全。

定義10(相對于N的語義完全性).設T是理論。稱T（相對于N）是語義完全的，如果，任給語句?如果N??都有T ??；否則，稱T（相對于N）是語義不完全的。

類似地，相對于N的完全性也可以進行推廣。

定義11(相對于N的Γ-語義完全性).設T是理論，Γ 是一個語句集。稱T（相對于N）是Γ-（語義）完全的，如果，任給語句? ∈Γ 如果N??都有T ??；否則，稱T（相對于N）是Γ-（語義）不完全的。

引理8.設T是理論。

(1) 如果T是Σn+1-完全的，那么T是Σn-完全的且Πn-完全的；

(2) 如果T是Πn+1-完全的，那么T是Πn-完全的且Σn-完全的；

(3) 如果T是Σn-完全的，那么T不一定是Πn-完全的；

(4) 如果T是Πn-完全的，那么T是Σn+1-完全的，因而也是Σn-完全的；

(5) 如果T是語義完全的，那么T是Σn-完全的且Πn-完全的。

證明.只證(3)和(4)。(3)Q 是Σ1-完全的但不是Π1-完全的（由哥德爾第一不完全性定理1 可知）。

(4)假設? ∈Σn+1滿足：對某個θ ∈Πn有?=?xθ(x)且N??。于是對某個m ∈N 有N?θ(m)，再由Πn-完全性有T ?θ(m)，因此T ??。

在哥德爾–羅瑟第一不完全性定理2 和哥德爾第二不完全性定理3 中，都要求理論T是遞歸可枚舉的。仔細檢查兩個定理的證明過程不難發(fā)現，遞歸可枚舉條件的主要作用是使得證明和可證性概念可以用算術語言表達。而把兩個不完全性定理推廣到非遞歸可枚舉理論上，為保證證明和可證性概念可以用算術語言表達，就要求理論T必須是可定義的：

定義12(可定義性).設T是被語句集? 公理化的理論。稱T是可定義的，如果存在某個公式axmT(x)使得?=且?是語句}。

考慮到理論T公理集的復雜度，自然有如下推廣的Γ-可定義性概念。

定義13(Γ-可定義性).設T是被語句集? 公理化的理論，Γ 是公式集。稱T是Γ-可定義的，如果存在某個公式axmT(x)∈Γ 使得?={? | N?axmT且?是語句}。

引理9.設T是一個理論。

(1) 如果T是Σn-可定義的，那么T是Σn+1-可定義的且Πn+1-可定義的；

(2) 如果T是Πn-可定義的，那么T是Σn+1-可定義的且Πn+1-可定義的；

(3) 如果T是Σn+1-可定義的，那么T是Πn-可定義的；

(4)T是遞歸可枚舉的當且僅當T是Σ0-可定義的當且僅當T是Σ1-可定義的。

證明.(1)和(2)顯然成立；關于(3)，詳見[20，Lemma 2.7]；關于(4)，由(3)可得“Σ1-可定義性?Σ0-可定義性”，“Σ0-可定義性?遞歸可枚舉性”是平凡成立的。而由如下斷言易得“遞歸可枚舉性?Σ1-可定義性：如果T是遞歸可枚舉的，那么T被某個遞歸集公理化（[4]）。

注4.引理9(4)說明，Γ-可定義性是遞歸可枚舉性的推廣。

為便于看出哥德爾不完全性定理是推廣的哥德爾不完全性定理的特殊情形，本節(jié)用以上推廣的元理論性質對哥德爾不完全性定理進行重述。根據引理9(4)和引理7(5)，哥德爾第一不完全性定理1 可以重述如下：

推論1.設T是包含Q 的理論。

(1) 如果T是Σ1-可定義的、1-一致的，那么T不是Π1-決定的。

(2) 如果T是Σ1-可定義的、Σ1-可靠的，那么T不是Π1-決定的。

由引理9(4)和引理7(6)，哥德爾–羅瑟第一不完全性定理2 可重述如下：

定理5.如果T是包含Q 的、Σ1-可定義的、Σ0-可靠的理論，那么T不是Π1-決定的。

由定理5，引理6 和引理7，哥德爾–羅瑟第一不完全性定理2 可重述如下：

推論2.設T是包含Q 的理論。

(1) 如果T是Σ1-可定義的、Π1-可靠的，那么T不是Π1-決定的。

(2) 如果T是Σ1-可定義的、可靠的，那么T不是Π1-決定的。

由引理9(4)和引理7(6)，哥德爾第二不完全性定理3 可重述如下。關于Σ0-Sound(T)和Π0-Sound(T)，參見下文。

推論3.設T是包含Q 的理論。

(1) 如果T是Σ1-可定義的、Σ0-可靠的，那么Σ0-Sound(T)。

(2) 如果T是Σ1-可定義的、Π0-可靠的，那么Π0-Sound(T)。

(3) 如果T是Π0-可定義的、Σ0-可靠的，那么Σ0-Sound(T)。

(4) 如果T是Π0-可定義的、Π0-可靠的，那么Π0-Sound(T)。

3 推廣的哥德爾第一不完全性定理

Salehi 和Seraji 首先將推論2(2)推廣到了非遞歸可枚舉理論上。

定理6([20，Theorem 2.1]).如果T是包含Q 的、Σn-可定義的、可靠的理論，那么T不是Πn-決定的。

不難看出，定理6 對于Πn-可定義的理論也成立。

推論4.如果T是包含Q 的、Πn-可定義的、可靠的理論，那么T不是Πn+1-決定的。

Salehi 和Seraji 進一步把條件“可靠性”加強為Πn-可定義理論的Σn-可靠性或Σn-可定義理論的Σn?1-可靠性。這里給出新證明，與原證明相比，該證明更簡潔易讀，并且可額外證明N?ρ，而前者不能。

定理7([20，Theorem 2.4]).如果T是包含Q 的、Πn-可定義的、Σn-可靠的理論，那么T不是Πn+1-決定的。

證明.令

再令T?=T+Πn(N)，則T?是Πn-完全的、Σn+1-完全的，且根據Σn-可靠性是一致的。先證兩個斷言。

斷言1.如果T ?δ，那么。

斷言的證明.假定T ?δ。則對某個m ∈N 有。又由于且T?是Πn-完全的，因而；根據T的一致性可知，因而任給k ∈N 都有。又由于Σn且T?是Σn+1-完全的，因而任給k ∈N 都有；再根據引理1(1)可得。因此T??rpbT。

斷言2.如果T ??δ，那么T???rpbT。

斷言的證明.假定T ??δ。則對某個m ∈N 有。又由于∈Πn且T?是Πn-完全的，因而?，F在只需證

給定x。

現在回到定理的證明。令ρ為?rpbT(y)的不動點，則

根據不動點引理中不動點的構造過程可知ρ ∈Πn+1?，F在只需證ρ獨立于T：如果T ?ρ，那么根據斷言1 可得，但根據(2)卻有T??，與T?的一致性矛盾，因而；如果T ??ρ，那么根據斷言2 可得，但根據(2)卻有，也與T?的一致性矛盾，因而。

可以進一步證明N?ρ。倘若，則N??ρ，又根據T?的Σn+1-完全性和?ρ ∈Σn+1可得T???ρ，矛盾。

推論5([20，Corollary 2.8 和2.9]).設n>1，T是包含Q 的理論。

(1) 如果T是Σn-可定義的、Σn?1-可靠的，那么T不是Πn-決定的；

(2) 如果T是Σn-可定義的、Σn-可靠的，那么T不是Πn-決定的。

條件“可靠性”也可以被加強為Πn-可定義理論的Πn+1-可靠性或Σn-可定義理論的Πn-可靠性。

定理8.如果T是包含Q 的、Πn-可定義的、Πn+1-可靠的理論，那么T不是Πn+1-決定的。

證明.根據引理5 可得。

推論6.如果T是包含Q 的、Σn-可定義的、Πn-可靠的理論，那么T不是Πn-決定的。

證明.根據引理9 和定理8 可得。

Salehi 和Seraji 進一步把條件Σn-可靠性加強為Πn-可定義理論的n-一致性或Σn-可定義理論的(n ?1)-一致性。

定理9([20，Corollary 2.6]).如果T是包含Q 的、Πn-可定義的、n-一致的理論，那么T不是Πn+1-決定的。

推論7.設n>1，T是包含Q 的理論。

(1)（[20，Corollary 2.11]）如果T是Σn-可定義的、(n ?1)-一致的，那么T不是Πn-決定的；

(2) 如果T是Σn-可定義的、n-一致的，那么T不是Πn-決定的；

(3) 如果T是Πn?1-可定義的、ω-一致的，那么T不是Πn-決定的；

(4) 如果T是Πn?1-可定義的、n-一致的，那么T不是Πn-決定的。

證明.(2)，(3)和(4)根據定理9 和引理4 可得。

Salehi 和Seraji 還證明n-一致性不能被加強為一致性。據此，還可以證明上述推廣的哥德爾第一不完全性定理在推論8 的意義上是最優(yōu)的。

定理10([20，Theorem 3.1]).如果T是包含Q 的、Σn+2-可定義的、一致的理論，那么T可能是完全的。

推論8([20，Corollary 3.4，無(2)和(5)]).設n>1，T是包含Q 的理論。

(1) 如果T是Σn-可定義的、Σn?2-可靠的，那么T可能是Πn-決定的；

(2) 如果T是Σn-可定義的、Πn?1-可靠的，那么T可能是Πn-決定的；

(3) 如果T是Σn-可定義的、(n ?2)-一致的，那么T可能是Πn-決定的；

(4) 如果T是Πn?1-可定義的、Σn?2-可靠的，那么T可能是Πn-決定的；

(5) 如果T是Πn?1-可定義的、Πn?1-可靠的，那么T可能是Πn-決定的；

(6) 如果T是Πn?1-可定義的、(n ?2)-一致的，那么T可能是Πn-決定的。

4 推廣的哥德爾第二不完全性定理

定義14.設T是包含PA 的、可定義的理論。T的一致性可被形式化為：

由于Σn-可靠性等價于Πn(N)-一致性，所以Σn-可靠性可被形式化為：

其中，Πn-true(x)定義公式集Πn(N)。類似地，可將Πn-可靠性形式化。

注5.雖然Σn-可靠性與Πn(N)-一致性等價，但PA 不能證明Σn-可靠性與Πn(N)-一致性等價。

形式化完Γ-可靠性之后，我和Seraji 證明了推廣的哥德爾第二不完全性定理11，該結果已發(fā)表（[3，Theorem 1]），但這里給出一種可讀性更強的新證明。

引理10.設T是包含PA 的、可定義的理論。則任給公式?都有

證明.在PA+Σn-Sound(T) 內推理：用反證法。不妨假設?Σn-Sound(T+?)且?Σn-Sound(T+??)，則存在s′，t′，u′，s′′，t′′，u′′使得

則對s=s′∧s′′，t=t′∧t′′和某個u有，即?Σn-Sound(T)，矛盾！

引理11([1，Proposition 2.11]).設T是包含PA 的、可定義的理論。則任給公式? ∈Σn+1，都有

定理11.如果T是包含PA 的、Πn-可定義的、Σn-可靠的理論，那么Σn-Sound(T)。

證明.令T?=T+Πn(N)，則根據T的Σn-可靠性可知：T?是一致的且Σn+1-完全的（亦即Πn-完全的）?，F在對如下定義的公式Σn-Sound(T+?(x))運用不動點引理：

則存在一個不動點ρ ∈Πn+1使得

證明最終結論之前，先證三個斷言。

斷言3.T?ρ。

斷言的證明.假如T??ρ，則存在s，t，u ∈N 使得caxmT(s)∧Πn-true(t)∧是一個真的Σn+1語句。由于所有真的Σn+1-語句在Πn(N)?T?中可證，所以T???Σn-Sound(T+?ρ)，從而T???ρ，這與T?的一致性矛盾！

斷言4.T??Σn-Sound(T+ρ)→ρ。

斷言的證明.根據引理11 可知，任給? ∈Σn+1都有

因而

又由于N??x(axmPA(x)→axmT(x))（T是PA 的擴張）和?x(axmPA(x)→axmT(x))∈Πn，因而根據T?的Πn-完全性可得

斷言5.T?+Σn-Sound(T)?ρ。

斷言的證明.假如T?+Σn-Sound(T)，則根據(3)可得

根據斷言4 可得

根據引理10 可得

綜合(6)、(7)和(8)可得T?+Σn-Sound(T)?ρ，矛盾，所以原結論成立。

回到定理的證明。不妨假設T ?Σn-Sound(T)。則T??Σn-Sound(T)，因而根據斷言5 可得T??ρ，與斷言3 矛盾。因此Σn-Sound(T)。

推論9([3，Theorem 2]).如果T是包含PA 的、Σn+1-可定義的、Σn-可靠的理論，那么Σn-Sound(T)。

實際上，按照證明定理11 的證明方法也可以證明Πn-可靠性相關的情形。

定理12.如果T是包含PA 的、Πn-可定義的、Πn+1-可靠的理論，那么Πn+1-Sound(T)。

推論10.如果T是包含PA 的、Σn+1-可定義的、Πn+1-可靠的理論，那么Πn+1-Sound(T)。

證明.根據定理12 和如下事實：任給Σn+1-可定義的理論T，都有一個與之等價的理論T′使得PA?Πn+1-Sound(T)?Πn+1-Sound(T′)。

上述推廣的哥德爾第二不完全性定理在如下結果的意義上是最優(yōu)的。定理13 的證明方法也適用于定理14。

定理13([3，Theorem 3]).任給n >0，都存在一個包含PA 的、?n+1-可定義的、Σn?1-可靠的理論T 使得T?Σn?1-Sound(T)。

推論11.任給n >0，都存在一個包含PA 的、Πn-可定義的、Σn?1-可靠的理論T 使得T?Σn?1-Sound(T)。

定理14.任給n>0，都存在一個包含PA 的、?n+1-可定義的、Πn-可靠的理論S 使得S?Πn-Sound(S)。

推論12.任給n>0，都存在一個包含PA 的、Πn-可定義的、Πn-可靠的理論S 使得T?Πn-Sound(S)。

5 非遞歸可枚舉理論與形式化的一致性

上述推廣的哥德爾第二不完全性定理都是有關Γ-可靠性的，那么涉及一致性的推廣的哥德爾第二不完全性定理是否成立？不妨假設成立，比較自然的證明思路是仿照哥德爾第二不完全性定理的證明思路：先證明滿足一定條件的理論T滿足三個可證條性條件，再證明它不能證明自身一致性。

定義15 (可證性關系).設T是可定義的理論，?是任意公式。令

定義16(可證性條件).設T是可定義的理論，?，ψ是任意公式。三個可證性條件為：

現在考察非遞歸可枚舉理論T需要滿足的條件，除了Σn-可定義性之外，不妨假設其它條件與哥德爾第二不完全性定理相同，即T是包含PA 的、Σn-可定義的、一致的理論。研究發(fā)現，這樣的理論并不一定滿足所有的可證性條件：

引理12.設n>1。如果T是包含PA 的、Σn-可定義的、一致的理論，那么T不一定滿足D1。

證明.構造反例：給定公式?滿足T ??，則對某個m ∈N 有，因而，即。注意，，因此只需要令。

因此需要強化非遞歸可枚舉理論T需要滿足的條件。鑒于引理12，要求T是Σn-完全的便是一個可行的選擇。經過研究發(fā)現，此時的理論T滿足所有的可證性條件。

引理13.如果T是包含PA 的、Σn-可定義的、一致的、Σn-完全的理論，那么T滿足D1。

證明.仿照[23，引理10.1.2]的證明。

引理14.如果T是包含PA 的、Σn-可定義的、一致的理論，那么T滿足D2。

證明.仿照[23，第10.2 節(jié)]中遞歸可枚舉理論滿足D2的證明。

引理15.如果T是包含PA 的、Σn-可定義的、一致的、Σn-完全的理論，那么T滿足D3。

證明.仿照[23，第10.3 節(jié)]中遞歸可枚舉理論滿足D3的證明。

把引理13、14、15 中的“Σn-可定義的”改為“Πn?1-可定義的”，或把“Σn-完全的”改為“Πn?1-完全的”，類似地可以證明其余3 組結論。

因此對于滿足一定條件的非遞歸可枚舉理論來說，改編哥德爾第二不完全性定理的證明即可得知它也不能證明自身的一致性，這是一種證明方法。下面給出第二種證明方法，即，將這些結論作為第4 節(jié)所證推廣的哥德爾第二不完全性定理的直接推論。

推論13.如果T是包含PA 的、Πn-可定義的、一致的、Πn-完全的理論，那么Con(T)。

證明.顯然T=T+Πn(N)，因而T是Σn-可靠的。由于T是一致的，根據定理11 可得Σn-Sound(T)。又由于Σn-Sound(T)Con(T+Πn(N))=Con(T)，因此Con(T)。

推論14.如果T是包含PA 的、Σn+1-可定義的、一致的、Πn-完全的理論，那么Con(T)。

證明.將推論13 證明中的定理11 改為定理9 即可。

推論15.如果T是包含PA 的、Πn-可定義的、一致的、Σn+1-完全的理論，那么Con(T)。

證明.根據推論13 和引理8 可得。

推論16.如果T是包含PA 的、Σn+1-可定義的、一致的、Σn+1-完全的理論，那么Con(T)。

證明.根據推論14 和引理8 可得。

如下結果表明了上述涉及一致性的推廣的哥德爾第二不完全性定理是最優(yōu)的，同時給出了兩組可證自身一致性的理論。

推論17.任給n>0，都存在一個包含PA 的、?n+1-可定義的、Πn?1-完全的理論T 使得T?Con(T)。

證明.將所有公式枚舉為χ0，χ1，χ2，...，其中χ0=Con(T0)。如下遞歸地構造T：T0=PA+Πn?1(N)；如果Ti+χi是一致的，令Ti+1=Ti+χi，否則令Ti+1=Ti+?χi；T=∪i∈NTi。在[3，Theorem 3]中，證明了T 是?n+1-可定義的、Σn?1-可靠的理論，同時T?Σn?1-Sound(T)。又因為Πn?1(N)?T，因此T 是Πn?1-完全的，而且由Σn?1-Sound(T) ?Con(T+Πn?1(N))=Con(T)可得T?Con(T)。

推論18.任給n>0，都存在一個包含PA 的、?n+1-可定義的、Σn-完全的理論S 使得S?Con(S)。

證明.將推論17 證明中的Πn?1(N)改為Σn(N)即可。

6 推廣的哥德爾不完全性定理產生的哲學影響

6.1 對形式化方法局限的反駁

所謂形式化方法是現代一階邏輯意義下的一種方法，其具體過程為：給定一個公理化的理論T（這里并不要求公理集是遞歸的），如皮亞諾算術；建立一個包括邏輯符號和非邏輯符號的一階語言，非邏輯符號應當與理論T中的某些基本概念對應起來，如應備有符號以分別表示加法函數、減法函數、小于關系、0、1、2、……等等；建立語法，明確什么是項和公式；建立語義，準確定義什么是真；建立一階邏輯公理系統(tǒng)，包括公理集和推理規(guī)則；在一階邏輯公理系統(tǒng)中定義什么是證明；把T的公理加入一階邏輯公理系統(tǒng)的公理集。

在哥德爾不完全性定理被證明后，不少學者將遞歸可枚舉理論的不完全性現象歸結為形式化方法的局限，比如J.W.Dawson、王浩（H.Wang）、H.-D.Ebbinghaus 等人。Dawson 在1999 年發(fā)表了一篇文章，除了講述哥德爾的生平，還重點談及哥德爾完全性定理和不完全性定理。他將這篇文章的標題擬為“G?del and the limits of logic”（[5]），其中“the limits of logic”指的便是形式化方法的局限；王浩曾在其專著《邏輯之旅》中說（[24，第90 頁]）：

這些結果包括(1)他對謂詞邏輯完全性的證明（1929 年）；(2)對任何數學形式系統(tǒng)構造一個在該系統(tǒng)中不可判定的數論問題的方法（1930 年）；(3)任何古典數學形式系統(tǒng)的一致性在同一系統(tǒng)中不可證的證明（1930 年）……完全性定理(1)可被視為一個成功的結論，肯定了我們對哥德爾稱之為“有窮心靈的邏輯”有了令人滿意的精確描述。這一定理也對不完全性定理(2)和(3)作了補充，從而證明機械化和具體直覺有作用但也有局限性……

其中的(2)指的是哥德爾第一不完全性定理1，(3)指的是哥德爾第二不完全性定理3，而“機械化”則與“形式化”含義相同；Ebbinghaus 等人曾在其編著《數理邏輯》中說（[6，第186 頁]）：

Intuitively this means that there is no decidable consistent system of axioms for mathematics which，for every mathematical statement，allows us to either prove or disprove it.In this fact an inherent limitation of the axiomatic method is manifested.

其中的“axiomatic method”即公理化方法，此處含義與形式化方法相同。不僅如此，其第10 章更直接以“Limitations of the Formal Method”為題（[6，第151頁]）。顯然，Ebbinghaus 等人認為不完全性現象是形式化方法本身固有的局限。

在本文作者看來，將不完全性現象歸結為形式化方法的局限是不合適的。下面以第一不完全性定理為例對此進行論證，第二不完全性定理的情形與此類似。如定理5 所言，足夠強的、一致的遞歸可枚舉理論是不完全的。雖然如推論5(1)所言，足夠強的、一致的非遞歸可枚舉理論滿足一定條件也是不完全的，但是改變這些條件，足夠強的、一致的非遞歸可枚舉理論卻可以是完全的：無論是可定義的——如定理9 中的理論，還是不可定義的——如理論Th(N)。換言之，之所以出現不完全性現象，是對理論性質的要求使然，而非形式化方法的問題。因此，不完全性現象是偶然而非必然的，從而也就不能將其歸結為形式化方法的局限。

6.2 對反機械主義的支持

作為機械主義（mechanism）的代表人物，T.Hobbes（見[10]）、J.O.de La Mettrie（見[14]）等人認為人的心靈（mind）用神經系統(tǒng)的物理操作足以解釋，因而是一臺機器。在某種程度上可以稱為某種機械主義的計算主義（computabilism），在這方面更進一步，認為大腦（brain）和心靈基本像一臺計算機一樣工作（見[24，第231 頁]）。而作為反機械主義（antimachanism）的代表人物，N.Malcolm（見[16]）、D.Chalmers（見[2]）等人則基于與心靈、意識和自由意志相關的常識提出了反駁：心靈哲學層面，他們認為非意識部分不足以解釋意識現象；形而上學層面，他們認為機械主義會導致有關人類行動的決定論，而這與通常認為的“人是有自由意志的動物”相矛盾。

哥德爾不完全性定理在被證明以后成為了反駁機械主義尤其是計算主義的有力武器。利用哥德爾不完全性定理進行反駁的有哥德爾、J.R.Lucas、R.Penrose 等人2Lucas 的論證（[15]）與哥德爾的論證相似，這里只論述哥德爾的論證；而Penrose 的論證雖說也與哥德爾的論證有相似之處，但差別較大且與第6.3 節(jié)內容聯系密切，故將其放在第6.3 節(jié)。。哥德爾認為大腦在某種程度上的確是一臺機器（計算機）（[24，第231 頁]），但卻不認為心靈是一臺機器，并認為心靈勝過所有的機器，他借助哥德爾第二不完全性定理和理性樂觀主義對此進行了論證3詳見[22，第324–326 頁]或[24，第231–241 和416–419 頁]，該論證過程始于1951 年的[7]，終于1972 年的[22，第324–326 頁]。為使哥德爾的論述看上去是一個完整的論證，本文作者將其按如下方式排放，同時為增強可讀性還添加了四處［］內的注釋。：

心靈不能將它所有的數學直覺都形式化（或機械化）。這就是說，如果它成功地形式化了其中一些直覺，那么這件事實本身又生出了新的直覺性知識，比如這個形式化的一致性。［這里運用了與哥德爾第二不完全性定理3等價的論斷：如果一臺足夠強的定理證明機器是一致的，那么它不能證明表達其自身一致性的語句］這可以稱為數學的“不可完全性”。另一方面，基于迄今已證明的結果，有可能存在（甚至可以在經驗中發(fā)現）一臺定理證明機器，它事實上等價于數學直覺，但不能被證明如此，甚至不能證明對有窮數論它只產生正確的定理。

［鑒于上述考察，我們可以知道］或者心靈勝過所有的機器（說得確切一些，它比任何機器都能判定更多的數論問題），或者存在一些心靈不能判定的數論問題。（不排除二者都真）

如果這［存在一些心靈不能判定的數論問題］是真的，那么這意味著人類理性毫無道理可言，因為它出了它不能回答的問題，而又斷然聲稱只有理性才能回答它們。這樣一來，人類理性非但極不完美，而且在種意義上甚至是不一致的，與下面的事實構成尖銳的矛盾：那些得到了系統(tǒng)而完全的發(fā)展的數學分支（比如，一次與二次丟番圖方程理論—后者有兩個未知量）顯示出驚人程度的優(yōu)美與完滿。在這些領域里，通過全然出人意料的規(guī)律與過程（如二次互反律、歐幾里德算法、連分數等等），我們獲得了解決所有相關問題的手段，不僅如此，這些手段還以最優(yōu)美和純粹可行的方式解決問題（例如，由簡單的表達式產生所有的解）。這些事實似乎核證了可以稱之為“理性樂觀主義”的觀點。

［因此，心靈勝過所有的機器。］

類似地，推廣的哥德爾第二不完全性定理，如定理11，也可以為哥德爾“心靈勝過所有的機器”的反機械主義主張?zhí)峁┲С郑湔撟C與之類似4與之不同的是：遞歸可枚舉理論因其公理集是遞歸的，可以毫無問題地形式化為公理系統(tǒng)，從而等價于一臺足夠強的定理證明機器；但非遞歸可枚舉理論因其公理集是非遞歸可枚舉的，無法形式化為公理系統(tǒng)，但因其是可定義的，足夠強的定理證明機器至少可以“用算術語言談論”它。：如果心靈可以形式化為一臺足夠強的、可以談論非遞歸可枚理論的機器，那么根據推廣的哥德爾第二不完全性定理就會產生一個新的算術語句，如Σn-可靠性，該機器無法證明它從而也就“不知道”它是真的，但心靈知道它是真的；于是，或者心靈勝過所有的機器，或者存在一些心靈不能判定的算術語句；再根據理性樂觀主義，可以排除“存在一些心靈不能判定的算術語句”，因此心靈勝過所有的機器。

6.3 對數學家地位的辯護

同樣借助于哥德爾第二不完全性定理3，Penrose 先后在[17，18]中提出、論證并完善了對“數學洞察力（insight）不能被計算地（algorithmically）模仿”的反機械主義主張。他將數學洞察力定義為數學家生成數學命題和證明以及能夠理解彼此證明的方法。其具體論證如下5為增強可讀性，該論證以及下文兩個子論證的具體表述略有刪改。：

(1) 假如存在某個公理系統(tǒng)S 可以抓住數學洞察力所必需的思想。

(2) 那么，根據哥德爾第二不完全性定理，S 不能證明S 是一致的。

(3)［富有數學洞察力的］我們知道S 是一致的。

(4) 由于S 可以抓住我們的思想［數學洞察力所必需的思想］，所以S 可以證明S 是一致的。

(5) 矛盾！因此，不存在如此的公理系統(tǒng)。

如果(3)是可信的，那么上述論證將是非常可靠的。于是Penrose 分兩種情形論證了(3)：(a)我們知道S 抓住了我們的思想；(b)我們不知道S 抓住了我們的思想。關于第一種情形，其論證比較簡單：

(3a.1) 我們知道我們的思想是一致的。

(3a.2) 因此，如果我們知道S 抓住了我們的思想，那么我們便知道S 是一致的。

關于第二種情形，Penrose 在一定程度上求助了人類理性思維的可靠性：

(3b.1) 根據定義，S 由公理集和推理規(guī)則集組成。

(3b.2) 每個公理的有效性都可以被我們查證。

(3b.3) 并且，每個推理規(guī)則的有效性也可以被我們查證，不然人類的推理將會建立在無把握的推理規(guī)則之上，而這是難以置信的。

(3b.4) 由于我們知道每個公理和推理規(guī)則都是有效的，所以我們知道S 是一致的。

可以看到在這兩種情形的論證中，Penrose 的部分想法與哥德爾的理性樂觀主義有異曲同工之妙。

從Penrose 的“數學洞察力不能被計算地模仿”的反機械主義主張，我們可以更進一步：富有數學洞察力的數學家不可能被計算機所取代，因此數學家之所以為數學家的主體地位就難為計算機所撼動。這一整個論證過程是以哥德爾第二不完全性定理為基礎的，將其中的“公理系統(tǒng)S”替換為“一臺足夠強的定理證明機器”可以得到一個本質相同的論證，而這個替換后的論證可以如上小節(jié)內容一樣略經修改得到一個以推廣的哥德爾第二不完全性定理為基礎的新論證，從而為數學家的地位提供類似的辯護。

7 問 題

本文將哥德爾不完全性定理進行了充分的推廣，并基于這些推廣的哥德爾不完全性定理重新審視了哥德爾不完全性定理產生的哲學影響。與此同時，有兩個尚未解決但比較重要的問題需要指出以待進一步研究。第一個問題與推廣的哥德爾第二不完全性定理有關。推廣的哥德爾第一不完全性定理既有與Γ-可靠性相關的，也有與n-一致性相關的。而所證推廣的哥德爾第二不完全性定理卻全是與Γ-可靠性相關的，那么是否也有與n-一致性相關的推廣的哥德爾第二不完全性定理？

問題1.設T是包含PA 的、Σm+1-可定義的（Πm-可定義的）的理論。如果T是n-一致的，那么Con(T)是否成立？如果成立，那么m，n差值又可以是多少？

第二個問題與可證自身一致性理論需要滿足的條件有關。第5 節(jié)定義的T 和S都是可證自身一致性的特殊理論，于是不禁要問：

問題2.如果一個理論可證自身一致性，那么對其需要滿足的充分條件有沒有一個更一般的刻劃？