第九章 半群與群(Semigroups and Groups)

1、第九章 半群與群（Semigroups and Groups）本章討論含一個(gè)二元運(yùn)算的特殊的代數(shù)系統(tǒng)半群與群。群論近世代數(shù)中發(fā)展最早、內(nèi)容最豐富、應(yīng)用最廣泛的部分，也是建立其他代數(shù)系統(tǒng)的基礎(chǔ)。群論在自動(dòng)機(jī)政論、形式語(yǔ)言，語(yǔ)法分析快速加法器設(shè)計(jì)、糾錯(cuò)碼制定等方面均有卓有成效的應(yīng)用。 21 半群與含幺半群定義21.1 滿足結(jié)合律的代數(shù)系統(tǒng)U=<S,*>稱為半群。例21.1 <N,+>,<N,×>,<2I+,+>和<2I+,×>都是半群。例21.2 <Nm,+m>和<Nm,×m>都是半群

2、。例21.3 <M2(I),+>和<M2(I),·>都是半群。定義21.2 含幺元e的半群U=<S,*>稱為含幺半群，常記作U=<S,*,e>。在例21.1例21.3中，除<2I+,+>和<2I+,×>外都是含幺半群。例21.4 設(shè)S是任意非空集合，則<p(S),>和<p(S),>都是含幺半群。例21.5 在形式語(yǔ)言中，我們常稱非空有限字符集合為字母表。字母表中字符的n重序元稱為字符串，由m個(gè)字符所組成的字符串稱為長(zhǎng)度為m的字符串。長(zhǎng)度為0的字符串稱為空串，用 來(lái)表示。如對(duì)V=a

3、,b, =aa和=ab都是長(zhǎng)度為2的字符串；=aab和=bab都是長(zhǎng)度為3的字符串。我們用*來(lái)表示兩個(gè)字符串的鄰接運(yùn)算，如,*=aabab,*=aaaab。設(shè)用V*表示字母表V的所有有限長(zhǎng)度字符串的集合，而用V+表示V*- ，則顯然<V+,*>是半群，<V+,*, >是含幺半群。定義21.3 對(duì)運(yùn)算滿足交換律的半群（含幺半群）稱為交換半群（交換含幺半群）。在例21.1例21.3中，除<M2(I),·>外都是交換半群，除<M2(I),·>，<2I+,+>和<2I+,×>外都是交換含幺半群。例21

4、.4的含幺半群也都是交換含幺半群。定義21.4 設(shè)<S,*>是半群（含幺半群），若S中存在一個(gè)元素g，可將S中任意元素a表示成a=gnnÎI+,(nÎN)，則稱<S,*>是循環(huán)半群（循環(huán)含幺半群）,g就稱為是它的生成元。此時(shí)，常將<S,*>記作<g>。注意在含幺半群中，我們規(guī)定任意元素的零次冪為幺元。例21.6 <2I+,+>=<2>是循環(huán)半群。例21.7 <i,-1,-i,1,×>=<i>=<-i>,<N4,+4>=<I>和<

5、1,2,3,4,×5>=<2>=<3>都是循環(huán)含幺半群。可見(jiàn)循環(huán)半群（循環(huán)含幺半群）的生成元不一定是唯一的，但它們一定是可交換的。定理21.1 兩個(gè)半群（含幺半群）的積代數(shù)是半群（含幺半群）。證明 設(shè)<S,*>和<T, >是兩個(gè)半群，其積代數(shù)為<S×T, >。對(duì)S×T中任意三個(gè)元素<s1,t1><s2,t2>和<s3,t3>，因?yàn)?<s1,t1> <s2,t2>) <s3,t3>=<(s1*s2)*s3,(t1 t2) t

6、3>=<s1*(s2*s3),t1 (t2 t3)>=<s1*t1> (<s2,t2> <s3,t3>)故<S×T, >是半群。設(shè)<S,*>和<T, >是兩個(gè)含幺半群，共中幺元分別為es和eT，則顯然<es,eT>是半群<S×T, >的幺元,故<S×T,*>是含幺半群。 很明顯，可交換半群（含幺半群）的積代數(shù)也是可交換的。22 子半群與子含幺半群子含幺半群的概念是子代數(shù)系統(tǒng)概念在（含幺）半群這種代數(shù)系統(tǒng)中的具體體現(xiàn)。定義22.1 設(shè)<

