部分變換半群與全變換半群之間的同態(tài)*

林雙 楊秀良

(1.江蘇省新沂市瓦窯中學(xué)高中部，新沂,221400;2.杭州師范大學(xué)理學(xué)院，杭州，310036)

1 引言

集合X上的所有部分變換的集合稱作是X的部分變換半群，記作PTX；集合X上的所有全變換的集合稱作X的全變換半群, 記作TX；集合X上的所有部分單變換的集合稱作是X的對稱逆半群, 記作ISX. 它們上的運算都是映射的合成(本文規(guī)定合成運算從右到左). 本文討論X是有限的情況，即X是基為自然數(shù)的集合. 不妨設(shè)X=N= {1,2,…,n}.這時PTX，TX和ISX分別記作PTn，Tn和ISn.

1997年，Schein 和Teclezghi[1]研究了ISn的所有自同態(tài). 隨后在 1998 年，他們在[2,3]中又分別討論了Tn和PTn的自同態(tài). 2009年， Ganyushkin 和Mazorchuk 在 [4]中討論自同態(tài)時提出了一個公開問題：描述從S到T的所有同態(tài)(單同態(tài)，滿同態(tài))，其中S,T∈{PTn,Tn,ISn}. 本文描述了PTn與Tn之間的所有同態(tài).

2 主要結(jié)果

設(shè)半群S代表PTn或Tn.半群S的所有自同構(gòu)的集合記作Aut(S),集合N上的置換群記作Sn,群Sn的所有自同構(gòu)的集合記作Aut(Sn).當(dāng)n≠4時,S4除了有正規(guī)子群S4,A4和E4外,還有一個正規(guī)子群K,稱作Klein四元群.

對任意的x∈N,ax={(x,x)}表示PTn中秩為1的冪等元,即

其中ax(i)=?表示i不屬于ax的定義域，即i?dom(ax),i=1,2,…,x-1,x,x+1,…,n.

0x表示PTn或Tn的常量變換，即

0表示PTn的空變換，即

本文的主要結(jié)論如下：

定理1設(shè)n≠4.選取ε,δ∈Tn使得ε3=ε且εδ=δε=δ2=δ.定義Θε,δ:PTn→Tn如下:

則Θε,δ是PTn到Tn的一個同態(tài).若ε2=ε=δ,則Θε,δ是一個常量同態(tài)，即Θε,δ把PTn映到Tn的一個冪等元δ.若ε2=ε≠δ,則Θε,δ是一個秩為2的同態(tài)，即Θε,δ把PTn映到Tn的一個半格{ε,δ},滿足δ<ε.若ε≠ε2≠δ,則Θε,δ是一個秩為3的同態(tài)，即Θε,δ把PTn映到Tn的一個半群{ε,ε2,δ},其中δ是零元,{ε,ε2}是Tn的一個子群.

反之，當(dāng)n≠4時,PTn到Tn的每個同態(tài)都具有以上形式.對于n=4,PT4到T4除了有以上的同態(tài)外,還具有同態(tài)σπ,π∈S4,其定義如下:

K4在S4中的每個陪集恰包含H4中的一個元素.若α∈S4,設(shè)σ(α)∈K4α∩H4是這個元素；若α∈PT4S4,設(shè)σ(α)=04，則σπ定義為:對任意的α∈IS4,σπ(α)=πσ(α)π-1.

定理2設(shè)n≠4.

(i)設(shè)π∈Sn.對任意的α∈Tn,定義Λπ(α)=παπ-1，則Λπ是Tn到PTn的一個同態(tài).

(ii)選取ψ∈Aut(Sn).定義Ωψ:Tn→PTn如下:

則Ωψ是Tn到PTn的一個同態(tài).

(iii)選取ε,δ∈PTn使得ε3=ε且εδ=δε=δ2=δ.定義Θε,δ:Tn→PTn如下:

則Θε,δ是Tn到PTn的一個同態(tài).若ε2=ε=δ,則Θε,δ是一個常量同態(tài).若ε2=ε≠δ,則Θε,δ把Tn映到PTn的一個半格{ε,δ},滿足δ<ε.若ε≠ε2≠δ,則Θε,δ把Tn映到PTn的一個半群{ε,ε2,δ},其中δ是零元,{ε,ε2}是PTn的一個子群.

(iv)選取π∈Sn,i,j,z∈Xn.定義Ψπ:Tn→PTn如下:

則Ψπ是Tn到PTn的一個同態(tài).

反之，對于n≠4,Tn到PTn的每個同態(tài)都具有形式(i)-(iv).對于n=4,T4到PT4除了有以上的同態(tài)外,還具有同態(tài)Υπ,π∈S4, 其定義如下:

3 定理的證明

定理1的證明需要用到以下引理.

引理1([4])n≥1，Tn中不包含任何元素α使得對任意γ∈Sn滿足γα=α.

