可數(shù)一致連續(xù)偏序集的序同態(tài)與擴張

劉東明, 姜廣浩, 李 輝

(淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 安徽 淮北 235000)

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

1 預(yù)備知識

設(shè)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]設(shè)P是偏序集,S?P,若?x,y∈S,存在z∈P使得x≤z,y≤z,則稱S為P的一致集.若對于任意一致集S都有上確界supS,則稱偏序集P是一致完備的,簡記為UCPO.

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

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

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

2)x=supcux,

則稱P為可數(shù)一致連續(xù)偏序集.

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

1) supB=x；

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

2 可數(shù)一致連續(xù)偏序集的序同態(tài)

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

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

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

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

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

定理2.1設(shè)f:P→Q,P為可數(shù)一致連續(xù)偏序集,則下列結(jié)論等價：

1)f為序同態(tài)；

2)f?？蓴?shù)一致并且保可數(shù)一致way below；

3)f?？蓴?shù)一致極小集.

證明1)?2) 若f為序同態(tài),則顯然f為?？蓴?shù)一致并的,下證f?？蓴?shù)一致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上的可數(shù)一致集,從而存在s∈S,使得x≤f-1(s),進而f(x)≤s,即f(x)?cuf(y),所以f為?？蓴?shù)一致way below的,故結(jié)論成立.

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

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

supf-1(U),

即supf-1(U)=f-1(supU).故f-1為?？蓴?shù)一致并映射,所以f為序同態(tài).

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

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

且

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

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

3)?2) 一方面,?x,y∈P且x?cuy,則cuy為y的可數(shù)一致極小集,因f?？蓴?shù)一致極小集,從而f(cuy)為f(y)的可數(shù)一致極小集且f(cuy)?cuf(y),易知f(x)?cuf(y),故f?？蓴?shù)一致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)的可數(shù)一致極小集,從而可以得到

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

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

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

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

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

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

1)U=↑U;

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

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

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

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

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

1) ?x∈P,cux是可數(shù)一致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可數(shù)一致Scott閉集?B為下集且B關(guān)于可數(shù)一致并封閉.

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

2) 設(shè)U∈σcu(P)且x∈U,因為P為可數(shù)一致連續(xù)偏序集,故cux為可數(shù)一致集且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為可數(shù)一致Scott開集.一方面,int(U)?S,事實上,設(shè)x∈US,則?y∈cux,有y?U,否則若y∈U有x∈cuy?S,這與假設(shè)矛盾,從而x?int(U),進而int(U)?S；另一方面,?x∈U,有cux?U,因為cux為可數(shù)一致Scott開集,進而cux=intcux?int(U),故S=∪{cu(x):x∈U}?int(U),綜合可知,結(jié)論成立.

4) ?x∈P,一方面,因為可數(shù)一致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為可數(shù)一致連續(xù)偏序集,故x=supcu(x)≤y,從而y∈↑x,故∩{U:U∈σcu(P),x∈U}?↑(x),綜合可知,結(jié)論成立.

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

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

定理2.3設(shè)P、Q為可數(shù)一致完備偏序集,f:P→Q為?？蓴?shù)一致并映射?f為可數(shù)一致Scott連續(xù)映射.

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

必要性 首先,若f為可數(shù)一致Scott連續(xù)映射,則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)成立,假設(shè)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*,由可數(shù)一致Scott的定義知D∩V*≠?,即存在d∈D∩V*,從而f(d)∈U*,進而有f(d)supf(D),矛盾；故f(supD)=supf(D),結(jié)論成立.

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

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

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

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

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

故supP(S)∈B且supB(S)=supP(S),所以B對于可數(shù)一致并封閉；再者,?x∈B,一方面,易知x為cux的一個上界,從而supcuB(x)≤x；另一方面,若?y∈P且y?cuPx,則對于任意B中的可數(shù)一致集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設(shè)P為可數(shù)一致連續(xù)偏序集,p:P→P?？蓴?shù)一致并(可數(shù)一致Scott連續(xù)映射),則下列結(jié)論成立：

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

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

3 可數(shù)一致序同態(tài)的擴張

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

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

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

定理3.1設(shè)P為CUCPO,則下列結(jié)論成立:

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

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

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

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

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

證明1) 必要性 顯然的.

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

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

x=supDx=sup(B∩Dx)≤

sup(B∩cux)≤x,

所以sup(B∩cux)=x.

充分性 顯然的.

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

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

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

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

下面給出幾個可數(shù)一致連續(xù)偏序集序同態(tài)一些擴張定理.

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

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

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

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

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

再者,證明f為序同態(tài)；一方面,f保序,事實上,?x,y∈P且x≤y,則cux∩B?cuy∩B,根據(jù)f的構(gòu)造得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保可數(shù)一致并；另一方面,?x,y∈P且x?cuy,由可數(shù)一致基的性質(zhì)有,存在u,v∈B使得x?cuu?cuv?cuy,因f保序且g為序同態(tài),從而有

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

根據(jù)f的構(gòu)造得g(v)≤f(y),即有f(x)?cuf(y),故f?？蓴?shù)一致way below；由定理2.1,綜合可知f為序同態(tài).

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

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

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

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

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

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

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

證明結(jié)合定理2.1、定理3.1和定理3.2可以證明.

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

證明結(jié)合定理2.1、定理3.1和定理3.2也可以證明.

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

證明結(jié)合定理2.3、定理3.1和定理3.2可以證明.

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