7、S,*>是半群，T是S 的非空子集，若T對(duì)*封閉，則稱<T,*>是半群<S,*>的子半群。定義22.2 設(shè)<S,*,e>是含幺半群，T是S的非空子集，若T對(duì)*封閉，且eÎT，則稱<T,*.e>是含幺半群<S,*,e>的子含幺半群。易知子半群必是半群；子含幺半群必是含幺半群。例22.1 對(duì)任意正整數(shù)m，<mN,´>是半群<N,´>的子半群。例22.2 設(shè)集合S=e,0,1，若在S中規(guī)定二元運(yùn)算*（見(jiàn)表22.1）， * e 0 1 e e 0 10 0 0 01 1 0 1表22

8、.1則<S,*>是含幺半群，從運(yùn)算表可看出<0,1,*>不是<S,*>的子含幺半群。定理22.1 設(shè)T是可交換含幺半群<S,*,e>的等冪元構(gòu)成的集合，則<T,*>是<S,*,e>的子含幺半群。證明 因e2=e，故eÎT，即T非空。又對(duì)T中任意元素a和b，因(a*b)2=(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)=a2*b2=a*b故a*bÎT。這就證明了<T,*>是<S,*,e>的子含幺半群。 23 半群與含幺半群的同態(tài)和同構(gòu)本節(jié)中，

9、將把代數(shù)系統(tǒng)運(yùn)用的同態(tài)與同構(gòu)的概念應(yīng)用于半群（含幺半群），有關(guān)定義與性質(zhì)，幾乎是代數(shù)系統(tǒng)部分的平行照搬。定義2-3.1 設(shè)U=<S,*>和V=<T, >是兩個(gè)半群。若存在映射（滿射，單射，雙射）f: ST，對(duì)S中任意元素a和b，有f(a*b)=f(a) f(b)則稱f是U到V的一個(gè)半群同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）映射或簡(jiǎn)稱同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）。特別U到U（上）的同態(tài)（同構(gòu)）f稱為U的自同態(tài)（自同構(gòu)）。定義23.2 若半群U=<S,*>到V=<T, >存在一個(gè)滿同態(tài)（同構(gòu)），則稱U同態(tài)（同構(gòu)）于V,記作UV(UV)。定義23.3 設(shè)U=&l

10、t;S,*,e>和V=<T, ,eT>是兩個(gè)含幺半群。若存在映射（滿射，單射，雙射）f: S®T，對(duì)S中任意元素a和b，有 f(a*b)=f(a) f(b) f(es)=eT則稱f是U到V的一個(gè)含幺半群同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）映射或簡(jiǎn)稱同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）。特別U到U（上）的同態(tài)（同構(gòu)）f稱為U的自同態(tài)（自同構(gòu)）。定義23.4 若含幺半群U=<S,*,es>到V=<T, ,eT>存在一個(gè)滿同態(tài)（同構(gòu)），則稱U同態(tài)（同構(gòu)）于V，記作UV(UV)。例23.1 我們已知例21.1中的U=<N,+>是半群（也是含幺半群）。易知

11、N到S的映射是半群U到V的同態(tài)。但不是含幺半群U到V的同態(tài)。例23.2 對(duì)半群（含幺半群）U<N,+>和V<M4,+4>,N到M4的映射f: a®a(mod 4)即是半群U到V的同態(tài)，也是含幺半群U到V的同態(tài)。24 群對(duì)子群再附加一些性質(zhì)就可成為群。群是代數(shù)“系統(tǒng)中研究得比較完美的一類，目前已有許多群的專著。在計(jì)算機(jī)科學(xué)中，群在快速加法器設(shè)計(jì)和糾錯(cuò)碼理論等方面有廣泛應(yīng)用。定義24.1 每個(gè)元素都有逆元的含幺半群U<G,*>稱為群。若群還滿足交換律，則稱為交換群或阿貝爾群。也就是說(shuō)，設(shè)U=<G,*>是代數(shù)系統(tǒng)，若滿足：1） 對(duì)G中任意元素

