谢晓林， 寇 辉

(四川大学数学学院, 成都, 610064)

1 引 言

幂domain理论是domain理论的重要组成部分, 其目的是为函数式程序语言的非确定性指称语义提供数学模型. domain理论中有三种经典的幂结构, 分别是下幂domain (又称Hoaer幂domain)、上幂domain (又称Smyth幂domain)和凸幂domain (又称Plotikin幂domain)[1-6], 且上述每种幂结构都有标准的拓扑表示.

近年来, 文献[7-10]等对这些幂结构做了大量推广. 总的来说，这些幂结构都是domain关于某种二元运算生成的自由代数.2015年, Batenfeld和Schöder[11]在一般的拓扑空间上引入幂空间结构, 通过布尔代数2赋予Sierpinski拓扑作为可观察结构, 定义了上幂空间和下幂空间结构, 并称之为观察诱导的上(下) 幂空间 (observationally-induced lower and upper powerspace). 该工作为普通拓扑空间范畴应用于表示函数式程序的非确定性指称语义提供了可能, 但是通过布尔代数2诱导的幂结构方法复杂，不易理解.

本文考虑一类特殊的拓扑空间——定向空间(等价于文献[12]中的monotone determined space). 文献[10]证明, 定向空间包含domain理论的基本对象——所有赋予Scott拓扑的定向完备偏序集, 且与连续函数一起构成Cartesian闭范畴, 定向空间是domain理论的一个扩展模型. 本文则考虑在定向空间范畴推广幂domain结构, 通过自由代数的方式定义了定向下幂空间的概念, 证明每个定向空间的定向下幂空间存在并给出其具体构造. 一般情况下, 定向空间的定向下幂空间既不同于赋予Scott 拓扑的定向完备偏序集的下幂domain, 也不同于普通拓扑空间上观察诱导的下幂空间.

2 预备知识

下面我们介绍本文需要的概念. 某些关于 domain理论、拓扑学及范畴论的基础知识请参见文献[1, 13-14].

设P是一个非空集合.P上的一个关系≤称为偏序, 如果≤满足反身性(x≤x)，传递性(x≤y&y≤z⟹x≤z)和反对称性(x≤y&y≤x⟹x=y). 称P是一个偏序集若，P被赋予某种偏序≤. 给定子集A⊆P, 记 ↓A={x∈P:∃a∈A,x≤a}, ↑A={x∈P:∃a∈P,a≤x}.A称为下集(上集) 如果A=↓A(A=↑A). 一个非空子集D⊆P称为定向的如果D的非空有限子集在D中有上界. 特别地, 每个定向子集都有上确界(记为∨D)的偏序集称为定向完备偏序集, 简称dcpo. 偏序集P的子集U称为 Scott开集如果它是上集且对任意定向集D⊆P, 若 ∨D存在且属于U则U∩D≠∅成立.P的所有 Scott 开集形成一个拓扑, 称为Scott拓扑并记为σ(P). 设P,E是两个偏序集, 函数f:P→E称为Scott连续如果它关于 Scott 拓扑σ(P) 和σ(E)是连续的.

本文的所有拓扑空间都要求具有T0分离性. 拓扑空间X的一个网是一个映射ξ:J→X, 这里J是一个定向集. 因此, 偏序集的每个定向子集都可看成一个网, 其指标集就是它自己. 通常, 我们把一个网表示为 (xj)j∈J或 (xj). 设x∈X, 称(xj)收敛到x, 记为 (xj)→x或x≡limxj, 若 (xj) 终在x的每个开邻域, 即, 任给x的开邻域U, 存在j0∈J使得对任意j∈J,j≥j0⟹xj∈U,特别地,{y}表示取值为常值y的常值网.

设X是一个T0拓扑空间，其拓扑记为O(X)，X上的特殊化序定义如下:

命题2.1[1,13]对于T0空间X,下列性质总成立:

(i) 对任意开集U⊆X,U=↑U;

(ii) 对任意闭集A⊆X,A=↓A;

定义2.2[10]设X是一个T0空间.

(i) 一个子集U⊆X称为定向开集如果 ∀(D,x)∈D(X),x∈U⟹D∩U≠Ø. 记d(X)表示由X的所有定向开集组成的集合.

(ii) 称X为一个定向空间如果X每个定向开集都是开集, 即,d(X)=O(X).

(ii) 这里的定向空间等价于文中的monotone determined space.

(iii) 每个偏序集赋予Scott拓扑是一个定向空间. 因此, 定向空间扩展Scott拓扑的概念.

下面介绍定向连续函数.

