謝曉林， 寇 輝

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

1 引 言

冪domain理論是domain理論的重要組成部分, 其目的是為函數(shù)式程序語言的非確定性指稱語義提供數(shù)學(xué)模型. domain理論中有三種經(jīng)典的冪結(jié)構(gòu), 分別是下冪domain (又稱Hoaer冪domain)、上冪domain (又稱Smyth冪domain)和凸冪domain (又稱Plotikin冪domain)[1-6], 且上述每種冪結(jié)構(gòu)都有標(biāo)準(zhǔn)的拓?fù)浔硎?

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

本文考慮一類特殊的拓?fù)淇臻g——定向空間(等價于文獻[12]中的monotone determined space). 文獻[10]證明, 定向空間包含domain理論的基本對象——所有賦予Scott拓?fù)涞亩ㄏ蛲陚淦蚣? 且與連續(xù)函數(shù)一起構(gòu)成Cartesian閉范疇, 定向空間是domain理論的一個擴展模型. 本文則考慮在定向空間范疇推廣冪domain結(jié)構(gòu), 通過自由代數(shù)的方式定義了定向下冪空間的概念, 證明每個定向空間的定向下冪空間存在并給出其具體構(gòu)造. 一般情況下, 定向空間的定向下冪空間既不同于賦予Scott 拓?fù)涞亩ㄏ蛲陚淦蚣南聝鏳omain, 也不同于普通拓?fù)淇臻g上觀察誘導(dǎo)的下冪空間.

2 預(yù)備知識

下面我們介紹本文需要的概念. 某些關(guān)于 domain理論、拓?fù)鋵W(xué)及范疇論的基礎(chǔ)知識請參見文獻[1, 13-14].

設(shè)P是一個非空集合.P上的一個關(guān)系≤稱為偏序, 如果≤滿足反身性(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 開集形成一個拓?fù)? 稱為Scott拓?fù)洳⒂洖棣?P). 設(shè)P,E是兩個偏序集, 函數(shù)f:P→E稱為Scott連續(xù)如果它關(guān)于 Scott 拓?fù)洇?P) 和σ(E)是連續(xù)的.

本文的所有拓?fù)淇臻g都要求具有T0分離性. 拓?fù)淇臻gX的一個網(wǎng)是一個映射ξ:J→X, 這里J是一個定向集. 因此, 偏序集的每個定向子集都可看成一個網(wǎng), 其指標(biāo)集就是它自己. 通常, 我們把一個網(wǎng)表示為 (xj)j∈J或 (xj). 設(shè)x∈X, 稱(xj)收斂到x, 記為 (xj)→x或x≡limxj, 若 (xj) 終在x的每個開鄰域, 即, 任給x的開鄰域U, 存在j0∈J使得對任意j∈J,j≥j0?xj∈U,特別地,{y}表示取值為常值y的常值網(wǎng).

設(shè)X是一個T0拓?fù)淇臻g，其拓?fù)溆洖镺(X)，X上的特殊化序定義如下:

命題2.1[1,13]對于T0空間X,下列性質(zhì)總成立:

(i) 對任意開集U?X,U=↑U;

(ii) 對任意閉集A?X,A=↓A;

定義2.2[10]設(shè)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拓?fù)涫且粋€定向空間. 因此, 定向空間擴展Scott拓?fù)涞母拍?

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

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

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

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

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

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

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

我們稱該序為X×Y上的點態(tài)序.接下來,我們在X×Y定義一個拓?fù)淇臻gX?Y如下:

(i)X?Y的承載集是X×Y;

(ii)X?Y的拓?fù)溆扇缦路绞缴? 任給≤-定向集D?X×Y及(x,y)∈X×Y,D→(x,y)∈X?Y?π1D→x∈X,π2D→y∈Y;

(iii) 子集U?X×Y是開的當(dāng)且僅當(dāng)對任意按上述方式定義的定向極限D(zhuǎn)→(x,y), (x,y)∈U?U∩D≠?.

定理2.5[10]設(shè)X和Y是兩個定向空間.

(ii) 設(shè)Z是另一個定向空間, 則函數(shù)f:X?Y→Z連續(xù)當(dāng)且僅當(dāng)它關(guān)于每個變量分別連續(xù).

