偏序集的序連通關(guān)系及其序連通分支

唐照勇

(揚州大學(xué) 廣陵學(xué)院,江蘇揚州 225000)

§1 引言

偏序集刻畫了事物的順序特征,連通性是偏序集理論重要研究內(nèi)容.元素間連通具有很強的直觀性,表現(xiàn)為其Hassse圖兩個元素都是相連的.文獻[1]闡述了序連通概念,即任意兩個元素間可以找到有限多個元素,使得這些元素間是依次可比地.唐照勇等在文獻[2-4]中也研究了偏序集的連通性,不過構(gòu)造的集列中每個步集(除了第一個步集外)既是上升集,也是下降集.在此基礎(chǔ)上,本文以上集列為工具,構(gòu)造上集列連通分支來刻畫偏序集的連通性,提供描述偏序集連通性的新方法及新形式.由此得到許多良好的結(jié)論,并且由此可知,刻畫偏序集連通性的途徑可以是多樣地.

§2 預(yù)備知識

定義2.1[1]設(shè)E是一個非空集合.如果R是E上的一個二元關(guān)系并滿足下面條件(1)-條件(3),則稱R是E的序關(guān)系.

(1) 自反性: (?x ∈E)xRx;

(2) 反對稱性: (?x,y ∈E)若xRy,yRx,則x=y;

(3) 傳遞性: (?x,y,z ∈E)若xRy,yRz,則xRz.

通常把這樣的一個序關(guān)系R寫為≤(稱為小于或等于).稱賦予序≤的集合E為偏序集,記為(E,≤).

定義2.2[1]設(shè)(E,≤)是偏序集,D是E的非空子集.定義D上的一個序關(guān)系

則(D,≤D)是一個偏序集,稱為(E,≤)的子偏序集.

定義2.3[1]設(shè)(E,≤)是偏序集,D是E的非空子偏序集.若對任意x ∈D和任意y ∈E,y ≤x蘊含y ∈D,則稱D是E的一個下降集;對偶地,稱D是E的一個上升集,如果對任意x ∈D和任意y ∈E,y ≥x蘊含y ∈D.

定義2.4[1]設(shè)(E,≤)是偏序集,若對任意x,y ∈E,inf{x,y}和sup{x,y}在E中存在,則稱E是一個格.

定義2.5[5]設(shè)f:是一個保序雙射.如果f的逆映射f-1:也是保序映射,那么稱f是保序同構(gòu)映射,并稱偏序集E和F是保序同構(gòu),記為.

引理2.1[5]設(shè)(E,≤)是偏序集,H是E的非空子集.則H是上升(下降)集當(dāng)且僅當(dāng)

其中↑H={x ∈E |x ≥y,y ∈H},↓H={x ∈E |x ≤y,y ∈H}.

引理2.2設(shè)(E,≤)是偏序集,A,B是E的非空子集.則有

由此引理,易得下列推論.

推論設(shè)(E,≤)是偏序集,A,B是E的非空子集.若B ?A,則有

引理2.3[1]設(shè)E,F是偏序集.則f:是一個保序同構(gòu)映射當(dāng)且僅當(dāng)下面的條件成立.

(1)f是滿射;(2) (?x,y ∈E)x ≤y ?f(x)≤f(y).

§3 上集列與上集列連通分支

定義3.1(上集列)設(shè)(E,≤)是偏序集,a ∈E.按以下步驟操作.

定義3.2(上集列連通分支)設(shè)(E,≤)是偏序集,a ∈E,是上集列.記

則稱[↑a]為元素a的上集列連通分支.在不引起混亂的情況下,簡稱連通分支.本文中所提到的連通分支都是指上集列連通分支.

定理3.1設(shè)(E,≤)是偏序集,a,b ∈E.a ∈[↑b]的充要條件是存在有限個元素

注1定理結(jié)論中(2)式和(3)式是可以相互轉(zhuǎn)化的.例如當(dāng)n是一個偶數(shù)時,結(jié)論(2)的形式

也可以寫成(3)的形式

因而無論采用哪種形式來說都不影響定理的正確性.

注2這些有限個元素xi ∈[↑b],i=1,2,···,n.這由定理的證明過程容易得到.