12、a,b和c，有 (a*b)*c=a*(b*c)2） 在G中存在元素e，對(duì)G中任意元素a，使 c*a=a*e=a3） 對(duì)G中任意元素a，在G中存在元素a-1，使 a-1*a=a*a-1=e則稱U=(G,*)為群。若還滿足4） 對(duì)G中任意元素a和b，有 a*b=b*a則稱U=<G,*>為交換群或阿貝爾群。由定義24.1，定理11.1和定理11.4知群中的幺元和每個(gè)元素的逆元都是唯一的。且對(duì)群中任意元素a1,a2,am必有。由定理11.3知除單個(gè)元素構(gòu)成的群外，群無(wú)零元。還應(yīng)注意，含幺半群中的等冪元不一定是唯一的，但群中的等冪元卻一定是唯一的，即只有幺元一個(gè)。例24.1 <I,+&

13、gt;,<Q,+>,<R,+>,<C,+>,<Q*,×>,<R*,×>和<C*,×>都是交換群。例24.2 <Nm,+m>和<Rx,+>都是交換群，其中Rx表示所有實(shí)系數(shù)多項(xiàng)式的集合。顯然，由定義24.1知，給空集合G，和其上的二元運(yùn)算A，<G,*>能構(gòu)成群的判定過(guò)程如下：（1） 驗(yàn)證*運(yùn)算的封閉性（2） 驗(yàn)證*運(yùn)算的可結(jié)合性（3） 驗(yàn)證題$eÎG,"xÎG有e*x=x*e=x（4） 驗(yàn)證"xÎG,$x-1&

14、#206;G使x*x-1=x-1*x=e上述四個(gè)步驟中至少一個(gè)步驟的驗(yàn)證不成立,<G,*>都不是群。定理24.1 半群<G,*>是群的充要條件為存在左（右）幺元e1(er)，且每個(gè)元素對(duì)此左（右）幺元具有左（右）逆元。證明 必要性是很明顯的。充分性，只證“左”的情況（“右”的情況完全類似），對(duì)G中任意元素a，設(shè)其左逆元為則因在此式兩邊左“乘” 的左逆元，可得即 也是a的右逆元。又因 即e1也是右幺元。故由定理1-1.1和定理1-1.4知e1=e， 可見(jiàn)<G,*>是群。 這個(gè)定理說(shuō)明群定義中的條件可以削弱。定理24.2 代數(shù)系統(tǒng)<G,*>是群的充要

15、條件為1)對(duì)G中任意元素a,b和c，有(a*b)*c=a*(b*c)2）對(duì)G中任意元素a和b，方程a*x=b和y*a=b都有解。證明 必要懷是很明顯的。實(shí)際上，x=a-1*b和y=b*a-1就是2）中方 程的（唯一）解。充分性：對(duì)G中任意元素a和b，設(shè)方程b*x=a的解為 d，方程y*b=b的解為e，則有e*a=e*(b*d)=(e*b)*d=b*d=a，即e是左幺元。又方程y*a=e的解是a的左逆元。故由定理24.1知<G,*>是群。 定理24.3 若<G,*>是群，則對(duì)*滿足消去律。證明 設(shè)a*b=a*c或b*a=c*a，則在等式兩邊左“乘”或右“乘” a-1即得b

16、=c。 定理24.4 有限半群<G,*>是群的充要條件為對(duì)*滿足消去律。證明 必要性由定理24.3即得。充分性：由于有限半群<G,*>滿足消去律，可見(jiàn)其運(yùn)算表中的每行（列）都是G中元素的不同排列，故對(duì)G中任意元素a和b，方程a*x=b和y*a=b都有解。由定理2-4.2即知<G,*>是群。 我們知道，在半群（含幺半群）中可定義元素的正整數(shù)（非負(fù)整數(shù)）次冪的概念，且相應(yīng)的指數(shù)律成立。而在群中則可定義元素的整數(shù)次冪的概念。定義24.2 設(shè)<G,*>是幺元為e的群，則對(duì)G中任意元素a和任意正整數(shù)m，可規(guī)定a0=e利用數(shù)學(xué)歸納法，易證對(duì)群中任意元素的整數(shù)

17、次冪，其指數(shù)律也成立。定義24.3 設(shè)<G,*>是群，其幺元為e，則稱為群<G,*>的階。而稱為群<G,*>中元素a的階。定義24.4 n階有限集合S=a1,a2,an到S的雙射P稱為S的n次置換，常記作其中P(ak)=aik,k=1,2,，n。置換中列的次序顯然無(wú)關(guān)緊要。置換中兩行逆序的和若是偶（奇）數(shù)，則稱這種置換為偶（奇）置換。對(duì)n次置換Pi和Pj，規(guī)定PiPj=PjPi，其中是映射的合成。如設(shè)則PiPj=可以證明 偶置換偶置換=偶置換 偶置換奇置換=奇置換 奇置換偶置換=奇置換 奇置換奇置換=偶置換對(duì)二元運(yùn)算，我們將某些n次置換的集合構(gòu)成的群稱為n次

