量詞可消去的線性序理論

杜芬芬，陳國龍

1.淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，淮北，235000；2.宿州學(xué)院,宿州，234000

量詞可消去的線性序理論

杜芬芬1，陳國龍2

1.淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，淮北，235000；2.宿州學(xué)院,宿州，234000

量詞消去法在模型論的證明中是應(yīng)用很廣的一種方法。本文主要討論在語言L=<,0上的有首元但無末元的稠密線性序理論T和在語言L0=<上的無末元離散線性序理論T0的量詞可消去性,及其在擴充語言L1=S,<下理論T0的量詞消去性。

稠密；離散；線性序；量詞消去

量詞消去是模型論研究的重要工具，而對于可定義集上理論的研究，由于量詞的存在使得研究變得相當復(fù)雜。由于一階理論具有量詞消去性質(zhì),所以對于該理論中公式的研究范圍就可以縮小到無量詞公式，這樣就減少了研究的難度。

本文主要討論有首元但無末元的稠密線性序理論和無末元的離散線性序理論。分別考慮語言L=<,0,語言L0=<及其擴充下的語言L1=S,<，其中<在它的模型中的解釋是序關(guān)系,S被解釋為后繼函數(shù)。本文第1部分給出一些定義,第2部分證明理論T和T0分別在語言L=<,0和語言L1=S,<上具有量詞消去性質(zhì)，而T0在語言L0=<上量詞不可消去的。

1 準備工作

定義1[1]設(shè)T為語言L中的理論，假如對T中的任意L-公式φ，存在無量詞的L-公式ψ，使得

T╞φ?ψ

則稱理論T是量詞可消去的。

定義2[2]設(shè)A,B是語言L的模型并且A?B。當下列條件成立時,稱A為B的初等子模型,記作AB:對L中每一公式φx1，…，xn及A中每一n元組a1,…,an,都有

A╞φa1，…，an當且只當B╞φa1，…，an引理1[1]語言為L的理論T為量詞可消去的當且僅當形為?x?1∧，…，∧?k的所有公式量詞可消去，這里?i為L的原子公式或原子公式的否定。

引理2[2]設(shè)T是L中的理論,當T適合下列條件時,稱為模型完全的:對T的任何模型A,B,若A?B,則AB。

2 主要結(jié)果的證明

定理1有首元但無末元的稠密線性序理論在語言L=<,0中是量詞可消去的。

證明將該理論的公理集分類列在下面：

線性序公理：

A1?x┐x

