W-代數(shù)偏序集及其性質(zhì)

折海芳, 趙 彬

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 陜西 西安 710119)

?

W-代數(shù)偏序集及其性質(zhì)

折海芳, 趙 彬*

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 陜西 西安 710119)

引入了W-引代數(shù)偏序集與強(qiáng)W-代數(shù)偏序集的概念。討論了W-代數(shù)偏序集、Exact偏序集以及代數(shù)偏序集的關(guān)系，證明了W-代數(shù)偏序集在保定向并的單的核算子下的像是W-代數(shù)偏序集。最后得到了每一點(diǎn)有最小局部基的弱Domain是強(qiáng)W-代數(shù)Domain,證明了弱Domain上的Scott連續(xù)映射保局部基當(dāng)且僅當(dāng)它保Weakly way below關(guān)系。

W-代數(shù)偏序集； 代數(shù)偏序集；Exact偏序集； 弱Domain； 局部基

從20世紀(jì)70年代初Scott的開創(chuàng)性工作以來(lái),Domain理論因具有理論計(jì)算機(jī)科學(xué)和數(shù)學(xué)的雙重背景而一直受到諸多學(xué)者的關(guān)注。對(duì)Domain的推廣是Domain理論研究的一個(gè)重要內(nèi)容。迄今為止,較為成功的推廣是擬連續(xù)Domain[1]和Z-連續(xù)偏序集[2]。作為Domain的另一推廣,2007年Mashburn在文獻(xiàn)[3]中引入了Weakly way below關(guān)系、Exact偏序集和弱Domain的概念,并討論了它們的一些基本性質(zhì)。文獻(xiàn)[4]研究了Exact偏序集的乘積和映射性質(zhì),并且討論了Exact偏序集的基。文獻(xiàn)[5]討論連續(xù)定向完備偏序集(Dcpo)的特征時(shí)引入了局部基的概念,并討論了由此涉入的一些關(guān)系定理。本文在Exact偏序集的基礎(chǔ)上應(yīng)用Weakly way below關(guān)系推廣了代數(shù)偏序集,給出了W-代數(shù)偏序集的概念,并討論了W-代數(shù)偏序集與Exact偏序集以及W-代數(shù)偏序集與代數(shù)偏序集的關(guān)系。最后文章討論了弱Domain的局部基的相關(guān)性質(zhì)。

1 預(yù)備知識(shí)

定義1[6]設(shè)L是偏序集，A?L。若?x∈A,y∈L,y≤x時(shí)有y∈A，則稱A是下集。若?x∈A,y∈L,y≥x時(shí)有y∈A,則稱A是上集。

定義2[6]設(shè)L是偏序集，D?L。若D≠?且?x、y∈D,?z∈D，使得x、y≤z，則稱D是定向子集。若L中任一定向子集的上確界存在，則稱L為Dcpo。

定義3[7]設(shè)L是偏序集，x、y∈L。若對(duì)L中任意定向集D,∨D存在且y≤∨D時(shí)?d∈D,使得x≤d,則稱xWay belowy，記為x?y。記x={u∈L|u?x},x={u∈L|x?u}。

定義4[7]設(shè)L是偏序集,k∈L。若k?k，則稱k為緊元。記L中全體緊元之集為K(L)。

定義5[7]設(shè)L是偏序集。若?x∈L,x是定向集且x=∨x，則稱L是連續(xù)偏序集。

命題1[7]設(shè)L是連續(xù)偏序集，x、z∈L。若x?z,則?y∈L，使得x?y?z，即?滿足插入性質(zhì)。

定義6[7]設(shè)L是偏序集。若?x∈L,↓x∩K(L)是定向集且x=∨(↓x∩K(L)),則稱L是代數(shù)偏序集。