18、置換群。特別，將所有n次置換的集合（其元素共n!個(gè)）構(gòu)成的群稱為n次對(duì)稱群，記作<Sn, >將所有n次偶置換的集合（其元素共個(gè)）構(gòu)成的群稱為n次交代群，記作<An, >，這兩個(gè)結(jié)論請(qǐng)讀者自行證之。例24.3 設(shè)S=1,2,3，則所有3次置換為運(yùn)算表為 P1 P2 P3 P4 P5 P6P1 P1 P2 P3 P4 P5 P6P2 P2 P1 P5 P6 P3 P4P3 P3 P6 P1 P5 P4 P2P4 P4 P5 P6 P1 P2 P3P5 P5 P4 P2 P3 P6 P1P6 P6 P3 P4 P2 P1 P5表24.1可見(jiàn)<P1,P2,>,<

19、;P1,P3,>和<P1,P4,>等都是3次置換群。 <S3, >是3次對(duì)稱群，其中S3=P1,P2,P3,P4,P5,P6。<A3,>是3次交代群，其中A3=P1,P5,P6。定義24.5 設(shè)<G,*>是群，若G中存在一個(gè)元素g，可將G中任意元素a表示成a=gn，nÎI，則稱<G,*>是循環(huán)群，g就稱為是它的生成元，此時(shí)，常將<G,*>記作<g>。定理24.5 設(shè)<G,*>=<g>是循環(huán)群。1） 若|G|=n，則G=g0,g1,g2,gn-1。2） 若|G|=，則G=,

20、g-2,g-1,g0,g1,g2,。證明 對(duì)于1），有a) g1,g2,gn-1都不等幺元e：用反證法。若gm=e,0mn,則對(duì)于G中任意元素gk。可設(shè)k=qm+r 0rm，故必有g(shù)k=gqm+r=(gm)q*gr=eq*gr=gr可見(jiàn)G中至多有m個(gè)元素，這與|G|=n矛盾。b) g1,g2,gn-1,gn都互不相等；用反證法。若gi=gj 1ijn，則有g(shù)j-i=e 0j-in，這與a)的結(jié)論矛盾。故由a),b)的結(jié)論和|G|=n，得gn=g0=e，即1）的結(jié)論成立。對(duì)于2），顯然g-2,g-1,g0,g1,g2,也都互不相等，因而2）的結(jié)論成立?？梢?jiàn)n階有限循環(huán)群生成元的階為n，而無(wú)限循環(huán)

21、群生成元的階為。 定理 24.6 兩個(gè)群的積代數(shù)是群。證明 設(shè)<G,*>和<H, >是兩個(gè)群，其幺元分別為eG和eH，其積代數(shù)為<G×H, >，由定理21.1知<G×H, >是含幺半群，其幺元為<eG,eH>。又G×H中任意元素<g,h>有逆元<g-1,h-1>，故<G×H, >是群。 實(shí)際上，可以定義兩個(gè)以上群的積代數(shù)，產(chǎn)生更高階的群的積代數(shù)，本文從略。25 子群與陪集子群在群論中的地位，與子半群機(jī)子含幺半群在半群中的地位相似。定義25.1 設(shè)<G,*

22、>是群，e是其幺元，S是G的非空子集，若對(duì)S中任意元素a和b，有1) a*bÎS2) a-1ÎS3) eÎS 則稱<S,*>是群<G,*>的子群。可見(jiàn)子群必是群，且其幺元與原群幺元一致。<e,*>和<G,*>都是群<G,*>的子群，這種子群常稱為平凡子群。非平凡子群稱為真子群。設(shè)a是群<G,*>中的任意元素，H=ai|iÎI，則<H,*>也是群<G,*>的一個(gè)子群，稱為由元素a生成的子群。還應(yīng)注意，定義25.1中的條件3）實(shí)際上是多余的。這是因?yàn)镾是非空

23、集合，故必存在元素d，從而由條件1）和2）可得出e=d*d-1ÎS。例25.1 <Q+,×>不是群<Q,+>的子群，因?yàn)樗鼈兊亩\(yùn)算不同。 例25.2 <I*,×>不是群<Q*,×>的子群。例25.3 <2I,+>是群<I,+>的子群。例25.4 在例24.4中，<P1,P2,>,<P1,P3,>,<P1,P4,>和<A3, >都是3次對(duì)稱群<S3, >的子群。定理25.1 設(shè)<G,*>是群，S是G的非空子集，

