相對(duì)交連續(xù)半格及其等價(jià)刻畫(huà)

陳必琴，姜廣浩①

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

0 引言

Domain理論為計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的指稱(chēng)語(yǔ)義學(xué)奠定數(shù)學(xué)基礎(chǔ)，屬于格論、拓?fù)鋵W(xué)、范疇論及理論計(jì)算機(jī)科學(xué)為基礎(chǔ)的交叉學(xué)科，而連續(xù)Domain是Domain理論中的重要研究對(duì)象［1-7］.而作為Domain理論的重要理論特殊元理論，是眾多學(xué)者研究的熱門(mén)話題.文獻(xiàn)［8-9］對(duì)偏序集上的弱理想的研究取得豐富的成果，文獻(xiàn)［10-11］對(duì)偏序集上的局部極大理想和濾子極大理想的探究也取得不錯(cuò)成績(jī).近年來(lái)，這方面的研究得到一些好的結(jié)果［11-15］.文獻(xiàn)［16-17］將經(jīng)典概念定向集推廣為一致集，引入并探討一致連續(xù)偏序集.文獻(xiàn)［18］利用相對(duì)的思想引入相對(duì)定向集的概念，探討相對(duì)連續(xù)偏序集及其性質(zhì)［18-20］.作為Domain理論中交連續(xù)半格這一經(jīng)典概念的自然推廣，本文首先引入相對(duì)輔助關(guān)系的概念，研究其在給定的集合T中的一些性質(zhì)；然后利用相對(duì)輔助關(guān)系定義相對(duì)逼近輔助關(guān)系的概念.此外給出相對(duì)交連續(xù)半格的概念，并得到其若干內(nèi)部刻畫(huà).最后探討相對(duì)連續(xù)Domain及其若干拓?fù)湫再|(zhì)，并研究相對(duì)連續(xù)半格與相對(duì)交連續(xù)半格之間的關(guān)系.

1 預(yù)備知識(shí)

設(shè)P為偏序集，記↓X={y∈P:?x∈X,y≤x}，↑X={y∈P:?x∈X,x≤y}，↓x=↓{x}，↑x=↑{x}.X?P，稱(chēng)X為下集當(dāng)且僅當(dāng)X=↓X；X為上集當(dāng)且僅當(dāng)X=↑X.設(shè)X?P，X≠?，若?x,y∈X，?z∈X使得x,y≤z，則稱(chēng)X是P的定向子集.設(shè)X?P，X為理想當(dāng)且僅當(dāng)X既是下集又是定向集.記P所有的理想構(gòu)成的集合為Idl(P).若對(duì)于任意定向子集D，supD存在且supD∈D，則稱(chēng)P是定向完備的.簡(jiǎn)記為dcpo.

定義1［2］若偏序集L上的二元關(guān)系"?"滿(mǎn)足：

（1）x?y?x≤y.

（2）u≤x?y≤z?u?z.

（3）若最小元0存在?0?x.

稱(chēng)"?"為輔助關(guān)系，全體"?"記為Aux(L).

定義2［18］設(shè)L是偏序集，S,T?L,S≠?，若?x,y∈S，存在t∈T，使得x≤t,y≤t，則稱(chēng)S為偏序集L上相對(duì)于T的定向集.當(dāng)T明了時(shí)，簡(jiǎn)稱(chēng)S為相對(duì)定向集.記U(T)={S:S為相對(duì)于T的定向集}.

定義3［18］設(shè)L是偏序集，I,T?L,I≠?,T≠?，若I相對(duì)于T定向且I為下集，則稱(chēng)I是偏序集L上相對(duì)于T的理想，當(dāng)T明確給定時(shí)，簡(jiǎn)稱(chēng)I為相對(duì)理想.記RIdl(T)={I:I為相對(duì)于T的理想}.

定義4［18］設(shè)L是偏序集，T?L,T≠?，若任意相對(duì)于T的定向集S,L都有最小上界supS，則稱(chēng)L為相對(duì)于T的定向完備集；當(dāng)T明了時(shí)，則稱(chēng)L為相對(duì)定向完備集，記為RDCPO(T).

