理論的相對一致性

許滌非

理論的相對一致性

許滌非

證明理論的一致性有兩種基本方法:一是直接給出滿足理論的語義結(jié)構(gòu);二是從一種理論的一致性得到要證理論的一致性。相對化的方法屬于第二種方法,它可以從弱系統(tǒng)的一致性證明強(qiáng)系統(tǒng)的一致性。相對化證明理論的一致性實(shí)質(zhì)上是以某個理論為中介,間接地給出滿足理論 T的語義結(jié)構(gòu)。相對化的本質(zhì)是“保守性”的翻譯,而“保守性”翻譯恰是從弱系統(tǒng)證明強(qiáng)系統(tǒng)的關(guān)鍵。

理論;相對化;保守性;一致性

兩個一階理論T與T′的一致性可以有某種聯(lián)系。如果 T是不比 T′弱的理論(也就是從 T′可推出的東西都可以由 T推出),那么,T′如果能夠推出矛盾,則 T也能夠推出矛盾。所以,從較強(qiáng)的理論的一致性能夠得到較弱理論的一致性。本文的主要目的就是討論一種證明公式集一致性的方法——相對化,重點(diǎn)說明它背后的思想、證明思路以及應(yīng)用。

一、“一致性”概念

一致性是一個相對概念,都是相對某個系統(tǒng)而言的。常見的一致性有三種,分別是古典一致性、語法一致性和語義一致性。下面是其定義。

定義1.1 古典一致。如果在系統(tǒng)S中,從公式集推不出矛盾,則稱公式集Γ相對于 S是古典一致的,即:如果不存在公式α使得Γ├Sα且Γ├Sα,則稱Γ相對于S是古典一致的。

定義1.2 語法不一致,語法一致。如果公式集Γ在系統(tǒng)S中可以推出一切公式,則稱公式集Γ相對于S是語法不一致的。如果公式集Γ相對系統(tǒng)S不是語法不一致的,則稱公式集Γ相對系統(tǒng) S是語法一致的,即:如果存在α,使得并非Γ├Sα,則稱公式集Γ相對系統(tǒng)S是語法一致的。

定義1.3 語義一致。如果有滿足公式集Γ模型或者解釋,則稱公式集Γ是語義一致的。公式集Γ相對于系統(tǒng)S是語義一致的,也就是:存在S所屬語言的模型,使得任給Γ中的任意公式α都有M╞α。

需要注意的是,這里的“語義一致”與“廣義語義一致”是不同的。

定義1.4 廣義語義一致。在系統(tǒng)S中,對于任意公式集Γ,如果Γ├Sα,則Γ╞α,稱該系統(tǒng)廣義語義一致。

廣義語義一致是就某個邏輯系統(tǒng)而言的,是說任何公式集Γ的語法后承都是語義后承。語義一致是就某個公式集Γ而言的,說的是存在滿足某個公式集Γ的模型。一個邏輯系統(tǒng)是廣義語義一致的,不一定任一公式集Γ相對于該系統(tǒng)語義一致。如果這個公式集包含一對矛盾的公式,則自然不可滿足,但是此時仍然有:如果Γ├Sα,則Γ╞α。這就說明廣義語義一致與語義一致是不同的概念。

對于一階邏輯,古典一致性、語法一致性、語義一致性是等價的。下面是這個結(jié)果的說明。

結(jié)論1.5 古典一致性?語法一致性。

如果Γ語法不一致,則對任一公式α,Γ├Sα,即存在公式α,使得Γ├Sα且Γ├Sα,即Γ古典不一致;如果Γ古典不一致,則存在公式α,Γ├Sα且Γ├Sα,又由一階邏輯定理Γ├Sα→ α→β,得Γ├Sβ,由β的任意性 ,得Γ語法不一致。

結(jié)論1.6 古典一致性?語義一致性。

如果古典一致,則由一階邏輯的完全性,?？蓾M足,即Γ語義一致。