24、則<S,*>是子群的充要條件為對(duì)S中任意元素a和b，有a*b-1ÎS。證明 必要性是很明顯的。充分性：設(shè)群<G,*>中的幺元為e，因?yàn)镾是非空集合，故必存在元素d，從而e=d*d-1ÎS，由此對(duì)S中任意元素a和b有a-1=e*a-1ÎS，由此又有a*b=a*(b-1)-1ÎS。根據(jù)定義2-5.1即知<S,*>是群<G,*>的子群。 這個(gè)定理是判斷群的非空子集是否構(gòu)成子群的一個(gè)方法。定理25.2 循環(huán)群的子群必為循環(huán)群。 證明 設(shè)<G,*>=<g>是循環(huán)群，<H,*>是其子

25、群，則必存在最小正整數(shù)m使gmÎH。對(duì)H中任意元素gk，令k=gm+r 0rm，就有g(shù)r=gk-qm=gk*(gm)-qÎH，從而r=0，故gk=(gm)q，即<H,*>=<gm>。 定義25.2 設(shè)<H,*>是群<G,*>的子群。對(duì)G中任意元素a和b，在G中定義二元關(guān)系： L ab(mod H)Ûb-1*aH R(ab(mod H)Ûa*b-1H)稱為群<G,*>對(duì)子群<H,*>的左（右）陪集關(guān)系或簡(jiǎn)稱模H的左（右）陪集關(guān)系。我們證明模H的左（右）陪集關(guān)系是G中的等價(jià)關(guān)系。1） 對(duì)

26、G中任意元素a，因a-1*a=e，故aa(mod H)；2） 對(duì)G中任意元素a和b，若ab(mod H)，則b-1*aH，從而a-1*b=(b-1*a)-1 H，故ba(mod H)；3） 對(duì)G中任意元素a,b和c，若ab(mod H)，bc(mod H),則b-1*aH，c-1*bH，從而c-1*a=(c-1*b)*(b-1*a)H，故。ac(mod H)由1），2）和3）知模H的左陪集關(guān)系是G中的等價(jià)關(guān)系。同理可證模H的右陪集關(guān)系也是G中的等價(jià)關(guān)系。這樣一來(lái)，模H的左（右）陪集關(guān)系將G劃分成一些等價(jià)類： La=x|xG,xa(mod H)=x|xG,a-1*xH =a*h|hH=aH R等

27、價(jià)類aH(Ha)稱為代表元素為a的群<G,*> 關(guān)于子群<H,*>的左（右）陪集或簡(jiǎn)稱子群<H,*>的左（右）陪集。由集合中等價(jià)類的性質(zhì)知任意兩個(gè)左（右）陪集或相等或者其交為空集。當(dāng)然，一般來(lái)說(shuō)aHHa。但對(duì)任意兩個(gè)左陪集aH和bH，均有|aH|=|bH|=|H|，對(duì)任意兩個(gè)右陪集也一樣。設(shè)所有左（右）陪集構(gòu)成的集為S1(Sr)，則也有|Sl|=|Sr|。例25.5 設(shè)集合H=0,2，則<H,+4>是交換群<M4,+4>的子群，<H,+4>的左、右陪集為0 H=2H=H0=H2=0,21 H=3H=H1=H3=1,3例25

28、.6 設(shè)集合H=P1,P2，則<H,>是3次對(duì)稱群<S3,>的子群,<H, >的左陪集為P1H=P2H=P1,P2P3H=P6H=P3,P6P4H=P5H=P4,P5而右陪集為HP1=HP2=P1,P2HP3=HP5=P3,P5HP4=HP6=P4,P6可見(jiàn)P3HHP3,P4HHP4,即H的左陪集不同于它的右陪集。定理 25.3 （拉格朗日Lagrange）有限群的子群的階必能整除該群的階。證明 設(shè)<H,*>是n階有限群<G,*>的m階子群,<H,*>的左陪集個(gè)數(shù)為K。因n=km,故m|n。 推論1 素?cái)?shù)階的群只有平凡子群

