理论的相对一致性

许涤非

理论的相对一致性

许涤非

证明理论的一致性有两种基本方法:一是直接给出满足理论的语义结构;二是从一种理论的一致性得到要证理论的一致性。相对化的方法属于第二种方法,它可以从弱系统的一致性证明强系统的一致性。相对化证明理论的一致性实质上是以某个理论为中介,间接地给出满足理论 T的语义结构。相对化的本质是“保守性”的翻译,而“保守性”翻译恰是从弱系统证明强系统的关键。

理论;相对化;保守性;一致性

两个一阶理论T与T′的一致性可以有某种联系。如果 T是不比 T′弱的理论(也就是从 T′可推出的东西都可以由 T推出),那么,T′如果能够推出矛盾,则 T也能够推出矛盾。所以,从较强的理论的一致性能够得到较弱理论的一致性。本文的主要目的就是讨论一种证明公式集一致性的方法——相对化,重点说明它背后的思想、证明思路以及应用。

一、“一致性”概念

一致性是一个相对概念,都是相对某个系统而言的。常见的一致性有三种,分别是古典一致性、语法一致性和语义一致性。下面是其定义。

定义1.1 古典一致。如果在系统S中,从公式集推不出矛盾,则称公式集Γ相对于 S是古典一致的,即:如果不存在公式α使得Γ├Sα且Γ├Sα,则称Γ相对于S是古典一致的。

定义1.2 语法不一致,语法一致。如果公式集Γ在系统S中可以推出一切公式,则称公式集Γ相对于S是语法不一致的。如果公式集Γ相对系统S不是语法不一致的,则称公式集Γ相对系统 S是语法一致的,即:如果存在α,使得并非Γ├Sα,则称公式集Γ相对系统S是语法一致的。

定义1.3 语义一致。如果有满足公式集Γ模型或者解释,则称公式集Γ是语义一致的。公式集Γ相对于系统S是语义一致的,也就是:存在S所属语言的模型,使得任给Γ中的任意公式α都有M╞α。

需要注意的是,这里的“语义一致”与“广义语义一致”是不同的。

定义1.4 广义语义一致。在系统S中,对于任意公式集Γ,如果Γ├Sα,则Γ╞α,称该系统广义语义一致。

广义语义一致是就某个逻辑系统而言的,是说任何公式集Γ的语法后承都是语义后承。语义一致是就某个公式集Γ而言的,说的是存在满足某个公式集Γ的模型。一个逻辑系统是广义语义一致的,不一定任一公式集Γ相对于该系统语义一致。如果这个公式集包含一对矛盾的公式,则自然不可满足,但是此时仍然有:如果Γ├Sα,则Γ╞α。这就说明广义语义一致与语义一致是不同的概念。

对于一阶逻辑,古典一致性、语法一致性、语义一致性是等价的。下面是这个结果的说明。

结论1.5 古典一致性⇔语法一致性。

如果Γ语法不一致,则对任一公式α,Γ├Sα,即存在公式α,使得Γ├Sα且Γ├Sα,即Γ古典不一致;如果Γ古典不一致,则存在公式α,Γ├Sα且Γ├Sα,又由一阶逻辑定理Γ├Sα→ α→β,得Γ├Sβ,由β的任意性 ,得Γ语法不一致。

结论1.6 古典一致性⇔语义一致性。

如果古典一致,则由一阶逻辑的完全性,Γ可满足,即Γ语义一致。

如果Γ古典不一致,则存在公式α使得Γ├Sα,且Γ├Sα,由一阶逻辑的广义一致性,得Γ╞α且Γ╞α,即不存在满足Γ的模型,即Γ语义不一致。

结论1.7 古典一致性⇔语法一致性⇔语义一致性。

在不引起歧义的情况下,公式集相对于一个系统S的古典一致性或语法一致性也称为公式集的古典一致性或语法一致性。实际上,证明一个公式集的古典一致性或者语法一致性要归结到证明一个公式的不可证,例如证明公式集的古典一致性,就是证明并非Γ├Sα˄ α,证明其语法一致性就是证明存在一个公式α,并非Γ├Sα。但是,要证明一个公式不能由某个公式集推出,仅用推演的方法,或者说仅从语法的角度是很有难度的。系统的一致性在系统所属的语言下能否表示、如何表示,是比较复杂的。这里不讨论这个问题。证明公式集是一致的,常用的方法就是利用语义一致性来证明,也就是找到或者说构造出满足公式集的模型,以此说明这个公式集是语义一致的,再由三种一致性的等价性,可以得到这个公式集就是古典一致的或者语法一致的。利用语义一致性来断言公式集的古典一致性或者语法一致性,是用模型的办法,而模型是系统外的考察,也就是在系统外给出一个公式集的模型,而不是在系统内去说这个公式集有模型。