定理1的證明設(shè)φ是PTn到Tn的同態(tài). 若n=1，則φ(PTn)={(1)}=T1，其中元素(1)表示恒等變換，因此φ是常量同態(tài).

以下設(shè)n>1. 考慮三種情況:φ在Sn上是單的；φ在Sn上是非單的且n≠4；φ在Sn上是非單的且n=4.

若φ在Sn上是單的，則Sn?φ(Sn)，進而|φ(Sn)|=n!.由于φ(Sn)是N的某個子集Y的置換群，其中Y=im(ε)，ε是φ(Sn)的單位元，因此n!=|φ(Sn)|≤|Y|!，進而Y=N,φ(Sn)=Sn.

對任意γ∈Sn，存在η∈Sn使得φ(η)=γ.由于η0=0η=0，因此,

γφ(0)=φ(0)η=φ(0).

由引理1知，φ(0)不可能是Tn中元素，故φ在Sn上不可能是單的.

若φ在Sn上非單且n≠4，則φ具有形式Θε,δ.若φ在Sn上非單的且n=4時，則φ具有形式σπ.再按[2]同樣的討論即可證定理1成立.

下面來證明定理2. 為此，先給出下面幾個引理.

引理2([4]) 設(shè)S表示Tn,ISnTn,ISn或PTn之一.設(shè)ε是S的一個冪等元.則

(i)S的包含ε的一個極大子群Gε為

Gε={α∈S:im(α)=im(ε),ρα=ρε}.

(ii) 若rank(ε)=k,則Gε≌Sk.

證明(i)略.

(ii) 設(shè)冪等元

顯然對任意的i有ti∈Bi.設(shè)Sk是集合{t1, …,tk}上的置換群.Gε中任意一個元素g都具有下面的形式

其中ti1,…,tikti1,…,ti2是t1,…,tk的一個排列.定義映射

顯然φ是一個雙射. 經(jīng)驗算可知φ保持運算, 故φ是同構(gòu).

引理3設(shè)S,T∈{Tn,ISn,PTn},且設(shè)φ是S到T的同態(tài),φ在Sn上是單的,則φ(Sn)=Sn且φ|Sn∈Aut(Sn).

證明由于φ在Sn是單的,因此φ(Sn)?Sn,且φ(Sn)是T的一個子群，進而φ(Sn)包含在T的某個極大子群中.由引理2知T的所有極大子群都同構(gòu)于Sk,k≤n,而且同構(gòu)于Sn的極大子群只有Sn本身,因此φ(Sn)=Sn,且φ|Sn∈Aut(Sn).

引理4設(shè)Xn={1,2,…,n},k是一個正整數(shù)且1≤k≤n,則下列結(jié)論成立:

(i) 若k>n/2,則Xn中任意兩個k-子集的交非空.

(ii) 若k≤n/2,令E是滿足下列條件的Xn的若干個k-子集組成的集合:

A=B或A∩B=?(A,B∈E)，

則|E|≤n/k.

證明(i) 顯然.

引理5設(shè)n,k為正整數(shù).

證明(i) 由于

即

(n-1)(n-2)…(n-k+1)≤k!=k(k-1)…2·1,

故k=n-1.

定理2的證明容易驗證(i)-(iii)及(v)成立.下面驗證Ψπ是同態(tài).設(shè)φ=π-1Ψπ(α)π.則

因此只需證明φ是同態(tài).

其中{x1,…,xn}={y1,…,yn}={z1,…,zn}=Xn，則

由于

因此φ是同態(tài).

其中{x1,…,xn}={y1,…,yn}={z1,…,zn}=Xn.易驗算φ是同態(tài).

dom(φ(α))∩im(φ(β))=?,

進而φ(α)φ(β)=0,因此φ保持運算.

若rank(αβ)=n-1,則α在im(β)上是單的. 設(shè)

則x1和x2只有一個在im(β)中.不妨設(shè)x1∈im(β).設(shè)

經(jīng)驗算知φ保持運算.

反之,設(shè)φ是Tn到PTn的同態(tài).若n=1,則φ(T1)={1n},或φ(T1)={0},因此φ是形式(ii)中的常量同態(tài).

下面討論n>1.考慮三種情形:φ在Sn上是單的;φ在Sn上是非單的且n≠4;φ在Sn上是非單的且n=4.

情形1若φ在Sn上是單的,則由引理3知φ(Sn)=Sn.對任意γ∈Sn,存在η∈Sn使得φ(η)=γ.對任意的a∈Xn, 0aη=0a,進而φ(0a)φ(η)=φ(0a),因此φ(0a)γ=φ(0a),故φ(0a)=0或φ(0a)=0ta,ta∈Xn.

情形1.1設(shè)φ(0a)=0ta,ta∈Xn，映射π:Xn→Xn為π(a)=ta.則φ(0a)=0ta=0π(a).對任意的α∈Tn,α0a=0α(a),進而有