記Dtop表示由所有定向空間及連續(xù)映射構(gòu)成的范疇. 文獻[10]證明, Dtop包含所有賦予Scott拓?fù)涞钠蚣沂且粋€cartesian閉范疇; 特別地, 兩個定向空間X和Y的范疇乘積同構(gòu)于X?Y. 因此, 定向空間是domain 理論的擴展模型.

3 定向空間的下冪空間

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

定義3.1設(shè)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ù)的當(dāng)且僅當(dāng)它是單調(diào)的且任給x,y∈X及定向集D?X, 若x≡limD則x⊕y≡lim(D⊕y). 這里,D⊕y={d⊕y:d∈D}.

例3.2(i) 設(shè)P是一個偏序集并賦予Scott拓?fù)? 且對任意a,b∈P,a和b在P中的上確界存在(記為a∨b). 則(P,∨)是一個定向膨脹半格.

(ii) 令I(lǐng)=[0,1] (單位區(qū)間), 記AI={[a,1]:a∈I}, 則AI是I上的亞力山大拓?fù)? 容易驗證, (I,AI)是一個定向空間, 且賦予該拓?fù)浜?I,max)是一個定向膨脹半格.

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

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

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

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

由上述定義知, 若膨脹半格(Z1,∨)和(Z2,∨)都是定向空間X的下冪空間, 則存在拓?fù)渫叩呐蛎浲瑧B(tài)g:Z1→Z2. 因此，在序同構(gòu)且拓?fù)渫咭饬x下, 定向空間的下冪空間唯一. 特別地, 我們把任意定向空間X的下冪空間記為PL(X).

下面, 我們將通過具體構(gòu)造的方式證明每個定向空間X的下冪空間存在.

設(shè)X是一個定向空間. 記

LX={↓F:F?finX},

這里F?finX的非空有限子集. 在LX上定義序關(guān)系≤L如下:↓F1≤L↓F2?↓F1?↓F2.

設(shè)D?LX是定向集 (關(guān)于上述序關(guān)系≤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設(shè)X是一個定向拓?fù)淇臻g, 則下述各條成立:

(i) (LX,O?L(LX))是一個拓?fù)淇臻g,簡記為LX;

(iii) (LX,O?L(LX))是定向空間,即O?L(LX)=d(LX).

(iii) 對任意一個拓?fù)淇臻gX,有O(X)?d(X), 于是O?L(LX)?d(LX). 另一方面, 根據(jù)?L收斂的定義, 若LX的定向集D?L↓F, 則D關(guān)于拓?fù)銸?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設(shè)X是一個定向空間. 則(LX,O?L(LX))關(guān)于集合并運算∪是一個定向膨脹半格.

證明 由命題3.6, (LX,O?L(LX))是一個定向空間. 下證∪是一個膨脹運算. 任給↓F1,Z↓F2∈LX, 則↓F1∪↓F2=↓(F1∪F2)∈LX. 顯然∪運算滿足定義3.1 中的(a),(b),(c),(d) 四個要求, 只需證明∪ 是連續(xù)的. ∪ 顯然是單調(diào)的. 由定理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設(shè)⊕:X×X→X是定向空間X上的一個二元運算. 則算子⊕是連續(xù)的當(dāng)且僅當(dāng)任給兩個定向集D1,D2?X及x1,x2∈X, 若Di→xi(i=1,2), 則D1⊕D2→x1⊕x2. 這里,D1⊕D2={d1⊕d2:(d1,d1)∈D1×D2}.

下面的定理是本文的主要結(jié)果.

證明 定義映射i:X→LX如下：?x∈X,i(x)=↓x. 下證映射i連續(xù).i顯然單調(diào). 設(shè)定向集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)=

由于下冪空間在序同構(gòu)及拓?fù)渫叩囊饬x下是唯一的, 因此我們直接把每個定向空間X的下冪空間記為PL(X)=(LX,∪).

設(shè)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, 我們有下述結(jié)果.

推論3.11函子PL是遺忘函子U的左伴隨, 即, 定向膨脹半格范疇Disl是定向空間范疇Dtop的反射子范疇.

