可數一致連續偏序集的序同態與擴張

劉東明, 姜廣浩, 李 輝

(淮北師范大學 數學科學學院, 安徽 淮北 235000)

連續Domain理論[1-2]創立的初衷是為了解決一些計算機程序語言邏輯的問題.經多年發展,現如今的連續Domain理論顯然已經成為一個重要的數學分支,由于它具有比較深的計算機科學背景,所以連續Domain理論的各項研究一直備受中外學者們的關注.對連續Domain理論的研究思路之一是將其進行推廣,文獻[3]給出了可數連續偏序集的概念,并建立了完善的可數連續Domain理論；文獻[4]首次引入了相容定向集的概念,為相容連續Domain理論構建奠定基礎；文獻[5]則提出了一致連偏序集的概念;文獻[6]給出了可數一致連續偏序集和可數一致極小集的概念.本文沿此思路,首先在可數一致連續偏序集上引入序同態的概念,給出序同態的若干等價刻畫；然后引入可數一致Scott拓撲的概念,研究其具有的一些基本性質,并證明可數一致連續偏序集在保可數一致并投射下的像自身仍為可數一致連續偏序集；再者引入可數一致基與可數一致稠密集的概念,探討其基本性質;最后證明它們的序同態可以唯一擴張為整個可數一致連續偏序集的序同態.

1 預備知識

設P為偏序集,D?P,D≠?,?x,y∈D,?z∈D使得x,y≤z,則稱D是P的定向子集；若對于任意定向子集D都有上確界supD,則稱偏序集P是定向完備的.簡記為DCPO.

記↓X={y∈P:?x∈X,y≤x},↑X={y∈P:?x∈X,y≤x},↓x=↓{x},↑x=↑{x}.

定義1.1[5]設P是偏序集,S?P,若?x,y∈S,存在z∈P使得x≤z,y≤z,則稱S為P的一致集.若對于任意一致集S都有上確界supS,則稱偏序集P是一致完備的,簡記為UCPO.

定義1.2[6]設P為偏序集,S?P,若對于任意可數集C?S,存在p∈P使得?c∈C,有c≤p,則稱S為P上的可數一致集.若對于P中的任意可數一致集S都有上確界supS,則稱P為可數一致完備集,簡稱為CUCPO.記P上的全體可數一致集為Ucu(P),記Icu(P)={↓S:S為P上的可數一致集}.

定義1.3[6]設P為CUCPO,定義P上的way below?cu關系:?x,y∈P,?S∈Uc(P),supS存在,當y≤supS時,?s∈S,使得x≤s,則稱x可數一致小于y,記為x?cuy.當x?cux時,稱x為可數一致緊元,P上的全體可數一致緊元記為Kcu(P).記cux={y:x?cuy},cux={y∈P:y?cux}.

定義1.4[6]設P為CUCPO,若?x∈P,滿足下列條件：

2)x=supcux,

則稱P為可數一致連續偏序集.

定義1.5[6]設P為CUCPO,x∈P,B∈Ucu(P),B稱為x的一個可數一致極小集,如果B滿足:

1) supB=x；

2) 若C∈Ucu(P)且x≤supC時,?y∈B,存在z∈C,使得y≤z.

2 可數一致連續偏序集的序同態

定義2.1設P、Q是可數一致完備偏序集,f:P→Q是保序映射,如果對于任意可數一致集S?P,f(supS)=supf(S),則稱f是保可數一致并的.

定義2.2設P、Q是可數一致完備偏序集,f:P→Q是保序映射,如果?x,y∈P,x?cuy,有f(x)?cuf(y),則稱f是保可數一致way below的.

定義2.3設P、Q是可數一致完備偏序集,映射f:P→Q稱為序同態的,如果f和f-1都是是保可數一致并的,其中,f-1:Q→P為f的逆映射,它的定義為

f-1(y)=sup{↓x?P:f(↓x)?↓y}.

定義2.4設P、Q是可數一致完備偏序集,映射f:P→Q稱為保可數一致極小集的,若?A?P,A為a可數一致極小集,則f(A)為f(a)可數一致極小集.

定理2.1設f:P→Q,P為可數一致連續偏序集,則下列結論等價：

1)f為序同態；

2)f保可數一致并且保可數一致way below；

3)f保可數一致極小集.

證明1)?2) 若f為序同態,則顯然f為保可數一致并的,下證f保可數一致way below,?x,y∈P,若x?cuy,?S∈Ucu(Q),當f(y)≤supS時,有y≤f-1(supS)=supf-1(S),又因為f-1保序,故f-1(S)為P上的可數一致集,從而存在s∈S,使得x≤f-1(s),進而f(x)≤s,即f(x)?cuf(y),所以f為保可數一致way below的,故結論成立.