如果Γ古典不一致,則存在公式α使得Γ├Sα,且Γ├Sα,由一階邏輯的廣義一致性,得Γ╞α且Γ╞α,即不存在滿足Γ的模型,即Γ語義不一致。

結(jié)論1.7 古典一致性?語法一致性?語義一致性。

在不引起歧義的情況下,公式集相對于一個系統(tǒng)S的古典一致性或語法一致性也稱為公式集的古典一致性或語法一致性。實(shí)際上,證明一個公式集的古典一致性或者語法一致性要?dú)w結(jié)到證明一個公式的不可證,例如證明公式集的古典一致性,就是證明并非Γ├Sα? α,證明其語法一致性就是證明存在一個公式α,并非Γ├Sα。但是,要證明一個公式不能由某個公式集推出,僅用推演的方法,或者說僅從語法的角度是很有難度的。系統(tǒng)的一致性在系統(tǒng)所屬的語言下能否表示、如何表示,是比較復(fù)雜的。這里不討論這個問題。證明公式集是一致的,常用的方法就是利用語義一致性來證明,也就是找到或者說構(gòu)造出滿足公式集的模型,以此說明這個公式集是語義一致的,再由三種一致性的等價性,可以得到這個公式集就是古典一致的或者語法一致的。利用語義一致性來斷言公式集的古典一致性或者語法一致性,是用模型的辦法,而模型是系統(tǒng)外的考察,也就是在系統(tǒng)外給出一個公式集的模型,而不是在系統(tǒng)內(nèi)去說這個公式集有模型。

相對化在邏輯研究中是一種重要的方法,特別是對于證明一階理論的一致性很重要。相對化本質(zhì)上就是給出一階理論的模型,或者說就是證明理論的語義一致性。只不過這個模型的存在是通過另一個一致一階理論可以描述這個理論的模型得到的。

二、一階理論

定義2.1 一階理論。設(shè)L是一階語言,T是L語言下的句子集,如果 T的語義后承都在公式集 T中,則稱 T是一階理論。

一階理論是一個語義后承封閉的句子集(句子是不含自由變元的公式)。在一階邏輯中,如果 T├α(α是Γ的語法后承),則有 T╞α(α是Γ的語義后承)。此時的T可以是任意公式集,所以對于句子集也會有這樣的結(jié)果。由于一階理論對于語義后承封閉,如果 T╞α,則α εT,所以 T├α。因此,一階理論都是有廣義完全性和廣義一致性的,或者說一階理論的語義后承與語法后承等價。需要注意的是,一階理論的廣義一致性(T├α?T╞α)并不意味著T的語義一致性,即不意味著有滿足 T的模型。如果T是一個不一致的句子集,則任何公式都是它的語義后承。如果句子集 T包括所有L的句子,那么,這個句子集 T也是一個一階理論,只不過是一個不一致的理論。

現(xiàn)在討論利用相對化怎樣從一個理論的一致性得到另一個理論的一致性。

三、相對化

定義3.1 公式ψ的φ相對化ψφ。設(shè)φ是一階語言L的公式,它至多只有一個自由變元v1,下面的規(guī)則定義了任意L公式ψ的φ相對化ψφ:

(1)對原子公式ψ,ψφ=ψ;

(2)( ψ)φ= ψφ;

(3)(ψ1→ψ2)φ=ψ1φ→ψ2φ;

(4)(?xψ)φ= ?x(φ′[x/v1]→ψφ)(其中ψ′是φ的一個合適易字,使得x對v1在φ′代入自由)。

從這個定義可以看出,公式關(guān)于φ的相對化主要是改變公式的量詞,也就是規(guī)則(4)的內(nèi)容。它把全稱公式修改為一個蘊(yùn)涵式,直觀上的意思是:修改論域,“對所有x,…”改成了“對所有滿足公式φ的x,…”。

在規(guī)則(4)中,雖然φ′可有多種選擇,但可以約定約束變元易字時所選用的順序,這樣就可以唯一地確定φ′。以下約定,在做公式的φ′相對化時,都已做過了適當(dāng)?shù)囊鬃?,所以規(guī)則(4)一般可以直接寫成(?xψ)φ= ?x(φ→ψφ)。