29、。推論2 對(duì)n階有限群<G,*>中的任意元素a，必有an=e,e是群<G,*>中的幺元。證明 設(shè)<H,*>是由a生成的m階循環(huán)子群，則am=e，再由定理25.3知m|n，即n=km，故an=(am)k=ek=e。 定義25.3 設(shè)<H,*>是群<G,*>的子群，若對(duì)G中任意元素a，有aH=Ha，則稱<H,*>為正規(guī)子群或不變子群。當(dāng)<H,*>是群<G,*>的正規(guī)子群時(shí)，其左陪集或右陪集可稱為陪集。模H的左陪集關(guān)系或右陪集關(guān)系可稱為模H的陪集關(guān)系，記作。交換群的每個(gè)子群當(dāng)然都是正規(guī)子群。但應(yīng)注意，aH

30、=Ha并不意味著對(duì)H中任意元素h均有a*h=h*a，而是對(duì)h，在H中必存在元素h1和h2，使a*h=h1*a和a*h2=h*a成立。定理25.4 設(shè)<H,*>是群<G,*>的子群，則<H,*>是正規(guī)子群的充要條件為對(duì)G中的任意元素a和H中任意元素h，有a-1*h*aH。證明 必要性：因h*aHa=aH，故H中存在元素h，使h*a=a*h，從而a-1*h*a=hH。充分性：設(shè)h1*a是Ha中的任意元素，由所給條件知a-1*h1*a=h2H，故h1*a=a*h2aH，即HaÍaH。同理可證aHÍHa。從而aH=Ha，即<H,*>是

31、正規(guī)子群。 由定理25.1和定理25.4可得下面定理。定理25.5 設(shè)<G,*>是群，H是G中的非空子集，則<H,*>是正規(guī)子群的充要條件為對(duì)H是任意元素h,h1和G中任意元素a，有且a-1*h*aH。這個(gè)定理是判斷群的非空子集是否構(gòu)成正規(guī)子群的一個(gè)方法。如例25.4中的子群，只有3次交代群<A3,>是3次對(duì)稱群<S3,>的正規(guī)子群。例25.7 對(duì)任意正整數(shù)m，<mI,+>是群<I,+>的正規(guī)子群，且其所有陪集恰好就是集合Mm=0,1,m-1的所有元素。我們證明，若<H,*>是群<G,*>的正規(guī)子群