2)?1) 若條件成立,則f為保可數一致并映射,下證f-1也為保可數一致并的.?U∈Ucu(Q),一方面,f-1保序,從而有f-1(supU)為f-1(U)的一個上界,即supf-1(U)≤f-1(supU).另一方面,設x?cuf-1(supU),因為f是保可數一致way below的,從而有f(x)?cuf(f-1(supU))≤supU,進而存在u∈U,使得f(x)≤u,即有x≤f-1(u)≤supf-1(U),又因為P為可數一致連續偏序集,故得

f-1(supU)=sup{x:x?cuf-1(supU)}≤

supf-1(U),

即supf-1(U)=f-1(supU).故f-1為保可數一致并映射,所以f為序同態.

2)?3) ?x∈P,S∈Ucu(P),設S為a的可數一致極小集,則有S?cux且supS=x,根據2)知,f保可數一致并且保可數一致way below,故得

f(S)?f(cux)?cuf(x),

且

f(supS)=supf(S)=f(x),

由可數一致極小集定義易知,f(S)為f(x)的可數一致極小集.

3)?2) 一方面,?x,y∈P且x?cuy,則cuy為y的可數一致極小集,因f保可數一致極小集,從而f(cuy)為f(y)的可數一致極小集且f(cuy)?cuf(y),易知f(x)?cuf(y),故f保可數一致way below；另一方面,?S∈Ucu(P),因f保序,從而有supf(S)≤f(supS).下證f(supS)≤supf(S),?x?cusupS,則存在s∈S使得x≤s,從而f(x)≤f(s)≤supf(S).由前面證明可知f(cusupS)為f(supS)的可數一致極小集,從而可以得到

f(supS)=supf(cusupS)≤supf(S),

即supf(S)=f(supS),故f保可數一致并,綜合可知,結論成立.

命題2.1設P、Q都為可數一致完備偏序集,若f:P→Q是保可數一致way below的,則下列結論成立：

1) ?x∈P,有f(cux)?cuf(x)；

2) ?x∈P,有f(cux)?cuf(x).

定義2.5設P為可數一致完備偏序集,U?P,若U滿足:

1)U=↑U;

2) 對于任意可數一致集S,supS∈U蘊含著S∩U≠?,

則稱U為P上的可數一致Scott開集,PU則稱為P上的可數一致Scott閉集.

記P上的全體可數一致Scott開集為σcu(P),可數一致Scott拓撲空間(P,σcu(P))記為Σcu(P).

引理2.1[6]設P為可數一致連續偏序集,?x,y∈P,若x?cuy,則存在z∈P使得x?cuz?cuy,即可數一致連續偏序集的插值性成立.

定理2.2設P為可數一致連續偏序集,Σcu(P)為P的可數一致Scott拓撲則：

1) ?x∈P,cux是可數一致Scott開集；

3)U?P為上集?int(U)={y∈U:?x∈U,x?cuy}=∪{cu(x):x∈U}；

4) ?x∈P,↑(x)=∩{U:U∈Σcu(P),x∈U}；

5)B?P,B可數一致Scott閉集?B為下集且B關于可數一致并封閉.

證明1) ?S∈Ucu(P),若supS∈cux,則x?cusupS,由插值性可得,存在y∈P使得x?cuy?cusupS,從而存在s∈S使得y≤s且x?cus,進而有S∩cux≠?,故cux是可數一致Scott開集.

2) 設U∈σcu(P)且x∈U,因為P為可數一致連續偏序集,故cux為可數一致集且x=supcux∈U,從而存在y∈cux∩U,又因U是上集,故可得到x∈cuy?↑y?U,所以{cux:x∈P}是拓撲空間Σcu(P)的一個基.

3) 令S=∪{cu(x):x∈U}={y∈U:?x∈U,x?cuy},則S為可數一致Scott開集.一方面,int(U)?S,事實上,設x∈US,則?y∈cux,有y?U,否則若y∈U有x∈cuy?S,這與假設矛盾,從而x?int(U),進而int(U)?S；另一方面,?x∈U,有cux?U,因為cux為可數一致Scott開集,進而cux=intcux?int(U),故S=∪{cu(x):x∈U}?int(U),綜合可知,結論成立.

4) ?x∈P,一方面,因為可數一致Scott開集都為上集,故可以得到↑(x)?∩{U:U∈σcu(P),x∈U}.另一方面,?y∈∩{U:U∈σcu(P),x∈U},若z∈cux,則x∈cuz∈σcu(P),從而y∈cuz,進而有z≤y,因P為可數一致連續偏序集,故x=supcu(x)≤y,從而y∈↑x,故∩{U:U∈σcu(P),x∈U}?↑(x),綜合可知,結論成立.

