哥德爾不完全性定理的推廣形式及其哲學(xué)影響

趙曉玉

1 引言

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

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

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

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

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

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

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

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

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

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

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

現(xiàn)在給出一些基本的記號(hào)、概念和命題，詳見[9，19，23]。

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

引理1.設(shè)m，n ∈N。

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

記號(hào)2(語法的算術(shù)化).是?的哥德爾編碼；公式caxmT(x)意為“x是有窮個(gè)T公理的合取”，而且caxmT(x)∈Σn當(dāng)且僅當(dāng)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(不動(dòng)點(diǎn)).設(shè)T是包含Q 的理論，?(x)是只含有自由變?cè)獂的公式。則存在某個(gè)語句ρ使得。其中ρ稱為?(x)的不動(dòng)點(diǎn)。

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

2 推廣的元理論性質(zhì)

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

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

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

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

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

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

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

引理3.設(shè)T是理論。

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

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

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

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

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

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

引理4.設(shè)n>0 且T是理論。

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

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

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

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

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

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

類似地，相對(duì)于N的可靠性也可以進(jìn)行推廣。

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

引理5.設(shè)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)。假設(shè)? ∈Πn+1滿足：對(duì)某個(gè)θ ∈Σn有?=?xθ(x) 并且T ??。則任給m ∈N 都有T ?θ(m)。再由Σn-可靠性可知，任給m ∈N 都有N?θ(m)。因此N??xθ(x)，即N??。

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

引理6.設(shè)T是理論。

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

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

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

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

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

引理7.設(shè)T是理論。

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

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

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

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

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

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

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

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

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

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

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

在哥德爾第二不完全性定理3 中，要求T是一致的，結(jié)論是T不能證明“T是一致的”，因而T是不完全的。又因?yàn)椤癟是一致的”可以轉(zhuǎn)化為N中的真語句，所以這里“不完全”的含義實(shí)際上是如下意義的語義不完全。

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

類似地，相對(duì)于N的完全性也可以進(jìn)行推廣。

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

引理8.設(shè)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)假設(shè)? ∈Σn+1滿足：對(duì)某個(gè)θ ∈Πn有?=?xθ(x)且N??。于是對(duì)某個(gè)m ∈N 有N?θ(m)，再由Πn-完全性有T ?θ(m)，因此T ??。

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

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

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

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

引理9.設(shè)T是一個(gè)理論。

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

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

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

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

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

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

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

推論1.設(shè)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.設(shè)T是包含Q 的理論。

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

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

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

推論3.設(shè)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 對(duì)于Πn-可定義的理論也成立。

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

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

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

證明.令

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

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

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

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

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

給定x。

現(xiàn)在回到定理的證明。令ρ為?rpbT(y)的不動(dòng)點(diǎn)，則

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

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

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

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

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

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

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

證明.根據(jù)引理5 可得。

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

證明.根據(jù)引理9 和定理8 可得。

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

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

推論7.設(shè)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)根據(jù)定理9 和引理4 可得。

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

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

推論8([20，Corollary 3.4，無(2)和(5)]).設(shè)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.設(shè)T是包含PA 的、可定義的理論。T的一致性可被形式化為：

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

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

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

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

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

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

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

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

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

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

則存在一個(gè)不動(dòng)點(diǎn)ρ ∈Πn+1使得

證明最終結(jié)論之前，先證三個(gè)斷言。

斷言3.T?ρ。

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

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

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

因而

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

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

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

根據(jù)斷言4 可得

根據(jù)引理10 可得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此需要強(qiáng)化非遞歸可枚舉理論T需要滿足的條件。鑒于引理12，要求T是Σn-完全的便是一個(gè)可行的選擇。經(jīng)過研究發(fā)現(xiàn)，此時(shí)的理論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 組結(jié)論。

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

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

證明.顯然T=T+Πn(N)，因而T是Σn-可靠的。由于T是一致的，根據(jù)定理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)。

證明.根據(jù)推論13 和引理8 可得。

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

證明.根據(jù)推論14 和引理8 可得。

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

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

證明.將所有公式枚舉為χ0，χ1，χ2，...，其中χ0=Con(T0)。如下遞歸地構(gòu)造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-可靠的理論，同時(shí)T?Σn?1-Sound(T)。又因?yàn)棣皀?1(N)?T，因此T 是Πn?1-完全的，而且由Σn?1-Sound(T) ?Con(T+Πn?1(N))=Con(T)可得T?Con(T)。

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

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

6 推廣的哥德爾不完全性定理產(chǎn)生的哲學(xué)影響

6.1 對(duì)形式化方法局限的反駁

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

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

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

其中的(2)指的是哥德爾第一不完全性定理1，(3)指的是哥德爾第二不完全性定理3，而“機(jī)械化”則與“形式化”含義相同；Ebbinghaus 等人曾在其編著《數(shù)理邏輯》中說（[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 等人認(rèn)為不完全性現(xiàn)象是形式化方法本身固有的局限。

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

6.2 對(duì)反機(jī)械主義的支持

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

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

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

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

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

［因此，心靈勝過所有的機(jī)器。］

類似地，推廣的哥德爾第二不完全性定理，如定理11，也可以為哥德爾“心靈勝過所有的機(jī)器”的反機(jī)械主義主張?zhí)峁┲С?，其論證與之類似4與之不同的是：遞歸可枚舉理論因其公理集是遞歸的，可以毫無問題地形式化為公理系統(tǒng)，從而等價(jià)于一臺(tái)足夠強(qiáng)的定理證明機(jī)器；但非遞歸可枚舉理論因其公理集是非遞歸可枚舉的，無法形式化為公理系統(tǒng)，但因其是可定義的，足夠強(qiáng)的定理證明機(jī)器至少可以“用算術(shù)語言談?wù)摗彼＃喝绻撵`可以形式化為一臺(tái)足夠強(qiáng)的、可以談?wù)摲沁f歸可枚理論的機(jī)器，那么根據(jù)推廣的哥德爾第二不完全性定理就會(huì)產(chǎn)生一個(gè)新的算術(shù)語句，如Σn-可靠性，該機(jī)器無法證明它從而也就“不知道”它是真的，但心靈知道它是真的；于是，或者心靈勝過所有的機(jī)器，或者存在一些心靈不能判定的算術(shù)語句；再根據(jù)理性樂觀主義，可以排除“存在一些心靈不能判定的算術(shù)語句”，因此心靈勝過所有的機(jī)器。

6.3 對(duì)數(shù)學(xué)家地位的辯護(hù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 問 題

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

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

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

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