王武， 譚彬， 張舜

1.天津理工大學(xué) 中環(huán)信息學(xué)院 基礎(chǔ)課部，天津 300380；2.天津理工大學(xué) 理學(xué)院，天津 300384；3.天津仁愛(ài)學(xué)院 數(shù)理教學(xué)部，天津 300163

定向完備偏序集是偏序集理論中的一種重要結(jié)構(gòu), 旨在為計(jì)算機(jī)高級(jí)程序設(shè)計(jì)語(yǔ)言提供數(shù)學(xué)模型, 受到了計(jì)算機(jī)科學(xué)和數(shù)學(xué)領(lǐng)域諸多學(xué)者的關(guān)注, 并得到了很多有價(jià)值的結(jié)論和模型[1-6]． 隨著計(jì)算機(jī)理論的發(fā)展, 偏序集理論不斷向信息科學(xué)、 邏輯學(xué)、 分析學(xué)及各種應(yīng)用學(xué)科滲透[7-8]． Domain理論研究的一個(gè)重要方面是盡可能地將連續(xù)格(Domain)推廣到更為一般的格序結(jié)構(gòu)上去, 其中最重要的推廣就是擬連續(xù)Domain． 擬連續(xù)Domain具有很多類似于Domain的良好性質(zhì), 并且在理論計(jì)算機(jī)領(lǐng)域應(yīng)用更廣泛[9]． 文獻(xiàn)[10]給出了擬連續(xù)Domain的擬基的概念, 并研究了擬基的一些性質(zhì)． 連續(xù)Domain的M性質(zhì)與Lawson拓?fù)涞木o性密切相關(guān), 文獻(xiàn)[11]將M性質(zhì)進(jìn)行了推廣, 引入了MF性質(zhì), 并給出了擬連續(xù)Domain為L(zhǎng)awson緊的一個(gè)等價(jià)條件． 文獻(xiàn)[12]在連續(xù)Domain中給出了比M性質(zhì)更強(qiáng)的SM性質(zhì), 同時(shí)研究了具有性質(zhì)SM的連續(xù)Domain與L-Domain的關(guān)系． 本文在此基礎(chǔ)上, 將連續(xù)Domain的M性質(zhì)進(jìn)行推廣, 首先給出M*性質(zhì)的一些結(jié)論, 其次研究了擬連續(xù)Domain中比M*性質(zhì)更強(qiáng)的SM*性質(zhì), 并得到了一些有意義的結(jié)論． 主要結(jié)果有: 給出了擬連續(xù)Domain具有M*性質(zhì)的等價(jià)刻畫; 給出了擬連續(xù)Domain的SM*性質(zhì)的定義, 并說(shuō)明了M*性質(zhì)與SM*性質(zhì)的關(guān)系; 給出了QL-Domain具有SM*性質(zhì)的等價(jià)條件; 給出了兩類具有性質(zhì)SM*的特殊擬連續(xù)Domain． 本文的結(jié)果有助于Domain理論的進(jìn)一步研究．

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

首先, 介紹偏序集中的一些基本概念[13]． 設(shè)L是偏序集,D?L, 如果D中任意兩個(gè)元在D中有上界, 則稱D為定向集． 如果L的每個(gè)定向子集D都有上確界(記為supD), 則稱L為定向完備偏序集． 任給A?L, 記

↑A={x∈L: 存在a∈A, 使得a≤x}

↓A={x∈L: 存在a∈A, 使得x≤a}

若A為單點(diǎn)集{a}, 則有記號(hào)↑A=↑a, ↓A=↓a．

設(shè)L是偏序集,G,H為L(zhǎng)的兩個(gè)非空子集． 如果H?↑G, 則G≤H, 稱這種序關(guān)系為Symth序． 如果對(duì)任意的定向集D?L, supD∈↑H蘊(yùn)含存在d∈D使得d∈↑G, 則稱G逼近H, 記為G?H． 特別地, {y}?H簡(jiǎn)記為y?H,G?{x}簡(jiǎn)記為G?x． 顯然,G?H蘊(yùn)含?h∈H,G?h． 易知上述定義的逼近關(guān)系有如下性質(zhì):

(i)G?H蘊(yùn)含G≤H;

(ii)G≤E?F≤H蘊(yùn)含G?H．

定義1[13]設(shè)L是定向完備偏序集,

(a) 任給子集U?L, 如果U=↑U, 且任意的定向集D?L, supD∈U意味著D∩U≠?, 則稱U為Scott開(kāi)集． 所有的Scott開(kāi)集構(gòu)成一個(gè)拓?fù)? 稱為Scott拓?fù)? 記為σ(L);