5) 必要性 設B為可數一致Scott閉集,則存在UB∈σcu(P)使得B=PUB,從而B為下集,?S?B且S為可數一致集,則supS∈B.事實上,若supS?B,則有supS∈PB=UB,從而?=S∩(PB)≠?,矛盾,故結論成立.

充分性B?P,首先,若B為下集,則PB為上集；再者,若B關于可數一致并封閉,則對于任意可數一致集S,若supS∈PB,則有S∩(PB)≠?,從而PB為可數一致Scott開集,故B為可數一致Scott閉集,結論成立.

定理2.3設P、Q為可數一致完備偏序集,f:P→Q為保可數一致并映射?f為可數一致Scott連續映射.

證明充分性 設?A?Q且A為可數一致Scott閉集,下證f-1(A)為P中的可數一致Scott閉集,?D?f-1(A)且D∈Ucu(P),因f保可數一致并,則有f(supD)=supf(D)且f(D)∈Ucu(Q).又A為可數一致Scott閉集,從而supf(D)∈A,進而f(supD)∈A,所以supD∈f-1(A).又易知f-1(A)為下集,由定理2.2得f-1(A)為P中的可數一致Scott閉集,故結論成立.

必要性 首先,若f為可數一致Scott連續映射,則f保序.事實上,?x,y∈P且x≤y,若f(x)f(y),令V=Q↓f(y),則V∈σcu(Q)且f(x)∈V,從而存在U=f-1(V)∈σcu(P)且x∈U,y?U,這與U為上集相矛盾,故f保序；再者,?D∈Ucu(P),因f保序,故有supf(D)≤f(supD)；下證f(supD)≤supf(D)成立,假設f(supD)supf(D),可令U*=Q↓supf(D),則U*∈σcu(Q)且f(supD)∈U*,從而存在

V*=f-1(U*)=f-1(Q↓supf(D))∈σcu(P)

且supD∈V*,由可數一致Scott的定義知D∩V*≠?,即存在d∈D∩V*,從而f(d)∈U*,進而有f(d)supf(D),矛盾；故f(supD)=supf(D),結論成立.

定義2.6[2]設P為偏序集,p:P→P稱為投射,若p是保序的且是冪等的.

定理2.4設P為可數一致連續偏序集,p:P→P是保可數一致并的冪等映射,則p(P)作為P的子偏序集是可數一致連續偏序集.即可數連續偏序集的保可數一致并的投射像自身也是可數一致連續偏序集.

證明令B=p(P)?P,則有B={x:x∈P,p(x)=x}.首先,?S?B且S∈Ucu(P),因P為可數一致連續偏序集,易知supP(S)存在,又p保一致可數并,進而有

p(supP(S))=supP(p(S))=

supP{s:s∈S}=supP(S),

故supP(S)∈B且supB(S)=supP(S),所以B對于可數一致并封閉；再者,?x∈B,一方面,易知x為cux的一個上界,從而supcuB(x)≤x；另一方面,若?y∈P且y?cuPx,則對于任意B中的可數一致集S,當x≤supB(S)=supP(S)時,則存在s∈S使得y≤s,從而p(y)≤p(s)=s,進而在B中有p(y)?cuBx成立,所以有

x=p(x)=p{supP{y∈P:y?cuPx}}=

supP{p(y):y?cuPx}=supB{p(y):y?cuPx}≤

supB{u∈B:u?cuBx}=supcuBx.

由上述2個定理可得到下列推論.

推論2.1設P為可數一致連續偏序集,p:P→P保可數一致并(可數一致Scott連續映射),則下列結論成立：

1)p為閉包算子?p(P)作為P的子偏序集是可數一致連續偏序集；

2)p為內部算子?p(P)作為P的子偏序集是可數一致連續偏序集.

3 可數一致序同態的擴張

定義3.1設P為CUCPO,D?P,若?x,y∈P,x?cuy,存在u∈D使得x?cuu?cuy,稱D在P中是可數一致稠密的(?cu稠密).

注3.1若P為CUCPO,P本身就是?cu稠密.

定義3.2設P為CUCPO,?B?P,若?x∈P,存在Bx?B使得Bx∈Ucu(P),Bx?cux且supBx=x,則稱B為P的一個可數一致基.

定理3.1設P為CUCPO,則下列結論成立:

1)P為可數一致連續偏序集?P有可數一致基；

2)B?P為P的可數一致基??x∈P,B∩cux∈Ucu(P)且sup(B∩cux)=x；

3)P為可數一致連續偏序集,B?P為可數一致基??x,y∈P,x?cuy?存在b∈B使得x?cub?cuy；

4)P為可數一致連續偏序集,B?P為可數一致基?B在P中是可數一致稠密的；

5)P為可數一致連續偏序集,B?P為可數一致基?Kcu(P)?B.

