離散數(shù)學(xué)第六章代數(shù)系統(tǒng)2-1st

1、1/30第六章 代數(shù)系統(tǒng)2/30回顧同余定義定義性質(zhì)商代數(shù)定義性質(zhì)積代數(shù)定義性質(zhì)3/30第二部分： 半群與群6.7 半群和獨(dú)異點(diǎn)的定義及性質(zhì)定義6.7.1 給定，若滿足結(jié)合律，則稱為半群?？梢?，半群就是由集合及其上定義的一個(gè)可結(jié)合的二元運(yùn)算組成的代數(shù)結(jié)構(gòu)。定義6.7.2 給定，若是半群且有幺元或滿足結(jié)合律且擁有幺元，則稱為獨(dú)異點(diǎn)。可以看出，獨(dú)異點(diǎn)是含有幺元的半群。因此有些著作者將獨(dú)異點(diǎn)叫做含幺半群。有時(shí)為了強(qiáng)調(diào)幺元e，獨(dú)異點(diǎn)表為。4/30例6.7.1 給定和，其中N為自然數(shù)集合，+和為普通加法和乘法。易知和都是半群，而且還是獨(dú)異點(diǎn)。因?yàn)?是+的幺元，1是的幺元。如果半群中的集合S是有限的，則稱

2、半群為有限半群。對(duì)于有限半群可以給出下面有趣定理：5/30定理6.7.1 為有限半群(x)(xSxx=x)本定理告訴我們，有限半群存在等冪元。證明：因?yàn)槭强山Y(jié)合的，所以對(duì)任意的xS有xx=x2 S （封閉性）x2 x=x S因?yàn)镾是有限集，必存在ji使得 xj=xi 6/30令p=j-i,則xj= xi= xp xi (1)所以，對(duì)于qi有xq= xp xq因?yàn)閜1,故總有k 1,使得kpi.對(duì)于xkpS,則由(1)有 xkp = xp xkp = xp (xp xkp ) = x2p xkp = = xkp xkp 因此，存在y= xkp S,使得y y=y即y是等冪元 7/30定義6.7.

3、3 給定半群，若是可交換的，則稱是可交換半群。類似地可定義可交換獨(dú)異點(diǎn)。例6.7.2 給定和，其中P(S)是集合S的冪集，和為集合上的并與交運(yùn)算。可知和都是可交換半群。不僅如此，它們還都是可交換獨(dú)異點(diǎn)，因?yàn)榕cS分別是它們的幺元。8/30定義6.7.4 給定半群和gS，以及自然數(shù)集合N，則g為的生成元：(x)(xS(n)(nNx = gn)此時(shí)也說，元素g生成半群，而且稱該半群為循環(huán)半群。類似地定義獨(dú)異點(diǎn)M，e)的生成元g和循環(huán)獨(dú)異點(diǎn)，并且規(guī)定g0=e。定理6.7.2 每個(gè)循環(huán)獨(dú)異點(diǎn)都是可交換的。將生成元的概念加以推廣便得出生成集的概念。9/30定義6.7.5 給定半群及GS，則G為的生成集：(

4、a)(aSa=(G)min|G| GS這里(G)表示用G中的元素經(jīng)的復(fù)合而生成的元素。類似地定義獨(dú)異點(diǎn)的生成集。例6.7.3 給定，其中N是自然數(shù)集合，+為普通加法，則是無窮循環(huán)獨(dú)異點(diǎn)，0是幺元，1是生成元。10/30例6.7.4 令半群，其中S=a，b，c，d，定義如表6.7.1，試證明生成集G = a，b 表6.7.1 a b c d a d c b a b b b b b c c c c c d a b c d11/30解：由表6.7.1可以看出： a1=a b1=b aa=a2=d ab=c即集合a,b可以生成集合a,b,c,d. 12/30定義6.7.6 給定半群及非空集合TS，若T

5、對(duì)封閉，則稱為的子半群。類似地定義獨(dú)異點(diǎn)的子獨(dú)異點(diǎn)，應(yīng)注意的是eP。定理6.7.3 給定半群及任意aS，則是循環(huán)子半群。證明：因?yàn)槭前肴?，所以，?duì)任意aS, aaS(封閉性)即a2 S,于是a2aS ,ai S , iZ+即a，a2，a3， S,并且a是生成元，13/30于是是循環(huán)子半群定理6.7.4 給定可交換獨(dú)異點(diǎn)，若P為其等冪元集合，則為子獨(dú)異點(diǎn)。證明：eP是明顯的，令a,b P,則有aa P和bbP于是有 (ab)(ab)= (ab)(ba) = a(bb)a = aba =(aa)b =abP即對(duì)是封閉的，得證14/30定理6.7.5 設(shè)為獨(dú)異點(diǎn)，則關(guān)于的運(yùn)算表中任兩列或任兩行均不相