§4 刻畫連通性

下面將利用上集列連通分支來刻畫偏序集的連通性.

定義4.1(連通)設(shè)(E,≤)是偏序集,x,y ∈E.若存在一個連通分支[↑a],使得x,y ∈[↑a],則稱x和y在E上是連通的,簡稱x和y連通,記作x～y,也就是說屬于同一個連通分支的兩個元素是連通的.

定理4.1設(shè)(E,≤)是偏序集,a,b ∈E.若[↑a]∩[↑b]?,則[↑a]=[↑b].

證假設(shè)[↑a]∩[↑b]?,則存在e ∈E,使得e ∈[↑a]且e ∈[↑b].任取x ∈[↑a],下證x ∈[↑b].

依據(jù)定理3.1必要條件可知,存在有限個元素

將這些元素合起來便有p+m+n個元素使得(相同元素重復(fù)計算)

在依據(jù)定理3.1充分條件可知x ∈[↑b],故[↑a]?[↑b].同理可證[↑b]?[↑a],所以[↑b]=[↑a].

連通關(guān)系構(gòu)成了偏序集元素間的一個關(guān)系,而且這個關(guān)系是一個等價關(guān)系.

定理4.2偏序集的連通關(guān)系是一個等價關(guān)系.

證設(shè)(E,≤)是偏序集,x,y,z ∈E.

(1) 顯然連通關(guān)系～滿足反身性: 因為x ∈[↑x],故x～x;

(2) 滿足對稱性: 假設(shè)x～y,由連通定義知存在一個連通分支[↑z],使得x,y ∈[↑z],故y～x;

(3) 關(guān)系滿足傳遞性: 假設(shè)x～y,y～z.由連通定義知存在連通分支[↑a],[↑b],使得

從而[↑a]∩[↑b]?,故[↑a]=[↑b].所以x,z ∈[↑b],即x～z.

由近世代數(shù)[6]知識可知,一個等價關(guān)系必然形成一個分類.必須指出的是上述連通分支就是分類中的一個類,即有如下結(jié)論.

定理4.3設(shè)(E,≤)是偏序集,a ∈E.則[↑a]=[a](其中[a]是一個類).

證設(shè)類[a]={x|x～a}.

由x～a知,存在一個連通分支[↑c],使得x,a ∈[↑c].則a ∈[↑a]∩[↑c]?,故[↑a]=[↑c],x ∈[↑a].由x的任意性可知,

此定理揭示了由連通關(guān)系產(chǎn)生的類具體的構(gòu)造,即每一個類都是一個連通分支.這樣就不難得到下述定理.

定理4.4設(shè)(E,≤)是偏序集,a,b ∈E.a ∈[↑b]當(dāng)且僅當(dāng)a～b.

由定理3.1,定理4.4立馬可得下述定理.

定理4.5設(shè)(E,≤)是偏序集,a,b ∈E.a～b當(dāng)且僅當(dāng)存在在有限個元素

另外依據(jù)定理4.1還可得下面結(jié)論.

定理4.6 設(shè)(E,≤)是偏序集,a,b ∈E.a ∈[↑b]當(dāng)且僅當(dāng)[↑a]=[↑b].

證(必要性)由a ∈[↑b]且a ∈[↑a]知[↑a]∩[↑b]?,從而[↑a]=[↑b].

充分性顯然.

§5 連通子集

定義5.1 設(shè)(D,≤D)是偏序集(E,≤)的非空子偏序集,如果D中任意兩個元素在(D,≤D)上都是連通的,稱D是E的連通子集.否則稱D為不連通子集.特別地,若E是連通的,則稱偏序集(E,≤)是連通偏序集;若E是不連通的,則稱偏序集(E,≤)是不連通偏序集.

值得注意的是,子偏序集上的連通概念,也是在子偏序集上相應(yīng)的定義步集,上集列,上集列連通分支等概念基礎(chǔ)上的.這里就不贅述了.

定理5.1格都是連通偏序集.

由此定理可知,格的連通分支只有一個,就是其本身.事實上,任何一個連通偏序集的連通分支都只有一個,就是其本身.反過來,有且僅有一個連通分支的偏序集必是連通偏序集.