相对化在逻辑研究中是一种重要的方法,特别是对于证明一阶理论的一致性很重要。相对化本质上就是给出一阶理论的模型,或者说就是证明理论的语义一致性。只不过这个模型的存在是通过另一个一致一阶理论可以描述这个理论的模型得到的。

二、一阶理论

定义2.1 一阶理论。设L是一阶语言,T是L语言下的句子集,如果 T的语义后承都在公式集 T中,则称 T是一阶理论。

一阶理论是一个语义后承封闭的句子集(句子是不含自由变元的公式)。在一阶逻辑中,如果 T├α(α是Γ的语法后承),则有 T╞α(α是Γ的语义后承)。此时的T可以是任意公式集,所以对于句子集也会有这样的结果。由于一阶理论对于语义后承封闭,如果 T╞α,则α εT,所以 T├α。因此,一阶理论都是有广义完全性和广义一致性的,或者说一阶理论的语义后承与语法后承等价。需要注意的是,一阶理论的广义一致性(T├α⇒T╞α)并不意味着T的语义一致性,即不意味着有满足 T的模型。如果T是一个不一致的句子集,则任何公式都是它的语义后承。如果句子集 T包括所有L的句子,那么,这个句子集 T也是一个一阶理论,只不过是一个不一致的理论。

现在讨论利用相对化怎样从一个理论的一致性得到另一个理论的一致性。

三、相对化

定义3.1 公式ψ的φ相对化ψφ。设φ是一阶语言L的公式,它至多只有一个自由变元v1,下面的规则定义了任意L公式ψ的φ相对化ψφ:

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

(2)( ψ)φ= ψφ;

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

(4)(∀xψ)φ= ∀x(φ′[x/v1]→ψφ)(其中ψ′是φ的一个合适易字,使得x对v1在φ′代入自由)。

从这个定义可以看出,公式关于φ的相对化主要是改变公式的量词,也就是规则(4)的内容。它把全称公式修改为一个蕴涵式,直观上的意思是:修改论域,“对所有x,…”改成了“对所有满足公式φ的x,…”。

在规则(4)中,虽然φ′可有多种选择,但可以约定约束变元易字时所选用的顺序,这样就可以唯一地确定φ′。以下约定,在做公式的φ′相对化时,都已做过了适当的易字 ,所以规则(4)一般可以直接写成(∀xψ)φ= ∀x(φ→ψφ)。

下面定义一个到一阶理论中的相对化。

定义3.2 φ可定义一个到 T中的相对化。设 T是语言L的一阶理论,φ是至多只含一个变元v1的L公式,如果T与φ满足以下条件,则称φ可定义一个到 T中的相对化:

(1)T├∃v1φ;

(2)对L的每个常量符号c,都有 T├φ[c/v1];

(3)对每个n元函数符号f,都有 T├∀x1…∀xn(φ[x1/v1]→ …→φ[xn/v1]→φ[fx1…xn/v1])。

直观上说,φ可定义一个到 T的相对化,实际上是用T和φ描述了一个语言L的结构。我们知道,结构包括论域和语言中非逻辑符号在论域上解释,结构的论域要求非空。这个定义描述的结构是这样的:条件(1)是用公式φ来规定论域非空;(2)和(3)直观上是说,常量符号和函数符号的解释分别是论域上的个体和论域上的函数。

这里给出的相对化解释在于说明这种语法的直观意义,后面将详细讨论相对化的语义。但是公式ψ的φ相对化ψφ以及φ可定义一个到 T中的相对化都是语法定义,不涉及语义。第一个定义规定了一种符号串的变形规则;第二个定义规定了某种特殊的语法推出。

相对化有一个重要的结果,它揭示了两个一阶理论一致性的关系。依据这个关系,可以由一个理论的一致性得到另一个理论的一致性。

定义3.3 设 T是语言L的理论,L的公式φ可定义一个到 T中的相对化,再设Ψ是L的句子集,使得对每个ψ ε Ψ ,都有 T ├ψφ,则

(1)对 L 语句θ,如果Ψ├θ,则 T ├θφ;

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

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

前面曾谈到涉及相对化的两个定义都是语法定义,从T的一致性到 Th(Ψ)的一致性,利用的是语法证明。公式φ的相对化ψφ,实际上是公式变形的函数(此时约束变元易字所用的变元是确定的,这一点容易做到)。[2](P53)对于任何公式ψ,它唯一地指定了ψφ。但是,并不是任何相对化都能达到证明一致性的结果,这里要求φ可以定义一个 T中的相对化,也就是满足第二个定义的语法推出条件。有了这些条件,还要求每个ψ中的句子ψ,都有T├ψφ。只有这三个条件都满足了,才可以用相对化证明Th(Ψ)一致 。