定義5［18］設(shè)L是偏序集，T?L,T≠?，L為相對(duì)于T的定向完備集，?x,y∈L，若對(duì)于任意相對(duì)于T的定向集D，當(dāng)y≤supD時(shí)，?s∈D，使x≤s,則稱(chēng)x在L上相對(duì)于T雙小于y，當(dāng)T明確給定時(shí)，記為x＜＜T y.若x＜＜T x成立，則稱(chēng)x為L(zhǎng)上相對(duì)于T的緊元，當(dāng)T明確給定時(shí)，稱(chēng)為x為相對(duì)緊元.記?T x={u:x＜＜Tu},?T x={v:v＜＜T x}.

定義6［18］設(shè)L是偏序集，T?L,T≠?，U?T，若U滿(mǎn)足：

（1）U=↑TU={z∈T:?x∈U,x≤z}；

（2）對(duì)于L中的任意相對(duì)于T的定向集D，當(dāng)supD∈U時(shí)，?d∈D使得d∈U，則稱(chēng)U是L的相對(duì)T的Scott開(kāi)集，當(dāng)T明確給定時(shí)，簡(jiǎn)稱(chēng)為相對(duì)Scott開(kāi)集.令σT(L)={U?L:U為L(zhǎng)的相對(duì)于T的scott開(kāi)集}，則σT(L)為T(mén)的一個(gè)拓?fù)?，稱(chēng)它為L(zhǎng)上相對(duì)于T的Scott拓?fù)?，?dāng)T明確給定時(shí)，簡(jiǎn)稱(chēng)為相對(duì)scott拓?fù)?

2 相對(duì)交連續(xù)定向完備半格

首先來(lái)定義相對(duì)輔助關(guān)系，再依賴(lài)此定義展開(kāi)其他研究.

定義7設(shè)L是偏序集，T?L,T≠?，L為相對(duì)于T的定向完備集，對(duì)于任意u,x,y,z∈T，若L上的二元關(guān)系"?T"滿(mǎn)足：

（1）x?T y?x≤y；

（2）u≤x?T y≤z?u?T z；

（3）若L上有最小元0存在?0?T x.

稱(chēng)"?T"為相對(duì)輔助關(guān)系，全體"?T"記為RAux(L).

命題1二元關(guān)系"?T"滿(mǎn)足下列兩條性質(zhì)：

（1）反對(duì)稱(chēng)性：?a,b∈L，若a?Tb,b?Ta,有a≤b,b≤a,即a=b；

（2）傳遞性：?a,b,c∈L，若a?Tb,b?Tc,有a≤b,b?Tc,即a?Tc.

例1設(shè)L是連續(xù)偏序集，T?L,T≠?，L為相對(duì)于T的定向完備集，則L上的"≤T"，"＜＜T"為相對(duì)輔助關(guān)系.

定義8在dcpo L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，L上的相對(duì)輔助關(guān)系"?T"稱(chēng)為相對(duì)逼近關(guān)系當(dāng)且僅當(dāng)集合{u∈T:u?T x}=s?T(x)是定向的，且?x∈L,x=sup{u∈T:u?T x}=sups?T(x)，所有的相對(duì)逼近輔助關(guān)系記為RApp(L).在偏序集中"≤T"是相對(duì)逼近輔助關(guān)系，Domain中"＜＜T"為相對(duì)逼近輔助關(guān)系.

命題2在dcpo L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，"?T"為L(zhǎng)上的輔助關(guān)系，則下列條件等價(jià)：

（1）"?T"為相對(duì)逼近的；

（2）?x,y∈L，若x■y，則?z?T x使z■y.

證明（1）?（2）反證法：若?z?T x，有z≤y，則z∈s?T(x)，從而sups?T(x)≤y，由（1）x≤y，矛盾.

（2）?（1）?y∈L，顯然sups?T(y)≤y.設(shè)sups?T(y)=x，若y■x，由（2）知，?t?T y,t■x，矛盾.故y≤x，即y=sups?T(y)=sup{u:u?T y}，故"?T"是相對(duì)逼近的.

