幾乎代數基與有界完備domain

陳 煜, 寇 輝

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

1 預備知識

Domain范疇的cartesian閉性是Domain理論最核心的問題之一[1].為研究函數的可計算性,Hamrin等[2]引入幾乎代數性質,證明了具有可數幾乎代數閉基的domain構成的范疇是cartesian閉的.由于要求定向完備偏序集(簡稱dcpo)的一個可數幾乎代數基滿足閉性條件是相當困難的,因此文獻[2]提出是否可以尋求一個嚴格弱于閉性的條件使得函數空間對于可數幾乎代數及該性質封閉.本文將閉性條件改為弱閉性,證明具有可數幾乎代數弱閉基的domain范疇CAWCB是cartesian閉的,改進Hamrin等[2]的結果.

冪domain的構造源于解釋非確定性程序語言的語義.經典的冪domain包含上冪domain、下冪domain和Plotkin冪domain[3-7],其拓撲表示在文獻[8-9]中也有詳細介紹.文獻[10-12]提出相容冪domain的概念,證明連續domain關于相容下冪domain封閉并給出具體的拓撲表示.本文研究具有(可數)幾乎代數基的dcpo的相容下冪domain,若dcpo具有(可數)幾乎代數基,則其相容下冪domain是一個具有(可數)幾乎代數弱閉基的有界完備domain，表明范疇CAWCB包含充分多有重要意義的對象，因此,弱閉性是閉性條件的合理推廣.

↓A={x∈D:?a∈A,x≤a},
↑A={x∈D:?a∈A,a≤x}.

定義1.2[9]設P是一個dcpo.子集U?P稱為Scott開集,若U=↑U并且對于任意定向集D?U,∨D∈U意味著D∩U≠?.由所有Scott開集構成一個拓撲,稱為Scott拓撲,并記為σ(P).

定義1.3[9]設D、E是2個dcpo.

1) 一個映射f:D→E稱為是Scott連續的,如果f是單調的,并且保持D中任意定向子集的上確界.

2) 函數空間[D→E],表示D到E的所有Scott連續映射在點態序下的集合,其中點態序表示f≤g,當且僅當對任意x∈D,f(x)≤g(x).

容易驗證,一個映射f:D→E是Scott連續當且僅當它關于Scott拓撲是連續的.

2 幾乎代數dcpo的相關性質

幾乎代數性是文獻[2]為研究有界完備domain的可計算性而引入的一種特殊性質.

定義2.1[2]設D=(D,≤,⊥)是一個連續的cpo,D的一個基B稱為是幾乎代數的,如果它具有以下2個性質.

1) (上逼近性質)對于任給a∈B,存在序列(an)n∈N?B使得

a?…?an+1?an?…?a1，

(1)

并且對于任意b,若a?b,則存在n∈N,an?b.以上序列(an)n∈N稱為上逼近序列.

容易看出,所有代數cpo具有幾乎代數性,這也是稱其幾乎代數的原因.存在大量非代數的幾乎代數domain，如文獻[15]所證明,每個完備度量空間的形式閉球domain是幾乎代數的非代數dcpo.

命題2.3每個cpo的幾乎代數基(若存在)是約簡的.

證明由定義2.1,幾乎代數基的每個元有上逼近序列,因此必是約簡的.證畢.

證明任給b是(an)n∈ω的一個下界，斷言b≤a.反證法,假設ba,由連續性,存在c∈BD,c?b,但是ca.對任意的存在n∈ω使得an?x,因此c?b≤an?x,即?由幾乎代數性質得到c≤a矛盾，因此,證畢.

設P是一個dcpo,V?P.稱V是P的一個濾子,若V≠?且?a,b∈V,?c∈V,c≤a,b.此時,若V是一個Scott開集,則稱為開濾子.記P的所有開濾子之集為OF(P)并賦予集包含關系,則OF(P)也是一個dcpo,并稱為P的余素譜對偶.

引理2.5[9]設P是一個dcpo,U?P是一個Scott開集,則V是σ(P)的余素元當且僅當U是一個濾子.

一個預序集(B,)稱為抽象基,若?b∈B,M?finB,bM??b′∈B,bb′M,這里bM表示?m∈M,bm.子集I?B稱為B的round理想,若I是關于的定向下集且?a∈I,?a′∈I,aa′.I的所有round理想之集賦予包含關系,記為RI(B),稱為B的round理想完備.抽象基round理想完備是一個連續dcpo[1].

命題2.6設P是一個dcpo,B?P是一個幾乎代數基，則OF(P)同構于(B,?op)的round理想完備RI(Bop).這里?a,b∈B,a?opb≤?b?a.