相对化证明系统的一致性是一种语法证明方法。除了相对性,利用其他语法方法证明理论的一致性在现代逻辑中有很多。比如证明一阶谓词逻辑(不含等词、函数符号)系统的一致性,就可以从语法的角度,通过经典命题逻辑的一致性得到证明。[3](P95)关键是通过公式变形函数f,它规定了每一个一阶谓词逻辑公式都唯一对应于一个命题逻辑公式(f变形实际上把原子公式与全称公式都处理成命题变元),然后证明每一个一阶逻辑定理的f变形都是命题逻辑系统的定理。这样,如果谓词逻辑系统是不一致的,则有两个相互矛盾的命题都是谓词逻辑系统的定理。它们所对应的f变形公式也是相互矛盾的,所以f变形后的两个相互矛盾的命题逻辑公式也都是命题逻辑的定理,而这是不可能的。再比如,在模态逻辑系统中证明一些正规的模态命题逻辑系统的一致性也可以用这样的语法方法,从经典的命题逻辑系统的一致性得到这些正规的模态命题逻辑系统的一致性。[4](P95)首先规定一个公式变形的函数P,它规定了如何把任意的模态命题公式唯一地对应到一个命题逻辑公式。P变形就是消去模态命题逻辑公式的所有模态词。然后证明所有的模态命题逻辑系统的定理的P变形都是命题逻辑系统的定理。这样,就可以从经典命题逻辑系统的一致性得到正规模态命题逻辑系统的一致性。

这两个例子很有代表性。第一个例子是把谓词逻辑的语言翻译成命题逻辑的语言,第二个例子是在同一种语言下做的公式翻译。这说明可以在同一种语言下利用语法证明系统的一致性,也可以在不同语言下利用语法证明系统的一致性。上述讨论的相对化是在同一种语言下证明系统的一致性,这种相对化实质上与这两个例子没有不同,它也是通过公式变形,然后证明 Th(Ψ)中的公式变形都可以由 T得到,从 T的一致性得到 Th(Ψ)的一致性。

相对化证明系统的一致性也可以扩展到不同语言。

定义3.4 解释。设L和L′是两个一阶语言,T是L的一个理论,语言L′到理论 T中的解释δ,由下列组成:

(1)指定L的一个一元谓词D,使得 T├ExDx,D称作解释的域;

(2)对L′的每个常量符号c,δ指定L的一个常量符号 cδ ,使得 T ├Dcδ;

(3)对L′的每个n元函数符号f(n≥1),δ指定L的一个n元函数符号fδ,使得 T├∀vl…∀vn(D vl→…→Dvn →Dfδ(vl…vn));

(4)对L′的每个n元谓词符号G(n≥1),δ指定L的一个n元函数符号 Gδ。

“解释”一词很形象。我们知道对于一阶逻辑语言的非逻辑符号是通过语义结构给出解释的,上述“解释”的定义本质上就是通过理论 T来描述L′语言的语义结构。(1)的意思是 T描述了语言L′的一个语义结构的论域;(2)的意思是 T描述的结构把L′的常量符号解释为这个论域的个体;(3)的意思是 T描述的结构把L′的函数符号解释为这个结构论域上的函数;(4)的意思是 T描述的L′的语义结构如何解释谓词。那么,这个解释怎样确定L′句子的真假呢?

首先把L′句子Ψ′中的非逻辑符号按照δ先换成L中的非逻辑符号。这样每一个Ψ′句子都变形为L公式Ψ。再通过Ψ′的Dx相对化,得到Ψ′Dx。如果 T├ΨDx,则L′公式Ψ′在 T所描述的这个语义结构中真。当然,T应该是一个一致的理论,否则它所描述的语义结构就是一个矛盾结构,这与我们对语义结构的要求相悖。因此,一致的理论可以描述一个语言的语义结构。这里,L和L′并不一定不相同,如果两种语言相同,那实际上就是 T通过Dx描述了 T所属语言的语义结构,也就是Dx定义了一个到 T中的相对化。

有关“解释”有一个很重要的结果。限于篇幅,这里只把结果列出,而不给证明过程。[5](P202)

定义3.5 设δ语言L′到L理论 T中的解释,Ψ是L′的一个句子集 ,使得对任意ψ ε Ψ ,都有 T ├ψDx,则

(1)对任意L′语句ψ,如果Ψ├ψDx,则 T├ψDx;

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

四、相对一致性的应用

首先,在同一语言下可以证明两个理论 T和 T′=Th(Ψ)之间的相对一致性。