定義9設(shè)L是定向完備半格，若?x∈L，T,D?L,D≠?，D為L(zhǎng)上相對(duì)于T的定向集，滿(mǎn)足xsupD=supxD，則稱(chēng)L是相對(duì)交連續(xù)的半格.

下面給出相對(duì)交連續(xù)定向完備半格的若干等價(jià)刻畫(huà).

定理1在定向完備半格L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，則下列條件等價(jià)：

（1）相對(duì)理想的并映射I→supI:RIdl→L是一個(gè)并半格同態(tài)；

（2）對(duì)于相對(duì)理想I1,I2，有( s upI1)( s upI2)=supI1I2；

（3）對(duì)于相對(duì)定向集D1,D2，有( s upD1)(s upD2)=supD1D2；

（4）L是相對(duì)交連續(xù)的；

（5）?相對(duì)定向集D和?x≤supD，有x≤supxD；

（6）交運(yùn)算(x,y)→xy:L×L→L保相對(duì)定向并.

證明（1）?（2）?I1,I2∈RIdl，由（1）的并映射同態(tài)，有( s upI1)∧( s upI2)=sup(I1∧I2)=sup(I1I2).

（2）?（1）?I1,I2∈RIdl，( s upI1)∧( s upI2)=sup(I1∧I2)，即并映射同態(tài).

（2）?（3）?兩個(gè)相對(duì)定向集D1,D2，需證( s upD1)(s upD2)=sup(D1D2)，對(duì)D1,D2同時(shí)取下集↓D1,↓D2，

此 時(shí)↓D1,↓D2為 相 對(duì) 理 想，由（2）得，( s up↓D1)(s up↓D2)=sup(↓D1↓D2)，下 證sup(↓D1↓D2)=sup(D1D2).

一 方 面，D1?↓D1,D2?↓D2，故D1D2?↓D1↓D2,sup(D1D2)≤sup(↓D1↓D2).令c=sup(D1D2),e=sup(↓D1↓D2)，則c≤e；?f∈↓D1↓D2,則?d1∈D1,d2∈D2,使f≤d1,f≤d2,有f≤d1d2≤supD1D2=c，故c為↓D1↓D2的一個(gè)上界，又e為↓D1↓D2的上確界，即最小上界，故e≤c，即e=c.

另一方面，因?yàn)樽陨硇院蛡鬟f性，D1和↓D1有相同的上界.設(shè)a=supD1，b=sup↓D1，由D1?↓D1，有supD1≤sup↓D1，即a≤b.又?d∈↓D1,?d1∈D1，使d≤d1≤supD1=a，即d≤a，從而a為↓D1的上界，又b為↓D1的最小上界，故b≤a，即a=b,則supD1=sup↓D1.同理supD2=sup↓D2.

綜上，( s upD1)( s upD2)=sup(D1D2)成立.

（3）?（2）因?yàn)橄鄬?duì)理想為相對(duì)定向集，故（2）成立.

（3）?（4）令D1={x},D2=D，則( s upD1)( s upD2)=xsupD,supD1D2=supxD，從而xsupD=supxD，故（4）成立.

（4）?（5）由（4），L為相對(duì)交連續(xù)，D為相對(duì)定向集，滿(mǎn)足xsupD=supxD.?相對(duì)定向集D，若x≤supD，兩邊同時(shí)取交，x∧x≤x∧supD，即x≤xsupD.

（5）?（6）設(shè)D?T，D?L×L是相對(duì)于T的定向集，且集Dn=πnD,n=1,2,…，那么D?D1×D2.另一方面，(d,e)∈D1×D2，?x,y∈L，(d,y),(x,e)∈D，因D相對(duì)定向，(d*,e*)∈T，有(d*,e*)∈↓D，由(d,e)≤(d*,e*)，有(d,e)∈↓D，從而D1×D2?↓D.

設(shè)m:L×L→L,m(x,y)=xy，則

m(D)?m(D1×D2)=D1D2?m(↓D)?↓m(D)，

故supm(D)≤supD1D2≤sup↓m(D)=supm(D)，即supm(D)=supD1D2.

令d1=supD1,d2=supD2，則(

d1,d2)=supD.