定义2.3设X,Y是两个T0空间.函数f:X→Y称为定向连续如果它是单调的并且保持X的所有定向集的极限;等价地,(D,x)∈D(X)⟹(f(D),f(x))∈D(Y).

下面是定向连续函数的刻画.

命题2.4[10]设X,Y是两个T0空间.函数f:X→Y是X,Y之间的映射.

(i)f定向连续当且仅当∀U∈d(Y),f-1(U)∈d(X).

(ii) 若X,Y是定向空间,则函数f连续当且仅当它是定向连续的.

接下来介绍定向空间的乘积.设X,Y是两个定向空间.令X×Y表示X,Y的笛卡尔乘积,则该乘积上有一个自然的偏序:∀(x1,y1),(x2,y2)∈X×Y,

我们称该序为X×Y上的点态序.接下来,我们在X×Y定义一个拓扑空间X⊗Y如下:

(i)X⊗Y的承载集是X×Y;

(ii)X⊗Y的拓扑由如下方式生成: 任给≤-定向集D⊆X×Y及(x,y)∈X×Y,D→(x,y)∈X⊗Y⟺π1D→x∈X,π2D→y∈Y;

(iii) 子集U⊆X×Y是开的当且仅当对任意按上述方式定义的定向极限D→(x,y), (x,y)∈U⟹U∩D≠Ø.

定理2.5[10]设X和Y是两个定向空间.

(ii) 设Z是另一个定向空间, 则函数f:X⊗Y→Z连续当且仅当它关于每个变量分别连续.

记Dtop表示由所有定向空间及连续映射构成的范畴. 文献[10]证明, Dtop包含所有赋予Scott拓扑的偏序集且是一个cartesian闭范畴; 特别地, 两个定向空间X和Y的范畴乘积同构于X⊗Y. 因此, 定向空间是domain 理论的扩展模型.

3 定向空间的下幂空间

如前所述, 定向空间是domain 理论的扩展模型. 就像文献[11]所做的工作一样, 在定向空间范畴推广幂domain结构是很有意义的. 本节将构造定向空间的下幂空间, 该结构是定向空间关于膨胀运算生成的自由代数.

定义3.1设X是一个定向空间.

(i) 称X上的一个二元运算⊕:X⊗X→X为一个膨胀运算如果它是连续的且满足以下四个条件: ∀x,y,z∈X,

a.x⊕x=x,∀x∈X;

b.(x⊕y)⊕z=x⊕(y⊕z),∀x,y,z∈X;

c.x⊕y=y⊕x;

d.x⊕y≥x,∀x,y∈X.

(ii) 若⊕是X上的膨胀运算, 则称(X,⊕)为一个定向膨胀半格， 即定向膨胀半格就是那些带有膨胀运算的定向空间.

由定理2.5,(ii)知, 定向空间X上的膨胀运算⊕是连续的当且仅当它是单调的且任给x,y∈X及定向集D⊆X, 若x≡limD则x⊕y≡lim(D⊕y). 这里,D⊕y={d⊕y:d∈D}.

例3.2(i) 设P是一个偏序集并赋予Scott拓扑, 且对任意a,b∈P,a和b在P中的上确界存在(记为a∨b). 则(P,∨)是一个定向膨胀半格.

(ii) 令I=[0,1] (单位区间), 记AI={[a,1]:a∈I}, 则AI是I上的亚力山大拓扑. 容易验证, (I,AI)是一个定向空间, 且赋予该拓扑后(I,max)是一个定向膨胀半格.

下面的引理表明一个定向空间上至多存在一个膨胀结构， 记Disl表示由所有定向膨胀半格和膨胀同态构成的范畴,因此范畴Disl可以看作定向空间范畴Dtop的子范畴.

接下来给出下幂空间的定义.

定义3.5设X是一个定向空间. 一个定向空间Z称为X的下幂空间如果下述两个条件成立：

(i)Z是一个定向膨胀半格, 即Z上的并运算∨存在且连续;

由上述定义知, 若膨胀半格(Z1,∨)和(Z2,∨)都是定向空间X的下幂空间, 则存在拓扑同胚的膨胀同态g:Z1→Z2. 因此，在序同构且拓扑同胚意义下, 定向空间的下幂空间唯一. 特别地, 我们把任意定向空间X的下幂空间记为PL(X).

下面, 我们将通过具体构造的方式证明每个定向空间X的下幂空间存在.

设X是一个定向空间. 记

LX={↓F:F⊆finX},

这里F⊆finX的非空有限子集. 在LX上定义序关系≤L如下:↓F1≤L↓F2⟺↓F1⊆↓F2.

