西南大学学报 (自然科学版)  2017, Vol. 39 Issue (8): 73-76.  DOI: 10.13718/j.cnki.xdzk.2017.08.010
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    马崛
    魏美华
    欢迎关注西南大学期刊社
     

  • Z准连续Domain的性质及其等价刻画    [PDF全文]
    马崛, 魏美华     
    榆林学院 数学与统计学院,陕西 榆林 719000
    摘要:引入了Z-准极小集,通过Z-准极小集定义了Z-准连续Domain,给出了Z-准连续Domain的等价刻画.
    关键词Z-准极小集    Z-准连续Domain    Z-连续Domain    

    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),AP,∀abA,∃cA,使得acbc,则称A为定向集.若P对定向并关闭,则称P为Dcpo. AP,记

    $ l\left( A \right) = \left\{ {x \in P:\forall a \in A, x \le a} \right\} $

    l(A)为AP中的所有下界之集.

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

    (1) ∀P∈ob(Poset),Z(P)⊆2P

    (2) ∀PQ∈ob(Poset),fPQ是保序映射,AZ(P)⇒f(A)∈Z(Q);

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

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

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

    (2) 设P∈ob(Poset),QP,则∀SZ(P),有SZ(Q).

    定义2[2]  设P∈ob(Poset),称偏序集PZ-完备的,若∀SZ(P),∨S存在.

    定义3[2]  设P∈ob(Poset),xyP,称xZ-Waybelow y的,记作xZy,若∀SZ(P),∨S存在,

    $ y \le \vee S \Rightarrow \exists s \in S $

    使得xs.记

    $ J\left( x \right) = \left\{ {y \in P\left| {y \ll {}_Zx} \right.} \right\} $

    定义4[2]  设P∈ob(Poset),称PZ-连续的,若∀xP,∃SZ(P)且SJ(x),使得x=∨S.

    定义5[2]  设PZ-完备的偏序集,xPAZ(P),称Ax的一个Z-极小集,如果supA=x且∀SZ(P),x≤supS⇒∀aA,∃sS,使得as.

    命题1[4]  设PZ-完备的偏序集,则下列条件等价:

    (1) PZ-连续Domain;

    (2) ∀xPxZ-极小集.

    定义6  设PZ-完备的偏序集,xPSZ(P),若x≤supS,则称SxZ-覆盖.

    定义7  设PZ-完备的偏序集,xPSxZ-覆盖,若∃DZ(P),使得x=supD,且∀dD,∃sS,使得ds,则称Dx的相应于SZ-准极小集.

    定义8  设PZ-完备的偏序集,∀xP,若对于x的任意Z-覆盖,x都有相应的Z-准极小集,则称xZ-准极小集.

    定义9  设PZ-完备的偏序集,∀xPx都有Z-准极小集,则称PZ-准连续Domain.

    命题2  设PZ-完备的偏序集,xP,若xZ-极小集,则xZ-准极小集.

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

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

      由命题1知,若PZ-连续Domain,则∀xPxZ-极小集.又由命题2知,xZ-准极小集,所以由定义9知,PZ-准连续Domain.

    定义10  设P∈ob(Poset),SZ(P),称保序映射sxsSPP中的一个Z-网,记(xs)sS或(xs).

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

      ∀S∈Z(P),嵌入映射sxs=sSP是保序映射,则由Z-网的定义知(xs)sSZ-网.反之,对任意PZ-网(xs)sS,由Z-网的定义知,sxsSP是保序映射.定义fPP,具体地,∀pP,若pSf(p)=xp;否则f(p)=xS.由sxsSP是保序映射及PZ-交封闭半格知,f是保序映射.由Z子集系统的定义知

    $ f\left( S \right) = {\left( {{x_s}} \right)_{s \in S}} \in Z\left( P \right) $

    Z-网也是Z-集.

    定理2  设PZ-完备的偏序集,则下列条件等价:

    (1) PZ-准连续Domain;

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

    (3) ∀xP,∀SZ(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) ∀xP,∀Z-网(xs)sS,恒有

    $ l\left( {\left\{ {x, { \vee _{s \in S}}{x_s}} \right\}} \right) = \left\{ {\sup J:J \subseteq \bigcup\limits_{{x_s} \in {{\left( {{x_s}} \right)}_{s \in S}}} {l\left( {\left\{ {x, s} \right\}} \right), J \in Z\left( P \right)} } \right\} $

      (1)⇒(2)  ∀SZ(P),∀x≤supS,由PZ-准连续Domain知,xZ-准极小集,则∃JZ(P),使得x=supJ且∀jJ,∃sS,使得js.又由x=supJ知,

    $ \forall j \in J, j \le \sup J = x $

    所以jl({xs}),从而

    $ J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)} $

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

    (2)⇒(1)  ∀xP,∀SZ(P),若x≤supS,则由(2) 知,∃JZ(P),使得

    $ \begin{array}{*{20}{c}} {x = \sup J}&{J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)} } \end{array} $

    $J\subseteq \underset{s\in S}{\mathop{\cup }}\, l\left( \left\{ x, s \right\} \right)$知,∀jJ,∃sS,使得jl({xs})即jxjs.所以Jx相应于SZ-准极小集.又由S的任意性知,xZ-准极小集.再由x的任意性和Z-准连续Domain的定义知,PZ-准连续Domain.

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

    $ \forall y \in l\left( {\left\{ {x, \sup S} \right\}} \right) $

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

    $ J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {y, s} \right\}} \right)} \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)} $

    所以

    $ y \in \left\{ {\sup J:J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)}, J \in Z\left( P \right)} \right\} $

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

    (3)⇒(2) ∀xP,∀SZ(P),x≤supS,则

    $ l\left( {\left\{ {x, \sup S} \right\}} \right) = \downarrow x $

    $ x \in l\left( {\left\{ {x, \sup S} \right\}} \right) $

    由(3) 知

    $ l\left( {\left\{ {x, \sup S} \right\}} \right) = \left\{ {\sup J:J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)}, J \in Z\left( P \right)} \right\} $

    所以

    $ x \in \left\{ {\sup J:J \subseteq \bigcup\limits_{s \in S} {l\left( {\left\{ {x, s} \right\}} \right)}, J \in Z\left( P \right)} \right\} $

    即∃JZ(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]  设PQ∈ob(Poset),称映射fPQZ-连续的,若∀SZ(P),∨S存在,则有∨f(S)也存在且f(∨S)=∨f(S).

    定理3  设Li(iI)是有最小元的Z-准连续Domain,若

    $ D \in Z\left( {\prod\limits_{i \in I} {{L_i}} } \right) \Leftrightarrow {D_i} \in Z\left( {{L_i}} \right) $

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

    $ \forall x = {\left( {{x_i}} \right)_{i \in I}}, y = {\left( {{y_i}} \right)_{i \in I}} \in \prod\limits_{i \in I} {{L_i}}, x \le y \Leftrightarrow {x_i} \le {y_i}\left( {\forall i \in I} \right) $

      $\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=(supLiDi)iI,其中DiD在第i个坐标的投影,则

    $ {D_i} \in \left\{ {Z\left( {{L_i}} \right)} \right\}且\;{x_i} \le {\sup _{{L_i}}}{D_i}\;\;\;\forall i \in I $

    由于每个Li都是Z-准连续Domain,所以∃JiZ(Li),使得xi=supJi且∀jiJi,∃diDi,使得jidi,这样就有$\prod\limits_{i\in I}{{{L}_{i}}}$Z-集J={(ji)iIjiJi},显然x=supJ,∀jJJ=(ji)iI,则jiJi,由上知存在diDi,使得jidi.取d=(di)iID,则jd,这样J就是x关于DZ-准极小集.所以$\prod\limits_{i\in I}{{{L}_{i}}}$是有最小元的Z-准连续Domain.

    定理4  设LZ-准连续Domain,pLLZ-连续投射,则p(L)是Z-准连续Domain.

      ∀yp(L),∃xL,使得y=p(x).设DZ(p(L))且p(x)≤supD,又由注1(2) 知DZ(L),由LZ-准连续Domain知,存在JZ(L),使得p(x)=supJ且∀jJ,∃dD,使得jd.由于p幂等且是Z-连续的,所以

    $ p\left( x \right) = p\left( {\sup J} \right) = \sup \left( {p\left( J \right)} \right) $

    显然p(J)∈Z[p(L)]且∀jJ,∃dD,使得

    $ p\left( j \right) \le p\left( d \right) = d $

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

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

      由于P关于Z-集是并封闭的,则P在诱导序下是Z-完备的.设xPDZ(P)且x≤supD,由注1知DZ(L).由于LZ-准连续Domain,则x有相应于DZ-准极小集,即∃JZ(L),使得x=supJ且∀jJ,∃dD,使得jd.由P是下集知JP,则JZ(P),(反之,若J不是PZ-集,由于含入映射iPL是单调的,则i(J)=J不是LZ-集,这与JZ(P)相矛盾)所以Jx相应于DZ-准极小集,因此P在诱导序下是Z-准连续Domain.

    参考文献
    [1] GIERZ G, HOFMANN K H, KEIMEL K, et al. Continuous Lattices and Domain[M]. Cambridge: Cambridge University Press, 2003.
    [2] 阮小军, 毕含宇, 赵洋. Z-极小集及其对Z-连续偏序集的应用[J]. 江西师范大学学报(自然科学版), 2006, 30(4): 328-335.
    [3] 尚云. 连续Domain的若干特征定理[J]. 西北大学学报(自然科学版), 2004, 34(4): 631-635.
    [4] 郭智莲, 赵彬. 准连续Domain和稳定映射[J]. 纺织高校基础科学学报, 2006, 19(3): 210-213.
    Properties and Characterizations of Z-Precontinous Posets
    MA Jue, WEI Mei-hua     
    College of Mathematics and statistics, Yulin University, Yulin Shaanxi 719000, China
    Abstract: In this paper, the notion of Z-precontinous Domain is introduced based on the Z-preminimal sets and Z-precontinous Domain are characterized terms of equalities.
    Key words: Z-preminimal sets    Z-precontinous Domain    Z-continous Domain    
    X