下證d1d2=supD1D2，?x∈D1，有xd2≤supD2，因此xd2=supxd2D2=supxD2，又d1d2≤supD1，即d1d2=supd1d2D=supD1d2，那么

即( s upD1)( s upD2)=supD1D2，則∧supD=sup∧D，即m(s upD)=supm(D).

（6）?（3）顯然.

定義10在dcpo L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，?I∈RIdL，定義

命題3在相對(duì)交連續(xù)半格L中，?I∈RIdL，所有屬于函數(shù)mI的關(guān)系都是相對(duì)逼近的.

證 明設(shè)x∈L，若x≤supI，則 由 定 理1有，supmI(x)=supxI=xsupI=x；若x■supI，則supmI(x)=sup↓T x=x.

定理2在定向完備半格L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，所有的相對(duì)逼近輔助關(guān)系包含"＜＜T"關(guān)系.若L為相對(duì)交連續(xù)半格，則"＜＜T"?相對(duì)逼近輔助關(guān)系的交，即?T x=s＜＜T(x)=?{s?T(x):?T∈RApp(L)}.

證明設(shè)y＜＜T x，"＜＜T"是相對(duì)逼近輔助關(guān)系，有{u∈L:u?T x}是相對(duì)于T的定向集，且上確界為x，則?u，有y≤u?T x，因此y?T x，即＜＜T??T.

另一方面，若L為相對(duì)交連續(xù)半格，由命題3有?T x=?{mI(x):I∈RIdL}??{s?T:?T∈RAPP(L)}.

定義11L為偏序集，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，若L上的相對(duì)逼近輔助關(guān)系滿(mǎn)足：?x,z∈L,x?T z且x≠z??y,有x?T y?T z且x≠y，則"?T"具有強(qiáng)插值性質(zhì)；?x,z∈L,x?T z??y,x?T y?T z，則"?T"具有插值性質(zhì).

定理3在定向完備半格L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，若L上的相對(duì)逼近輔助關(guān)系滿(mǎn)足：?x,z∈L,x?T z且x≠z??y,x≤y?T z且x≠y.

證明?z∈L,z=sup{u∈L:u?T z}=sups?T(z)，有u?T z,u■x.當(dāng)s?T(z)={u∈L:u?T z}是相對(duì)定向時(shí)，由u■x,x≠y,則?{x,u}的一個(gè)上界y，有y?T z.

定理4在定向完備半格L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，若"?T"為L(zhǎng)上的相對(duì)逼近輔助關(guān)系，則下列條件成立：

（1）若x＜＜T z,x≠z且z≤supD，D為相對(duì)定向集，則?d∈D,x?Td,x≠d；

（2）若x＜＜T z且x≠z，則?y，使得x?T y?T z，且x≠y.

證明（1）任取D∈U(T)，因L為相對(duì)于T的定向完備集，故supD存在，且滿(mǎn)足z≤supD.

令I(lǐng)=?{s?T(d):d∈D}，且supI=sup{s ups?T(d):d∈D}=supD，故z≤supI，又x＜＜T z，則x∈I.即?d∈D,有x?Td.

（2）令D=s?T(z)={y∈L:y?T z}，z=sups?T(z)=supD.若x＜＜T z且x≠z，由（1），?y∈D,有x?T y且y≠x，則x?T y?T z.

由定理4可得如下結(jié)論.

推論1在相對(duì)連續(xù)Domain中，相對(duì)way below關(guān)系滿(mǎn)足強(qiáng)插值性質(zhì).

3 相對(duì)連續(xù)Domain

定義12設(shè)L為偏序集，T?L,T≠?，且L為相對(duì)于T的定向完備集，若?x∈L，x=sup↑?T x，則稱(chēng)L為相對(duì)于T的連續(xù)偏序集.當(dāng)T明了時(shí)，簡(jiǎn)稱(chēng)L是相對(duì)連續(xù)偏序集.若L為dcpo，則稱(chēng)L為相對(duì)于T的Domain.若相對(duì)DomainL是半格，則稱(chēng)L為相對(duì)連續(xù)半格.↑?T表示相對(duì)定向雙下集.