设D⊆LX是定向集 (关于上述序关系≤L), ↓F∈LX. 定义符号D⟹L↓F表示下述意义的收敛:D⟹L↓F⟺∀a∈F,∃X的定向集Da⊆∪D满足Da→a.

一个子集U⊆LX称为LX的⟹L收敛开集如果对LX中的任意定向集D及↓F∈LX, 若D⟹L↓F∈U, 则D∩U≠Ø. 记O⟹L(LX)表示由LX的所有⟹L收敛开集组成的集族.

命题3.6设X是一个定向拓扑空间, 则下述各条成立:

(i) (LX,O⟹L(LX))是一个拓扑空间,简记为LX;

(iii) (LX,O⟹L(LX))是定向空间,即O⟹L(LX)=d(LX).

(iii) 对任意一个拓扑空间X,有O(X)⊆d(X), 于是O⟹L(LX)⊆d(LX). 另一方面, 根据⟹L收敛的定义, 若LX的定向集D⟹L↓F, 则D关于拓扑O⟹L(LX)收敛到↓F. 因此, 由定向开集的定义, 若D⟹L↓F∈U∈d(LX), 则必有U∩D≠Ø. 这表明,U∈O⟹L(LX), 从而O⟹L(LX)=d(LX), 即, (LX,O⟹L(LX)) 是定向空间.

命题3.8设X是一个定向空间. 则(LX,O⟹L(LX))关于集合并运算∪是一个定向膨胀半格.

证明 由命题3.6, (LX,O⟹L(LX))是一个定向空间. 下证∪是一个膨胀运算. 任给↓F1,Z↓F2∈LX, 则↓F1∪↓F2=↓(F1∪F2)∈LX. 显然∪运算满足定义3.1 中的(a),(b),(c),(d) 四个要求, 只需证明∪ 是连续的. ∪ 显然是单调的. 由定理2.5及命题3.7, 我们只需证明： 对任意定向集D⊆LX及↓F,↓G∈LX, 若D⟹L↓F, 则G∪D⟹L(↓G∪↓F)=↓(G∪F). 这里G∪D={↓(G∪F′):↓F′∈D}也是一个定向集. 任给a∈G∪F, 若a∈G, 则{a}→a; 若a∈F, 则由D⟹L↓F存在D⊆∪D使得D→a. 所以由⟹L收敛的定义, 有G∪D⟹L↓(G∪F).

引理3.9设⊕:X×X→X是定向空间X上的一个二元运算. 则算子⊕是连续的当且仅当任给两个定向集D1,D2⊆X及x1,x2∈X, 若Di→xi(i=1,2), 则D1⊕D2→x1⊕x2. 这里,D1⊕D2={d1⊕d2:(d1,d1)∈D1×D2}.

下面的定理是本文的主要结果.

证明 定义映射i:X→LX如下：∀x∈X,i(x)=↓x. 下证映射i连续.i显然单调. 设定向集D⊆X及x∈X满足D→x. 令D={↓d:d∈D}, 则D是LX的定向集并且D⟹L↓↓x. 注意到i(D)=D, 所以i(D)⟹L↓x=i(x). 由定理2.5, 映射i是连续的.

f(D1)∨f(D2)∨…∨f(Dk)→f(b1)∨…

∨f(bk).

(1)

这里

f(D1)∨f(D2)…∨f(Dk)=