0π(α(a))=φ(0α(a))=φ(α0a)=φ(α)φ(0a)=φ(α)0π(a)=0φ(α)(π(a)),

因此π(α(a))=φ(α)(π(a))，故π(α)=φ(α)(π).

下面證明π是單的.對任意x,y∈Xn,對任意γ∈Sn,γ(x),γ(y)都可取遍Xn.若π(x)=π(y),則

π(γ(x))=φ(γ)(π(x))=φ(γ)(π(y))=π(γ(y)).

因此或者x=y,進而π是單的;或者π是常量映射,進而存在b∈Xn使得π=0b.由于對任意α∈Tn有π(α)=φ(α)(π),因此0bα=φ(α)0b,進而0b=φ(α)0b,由此得φ(α)(b)=b.而φ(α)可取遍Sn,因此Xn=,這與n>1矛盾.

由于π是有限集合上的單射,因此π是雙射，進而π,π-1∈Sn.由于π(α)=φ(α)(π),因此φ(α)=παπ-1=Λπ,故φ∈Aut(Tn).

e2,e3,…,en和f1,f3,…,fn.

由于{φ(ei):i∈I}和{φ(fj):j∈J}都有n-1個元素,因此存在ki∈I,kj∈J使得φ(eki)=φ(fkj).而eki,fkj的值域不同,因此eki,fkj不在≡S2的同一個同余類中,矛盾.故φ不存在.

情形1.2.2若m=n,則φ-1(0)=Tn,這與φ在Sn上是單的矛盾.

情形1.2.3若m=n-1,則φ|Sn是Sn的自同構(gòu)且φ(TnSn)=0.故φ具有形式(ii).

(1)

對任意不同的i,j∈J,記Yij=im(ei)∩im(ej),則im(ej)Yij?Xnim(ei).由于ei,ej在Yij上的限制都是恒等變換,因此它們的積eiej在Yij上的限制也是恒等變換,進而有

φ(eiej)=φ(ei)φ(ej)=0,

于是

dom(φ(ei))∩im(φ(ej))=?.

(2)

|im(φ(e1))|=…=|im(φ(en-1))|=l，

由(2)式可得

下面分兩種情況進行討論.

情況A對任意的i∈J,設(shè)|dom(φ(ei))|=1.則φ(ei)∈{a1,a2,…,an}.從En中選取具有形式(1)的冪等元en,由x的任意性可得φ(en)∈{a1,a2,…,an}，故

{φ(e1),φ(e2),…,φ(en)}={a1,a2,…,an}.

從En中選取冪等元

則有

(3)

下面討論i0,j0的情況.

φ′(πe12π-1)=φ′(e12).

這顯然不成立,矛盾.

這顯然不成立,矛盾.

其中x1,…,xn,z1,z3,…,zn∈Xn.

設(shè)Sn中置換

則α=π2e12π1-1.因此

設(shè)

則

因此φ=πφ′π-1=Ψπ.

若n=6,則S6的自同構(gòu)中有6!個內(nèi)自同構(gòu). 若φ在S6上的限制是S6的內(nèi)自同構(gòu),則同前面證明一樣可證φ=Ψπ.下設(shè)φ在S6上的限制是S6的外自同構(gòu).S6有6!個外自同構(gòu)[5],[6].S6可由生成元(12),(13),(14),(15),(16)生成.定義映射

φ:(12)→(12)(36)(45), (13)→(16)(24)(35), (14)→(13)(25)(46),

(15)→(15)(26)(34), (16)→(14)(23)(56),

則φ是S6的一個外自同構(gòu).S6的外自同構(gòu)集合為{φΛπ:Λπ∈Inn(S6),π∈S6}.設(shè)φ′=φΛπ-1在S6上的限制為φ,φ′(e12)=e0.

對于α∈Tn,定義α的中心化子為集合CSn(α)={π∈Sn:απ=πα}.則

{π∈Sn:π(1)=1,π(2)=2}?CSn(e12).

取{π∈Sn:π(1)=1,π(2)=2}中的任意對換(ij),設(shè)φ′((ij))=(i1i2)(i3i4)(i5i6),其中i,j∈{3,4,5,6}, {i1,i2,i3,i4,i5,i6}=X6.由于(ij)e12=e12(ij),兩邊作用φ′得

(i1i2)(i3i4)(i5i6)e0=e0(i1i2)(i3i4)(i5i6).

(4)

設(shè)rank(e0)=1.若a=1,b,c∈{?},則(4)式無解,矛盾. 同理討論其他情況可知都是不成立的.

情形2φ在Sn上不是單的且n≠4.此時φ具有形式(iii),同[7]中定理證明的情況2討論即可.

情形3φ在Sn上不是單的且n=4.此時φ具有形式(iv),同[7]中定理證明的情況3討論即可.

定理2得證.

從定理2易得