相容連續(xù)Domain的特征與濃度

張鵬垚，姜廣浩，李海龍，占詩源

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院 ，安徽 淮北 235000）

相容連續(xù)Domain的特征與濃度

張鵬垚，姜廣浩，李海龍，占詩源

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院 ，安徽 淮北 235000）

引入相容連續(xù)Domain的權(quán)與稠密子集的概念，在此基礎(chǔ)上定義相容連續(xù)Domain的特征與濃度.給出局部基的刻畫，并討論相容連續(xù)Domain的特征、濃度與相容連續(xù)Domain帶上Scott拓?fù)浠騆awson拓?fù)鋾r(shí)拓?fù)淇臻g的特征與濃度之間的關(guān)系.證明相容連續(xù)Domain的特征、濃度分別帶上Scott拓?fù)鋾r(shí)拓?fù)淇臻g的特征、濃度相等，它們分別小于相容連續(xù)Domain帶上Lawson拓?fù)鋾r(shí)拓?fù)淇臻g的特征與濃度.

相容連續(xù)Domain；局部基；特征；濃度；Scott拓?fù)洌籐awson拓?fù)?/p>

1 預(yù)備知識

從20世紀(jì)70年代Scott的開創(chuàng)性工作以來，Domain理論一直受到計(jì)算機(jī)科學(xué)和數(shù)學(xué)領(lǐng)域的關(guān)注.由于在Domain理論中，拓?fù)洹⑿?、逼近及邏輯的概念和思想可以相互轉(zhuǎn)換與統(tǒng)一，因此它吸引了格上拓?fù)鋵W(xué)的學(xué)者.隨著連續(xù)Domain理論在計(jì)算機(jī)科學(xué)中的應(yīng)用，作為這種趨勢的一個(gè)標(biāo)志，1994年Abramsky和Jung在文獻(xiàn)［1］中以連續(xù)Domain為主要對象系統(tǒng)闡述了Domain的數(shù)學(xué)理論.文獻(xiàn)［2］提出相容連續(xù)Do?main的定義及一些性質(zhì).文獻(xiàn)［3］給出了連續(xù)Domain的權(quán)定義及性質(zhì).受文獻(xiàn)［4］的啟發(fā)，本文在相容連續(xù)Domain中引入特征與濃度的概念，并討論一些關(guān)系.

定義1.1［2］設(shè)L是偏序集，?≠D?L.若D是定性的，且存在x∈L使得D?↓x，則稱D為L中的相容定向集.

定義1.2［2］若L中每一個(gè)相容定向集的上確界都存在，則稱L是相容Dcpo.

定義1.3［2］設(shè)L是相容Dcpo，?x,y∈L.若對L中的相容定向集D，當(dāng)y≤∨D時(shí)，存在d∈D使得x≤d，則稱x相容雙小于y，記作x?y.若x?x，則稱x為L的緊元，記K(L)={x∈L：x?x}.令?x={u∈L：x?u}，?x={u∈L：u?x}.

定義1.4［2］設(shè)L是相容Dcpo，若?x∈L，?x是相容定向集，且x=∨?x，則稱L是相容連續(xù)Domain.①

命題1.1 設(shè)L是相容Dcpo，若?x∈L，存在定向集Dx，使得Dx??x且x=∨Dx，則L是相容連續(xù)Domain.

證明由定義1.4易得.

定理1.1［2］若L是相容連續(xù)Domain，則?x,z∈L且x≠z?(?y∈L)x?y?z且x≠y.

定義1.5 設(shè)L是相容Dcpo，B?L.若?x∈L,?Bx?B使得Bx是L的相容定向子集，Bx??x且∨Bx=x，則稱B是L的一個(gè)基.

定義1.6［2］設(shè)L是相容Dcpo，U?L.若U滿足：（1）U=↑U；（2）對L的任一相容定向子集D，當(dāng)∨D∈U時(shí)，?d∈D使得d∈U，即U?D≠?，則稱U為Scott開集.令σ(L)={U?L:U是L的Scott開集}，σ(L)稱為L的Scott拓?fù)?，拓?fù)淇臻g(L,σ(L))簡記為ΣL.

命題1.2 設(shè)L是相容連續(xù)Domain，σ(L)是L上的Scott拓?fù)洌瑒t下列性質(zhì)成立：（1）U?L是Scott開集當(dāng)且僅當(dāng)U=↑U且y∈U??x∈U使得x?y；（2）x?y?↑x是y的一個(gè)鄰域；（3）?U∈σ(L),U=?{?y:y∈U}；（4）{?x:x∈L}是拓?fù)淇臻g(L,σ(L))的一個(gè)基；（5）{?x:x?y}是y的一個(gè)鄰域基；（6）{?x:x∈B}是(L,σ(L))的一個(gè)基，其中B是L的基.