{f(d1)∨f(d2)∨…∨f(dk):(d1,d2,…,dk)∈

f(D1)∨…∨f(Dn)⊆

↓{∨f(F):↓F∈D}

(**)

g(↓F)=g(↓a1∪↓a2…∪↓an)=

g(↓a1)∨g(↓a2)∨…∨g(↓an)=

由于下幂空间在序同构及拓扑同胚的意义下是唯一的, 因此我们直接把每个定向空间X的下幂空间记为PL(X)=(LX,∪).

设X,Y是两个定向空间,f:X→Y是一个连续函数. 定义映射PL(f):PL(X)→PL(Y)如下: ∀↓F∈LX,PL(f)(↓F)=↓f(F).容易看出,PL(f)是良定义的且保序. 运用上述定理的证明方法, 容易验证PL(f)是两个下幂空间之间的膨胀同态并. 若idX是恒等映射且g:Y→Z是Y到定向空间Z的连续映射,PL(idX)=idPL(X),PL(g∘f)=PL(g)∘PL(f). 因此,PL:Dtop→Disl是定向空间范畴Dtop到定向膨胀半格范畴Disl的函子. 令U:Disl→Dtop表示遗忘函子. 则由定理3.10, 我们有下述结果.

推论3.11函子PL是遗忘函子U的左伴随, 即, 定向膨胀半格范畴Disl是定向空间范畴Dtop的反射子范畴.

4 下幂结构间的关系

本节我们比较dcpo的下幂domain、拓扑空间的观察诱导的下幂空间及定向空间的下幂空间之间的关系.

设X的一个拓扑空间 (其拓扑记为O(X)). 记C(X)是由X的所有非空闭集组成的集族. 显然,C(X)关于集合的有限并∪封闭. 任给U∈O(X), 令〈U〉={A∈C(X):A∩U≠Ø}.容易验证, {〈U〉:U∈O(X)}关于有限交和任意并封闭, 构成C(X)的一个拓扑, 该拓扑称为C(X) 的下Vietoris 拓扑并记为VL(C(X)). 同时,C(X)关于集合包含关系是一个dcpo.C(X)上的Scott拓扑记为σ(C(X)). 容易验证, 下Vietoris 拓扑VL(C(X))粗于Scott拓扑σ(C(X)), 即,VL(C(X))⊆σ(C(X)). 特别地, 记POL(X)=(C(X),∪)赋予下Vietoris 拓扑VL(C(X)), 记H(X)=(C(X),∪)赋予Scott 拓扑σ(C(X)).

定理4.1[1]设P是一个dcpo并赋予Scott拓扑σ(P). 则H(P) 同构于P的下幂domain (又称为Hoare 幂domain), 即H(P)是P的自由dcpo并半格.

定理4.2[11]设X是一个拓扑空间. 则PO L(X) 同构于X的观察诱导的下幂空间 (the observationally-induced lower powerspace overX).

例4.3设P=(N×N)∪{∞}, 其中N是自然数集. 定义P上的序关系如下: ∀x,y∈P,x≤y当且仅当下列条件之一成立:

·y=∞;

·∃n0∈N,x=(m,n0),y=(m′,n0) 且m′-m≥0.

显然,P是一个dcpo. 容易验证, 一个非空子集A是P的 Scott闭集当且仅当A=P或者存在P中一个反链B使得A=↓B. 因此,V≠〈V〉 对任意n∈N, 令Dn=N×{n}, 则Dn是一个定向集且∨(N×{n})=∞. 任给U⊆P,U是Scott开集当且仅当U=Ø或D∩Dn≠Ø. 所以,P的每个非空Scott开集等于它的极小元集minU的上集. 设U⊆C(P), 则U是关于下Vietoris 拓扑的开集当且仅当存在U∈σ(P)使得U={B∈C(P):B∩minU≠Ø}. 令

V={A∈C(P):∃n∈N,Z(5,n)∈A}∪{A∈

C(P):∃n∈N,Z(4,n),(4,n+1)∈A}.

容易验证,V是C(P)的一个Scott开集, 且对任意V∈σ(P),V≠〈V〉. 因此V不是下Vietoris 拓扑的开集. 这表明,H(P)≠POL(P).

上述例子说明, 赋予Scott拓扑的定向完备偏序集上的下幂domain与观察诱导的下幂空间一般来说是不相等的. 接下来考虑下幂domain与定向空间的下幂空间的关系.

设P是一个dcpo并赋予Scott拓扑σ(P). 以

σ(C(P))|LP={U∩LP:U∈σ(C(X))}

表示C(P) 的Scott拓扑遗传到LP上的拓扑. 对任意V∈O⟹L(LP), 记

↑C(P)V={A∈C(P):∃↓F∈V,Z↓F⊆A}.

命题4.4设P是一个dcpo并赋予Scott拓扑σ(P). 则σ(C(X))|LP⊆O⟹L(LP). 特别地,σ(C(X))|LP=O⟹L(LP)当且仅当∀V∈O⟹L(LP), ↑C(P)V∈σ(C(P)).

另一方面, 任给非空Scott闭集∈U, 令F(A)={↓F:F⊆finA}, 则F(A)是LP的定向集且A=∪F(A). 从而存在A的非空有限集F使得↓F∈U. 这表明,U=↑C(P)(U∩LP). 因此,σ(C(X))|LP=O⟹L(LP)当且仅当∀V∈O⟹L(LP), ↑C(P)V∈σ(C(P)).

设A是dcpoP的任意子集. 令A1=↓{x∈P:∃定向集D⊆↓A,∨D=x}.

推论4.6设P是一个连续或拟连续domain. 则σ(C(X))|LP=O⟹L(LP), 即P赋予Scott拓扑作为定向空间, 其下幂空间PL(X)是下幂domainH(P)的子空间.