32、，則模H的陪集關(guān)系是同余關(guān)系。前面已經(jīng)知道是等價(jià)關(guān)系。又若ap(mod H)，bq(mod H) ，即p-1*a=h1H，q-1*b=h2H,則由<H,*>是正規(guī)子群，在H中必存在元素h3，使h1*b=b*h3，從而(p*q)-1*(a*b)=(q-1*p-1)*(a*b)=q-1*(p-1*a)*b=q-1*h1*b=q-1*b*h3=h2*h3H，故a*bp*q(mod H)。這就證明了是同余關(guān)系。定義25.4 設(shè)<H,*>是群<G,*>的正規(guī)子群，因?yàn)槟的陪集關(guān)系是同余關(guān)系，故可在商集G/（常記作G/H）中規(guī)定相應(yīng)的運(yùn)算*。(aH) *(bH)=(a

33、*b)H從而<G/H, *>是群，稱為群<G,*>關(guān)于正規(guī)子群<H,*>的商群。例25.8 3次對(duì)稱群<S3, >關(guān)于3次交代群<A3, >的商群為<S3/A3, >，其中S3/A3=A3,B3A3=P1,P5,P6B3=P2,P3,P4 A3 B3A3 A3 B3B3 B3 A3表25.126 群的同態(tài)與同構(gòu)將代數(shù)系統(tǒng)同態(tài)與同構(gòu)的概念應(yīng)用到群，便可得出群的同態(tài)與同構(gòu)的定義。定義26.1 設(shè)U=<G,*>和V=<H, >是兩個(gè)群。若存在映射（滿射，單射，雙射）f: GH，對(duì)G中任意元素a和b，有f(

34、a*b)=f(a) f(b)則稱f是U到V的一個(gè)群同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）映射或簡(jiǎn)稱同態(tài)（滿同態(tài)，單同態(tài)，同構(gòu)）。特別U到U（上）的同態(tài)（同構(gòu)）f稱為U的自同態(tài)（自同構(gòu)）。設(shè)eG和eH分別是群U=<G,*>和V=<H, >的幺元，f是U到V的同態(tài)，因群中唯一的等冪元是幺元，故由f(eG) f(eG)=f(eG*eG)=f(eG)，可得f(eG)=eH。因f(a-1) f(a)=f(a-1*a)=f(eG)=eH，同理f(a) (a-1)=eH，可得f(a-1)=(f(a)-1。 定義26.2 若群U=<G,*>到<H, >存在一個(gè)滿同態(tài)（同構(gòu)

35、），則稱U同態(tài)（同構(gòu)）于V，記作UV(UV)。例26.1 f(a)=2不是群<Q,+>到<I,+>的同態(tài)。例26.2 f(<a,b>)=a+2b是群到<I,+>的滿同態(tài)，故例26.3 群<M4,+4>和<G,´>，其中G=1,-1,i,-i且i2=-1,<G,´>的運(yùn)算表如下： ´ 1 -1 i -i 1 1 -1 i -i-1 -1 1 -i i i i -i -1 1-i -i i 1 -1表26.1定義雙射 f: 01 1i 2-1 3-i則<M4,+4><

36、G,´>。例26.4 f(a)=|a|不是群<R,+>的自同態(tài)，但卻是群<R*,´>的自同態(tài)。例26.5 由運(yùn)算表可看出雙射01 f: 12 24 33是群<M4,+4>到<M5*,×5>的同構(gòu)，故<M4,×4><M5*,×5>。定理26.1 設(shè)<G,*>和<H, >是同型的代數(shù)系統(tǒng)，其中<G,*>是群，若存在滿射f: GH，對(duì)G中任意元素a和b，有f(a*b)=f(a) f(b)則<H, >也是群。證明 由定理12.2

37、的2），5），6）即得結(jié)論。 類似地，可象代數(shù)系統(tǒng)的同態(tài)基本室理一樣，平行地引出有關(guān)群的同態(tài)基本室理。（有興趣的讀者請(qǐng)參閱離散數(shù)學(xué)許華康 楊留記 西北大學(xué)出版社，1994）習(xí) 題2.1 試給出一個(gè)半群，它含有左幺元和右零元，但它不是含幺半群。2.2 給定代數(shù)系統(tǒng)U=<N,*>，其中二元運(yùn)算*定義如下：1）x*y=minx,y2）x*y=maxx,y對(duì)每種情況，U是否為半群？是否為含幺半群？2.3 設(shè)<S,*>是半群，取定aS，在S中定義新的二元運(yùn)算 為x y=x*a*y試確定<S, >是否為半群。2.4 給定半群<S,*>。試證，對(duì)S中任意元素a

38、,b和c，若a*c=c*a和b*c=c*b，則(a*b)*c=c*(a*b)。2.5 給定交換半群U=<S,*>。試證，若a和b是U中的等冪元，則a*b也是U中的等冪元。2.6 給定代數(shù)系統(tǒng)U=<R,*>，R是實(shí)數(shù)集合，"a,bÎR，定義*運(yùn)算如下：a*b=a+b+a´b試證明 <R,*>是含幺半群2.7 給定代數(shù)系統(tǒng)U=<Ss,o>，其中S=a,b，Ss是S中所有映射的集合，而o是映射的合成。U是否為含幺半群？是否為可交換含幺半群？2.8 給定代數(shù)系統(tǒng)U=<S,*>，其中S=a,b,c,d，運(yùn)算表為*

39、a b c da a b c db b c d ac c d a bd d a b c1） 試證U是一個(gè)循環(huán)含幺半群。2） 試求U的所有生成元和等冪元。2.9 試證，每個(gè)有限半群都有等冪元。2.10 給定代數(shù)系統(tǒng)U=<S,*>，其中S=a,b,c,d,運(yùn)算表為* a b c da c b a db b b b bc a b c dd d b d d1） U是否為循環(huán)含幺半群？2） 試求U的生成集合。2.11 給定字母表V=a,b，設(shè)S是所有以a開(kāi)始的有限字符串且包含空串 的集合，o是字符串的鄰接運(yùn)算。試證<S,o, >是含幺半群。2.12 給定兩個(gè)含幺半群U=<p

40、(X),>和V=<p(X),>其中X是任意集合， 和是通常集合的交和并。試求U和V的零元。2.13 設(shè)Z是半群U<S,*>的左零元。試證，對(duì)S中任意元素x，x*z也是半群U的左零元。2.14 給定兩個(gè)半群U=<S,*>和V=<T, >，f: ST是U到V的同構(gòu)。試證，若z是U的零元，則f(z)是V的零元。2.15 設(shè)a是半群U=<S,*>中的一個(gè)元素，對(duì)U中任意元素x和y，要是a*x=a*y(x*a=y*a)，就有x=y，則稱在U中a是左（右）可約的。試證，在U中若元素a和b都是左（右）可約的，則a*b也是左（右）可約的。2.1

41、6 試證，含幺半群的左（右）可逆元素的集合，能構(gòu)成一個(gè)子含幺半群。2.17 試求含幺半群U<N6,×6>的所有子半群。并舉出U的一個(gè)子半群，它是含幺半群，但不是U的子含幺半群。2.18 給定含幺半群U=<I,×,1>，其中×是通常數(shù)的乘法。試證：<0,×>是U的子半群，但不是子含幺半群。算*分別定義如下：1) S=1,3,4,5,9,*是模11乘法。2) S=Q,*是通常數(shù)的加法，3) S=Q,*是通常數(shù)的乘法。4) S=I,*是通常數(shù)的減法，5) S=a,b,c,d，運(yùn)算表為* a b c da b d a cb d

