第六章 代数系统2：-2nd-li.ppt

1、第六章 代数系统 李豪杰 副教授 大连理工大学软件学院 数字媒体技术系 Email: ,1/15,同余关系 定义： 给定，且E为S中的等价关系。 若 E关于有代换性质：(x1)(x2)(y1)(y2)(x1，x2，y1，y2Sx1Ex2y1Ey2) (x1y1)E(x2y2)。 则 E为中的同余关系 商代数 及其上的同余关系E，且由E对S所产生同余类构成一个商集S/E，定义运算*， xE *yE = xyE，则称为代数结构的商代数。 积代数 与是同类型的，可构造 = ,2/15,半群和独异点的定义 定义：运算满足结合律 性质： 半群、独异点的同态与同构 积半群 定义 性质 群 定义 性质,3/

2、39,6.9 积半群 把积代数方法应用于特殊一类代数结构半群，便产生积半群。 定义6.9.1 给定两个半群和。称为和的积半群，其中ST为集合S与T的笛卡儿积，运算定义如下： = ，其中s1，s2S，t1，t2T 由于运算是经和*定义的，易知，积半群是个半群。,4/39,积半群的性质,结合律 可交换性 幺元 零元 逆元,5/39,不难证明下列定理： 定理6.9.1 若半群和是可交换的，则也是可交换的。 定理6.9.2 给定半群和，且e1和e2分别是它们的幺元，则积半群含有幺元。 换言之，若和是独异点，则是独异点。,6/39,定理6.9.3 给定半群和，且1和2分别为它们的零元， 则积半群含有零元

3、。 定理6.9.4 给定半群和，且s的逆元s-1，tT的逆元t-1，则积半群中的逆元是。,7/39,6.10 群的基本定义与性质 定义6.10.1 给定代数系统，若是独异点且每个元素存在逆元， （或者 是可结合的， 关于存在幺元， G中每个元素关于是可逆的，） 则称是群。 可见，群是独异点的特例，或者说，群比独异点有更强的条件。,8/39,例6.10.1 给定和，其中Z和Q分别是整数集合和有理数集合，+和是一般加法和乘法。 可知是群，0是幺元，每个元素iZ的逆元是-i；不是群，1是幺元，0无逆元。但便成为群。 定义6.10.2 给定群，若G是有限集，则称是有限群。并且把G的基数称为该有限群的阶

4、数，若集合G是无穷的，则称为无穷群。特别，若| G | =1，则称为平凡群。,9/39,例6.10.2 例6.10.1中的是无限群， ，其中S = a，b，c，运算表如表6.8.1。 可以验证是群，a为幺元，b和c互为逆元；又因| G | = 3，故是3阶群。 由群的定义可知，群具有半群和独异点的性质，这里不再重复罗列了，而且群还有自己独特的性质，仅此讨论如下:,10/39,、定理6.10.1 是群|G|1无零元。 证明：若0是的零元，因|G|1，则有eG和e 0并且对任意xG均有0 x=0e 即0无逆元，这与群的定义矛盾故群无零元 非平凡群不含零元 、定理6.10.2 是群中的惟一等幂元是幺

5、元。 证明：若不然，设还有aG,a e并且有 aa=a， 于是e= a-1 a= a-1 (a a) =(a-1 a) a= e a=a矛盾,11/39,、定理6.10.3 给定群，则有 (a)(b)(c)(a，b，cG(ab = acba = ca)b = c) 即群满足可约律。 证明：因为是群，所以是可结合的，并且每个元素均有逆元，存在幺元e,对任何aG,其逆a-1 G,于是有 a b= a c a-1 (a b)= a-1 (a c) =(a-1 a) b= (a-1 a) c eb= e c b=c 同理可证b a=c a b=c 即群满足可约律,12/39,、定理6.10.4 给定群