定義7[3]設(shè)L是偏序集，x、y∈L。若對(duì)L中任意定向集D,∨D存在且y=∨D時(shí)?d∈D，使得x≤d，則稱xWeakly way belowy，記為x?wy。記wx={u∈L|u?wx},wx={u∈L|x?wu}。

命題2[3]設(shè)L是偏序集，x、y、z∈L,則有:

(1)x?y?x?wy;

(2)x?wy?x≤y;

(3)x≤y?wz?x?wz。

注1由上述命題知，wx為下集，但wx一般不是上集(見例2)。

定義8[3]設(shè)L是偏序集。若?x∈L,wx是定向集,且∨wx=x,則稱L為Exact偏序集。若L還是Dcpo，則稱L為Exact Domain。

命題3設(shè)L是偏序集，x、y∈L,則x=∨wx當(dāng)且僅當(dāng)xy時(shí)?u∈L，使得u?wx且uy。

命題4[8]每個(gè)連續(xù)偏序集都是Exact偏序集。

注2每個(gè)代數(shù)偏序集都是Exact偏序集。

定義9[3]設(shè)L是偏序集，R是L上的二元關(guān)系，?x、y、z∈L。若xRy≤z,?d∈L，使得zRd時(shí)有xRz，則稱關(guān)系R是Weakly increasing的。

定義10[3]設(shè)L是偏序集。若L是Exact Domain，且?w是Weakly increasing的，則稱L是弱Domain。

命題5每個(gè)Domain都是弱Domain。

命題6[3]設(shè)L是弱Domain，則?w具有插入性質(zhì)。

定義11[6]設(shè)L是偏序集，p:L→L是映射。若?x、y∈L，有

(1)x≤y?p(x)≤p(y);

(2)p(x)=p(p(x))。

則稱p是投射算子。

若p還滿足

(3)p(x)≤x(x≤p(x))。

則稱p是核(閉包)算子。

定義12[7]設(shè)L是偏序集,f:L→L是保序映射。若?D∈D(L)，且∨D存在，有f(∨D)=∨f(D),則稱f是Scott連續(xù)映射。

在本文中，D(L)表示L上的所有定向子集。所用而未標(biāo)注的概念和符號(hào)請(qǐng)參考文獻(xiàn)[2-3]。

2 W-代數(shù)偏序集

定義13設(shè)L是偏序集，k∈L。若k?wk，即?D∈D(L)，∨D存在且k=∨D時(shí)?d∈D，使得x≤d，則稱k為弱緊元。記L中全體弱緊元之集為Kw(L)。

由命題2知，緊元一定是弱緊元，但反之不成立。

圖1 L上的序關(guān)系≤Fig.1 Order relation ≤ of L

可以驗(yàn)證x是弱緊元但不是緊元。

命題7設(shè)L是偏序集,若?x∈L,wx是上集，則K(L)=Kw(L)。

證明顯然有K(L)?Kw(L)。反之，?x∈Kw(L)，有x?wx。下證x?x。?D∈D(L),x≤∨D。由wx是上集知,x?w∨D。則?d∈D,使得x≤d。故x?x,即x∈K(L)。從而，K(L)=Kw(L)。

定義14設(shè)L是完備格。若L滿足：

則稱L是W-穩(wěn)定的。

命題8設(shè)L是完備格。若L是W-穩(wěn)定的，則Kw(L)是完備格。

定義15設(shè)L是偏序集。若?x∈L,wx∩Kw(L)是定向集，且x=∨(wx∩Kw(L))，則稱L為W-代數(shù)偏序集。若?w還是Weakly increasing的，則稱L為強(qiáng)W-代數(shù)偏序集。若DcpoL是(強(qiáng))W-代數(shù)偏序集，則稱L為(強(qiáng))W-代數(shù)Domain。

上述所定義的W-代數(shù)偏序集以及強(qiáng)W-代數(shù)偏序集不一定是代數(shù)偏序集，見例2。

圖2 L上的序關(guān)系≤Fig.2 Order relation ≤ of L

