Properties and Characterizations of Z-Precontinous Posets

Domain理论为计算机程序设计语言的指称语义学奠定了数学基础，属于以格论、拓扑学、范畴论及理论计算机科学为基础的交叉领域^[1].连续Domain是Domain理论中的重要研究对象.文献[2]中给出了Z-连续Domain的定义和一些基本性质，由文献[2]还可以看出Z-连续Domain与连续Domain有好多相似的性质.文献[3]中介绍了弱于连续Domain的一种结构——准连续Domain.本文引入了弱于Z-连续Domain的一种结构——Z-准连续Domain，给出了它的一些等价刻画，并且讨论了Z-准连续Domain的积结构、商结构和子结构.一般来说，Z-连续Domain不一定是完备格，要给出Z-连续Domain的等式刻画比较困难，本文最后给出了Z-准连续Domain的等式刻画.

文中，Set表示集合范畴，Poset表示以所有偏序集为对象，保序映射为态射的范畴. Poset的对象集记为ob(Poset)，∀P∈ob(Poset)，A⊆P，∀a，b∈A，∃c∈A，使得a≤c且b≤c，则称A为定向集.若P对定向并关闭，则称P为Dcpo. A⊆P，记

即l(A)为A在P中的所有下界之集.

定义1^[2]  函子Z：Poste→Set称为Poset上的一个子集系统，简称一个子集系统，若Z满足以下条件：

(1) ∀P∈ob(Poset)，Z(P)⊆2^P；

(2) ∀P，Q∈ob(Poset)，f：P→Q是保序映射，A∈Z(P)⇒f(A)∈Z(Q)；

(3) ∃P∈ob(Poset)，使得Z(P)含有P的非单点的非空子集.

在以下讨论中，Z总表示一个子集系统，∀P∈ob(Poset)，称Z(P)为P上的一个子集系统. ∀A∈Z(P)，称A是P的Z-集.

注1^[2]  (1) 设P∈ob(Poset)，则∀x∈P，{x}∈Z(P).

(2) 设P∈ob(Poset)，Q⊆P，则∀S∈Z(P)，有S∈Z(Q).

定义2^[2]  设P∈ob(Poset)，称偏序集P是Z-完备的，若∀S∈Z(P)，∨S存在.

定义3^[2]  设P∈ob(Poset)，x，y∈P，称x是Z-Waybelow y的，记作x≪_Zy，若∀S∈Z(P)，∨S存在，

使得x≤s.记

定义4^[2]  设P∈ob(Poset)，称P是Z-连续的，若∀x∈P，∃S∈Z(P)且S⊆J(x)，使得x=∨S.

定义5^[2]  设P是Z-完备的偏序集，x∈P，A∈Z(P)，称A为x的一个Z-极小集，如果supA=x且∀S∈Z(P)，x≤supS⇒∀a∈A，∃s∈S，使得a≤s.

命题1^[4]  设P是Z-完备的偏序集，则下列条件等价：

(1) P是Z-连续Domain；

(2) ∀x∈P，x有Z-极小集.

定义6  设P是Z-完备的偏序集，x∈P，S∈Z(P)，若x≤supS，则称S为x的Z-覆盖.

定义7  设P是Z-完备的偏序集，x∈P，S为x的Z-覆盖，若∃D∈Z(P)，使得x=supD，且∀d∈D，∃s∈S，使得d≤s，则称D为x的相应于S的Z-准极小集.

定义8  设P是Z-完备的偏序集，∀x∈P，若对于x的任意Z-覆盖，x都有相应的Z-准极小集，则称x有Z-准极小集.

定义9  设P是Z-完备的偏序集，∀x∈P，x都有Z-准极小集，则称P是Z-准连续Domain.

命题2  设P是Z-完备的偏序集，x∈P，若x有Z-极小集，则x有Z-准极小集.

由以上的定义和命题得到以下结果：

定理1  Z-连续Domain是Z-准连续Domain.

证  由命题1知，若P是Z-连续Domain，则∀x∈P，x有Z-极小集.又由命题2知，x有Z-准极小集，所以由定义9知，P是Z-准连续Domain.

定义10  设P∈ob(Poset)，S∈Z(P)，称保序映射s↦x_s：S→P是P中的一个Z-网，记(x_s)_s∈S或(x_s).

命题3  设P∈ob(Poset)，P是Z-完备的偏序集，则P中的Z-集是Z-网，反之，Z-网也是Z-集.

证  ∀S∈Z(P)，嵌入映射s↦x_s=s：S→P是保序映射，则由Z-网的定义知(x_s)_s∈S是Z-网.反之，对任意P中Z-网(x_s)_s∈S，由Z-网的定义知，s↦x_s：S→P是保序映射.定义f：P→P，具体地，∀p∈P，若p∈S，f(p)=x_p；否则f(p)=x_∧S.由s↦x_s：S→P是保序映射及P是Z-交封闭半格知，f是保序映射.由Z子集系统的定义知

即Z-网也是Z-集.