6、，则 (a)(b)(a，bG(!x)(xGax = b)(!y)(yGya = b) 或(a)(b)(a，bG(!x)(!y)(x，yG(ax = bya = b) 即群中方程解是惟一的。 证明：因为a (a-1 b) =( aa-1) b=eb=b 即有 x= a-1 b使得a x=b 下面来证x是唯一的， 令ax=b还有一解c,则 ac=b=eb=(aa-1) b =a(a-1b) 即c= (a-1b). 同理可证ya=b的解是唯一的 即y= b a-1.,13/39,定义6.10.3 设为群，aG，nZ，则a的n次幂为： e n=0 an= an-1 a n0 (a-1)m n0 这里应

7、该注意的是：群中元素定义了负整数次幂，这与半群和独异点不同例如， 在中有 (2-1)3 e=0 =13 =1+3 1 +3 1=0 而在中，2-3= e=0 (2-1)3 =(-2)3 =(-2)+(-2)+(-2) =-6,14/39,定义6.10.4 给定群，若是可交换的，则称是可交换群或是Abel群。 是Abel群。,15/39,、定理6.10.6 给定，则 为Abel群(a)(b)(a，bG (ab)2 = a2b2 证明：充分性，设(ab)2 = a2b2来证 是Abel群，即证可交换： (ab)2 = a2b2 (ab)(ab)=(aa)(bb) a(ba)b=a(ab)b ba=

8、 ab 即是可交换的,16/39,再证必要性：即若是Abel群，来证 (ab)2 = a2b2 (ab)2= (ab) (ab) = a(b a)b =a(a b)b =(aa) (bb) =a2 b2. 得证,17/39,定义6.10.5 给定群，且a，幺元eG，则a的阶或周期为 使an=e的最小正整数， 并称n为a的阶记作| a | = n。 任何群幺元e的阶都是1。,18/39,、定理6.10.7 给定群， aG，且| a | = k，p为整数，则ap=e iff p|k。 证明：必要性：若a的阶为k，p为整数且ap=e, 来证p/k. 对p=qk+r, (0r k),于是 e=ap=a

9、qk+r=aqk ar=(ak)q ar =ear= ar，而k是a的阶，即使ak=e的最小正整数，而0r k,所以r=0. 即p=qk，k能整除p. 再证充分性：因为p|k,必存在qZ使得 p=kq,于是ap=akq=(ak)q=eq=e. 问题得证 推论：若an = e且没有n的因子d (1dn)使ad = e，则n为a的阶。,19/39,例6.10.5 如果a6 = e且a e ,a2 e和a3 e，则6是a的阶。,20/39,、定理6.10.8 给定群及aG，则a与a-1具有相同的阶。 证明：设a的阶是n，则an=e 于是(a-1)n= (an)-1=e-1=e, 若n是a-1的阶，则

10、nn. 另一方面， an=(a-1)-1)n)=(a-1)n)-1 =e-1=e 故n n，于是有nn。,21/39,6.11 置换群和对称群 定义6.11.1 令X是非空有限集合，从X到X的双射函数，称为集合X中的置换，并称|X|为置换的阶。 若X = x1，x2，xn，则n阶置换表为 x1， x2， ， xn P = p(x1) p(x2) ， p(xn),22/39,并称 p(x1) p(x2) ， ， p(xn) P-1= x1， x2， ， xn 为P的反置换 特别把置换 x1， x2， ， xn x1， x2， ， xn 为中的恒等置换或幺置换,23/39,此外，用PX表示集合X中

11、的所有置换的集合。 为了说明n个元素的集合可以有多少不同的置换，特给出如下定理： 定理6.11.1 若X=x1，x2，xn，则|PX| = n! 证明：每一种n阶置换都是n个元素的一种全排列，所以n个元素的集合中不同的n阶置换的总数等于n个元素的全排列的种类数目n!.故 |PX| = n!,24/39,定义6.11.2 给定集合X且pi，psPX，由X的元素先进行置换pi后继之作置换ps所得到的置换，表为pips，称pips是置换pi和ps的复合，是复合置换运算。 可以看出，若把置换看成一种特殊关系时，复合置换pips就是复合关系pi ps，常称之右复合；又若把置换看成函数时，那么复合置换又可

12、表成如下的复合函数即所谓左复合： pips= ps pi， 其中表示函数的复合 于是，对于xX有： (pips)(x)=(ps pi)(x)= ps(pi(x),25/39,例6.11.1 令X=a，b，c， 则PX = p1，p2，p3，p4，p5，p6且 a b c a b c p1 = a b c p4 = a c b a b c a b c p2 = b a c p5 = b c a a b c a b c p3 = c b a p6 = c a b 可见p1是恒等置换(p2p5)(a)=? =(p5 p2)(a)= p5(p2(a)=c 对于各置换的反置换也不难看出，如p2的反置换p

13、2-1是： p2 p2-1 =p2-1 p2 = pe = p1,26/39,由定义6.11.1可知，置换即是双射，亦即1-1函数，故PX中的元素, 即置换满足下列四个性质: (1) (p1)(p2)(p1，p2PXp1p2PXp2p1PX) (2) (p1)(p2)( p3)(p1，p2，p3PX (p1p2)p3 = p1(p2p3) (3) (pe)(pePX(p)(pPXpep = ppe = p) (4) (p)(pPX (p-1)(p-1PXpp-1 = p-1p = pe) (1)表明PX对于是封闭的； (2)表明PX对于是可结合的； (3)表明PX 中有幺置换； (4)表明PX

14、中每个置换都有反置换。 因此，可知是一个群，并称它为对称群，习惯上记为。 若Q PX = S|X|，则称由Q和构成的群为置换群。 对称群：集合到自身的所有置换（双射）构成的群。,27/39, 例6.11.2 例6.11.1中PX (现已写S|X|即S3)与构成对称群，其运算表如表6.11.1 表6.11.1 p1 p2 p3 p4 p5 p6 p1 p1 p2 p3 p4 p5 p6 p2 p2 p1 p5 p6 p3 p4 p3 p3 p6 p1 p5 p4 p2 p4 p4 p5 p6 p1 p2 p3 p5 p5 p4 p6 p3 p2 p1 p6 p6 p3 p4 p2 p1 p5,2

15、8/39,对称群是独立于集合X中各个元素，但却依赖于集合X中的元素个数。这就是说，任何三个其它元素的集合都会生成“同样”的置换，这就是为什么将对称群写成，即的理由。 此外，把集合X的基数称为对称群的次数。因此，是三次六阶群，因为|S3|=3!=6。 一般地说来，由n个元素的集合而构成的所有n!个n阶置换的集合Sn与复合置换运算构成群，它便是n次n!阶对称群。,29/39,应该注意，是对称群一定是置换群，但反之不一定成立，即是置换群不一定是对称群因为它并不要求一定要包括全部给定阶的置换。例如，三次置换群和都不是对称群， 其中p1，p2，p5，p6S3。 若说置换是个关系即有序对集合，那么由置换和

16、构成置换群，它会确立怎样的二元关系呢？下面就来回答这个问题。,30/39,定义6.11.3 令是一置换群 且Q S |X|。 称R = 所诱导的X上的二元关系。 例6.11.3 设X = a，b，c，d， Q = pe，p1，p2，p3，其中 a b c d pe= a b c d 可证是X上的一个置换群，而由诱导的X上的二元关系可由图6.11.1给出。,31/39,定理6.11.2 由置换群诱导的X上的二元关系是一等价关系。 R是等价关系，它必将X划分成等价类。关于等价类数目的计算Burnside给出著名定理，这可参见组合学计数部分，这里就不讲了。,32/39,现在，讨论一下置换与群的运算表

17、的联系。 众所周知，群保持独异点的性质， 故在群的运算表中，任两行或任两列均不相同。不仅如此，可以证明每行或每列都是G中元素的置换。 定理6.11.3 在有限群中，每行或每列都是G中元素的置换。,33/39,现在，应用该定理来考察一、二、三和四阶的群。 一阶群仅有幺元，即。 二阶群除幺元e外，还有一个元素，比如a，则有，其运算表如表6.11.2。由定理6.11.3可知，不可能再有其他运算表。在此预先指出，所有的二阶群都与该群同构。 三阶群，可令，其运算表如表6.11.3。由定理6.11.3知，不可能再有别的运算表。同样，任何三阶群都与它同构。,34/39,从运算表可以看出，所有二阶群和三阶群都是Abel群。事实上，四、五阶群也是Abel群，但六阶群未必都是Abel群。 表6.11. 2 表6.11. 3 e a e a b e e a e e a b a a e a a b e b b e a,35/39,上面讲了由有限集合X到X的双射即置换，以及置换群；下面不再限于X是有限集，换言之，它可以是个无限集。这时从集合X到X的双射，称之为一一变换或变换。如果令TX表示所有从集合X到X的变换的集合，则显然有TX XX，并且TX类似PX所具有的四条性质，具体如