-
定向完备偏序集是偏序集理论中的一种重要结构,旨在为计算机高级程序设计语言提供数学模型,受到了计算机科学和数学领域诸多学者的关注,并得到了很多有价值的结论和模型[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理论的进一步研究.
全文HTML
-
首先,介绍偏序集中的一些基本概念[13]. 设L是偏序集,D⊆L,如果D中任意两个元在D中有上界,则称D为定向集. 如果L的每个定向子集D都有上确界(记为sup D),则称L为定向完备偏序集. 任给A⊆L,记
若A为单点集{a},则有记号↑A=↑a,↓A=↓a.
设L是偏序集,G,H为L的两个非空子集. 如果H⊆↑G,则G≤H,称这种序关系为Symth序. 如果对任意的定向集D⊆L,sup D∈↑H蕴含存在d∈D使得d∈↑G,则称G逼近H,记为G≪H. 特别地,{y}≪H简记为y≪H,G≪{x}简记为G≪x. 显然,G≪H蕴含∀h∈H,G≪h. 易知上述定义的逼近关系有如下性质:
(ⅰ) G≪H蕴含G≤H;
(ⅱ) G≤E≪F≤H蕴含G≪H.
令
$\mathscr{P}^w$ (L)表示L的所有非空有限子集构成的集族. 设非空集族$\mathscr{F}$ ⊆$\mathscr{P}^w$ (L),如果任给E,F∈$\mathscr{F}$ ,存在有限集H∈$\mathscr{F}$ ,使得H⊆↑E∩↑F,则称$\mathscr{F}$ 为定向集族. 设L是定向完备偏序集,如果∀x∈L,集族fin(x)={F∈$\mathscr{P}^w$ (L):F≪x}是定向的,且↑x=∩F∈fin(x)↑F,则称L是拟连续Domain.定义1[13] 设L是定向完备偏序集,
(a) 任给子集U⊆L,如果U=↑U,且任意的定向集D⊆L,sup D∈U意味着D∩U≠Ø,则称U为Scott开集. 所有的Scott开集构成一个拓扑,称为Scott拓扑,记为σ(L);
(b) 以主滤子的补L\↑x为子基生成的拓扑称为下拓扑,记为ω(L);
(c) 称由σ(L)和ω(L)共同加细的拓扑σ(L)∨ω(L)为Lawson拓扑,记为λ(L).
命题1[13] 设L是拟连续Domain,记
$\Uparrow F=\{x: F \ll x\}$ ,则:(ⅰ) ∀x∈L,H为L的有限子集. 如果H≪x,则存在有限集F⊆L使得H≪F≪x;
(ⅱ)
$\operatorname{int}_{\sigma(L)}(\uparrow F)=\Uparrow F$ ,其中intσ(L)(↑F)表示↑F在Scott拓扑σ(L)中的内部;(ⅲ)
$\left\{\Uparrow F: F \in \mathscr{P}^w(L)\right\}$ 为Scott拓扑σ(L)的基.定义2[14] 设L是拟连续Domain,
$\mathscr{B} \subseteq \mathscr{P}^w(L)$ . 如果∀x∈L,集族$\operatorname{fin}(x) \cap \mathscr{B}$ 是定向集族且↑x=∩F∈fin(x)∩$\mathscr{B}$ ↑F,则称$\mathscr{B}$ 是L的拟基.显然,设L是定向完备偏序集,则L是拟连续的当且仅当L有拟基. 如果
$K(L)=\left\{G \in \mathscr{P}^w(L): G \ll G\right\}$ 是L的拟基,则称L是代数拟连续Domain.
-
文献[15]介绍了拟连续Domain的M*性质,并研究了其与Lawson拓扑紧性的关系. 本节首先研究拟连续Domain的M*性质,然后引入SM*性质的概念,并给出性质M*与性质SM*的关系以及QL-Domain具有性质SM*的等价条件.
定义3[15] 设L是拟连续Domain,
$\mathscr{B}$ 是L的拟基. 如果∀E,F,G,H∈$\mathscr{B}$ 且E≪G,F≪H,存在有限集族$\mathscr{B}$ *⊆$\mathscr{B}$ ,使得↑G∩↑H⊆∪B∈$\mathscr{B}$ *↑B⊆↑E∩↑F,则称L相对于拟基$\mathscr{B}$ 具有性质M*.拟连续Domain相对于拟基
$\mathscr{B}$ 具有性质M*,可以有更一般的描述. 文献[15]证明了以下命题:命题2[15] 设L是拟连续Domain. 则下列条件等价:
(ⅰ) ∀x,y∈L,↑x∩↑y是Scott紧的;
(ⅱ) L相对于所有拟基具有性质M*;
(ⅲ) L相对于某个拟基具有性质M*.
容易验证,命题2中,∀x,y∈L,↑x∩↑y是Scott紧的当且仅当∀E,F∈
$\mathscr{P}^w$ (L),↑E∩↑F是Scott紧的,其直接推论为文献[15]的推论4.7:拟连续Domain L上的Lawson拓扑是紧的当且仅当L是有限生成的且具有性质M*.由定义2知,任意拟连续Domain L,
$\mathscr{P}^w$ (L)是L的拟基. 如果L相对于某个拟基具有性质M*,则由命题2知L相对于$\mathscr{P}^w$ (L)也具有性质M*. 如未特殊说明,本文中的L具有性质M*总是指L相对于$\mathscr{P}^w$ (L)具有性质M*.命题3 设L是拟连续Domain,则L具有性质M*当且仅当对∀E,F∈
$\mathscr{P}^w$ (L),x,y∈L且E≪x,F≪y,存在有限集H∈$\mathscr{P}^w$ (L),使得↑x∩↑y⊆↑H⊆↑E∩↑F.证 必要性 因为L是具有性质M*的拟连续Domain,则由命题2知,L相对于
$\mathscr{P}^w$ (L)具有性质M*. 设E,F,{x},{y}∈$\mathscr{P}^w$ (L),且E≪x,F≪y. 由L具有性质M*可知,存在有限集族$\mathscr{B} $ *⊆$\mathscr{P}^w$ (L),使得令
$H=\bigcup_{B \in \mathscr{B}^*} \uparrow B$ ,有限多个有限集的并仍然是有限集,则H为有限集,且↑x∩↑y⊆↑H⊆↑E∩↑F.充分性
$\forall E, F, G, H \in \mathscr{B}$ 且E≪G,F≪H,显然∀g∈G,E≪g成立. 同理,∀h∈H,F≪h. 由已知条件可知,存在有限集Hgh∈$\mathscr{P}^w$ (L),使得令
显然其是有限集族,则
即L相对于拟基
$\mathscr{P}^w$ (L)具有性质M*.由于Smyth序为预序关系[16],下面给出一种具有性质M*的特殊的偏序结构.设L是偏序集,令
$\operatorname{fin}(L)=\left\{\uparrow F: F \in \mathscr{P}^w(L)\right\}$ . ∀↑E,↑F∈fin(L),定义二元关系:↑E≤↑F当且仅当↑F⊆↑E,即fin(L)上的偏序关系为反包含序. 本文中涉及到fin(L)中的序关系总是反包含序. 对∀$\mathscr{F}$ ⊆fin(L),记定义4 设L是偏序集,有限子集族
$\mathscr{F}$ ⊆fin(L). 如果:(a) 集族qumb
$\mathscr{F}$ 是有限的;(b) 任意
$\mathscr{F}$ 的上界↑A∈fin(L),存在↑E∈qumb$\mathscr{F}$ ,使得↑A⊆↑E.则称L是qumb-完备的.
命题4 设L是qumb-完备的拟连续Domain,则L具有性质M*.
证
$\forall x, y \in L, E, F \in \mathscr{P}^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. 令从而↑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,
$\mathscr{B}$ 是L的拟基. 如果∀E,F∈$\mathscr{B}$ ,存在有限集族$\mathscr{H} \subseteq \mathscr{B}$ 且∀H∈$\mathscr{H}$ ,H⊆↑E∩↑F,使得$\Uparrow E \cap \Uparrow F=\bigcup_{H \in \mathscr{H}} \Uparrow H$ ,则称L相对于拟基$\mathscr{B}$ 具有性质SM*. 如果L相对于拟基$\mathscr{P}^w$ (L)具有性质SM*,则简称L具有性质SM*.命题5 设L是拟连续Domain,
$\mathscr{B}$ 是L的拟基. 则L相对于拟基$\mathscr{B}$ 具有性质SM*蕴含L具有性质M*. 如果L是代数拟连续Domain,则L相对于拟基$\mathscr{K}$ (L)具有性质SM*当且仅当L具有性质M*.证 设L相对于拟基
$\mathscr{B}$ 具有性质SM*,$\forall E, F \in \mathscr{B}, x, y \in L$ 且E≪x,F≪y,存在有限集族$\mathscr{H}$ ⊆$\mathscr{B}$ ,并且$\forall H \in \mathscr{H}, H \subseteq \uparrow E \cap \uparrow F$ ,使得$\Uparrow E \cap \Uparrow F=\bigcup_{H \in \mathscr{H}} \Uparrow H$ 成立. 令H′=∪H∈$\mathscr{H}$ H,从而有则由命题3知L相对于拟基
$\mathscr{B}$ 具有性质M*. 由命题2知L具有性质M*.如果L是代数拟连续的,只需证明L具有性质M*蕴含L相对于
$\mathscr{K}$ (L)具有性质SM*. 设L具有性质M*,则由命题2知L相对于$\mathscr{K}$ (L)具有性质M*. ∀E,F∈$\mathscr{K}$ (L),E≪E,F≪F,存在有限集族$\mathscr{B}^* \subseteq \mathscr{K}(L)$ ,使得取
$\mathscr{H}=\mathscr{B}^*$ 即可得到$\Uparrow E \cap \Uparrow F=\bigcup_{H \in \mathscr{H}} \Uparrow H$ ,从而L相对于拟基$\mathscr{K}$ (L)具有性质SM*.参考文献[15]的引理4.8证明了所有的QFS-Domain具有M*性质. 由命题5知,所有的代数QFS-Domain相对于拟基
$\mathscr{K}$ (L)具有SM*性质.设L是定向完备偏序集,有限集族
$\mathscr{F} \subseteq \operatorname{fin}(L)$ ,记令
如果∀H∈
$\mathscr{P}^w$ (L),$\mathscr{F}_H$ 在反包含序下是完备格(任意子集的上确界存在),则称L是QL-Domain.定理1 设L是qumb-完备的拟连续QL-Domain.则下列结论等价:
(ⅰ) L具有性质SM*;
(ⅱ)
$\forall E, F \in \mathscr{P}^w(L), \mathrm{qmub}_{\ll}\{\uparrow E, \uparrow F\}$ 是有限集族;(ⅲ) 对任意有限集族
$\mathscr{F} \subseteq \operatorname{Fin}(L), \mathrm{qmub}_{\ll} \mathscr{F}$ 是有限集族.证 (ⅰ)⇒(ⅱ) 设↑G∈qmub≪{↑E,↑F},则↑G∈qmub{↑E,↑F}且
$\Uparrow G \neq \varnothing$ .设G≪x,则E≪x,F≪x,即$x \in \Uparrow E \cap \Uparrow F$ . 因为L具有性质SM*,则存在有限集族$\mathscr{H} \in \mathscr{P} w(L)$ ,且∀H∈$\mathscr{H}$ ,H⊆↑E∩↑F,使得$\Uparrow E \cap \Uparrow F=\bigcup_{H \in \mathscr{H}} \Uparrow H$ ,则$x \in \bigcup_{H \in \mathscr{H}} \Uparrow H$ . 故存在H∈$\mathscr{H}$ ,使得H≪x. 而$\uparrow E, \uparrow F \in \mathscr{F}_H$ ,且↑G为↑E和↑F的极小上界,同时$\mathscr{F}_H$ 是完备格,则$\uparrow G=\uparrow E \bigvee_{\mathscr{F}_H} \uparrow F$ . 因为$\mathscr{H}$ 是有限集族,则$\mathrm{qmub}_{\ll}\{\uparrow E, \uparrow F\}$ 也是有限集族.(ⅱ)⇒(ⅲ) 对有限集族
$\mathscr{F}$ 的基数做数学归纳法. 设$|\mathscr{F}|=2$ ,由已知,$\mathrm{qmub}_{\ll} \mathscr{F}$ 是有限集族. 假设|$\mathscr{F}$ |=n≥2时,$\mathrm{qmub}_{\ll} \mathscr{F}$ 是有限集族. 当$|\mathscr{F}|=n+1$ 时,设$\mathscr{F}=\left\{\uparrow F_1, \cdots, \uparrow F_n, \uparrow F_{n+1}\right\}$ ,令$\mathscr{F}_n$ ={↑F1,…,↑Fn}. ∀↑G∈qmub≪$\mathscr{F}$ ,↑Fi∈$\mathscr{F}_G$ (i=1,…,n+1). 令↑F=∨$\mathscr{F}_G$ Fn,显然↑G是↑F和↑Fn的上界. 设↑H∈$\mathscr{F}_G$ 且↑H=↑F∨$\mathscr{F}_G$ ↑Fn+1,则↑G⊆↑H. 而↑H为↑F和↑Fn+1的上界,故也是$\mathscr{F}$ 的上界,则由qumb-完备性知,存在↑G′∈qmub$\mathscr{F}$ ,使得↑H⊆↑G′. 因此↑G⊆↑H⊆↑G′,由↑G′的极小性知↑G=↑H=↑G′,即↑G是↑F和↑Fn的极小上界. 由假设qmub≪$\mathscr{F}_n$ 是有限集族知是有限集,则qmub≪
$\mathscr { F }$ 也是有限集. 因此由数学归纳法知,对任意有限集族$\mathscr { F }$ ⊆fin(L),qmub≪$\mathscr { F }$ 是有限集族.(ⅲ)⇒(ⅰ)
$\forall E, F \in \mathscr{P}^w(L), \uparrow E, \uparrow F \in \operatorname{fin}(L)$ ,令首先如果存在↑G∈qmub{↑E,↑F},使得G≪x,显然有E≪x,F≪x,即
$\forall x \in \Uparrow E \cap \Uparrow F$ , 有$E \bigvee_{\mathscr{F}_{\{x\}}} F \ll x$ 且$E \vee_{\mathscr{F}_{\{x\}}} F \in \mathrm{qmub}_{\ll}\{E, F\}, x \in \bigcup_{H \in \mathscr{H}} \Uparrow H$ 综上所述,有
$ \bigcup_{H \in \mathscr{H}} \Uparrow H=\Uparrow E \cap \Uparrow F$ ,L具有性质SM*.
-
下面介绍两类具有性质SM*的特殊的拟连续Domain:
定义6 设L是拟连续Domain,
$\mathscr{B}$ 是L的拟基. 若存在由有限集作为元素的有限集族$\mathscr{F}_i(i \in I)$ 满足:(a)
$\mathscr{B}$ ⊆∪i∈I$\mathscr{F}_i$ ,且{B1,B2}⊆$\mathscr{B}$ 蕴含{B1,B2}⊆$\mathscr{F}_i$ 对某个i成立;(b)
$\forall i \in I, E, F \in \mathscr{F}_i, x \in \Uparrow E \cap \Uparrow F$ , 存在$H \in \mathscr{F}_i$ ,使得$H \subseteq \uparrow E \cap \uparrow F \text { 且 } H \ll x$ .则称
$\mathscr{B}$ 是L的拟双有限基.定理2 设L是拟连续Domain,
$\mathscr{F} \subseteq \mathscr{P}^w(L)$ 是有限集族. 则$\forall E, F \in \mathscr{F}, x \in \Uparrow E \cap \Uparrow F$ ,存在H∈$\mathscr{F}$ ,使得H⊆↑E∩↑F且H≪x,当且仅当$D=\{\uparrow F: F \in \mathscr{F} \cap \operatorname{fin}(x)\}$ 在反包含序下存在最大元.证
$\forall E, F \in \mathscr{F}, x \in \Uparrow E \cap \Uparrow F$ ,存在H∈$\mathscr{F}$ ,使得H⊆↑E∩↑F且H≪x,则↑H是↑E和↑F在D中的上界,从而D是有限的定向集,则必有最大元. 反之,若D存在最大元↑H′,∀E,F∈$\mathscr{F}$ ,$x \in \Uparrow E \cap \Uparrow F$ ,则↑E,↑F∈D,故H′⊆↑E∩↑F且H′≪x.定理3 设L是拟连续Domain,
$\mathscr{B}$ 是L的拟双有限基,则L相对于$\mathscr{B}$ 具有性质SM*.证 设
$\forall E, F \in \mathscr{B}, E \ll x, F \ll x$ . 由于$\mathscr{B}$ 是L的拟双有限基,则存在由有限集作为元素的有限集族$\mathscr{F}_i(i \in I)$ ,使得:(ⅰ)
$\mathscr{B} \subseteq \bigcup_{i \in I} \mathscr{F}_i$ ,且$E, F \in \mathscr{F}_i$ 对某个i成立;(ⅱ) 存在
$H \in \mathscr{F}_i$ ,使得H⊆↑E∩↑F且H≪x,则$\Uparrow E \cap \Uparrow F \subseteq \bigcup_{i \in I} \Uparrow H$ .反之,若
$x \in \bigcup_{i \in I} \Uparrow H$ ,存在H∈$\mathscr{F}_i$ 使得H≪x对某个i成立,且$x \in \Uparrow E \cap \Uparrow F, \cup_{i \in I} \Uparrow H \subseteq \Uparrow E \cap \Uparrow F$ . 则$\bigcup_{i \in I} \Uparrow H=\Uparrow E \cap \Uparrow F$ ,L相对于$\mathscr{B}$ 具有性质SM*.定理4 设L是拟连续Domain,如果对任意有限集E,F⊆L,
$\Uparrow E \cap \Uparrow F$ 是Scott拓扑的紧子集,则L具有SM*性质.证 设有限集E,F⊆L.
$\forall x \in \Uparrow E \cap \Uparrow F$ ,由于$\Uparrow E \cap \Uparrow F$ 是Scott开集,则存在有限集Hx使得$x \in \Uparrow H_x \subseteq \Uparrow E \cap \Uparrow F$ ,则$\mathscr{H}=\left\{\Uparrow H_x: x \in \Uparrow H_x \subseteq \Uparrow E \cap \Uparrow F\right\}$ 是$\Uparrow E \cap \Uparrow F$ 的开覆盖,则存在有限多个$H_1, \cdots, H_n \in \mathscr{H}$ 是$\Uparrow E \cap \Uparrow F$ 的开覆盖,则$x \in U_i \Uparrow H_i$ .反之,
$\forall y \in \bigcup_i \Uparrow H_i$ ,存在i使得$H_i \ll y, y \in \Uparrow E \cap \Uparrow F$ . 从而$\Uparrow E \cap \Uparrow F=\bigcup_i \Uparrow H_i$ ,L具有SM*性质.本文给出了比M*性质更强的SM*性质,并给出了一些具有SM*性质的特殊拟连续Domain,并说明了在代数情形下,SM*性质与M*性质等价,同时给出了一种新的偏序结构QL-Domain以及其具有SM*性质的等价条件. 本文的结论有助于Domain理论的进一步研究.