6、同。證明：因?yàn)閷?duì)任意的a,bM且ab時(shí)，總有e a=a b=e b和ae=a b=b e因此在的運(yùn)算表中不可能有兩列和兩行是相同的15/30定理6.7.6 給定獨(dú)異點(diǎn)，對(duì)任意a，bM且a，b均有逆元，則(1) (a -1) -1 = a。(2) ab有逆元，且(ab) -1 = b -1a -1。16/306.8 半群和獨(dú)異點(diǎn)的同態(tài)與同構(gòu)定義6.8.1 給定兩個(gè)半群與，則 ：(f )(fTS(x)(y)(x，yS f(xy)= f(x)*f(y)并稱f為從到的半群同態(tài)映射。由定義可以知道，半群同態(tài)映射f可以不是惟一的。17/30與前面定義類似，根據(jù)半群同態(tài)映射f是單射(一對(duì)一)、滿射、雙射，把

7、半群同態(tài)映射f分別定義半群單一同態(tài)映射、半群滿同態(tài)映射和半群同構(gòu)映射。如果兩個(gè)半群，存在一個(gè)同構(gòu)映射，則稱一個(gè)半群同構(gòu)于另一個(gè)半群。由于代數(shù)結(jié)構(gòu)之間的滿同態(tài)具有保持運(yùn)算的各種性質(zhì)，對(duì)于半群滿同態(tài)當(dāng)然完全適用。18/30下面給出一個(gè)半群同態(tài)保持等冪性的定理。定理6.8.1 如果f為從到的半群同態(tài)映射，對(duì)任意aS且aa = a，則f(a) *f(a)= f(a)。證明：因?yàn)閷?duì)任意aS且aa = a而f是同態(tài)映射，即有f(aa)=f(a)= f(a)* f(a),即等冪性保持 19/30由于半群同態(tài)映射是個(gè)函數(shù)，因此可對(duì)半群同態(tài)映射進(jìn)行復(fù)合運(yùn)算，從而產(chǎn)生新的半群同態(tài)映射。請(qǐng)看如下定理：定理6.8.2

8、 如果g是從到的半群同態(tài)映射，h是從到的半群同態(tài)映射，則hg是從到的半群同態(tài)映射。證明：對(duì)任意x,yS,有(hg)(xy)=h(g(xy) /*g TS且是同態(tài) =h(g(x) g(y)=h(g(x)*h(g(y) /*h ut且是同態(tài) 即(hg) us 且是同態(tài) 20/30定義6.8.2 若g是從到的半群同態(tài)映射，則稱g為半群自同態(tài)映射；若g是從到的半群同構(gòu)映射，則稱g為半群自同構(gòu)映射。定理6.8.3 給定半群，如果A=g| g為到的半群自同態(tài)映射且是函數(shù)復(fù)合運(yùn)算，則為半群。該定理是明顯的，由前一個(gè)定理知在上是封閉的，函數(shù)的復(fù)合運(yùn)算是可結(jié)合的21/30由于恒等映射idA是復(fù)合運(yùn)算的幺元，因此

9、可得下面定理：定理6.8.4 給定半群，若B=h|h為到的半群自同構(gòu)映射，為函數(shù)復(fù)合運(yùn)算，則是獨(dú)異點(diǎn)。定理6.8.5 給定半群，又是從S到S的所有函數(shù)在復(fù)合運(yùn)算下構(gòu)成的函數(shù)半群，則存在從到的半群同態(tài)映射g，或者說半群同態(tài)于。但該函數(shù)是射入的22/30例6.8.1 給定半群，其中S=a，b，c，定義由表6.8.1所示。今定義g(SS)S，g(a)= fa， g(b)= fb， g(c)= fc，這里fa，fb，fcSS，并且fa(a)= a fa(b)= b fa(c)= cfb(a)= b fb(b)= c fb(c)= afc(a)= c fc(b)= a fc(c)= b顯然，SS中有33

10、 = 27個(gè)元素，且是獨(dú)異點(diǎn)。根據(jù)定理6.8.5可知，g是從到的半群同態(tài)映射。23/30表6.8.1 a b c a a b c b b c a c c a b上面介紹半群同態(tài)及有關(guān)定理。接著討論獨(dú)異點(diǎn)之間的同態(tài)及其有關(guān)定理。24/30定義6.8.3 給定獨(dú)異點(diǎn)和，則：(g)(gTM(x)( y) (x，yMg(xy)= g(x)*g(y)g(eM)= eT)并稱g為從到的獨(dú)異點(diǎn)同態(tài)映射。注意，獨(dú)異點(diǎn)同態(tài)區(qū)別半群同態(tài)就在于保持幺元，即g(eM)= eT。因此，半群同態(tài)未必是獨(dú)異點(diǎn)同態(tài)，反之都真。25/30例6.8.2 給定獨(dú)異點(diǎn)和，其中N為自然數(shù)集合，+為一般加法，0為幺元，S = e，0，1

11、，*定義如表6.8.2，e為幺元，又有映射gSN： 0 i0g(i)= 1 i=0試問g是否為到的獨(dú)異點(diǎn)同態(tài)映射？26/30表6.8.2 * e 0 1 e e 0 1 0 0 0 0 1 1 0 1證明：對(duì)任何i,j N和i 0,j 0i+j 0,于是有g(shù)(i+j)=0 g(i)+g(j)=0滿足運(yùn)算的象等于象的運(yùn)算，但是g(0)=1e,所以g不是獨(dú)異點(diǎn)同態(tài)映射27/30例6.8.3 給定獨(dú)異點(diǎn)和，其中R是實(shí)數(shù)集合，+和是一般加法和乘法，0和1分別為它們的幺元。令fRR:f(x)= ax 其中a0，xR問f是否為從到的獨(dú)異點(diǎn)同態(tài)映射？證明：因?yàn)閷?duì)任何x,yR, f(x+y)= ax+y= f(x)f(y)滿足運(yùn)算的象等于象的運(yùn)算又f(0)=a0=1 /*1是的幺元即f是獨(dú)異點(diǎn)同態(tài)映射28/30定理6.8.6 給定獨(dú)異點(diǎn)，則存在T MM，使。本定理表明，一個(gè)