羅天紅，羅永樂，王正攀

西南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 重慶 400715

一直以來， 半群上的同余與同余格是國內(nèi)外學(xué)者密切關(guān)注的對(duì)象(如文獻(xiàn)[1-10]等)． 綜述文獻(xiàn)[6-7]較詳盡地給出了20世紀(jì)關(guān)于半群的同余格的研究成果， 并指出了若干相關(guān)問題． 文獻(xiàn)[1]首次介紹了頂點(diǎn)間最多有1條邊的圖的圖逆半群， 并給出了這種圖逆半群同余自由的充分條件． 文獻(xiàn)[11]證明了： 頂點(diǎn)指數(shù)最多為1的連通圖最多有1個(gè)匯點(diǎn)， 且若該圖不是樹， 則在圈共軛的意義下只有1個(gè)非平凡圈． 文獻(xiàn)[9]建立了從圖逆半群上的所有同余構(gòu)成的集合到圖的同余三元組構(gòu)成的集合的一一對(duì)應(yīng)． 文獻(xiàn)[3]證明了： 圖逆半群的同余格是上半模格， 但不是下半模格． 文獻(xiàn)[4]應(yīng)用有向圖的性質(zhì)， 證明了圖逆半群上的0-受限同余所組成的集合關(guān)于包含關(guān)系形成一個(gè)分配格． 在這些基礎(chǔ)之上， 本文利用文獻(xiàn)[3]中的方法證明了： 頂點(diǎn)指數(shù)最多為1的連通圖上的圖逆半群的同余格不僅是上半模格， 還是下半模格．

有向圖Γ=(V，E，r，s)由V，E以及E到V的映射r，s構(gòu)成．V中的元素為頂點(diǎn)，E中的元素為邊． 對(duì)于邊e，s(e)為e的起點(diǎn)，r(e)為e的終點(diǎn)． 用|X|表示集合X的基數(shù)， 對(duì)任意頂點(diǎn)v， |s-1(v)|稱為v的指數(shù)． 以下Γ=(V，E，r，s) 總表示某個(gè)有向圖， 簡(jiǎn)記為Γ．

由V和E以及集合E*={e*：e∈E} 生成的滿足以下各條的含零半群稱為Γ上的圖逆半群， 記為Inv(Γ)： 對(duì)任意u，v∈V，e，f∈E，

(G1)uv=δu，vu；

(G2)s(e)e=er(e)=e；

(G3)r(e)e*=e*s(e)=e*；

(G4)f*e=δf，er(e)．

在Γ中， 路是由邊形成的序列α=e1e2…en， 其中r(ei)=s(ei+1)，i=1，2，…，n-1． 此時(shí)s(α)=s(e1)稱為路α的起點(diǎn)，r(α)=s(en)稱為路α的終點(diǎn)． 記{s(ei)：i=1，2，…，n}為u(α)， 約定頂點(diǎn)v為一條路徑， 且u(v)=?． 若s(α)=r(α)， 且當(dāng)i≠j時(shí)有s(ei)≠s(ej)， 則稱α為圈． 我們用Path(Γ) 表示Γ中所有路構(gòu)成的集合． 對(duì)于V1?V， 用C(V1) 表示所有滿足u(c)?V1的圈構(gòu)成的集合．

設(shè)H為V的子集， 若對(duì)任意e∈E， 當(dāng)s(e)∈H時(shí)總有r(e)∈H， 則稱H為V的遺傳子集． 令H為遺傳子集． 對(duì)任意v∈V， 稱|{e∈E：s(e)=v，r(e)?H}|為v相對(duì)于H的指數(shù)． 設(shè)W是V的子集， 且W中的元素相對(duì)于H的指數(shù)為1， 顯然H∩W=?． 設(shè)f是C(V)到Z+∪{∞}的映射， 若對(duì)任意c∈C(H)， 有f(c)=1， 對(duì)任意c?C(H)∪C(W)， 有f(c)=∞， 則稱f為圈映射． 在文獻(xiàn)[3]中，V的遺傳子集H、 相對(duì)于H的指數(shù)為1的頂點(diǎn)集的子集W， 以及圈映射f構(gòu)成Γ的一個(gè)同余三元組， 記為(H，W，f)． 用CT(Γ) 表示Γ的所有同余三元組構(gòu)成的集合．

對(duì)任意m1，m2∈Z+∪{∞}， 我們用(m1，m2) 表示它們的最大公約數(shù)， [m1，m2]表示它們的最小公倍數(shù)， 且設(shè)Z+∪{∞}中的任意元素m都整除∞， 即(m， ∞)=m， [m， ∞]=∞．