下面定義一個到一階理論中的相對化。

定義3.2 φ可定義一個到 T中的相對化。設(shè) T是語言L的一階理論,φ是至多只含一個變元v1的L公式,如果T與φ滿足以下條件,則稱φ可定義一個到 T中的相對化:

(1)T├?v1φ;

(2)對L的每個常量符號c,都有 T├φ[c/v1];

(3)對每個n元函數(shù)符號f,都有 T├?x1…?xn(φ[x1/v1]→ …→φ[xn/v1]→φ[fx1…xn/v1])。

直觀上說,φ可定義一個到 T的相對化,實(shí)際上是用T和φ描述了一個語言L的結(jié)構(gòu)。我們知道,結(jié)構(gòu)包括論域和語言中非邏輯符號在論域上解釋,結(jié)構(gòu)的論域要求非空。這個定義描述的結(jié)構(gòu)是這樣的:條件(1)是用公式φ來規(guī)定論域非空;(2)和(3)直觀上是說,常量符號和函數(shù)符號的解釋分別是論域上的個體和論域上的函數(shù)。

這里給出的相對化解釋在于說明這種語法的直觀意義,后面將詳細(xì)討論相對化的語義。但是公式ψ的φ相對化ψφ以及φ可定義一個到 T中的相對化都是語法定義,不涉及語義。第一個定義規(guī)定了一種符號串的變形規(guī)則;第二個定義規(guī)定了某種特殊的語法推出。

相對化有一個重要的結(jié)果,它揭示了兩個一階理論一致性的關(guān)系。依據(jù)這個關(guān)系,可以由一個理論的一致性得到另一個理論的一致性。

定義3.3 設(shè) T是語言L的理論,L的公式φ可定義一個到 T中的相對化,再設(shè)Ψ是L的句子集,使得對每個ψ ε Ψ ,都有 T ├ψφ,則

(1)對 L 語句θ,如果Ψ├θ,則 T ├θφ;

(2)如果 T一致,則 Th(Ψ)一致。[1](P195)

如果 T′可以有窮公理化,即 T′=Th(Ψ),其中Ψ是有窮的句子集,那么,上述公理的條件保證了可以從 T的一致性得到 T′的一致性。

前面曾談到涉及相對化的兩個定義都是語法定義,從T的一致性到 Th(Ψ)的一致性,利用的是語法證明。公式φ的相對化ψφ,實(shí)際上是公式變形的函數(shù)(此時約束變元易字所用的變元是確定的,這一點(diǎn)容易做到)。[2](P53)對于任何公式ψ,它唯一地指定了ψφ。但是,并不是任何相對化都能達(dá)到證明一致性的結(jié)果,這里要求φ可以定義一個 T中的相對化,也就是滿足第二個定義的語法推出條件。有了這些條件,還要求每個ψ中的句子ψ,都有T├ψφ。只有這三個條件都滿足了,才可以用相對化證明Th(Ψ)一致 。

