可数一致连续偏序集的序同态与扩张

刘东明, 姜广浩, 李 辉

(淮北师范大学 数学科学学院, 安徽 淮北 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)对本文给予了资助，谨致谢意.