拟连续Domain的SM*性质①

王武， 谭彬， 张舜

1.天津理工大学 中环信息学院 基础课部，天津 300380；2.天津理工大学 理学院，天津 300384；3.天津仁爱学院 数理教学部，天津 300163

定向完备偏序集是偏序集理论中的一种重要结构, 旨在为计算机高级程序设计语言提供数学模型, 受到了计算机科学和数学领域诸多学者的关注, 并得到了很多有价值的结论和模型[1-6]． 随着计算机理论的发展, 偏序集理论不断向信息科学、 逻辑学、 分析学及各种应用学科渗透[7-8]． Domain理论研究的一个重要方面是尽可能地将连续格(Domain)推广到更为一般的格序结构上去, 其中最重要的推广就是拟连续Domain． 拟连续Domain具有很多类似于Domain的良好性质, 并且在理论计算机领域应用更广泛[9]． 文献[10]给出了拟连续Domain的拟基的概念, 并研究了拟基的一些性质． 连续Domain的M性质与Lawson拓扑的紧性密切相关, 文献[11]将M性质进行了推广, 引入了MF性质, 并给出了拟连续Domain为Lawson紧的一个等价条件． 文献[12]在连续Domain中给出了比M性质更强的SM性质, 同时研究了具有性质SM的连续Domain与L-Domain的关系． 本文在此基础上, 将连续Domain的M性质进行推广, 首先给出M*性质的一些结论, 其次研究了拟连续Domain中比M*性质更强的SM*性质, 并得到了一些有意义的结论． 主要结果有: 给出了拟连续Domain具有M*性质的等价刻画; 给出了拟连续Domain的SM*性质的定义, 并说明了M*性质与SM*性质的关系; 给出了QL-Domain具有SM*性质的等价条件; 给出了两类具有性质SM*的特殊拟连续Domain． 本文的结果有助于Domain理论的进一步研究．

1 预备知识

首先, 介绍偏序集中的一些基本概念[13]． 设L是偏序集,D⊆L, 如果D中任意两个元在D中有上界, 则称D为定向集． 如果L的每个定向子集D都有上确界(记为supD), 则称L为定向完备偏序集． 任给A⊆L, 记

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

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

若A为单点集{a}, 则有记号↑A=↑a, ↓A=↓a．

设L是偏序集,G,H为L的两个非空子集． 如果H⊆↑G, 则G≤H, 称这种序关系为Symth序． 如果对任意的定向集D⊆L, supD∈↑H蕴含存在d∈D使得d∈↑G, 则称G逼近H, 记为G≪H． 特别地, {y}≪H简记为y≪H,G≪{x}简记为G≪x． 显然,G≪H蕴含∀h∈H,G≪h． 易知上述定义的逼近关系有如下性质:

(i)G≪H蕴含G≤H;

(ii)G≤E≪F≤H蕴含G≪H．

定义1[13]设L是定向完备偏序集,

(a) 任给子集U⊆L, 如果U=↑U, 且任意的定向集D⊆L, supD∈U意味着D∩U≠∅, 则称U为Scott开集． 所有的Scott开集构成一个拓扑, 称为Scott拓扑, 记为σ(L);

(b) 以主滤子的补L↑x为子基生成的拓扑称为下拓扑, 记为ω(L);

(c) 称由σ(L)和ω(L)共同加细的拓扑σ(L)∨ω(L)为Lawson拓扑, 记为λ(L)．

命题1[13]设L是拟连续Domain, 记F={x:F≪x}, 则:

(i) ∀x∈L,H为L的有限子集． 如果H≪x, 则存在有限集F⊆L使得H≪F≪x;

(ii) intσ(L)(↑F)=F, 其中intσ(L)(↑F)表示↑F在Scott拓扑σ(L)中的内部;

定义2[14]设L是拟连续Domain,⊆w(L)． 如果∀x∈L, 集族fin(x)∩是定向集族且↑x=∩F∈fin(x)∩↑F, 则称是L的拟基．

显然, 设L是定向完备偏序集, 则L是拟连续的当且仅当L有拟基． 如果K(L)={G∈w(L):G≪G}是L的拟基, 则称L是代数拟连续Domain．

2 性质M*与性质SM*

文献[15]介绍了拟连续Domain的M*性质, 并研究了其与Lawson拓扑紧性的关系． 本节首先研究拟连续Domain的M*性质, 然后引入SM*性质的概念, 并给出性质M*与性质SM*的关系以及QL-Domain具有性质SM*的等价条件．

定义3[15]设L是拟连续Domain,是L的拟基． 如果∀E,F,G,H∈且E≪G,F≪H, 存在有限集族*⊆, 使得↑G∩↑H⊆∪B∈*↑B⊆↑E∩↑F, 则称L相对于拟基具有性质M*．

命题2[15]设L是拟连续Domain． 则下列条件等价:

(i) ∀x,y∈L, ↑x∩↑y是Scott紧的;

(ii)L相对于所有拟基具有性质M*;

(iii)L相对于某个拟基具有性质M*．

容易验证, 命题2中, ∀x,y∈L, ↑x∩↑y是Scott紧的当且仅当∀E,F∈w(L), ↑E∩↑F是Scott紧的, 其直接推论为文献[15]的推论4.7: 拟连续DomainL上的Lawson拓扑是紧的当且仅当L是有限生成的且具有性质M*．

由定义2知, 任意拟连续DomainL,w(L)是L的拟基． 如果L相对于某个拟基具有性质M*, 则由命题2知L相对于w(L)也具有性质M*． 如未特殊说明, 本文中的L具有性质M*总是指L相对于w(L)具有性质M*．