相對化證明系統(tǒng)的一致性是一種語法證明方法。除了相對性,利用其他語法方法證明理論的一致性在現(xiàn)代邏輯中有很多。比如證明一階謂詞邏輯(不含等詞、函數(shù)符號)系統(tǒng)的一致性,就可以從語法的角度,通過經(jīng)典命題邏輯的一致性得到證明。[3](P95)關(guān)鍵是通過公式變形函數(shù)f,它規(guī)定了每一個一階謂詞邏輯公式都唯一對應(yīng)于一個命題邏輯公式(f變形實(shí)際上把原子公式與全稱公式都處理成命題變元),然后證明每一個一階邏輯定理的f變形都是命題邏輯系統(tǒng)的定理。這樣,如果謂詞邏輯系統(tǒng)是不一致的,則有兩個相互矛盾的命題都是謂詞邏輯系統(tǒng)的定理。它們所對應(yīng)的f變形公式也是相互矛盾的,所以f變形后的兩個相互矛盾的命題邏輯公式也都是命題邏輯的定理,而這是不可能的。再比如,在模態(tài)邏輯系統(tǒng)中證明一些正規(guī)的模態(tài)命題邏輯系統(tǒng)的一致性也可以用這樣的語法方法,從經(jīng)典的命題邏輯系統(tǒng)的一致性得到這些正規(guī)的模態(tài)命題邏輯系統(tǒng)的一致性。[4](P95)首先規(guī)定一個公式變形的函數(shù)P,它規(guī)定了如何把任意的模態(tài)命題公式唯一地對應(yīng)到一個命題邏輯公式。P變形就是消去模態(tài)命題邏輯公式的所有模態(tài)詞。然后證明所有的模態(tài)命題邏輯系統(tǒng)的定理的P變形都是命題邏輯系統(tǒng)的定理。這樣,就可以從經(jīng)典命題邏輯系統(tǒng)的一致性得到正規(guī)模態(tài)命題邏輯系統(tǒng)的一致性。

這兩個例子很有代表性。第一個例子是把謂詞邏輯的語言翻譯成命題邏輯的語言,第二個例子是在同一種語言下做的公式翻譯。這說明可以在同一種語言下利用語法證明系統(tǒng)的一致性,也可以在不同語言下利用語法證明系統(tǒng)的一致性。上述討論的相對化是在同一種語言下證明系統(tǒng)的一致性,這種相對化實(shí)質(zhì)上與這兩個例子沒有不同,它也是通過公式變形,然后證明 Th(Ψ)中的公式變形都可以由 T得到,從 T的一致性得到 Th(Ψ)的一致性。

相對化證明系統(tǒng)的一致性也可以擴(kuò)展到不同語言。

定義3.4 解釋。設(shè)L和L′是兩個一階語言,T是L的一個理論,語言L′到理論 T中的解釋δ,由下列組成:

(1)指定L的一個一元謂詞D,使得 T├ExDx,D稱作解釋的域;

(2)對L′的每個常量符號c,δ指定L的一個常量符號 cδ ,使得 T ├Dcδ;

(3)對L′的每個n元函數(shù)符號f(n≥1),δ指定L的一個n元函數(shù)符號fδ,使得 T├?vl…?vn(D vl→…→Dvn →Dfδ(vl…vn));

(4)對L′的每個n元謂詞符號G(n≥1),δ指定L的一個n元函數(shù)符號 Gδ。

“解釋”一詞很形象。我們知道對于一階邏輯語言的非邏輯符號是通過語義結(jié)構(gòu)給出解釋的,上述“解釋”的定義本質(zhì)上就是通過理論 T來描述L′語言的語義結(jié)構(gòu)。(1)的意思是 T描述了語言L′的一個語義結(jié)構(gòu)的論域;(2)的意思是 T描述的結(jié)構(gòu)把L′的常量符號解釋為這個論域的個體;(3)的意思是 T描述的結(jié)構(gòu)把L′的函數(shù)符號解釋為這個結(jié)構(gòu)論域上的函數(shù);(4)的意思是 T描述的L′的語義結(jié)構(gòu)如何解釋謂詞。那么,這個解釋怎樣確定L′句子的真假呢?

首先把L′句子Ψ′中的非邏輯符號按照δ先換成L中的非邏輯符號。這樣每一個Ψ′句子都變形為L公式Ψ。再通過Ψ′的Dx相對化,得到Ψ′Dx。如果 T├ΨDx,則L′公式Ψ′在 T所描述的這個語義結(jié)構(gòu)中真。當(dāng)然,T應(yīng)該是一個一致的理論,否則它所描述的語義結(jié)構(gòu)就是一個矛盾結(jié)構(gòu),這與我們對語義結(jié)構(gòu)的要求相悖。因此,一致的理論可以描述一個語言的語義結(jié)構(gòu)。這里,L和L′并不一定不相同,如果兩種語言相同,那實(shí)際上就是 T通過Dx描述了 T所屬語言的語義結(jié)構(gòu),也就是Dx定義了一個到 T中的相對化。