可以驗(yàn)證，L是(強(qiáng))W-代數(shù)偏序集。由于x不是緊元，故L不是代數(shù)偏序集。

(2) 設(shè)L=N∪{a,b,c,d}。其中L上的序關(guān)系≤如圖3所示。

圖3 L上的序關(guān)系≤Fig.3 Order relation ≤ of L

可以驗(yàn)證，L是W-代數(shù)偏序集，且a?wb≤c?wd不能推出a?wc。故L不是強(qiáng)W-代數(shù)偏序集，也不是代數(shù)偏序集。

命題9設(shè)L是偏序集。若?x∈L，存在定向集D?wx∩Kw(L),使得x=∨D,則L是W-代數(shù)偏序集。

證明(1)wx∩Kw(L)是定向集。?a、b∈wx∩Kw(L)，則a?wa?wx,b?wb?wx。從而有a?wx,b?wx。又x=∨D,故?da、db∈D,使得a≤da,b≤db。又D是定向集，故?d∈D，使得da、db≤d。又D?wx∩Kw(L),故

d∈wx∩Kw(L)且a,b≤d。

(2)x=∨(wx∩Kw(L))。由D?wx∩Kw(L)知，∨D≤∨(wx∩Kw(L))。由x=∨D知,x≤∨(wx∩Kw(L))。反之，由于wx∩Kw(L)?↓x，則∨(wx∩Kw(L))≤∨↓x=x。故

x=∨(wx∩Kw(L)。

推論1每個(gè)代數(shù)偏序集都是W-代數(shù)偏序集。

證明設(shè)L是代數(shù)偏序集,則?x∈L，↓x∩K(L)是定向集，且x=∨(↓x∩K(L))。由命題9知，只需證↓x∩K(L)?wx∩Kw(L)。由于?y∈↓x∩K(L),y?y≤x,故y?y?x,由命題2知

y?wy?wx,即y∈wx∩Kw(L)。

命題10設(shè)L是偏序集，則L是W-代數(shù)偏序集當(dāng)且僅當(dāng)L是Exact偏序集，且?x、y∈L，若x?wy，則?k∈Kw(L)使得x≤k?wy。

證明必要性。首先證明L是Exact偏序集。由L是W-代數(shù)偏序集知，?x∈L,wx∩Kw(L)是定向集且x=∨(wx∩Kw(L))。又因?yàn)閣x∩Kw(L)?wx，故L是Exact偏序集。

其次證明，?x、y∈L。若x?wy,則?k∈Kw(L)使得x≤k?wy。

由L是W-代數(shù)偏序集知，?y∈L,wy∩Kw(L)是定向集，且y=∨(wy∩Kw(L))。

設(shè)x?wy,則?k∈wy∩Kw(L),使得x≤k，從而x≤k?wy且k∈Kw(L)。

k∈wx∩Kw(L),且a、b≤k。

(ⅱ)x=∨(wx∩Kw(L))。顯然有∨(wx∩Kw(L))≤x。反之，假設(shè)x∨(wx∩Kw(L)),由命題3知，?u∈L，使得

u?wx且u∨(wx∩Kw(L))。

由u?wx以及已知條件知，?k∈Kw(L)使得u≤k?wx。從而k∈wx∩Kw(L)且u≤k。所以

u≤k≤∨(wx∩Kw(L)),

矛盾。故x≤∨(wx∩Kw(L))。從而

x=∨(wx∩Kw(L))。

推論2每個(gè)強(qiáng)W-代數(shù)Domain都是弱Domain。

p(y)=p(p(y))=p(∨wp(y))=

p(p(∨wp(y)))=

∨p(L){p(u)|u?wp(y)},

命題12設(shè)L是W-代數(shù)偏序集,p:L→L是保定向并的投射算子，則Kw(p(L))?p(Kw(L))。