證明1) 必要性 顯然的.

充分性 設B為P的基,?x∈P易知x為cux的一個上界,即supcux≤x；下證x≤supcux.事實上,若xsupcux,由可數一致基的定義得,存在Bx?B使得Bx∈Ucu(P),Bx?cux且supBx=x,從而supBxsupcux,矛盾；從而x=supcux,又易知cux∈Ucu(P),結論成立.

2) 必要性 設B為P上的一個可數一致基,則?x∈P,B∩cux∈Ucu(P),由可數一致基的定義得,?Dx?B使得Dx?cux且supDx=x,由于Dx?cux,故

x=supDx=sup(B∩Dx)≤

sup(B∩cux)≤x,

所以sup(B∩cux)=x.

充分性 顯然的.

3) 必要性 由可數一致基的定義和插入性可以證得.

充分性 設B?P,?x∈T,令Bx=B∩cux,則Bx∈Ucu(P).下證supBx=x.易知x為Bx的上界,即supBx≤x；若xsupBx,因為P為可數一致連續偏序集,故存在x*∈cux有x*supBx且x*≤x,再由條件知存在b∈B使得x*?cub?cux,進而b∈Bx,bsupBx,矛盾,所以x≤supBx,故supBx=x,B為P的一個可數一致基,結論成立.

4) 可以由可數一致稠密集及3)簡單證得.

5) 設P為可數一致連續偏序集且B?P為可數一致基,?x∈Kcu(P),則有x?cux?cux,由3)可知x∈B,故Kcu(P)?B.

下面給出幾個可數一致連續偏序集序同態一些擴張定理.

定理3.2設P、Q為可數一致連續偏序集,B?P為P上的可數一致基,若g:B→Q為序同態,則g可以擴張成一個序同態f:P→Q且擴張唯一.

證明構造f(x)=supg(cux∩B)(?x∈P).

首先,證明f|B=g；?x∈B,由g為序同態和可數一致基的定義得

f(x)=supg(cux∩B)=

g(sup(cux∩B))=g(x).

再者,證明f為序同態；一方面,f保序,事實上,?x,y∈P且x≤y,則cux∩B?cuy∩B,根據f的構造得f(x)≤f(y),即f保序；?D∈Ucu(P),由于f保序,易知supf(D)≤f(supD).下證

f(supD)≤supf(D), ?x∈cu(supD)∩B,

則x?cusupD,從而存在d∈D使得x≤d,故可以得到

g(x)=f(x)≤f(d)≤supf(D),

進而f(supD)≤supf(D),即f(supD)=supf(D),所以f保可數一致并；另一方面,?x,y∈P且x?cuy,由可數一致基的性質有,存在u,v∈B使得x?cuu?cuv?cuy,因f保序且g為序同態,從而有

f(x)?cuf(u)=g(u)?cug(v).

根據f的構造得g(v)≤f(y),即有f(x)?cuf(y),故f保可數一致way below；由定理2.1,綜合可知f為序同態.

最后,證明f唯一.設存在另外一個序同態的擴張h:P→Q,?x∈P有

h(x)=h(sup(cux∩B))=

suph(cux∩B)=supg(cux∩B)=f(x).

這個定理可以推廣,見下面命題.

命題3.1設P、Q為可數一致連續偏序集,D?P在P上為可數一致稠密的,若g:D→Q為序同態,則g可以擴張成一個序同態f:P→Q且擴張唯一.

證明由定理3.1知,D?P在P上為可數一致稠密則D為P的一個可數一致基,再由定理3.2得,結論成立.

命題3.2設P、Q為可數一致連續偏序集,B?P是P上的可數一致基(可數一致稠密的),若g:B→Q保可數一致并且保可數一致way below,則g可以擴張成一個保可數一致并且保可數一致way below的f:P→Q且擴張唯一.

證明結合定理2.1、定理3.1和定理3.2可以證明.

命題3.3設P、Q為可數一致連續偏序集,B?P是P上的可數一致基(可數一致稠密的),若g:B→Q為保可數一致極小集的,則g可以擴張成一個保可數一致極小集的f:P→Q且擴張唯一.

證明結合定理2.1、定理3.1和定理3.2也可以證明.

命題3.4設P、Q為可數一致連續偏序集,B?P是P上的可數一致基(可數一致稠密的),若g:B→Q為保可數一致way below的可數一致Scott連續映射,則g可以擴張成為一個保可數一致way below的可數一致Scott連續映射f:P→Q且擴張唯一.

證明結合定理2.3、定理3.1和定理3.2可以證明.

致謝淮北師范大學研究生創新基金(2017YJSCX07)和淮北師范大學研究生教育教學研究項目(2017JYXM03)對本文給予了資助，謹致謝意.