有關(guān)“解釋”有一個很重要的結(jié)果。限于篇幅,這里只把結(jié)果列出,而不給證明過程。[5](P202)

定義3.5 設(shè)δ語言L′到L理論 T中的解釋,Ψ是L′的一個句子集 ,使得對任意ψ ε Ψ ,都有 T ├ψDx,則

(1)對任意L′語句ψ,如果Ψ├ψDx,則 T├ψDx;

(2)如果 T一致,則 Th(Ψ)也是一致的。

四、相對一致性的應(yīng)用

首先,在同一語言下可以證明兩個理論 T和 T′=Th(Ψ)之間的相對一致性。

T和 T′=Th(Ψ)(Ψ是L的句子集)是同一語言L下的兩個理論,如果φ可定義一個到 T中的相對化,使得對每個ψ ε Ψ ,都有 T ├Ψφ,則由定義 3.3 可知 T 的一致性蘊(yùn)涵T的一致性。這個結(jié)果的一個簡單應(yīng)用就是利用群論的一致性得到交換群理論的一致性。群論和交換群是同一個一階語言下的兩個理論,群論比交換群理論弱,但由于可以找到一個公式φ,它可以定義一個到T中的相對化,并且交換群的公理(這些公理都是閉公式,所以都是句子集)φ的相對化都可以由群論得到,所以群論的一致性蘊(yùn)涵交換群的一致性。

其次,在不同語言下可以證明理論的相對一致性。

例如,向量標(biāo)量理論 TVS和標(biāo)量理論 TS是兩個不同語言下的理論,向量標(biāo)量理論VS的語言是標(biāo)量理論語言的擴(kuò)張,向量標(biāo)量理論是標(biāo)量理論的擴(kuò)張。但是,可以構(gòu)造出向量標(biāo)量語言在標(biāo)量理論 T中的解釋。注意:標(biāo)量語言的非邏輯符號中只有一個一元的謂詞F和二元函數(shù)符號+。F的直觀意義是“標(biāo)量”。標(biāo)量的公理只有兩個:(1)?xFx;(2)?x?y?z(x+y)+z=x+(y+z)。向量標(biāo)量理論的非邏輯符號除了 F和+外還有一元謂詞V、二元函數(shù)符號°,＊。可以構(gòu)造向量標(biāo)量理論的語言到標(biāo)量理論中的解釋。這個解釋的Dx就是Fx。把V指定為F,把°,＊都指定為+。這樣,向量標(biāo)量的公理都還原為向量的公理。利用定義3.5就可以從標(biāo)量理論的一致性得到向量標(biāo)量理論的一致性。這里的兩個例子都很簡單。實(shí)際上,相對一致性在數(shù)學(xué)基礎(chǔ)的研究中還有許多復(fù)雜的應(yīng)用。

比較相對化的兩條定理不難發(fā)現(xiàn),這兩條定理有一個基本的相同點(diǎn)——保守性。這兩條定理實(shí)質(zhì)上是把一些公式翻譯為另一些公式。如果這些公式可以從Ψ推出,那么它們的翻譯也可以從 T中推出。如果把保守性看做是相對化的本質(zhì),那么它與其他的語法翻譯的保守性證明一致性就沒有實(shí)質(zhì)的區(qū)別。比如,謂詞邏輯語言可以翻譯為命題邏輯語言,正規(guī)模態(tài)命題邏輯語言可以翻譯為命題邏輯語言,而且這種翻譯具有保守性,所以利用命題邏輯系統(tǒng)的一致性可以證明謂詞邏輯系統(tǒng)的一致性,利用命題邏輯系統(tǒng)的一致性可以證明正規(guī)模態(tài)邏輯系統(tǒng)的一致性。

五、結(jié)語