(b) 以主濾子的補(bǔ)L↑x為子基生成的拓?fù)浞Q為下拓?fù)? 記為ω(L);

(c) 稱由σ(L)和ω(L)共同加細(xì)的拓?fù)洇?L)∨ω(L)為L(zhǎng)awson拓?fù)? 記為λ(L)．

命題1[13]設(shè)L是擬連續(xù)Domain, 記F={x:F?x}, 則:

(i) ?x∈L,H為L(zhǎng)的有限子集． 如果H?x, 則存在有限集F?L使得H?F?x;

(ii) intσ(L)(↑F)=F, 其中intσ(L)(↑F)表示↑F在Scott拓?fù)洇?L)中的內(nèi)部;

定義2[14]設(shè)L是擬連續(xù)Domain,?w(L)． 如果?x∈L, 集族fin(x)∩是定向集族且↑x=∩F∈fin(x)∩↑F, 則稱是L的擬基．

顯然, 設(shè)L是定向完備偏序集, 則L是擬連續(xù)的當(dāng)且僅當(dāng)L有擬基． 如果K(L)={G∈w(L):G?G}是L的擬基, 則稱L是代數(shù)擬連續(xù)Domain．

2 性質(zhì)M*與性質(zhì)SM*

文獻(xiàn)[15]介紹了擬連續(xù)Domain的M*性質(zhì), 并研究了其與Lawson拓?fù)渚o性的關(guān)系． 本節(jié)首先研究擬連續(xù)Domain的M*性質(zhì), 然后引入SM*性質(zhì)的概念, 并給出性質(zhì)M*與性質(zhì)SM*的關(guān)系以及QL-Domain具有性質(zhì)SM*的等價(jià)條件．

定義3[15]設(shè)L是擬連續(xù)Domain,是L的擬基． 如果?E,F,G,H∈且E?G,F?H, 存在有限集族*?, 使得↑G∩↑H?∪B∈*↑B?↑E∩↑F, 則稱L相對(duì)于擬基具有性質(zhì)M*．

命題2[15]設(shè)L是擬連續(xù)Domain． 則下列條件等價(jià):

(i) ?x,y∈L, ↑x∩↑y是Scott緊的;

(ii)L相對(duì)于所有擬基具有性質(zhì)M*;

(iii)L相對(duì)于某個(gè)擬基具有性質(zhì)M*．

容易驗(yàn)證, 命題2中, ?x,y∈L, ↑x∩↑y是Scott緊的當(dāng)且僅當(dāng)?E,F∈w(L), ↑E∩↑F是Scott緊的, 其直接推論為文獻(xiàn)[15]的推論4.7: 擬連續(xù)DomainL上的Lawson拓?fù)涫蔷o的當(dāng)且僅當(dāng)L是有限生成的且具有性質(zhì)M*．

由定義2知, 任意擬連續(xù)DomainL,w(L)是L的擬基． 如果L相對(duì)于某個(gè)擬基具有性質(zhì)M*, 則由命題2知L相對(duì)于w(L)也具有性質(zhì)M*． 如未特殊說(shuō)明, 本文中的L具有性質(zhì)M*總是指L相對(duì)于w(L)具有性質(zhì)M*．

命題3設(shè)L是擬連續(xù)Domain, 則L具有性質(zhì)M*當(dāng)且僅當(dāng)對(duì)?E,F∈w(L),x,y∈L且E?x,F?y, 存在有限集H∈w(L), 使得↑x∩↑y?↑H?↑E∩↑F．

證 必要性因?yàn)長(zhǎng)是具有性質(zhì)M*的擬連續(xù)Domain, 則由命題2知,L相對(duì)于w(L)具有性質(zhì)M*． 設(shè)E,F,{x},{y}∈w(L), 且E?x,F?y． 由L具有性質(zhì)M*可知, 存在有限集族*?w(L), 使得

↑x∩↑y?∪B∈*↑B?↑E∩↑F

令H=∪B∈*↑B, 有限多個(gè)有限集的并仍然是有限集, 則H為有限集, 且↑x∩↑y?↑H?↑E∩↑F．

充分性?E,F,G,H∈且E?G,F?H, 顯然?g∈G,E?g成立． 同理, ?h∈H,F?h． 由已知條件可知, 存在有限集Hgh∈w(L), 使得

↑g∩↑h?↑Hgh?↑E∩↑F

令

*={Hgh:g∈G,h∈H}

顯然其是有限集族, 則

↑G∩↑H=∪g∈G, h∈H(↑g∩↑h)?∪B∈*↑Hgh?↑E∩↑F

即L相對(duì)于擬基w(L)具有性質(zhì)M*．

