可在www.sciencedirect.com在线获取理论计算机科学电子笔记301（2014）179-188www.elsevier.com/locate/entcs满足预连续偏序集张文峰四川大学数学系，成都，中国。Xiaoquan XuXiang，2岁江西师范大学数学系，南昌，中国。摘要本文引入交预连续偏序集的概念，它是交连续格在偏序集上的推广。主要结果是：（1）偏序集P是交预连续的i，它的正规完备化是交连续格i，它的正规完备化是交连续格i，在完备格的情况下，系统γ（P）是全体的格Scott-闭集是完备Heyting代数;（2）偏序集P是预连续的，且满足以下关系是P上的最小逼近辅助关系i，且P是交预连续的，P上存在最小逼近辅助关系。 最后，给出偏序集P和P上的辅助关系，刻画了P的way-below关系与所给辅助关系一致的并稠密子集关键词：准连续偏序集，交准连续偏序集，交连续格，正规完备化，辅助关系。1引言域理论是由Scott在60年代后期为编程语言的指称语义学而引入的。它为程序设计语言的设计、定义和实现，以及程序的规范和验证系统提供了数学基础。从计算机科学和纯数学的角度来看，Domain理论的一个重要方面是尽可能地将连续Domain理论推广到一般Domain理论。尽可能地形成有序的结构。由于它们与计算机科学、一般拓扑学和拓扑代数的密切联系，连续域已经被国家自然科学基金资助项目（Nos. 10861007、11161023）、基金全国优秀博士论文（2007B14）、江西省自然科学基金会（2007B20114BAB201008）、江西省教育厅基金（编号：GJJ12657）。1电子邮件：zhangwenfeng2100@163.com2电子邮件：xiqxu2002@163.comhttp://dx.doi.org/10.1016/j.entcs.2014.01.0151571-0661 © 2014 Elsevier B. V.在CC BY-NC-ND许可下开放访问。180W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179↑∈↑ ↓ ↓{<$↓}被来自不同地区的人们广泛研究[1，7]。有几种不同的等价方法来定义连续域，最直接的方法是使用下面的关系式我们说x在y的下方，记为xy，i<$x∈ <$y：={↓D：D是有向的，y≤ <$D}。一个dcpoP称为一个连续域，如果每个集合dcpoy都是有向的，并且有连接y。这个定义对于推广连续格理论的许多范畴和拓扑发展来说是非常富有成效因此，越来越多的场合研究偏序集的缺失上确界（见[5，10，12，15，18]）。 虽然连续偏序集继承了连续整环的一些好的性质，但它们也不能满足一些希望的性质，例如，它们不是完备不变的[3]，即连续偏序集的正规完备化不一定是连续格（见[2]）。在[2]中，Erne引入了一个新的Waybelow关系和预连续偏序集的概念，用Frink理想代替了有向下集[6]，它不局限于dcpos，并具有所需的完备不变性质。交连续格是一个完全格，其中二元交分布在有向上确界上（见[5]）。这个代数概念有一个纯粹的拓扑特征，可以推广到[7，9]中的有向完全偏序（dcpos）的集合：dcpoP是交连续的，如果对任何x∈P和任何有向子集D，其中x≤supD，有x∈clσ（P）（↓x<$D），其中clσ（P）（↓x<$D）是集合<$D<$↓x的Scott闭包。在[11]中，Mao和Xu将交连续dcpos的概念推广到一般偏序集上。交连续偏序集虽然继承了交连续偏序集的一些好的性质，但却不是完备不变的.第二节将给出一个简单的反例本文引入交预连续偏序集的概念。证明了偏序集P是交预连续的，且它的正规完备化是交连续格;考虑算子Γ和[2]中的系统γ（P），我们证明了偏序集P是交预连续的，且系统γ（P）是完备Heyting代数，P是预连续偏序集，具有插值性质iP是交预连续偏序集，对所有的x∈P，U∈γ（P）c，它是γ（P）的元素的补族，x∈U蕴涵有有限个F<$P和V∈γ（P）c使得x∈V<$↑ F<$U和Γ是幂等的. 我们还在辅助关系中找到了关系下面的路。证明了偏序集P是预连续的，且P上存在最小的逼近辅助关系.最后，我们证明了如何构造所有的准连续偏序集，其way-below关系与给定的辅助关系一致2个房间设P是偏序集。 对所有x∈P，A<$P，设↑x={y∈P：x≤y}， A= a Aa;x和A是对偶定义的。 设D（P）=AP：A=A.A↑和A↓分别表示A设Aδ=（A↑）↓，δ（P）={Aδ：A<$P}.（δ（P），φ）称为正规完备化，W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179181δC2）A=（{Aiδ：i∈I}）δ=（i∈Ii∈Ii∈I}=我和或P的Dedekind-MacNeille完备化。完备化不变性质是指对Pi成立的性质，它对P的任何正规完备化都成立.一个子集I<$P称为Frink理想，如果对所有有限子集Z<$I，我们有Zδ<$I。设Fid（P）表示P的所有Frink理想的集合.偏序集P的子集A是Scott闭的，如果↓A=A且对任意有向集D<$A，当supD存在时，supD∈A。 斯科特闭集的补集是斯科特开集，这些集合的族形成一个拓扑，称为斯科特拓扑，记为σ（P）。由所有主理想的补生成的拓扑称为上拓扑，记为<$x（P）。下面的引理是众所周知的（见[3]）。引理2.1设P是偏序集。(1) 映射（−） ↑：（ 2 P） op→ 2 P，A<$→A↑和（−） ↓： 2 P→（ 2 P） op，A<$→A↓是保序的。（2）（（−）↑，（−）↓）是（2 P）op和2 P之间的伽罗瓦联络，即对所有A，B<$P，B↑<$A惠B<$A↓。因此δ：2 P→ 2 P，A<$→Aδ=（A↑）↓和δ<$：2 P→ 2 P，A<$→（A↓）↑都是闭包算子。(3)对于所有{Cj：j∈J}<$2P，（Cj）↑=Cj↑，（Cj）↓= Cj↓。j∈Jj∈Jj∈Jj∈JδLδ δ(4) 设L=δ（P）. 对于所有{Ai：i∈I}{Ai：i∈ I}={Ai：i∈I}，推论2.2设P是偏序集。则映射j：P→δ（P），x<$→↓x是P在正规完备化δ（P）中的序嵌入，(1) j保留所有现有的连接并满足;(2) 对所有的Aδ∈δ（P），Aδ=a∈Aj（a）=a∈Aδj（a）.3满足预连续偏序集在[2]中，Erne′引入了算子：Γ：2P→2P，Y<$→{Iδ：I∈Fid（P），I↓ Y}. 用γ（P）表示Γ 的所有不动点系，即γ（P）={Y<$P ： Γ Y=Y}={Y ：I<$Y 且I∈Fid （ P ） 蕴 涵Iδ<$Y} 。显 然 ， γ （ P ）c={P\Z：Z∈γ（P）}={UimpliesI}。在完备格中，γ（P）是所有Scott闭集的系，γ（P）是所有Scott开集的系。 一般情况下，Γ保持任意交叉点，但它不需要保持有限联合（见[1，示例1]）。因此，我们认为，γ（P）不需要形成拓扑。很容易获得以下内容Proximion3.1LetP是偏序集。 则对所有{Yi：i∈I}<$γ（P），γ（P）{Yi：U∈γ（P）c，其中x∈U，U∈（Yi）i∈I{\fn方正黑体简体\fs18\b1\bord1\shad1\3cH2F2F2F}.Ai）δ。γ（P）{Yi：i∈I}={A∈γ（P）：i∈I Yi<$A}={x∈P：对于所有182W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179i=（i=1Ai）;i=1在文献[11]中，Mao和Xu将交连续dcpos的概念推广到一般偏序集，并引入了以下内容：定义3.2设P是偏序集。 则称P是交连续偏序集，如果对所有x∈P和所有有向子集D ， 如果supD 存 在且x≤supD ， 则x∈clσ （ P ）（ ↓D<$↓x） ，其 中clσ （ P ） （↓x<$↓D）是集合的Scott闭包↓D↓x.满足连续性不是完全不变的，如下例所示。例3.3设P ={0，1，2，. . }{a}。在P上定义一个偏序<<<<“≤“使得0 1 2 ···和0 a.显然，P是满足连续的。由于A={0，1，2， . . . }表示A↑=P，则有Aδ=P，因此δ（P）={{0}，{0，1}，{0，1，2}，.. . {{0，a}}{{P}}。 取D ={{0}，{0，1}，{0，1，2}，.. . }且x={ 0，a}。然后xD = x，但xD={ 0}。因此，δ（P）不是满足连续格现在我们引入交预连续的一个新概念，并证明它是完备不变的。定义3.4偏序集P称为交预连续的，如果对每个x∈P和I∈Fid（P），x∈Iδ蕴涵x∈（↓x<$I）δ.例3.5设S ={0，1，2，. . }，在S上具有偏序<<<如果a和b是S的两个不可比上界，则所得p集合P=S∈{a，b}是一个交预紧p集合.例3.6偏序集P ={0，1，2，. . 在例3.3中构造的{a}是满足连续的。 设D={0，1，2， . . . }，我们有一个vea∈Dδ=P，但a∈/（↓a <$↓D）δ={0}，因此它不是满足预连续的.通过命题3.1，我们可以得到以下结果：定理3.7对于偏序集P，下列条件等价：(1) P满足预连续;(2) 设I ∈ Fid（P），x ∈ Iδ. 则对于每个U ∈ γ（P）c，其中x ∈ U，我们有UI↓x/=。(3) 对任意x ∈ P和任意U ∈ γ（P）c，有↑（U <$↓ x）∈ γ（P）c.(4) γ（P）是完备的Heyting代数。命题3.8对于偏序集P，下列条件等价：(1) P满足预连续;(2) δ：Fid（P）→ δ（P）保持有限相交，即， 对于所有{Ai|1 ≤ i ≤nδ(3) 对所有的A，B∈Fid（P），Aδ<$Bδ=（A<$B）δ;(4) 对所有x ∈ P，A ∈ Fid（P），有↓ x <$Aδ=（↓x <$A）δ.n }n =Fid（P），W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179183δ证据 （2）惠（3）：微不足道。(1) <$（3）：对所有的A，B∈ Fid（P），显然（A<$B）δ<$Aδ<$Bδ. 设x∈Aδ<$Bδ. 由 式 （ 1 ） ， x∈↓x= （ ↓x<$A ） δ= （ ↓x<$B ） δ 。表 示 M=↓xA 和N=↓xB。则n∈N意味着n∈↓x=Mδ，这又产生n∈↓n=（↓n<$M）δ. 1.1.当x∈N δ=（n∈N↓n）δ=（（↓n∈Nn<$M）δ）δ <$（（M<$N）δ）δ=（M<$N）δ<$（A<$B）δ。(3) （4）：琐碎。(4) （1）：对于x∈P，A∈Fid（P），如果x∈Aδ，则由（4），x∈↓x<$Aδ=（↓xA）δ。Q根据定理3.7和命题3.8，我们可以得到以下结果：定理3.9对于偏序集P，下列两个条件等价：(1) P满足预连续;(2) （δ（P），ε）是交连续格.4准连续偏序集的γ（P）表示定义4.1设P是偏序集。(1) 给定两个元素x，y∈P，我们说x远低于y（用符号表示：xy），如果x∈Fid：={I∈ Fid（P）：y∈I}。(2) P称为预连续的，如果对每个x∈P，x∈（<$x）δ。定义4.2（[7]）对于完备格L，定义L上的关系式xxxy惠y∈intn（L）↑x. 称L为超连续的，如果对所有x∈L，x= sup{u∈L：u<$x}.定义4.3（[14]）设P是偏序集。 我们在P的子集集合上定义一个二元关系ρ如下：AρB当且仅当S是P的子集，超S存在且在↑B中，则S<$↑AAρ{x}}。- 是的Letρ（x）={A∈P：A是有限的，定义4.4（[14]）完备格L称为广义完全分配格当且仅当对所有x∈L，↑ x ={↑A：A∈ ρ（x）}。引理4.5（[13，16]）对于完备格L，以下两个条件是等价的：(1) L是超连续格;(2) 对于所有x，y∈L，x/≤y意味着存在u ∈L和有限个F ∈L使得：(i) x/∈↓F，u/∈↑y，和(ii) 对所有的z ∈ L，z ∈↓ F或z ∈↑ u.通过引理4.5，我们可以得到以下结果：命题4.6对于偏序集P，以下两个条件等价：(1) （γ（P）c，γ）是超连续格;184W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179(2) 对所有的x∈P，U∈γ（P）c，其中x∈U意味着有有限个F∈P，V∈γ（P）c使得x∈V <$↑F<$U.引理4.7（[17]）完备格L是广义完全分配格当且仅当Lop是超连续格。引理4.8（[17]）对于完备格L.以下条件是等价的：(1) L是完全分配格;(2) L既是Heyting代数又是广义完全分配格。引理4.9（[2]）对于偏序集P，下列条件等价：(1) P是一个预连续偏序集，具有插值性质;(2) Γ是一个闭包算子，保持下集的任意交(3) γ（P）= Γ（2 P）是一个完全分配闭包系统（而Γ是相应的闭包算子）.根据定理3.7、命题4.6、引理4.7、引理4.8和引理4.9，我们可以得到以下结果定理4.10对于偏序集P，下列两个条件等价：(1) P是一个预连续偏序集，具有插值性质;(2) P是交预连续偏序集，且对所有x∈P，U∈γ（P）c，x∈U蕴涵有有限个F<$P和V∈γ（P）c使得x∈V <$↑F<$U和Γ是幂等的.5定位关系下的路径辅助（P）内在这一节中，我们研究了交拟连续偏序集与拟连续偏序集之间的关系，并给出了偏序集P和P上的辅助关系，刻画了P的way-below关系与给定的辅助关系一致的并稠密子集定义5.1（[7]）我们说偏序集P上的二元关系是一个辅助关系，如果它对所有u，x，y，z∈P都满足下列条件，(i) x≠y蕴涵x≤y;(ii) u≤x<$y≤z蕴涵u<$z;(iii) 如果存在最小元素0，则0 =x。P上的所有辅助关系的集合将被表示为Aux（P）。 由于Aux（P）在2P×P中的任意相交处是闭的，因此它是一个完备格。定义5.2偏序集P上的一个辅助关系是逼近的，如果对每个x∈P，s<$（x）={y∈P：y<$x} ∈Fid（P）且x∈（s<$（x））δ。所有近似辅助关系的集合由App（P）表示。W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）1791851999年，《金刚经》（{mI：I∈Fid（P）}）=I∈F id（P）φ（φmI）=I∈Fid（P）s<$mI.命题5.3（[7，8]）设P是偏序集，M是所有单调函数s：P→D（P）满足s（x）<$↓x（x∈P）的集合-被认为是相对于序s ≤ti <$s（x）<$t（x）（x ∈P）的偏序集.则映射φ：Aux（L）→M，φ（L）=s<$=（x<$→ {y：y<$x}）是从Aux（P）到M的一个定义良好的同构，它的逆映射将每个函数s∈M与由x∈sy惠x∈ s（y）给出的关系x x联系起来。从下面关系的定义，我们有s（x）={I∈Fid（P）：x∈Iδ}，对所有x∈P.引理5.4设P是偏序集。 对于每个I∈Fid（P），我们定义函数mI：P→D（P）mI（x）=↓x<$I， 如果x∈Iδ，x，否则。则对于所有的I∈Fid（P），m I ∈ M且={<$mI：I∈Fid（P）}。证据很明显，对于所有的I∈Fid（P），m I ∈ M。 从命题5.3，我们只 需要证明φ（{mI：I ∈Fid（P）}）= φ（）= s。因为φ是一个根据mI和sI（x）的定义，sI（x）=mI（x）。现在我们证明（I∈F id（P）s<$mI）（x）= s （x）对于每个x∈P. 事实上（I∈Fid（P）s<$mI）（x）={s<$mI（x）：I∈Fid（P）}={mI（x）：I∈Fid（P）}=（ {↓x<$I：x∈Iδ}）<$（ {↓x：x∈/Iδ}）={I∈Fid（P）：x∈Iδ}=s（x）Q引理5.5在交预连续偏序集P中，属于函数m I的所有关系s∈mI，其中I∈Fid（P）是逼近的。这一点特别适用于预连续偏序集，因为它们是交预连续的。证据对于每个x∈P，smI（x）=mI（x）=↓x<$I， 如果x∈Iδ，x，否则。..186W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179MIMIFid（P）}。哪里{：∈App（P）}. 因此={：∈App（P）}。Q若x∈Iδ，则x∈（↓x<$I）δ=（s<$（x））δ，因为P是满足预连续的;若x∈/Iδ，theNx∈（↓x）δ=（mI（x））δ=（sI （x））δ. Obviously，↓x∈Fid（P）andd↓x<$I∈Fid（P）. 因此，对于所有的I∈Fid（P），I是近似的Q引理5.6在偏序集P中，如果P是交预连续的，则下路关系包含在所有的近似辅助关系中，并且等于它们的交。证据 设x，y ∈ P，其中yx，且P是一个近似辅助关系.则s<$（x）={u∈P：u<$x}∈Fid（P）且x∈（s<$（x））δ.它由y∈s<$（x）的定义得出，即y<$x。 故和{：∈App（P）}。 如果P是满足预连续的，则由引理5.5证明了I∈App（P）。因此{：∈App（P）}{fmI：I∈Fid（P）}. 通过Lemma5.4，={mI：I∈定理5.7对于偏序集P，下列条件等价：(1) P是预连续的;(2) 是P上的最小逼近辅助关系;(3) P是交预连续的，且P上存在最小的逼近辅助关系.证据（1）惠（2）：根据定义，P是预连续的，即P是一个近似辅助关系。因此，（1）和（2）的等价性由引理5.5的第一部分得出。(2) （3）：琐碎。(3) * *因此，如果存在最小近似辅助关系，则必须是，我们看到（3）意味着（1）。Q作为结论，我们构造了准连续的偏序集，其下关系的方式与辅助关系的方式一致。在可能存在歧义的情况下，我们将使用上标来区分与两个偏序集P和Q相关的概念，这里是P和Q。定义5.8（[3]）设P是偏序集。 我们说SP在P中是连接稠密的，如果x∈（↓x<$S）δ，对所有x∈P.定理5.9设S在偏序集P中是并稠密的，且S是S上的一个辅助关系。 如果对每个x∈S，s∈（x）={y∈S：y∈x}∈Fid（P），则下列陈述是等价的：(1) P是预连续的，且P在S上与P一致。(2) 对所有x，y∈S，x∈y蕴涵xPy且x∈（s∈（x））δ.证据（1）δ（2）：我们证明了对所有x∈S，x∈（sδ（x））δ。如果存在x∈S，且x∈/（s∈（x））δ，则存在y∈P，且y∈（s∈（x））↑such，使得x∈y。SinceP是预连续的，m∈ x<$y，即存在m∈x和m<$y.由于S是连接稠密的，W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179187δδδδ δm∈P，Db↓m使得b<$m。 由于S是并稠密的，存在p∈S并，Db∈Fid（P）. Weshowb∈（Db）. 如果fb∈/（ Db），则存在zp使得zm.设X={z}，则X∈Hb.因此z∈ {z}<$Db <$↓m，在P中，存在z∈S使得z≤m且z∈y.其中z≤mPx.因此zPx. 由（1），z<$x，与y∈（s<$（x））↑矛盾。 (2)第一章：索赔如果（2）成立，则对所有a，b∈P，aPb当且仅当存在有限个X<$S使得a∈Xδ且对每个x∈X有p∈S且x<$p≤b。索赔证明。假设aPb。如果b= 0，则X =0。我们假设b >0。设Hb={X<$S：X是有限的，对每个x∈X，有p∈Ssuch使得x<$p≤b}.LetDb={Xδ：X∈Hb}.SinceHb在有限条件下是闭的使得p≤b且p≠m。 由于p∈（s<$（p））δby（2），存在z∈S，与zm相矛盾。其中b∈（存在X∈ Hb使得a∈Xδ.Db）δ. 由于P b，a∈Db. 因而相反，假设a∈Xδ，其中X<$S是有限的，并且对于每个x∈X，存在px∈S，其中x<$px≤b。我们显示一个 Pb。设I∈Fid（P），b∈Iδ. 通过（2），xPpx≤b∈Iδ. 因为Iδ是一个下集合，所以px∈Iδ。其中x∈I。 因此XI。由于I∈Fid（P），a∈Xδ<$I.所以一个Pb。首先，我们证明P是预连续的。设b∈P.在证明该主张的过程中，我们已经证明了b∈（ Db）。 通过索赔， Dbb. 所以b∈（ Db）δ.然后我们证明了P =P。 通过（2）， 反之，设aPb。 根据权利要求，存在有限个X<$S使得a∈Xδ，且对于每个x∈X，x<$b。通过假设s<$（b）∈Fid（P），我们有Xδ<$s<$（b）。 所以是个混蛋。Q6总结本文在割算子的基础上，引入交预连续偏序集的概念，作为交连续格的推广研究交预连续偏序集的一些性质和特征特别地，我们讨论了交预连续偏序集和预连续偏序集之间的关系本文的重要贡献是证明了偏序集是交预连续的，且它的正规完备化是交连续格。因此，从文[2]中Erne′的意义上说，我们的推广是一个god推广.引用[1] Abramsky，S.，和A. Jung，Domain theory，in：S. Abramsky等人（编辑），计算机科学中的逻辑手册，卷。3，Clarendon Press，Oxford，1995，pp.1-168[2] 恩，先生，连续格上概念的一个完备不变扩张，In：B. Banaschewski和R. E. Ho Zurmann（eds.），连续格，Proc. 1979年，《数学讲义》（Lecture Notes in Math.）871，Springer-Verlag，Berhn-Heidelberg-New York，1981，pp.43-60[3] 恩，先生， D edekind-MacNeil l le完成作为一个receiver，Ord e r. 8（1991），159-173.[4] 恩，先生， 无限分布律与局部一致性和一致性概率，拓扑应用156（2009），2054-2069。188W. Zhang，X.Xu/Electronic Notes in Theoretical Computer Science 301（2014）179[5] 恩，先生，Z-连续子集及其拓扑表现，第二版. 卡泰格结构. 7（1999），31-70.[6] 弗林克，O.，偏序集合中的理想，Amer.Math.Monfhly。61（1954），223-234.[7] 吉尔茨湾例如，连续格和域，剑桥大学出版社，剑桥，2003年。[8] 吉尔茨湾例如，与插值性质和连续格的关系，1976年。[9] 寇，H.，Y. Liu和M.张国强，张建东.Lawson，Yingming Liu，Maokang Luo（编辑），Domain Theory，Logic and Computation，Kluwer Academic Publishers，2003，pp. 一三七至一四九[10] Hrbacek，K.，连续完备化，代数普遍。28（1991），230-244.[11] Mao，X.和L.徐，偏序集的满足连续性，理论计算机科学。410（2009），4234-4240。[12] Mislove，M.，代数偏序集，代数dcpos和并发模型，在：计算机科学中的拓扑和范畴理论，G。M. Reed，A. W.罗斯科河F. Wachter，编辑，牛津大学03 The Dog（1991）[13] Menon，V.G.，偏序集上的分离点，Houston J.数学21（1995），283-290.[14] Venugopalan，P.，完全分配格的一个推广，代数通用。27（1990），578-586.[15] 徐，L.，Continuity of posets via Scott topology and sobrification，Topology Appl.153（2006），1886-1894.[16] Xu ， X. 和 J. Yang ， Topological representations of distributed hypercontinuous lattices. 下 巴Ann.Math.30B（2009），199-206.[17] Yang，J.和X. Xu，广义完全分配格的对偶是超连续格，代数Universalis。63，（2010），275-281.[18] 张洪，关于连续偏序集的一个注记，半群论坛。47（1993），101-104.
我的内容管理
展开