命題13設(shè)L是W-代數(shù)偏序集，p:L→L是保定向并的單的核算子，則p(L)是W-代數(shù)偏序集。

證明設(shè)y∈p(L)?L,則y∈L。由L是W-代數(shù)偏序集知，wy∩Kw(L)是定向集，且y=∨(wy∩Kw(L))。由于p保定向并，故

y=p(y)=p(∨(wy∩Kw(L)))=

∨p(wy∩Kw(L))。

下證p(wy∩Kw(L))?。其中

?t∈p(wy∩Kw(L)),則?x∈wy∩Kw(L)使得t=p(x),則。由命題11知，。即。?D∈D(p(L)),t=∨p(L)D,則p(x)=t=p(t)=p(∨p(L)D)。由p是核算子知，∨LD存在且∨p(L)D=∨LD,則p(x)=p(∨LD)。再由p是單的知，x=∨LD。由知，?d∈D,使得x≤d。從而p(x)≤p(d)=d,即t≤d。故,即

3 弱Domain的局部基

定義16設(shè)L是Dcpo，x∈L。若Dx?wx,Dx是定向集且∨Dx=x,則稱Dx是x的局部基。

命題14設(shè)L是Dcpo，則L是Exact偏序集當(dāng)且僅當(dāng)?x∈L,x有局部基。

命題15設(shè)L是弱Domain，x∈L，且D?wx。則D是x的局部基當(dāng)且僅當(dāng)?y∈wx,?d∈D,使得y?wd。

證明必要性。?y∈wx,由命題6知，?z∈L使得y?wz?wx。又因?yàn)镈是x的局部基，則x=∨D,所以?d∈D使得y?wz≤d?wx。由?w是Weakly increasing的知，y?wd。

充分性。設(shè)d1、d2∈D,則d1、d2?wx。由wx是定向集知，?d′∈wx使得d1、d2≤d′且d′?wx，由條件知?d∈D使得d′?wd,則d1、d2≤d。從而D是定向集。顯然有x=∨wx≤∨D≤x故x=∨D,即D是x的局部基。

命題16設(shè)L是弱Domain，x∈L，且D?wx。則D是x的局部基當(dāng)且僅當(dāng)D是定向集且?y∈L，若xy，則?d∈D使得dy。

證明必要性。顯然D是定向集。由D是x的局部基知，x=∨D。若xy,則∨Dy。故?d∈D使得dy;

充分性。只需證x=∨D。由D?wx知，∨D≤∨wx=x。反之，假設(shè)x∨D，則由條件知?d∈D使得d∨D，矛盾，故x≤∨D。從而x=∨D。

命題17設(shè)L是弱Domain，x∈L,且D?wx,則D是x的局部基當(dāng)且僅當(dāng)?y∈L，若y∈wx,則?d∈D，使得y≤d。

證明必要性。由命題15可知。

充分性。設(shè)d1、d2∈D，則d1、d2?wx。由wx是定向集知,?d′∈wx，使得d1、d2≤d′。又由條件知?d∈D使得d′≤d。這時(shí)有d1、d2≤d，故D是定向集。顯然有x=∨wx≤∨D≤x。故x=∨D,即D是x的局部基。

命題18設(shè)L是弱Domain,x∈L。若D是x的最小局部基，則D?Kw(L)。

證明由D是x的最小局部基知，D?wx。假設(shè)?b∈DKw(L)。下證D也是x的局部基。

?d1、d2∈D,由D是定向集知?d0∈D使得d1、d2≤d0,再由D是定向集知?d3∈D使得b、d0≤d3。由命題15知?d∈D使得d3?wd。從而d1、d2≤d,b?wd。故b≠d。所以D是定向集。由D是x的局部基以及命題15知，?d0∈D使得b?wd0。且d0∈D。從而x=∨D=∨(D),即x=∨(D);

從而D是x的局部基。這與D的最小性矛盾,故D?Kw(L)。