下例指出一個事實,偏序集中的兩個元素在此偏序集中是連通的,但是在子偏序集中可能是不連通的.反過來,如果兩個元素在子偏序集中連通,必然在偏序集中連通,這點可由定理4.5得知.

例1設(shè)(E,≤)是偏序集,其Hasse圖如下圖1-1所示.

圖1-1 (E,≤)

易得由元素a產(chǎn)生的上集列

圖1-2 (D,≤D)

定理5.2設(shè)(E,≤) 是偏序集,a ∈E.則連通分支[↑a]是E的連通子集.

證設(shè)b,c ∈[↑a],即b～c.下證b和c在子偏序集([↑a],≤[↑a]) 上也是連通的.一方面,依據(jù)定理4.5必要條件,由b～c可知,存在有限個元素

由定理3.1的注2知xi ∈[↑b](i=1,2,3···n).

另一方面,依據(jù)定理4.6,由b ∈[↑a]得[↑a]=[↑b],故xi ∈[↑a](i=1,2,3···n).再依據(jù)定理4.5充分條件知在子偏序集([↑a],≤[↑a])上b,c之間也是連通的.所以連通分支[↑a]是E的連通子集.

由定理4.3和定理5.2可知

推論1連通分支[↑a]是含元a的最大連通子集.

定理5.3設(shè)(E,≤)是偏序集,則E可以唯一分解為一些連通分支的不交并.

證一方面,取a ∈E,有a ∈[↑a],即對于E中每個元素,都存在某一個連通分支使得該元素屬于這個連通分支;

另一方面,設(shè)a ∈[↑x],a ∈[↑y],則由定理4.1可知[↑x]=[↑y],即每個元素不能同時屬于兩個不同的連通分支,也就是說只能屬于一個連通分支.綜上可知,對于E中每個元素有且只能屬于一個連通分支.故

定義5.2設(shè)H是偏序集(E,≤)的非空子集.若H=↑H=↓H,則稱H是分支并,即分支并既是上升集又是下降集.

下述定理揭示了連通分支應(yīng)該滿足的特征.

定理5.4設(shè)H是偏序集(E,≤)的非空子集.則H是E的連通分支當(dāng)且僅當(dāng)H既是分支并又是連通子集,簡稱連通分支并.

證必要性 設(shè)a ∈E,不妨令H=[↑a],即H是E的連通分支.由定理5.2可知H是連通子集.下證H是分支并.

設(shè)b ∈H,x ∈E,x ≤b.則?n ∈N+,使得于是必有

由此可知H是下降集.同理可證H是上升集,所以H是分支并.必要性得證.

充分性 設(shè)H是一個連通分支并,a ∈H.由預(yù)備知識中的推論,有

以此類推下去知對任意n ∈N+,都有,從而,即連通分支[↑a]?H.下證[↑a]=H.

定理5.5在保序同構(gòu)映射下,連通子集的像(原像)也是連通子集.

證一方面,設(shè)f:是一個保序同構(gòu)映射.其中H是偏序集(E,≤E)的非空連通子集,下證像f(H)是偏序集(F,≤F)的連通子集.

任取x,y ∈f(H),則有唯一元a,b ∈H使得a=f-1(x),b=f-1(y).依據(jù)定理4.5,由a～b可知存在有限個元素

依據(jù)引理2.3知在f(H)中必存在唯一一些元素

從而x與y在f(H)上連通,故f(H)是連通子集.

另一方面,設(shè)H是偏序集(F,≤F)的非空連通子集,類似證明可得原像f-1(H)是偏序集(E,≤E)的連通子集.

另外,不難驗證在保序同構(gòu)映射下,上升集的像(原像)也是上升集,下降集的像(原像)也是下降集.于是結(jié)合定理5.5可知,連通分支并的像(原像)也是連通分支并.最后再由定理5.4可得下列結(jié)論.

定理5.6在保序同構(gòu)映射下,連通分支的像(原像)也是連通分支.

最后指出,就(序)連通關(guān)系和(序)連通分支而言,偏序集與其對偶偏序集是“等同”的.