命題1.3 設(shè)L是相容Dcpo，B?L，則B是基??x∈L，Bx=B??x是相容定向集且∨Bx=x.

命題1.4 設(shè)L是相容Dcpo，則L有一個(gè)基當(dāng)且僅當(dāng)L是相容連續(xù)Domain.

命題1.5 若L是相容連續(xù)Domain，B?L，則B是基當(dāng)且僅當(dāng)?x,y∈L,x?y且x≠y時(shí)??b∈B使得x?b?y且x≠b.

定義1.7 若L是相容Dcpo，定義λ(L)=σ(L)∨ω(L)，其中ω(L)是以{L↑x:x∈L}為子基的上區(qū)間拓?fù)?，則λ(L)是以σ(L)?ω(L)為子基的拓?fù)洌?L)稱為L上的Lawson拓?fù)?，記拓?fù)淇臻g(L,λ(L))為ΛL的一個(gè)基.

命題1.6 若L是相容連續(xù)Domain，B是L的基，則{?x↑F:x∈B且F是B的有限子集}是ΛL的一個(gè)基.

命題1.7 設(shè)L是相容Dcpo，則（1）上集U是Lawson開集?它是Scott開集；（2）下集C是Lawson閉集?它對相容定向并封閉.

推論1.1 設(shè)L是相容Dcpo，U∈λ(L)且D是L的相容定向集，則∨D∈U?U?D≠?.

命題1.8 設(shè)L是相容連續(xù)Domain，則U∈λ(L)?↑U∈σ(L).

證明首先，↑U是上集；其次，設(shè)D?L是相容定向集且∨D∈↑U，則?x∈U使得x≤∨D，而x=∨?x，由推論1.1知,?y∈U使y?x，從而?d∈D使得y≤d.這說明d∈↑U，即U?D≠?，所以↑U∈σ(L).

2 相容連續(xù)Domain的特征

定義2.1 設(shè)L是相容連續(xù)Domain.定義W(L)=min{|B|:B是L的一個(gè)基}，則稱W(L)是相容連續(xù)DomainL的權(quán).

定義2.2［5］設(shè)L是相容Dcpo，.若，是相容定向集且，則稱是x的局部基.

定義2.3 設(shè)L是相容連續(xù)Domain，?x∈L，令χ(x,L)=min{|Dx|:Dx是x的局部基}，則稱χ(x,L)為相容連續(xù)DomainL中點(diǎn)x的特征.令χ(L)=supχ(x,L)，x∈L，稱其為相容連續(xù)DomainL的特征.記χ(x,ΣL)為拓?fù)淇臻gΣL中點(diǎn)x的特征，χ(ΣL)為拓?fù)淇臻gΣL的特征，記χ(x,ΛL)為拓?fù)淇臻gΛL中點(diǎn)x的特征，χ(ΛL)為拓?fù)淇臻gΛL的特征.

定義2.4 設(shè)L是相容連續(xù)Domain，若χ(L)≤ω，則稱L是第一可數(shù)的相容連續(xù)Domain.

命題2.1 設(shè)L是相容Dcpo，a∈L.則下列性質(zhì)成立：（1）若a有局部基，則?a是a的最大局部基；（2）若a?a且Da是a的局部基，則a∈Da；（3）若a?a，則{a}是a的最小局部基，即χ(a，L)=1，（4）若b≤a且Da，Db分別是a，b的局部基，則Db??Da.

定理2.1 設(shè)L是相容連續(xù)Domain，a∈L且D??a.則D是a的局部基當(dāng)且僅當(dāng)?c∈?a且c≠a，?d∈D使得c?d且c≠d.

證明必要性.?c∈?a且c≠a，由L是相容連續(xù)Domain知,?x∈L，使得c?x?a且x≠c.又因?yàn)镈是a的局部基，則∨D=a，所以?d∈D使得c?d且c≠d.

充分性.先證明D是相容定向集.設(shè)d1,d2∈D，di?a(i=1,2).由?a的定向性知,?d3?a使得di≤d3(i=1,2).又由條件?d∈D使得d3?d且d3≠d，則?d∈D使得di

定理2.2 設(shè)L是相容連續(xù)Domain，a∈L且D??a.則D是a的局部基當(dāng)且僅當(dāng)D是相容定向集且?x∈L，若a?x，則?d∈D使得d?x.

證明必要性.顯然D是相容定向集.又由∨D=a知，若a?x，則?d∈D使得d?x.