A2?x?y(x=y∨x

A3?x?y?zx

稠密性公理：

B?x?y?zx

首元0的公理：C1?xx=0∨0

無末元的公理：C2?x?yx

根據(jù)引理1,只需要證明形為：

?x?1∧…∧?r

(1)

的任意一個公式都可以等價到一個無量詞公式。這里的?i為L中原子公式或原子公式的否定，現(xiàn)在討論?i的多種可能形式。

假定t1和t2為語言中L的項，則它們可能為0,1或者變元，那么?i一定為t1=t2，t1

又因為┐t1

奠基當r=1 時，公式(1)為?xt1

歸納假定對一切r

?x(x

(2)

其中ti,vi和ui為項，假定它們和x都不相同。假如ti=x或ui=x，那么(2)式可等價到假;如果vi=x，則(2)式可以歸約到r=k-1的情形。

情形1當m>1時,(2)式可等價到：

(t1

∨┐x

該公式歸約為r=k-1的情形。

當n>1時，那么(2)式可等價到：

(u1

該公式歸約為r=k-1的情形。

情形2現(xiàn)在考察m=1,n=1的情形，則公式(2)可以寫成:

?xx

情形3其次考察m=0,n=1的情形，則公式(2)可寫成:

?xu1

如果l≠0，它等價到u1

情形4如果m=1,n=0，公式(2)可等價到：

?xx

如果l≠0，它等價到v1

情形5最后考慮m=0,n=0的情形，則該公式可以等價到:

?xx=v1∧…∧x=vl

那么該公式可以等價到真或假。

這樣就證明了有首元但無末元的稠密線性序理論在語言L=<,0中是量詞可消去的。

定理2無末元離散線性序的理論在語言L0=<中是量詞不可消去的。

證明現(xiàn)將該理論公理集分類列在下面:

線性序公理:

A1?x┐x

A2?x?y(x=y∨x

A3?x?y?zx

D?x?yx

由Z╞T0,設(shè)Z0=Z∪1/3,可知Z0╞T0，顯然Z?Z0。令Z0╞?x0

定理3無末元的離散線性序理論在語言L1=S,<中是量詞可消去的，這里的S是后繼函數(shù)。

證明首先列出該理論的公理集。

線性序公理：

A1?x┐x

A2?x?y(x=y∨x

A3?x?y?zx

再定義后繼函數(shù)和表示無末元的公理。

D1?x?yx

D2?x?yy=Sx

在一個語言L1中，項的一般形式為Sx=S，…，Sx(p次)，根據(jù)引理，只需證明形為

?x?1∧，…，?r

(3)

的任意公式均可等價到一個無量詞公式。這里?i為L1中的原子公式或原子公式的否定。現(xiàn)在考察?i的多種可能形式。

假定Sp1x1和Sp2x2為L1中的項，?i必為Sp1x1

注意到┐(Sp1x1

下面使用歸納法證明，并歸納于原子公式?i的個數(shù)r。

奠基r=1。

情形1Sp1x1

情形1.1x1和x2中至少有一個是x,比如x=x1,則?xSp1x

情形1.2考慮x=x1=x2，那么如果p1

情形2Sp1x1=Sp2x2,則分為以下兩種子情形。

情形2.1x1=x或x2=x,不失一般性，設(shè)x1=x,則?xSp1x=Sp2x2或為真或為假，看是否存在首元。

情形2.2x1=x2=x,如果p1=p2,則該公式為真，否則為假。

下一步歸納證明的第2部分。

歸納假定對一切r

如果有某個?i不含x，則可歸約為k-1的情形,因此可設(shè)?i中至少有一個x1或x2為x。如果某個?i中有x1=x2=x，則該?i形如Sp1x

下面將Spx=x1和Spx

?x(x

(4)

這里ti，ui和vi均為形式為Spx的項，p為整數(shù)。

情形1當m>1時，公式(4)可等價到:

(t1

該公式歸約為r=k-1的情形。

當n>1時，公式(4)可等價到:

u1

該公式歸約為r=k-1的情形。

情形2現(xiàn)在考察m=1,n=1的情形，則公式(4)可寫成:

?xx

情形3考察m=0,n=1的情形，則公式(4)可寫成:

?xu1

如果l≠0，它等價到u1

情形4如果m=1,n=0，則公式(4)可寫成:

?xx

如果l≠0，它等價到v1

情形5最后考察m=0,n=0的情形,則該公式變?yōu)?

?xx=v1∧…∧x=vl

那么該公式為真或假。

這樣就證明了無終端離散線性序理論T0在語言L1=S,<中是量詞可消去的。

[1]史念東.代數(shù)模型論引論[M].北京:科學(xué)出版社,2011:11-17

[2]王世強.模型論基礎(chǔ)[M].北京:科學(xué)出版社,1987:1-10

[3]Marker D.Model Theory:An Introduction[M].北京:科學(xué)出版社,2007:71-83

[4]沈云付.素數(shù)階群理論消去及復(fù)雜性[J].數(shù)學(xué)學(xué)報,2001,44(1):21-28

[5]沈紹恩.一類具有量詞消去性質(zhì)的偏序結(jié)構(gòu)[J].科學(xué)通報,1992,23(37):13-14

(責任編輯：劉小陽)

2017-06-25

安徽省高校自然科學(xué)研究重大項目(KJ2014ZD31)。

杜芬芬(1992-)，女，安徽阜陽人，在讀碩士研究生，研究方向：數(shù)理邏輯及其應(yīng)用。

10.3969/j.issn.1673-2006.2017.10.025

O141.4

A

1673-2006(2017)10-0096-03