推論3設(shè)L是弱Domain。若?x∈L,x有最小局部基，則L是強(qiáng)W-代數(shù)Domain。

命題19設(shè)L、M是弱Domain，則Scott連續(xù)映射f:L→M保局部基當(dāng)且僅當(dāng)f保Weakly way below關(guān)系。

證明必要性。設(shè)x、y∈L且x?wy,Dy是y的局部基，則由命題15知，?d∈Dy使得x?wd。因?yàn)閒保局部基，所以f(Dy)是f(y)的局部基。則f(d)∈f(Dy)?wf(y)。從而

f(x)≤f(d)?wf(y),則f(x)?wf(y)。

充分性。設(shè)Dx是x的局部基，則Dx?wx,x=∨Dx。由連續(xù)映射f保Weakly way below關(guān)系知，f(Dx)?wf(x)且f(Dx)是定向集，且

∨f(Dx)=f(∨Dx)=f(x)。

故f(Dx)是f(x)的局部基，即f保局部基。

4 結(jié)語(yǔ)

本文在代數(shù)偏序集的基礎(chǔ)上,引入了W-代數(shù)偏序集的概念,討論了W-代數(shù)偏序集、Exact偏序集以及代數(shù)偏序集的關(guān)系。最后引入弱Domain的局部基的概念,討論了局部基的相關(guān)性質(zhì)。這些結(jié)果將有利于對(duì)保局部基的Scott連續(xù)映射的性質(zhì)展開進(jìn)一步的研究。

[1] Gierz G, Lawson J D, Stralka A. Quasicontinuous posets[J].Houston Journal of Mathematics, 1983, 9(2): 191-208.

[2] Wright J B, Wagner E G, Thather J W. A uniform approach to inductive posets and inductive closure[J].Theoretical Computer Science, 1978, 7(1): 57-77.

[3] Mashburn J.A comparison of three topologies on ordered sets[J].Topology Proceedings, 2007, 31: 1-21.

[4] 俞挺, 徐曉泉.Exact偏序集的乘積和映射性質(zhì)[J].江西師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2008, 32(3): 292-295.

[5] 趙彬, 劉妮.連續(xù)domain的特征與濃度[J].陜西師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2002, 30(2): 1-6.

[6] Davey B A, Priestley H A.Introduction to lattice and order[M].Cambridge:Cambridge University Press,1990.

[7] Gierz G, Hofmann K H, Keimel K, et al.Continuous lattices and domains[M].Cambridge: Cambridge University Press, 2003.

[8] 陳昱.半連續(xù)格及相容連續(xù)偏序集研究[D].揚(yáng)州: 揚(yáng)州大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 2009.

〔責(zé)任編輯 宋軼文〕

W-algebraic poset and its properties

SHE Haifang, ZHAO Bin*

(School of Mathematics and Information Science, Shaanxi Normal University,Xi′an 710119, Shaanxi, China)

The concepts ofW-algebraic poset and strongW-algebraic poset are introduced.The relationship amongW-algebraic poset,Exact poset and algebraic poset is investigated.The image of aW-algebraic poset under an injective kernel operator preserving sups of directed sets isW-algebraic poset.It is shown that it is a strongW-algebraic domain if every point of a weak domain has a minimum local basis.It is also shown that a Scott continuous mapping of a weak domain preserves local basis if and only if it preserves Weakly way below relation.

W-algebraic poset; algebraic poset; Exact poset; weak domain; local basis

06A11, 06B35

1672-4291(2015)03-0013-05

10.15983/j.cnki.jsnu.2015.03.134

2014-09-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171196,11301316); 中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(GK201302003)

折海芳,女,碩士研究生,研究方向?yàn)楦裆贤負(fù)渑c模糊推理。E-mail: shehaifang123@126.com

*通信作者：趙彬,男,教授,博士生導(dǎo)師。E-mail: zhaobin@snnu.edu.cn

O153.1

A