充分性.證明∨D=a即可.顯然∨D≤a.a?∨D，由條件?d∈D使得d?D，矛盾！故∨D=a，所以D是a的局部基.

定理2.3 設(shè)L是相容連續(xù)Domain，a∈L且D??a.則D是a的局部基當(dāng)且僅當(dāng)D是相容定向集且?x∈L，若x∈?a且x≠a，則?d∈D使得x

證明必要性.由定理2.1即知.

充分性.先證明D是相容定向集.設(shè)d1,d2∈D，di?a(i=1,2).由?a的定向性知,?d3?a使得di≤d3(i=1,2).又由條件?d∈D使得d3

定理2.4 設(shè)L是相容連續(xù)Domain，則χ(L)≤W(L).

證明設(shè)B是相容連續(xù)DomainL的基，且|B|=W(L).?x∈L，令Bx=B??x，則由命題1.3與命題1.4知,Bx是相容定向集且x=∨Bx，故Bx是x的局部基，從而χ(x,L)≤|Bx|≤|B|=W(L).由x的任意性知,χ(L)≤W(L).

定理2.5 設(shè)L是相容連續(xù)Domain，則χ(L)=χ(ΣL).

證明先證明χ(ΣL)≤χ(L).?x∈L，存在x的局部基D使得|D|≤χ(L).令β={?y:y∈D}.下面證明β為ΣL中x的一個(gè)鄰域基.首先β?σ(L)；其次?U∈σ(L)，若x∈U，則∨D∈U.從而?d∈U?D使得x∈?d?U，故β是x的鄰域基.則χ(x,ΣL)≤|D|≤χ(L).由x的任意性知,χ(ΣL)≤χ(L).再證明χ(L)≤χ(ΣL).?x∈L，存在ΣL中x的一個(gè)鄰域基β使得|β|≤χ(L).?U∈β，由x∈U且U是Scott開集知，?y∈U使得x∈?y?↑y?U.取一個(gè)這樣的y記作yU，設(shè)D={yU:U∈β}.下證D是x的一個(gè)鄰域基.首先由D中元素的取法知,D??x；其次?z∈L，若z?x且z≠x，則有x∈?z且z≠x.由β是x的鄰域基知，?U∈β使得x∈U??z且z≠x.又因?yàn)閁是Scott開集，?y∈U使得x∈?y?↑y?U??z.從而?yU∈D使得z?yU且z≠yU.否則若z=yU，U是存在的但與它的任意性不符，矛盾！由定理2.1知,D是相容連續(xù)DomainL中點(diǎn)x的鄰域基.故χ(x,L)≤|D|≤|β|≤χ(L).由x的任意性知,χ(L)≤χ(ΣL).從而在相容連續(xù)DomainL中χ(L)=χ(ΣL).

命題2.1 設(shè)L是相容連續(xù)Domain，則L是第一可數(shù)的相容連續(xù)Domain當(dāng)且僅當(dāng)ΣL是第一可數(shù)的拓?fù)淇臻g.

定理2.6 設(shè)L是相容連續(xù)Domain，則χ(ΣL)≤χ(ΛL).

證明?x∈L，存在ΛL中點(diǎn)x的鄰域基β使得|β|≤χ(ΛL)′，令β′={↑U:U∈β}.由命題1.7知β′?σ(L)，且易證β′為 ΣL中x的一個(gè)鄰域基，則χ(x,ΣL)≤|β′|≤|β|≤χ(ΛL).由x的任意性知,χ(ΣL)≤χ(ΛL).

3 相容連續(xù)Domain的濃度

定義3.1 設(shè)L是相容連續(xù)Domain，A?L.若?x∈L及?y∈?x，?a∈A使得y?a，則稱A為L的稠密子集.

命題3.1 設(shè)L是相容連續(xù)Domain，A?L.則A為L的稠密子集當(dāng)且僅當(dāng)?x,y∈L，當(dāng)x?y時(shí)，?a∈A使得x?a.

定義3.2 設(shè)L是相容連續(xù)Domain，令d(L)=min{|A|:A是L的稠密子集}，則稱d(L)為相容連續(xù)Do?mainL的濃度.特別地，若d(L)≤ω，則稱相容連續(xù)DomainL是可分的.

下面用d(ΣL)與d(ΛL)分別表示拓?fù)淇臻g(L,σ(L))與(L,λ(L))的濃度.

定理3.1 設(shè)L是相容連續(xù)Domain，則d(L)≤W(L).

證明證明基是稠密子集即可.設(shè)B是L的基，?x,y∈L，若x?y且x≠y，則由命題1.5知,?b∈B使得x?b?y且x≠b.若x=y時(shí)，由基的定義知,?b∈B使得b=x，再由命題3.1知B是L的稠密子集.