根據(jù)文獻(xiàn)[3]， 作者證明了圖逆半群Inv(Γ)的同余格同構(gòu)于CT(Γ) 關(guān)于以下二元關(guān)系形成的格： 對(duì)任意(H1，W1，f1)，(H2，W2，f2)∈CT(Γ)， (H1，W1，f1)≤(H2，W2，f2) 當(dāng)且僅當(dāng)H1?H2，W1H2?W2， 且對(duì)任意c∈C(V)，f2(c)|f1(c)．

在格L中， 我們用a∧b和a∨b分別表示a和b的上確界和下確界． 若a>b， 且在L中不存在元素x使得a>x>b， 則稱a覆蓋b， 記為a?b或ba．

對(duì)L中任意元素a，b，c， 若有(a∨b)∧c=(a∧c)∨(b∧c)， 則稱L為分配格；

對(duì)L中任意元素a，b，c，a≤c， 若有(a∨b)∧c=a∨(b∧c)， 則稱L為模格；

對(duì)L中任意元素a，b， 若a?a∧b，b?a∧b時(shí)總有a∨b?a，a∨b?b， 則稱L為上半模格； 對(duì)L中任意元素a，b， 若a∨b?a，a∨b?b時(shí)總有a?a∧b，b?a∧b， 則稱L為下半模格．

本文引用文獻(xiàn)[3] 對(duì)CT(Γ)中任意兩個(gè)元素的上確界和下確界的刻畫． 設(shè)

T1=(H1，W1，f1)T2=(H2，W2，f2)

是Γ的任意兩個(gè)同余三元組． 我們用V0表示(W1∪W2)(H1∪H2)中相對(duì)于H1∪H2的指數(shù)為0的頂點(diǎn)形成的集合，X表示集合(W1∩W2)V0，J表示(W1∪W2)(H1∪H2)中存在以其為起點(diǎn)的滿足條件u(α)?W1∪W2且以V0中某頂點(diǎn)為終點(diǎn)的路徑α的頂點(diǎn)形成的集合．

定理1當(dāng)圖Γ為頂點(diǎn)指數(shù)最多為1的連通圖時(shí)， 同余格(CT(Γ)， ≤)是下半模格．

證當(dāng)Γ為頂點(diǎn)指數(shù)最多為1的連通圖時(shí)， 由文獻(xiàn)[11]的定理3.1知：Γ要么在不計(jì)循環(huán)置換的意義下只有1個(gè)圈， 要么最多有1個(gè)匯點(diǎn)(V中任意頂點(diǎn)都有路徑到該點(diǎn)的頂點(diǎn)即為匯點(diǎn))； 若H為V的非空遺傳子集， 則H包含Γ的圈或匯點(diǎn)． 我們用ev表示從頂點(diǎn)v(v∈V)出發(fā)的邊， 由Γ的定義，ev是唯一的． 則

V0={v∈W1H2：r(ev)∈H2}∪{v∈W2H1：r(ev)∈H1}

由于W1∩W2中的頂點(diǎn)相對(duì)于H1∪H2的指數(shù)為1， 故

X=W1∩W2

對(duì)T1=(H1，W1，f1)∈CT(Γ)，T2=(H2，W2，f2)∈CT(Γ)， 由文獻(xiàn)[3]中引理2.7和引理2.8可得Tl=(Hl，Wl，fl)， 其中

Hl=H1∩H2Wl=(W1∩H2)∪(W2∩H1)∪X

對(duì)任意c∈C(V)，fl(c)=[f1(c)，f2(c)]．Tu=(Hu，Wu，fu)， 其中

Hu=H1∪H2∪JWu=(W1∪W2)Hu

對(duì)任意c∈C(V)，fu=(f1(c)，f2(c))． 要證明定理1， 即證明若有Tu?T1，Tu?T2， 則有T1?Tl，T2?Tl．

當(dāng)H1=H2時(shí)， 據(jù)文獻(xiàn)[3]的推論2.9 可知， 結(jié)論成立．

當(dāng)H1≠H2時(shí)， 我們分H1?H2，H2?H1和H1H2且H2H1這3種情形討論．

情形1H1?H2．

此時(shí)

Hu=H2∪JWu=(W1∪W2)(H2∪J)

H1可為空集， 但H2不能為空集， 則H2包含Γ的匯點(diǎn)或圈， 從而W2中無圈． 由圈映射的定義， 對(duì)任意c∈C(V)，f2(c) 取值為1， 故

fu(c)=(f1(c)，f2(c))=f2(c)fl(c)=[f1(c)，f2(c)]=f1(c)

情形1.1 當(dāng)J=?時(shí)， 即Hu=H2．