定理5相對(duì)連續(xù)半格是相對(duì)交連續(xù)半格.

證明設(shè)L是相對(duì)連續(xù)半格，T?L,T≠?，D是相對(duì)于T的定向集，且x≤supD，由定理1中（5），要證x≤supxD，即證?T x??supxD?↓supxD.事實(shí)上，?y∈?T x，有y＜＜T x，從而y≤x.又?z∈D使y≤z，從而y≤xz∈xD，則y≤supxD，即y∈↓supxD，綜上?T x?↓supxD，故x≤supxD.

定理6在dcpo L中，設(shè)T?L,T≠?，L為相對(duì)于T的定向完備集，下列條件等價(jià)：

（1）L相對(duì)連續(xù)Domain；

（2）＜＜T是最小的相對(duì)逼近輔助關(guān)系；

（3）L上有最小的相對(duì)逼近輔助關(guān)系.

證明（1）?（2）由L是相對(duì)連續(xù)Domain知，"＜＜T"是相對(duì)逼近輔助序，所以?T x是相對(duì)理想.又由{s?T(x):?T是相對(duì)逼近的}?{I∈RIdL:x≤supI},所 以?{s?T(x):?T是相對(duì)逼近的}??{I∈RIdL:x≤supI}=?T x.又 因"＜＜T"是 相 對(duì) 逼 近 的，則?T x∈{s?T(x):?T是相對(duì)逼近的}，所 以?T x=?{s?T(x):?T是相對(duì)逼近的}.

（2）?（3）顯然.

（3）?（1）若L有最小的相對(duì)逼近輔助序M，下證?x∈L，M=?T x.事實(shí)上，M??{I∈RIdL:x≤supI}=?T x?M,從而有M=↑?T x，所以L是相對(duì)連續(xù)Domain.

下面給出相對(duì)連續(xù)Domain中Scott開(kāi)集的若干性質(zhì).

定理7若L是相對(duì)連續(xù)Domain，T?L,T≠?，?T x?T，則下列條件成立：

（1）?x∈L，集合?T x是相對(duì)于T的Scott開(kāi)集；

（2）若L是定向dcpo且y∈int(↑T x)，則x＜＜T y.

證明（1）因?T x是L上相對(duì)于T的上集，只需證定義6中的（2）.設(shè)D為相對(duì)于T的定向集，且supD∈?T x，則x＜＜TsupD.又L為 相 對(duì) 連 續(xù)Domain，?d∈D，使 得x＜＜Td，即d∈?T x，故D??T x≠?，?T x為相對(duì)Scott開(kāi)集.

（2）若L是dcpo且y∈int(↑T x)，設(shè)D是L上相對(duì)于T的定向集，且y≤supD，故supD∈↑y?int(↑T x)，D?int(↑T x)≠?.從而?d∈D，有d∈int(↑T x)?↑T x，有x≤Td，即x≤d，故x＜＜T y.

定理8設(shè)L是相對(duì)連續(xù)Domain，則下列條件成立：

（1）上集U是相對(duì)T的Scott開(kāi)集??x∈U，?u∈U，使得u＜＜T x；

（2）{?Tu,u∈L}構(gòu)成σT(L)的一個(gè)基；

（3）在σT(L)中，有int(↑T x)=?T x.

證明（1）?設(shè)T?L,T≠?，上集U是相對(duì)于T的Scott開(kāi)集且x∈U，又L為相對(duì)連續(xù)Domain，有x=sup↑?T x，故sup↑?T x∈U，即?T x?U≠?.從而?u∈U，有u∈?T x，即u＜＜T x.

?若?x∈U，?u∈U，使得u＜＜T x，即x∈?Tu.因U??{?Tu:u∈U}?U，即U=?{?Tu:u∈U}，由定理7（1）知，?T x是Scott開(kāi)的，即U為相對(duì)于T的scott開(kāi)集.

（2）由（1）顯然.

（3）設(shè)T?L,T≠?，因?T x?↑T x，有?T x?int(↑T x).反之，由定理7（2）知，int(↑T x)??T x，故?T x=int(↑T x).