离散数学第六章代数系统2-1st

1、1/30第六章 代数系统2/30回顾同余定义定义性质商代数定义性质积代数定义性质3/30第二部分： 半群与群6.7 半群和独异点的定义及性质定义6.7.1 给定，若满足结合律，则称为半群。可见，半群就是由集合及其上定义的一个可结合的二元运算组成的代数结构。定义6.7.2 给定，若是半群且有幺元或满足结合律且拥有幺元，则称为独异点。可以看出，独异点是含有幺元的半群。因此有些著作者将独异点叫做含幺半群。有时为了强调幺元e，独异点表为。4/30例6.7.1 给定和，其中N为自然数集合，+和为普通加法和乘法。易知和都是半群，而且还是独异点。因为0是+的幺元，1是的幺元。如果半群中的集合S是有限的，则称

2、半群为有限半群。对于有限半群可以给出下面有趣定理：5/30定理6.7.1 为有限半群(x)(xSxx=x)本定理告诉我们，有限半群存在等幂元。证明：因为是可结合的，所以对任意的xS有xx=x2 S （封闭性）x2 x=x S因为S是有限集，必存在ji使得 xj=xi 6/30令p=j-i,则xj= xi= xp xi (1)所以，对于qi有xq= xp xq因为p1,故总有k 1,使得kpi.对于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 给定半群，若是可交换的，则称是可交换半群。类似地可定义可交换独异点。例6.7.2 给定和，其中P(S)是集合S的幂集，和为集合上的并与交运算。可知和都是可交换半群。不仅如此，它们还都是可交换独异点，因为与S分别是它们的幺元。8/30定义6.7.4 给定半群和gS，以及自然数集合N，则g为的生成元：(x)(xS(n)(nNx = gn)此时也说，元素g生成半群，而且称该半群为循环半群。类似地定义独异点M，e)的生成元g和循环独异点，并且规定g0=e。定理6.7.2 每个循环独异点都是可交换的。将生成元的概念加以推广便得出生成集的概念。9/30定义6.7.5 给定半群及GS，则G为的生成集：(

4、a)(aSa=(G)min|G| GS这里(G)表示用G中的元素经的复合而生成的元素。类似地定义独异点的生成集。例6.7.3 给定，其中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、对封闭，则称为的子半群。类似地定义独异点的子独异点，应注意的是eP。定理6.7.3 给定半群及任意aS，则是循环子半群。证明：因为是半群，所以，对任意aS, aaS(封闭性)即a2 S,于是a2aS ,ai S , iZ+即a，a2，a3， S,并且a是生成元，13/30于是是循环子半群定理6.7.4 给定可交换独异点，若P为其等幂元集合，则为子独异点。证明：eP是明显的，令a,b P,则有aa P和bbP于是有 (ab)(ab)= (ab)(ba) = a(bb)a = aba =(aa)b =abP即对是封闭的，得证14/30定理6.7.5 设为独异点，则关于的运算表中任两列或任两行均不相

6、同。证明：因为对任意的a,bM且ab时，总有e a=a b=e b和ae=a b=b e因此在的运算表中不可能有两列和两行是相同的15/30定理6.7.6 给定独异点，对任意a，bM且a，b均有逆元，则(1) (a -1) -1 = a。(2) ab有逆元，且(ab) -1 = b -1a -1。16/306.8 半群和独异点的同态与同构定义6.8.1 给定两个半群与，则 ：(f )(fTS(x)(y)(x，yS f(xy)= f(x)*f(y)并称f为从到的半群同态映射。由定义可以知道，半群同态映射f可以不是惟一的。17/30与前面定义类似，根据半群同态映射f是单射(一对一)、满射、双射，把

7、半群同态映射f分别定义半群单一同态映射、半群满同态映射和半群同构映射。如果两个半群，存在一个同构映射，则称一个半群同构于另一个半群。由于代数结构之间的满同态具有保持运算的各种性质，对于半群满同态当然完全适用。18/30下面给出一个半群同态保持等幂性的定理。定理6.8.1 如果f为从到的半群同态映射，对任意aS且aa = a，则f(a) *f(a)= f(a)。证明：因为对任意aS且aa = a而f是同态映射，即有f(aa)=f(a)= f(a)* f(a),即等幂性保持 19/30由于半群同态映射是个函数，因此可对半群同态映射进行复合运算，从而产生新的半群同态映射。请看如下定理：定理6.8.2

8、 如果g是从到的半群同态映射，h是从到的半群同态映射，则hg是从到的半群同态映射。证明：对任意x,yS,有(hg)(xy)=h(g(xy) /*g TS且是同态 =h(g(x) g(y)=h(g(x)*h(g(y) /*h ut且是同态 即(hg) us 且是同态 20/30定义6.8.2 若g是从到的半群同态映射，则称g为半群自同态映射；若g是从到的半群同构映射，则称g为半群自同构映射。定理6.8.3 给定半群，如果A=g| g为到的半群自同态映射且是函数复合运算，则为半群。该定理是明显的，由前一个定理知在上是封闭的，函数的复合运算是可结合的21/30由于恒等映射idA是复合运算的幺元，因此

9、可得下面定理：定理6.8.4 给定半群，若B=h|h为到的半群自同构映射，为函数复合运算，则是独异点。定理6.8.5 给定半群，又是从S到S的所有函数在复合运算下构成的函数半群，则存在从到的半群同态映射g，或者说半群同态于。但该函数是射入的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个元素，且是独异点。根据定理6.8.5可知，g是从到的半群同态映射。23/30表6.8.1 a b c a a b c b b c a c c a b上面介绍半群同态及有关定理。接着讨论独异点之间的同态及其有关定理。24/30定义6.8.3 给定独异点和，则：(g)(gTM(x)( y) (x，yMg(xy)= g(x)*g(y)g(eM)= eT)并称g为从到的独异点同态映射。注意，独异点同态区别半群同态就在于保持幺元，即g(eM)= eT。因此，半群同态未必是独异点同态，反之都真。25/30例6.8.2 给定独异点和，其中N为自然数集合，+为一般加法，0为幺元，S = e，0，1

11、，*定义如表6.8.2，e为幺元，又有映射gSN： 0 i0g(i)= 1 i=0试问g是否为到的独异点同态映射？26/30表6.8.2 * e 0 1 e e 0 1 0 0 0 0 1 1 0 1证明：对任何i,j N和i 0,j 0i+j 0,于是有g(i+j)=0 g(i)+g(j)=0满足运算的象等于象的运算，但是g(0)=1e,所以g不是独异点同态映射27/30例6.8.3 给定独异点和，其中R是实数集合，+和是一般加法和乘法，0和1分别为它们的幺元。令fRR:f(x)= ax 其中a0，xR问f是否为从到的独异点同态映射？证明：因为对任何x,yR, f(x+y)= ax+y= f(x)f(y)满足运算的象等于象的运算又f(0)=a0=1 /*1是的幺元即f是独异点同态映射28/30定理6.8.6 给定独异点，则存在T MM，使。本定理表明，一个