由Tu?T1，Tu?T2以及文獻(xiàn)[3]的引理2.1和引理2.3知，W1H2=Wu，W2?Wu且|WuW2|=1． 故有W2?Wu?W1， 從而

Tl=(H1， (W1∩H2)∪W2，f1)

因?yàn)?/p>

|W1Wl|=|W1[(W1∩H2)∪W2]|=|WuW2|=1

所以由文獻(xiàn)[3]的引理2.3， 結(jié)論成立． 下證T2?Tl．

對(duì)任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H2，W2，f2)>(H′，W′，f′)≥(H1， (W1∩H2)∪W2，f1)

(1)

則

H1?H′?H2

若H2=H′， 則W′?W2， 且由(1)式可得

[(W1∩H2)∪W2]H2=W2?W′

所以W′=W2， 進(jìn)而f′=f2， 與假設(shè)矛盾， 所以H2≠H′．

由(1)式可知

[(W1∩H2)∪W2]H′?W′

所以(W1∩H2)H′中的頂點(diǎn)相對(duì)于H′的指數(shù)為1． 又由Wu=W1H2知，W1H2中頂點(diǎn)相對(duì)于H2的指數(shù)為1， 從而相對(duì)于H′的指數(shù)也為1 (V中任意頂點(diǎn)的指數(shù)最多為1)， 故(H′，W1H′，f2)∈CT(Γ)． 所以有

Tu=(H2，W1H2，f2)>(H′，W1H′，f2)≥(H1，W1，f1)

由Tu?T1知H′=H1．

但若H1=H′， 由Tu?T1和文獻(xiàn)[3]的引理2.1知， 當(dāng)c∈C[(W1∩H2)∪W2]時(shí)， 有

fu(c)=f1(c)=f2(c)

且在H2[H1∪(W1∩H2)∪W2]=H2(H1∪W1)中沒有頂點(diǎn)相對(duì)于H1的指數(shù)為1． 又由于

H1?H2[(W1∩H2)∪W2]H2=W2

故由文獻(xiàn)[3]的引理2.5得

W′=(W1∩H2)∪W2f′=f1

即T′=Tl． 從而有T2?Tl．

情形1.2 當(dāng)J≠?時(shí)， 即Hu=H2∪J．

此時(shí)H1?Hu，H2?Hu． 由Tu?T1和文獻(xiàn)[3]的引理2.1知

W1Hu=(W1∪W2)Hu

所以W2W1?J． 但在(H2∪J)(H1∪W1)中頂點(diǎn)相對(duì)于H1的指數(shù)為0， 所以W2W1中頂點(diǎn)相對(duì)于H1的指數(shù)為0， 從而相對(duì)于H2的指數(shù)為0， 由同余三元組的定義W2W1=?， 即有W2?W1． 類似地， 由Tu?T2和文獻(xiàn)[3]的引理2.1知

W1(W2∪H2)?JWu?W2

所以有

Wu?W2?W1

因?yàn)?H2∪J)(H2∪W2)中頂點(diǎn)相對(duì)于H2的指數(shù)為0， 所以

V0=W1(H2∪W2)

因此W2≠W1， 否則V0=?，J=?， 與假設(shè)矛盾． 所以

Wu?W2?W1

下證|V0|=1． 若|V0|>1， 對(duì)任意v1∈V0， 令

J1={v1}∪{v∈J： 存在α∈Path(Γ)， 使得s(α)=v，u(α)?W1，r(α)=v1}

由J1的定義不難看出H2∪J1是遺傳子集． 若W2J1中存在頂點(diǎn)v相對(duì)于H2∪J1的指數(shù)為0， 因?yàn)棣Ｊ沁B通圖， 所以存在一條邊以v為起點(diǎn)， 終點(diǎn)在J1中， 因此有v∈J1， 矛盾． 故W2J1中的頂點(diǎn)相對(duì)于H2∪J1的指數(shù)為1， 因此(H2∪J1，W2J1，f2)∈CT(Γ)． 所以有

(H2∪J，W1(H2∪J)，f2)>(H2∪J1，W2J1，f2)>(H2，W2，f2)

與Tu?T2矛盾， 所以

|V0|=|W1(H2∪W2)|=1

由于

|W1Wl|=|W1[(W1∩H2)∪W2]|=|W1(H2∪W2)|=1

據(jù)文獻(xiàn)[3]的引理2.3， 有

(H1，W1，f1)?(H1， (W1∩H2)∪W2，f1)

即有T1?Tl． 下證T2?Tl．

對(duì)任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H2，W2，f2)>(H′，W′，f′)≥(H1， (W1∩H2)∪W2，f1)

(2)