由于Smyth序?yàn)轭A(yù)序關(guān)系[16], 下面給出一種具有性質(zhì)M*的特殊的偏序結(jié)構(gòu)． 設(shè)L是偏序集, 令fin(L)={↑F:F∈w(L)}． ?↑E,↑F∈fin(L), 定義二元關(guān)系: ↑E≤↑F當(dāng)且僅當(dāng)↑F?↑E, 即fin(L)上的偏序關(guān)系為反包含序． 本文中涉及到fin(L)中的序關(guān)系總是反包含序． 對(duì)??fin(L), 記

qumb={↑E∈fin(L): ↑E是在fin(L)中的極小上界}

定義4設(shè)L是偏序集, 有限子集族?fin(L)． 如果:

則稱L是qumb-完備的．

命題4設(shè)L是qumb-完備的擬連續(xù)Domain, 則L具有性質(zhì)M*．

證?x,y∈L,E,F∈w(L), 且E?x,F?y, 由L的qumb-完備性知qumb{↑E, ↑F}是有限集族． ?z∈↑x∩↑y, {z}是E,F的上界, 且↑z是↑E和↑F的上界． 由L的qumb-完備性知, 存在↑G∈qumb(↑E, ↑F), 使得z∈↑G． 令

H=∪{G: ↑G∈qumb{↑E, ↑F}}

從而↑x∩↑y?↑H?↑E∩↑F, 由qmub{↑E, ↑F}的有限性和G為有限集知H是有限集, 故由命題3知L具有性質(zhì)M*．

文獻(xiàn)[15]引入了QFS-Domain的概念, 并證明了QFS-Domain具有性質(zhì)M*． 結(jié)合命題4, 說(shuō)明存在一些特殊的偏序結(jié)構(gòu)(如QFS-Domain、 qumb-完備的擬連續(xù)Domain)具有性質(zhì)M*． 接下來(lái), 引入擬連續(xù)Domain的SM*性質(zhì)的概念．

定義5設(shè)L是擬連續(xù)Domain,是L的擬基． 如果?E,F∈, 存在有限集族?且?H∈,H?↑E∩↑F, 使得E∩F=∪H∈H, 則稱L相對(duì)于擬基具有性質(zhì)SM*． 如果L相對(duì)于擬基w(L)具有性質(zhì)SM*, 則簡(jiǎn)稱L具有性質(zhì)SM*．

命題5設(shè)L是擬連續(xù)Domain,是L的擬基． 則L相對(duì)于擬基具有性質(zhì)SM*蘊(yùn)含L具有性質(zhì)M*． 如果L是代數(shù)擬連續(xù)Domain, 則L相對(duì)于擬基(L)具有性質(zhì)SM*當(dāng)且僅當(dāng)L具有性質(zhì)M*．

證設(shè)L相對(duì)于擬基具有性質(zhì)SM*, ?E,F∈,x,y∈L且E?x,F?y, 存在有限集族?, 并且?H∈,H?↑E∩↑F, 使得E∩F=∪H∈H成立． 令H′=∪H∈H, 從而有

↑x∩↑y?E∩F=∪H∈H?∪H∈↑H=↑H′?↑E∩↑F

則由命題3知L相對(duì)于擬基具有性質(zhì)M*． 由命題2知L具有性質(zhì)M*．

如果L是代數(shù)擬連續(xù)的, 只需證明L具有性質(zhì)M*蘊(yùn)含L相對(duì)于(L)具有性質(zhì)SM*． 設(shè)L具有性質(zhì)M*, 則由命題2知L相對(duì)于(L)具有性質(zhì)M*． ?E,F∈(L),E?E,F?F, 存在有限集族*?(L), 使得

E∩F=↑E∩↑F?∪B∈*↑B?↑E∩↑F=E∩F

參考文獻(xiàn)[15]的引理4.8證明了所有的QFS-Domain具有M*性質(zhì)． 由命題5知, 所有的代數(shù)QFS-Domain相對(duì)于擬基(L)具有SM*性質(zhì)．

設(shè)L是定向完備偏序集, 有限集族?fin(L), 記

qmub?={↑G: ↑G∈qmub(),G≠?}

令

H={↑G: ↑G∈fin(L), ↑H?↑G}

如果?H∈w(L),H在反包含序下是完備格(任意子集的上確界存在), 則稱L是QL-Domain．

定理1設(shè)L是qumb-完備的擬連續(xù)QL-Domain． 則下列結(jié)論等價(jià):

(i)L具有性質(zhì)SM*;

(ii) ?E,F∈w(L), qmub?{↑E, ↑F}是有限集族;