定理3.2 設(shè)L是相容連續(xù)Domain，則d(L)=d(ΣL)≤d(ΛL).

證明設(shè)A為相容連續(xù)DomainL的一個(gè)稠密子集且d(L)=|A|.?U∈σ(L)且U≠?，由命題1.2知?x,y∈U使得x?y，由命題3.1知?a∈A使得x?a，又U是上集，則a∈U，即A?U≠?，所以A在ΣL中稠密，故d(L)≤d(ΣL).反之，設(shè)A在ΣL中稠密，且d(ΣL)=|A|.?x,y∈L，若x?y，則y∈?x.又?x是Scott開的，所以A??x≠? ，即 ?a∈A使得x?a.由命題3.1知,A為L的一個(gè)稠密子集.則d(L)≤|A|≤d(ΣL).又σ(L)?λ(L)，所以d(ΣL)≤d(ΛL)，即d(L)=d(ΣL)≤d(ΛL).

推論3.1 設(shè)L是相容連續(xù)Domain，則d(ΣL)≤W(L).

推論3.2 設(shè)L是相容連續(xù)Domain，則L是可分的相容連續(xù)Domain當(dāng)且僅當(dāng)ΣL是可分空間.

定理3.3 設(shè)L是含最小元相容連續(xù)Domain，則d(ΛL)≤W(L).

證明令0是L中的最小元，B是L的基且|B|=W(L)，則必有0∈B.由定理3.1的證明知B是L的稠密子集，再由定理3.2知,B也是ΣL的一個(gè)稠密子集.要證明B在ΛL中稠密，只需證明?L↑F≠?，其中F是L的有限子集，B?(L↑F)≠?.因?yàn)長↑F≠? 且是下集，所以 0∈L↑F，從而B?(L↑F)≠?.

定理3.4 設(shè)L是含最小元相容連續(xù)Domain，則d(ΛL)≤d(L)+1.

證明由定理3.2的證明過程即知,A在L中稠密當(dāng)且僅當(dāng)A在ΣL中稠密.所以若A在L稠密且d(L)=|A|，則A在ΣL中也稠密，從而A?{0}在ΣL中也稠密.由于0∈A?{0}，所以由定理3.3的證明知A?{0}在下拓?fù)渲谐砻?，因而A?{0}在ΛL中稠密.則d(ΛL)≤|A?{0}|≤|A|+1=d(L)+1.

推論3.3 若L有最小元，則L是可分相容連續(xù)Domain當(dāng)且僅當(dāng)ΛL是可分空間.

［1］ABRAMSKY S，JUNG A.Domain thory［M］.New York：Oxford University Press，1994.

［2］徐羅山.相容連續(xù)偏序集及其定向完備化［J］.揚(yáng)州大學(xué)學(xué)報(bào)，2000（1）：1-6.

［3］趙彬.連續(xù)Domain的基與權(quán)［J］.工程數(shù)學(xué)學(xué)報(bào)，2000，17（4）：91-95.

［4］趙彬，劉妮.連續(xù)Domain的特征與濃度［J］.陜西師范大學(xué)學(xué)報(bào)，2002，30（2）：1-6.

［5］何為民.相容連續(xù)Domain的不變性［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26（2）：211-214.

［6］GIERZ G.Continous lattices and domains［M］.Cambridge:Cambridge University Press，2003.

Characteristic and Density of Consistently Continuous Domain

ZHANG Peng-yao，JIANG Guang-hao，LI Hai-long，ZHAN Shi-yuan
（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）

The definitions of weight，dense set，characteristic and density of consistently continuous Domain are given first,and some characteristic theorems are obtained.In addition，the relations between the character?istic and density of a consistently continuous Domain and that of the related topological space with Scott to?pology or Lawson are discussed.It is concluded that the characteristic and density of consistently continuous Domain and those on the related space with Scott topology are consistent，less than that of the related space with Lawson topology respectively.

consistently continuous Domain；local basis；characteristic；density；Scott topology；Lawson topolo?gy

O 189.1；O 153.1

：A

：2095-0691（2014）01-0012-04

2013-11-04

國家自然科學(xué)基金資助項(xiàng)目（11001001）；安徽省教育廳自然科學(xué)基金資助項(xiàng)目（KJ2013A236）

張鵬垚（1990- ），男，甘肅天水人，碩士生，主要從事Domain理論的研究；通訊作者：姜廣浩（1973- ），男，江蘇沛縣人，博士，副教授，主要從事一般拓?fù)鋵W(xué)的研究.