則有

H1?H′?H2

若H′=H2， 則由(2)式可得

[(W1∩H2)∪W2]H2=W2?W′W′?W2

所以W′=W2， 進(jìn)而f′=f2， 與假設(shè)矛盾． 所以H2≠H′． 故

H1?H′?H2

若以V0中的唯一的頂點(diǎn)為起點(diǎn)的邊的終點(diǎn)在H′中， 則H′∪J是遺傳子集． 由(2)式可得

[(W1∩H2)∪W2]H′?W′

因此W1H′中的頂點(diǎn)相對(duì)于H′的指數(shù)為1． 又因(W1∩H2)H′?H2， 且H2為遺傳子集， 所以(W1∩H2)H′中的頂點(diǎn)相對(duì)于H′∪J的指數(shù)為1． 因?yàn)?/p>

H′∪J?H2∪J=Hu

故Wu中的頂點(diǎn)相對(duì)于H′∪J的指數(shù)也為1． 從而得到

(H′∪J，Wu∪[(W1∩H2)H′]，f2)∈CT(Γ)

且有

(H2∪J，Wu，f2)>(H′∪J，Wu∪[(W1∩H2)H′]，f2)>(H1，W1，f1)

這與Tu?T1矛盾， 所以以V0中的唯一的頂點(diǎn)為起點(diǎn)的邊的終點(diǎn)在H2H′中． 于是(H′，W1H′，f1)∈CT(Γ)， 且有

(H2∪J，Wu，f2)>(H′，W1H′，f1)≥(H1，W1，f1)

再由Tu?T1知H′?H1．

由(2)式和文獻(xiàn)[3]的引理2.5 知[(W1∩H2)∪W2]=W′， 進(jìn)而f′=f2．T2?Tl得證．

情形2H2?H1．

與情形1的證明類似．

情形3H1H2且H2H1．

此時(shí)H1≠?，H2≠?， 故若Γ中有圈， 則圈在H1∩H2中， 所以W1和W2中均無圈． 從而可設(shè)

fu=f1=f2=fl=f． 由Tu?T1，Tu?T2以及文獻(xiàn)[3]的引理2.1可得

V0=[W1(H2∪W2)]∪[W2(H1∪W1)]

下證V0=?． 否則， 不妨設(shè)W2(H1∪W1)≠?． 令

J2={v∈J： 存在α∈Path(Γ)， 使得s(α)=v，u(α)?W1∪W2，r(α)∈W2(H1∪W1)}

則J2≠?． 由Tu?T1和文獻(xiàn)[3]的引理2.1知，W2(H1∪W1)中的頂點(diǎn)相對(duì)于H1的指數(shù)為0， 所以H1∪J2為遺傳子集． 類似于情形1.2的證明，W1J2中的頂點(diǎn)相對(duì)于H1∪J2的指數(shù)為1， 所以(H1∪J2，W1J2，f)∈CT(Γ)． 因此

(H1∪H2∪J，Wu，f)>(H1∪J2，W1J2，f)>(H1，W1，f1)

這與Tu?T1矛盾， 故V0=?．

由V0=?及J的定義可得J=?， 所以

W1=(W1∩H2)∪(W1∩W2)W2=(W2∩H1)∪(W1∩W2)

Tu=(H1∪H2，W1∩W2，f)Tl=(H1∩H2，W1∪W2，f)

下證T1?Tl． 對(duì)任意T′=(H′，W′，f′)∈CT(Γ)， 若有

(H1，W1，f)>(H′，W′，f′)≥(H1∩H2，W1∪W2，f)

(3)

則有H1∩H2?H′?H1． 若H′=H1， 由(3)式可得

(W1∪W2)H′=W1?W′W′?W1

所以W′=W1． 進(jìn)而f′=f， 與假設(shè)矛盾， 所以H′≠H1． 故H1∩H2?H′?H1， 進(jìn)而有

H2?H′∪H2?H1∪H2

由(3)式可知(W1∪W2)H′?W′， 所以W2H′?W′， 這說明在W2H′中的頂點(diǎn)相對(duì)于H′的指數(shù)為1． 又因?yàn)镠′∪H2是遺傳子集． 所以(H′∪H2，W2H′，f)∈CT(Γ)． 由

Tu>(H′∪H2，W2H′，f)≥(H2，W2，f2)

得H2=H′∪H2， 即H′?H2． 又由H′?H1， 所以H′?H1∩H2． 故H′=H1∩H2． 與情形1.1的證明類似， 由文獻(xiàn)[3]的引理2.5得

W′=W1∪W2f′=f

即T′=Tl，T1?Tl得證． 同理可證T2?Tl．