幾乎代數(shù)基與有界完備domain

陳 煜, 寇 輝

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

1 預備知識

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

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

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

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

定義1.3[9]設(shè)D、E是2個dcpo.

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

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

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

2 幾乎代數(shù)dcpo的相關(guān)性質(zhì)

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

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

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

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

(1)

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

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

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

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

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

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

引理2.5[9]設(shè)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是關(guān)于的定向下集且?a∈I,?a′∈I,aa′.I的所有round理想之集賦予包含關(guān)系,記為RI(B),稱為B的round理想完備.抽象基round理想完備是一個連續(xù)dcpo[1].

命題2.6設(shè)P是一個dcpo,B?P是一個幾乎代數(shù)基，則OF(P)同構(gòu)于(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是幾乎代數(shù)基,容易驗證,?V∈OF(P)及I∈RI(Bop),VIV=V且IVI=I，OF(P)同構(gòu)于(B,?op)的round理想完備RI(Bop).證畢.

3 幾乎代數(shù)弱閉基與有界完備domain

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

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

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

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

定理3.2[2]具有幾乎代數(shù)可數(shù)閉基的有界完備domain關(guān)于笛卡爾乘積和函數(shù)空間封閉,該結(jié)構(gòu)關(guān)于Scott連續(xù)函數(shù)構(gòu)成cartesian閉范疇.

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

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

1)P是有界完備domain;

2)P有一個弱閉基.

例3.5令I(lǐng)=[0,1],記BI表示區(qū)間domain,即

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

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

(2)

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

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

引理3.6[2]已知D、E是連續(xù)的cpo,D有一個幾乎代數(shù)基BD,E有一個可數(shù)基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設(shè)D、E是2個有界完備domain,分別有一個幾乎代數(shù)可數(shù)弱閉基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}.根據(jù)引理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設(shè)D、E是2個有界完備domain,分別有一個幾乎代數(shù)可數(shù)弱閉基BD、BE,則B[D→E]是函數(shù)空間[D→E]的一個可數(shù)、幾乎代數(shù)、弱閉基.

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

設(shè)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,根據(jù)引理3.6,(aibi)?f≤?bi?f(ai),由幾乎代數(shù)性質(zhì)存在ji∈ω使得對任意j≥ji有

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

由上可知:

(8)

(9)

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

(10)

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

由引理3.6有

(ci

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

∨i∈I(ci

根據(jù)假設(shè)有

(ab)

因此

(11)

即

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

證畢.

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

推論3.9CAWCB是cartesian閉范疇.

4 相容下冪domain與幾乎代數(shù)基

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

定義4.1[10]設(shè)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連續(xù)的交換、冪等及結(jié)合的相容算子,則稱為dcpo相容半格.特別地,若該運算是相容并(交),則稱P為dcpo相容并(交)半格.

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

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

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

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

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

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

設(shè)P是一個dcpo,B?P是一個基.記

(12)

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

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

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

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

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

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

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

[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性質(zhì)[J]. 四川大學學報(自然科學版),2015,52(1):16-20.