命题3设L是拟连续Domain, 则L具有性质M*当且仅当对∀E,F∈w(L),x,y∈L且E≪x,F≪y, 存在有限集H∈w(L), 使得↑x∩↑y⊆↑H⊆↑E∩↑F．

证 必要性因为L是具有性质M*的拟连续Domain, 则由命题2知,L相对于w(L)具有性质M*． 设E,F,{x},{y}∈w(L), 且E≪x,F≪y． 由L具有性质M*可知, 存在有限集族*⊆w(L), 使得

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

令H=∪B∈*↑B, 有限多个有限集的并仍然是有限集, 则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相对于拟基w(L)具有性质M*．

由于Smyth序为预序关系[16], 下面给出一种具有性质M*的特殊的偏序结构． 设L是偏序集, 令fin(L)={↑F:F∈w(L)}． ∀↑E,↑F∈fin(L), 定义二元关系: ↑E≤↑F当且仅当↑F⊆↑E, 即fin(L)上的偏序关系为反包含序． 本文中涉及到fin(L)中的序关系总是反包含序． 对∀⊆fin(L), 记

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

定义4设L是偏序集, 有限子集族⊆fin(L)． 如果:

则称L是qumb-完备的．

命题4设L是qumb-完备的拟连续Domain, 则L具有性质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具有性质M*．

文献[15]引入了QFS-Domain的概念, 并证明了QFS-Domain具有性质M*． 结合命题4, 说明存在一些特殊的偏序结构(如QFS-Domain、 qumb-完备的拟连续Domain)具有性质M*． 接下来, 引入拟连续Domain的SM*性质的概念．

定义5设L是拟连续Domain,是L的拟基． 如果∀E,F∈, 存在有限集族⊆且∀H∈,H⊆↑E∩↑F, 使得E∩F=∪H∈H, 则称L相对于拟基具有性质SM*． 如果L相对于拟基w(L)具有性质SM*, 则简称L具有性质SM*．

命题5设L是拟连续Domain,是L的拟基． 则L相对于拟基具有性质SM*蕴含L具有性质M*． 如果L是代数拟连续Domain, 则L相对于拟基(L)具有性质SM*当且仅当L具有性质M*．

证设L相对于拟基具有性质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相对于拟基具有性质M*． 由命题2知L具有性质M*．

如果L是代数拟连续的, 只需证明L具有性质M*蕴含L相对于(L)具有性质SM*． 设L具有性质M*, 则由命题2知L相对于(L)具有性质M*． ∀E,F∈(L),E≪E,F≪F, 存在有限集族*⊆(L), 使得

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

参考文献[15]的引理4.8证明了所有的QFS-Domain具有M*性质． 由命题5知, 所有的代数QFS-Domain相对于拟基(L)具有SM*性质．

设L是定向完备偏序集, 有限集族⊆fin(L), 记

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

令

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

如果∀H∈w(L),H在反包含序下是完备格(任意子集的上确界存在), 则称L是QL-Domain．

定理1设L是qumb-完备的拟连续QL-Domain． 则下列结论等价:

(i)L具有性质SM*;

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

证(i)⟹(ii)设↑G∈qmub≪{↑E, ↑F}, 则↑G∈qmub{↑E, ↑F}且G≠∅． 设G≪x, 则E≪x,F≪x, 即x∈E∩F． 因为L具有性质SM*, 则存在有限集族∈w(L), 且∀H∈,H⊆↑E∩↑F, 使得E∩F=∪H∈H, 则x∈∪H∈H． 故存在H∈, 使得H≪x． 而↑E,↑F∈H, 且↑G为↑E和↑F的极小上界, 同时H是完备格, 则↑G=↑E∨↑F． 因为是有限集族, 则qmub≪{↑E, ↑F}也是有限集族．

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

是有限集, 则qmub≪也是有限集． 因此由数学归纳法知, 对任意有限集族⊆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具有性质SM*．

3 几类具有SM*性质的特殊拟连续Domain

下面介绍两类具有性质SM*的特殊的拟连续Domain:

定义6设L是拟连续Domain,是L的拟基． 若存在由有限集作为元素的有限集族i(i∈I)满足:

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

定理2设L是拟连续Domain,⊆w(L)是有限集族． 则∀E,F∈,x∈E∩F, 存在H∈, 使得H⊆↑E∩↑F且H≪x, 当且仅当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设L是拟连续Domain,是L的拟双有限基, 则L相对于具有性质SM*．

证设∀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对某个i成立, 且x∈E∩F, ∪i∈IH⊆E∩F． 则∪i∈IH=E∩F,L相对于具有性质SM*．

定理4设L是拟连续Domain, 如果对任意有限集E,F⊆L,E∩F是Scott拓扑的紧子集, 则L具有SM*性质．

证设有限集E,F⊆L． ∀x∈E∩F, 由于E∩F是Scott开集, 则存在有限集Hx使得x∈Hx⊆E∩F, 则={Hx:x∈Hx⊆E∩F}是E∩F的开覆盖, 则存在有限多个H1,…,Hn∈是E∩F的开覆盖, 则x∈∪iHi．

反之, ∀y∈∪iHi, 存在i使得Hi≪y,y∈E∩F． 从而E∩F=∪iHi,L具有SM*性质．

本文给出了比M*性质更强的SM*性质, 并给出了一些具有SM*性质的特殊拟连续Domain, 并说明了在代数情形下, SM*性质与M*性质等价, 同时给出了一种新的偏序结构QL-Domain以及其具有SM*性质的等价条件． 本文的结论有助于Domain理论的进一步研究．