42、 c b ac a b c dd c a d b6) S=a,b,c,d，運(yùn)算表為* a b c da a b c db b a d cc c d a ad d c b b對(duì)每種情況，試確定U是否為群，若U是群，則指出它的幺元和每個(gè)元素的逆元。2.20 設(shè)U=<G,*>是一個(gè)具有幺元e的群，試證，若G的任意元素a都有a2=e(或a-1=a)，則U必是交換群。2.21 試證，若<G,*>是交換群，而n是任意整數(shù)，則對(duì)于G的任意元素a和b，必有(a*b)n=an*bn。2.22 給定群U=<G,*>。試證，U是交換群當(dāng)且僅當(dāng)對(duì)G中任意元素a和b，有a2*b2=(

43、a*b)2。2.23 給定群U=<G,*>。試證，若對(duì)G中任意元素a和b，有a3*b3=(a*b)3 a4*b4=(a*b)4 a5*b5=(a*b)5則U是交換群。2.24 給定兩個(gè)群U=<1,×>和V=<1,-1,×>，其中×是通常數(shù)的乘法，試證，對(duì)×，U和V是僅有的非零實(shí)數(shù)構(gòu)成的有限群。2.25 給定群U=<Nm,+m>。試證，當(dāng)且僅當(dāng)d是U中一個(gè)元素的階時(shí)，d才是m的一個(gè)因數(shù)。2.26 給定代數(shù)系統(tǒng)<K,*>其中K=e,a,b,c，運(yùn)算表為* e a b ce e a b ca a e

44、c bb b c e ac c b a e試證，<K,*>是群（稱克萊因(KIein)四元群），但不是循環(huán)群。2.27 試用例24.4中對(duì)稱群<S3,>的運(yùn)算表，求出其中哪些元素a和b，能使1）(ab)2a2b22）a2=e3）a3=e這里e表示對(duì)稱群<S3, >中的幺元。2.28 給定集合S=1,2,3,4,5和其置換試求出ab,ba,a2,cb,d-1和abc。并解置換方程ax=b。2.29 試求出<N5,+5>和<N12,+12>的所有子群。2.30 試求出不是正四邊形的四邊形二面體群。并證這個(gè)群是例24.6中正四邊形二面體群&

45、lt;D4, >的子群。2.31 給定<G,*>，令H=x|xG,對(duì)aG,x*a=a*x。試證<H,*>是群<G,*>的子群。2.32 設(shè)p為素?cái)?shù)。試證，pm階群中一定有p階子群。2.33 設(shè)<S,*>和<T,*>是群<G,*>的s階和t階子群，且|ST|=，|ST|=。試證st。2.34 設(shè)<H1,*>和<H2,*>是群<G,*>的兩個(gè)互不包含的子群，試證，G中存在元素，它既不屬于H1，也不屬于H2。2.35 設(shè)<G,*>是偶數(shù)階有限群，其幺元為e，試證，在G中存在元素ae，使a2=e。2.36 設(shè)<G,*>是群，H是G的一個(gè)子集，且2|H|G|。試證，對(duì)G中任意元素a，在H中必存在元素b1和b2，使a=b1*b2。2.37 設(shè)f和g都是群U=<G1,*>到V=<G2, >的同態(tài)，令H1=x|xG1,f(x)=g(x