4 下冪結(jié)構(gòu)間的關(guān)系

本節(jié)我們比較dcpo的下冪domain、拓?fù)淇臻g的觀察誘導(dǎo)的下冪空間及定向空間的下冪空間之間的關(guān)系.

設(shè)X的一個拓?fù)淇臻g (其拓?fù)溆洖镺(X)). 記C(X)是由X的所有非空閉集組成的集族. 顯然,C(X)關(guān)于集合的有限并∪封閉. 任給U∈O(X), 令〈U〉={A∈C(X):A∩U≠?}.容易驗證, {〈U〉:U∈O(X)}關(guān)于有限交和任意并封閉, 構(gòu)成C(X)的一個拓?fù)? 該拓?fù)浞Q為C(X) 的下Vietoris 拓?fù)洳⒂洖閂L(C(X)). 同時,C(X)關(guān)于集合包含關(guān)系是一個dcpo.C(X)上的Scott拓?fù)溆洖棣?C(X)). 容易驗證, 下Vietoris 拓?fù)銿L(C(X))粗于Scott拓?fù)洇?C(X)), 即,VL(C(X))?σ(C(X)). 特別地, 記POL(X)=(C(X),∪)賦予下Vietoris 拓?fù)銿L(C(X)), 記H(X)=(C(X),∪)賦予Scott 拓?fù)洇?C(X)).

定理4.1[1]設(shè)P是一個dcpo并賦予Scott拓?fù)洇?P). 則H(P) 同構(gòu)于P的下冪domain (又稱為Hoare 冪domain), 即H(P)是P的自由dcpo并半格.

定理4.2[11]設(shè)X是一個拓?fù)淇臻g. 則PO L(X) 同構(gòu)于X的觀察誘導(dǎo)的下冪空間 (the observationally-induced lower powerspace overX).

例4.3設(shè)P=(N×N)∪{∞}, 其中N是自然數(shù)集. 定義P上的序關(guān)系如下: ?x,y∈P,x≤y當(dāng)且僅當(dāng)下列條件之一成立:

·y=∞;

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

顯然,P是一個dcpo. 容易驗證, 一個非空子集A是P的 Scott閉集當(dāng)且僅當(dāng)A=P或者存在P中一個反鏈B使得A=↓B. 因此,V≠〈V〉 對任意n∈N, 令Dn=N×{n}, 則Dn是一個定向集且∨(N×{n})=∞. 任給U?P,U是Scott開集當(dāng)且僅當(dāng)U=?或D∩Dn≠?. 所以,P的每個非空Scott開集等于它的極小元集minU的上集. 設(shè)U?C(P), 則U是關(guān)于下Vietoris 拓?fù)涞拈_集當(dāng)且僅當(dāng)存在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 拓?fù)涞拈_集. 這表明,H(P)≠POL(P).

上述例子說明, 賦予Scott拓?fù)涞亩ㄏ蛲陚淦蚣系南聝鏳omain與觀察誘導(dǎo)的下冪空間一般來說是不相等的. 接下來考慮下冪domain與定向空間的下冪空間的關(guān)系.

設(shè)P是一個dcpo并賦予Scott拓?fù)洇?P). 以

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

表示C(P) 的Scott拓?fù)溥z傳到LP上的拓?fù)? 對任意V∈O?L(LP), 記

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

命題4.4設(shè)P是一個dcpo并賦予Scott拓?fù)洇?P). 則σ(C(X))|LP?O?L(LP). 特別地,σ(C(X))|LP=O?L(LP)當(dāng)且僅當(dāng)?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)當(dāng)且僅當(dāng)?V∈O?L(LP), ↑C(P)V∈σ(C(P)).

設(shè)A是dcpoP的任意子集. 令A(yù)1=↓{x∈P:?定向集D?↓A,∨D=x}.

推論4.6設(shè)P是一個連續(xù)或擬連續(xù)domain. 則σ(C(X))|LP=O?L(LP), 即P賦予Scott拓?fù)渥鳛槎ㄏ蚩臻g, 其下冪空間PL(X)是下冪domainH(P)的子空間.