陳必琴，姜廣浩①

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

0 引言

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

1 預(yù)備知識

設(shè)P為偏序集，記↓X={y∈P:?x∈X,y≤x}，↑X={y∈P:?x∈X,x≤y}，↓x=↓{x}，↑x=↑{x}.X?P，稱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，則稱X是P的定向子集.設(shè)X?P，X為理想當(dāng)且僅當(dāng)X既是下集又是定向集.記P所有的理想構(gòu)成的集合為Idl(P).若對于任意定向子集D，supD存在且supD∈D，則稱P是定向完備的.簡記為dcpo.

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

（1）x?y?x≤y.

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

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

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

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

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

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

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

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

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

（2）對于L中的任意相對于T的定向集D，當(dāng)supD∈U時，?d∈D使得d∈U，則稱U是L的相對T的Scott開集，當(dāng)T明確給定時，簡稱為相對Scott開集.令σT(L)={U?L:U為L的相對于T的scott開集}，則σT(L)為T的一個拓?fù)?，稱它為L上相對于T的Scott拓?fù)洌?dāng)T明確給定時，簡稱為相對scott拓?fù)?

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

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

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

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

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

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

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

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

（1）反對稱性：?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為相對于T的定向完備集，則L上的"≤T"，"＜＜T"為相對輔助關(guān)系.

定義8在dcpo L中，設(shè)T?L,T≠?，L為相對于T的定向完備集，L上的相對輔助關(guān)系"?T"稱為相對逼近關(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)，所有的相對逼近輔助關(guān)系記為RApp(L).在偏序集中"≤T"是相對逼近輔助關(guān)系，Domain中"＜＜T"為相對逼近輔助關(guān)系.

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

（1）"?T"為相對逼近的；

（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"是相對逼近的.

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

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

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

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

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

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

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

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

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

證明（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）?兩個相對定向集D1,D2，需證( s upD1)(s upD2)=sup(D1D2)，對D1,D2同時取下集↓D1,↓D2，

此 時↓D1,↓D2為 相 對 理 想，由（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的一個上界，又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)橄鄬硐霝橄鄬Χㄏ蚣剩?）成立.

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

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

（5）?（6）設(shè)D?T，D?L×L是相對于T的定向集，且集Dn=πnD,n=1,2,…，那么D?D1×D2.另一方面，(d,e)∈D1×D2，?x,y∈L，(d,y),(x,e)∈D，因D相對定向，(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為相對于T的定向完備集，?I∈RIdL，定義

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

證 明設(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為相對于T的定向完備集，所有的相對逼近輔助關(guān)系包含"＜＜T"關(guān)系.若L為相對交連續(xù)半格，則"＜＜T"?相對逼近輔助關(guān)系的交，即?T x=s＜＜T(x)=?{s?T(x):?T∈RApp(L)}.

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

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

定義11L為偏序集，設(shè)T?L,T≠?，L為相對于T的定向完備集，若L上的相對逼近輔助關(guā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為相對于T的定向完備集，若L上的相對逼近輔助關(guā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}是相對定向時，由u■x,x≠y,則?{x,u}的一個上界y，有y?T z.

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

（1）若x＜＜T z,x≠z且z≤supD，D為相對定向集，則?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為相對于T的定向完備集，故supD存在，且滿足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在相對連續(xù)Domain中，相對way below關(guān)系滿足強(qiáng)插值性質(zhì).

3 相對連續(xù)Domain

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

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

證明設(shè)L是相對連續(xù)半格，T?L,T≠?，D是相對于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為相對于T的定向完備集，下列條件等價：

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

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

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

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

（2）?（3）顯然.

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

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

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

（1）?x∈L，集合?T x是相對于T的Scott開集；

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

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

（2）若L是dcpo且y∈int(↑T x)，設(shè)D是L上相對于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是相對連續(xù)Domain，則下列條件成立：

（1）上集U是相對T的Scott開集??x∈U，?u∈U，使得u＜＜T x；

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

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

證明（1）?設(shè)T?L,T≠?，上集U是相對于T的Scott開集且x∈U，又L為相對連續(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開的，即U為相對于T的scott開集.

（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).