定理2  设P是Z-完备的偏序集，则下列条件等价：

(1) P是Z-准连续Domain；

(2) ∀S∈Z(P)，∀x≤supS，∃J∈Z(P)且$J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right)$，使得x=supJ；

(3) ∀x∈P，∀S∈Z(P)，恒有$l\left( \left\{ x, \sup S \right\} \right)=\left\{ \sup J:J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right), J\in Z\left( P \right) \right\}$；

(4) ∀x∈P，∀Z-网(x_s)_s∈S，恒有

证  (1)⇒(2)  ∀S∈Z(P)，∀x≤supS，由P是Z-准连续Domain知，x有Z-准极小集，则∃J∈Z(P)，使得x=supJ且∀j∈J，∃s∈S，使得j≤s.又由x=supJ知，

所以j∈l({x，s})，从而

所以∃J∈Z(P)且$J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right)$，使得x=supJ.

(2)⇒(1)  ∀x∈P，∀S∈Z(P)，若x≤supS，则由(2) 知，∃J∈Z(P)，使得

由$J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right)$知，∀j∈J，∃s∈S，使得j∈l({x，s})即j≤x，j≤s.所以J是x相应于S的Z-准极小集.又由S的任意性知，x有Z-准极小集.再由x的任意性和Z-准连续Domain的定义知，P是Z-准连续Domain.

(2)⇒(3) 显然(3) 中不等式左边包含右边.另一方面，

则y≤x，y≤supS，由(2) 知，∃J∈Z(P)且$J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ y, s \right\} \right)$，使得y=supJ.由y≤x知

所以

从而不等式右边也包含左边.

(3)⇒(2) ∀x∈P，∀S∈Z(P)，x≤supS，则

即

由(3) 知

所以

即∃J∈Z(P)且$J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right)$，使得x=supJ.所以(2) 成立.

(3)⇒(4) 显然，由于每个Z-网都是Z-集.

(4)⇒(3) 显然，由于每个Z-集都是特殊的Z-网.

定义11^[2]  设P，Q∈ob(Poset)，称映射f：P→Q是Z-连续的，若∀S∈Z(P)，∨S存在，则有∨f(S)也存在且f(∨S)=∨f(S).

定理3  设L_i(i∈I)是有最小元的Z-准连续Domain，若

则$\prod\limits_{i\in I}{{{L}_{i}}}$是有最小元的Z-准连续Domain.其中D_i是D在第i个坐标的投影，且

证  $\forall x={{\left( {{x}_{i}} \right)}_{i\in I}}\in \prod\limits_{i\in I}{{{L}_{i}}}$，设$D\in Z\left( \prod\limits_{i\in I}{{{L}_{i}}} \right)$且x≤supD=(sup_LiD_i)_i∈I，其中D_i是D在第i个坐标的投影，则

由于每个L_i都是Z-准连续Domain，所以∃J_i∈Z(L_i)，使得x_i=supJ_i且∀j_i∈J_i，∃d_i∈D_i，使得j_i≤d_i，这样就有$\prod\limits_{i\in I}{{{L}_{i}}}$的Z-集J={(j_i)_i∈I：j_i∈J_i}，显然x=supJ，∀j∈J，J=(j_i)_i∈I，则j_i∈J_i，由上知存在d_i∈D_i，使得j_i≤d_i.取d=(d_i)_i∈I∈D，则j≤d，这样J就是x关于D的Z-准极小集.所以$\prod\limits_{i\in I}{{{L}_{i}}}$是有最小元的Z-准连续Domain.

定理4  设L是Z-准连续Domain，p：L→L是Z-连续投射，则p(L)是Z-准连续Domain.

证  ∀y∈p(L)，∃x∈L，使得y=p(x).设D∈Z(p(L))且p(x)≤supD，又由注1(2) 知D∈Z(L)，由L是Z-准连续Domain知，存在J∈Z(L)，使得p(x)=supJ且∀j∈J，∃d∈D，使得j≤d.由于p幂等且是Z-连续的，所以

显然p(J)∈Z[p(L)]且∀j∈J，∃d∈D，使得

所以p(J)是y相应于D的Z-准极小集.由D的任意性知，y有Z-准极小集.由y的任意性知p(L)是Z-准连续Domain.

定理5  设L是Z-准连续Domain，P⊆L是关于Z-集的并封闭的下集，则P在诱导序下是Z-准连续Domain.

证  由于P关于Z-集是并封闭的，则P在诱导序下是Z-完备的.设x∈P，D∈Z(P)且x≤supD，由注1知D∈Z(L).由于L是Z-准连续Domain，则x有相应于D的Z-准极小集，即∃J∈Z(L)，使得x=supJ且∀j∈J，∃d∈D，使得j≤d.由P是下集知J⊆P，则J∈Z(P)，(反之，若J不是P的Z-集，由于含入映射i：P→L是单调的，则i(J)=J不是L的Z-集，这与J∈Z(P)相矛盾)所以J是x相应于D的Z-准极小集，因此P在诱导序下是Z-准连续Domain.