證明理論的一致性有兩種基本方法:一種是直接給出滿足理論的語義結(jié)構(gòu),另一種是通過一個理論的一致性得到要證理論的一致性。第一種方法最直接。一般來說,每一個語義結(jié)構(gòu)都可以被一個一致理論 T描述。它描述了語義結(jié)構(gòu)的論域,并且給出非邏輯符號的解釋,還規(guī)定了句子的真假。如果T′描述了一個滿足T的語義結(jié)構(gòu),則 T′的一致性蘊(yùn)涵 T的一致性。要證理論 T′的一致性需要給出一個滿足它的語義結(jié)構(gòu),然而該語義結(jié)構(gòu)又可以由另一個理論 T″來描述,也需要證明這個理論 T″的一致性……陷入無窮倒退。這種無窮倒退并不是什么可怕的事情,它僅僅啟示了我們的思維無法證明我們思維所用邏輯的合理性(無矛盾),因?yàn)槲覀冊谧C明思維所用邏輯的合理性時也在使用思維中的邏輯。

有的邏輯學(xué)家認(rèn)為系統(tǒng)的有窮模型是一種絕對的一致性,但數(shù)學(xué)家并不對這種“絕對”的一致性感興趣,因?yàn)槎鄶?shù)有價值并且有趣數(shù)學(xué)理論沒有有窮模型。[6](P202)究竟什么是絕對的一致性,也應(yīng)是數(shù)學(xué)哲學(xué)中一個很有趣的問題。如果絕對的一致性就是有窮模型性,那么,并非所有的理論都有這樣的一致性。要證明這些理論的一致性,我們就要從一個理論的一致性得到另一個理論的一致性。相對化就是證明理論一致性的一種很重要的方法。這種方法無論是對于同一語言下的兩種理論還是對于不同語言下的兩種理論都可應(yīng)用。相對性可以從弱系統(tǒng)的一致性得到強(qiáng)系統(tǒng)的一致性,即證明強(qiáng)系統(tǒng)相對弱系統(tǒng)的一致性。這較之弱系統(tǒng)相對強(qiáng)系統(tǒng)的一致性不平常(not trivial)。這也是希爾伯特提出希爾伯特計(jì)劃的初衷,即希望從有窮數(shù)學(xué)的一致性推出包含理想元(無窮)數(shù)學(xué)的一致性。雖然希爾伯特的計(jì)劃由于哥德爾不完全性定理遭到破壞,但這個基本的思想?yún)s一直在現(xiàn)代邏輯中有著很強(qiáng)的活力,現(xiàn)在證明論的還原性的工作就是希爾伯特的修正方案的繼續(xù)。

[1]葉峰:《一階邏輯與一階理論》,北京,中國社會科學(xué)出版社,1994。

[2][5]H.D.Ebbinghause,J.Flum,W.Thomas.Mathematical Logic.Second Edition.Springer,1994.

[3]劉壯虎:《邏輯演算》,北京,中國社會科學(xué)出版社,1993。

[4]周北海:《模態(tài)邏輯》,北京,北京大學(xué)出版社,1997。

[6]Roman Murawski.Recursive Functions and Metamathematics.Kluwer Academic Publishers,1999.

A Theory's Relative Consistency

XU Di-fei
(School of Philosophy,Renmin University of China,Beijing 100872)

Consistency is a basic requirement of a“good”theory.There are two basic methods to prove that a theory is consistent.One is to give a semantic structure which satisfies the theory and the other is to prove the consistency of the theory from the consistency of another theory.Relativisation is the method to prove a theory's consistency which belongs to the latter.It can prove a stronger theory's consistency from a weaker theory's consistency.It is shown that relativisation is essentially to give a theory T's semantic structure indirectly by a media—another theory which can describe the structure of the language of the theory T.The essence of relativization is a conservative translation,which is the key to prove the consistency of a stronger theory from that of the weaker.

relativisation;interpretation;conservative;consistency

許滌非:哲學(xué)博士,中國人民大學(xué)哲學(xué)系副教授(北京100872)

(責(zé)任編輯 李 理)

中國人民大學(xué)科學(xué)研究基金項(xiàng)目(06XNB068)