證明(B,?)op是一個抽象基，顯然,?op是一個預序.?b∈B,M?finB,若M?opb(即b?M),則存在b的上逼近序列中的元素bn使得b?bn?M,即M?opbn?opb，(B,?)op是一個抽象基.

注意到B是幾乎代數基,容易驗證,?V∈OF(P)及I∈RI(Bop),VIV=V且IVI=I，OF(P)同構于(B,?op)的round理想完備RI(Bop).證畢.

3 幾乎代數弱閉基與有界完備domain

一個dcpoD稱為有界完備domain,若D有最小元且每個非空相容子集有上確界.

定理3.1[2]設D是一個dcpo,B?D是一個基,稱B是閉的,若任給a,b∈B,↑a∩↑b?a∨b∈B,即B關于有上界的有限子集的上確界封閉.

顯然,具有最小元和閉基的dcpo是一個有界完備domain.

文獻[2]考慮具有幾乎代數基的有界完備domain,并得到如下主要定理.

定理3.2[2]具有幾乎代數可數閉基的有界完備domain關于笛卡爾乘積和函數空間封閉,該結構關于Scott連續函數構成cartesian閉范疇.

由于一個可數的幾乎代數基要滿足閉性并不容易,文獻[2]提出是否能減弱閉性到一個合適的條件使得domain的函數空間關于幾乎代數性封閉.本文在有界完備domain上給出弱閉性條件,并證明具有可數幾乎代數弱閉基的有界完備domain是cartesian閉范疇.

命理3.4設P是有最小元的dcpo,則下面2條等價:

1)P是有界完備domain;

2)P有一個弱閉基.

例3.5令I=[0,1],記BI表示區間domain,即

BI={[a,b]:a,b∈I,a≤b},

?[a,b],[c,d]∈BI,
[a,b]≤[c,d]≤?a≤c≤d≤b,

(2)

則BI是一個有界完備連續domain[9].令B={[a,b]:a,b∈[0,1]∩Q,a

接下來考慮具有可數的幾乎代數弱閉基的有界完備domain.記CAWCB表示以所有具有可數的幾乎代數弱閉基的有界完備domain為對象、以Scott連續函數為態射的范疇.

引理3.6[2]已知D、E是連續的cpo,D有一個幾乎代數基BD,E有一個可數基BE,a,c∈BDb,d∈BE,則有:

1) (ab)≤(cd)≤?c≤a&b≤d；

2) (ab)?(cd)≤?c?a&b?d；

3) 若D,E是有界完備domain且f∈[D→E],則

(ab)?f≤?b?f(a).

(3)

命題3.7設D、E是2個有界完備domain,分別有一個幾乎代數可數弱閉基BD、BE,則[D→E]存在一個基B[D→E],定義為

(4)

證明如果存在f∈[D→E]使得(aibi)?f對i=1,2,…,n成立,定義h:D→E如下:h(x)=∨{bi:ai?x,i≤n}.根據引理3.6,如果ai?x,則

bi?f(ai)≤f(x),

因此

h是良定義的.容易驗證h保持定向上確界并且

h=∨{(aibi):i=1,2,…,n}，

(5)

B[D→E]是D→E的一組基.證畢.

定理3.8設D、E是2個有界完備domain,分別有一個幾乎代數可數弱閉基BD、BE,則B[D→E]是函數空間[D→E]的一個可數、幾乎代數、弱閉基.

證明顯然B[D→E]是可數弱閉的,下證其滿足幾乎代數性質.

設I是一個有限集,存在f∈[D→E]使得

{(aibi):ai∈BD,bi∈BE,i∈I}?
f.h=∨{(aibi):ai∈BD,bi∈BE,i∈I}?f.

(ai?j∈ω;

(6)

(7)

對任意i∈I,根據引理3.6,(aibi)?f≤?bi?f(ai),由幾乎代數性質存在ji∈ω使得對任意j≥ji有

又因為I是一個有限集,所以存在j0=max{ji:i∈I}使得任意的j≥j0都有

由上可知:

(8)

(9)

由此可知基B[D→E]滿足定義2.1幾乎代數性質的條件1),即滿足上逼近性質.下證其滿足定義2.1幾乎代數性質條件2),即需要證明:

(10)

其中I為有限集且b≠⊥.因BE是E的幾乎代數基,對任意的i∈I存在關于di的幾乎代數序列

由引理3.6有

