謝曉林， 寇 輝

(四川大學數(shù)學學院, 成都, 610064)

1 引 言

冪domain理論是domain理論的重要組成部分, 其目的是為函數(shù)式程序語言的非確定性指稱語義提供數(shù)學模型. domain理論中有三種經典的冪結構, 分別是下冪domain (又稱Hoaer冪domain)、上冪domain (又稱Smyth冪domain)和凸冪domain (又稱Plotikin冪domain)[1-6], 且上述每種冪結構都有標準的拓撲表示.

近年來, 文獻[7-10]等對這些冪結構做了大量推廣. 總的來說，這些冪結構都是domain關于某種二元運算生成的自由代數(shù).2015年, Batenfeld和Sch?der[11]在一般的拓撲空間上引入冪空間結構, 通過布爾代數(shù)2賦予Sierpinski拓撲作為可觀察結構, 定義了上冪空間和下冪空間結構, 并稱之為觀察誘導的上(下) 冪空間 (observationally-induced lower and upper powerspace). 該工作為普通拓撲空間范疇應用于表示函數(shù)式程序的非確定性指稱語義提供了可能, 但是通過布爾代數(shù)2誘導的冪結構方法復雜，不易理解.

本文考慮一類特殊的拓撲空間——定向空間(等價于文獻[12]中的monotone determined space). 文獻[10]證明, 定向空間包含domain理論的基本對象——所有賦予Scott拓撲的定向完備偏序集, 且與連續(xù)函數(shù)一起構成Cartesian閉范疇, 定向空間是domain理論的一個擴展模型. 本文則考慮在定向空間范疇推廣冪domain結構, 通過自由代數(shù)的方式定義了定向下冪空間的概念, 證明每個定向空間的定向下冪空間存在并給出其具體構造. 一般情況下, 定向空間的定向下冪空間既不同于賦予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是兩個偏序集, 函數(shù)f:P→E稱為Scott連續(xù)如果它關于 Scott 拓撲σ(P) 和σ(E)是連續(xù)的.

本文的所有拓撲空間都要求具有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拓撲的概念.

下面介紹定向連續(xù)函數(shù).

定義2.3設X,Y是兩個T0空間.函數(shù)f:X→Y稱為定向連續(xù)如果它是單調的并且保持X的所有定向集的極限;等價地,(D,x)∈D(X)?(f(D),f(x))∈D(Y).

下面是定向連續(xù)函數(shù)的刻畫.

命題2.4[10]設X,Y是兩個T0空間.函數(shù)f:X→Y是X,Y之間的映射.

(i)f定向連續(xù)當且僅當?U∈d(Y),f-1(U)∈d(X).

(ii) 若X,Y是定向空間,則函數(shù)f連續(xù)當且僅當它是定向連續(xù)的.

接下來介紹定向空間的乘積.設X,Y是兩個定向空間.令X×Y表示X,Y的笛卡爾乘積,則該乘積上有一個自然的偏序:?(x1,y1),(x2,y2)∈X×Y,

我們稱該序為X×Y上的點態(tài)序.接下來,我們在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是另一個定向空間, 則函數(shù)f:X?Y→Z連續(xù)當且僅當它關于每個變量分別連續(xù).

記Dtop表示由所有定向空間及連續(xù)映射構成的范疇. 文獻[10]證明, Dtop包含所有賦予Scott拓撲的偏序集且是一個cartesian閉范疇; 特別地, 兩個定向空間X和Y的范疇乘積同構于X?Y. 因此, 定向空間是domain 理論的擴展模型.

3 定向空間的下冪空間

如前所述, 定向空間是domain 理論的擴展模型. 就像文獻[11]所做的工作一樣, 在定向空間范疇推廣冪domain結構是很有意義的. 本節(jié)將構造定向空間的下冪空間, 該結構是定向空間關于膨脹運算生成的自由代數(shù).

定義3.1設X是一個定向空間.

(i) 稱X上的一個二元運算⊕: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ù)的當且僅當它是單調的且任給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] (單位區(qū)間), 記AI={[a,1]:a∈I}, 則AI是I上的亞力山大拓撲. 容易驗證, (I,AI)是一個定向空間, 且賦予該拓撲后(I,max)是一個定向膨脹半格.

下面的引理表明一個定向空間上至多存在一個膨脹結構， 記Disl表示由所有定向膨脹半格和膨脹同態(tài)構成的范疇,因此范疇Disl可以看作定向空間范疇Dtop的子范疇.

接下來給出下冪空間的定義.

定義3.5設X是一個定向空間. 一個定向空間Z稱為X的下冪空間如果下述兩個條件成立：

(i)Z是一個定向膨脹半格, 即Z上的并運算∨存在且連續(xù);

由上述定義知, 若膨脹半格(Z1,∨)和(Z2,∨)都是定向空間X的下冪空間, 則存在拓撲同胚的膨脹同態(tài)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) 四個要求, 只需證明∪ 是連續(xù)的. ∪ 顯然是單調的. 由定理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上的一個二元運算. 則算子⊕是連續(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連續(xù).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是連續(xù)的.

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是一個連續(xù)函數(shù). 定義映射PL(f):PL(X)→PL(Y)如下: ?↓F∈LX,PL(f)(↓F)=↓f(F).容易看出,PL(f)是良定義的且保序. 運用上述定理的證明方法, 容易驗證PL(f)是兩個下冪空間之間的膨脹同態(tài)并. 若idX是恒等映射且g:Y→Z是Y到定向空間Z的連續(xù)映射,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 下冪結構間的關系

本節(jié)我們比較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是自然數(shù)集. 定義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是一個連續(xù)或擬連續(xù)domain. 則σ(C(X))|LP=O?L(LP), 即P賦予Scott拓撲作為定向空間, 其下冪空間PL(X)是下冪domainH(P)的子空間.