證(i)?(ii)設(shè)↑G∈qmub?{↑E, ↑F}, 則↑G∈qmub{↑E, ↑F}且G≠?． 設(shè)G?x, 則E?x,F?x, 即x∈E∩F． 因?yàn)長(zhǎng)具有性質(zhì)SM*, 則存在有限集族∈w(L), 且?H∈,H?↑E∩↑F, 使得E∩F=∪H∈H, 則x∈∪H∈H． 故存在H∈, 使得H?x． 而↑E,↑F∈H, 且↑G為↑E和↑F的極小上界, 同時(shí)H是完備格, 則↑G=↑E∨↑F． 因?yàn)槭怯邢藜? 則qmub?{↑E, ↑F}也是有限集族．

{↑F=∨n: ↑G∈qmub?}

是有限集, 則qmub?也是有限集． 因此由數(shù)學(xué)歸納法知, 對(duì)任意有限集族?fin(L), qmub?是有限集族．

(iii)?(i)?E,F∈w(L), ↑E,↑F∈fin(L), 令

H=qmub?{↑E, ↑F}={↑G∈qmub{↑E, ↑F}:G≠?}

首先如果存在↑G∈qmub{↑E, ↑F}, 使得G?x, 顯然有E?x,F?x, 即

∪H∈H={x: 存在G∈qmub{E,F}, 使得G?x}?E∩F

?x∈E∩F, 有E∨F?x且E∨F∈qmub?{E,F},x∈∪H∈H．

綜上所述, 有∪H∈H=E∩F,L具有性質(zhì)SM*．

3 幾類具有SM*性質(zhì)的特殊擬連續(xù)Domain

下面介紹兩類具有性質(zhì)SM*的特殊的擬連續(xù)Domain:

定義6設(shè)L是擬連續(xù)Domain,是L的擬基． 若存在由有限集作為元素的有限集族i(i∈I)滿足:

(b) ?i∈I,E,F∈i,x∈E∩F, 存在H∈i, 使得H?↑E∩↑F且H?x．

定理2設(shè)L是擬連續(xù)Domain,?w(L)是有限集族． 則?E,F∈,x∈E∩F, 存在H∈, 使得H?↑E∩↑F且H?x, 當(dāng)且僅當(dāng)D={↑F:F∈∩fin(x)}在反包含序下存在最大元．

證?E,F∈,x∈E∩F, 存在H∈, 使得H?↑E∩↑F且H?x, 則↑H是↑E和↑F在D中的上界, 從而D是有限的定向集, 則必有最大元． 反之, 若D存在最大元↑H′, ?E,F∈,x∈E∩F, 則↑E,↑F∈D, 故H′?↑E∩↑F且H′?x．

定理3設(shè)L是擬連續(xù)Domain,是L的擬雙有限基, 則L相對(duì)于具有性質(zhì)SM*．

證設(shè)?E,F∈,E?x,F?x． 由于是L的擬雙有限基, 則存在由有限集作為元素的有限集族i(i∈I), 使得:

(ii) 存在H∈i, 使得H?↑E∩↑F且H?x, 則E∩F?∪i∈IH．

反之, 若x∈∪i∈IH, 存在H∈i使得H?x對(duì)某個(gè)i成立, 且x∈E∩F, ∪i∈IH?E∩F． 則∪i∈IH=E∩F,L相對(duì)于具有性質(zhì)SM*．

定理4設(shè)L是擬連續(xù)Domain, 如果對(duì)任意有限集E,F?L,E∩F是Scott拓?fù)涞木o子集, 則L具有SM*性質(zhì)．

證設(shè)有限集E,F?L． ?x∈E∩F, 由于E∩F是Scott開(kāi)集, 則存在有限集Hx使得x∈Hx?E∩F, 則={Hx:x∈Hx?E∩F}是E∩F的開(kāi)覆蓋, 則存在有限多個(gè)H1,…,Hn∈是E∩F的開(kāi)覆蓋, 則x∈∪iHi．

反之, ?y∈∪iHi, 存在i使得Hi?y,y∈E∩F． 從而E∩F=∪iHi,L具有SM*性質(zhì)．

本文給出了比M*性質(zhì)更強(qiáng)的SM*性質(zhì), 并給出了一些具有SM*性質(zhì)的特殊擬連續(xù)Domain, 并說(shuō)明了在代數(shù)情形下, SM*性質(zhì)與M*性質(zhì)等價(jià), 同時(shí)給出了一種新的偏序結(jié)構(gòu)QL-Domain以及其具有SM*性質(zhì)的等價(jià)條件． 本文的結(jié)論有助于Domain理論的進(jìn)一步研究．