(ci

且由上面的證明可知?n0,當n≥n0時有

∨i∈I(ci

根據假設有

(ab)

因此

(11)

即

(ab)≤∨i∈I(cidi).

證畢.

由于具有可數幾乎代數弱閉基的有界完備domain關于有限笛卡爾乘積是封閉的,結合上述定理有下面的結論.

推論3.9CAWCB是cartesian閉范疇.

4 相容下冪domain與幾乎代數基

文獻[10]引入相容下冪domain的概念,證明連續dcpo的相容下冪domain存在并給出其拓撲表示.下面將證明,若dcpo有最小元且具有一個可數的幾乎代數基,則其相容下冪domain是具有可數的幾乎代數弱閉基的有界完備domain.

定義4.1[10]設P是一個dcpo.

1) 子集A?P稱為相容的,若A在P中有上界,即存在b∈P使得A?↓b.

2) 一個部分二元運算+↑:P×P→P稱為相容算子,若對任意a,b∈P,a+↑b有定義當且僅當a,b相容,即↑a∩↑b≠?.

3) 若P具有一個Scott連續的交換、冪等及結合的相容算子,則稱為dcpo相容半格.特別地,若該運算是相容并(交),則稱P為dcpo相容并(交)半格.

dcpoP上的相容下冪domain即是由P生成的自由dcpo相容并交半格.

定義4.2[10]設P是一個連續dcpo.子集A?P稱為相關相容閉集若A是非空Scott閉集且存在由非空有限相容子集組成的集族F使得:

1) ?F1,F2∈F,?F∈F,F1∪F2?↓F;

記Hc(P)為P的所有相關相容閉集所組成的集合,并賦予集包含關系.

定理4.3[10]設P是連續dcpo,則Hc(P)同構于P的相容下冪domain且滿足：

1)Hc(P)是連續的dcpo相容并半格；

設P是一個dcpo,B?P是一個基.記

(12)

則由上述定理知,FC(B)是相容下冪domainHc(P)的一個基.若B是可數的,則FC(B)也是可數的.

定理4.4設P是一個有最小元⊥的dcpo,B?P是一個可數的幾乎代數基.則相容下冪domainHc(P)是一個具有可數幾乎代數弱閉基的有界完備domain.

證明顯然,{⊥}是Hc(P)的最小元.由定理4.3,Hc(P)是連續的相容并半格,故Hc(P)是一個有界完備domain.設B是P的一個可數的幾乎代數基，則FC(B)是Hc(P)的一個可數基.下證FC(B)是幾乎代數的.

任給↓F∈FC(B).記F={a1,b2,…,bnF}.由B是P的幾乎代數基,對每個1≤n≤nF,存在bn的上逼近序列

mA=Max{mn:1≤n≤nF},

上述結果表明,具有可數幾乎代數弱閉基的有界完備domain范疇包含充分多由重要意義的結構.因此,就該范疇而言,弱閉性是對閉性的合理推廣.

最后,注意到幾乎代數閉基必是弱閉的,具有可數幾乎代數弱閉基的有界完備domain是否有一個可數幾乎代數閉基？

[1] ABRAMSKY S, JUNG A. Domain Theory, Handbook of Logic in Computer Science[M]. Oxford:Clarendon Press,1994:1-168.

[2] HAMRIN G, STOLTENBERG-HANSEN V. Two categories of effective continuous cpos[J]. Theoretical Computer Science,2006,365(3):216-236.

[3] HECKMANN R. Power domain constructions[J]. Sci Computer Programming,1991,17(1/2/3):77-117.

[4] PLOTKIN G D. Apowerdomain construction[J]. SIAM J Computing,1976,5(3):452-487.

[5] SMYTH M. Power domains and predicate transformers:a topological view[J]. Automata, Languages and Programming,1983:662-675.

[6] JONES C, PLOTKIN G. A probabilistic powerdomain of evaluations[C]//Logic in Computer Science, Fourth Symposium on IEEE,1989:186-195.

[7] TIX R, KEIMEL K, PLOTKIN G. Semantic domains for combining probability and non-determinism[J]. Electronic Notesin Theoretical Computer Science,2009,222:3-99.

[8] GIERZ G, HOFMANN K H, KEIMEL K, et al. A Compendium of Continuous Lattices[M]. Berlin:Springer-Verlag,1980.

[9] GIERZ G, HOFMANN K H, KEIMEL K, et al. Continuous Lattices and Domains[M]. Cambridge:Cambridge University Press,2003.

[10] YUAN Y, KOU H. Consistent hoare powerdomains[J]. Topology and Its Applications,2014,178:40-45.

[11] YUAN Y, KOU H. Consistent Smyth powerdomains[J]. Topology and Its Applications,2014,173:264-275.

[12] YUAN Y, KOU H. Consistent Plotkin powerdomains[J]. Topology and Its Applications,2014,178:339-344.

[13] JUNG A. Cartesian Closed Categories of Domains[M]. Amsterdam:Centrum Voor Wiskunde Eninformatica,1989.

[14] MACLANE S. Categories for the Working Mathematician[M]. New York:Springer-Verlag,2013.

[15] 呂振超,寇輝. C-雙有限domain與SM性質[J]. 四川大學學報(自然科學版),2015,52(1):16-20.