T和 T′=Th(Ψ)(Ψ是L的句子集)是同一语言L下的两个理论,如果φ可定义一个到 T中的相对化,使得对每个ψ ε Ψ ,都有 T ├Ψφ,则由定义 3.3 可知 T 的一致性蕴涵T的一致性。这个结果的一个简单应用就是利用群论的一致性得到交换群理论的一致性。群论和交换群是同一个一阶语言下的两个理论,群论比交换群理论弱,但由于可以找到一个公式φ,它可以定义一个到T中的相对化,并且交换群的公理(这些公理都是闭公式,所以都是句子集)φ的相对化都可以由群论得到,所以群论的一致性蕴涵交换群的一致性。

其次,在不同语言下可以证明理论的相对一致性。

例如,向量标量理论 TVS和标量理论 TS是两个不同语言下的理论,向量标量理论VS的语言是标量理论语言的扩张,向量标量理论是标量理论的扩张。但是,可以构造出向量标量语言在标量理论 T中的解释。注意:标量语言的非逻辑符号中只有一个一元的谓词F和二元函数符号+。F的直观意义是“标量”。标量的公理只有两个:(1)∀xFx;(2)∀x∀y∀z(x+y)+z=x+(y+z)。向量标量理论的非逻辑符号除了 F和+外还有一元谓词V、二元函数符号°,＊。可以构造向量标量理论的语言到标量理论中的解释。这个解释的Dx就是Fx。把V指定为F,把°,＊都指定为+。这样,向量标量的公理都还原为向量的公理。利用定义3.5就可以从标量理论的一致性得到向量标量理论的一致性。这里的两个例子都很简单。实际上,相对一致性在数学基础的研究中还有许多复杂的应用。

比较相对化的两条定理不难发现,这两条定理有一个基本的相同点——保守性。这两条定理实质上是把一些公式翻译为另一些公式。如果这些公式可以从Ψ推出,那么它们的翻译也可以从 T中推出。如果把保守性看做是相对化的本质,那么它与其他的语法翻译的保守性证明一致性就没有实质的区别。比如,谓词逻辑语言可以翻译为命题逻辑语言,正规模态命题逻辑语言可以翻译为命题逻辑语言,而且这种翻译具有保守性,所以利用命题逻辑系统的一致性可以证明谓词逻辑系统的一致性,利用命题逻辑系统的一致性可以证明正规模态逻辑系统的一致性。

五、结语

证明理论的一致性有两种基本方法:一种是直接给出满足理论的语义结构,另一种是通过一个理论的一致性得到要证理论的一致性。第一种方法最直接。一般来说,每一个语义结构都可以被一个一致理论 T描述。它描述了语义结构的论域,并且给出非逻辑符号的解释,还规定了句子的真假。如果T′描述了一个满足T的语义结构,则 T′的一致性蕴涵 T的一致性。要证理论 T′的一致性需要给出一个满足它的语义结构,然而该语义结构又可以由另一个理论 T″来描述,也需要证明这个理论 T″的一致性……陷入无穷倒退。这种无穷倒退并不是什么可怕的事情,它仅仅启示了我们的思维无法证明我们思维所用逻辑的合理性(无矛盾),因为我们在证明思维所用逻辑的合理性时也在使用思维中的逻辑。

有的逻辑学家认为系统的有穷模型是一种绝对的一致性,但数学家并不对这种“绝对”的一致性感兴趣,因为多数有价值并且有趣数学理论没有有穷模型。[6](P202)究竟什么是绝对的一致性,也应是数学哲学中一个很有趣的问题。如果绝对的一致性就是有穷模型性,那么,并非所有的理论都有这样的一致性。要证明这些理论的一致性,我们就要从一个理论的一致性得到另一个理论的一致性。相对化就是证明理论一致性的一种很重要的方法。这种方法无论是对于同一语言下的两种理论还是对于不同语言下的两种理论都可应用。相对性可以从弱系统的一致性得到强系统的一致性,即证明强系统相对弱系统的一致性。这较之弱系统相对强系统的一致性不平常(not trivial)。这也是希尔伯特提出希尔伯特计划的初衷,即希望从有穷数学的一致性推出包含理想元(无穷)数学的一致性。虽然希尔伯特的计划由于哥德尔不完全性定理遭到破坏,但这个基本的思想却一直在现代逻辑中有着很强的活力,现在证明论的还原性的工作就是希尔伯特的修正方案的继续。

[1]叶峰:《一阶逻辑与一阶理论》,北京,中国社会科学出版社,1994。

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

[3]刘壮虎:《逻辑演算》,北京,中国社会科学出版社,1993。

[4]周北海:《模态逻辑》,北京,北京大学出版社,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

许涤非:哲学博士,中国人民大学哲学系副教授(北京100872)

(责任编辑 李 理)

中国人民大学科学研究基金项目(06XNB068)