离散数学典型代数系统教学PPT.ppt

第6章 典型代数系统,基本内容,半群与群 环和域 格与布尔代数,6.1 半群与群,6.1.1 半群与独异点 定义6.1 给定一个代数系统，其中s是非空集合，是s上的一个二元运算，如果运算是封闭的，则称代数系统为广群。 可见，一个封闭的代数系统即为广群。 定义6.2 给定一个代数系统，其中s是非空集合，是s上的一个二元运算，如果运算是封闭的，并且满足结合律，则称代数系统为半群。 可见，若广群上的运算满足结合律，即为半群。,6.1.1 半群与独异点,定义6.3 给定，若是半群且有幺元，则称为独异点。 可以看出，独异点是含有幺元的半群。因此有些著作中将独异点也叫做含幺半群。有时为了强调幺元e，将独异点表示为。 例6.1 设集合sk=x|xzxk，k0，那么是一个半群，其中+是普通的加法运算。 解：因为运算+在sk上是封闭的，而且普通加法运算是可结合的。所以，是一个半群。,6.1.1 半群与独异点,本例中，k0这个条件是很重要的，否则，如果k和，其中n为自然数集合，+和为普通加法和乘法。易知和都是半群，而且还是独异点。因为0是+的幺元，1是的幺元。 如果半群中的集合s是有限的，则称半群为有限半群。对于有限半群可以给出下面定理： 定理6.1 为有限半群(x)(xsxx=x),6.1.1 半群与独异点,证明：因为是半群，对于任意的bs，由的封闭性可知 bbs，记b2= bb b2b=bb2s，记b3= b2b= bb2 因为s是有限集，所以必定存在ji，使得 bi= bj 令 p=j-i 便有 bi= bpbi 所以 bq= bpbq qi 因为p1，所以总可以找到k1，使得 kpi,6.1.1 半群与独异点,对于s中的元素bkp，就有 bkp=bpbkp =bp(bpbkp)=b2pbkp=b2p(bpbkp) =bkpbkp 这就证明了在s中存在元素x=bkp，使得xx=x 本定理告诉我们，有限半群必存在等幂元。 定义6.4 给定半群，若是可交换的，则称是可交换半群。类似地可定义可交换独异点。,6.1.1 半群与独异点,例6.3 给定和，其中p(s)是集合s的幂集，和为集合上的并与交运算。可知和都是可交换半群。不仅如此，它们还都是可交换独异点，因为与s分别是它们的幺元。 定义6.5 给定半群和gs，以及自然数集合n，则g为的生成元当且仅当(x)(xs(n)(nnx = gn)。此时也说，元素g生成半群，而且称该半群为循环半群。 类似地定义独异点的生成元g和循环独异点，并且规定g0=e。,6.1.1 半群与独异点,定理6.2 每个循环半群都是可交换的。 证明：设是一个循环半群，g是生成元，那么，对于任意的x，ys，必有r，sn，使得 x=gr和y=gs 而且 xy=grgs=gr+s=gs+r= gsgr= yx 因此，是可交换的。 类似地有每个循环独异点都是可交换的。 对于生成元的概念加以推广便得出生成集的概念。,6.1.1 半群与独异点,定义6.6 给定半群及gs，则g为的生成集当且仅当(a)(asa=(g) ，这里(g)表示用g中的元素经的复合而生成的元素。 类似地定义独异点的生成集。 例6.4 给定，其中n是自然数集合，+为普通加法，则是无穷循环独异点，0是幺元，1是生成元。 例6.5 令半群，其中s=a，b，c，d，定义如表6-1，试证明生成集g = a，b。,6.1.1 半群与独异点,解：由表6-1可知， c= ab, d= aa 可见，a，b生成a，b，c，d，故得生成集g = a，b。 表6-1,6.1.1 半群与独异点,定义6.7 给定半群及非空集ts，若t对封闭，则称为的子半群。 类似地定义独异点的子独异点，应注意的是ep。 定理6.3 给定半群及任意as，则是循环子半群。 证明：因为是半群，故对任意as，ais，其中i为正整数，则a，a2，a3，s。显然，a是的生成元。故是循环子半群。,6.1.1 半群与独异点,定理6.4 给定可交换独异点，若p为其等幂元集合，则为子独异点。 证明：显然，ep，令a，bp，于是 aa=a， bb =b 又因为是可交换的，故 (ab)(ab)=(ab)(ba) =a(bb)a =aba =aab =ab 可见，abp，即对于p是封闭的，因而是的子独异点。,6.1.1 半群与独异点,定理6.5 设为独异点，则关于的运算表中任两列或任两行均不相同。 证明：因为对任意的a，bm且ab时，总有 ea=ab=eb 和 ae =ab=be 因此，在的运算表中不可能有两列或两行是相同的。 定理6.6 给定独异点，对任意a，bm且a，b均有逆元，则,6.1.1 半群与独异点,(1) (a-1)-1 = a。 (2) ab有逆元，且(ab)-1 =b-1a-1。 证明：(1) 因为a-1是a的逆元，即 aa-1= a-1a=e 所以 (a-1)-1 = a。 (2) 因为 (ab)(b-1a-1) = a(bb-1)a-1 = aea-1= aa-1=e 同理可证 (b-1a-1)(ab)=e 所以 (ab)-1 =b-1a-1。,6.1.1 半群与独异点,代数系统之间的同态与同构的概念完全适用于半群和独异点。半群同态的定义如下： 定义6.8 给定两个半群与，则同态于当且仅当(f)(fts(x)(y)(x，ys f(xy)= f(x)*f(y)，并称f为从到的半群同态映射。 由定义可以知道，半群同态映射f可以不是惟一的。 与前面定义类似，根据半群同态映射f是单射(一对一)、满射、双射，把半群同态映射f分别定义半群单一同态映射、半群满同态映射和半群同构映射。,6.1.1 半群与独异点,如果两个半群，存在一个同构映射，则称一个半群同构于另一个半群。 由于代数系统之间的满同态具有保持运算的各种性质，对于半群满同态当然完全适用。 下面给出一个半群同态保持等幂性的定理。 定理6.7 如果f为从到的半群同态映射，对任意as且aa=a，则f(a)*f(a)= f(a)。,6.1.1 半群与独异点,证明：因为f为从到的半群同态映射，对任意as且aa=a，则有 f(a)= f(aa)= f(a)*f(a) 故，由as是关于的等幂元可推出f(a)是关于*的等幂元。 由于半群同态映射是个函数，因此可对半群同态映射进行复合运算，从而产生新的半群同态映射。请看如下定理： 定理6.8 如果g是从到的半群同态映射，h是从到的半群同态映射，则hg是从到的半群同态映射。,6.1.1 半群与独异点,证明：对任意x，ys，则 (hg)(xy)=h(g(xy) = h(g(x)g(y)= h(g(x)*h(g(y) =(hg)(x)*(hg)(y) 可见，hg是所求的半群同态映射。 定义6.9 若g是从到的半群同态映射，则称g为半群自同态映射；若g是从到的半群同构映射，则称g为半群自同构映射。,6.1.1 半群与独异点,定理6.9 给定半群，如果a=g|g为到的半群自同态映射且是函数复合运算，则为半群。 证明：由定理6.8知，a在的作用下是封闭的，又因为对任意f，g，ha，有 (hg)f)(x)=(hg)(f(x) =h(g(f(x) =h(gf)(x) 可见，是可结合的，故是半群。 由于恒等映射ia是复合运算的幺元，因此可得下面定理：,6.1.1 半群与独异点,定理6.10 给定半群，若b=h|h为到的半群自同构映射，为函数复合运算，则是独异点。 定理6.11 给定半群，又是从s到s的所有函数在复合运算下构成的函数半群，则存在从到的半群同态映射g，或者说半群同态于。 证明：对任意xs，令g(x) = fx，其中fxss，其定义如下： fx(y)= xy，其中ys，,6.1.1 半群与独异点,现在 g(xy)=fxy 这里 fxy(z)=(xy)z=xyz = fx(fy(z) = fxfy(z) 其中zs 故 g(xy)=fxy=fxfy=g(x) g(y) 可见g是到的半群同态映射，并且对于xs，函数fx可由的运算表中与x所在行的各项所确定。 例6.6 给定半群，其中s=a，b，c，定义由表6-2所示。今定义g(ss)s，g(a)= fa， g(b)= fb， g(c)= fc，这里fa，fb，fcss，并且,6.1.1 半群与独异点,fa(a)= a fa(b)= b fa(c)= c fb(a)= b fb(b)= c fb(c)= a fc(a)= c fc(b)= a fc(c)= b 显然，ss中有33 = 27个元素，且是独异点。根据定理6.11可知，g是从到的半群同态映射。 表6-2,6.1.1 半群与独异点,上面介绍半群同态及有关定理。接着讨论独异点之间的同态及其有关定理。 定义6.10 给定独异点和，则同态于当且仅当(g)(gtm(x)(y)(x，ymg(xy)= g(x)*g(y)g(em)= et)，并称g为从到的独异点同态映射。 注意，独异点同态区别半群同态就在于保持幺元，即g(em)= et。因此，半群同态未必是独异点同态，反之都真。,6.1.1 半群与独异点,例6.7 给定独异点和，其中n为自然数集合，+为一般加法，0为幺元，s = e，0，1，*定义如表6-3，e为幺元，又有映射gsn： 试问g是否为到 表6-3 的独异点同态映射？ ,6.1.1 半群与独异点,解：对任意i，jn和i0及j0，则有 g(i+j)=0, g(i)*g(j)=0*0=0 然而， g(0)=1e 因此，g不是从到的独异点同态映射。 例6.8 给定独异点和，其中r是实数集合，+和是一般加法和乘法，0和1分别为它们的幺元。令frr: f(x)= ax 其中a0，xr,6.1.1 半群与独异点,问f是否为从到的独异点同态映射？ 解：因为对任意x，yr，有 f(x+y)=a x+y=axay= f(x)f(y) f(0)= a 0=1 故，f是从到的独异点同态映射。,6.1.1 半群与独异点,定理6.12 给定独异点，则存在t mm，使。 证明：类似定理6.11，构造g(mm)m，则存在g(m)是m在同态映射g作用下的象，显然g(m) mm，且g是到的满同态，又因为为独异点，故其运算表中的任两行或任两列均不相同，因此g又是双射。故g是到的同构映射。若取t= g(m)，则有。 本定理表明，一个独异点可与复合运算下的函数独异点同构。,6.1.2 群的定义与性质,定义6.11 给定，若是独异点且每个元素存在逆元，或者运算是封闭的，是可结合的，关于存在幺元，g中每个元素关于是可逆的，则称是群。 可见，群是独异点的特例，或者说，群比独异点有更强的条件。 顺便指出，1944年，p.lorenzen曾给出40个以上群的定义。,6.1.2 群的定义与性质,例6.9 给定和，其中z和q分别是整数集合和有理数集合，+和是一般加法和乘法。可知是群，0是幺元，每个元素iz的逆元是-i；不是群，1是幺元，0无逆元。但便成为群。 定义6.12 给定群，若g是有限集，则称是有限群。并且把g的基数称为该有限群的阶数，若集合g是无穷的，则称为无穷群。特别，若|g| =1，则称为平凡群。,6.1.2 群的定义与性质,例6.9中的是无穷群，再如例6.6中，其中s = a，b，c，运算表如表6-2。可以验证是群，a为幺元，b和c互为逆元；又因|g| = 3，故是3阶群。 例6.10 设s=0，60，120，180，240，300表示在平面上几何图形围绕中心顺时针旋转角度的六种可能情况，设是s上的二元运算，对于s中任意两个元素a和b，ab表示平面图形连续旋转a和b得到的总旋转角度。并规定旋转360等于原来的状态，即看作没有经过旋转。试证：是一个群。,6.1.2 群的定义与性质,证明：由题意，s上二元运算的运算表如表6-4所示： 表6-4 由表6-4可见，运算在s上是封闭的。,6.1.2 群的定义与性质,对于任意的a，b，cs，(ab)c表示将图形依次旋转a，b和c，而a(bc)表示将图形依次旋转b，c和a，而总的旋转角度等于a+b+c(mod 360)，因此(ab)c = a(bc)。 显然0是幺元。 60与300互为逆元，120与240互为逆元，180的逆元是180。因此是一个群。 由群的定义可知，群具有半群和独异点的性质，这里不再重复罗列了，而且群还有自己独特的性质，讨论如下:,6.1.2 群的定义与性质,定理6.13 是群|g|1无零元。 证明：若为的零元，又知|g|1，则由定理5.4得：e。对任意xg，均有x=e，故无逆元，这与是群矛盾。 定理6.14 是群中的惟一等幂元是幺元。 证明：假定a是等幂元，即有 aa=a。于是， e= a-1a = a-1(aa) =( a-1a) a = ea = a 可见，只有幺元e为等幂元。,6.1.2 群的定义与性质,定理6.15 给定群，则有(a)(b)(c)(a，b，cg(ab = acba = ca)b = c) 即群满足可约律。 证明：因为是群，故可令e为其幺元，并且是可结合得。 又设任意ag，其逆元为a-1。于是 ab = ac a-1(ab) = a-1(ac) ( a-1a)b = (a-1a)c eb = ec b =c 即得 ab = ac b =c 同理 ba = ca b =c,6.1.2 群的定义与性质,定理6.16 给定群，则 (a)(b)(a，bg(!x)(xgax = b)(!y)(ygya = b) 或(a)(b)(a，bg(!x)(!y)(x，yg(ax = bya = b) 即群中方程解是惟一的。 证明：因为是群，应有幺元e，并且是可结合的。于是a(a-1b) =(a-1a)b= eb= b 故，x= a-1b。,6.1.2 群的定义与性质,下面再证x的惟一性。令ax= b还有一解c，则 ac= b= eb=(a-1a)b= a(a-1b) 根据群的可约律可得 c= a-1b 同理可证，ya = b的解是惟一的。,6.1.2 群的定义与性质,定义6.13 设为群，ag，nz，则a的n次幂为： 值得注意的是：群中元素定义了负整数次幂，这与半群和独异点不同。例如，在中有2-3 =(2-1)3 = 13 = 1 +3 1 +3 1 = 0，而在中，2-3 =(2-1)3 =(-2)3 =(-2)+(-2)+(-2)= -6,6.1.2 群的定义与性质,定理6.17 设为群，则 ag，(a-1)-1 = a a，bg，(ab)-1 = b-1a-1 ag，m，nz，有aman = am+n ag，m，nz，有(am)n = amn 、的证明见定理6.6。、由数学归纳法不难得证。,6.1.3 阿贝尔群、置换群与循环群,1阿贝尔群 定义6.14 给定群，若是可交换的，则称是abel群或是可交换群。 例6.11 例6.9中和例5.1中都是abel群。 例6.12 设s=a，b，c，d，在s上定义一个双射函数f：f(a)=b，f(b)=c，f(c)= d，f(d) =a，对于任一xs，构造复合函数 f 2(x)= f f(x) = f(f(x), f 3(x)= ff 2(x) = f(f 2(x) f 4(x)= ff 3(x) = f(f 3(x),6.1.3 阿贝尔群、置换群与循环群,如果用f 0表示s上的恒等映射，即 f 0(x)=x，xs 很明显，有f 4(x)= f 0(x)，记f 1= f，构造集合f=f 0，f 1，f 2，f 3，那么试证是一个abel群。 证明：对于中任意两个函数的复合，可以由表6-5给出。 表6-5,6.1.3 阿贝尔群、置换群与循环群,可见，复合运算关于f是封闭的，并且是可结合的。 f 0是关于复合运算的幺元。 f 0的逆元就是它自身，f 1和f 3互为逆元，f2的逆元也是它自身。 由表6-5的对称性，可知复合运算是可交换的。因此是一个abel群。 定理6.18 给定群，则 为abel群(a)(b)(a，bg (ab)2 = a2b2),6.1.3 阿贝尔群、置换群与循环群,证明：充分性：设对任意a，bg，有 (ab)2 = a2b2，即 (ab)(ab) = (aa)(bb) 因为 a(ab)b= (aa)(bb) = (ab)(ab) = a(ba)b 所以 a-1(a(ab)b)b-1 = a-1(a(ba)b)b-1 即得 ab=ba 因此，群是abel群。,6.1.3 阿贝尔群、置换群与循环群,必要性：设是abel群，则对任意的a，bg，有 ab=ba 因此 (aa) (bb) = a(ab)b = a(ba)b=(ab)(ab) 定义6.15 给定群，且ag，幺元e，则a的阶或周期为n：=(k)(kz+ ，并称a的阶是有限的，并记作|a| = n；否则，a的阶是无穷的。 例6.13 任何群的幺元e的阶都是1。,6.1.3 阿贝尔群、置换群与循环群,定理6.19 给定群，ag，且|a| =n，m为整数，则ak=e 当且仅当k=mn。 证明：充分性：因为k=mn，故 ak=amn=(an)m=em=e 必要性：若ak=e，于是对于0tn，有 k=mn+t 故，at=ak-nm=aka-nm=e(an)-m=e-m=e，由定义6.15知，n是使an=e的最小正整数，而0tn，因此t=0，即得k=mn。,6.1.3 阿贝尔群、置换群与循环群,推论6.1 若an = e且没有n的因子d (1dn)使ad = e，则n为a的阶。 例6.14 如果a6 = e且a2 e和a3 e，则6是a的阶。 定理6.20 给定群及ag，则a与a-1具有相同的阶。 证明：设a的阶是n，则an = e。于是 (a-1)n=(an)-1=e -1=e 若m是a-1的阶，则mn。 另一方面，am=( a-1m)-1=e -1=e，故nm。可见n=m。,6.1.3 阿贝尔群、置换群与循环群,接下来讨论置换群，在研究群的同构群时，置换群有着非常重要的作用。在讨论置换群之前，我们先作一些必要的准备。 2置换群 定义6.16 令x是非空有穷集合，从x到x的双射，称为集合x中的置换，并称|x|为置换的阶。 若x = x1，x2，xn，则n阶置换表为,6.1.3 阿贝尔群、置换群与循环群,并称 为置换中的反置换，记为p-1。特别把置换 称为x中的幺置换或恒等置换，记为pe。 此外，用px表示集合x中的所有置换的集合。 为了说明n个元素的集合可以有多少不同的置换，特给出如下定理： 定理6.21 若x=x1，x2，xn，则|px| = n! 证明：因为每一种n阶置换都是n个元素的一种全排列，所以n个元素的集合中不同的n阶置换的总数等于n个元素的全排列的种类数目n!。故|px| = n!。,6.1.3 阿贝尔群、置换群与循环群,定义6.17 给定集合x且pi，pjpx，由x的元素先进行置换pi后继之作置换pj所得到的置换，表为pipj，称pipj是置换pi和pj的复合，是复合置换运算。 可以看出，若把置换看成一种特殊关系时，复合置换pipj就是复合关系pi pj，常称之右复合；又若把置换看成函数时，那么复合置换又可表成如下的复合函数即所谓左复合： pipj = pj pi， 其中表示函数的复合 于是，对于xx有：(pipj)(x)=(pj pi)(x)= pj(pi(x),6.1.3 阿贝尔群、置换群与循环群,例6.15 令x=a，b，c，则px = p1，p2，p3，p4，p5，p6且 p1 = p2 = p3 = p4 = p5 = p6 = 可见，p1是幺置换。 对于各置换的反置换也不难看出，如p2的反置换p2-1是： p2-1 = 任何两个置换复合也易计算，如p3p4 = = = p5,6.1.3 阿贝尔群、置换群与循环群,由定义6.15可知，置换即是双射，亦即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对于是可结合的；,6.1.3 阿贝尔群、置换群与循环群,(3)表明px中有幺置换； (4)表明px中每个置换都有反置换。 因此，可知是一个群，并称它为对称群，习惯上记为。若q px = s|x|，则称由q和构成的群为置换群。 例6.16 例6.15中px(现已写s|x|即s3)与构成对称群，其运算表如表6-6。 对称群是独立于集合x中各个元素，但却依赖于集合x中的元素个数。,6.1.3 阿贝尔群、置换群与循环群,这就是说，任何三个其它元素的集合都会生成“同样”的置换，这就是为什么将对称群写成，即的理由。此外，把集合x的基数称为对称群的次数。因此，是三次六阶群，因为|s3|=3!=6。 表6-6,6.1.3 阿贝尔群、置换群与循环群,一般地说来，由n个元素的集合而构成的所有n!个n阶置换的集合sn与复合置换运算构成群，它便是n次n!阶对称群。 应该注意，置换群一般都不是对称群，因为它并不要求一定要包括全部给定阶的置换。例如，三次置换群和都不是对称群，其中p1，p2，p5，p6s3。 若说置换是个关系即有序对集合，那么由置换和构成置换群，它会确立怎样的二元关系呢？下面就来回答这个问题。,6.1.3 阿贝尔群、置换群与循环群,定义6.18 令是一置换群且q s|x|。称r=所诱导的x上的二元关系。 例6.17 设x = a，b，c，d，q = pe，p1，p2，p3，其中 pe= p1= p2= p3= 可证是x上的一个置换群，而由诱导的x上的二元关系可由图6.1给出。,6.1.3 阿贝尔群、置换群与循环群,图6.1 定理6.22 由置换群诱导的x上的二元关系是一等价关系。 证明：由诱导的x上的二元关系是 r=a，b|p(a)= bpq s|x|a，bx 因为幺置换peq，故对任意ax，必有a，ar，这即表明r是自反的；,6.1.3 阿贝尔群、置换群与循环群,令是群，故p-1q，即 b，ar，可见r是对称的。 最后，再令a，b和 b，cr，则有p1，p2q，使p1(a)= b，p2(b)= c。因为p1p2q，而(p1p2)(a) =(p2p1)(a)= p2(p1(a)= p2(b) =c，即 a，cr，所以r是传递的。综上所述，r是一个等价关系。 r是等价关系，它必将x划分成等价类。关于等价类数目的计算burnside给出著名定理，这可参见组合学计数部分，详见第10章。,6.1.3 阿贝尔群、置换群与循环群,现在，讨论一下置换与群的运算表的联系。 众所周知，群保持独异点的性质，故在群的运算表中，任两行或任两列均不相同。不仅如此，可以证明每行或每列都是g中元素的置换。 定理6.23 在有限群中，每行或每列都是g中元素的置换。 证明：首先，证明运算表的任一行所含g中的元素不可能多于一次。若不然，令对应于ag的那一行有两个元素都是c，即对于行表头中的元素b1，b2，有 ab1=ab2=c,6.1.3 阿贝尔群、置换群与循环群,根据群的可约律，得 b1=b2 而这与b1b2矛盾。 其次，证明g中每个元素都在运算表的每一行中出现。为此，考察对应于ag的那一行，令b为g中任意元素，由于b= a(a-1b)，可见，b必出现对应于a的那一行中。 又因为群的运算表中任两行均不相同，便可得出的运算表中每行都是g中元素的一个置换，且各行都是不相同的置换。 类似可证，同样的结论对于列也成立。,6.1.3 阿贝尔群、置换群与循环群,现在，应用该定理来考察一、二、三和四阶的群。 一阶群仅有幺元，即。 二阶群除幺元e外，还有一个元素，比如a，则有，其运算表如表6-7。由定理6.23可知，不可能再有其他运算表。在此预先指出，所有的二阶群都与该群同构。 三阶群，可令，其运算表如表6-8。由定理6.21知，不可能再有别的运算表。同样，任何三阶群都与它同构。,6.1.3 阿贝尔群、置换群与循环群,从运算表可以看出，所有二阶群和三阶群都是abel群。事实上，四、五阶群也是abel群，但六阶群未必都是abel群。 例6.18 给定四阶群，其运算表如表6-9所示。可以看出，a为幺元，b-1 = b，c-1 = d，d-1 = c，要验证确是可结合的，必须考察元素b，c和d的27个组合，这是比较麻烦的事情，然而又只能这样去做。,6.1.3 阿贝尔群、置换群与循环群,上面讲了由有限集合x到x的双射即置换，以及置换群；下面不再限于x是有限集，换言之，它可以是个无穷集。这时从集合x到x的双射，称之为一一变换或变换。如果令tx表示所有从集合x到x的变换的集合，则显然有tx xx，并且tx类似px所具有的四条性质，具体如下：,6.1.3 阿贝尔群、置换群与循环群,(1)(f)(g)(f，gtx f g，gf tx) (2)(f)(g)(h)(f，g，htx (f g)h = f (gh) (3)(ia)( iatx(f)(f tx iaf = f ia = f ) (4)(f )(f tx (f -1)(f -1txff -1=f -1f = i) 因而，可证构成群，在代数中称为变换群，显然，置换群是变换群的特例。 请注意，由tx中的一些变换与运算构成的群，都称为变换群，而只不过是个特殊情形而己。,6.1.3 阿贝尔群、置换群与循环群,3循环群 定义6.19 设是群，若gg，对xg，kz，有x = gk，称是循环群，记作g = ，称g是群的生成元。 若存在最小正整数n，gn = e，称n为生成元的阶或周期；否则称g是无限阶的。 根据生成元g的阶，将循环群分成两类：一是有限循环群，二是无限循环群。于是若g= 且g的阶为n，则g = g0 = e，g，g2，gn-1，即|g| = |g| = n，否则，g = g0 = e，g1，g2，有|g|g| = 。,6.1.3 阿贝尔群、置换群与循环群,例如，是6阶循环群，生成元是1，而是无限循环群，其生成元是1和-1。 例6.19 在例6.18中，由表6-9得： aa = a bb = a cc = c2 = b c3 = d c4 = a dd = d2 = b d3 = c d4 = a 可见，生成元是c或d，故是循环群。 定理6.24 任何一个循环群必定是abel群。 可仿定理6.2的证明。,6.1.3 阿贝尔群、置换群与循环群,定理6.25 设是以g为生成元的循环群，e为幺元，若|g|=n，则gn = e，且g = g，g2，gn = e。 证明：假设对于某个正整数mz+和mn，有gn = e。 因为是循环群，故对于g中的任意元素a，存在sz+，使得a= gs。 令s=mq+r，其中qz且0rm。于是 gs= gmqgr= (gm)qgr=eqgr= gr,6.1.3 阿贝尔群、置换群与循环群,这意味着，g中每个元素可表示为gr且0rm。可见g中的元素至多有m个不同元素。即|g|mn，这与|g|=n矛盾。因此gn = e。 下面再证g，g2，gn = e全都是互不相同的。否则，存在ijn，使得gi= gj，于是，gig-i= gjg-i=e，且j -i n，这又与|g|=n矛盾。,6.1.4 子群、陪集与拉格朗日定理,子群概念，类似于子半群和子独异点。 定义6.20 设是一个群，hg为非空集合，若也是群，则称为群的子群。显然，和都是的子群，并且分别是的“最小”和“最大”的子群，这对任何群来说，都有这样的子群，因此这两个子群称为平凡子群，而其余子群则称为真子群。 例6.20 在例6.16群中，取h = p1，p4，由运算表6-6可知，h s3，而且是群，因为幺元是p1，p4-1=p4。故是的子群。,6.1.4 子群、陪集与拉格朗日定理,群与其子群有如下的明显性质： 定理6.26 是群的子群 eh = eg，其中eh和eg分别是和的幺元，即群与其子群具有相同幺元。 证明：因为是群的子群，则对任意ahg，有 aeh = a= aeg 根据群的可约律，得eh = eg。 下面给出关于子群的充要条件的定理。,6.1.4 子群、陪集与拉格朗日定理,定理6.27 给定群及非空hg，则是的子群当且仅当(a)(b)(a，bhabh)(a)(aha-1h)。 证明：充分性：由(a)(b)(a，bhabh)可知，运算在h上是封闭的。 下面再证是群。 由于是群，可知是可结合的，又由题设(a)(aha-1h)知h中每个元素存在逆元，再由在h上是封闭的及h中每个元素存在逆元可推出幺元eh如下：e= aa-1h，ah,6.1.4 子群、陪集与拉格朗日定理,必要性：显然成立。 本定理表明为的子群的充要条件是h对于封闭及h中每个元素存在逆元。 定理6.28 给定群及非空hg，则 是的子群(a)(b)(a，bhab-1h) 证明：充分性：令任意ah，则e=aa-1h。于是，a-1=ea-1h。又若a，bh，则由上面结果知b-1h，于是a(b-1)-1h，根据定理6.27的充分条件知是的子群。,6.1.4 子群、陪集与拉格朗日定理,必要性：若，根据定理6.27的必要条件知b-1h及ab-1h。 定理6.29 给定群及非空有限集hg，则 是的子群(a)(b)(a，bhabh) 证明：必要性：显然成立。 充分性：由(a)(b)(a，bhabh)可知，运算在h上是封闭的。 下面再证是群。,6.1.4 子群、陪集与拉格朗日定理,令任意ah，则由有限集h对于封闭可知，存在ij，使得ai=aj。因此，e=aj-ih且a-1= aj-i-1。可见，幺元e是存在的且每个元素存在逆元。 故根据定理6.27知是的子群。 确定已知群的全部子群，一般来说是很困难的，但对于循环群而言，却是容易办到的，这可由下面定理得出： 定理6.30 循环群的任何子群都是循环群。,6.1.4 子群、陪集与拉格朗日定理,证明：设是循环群的子群，且he。g为的生成元，则存在最小的正整数m，使得gmh。对于任意的glh，必有l=tm+r，0rm，t0，故gr=gl-tm= gl(gm)-th。因为m是gmh的最小正整数，所以，只能有r =0，即得gl=(gm)t。这说明，h中的任意元素都是gm的乘幂。因此，是以gm为生成元的循环群。 接下来我们讨论子群的陪集与拉格朗日定理。,6.1.4 子群、陪集与拉格朗日定理,定义6.21 令是群的子群且ag，则把下面集合： ah = ah|hh 称为由元素a所确定的群中的h的左陪集，或简称为左陪集并简记ah。此外，称a是左陪集ah的代表元素。 类似地可定义由a所确定群中的h的右陪集ha。 显然，若是abel群，并且是其子群，则ah = ha，即任意元素的左陪集等于其右陪集。,6.1.4 子群、陪集与拉格朗日定理,定义6.22 给定群，子群的左陪集关系，记作 ，其定义为： ：= 的左陪集关系 是群中的一种等价关系。其证明如下： 由于a-1a = eh，则a a，即 有自反性。 若a b，则b-1ah，于是a-1b=(b-1a)-1h，故b a，因而 满足对称性。,6.1.4 子群、陪集与拉格朗日定理,若a b且b c，则b-1ah和c-1bh，所以 c-1a =(c-1b) (b-1a)h，故有a c，因而 满足传递性。 显然，左陪集关系 能把集合g划分成等价类。若ag，则a = b|b a=b| = b|a-1bh = b|b = ah，hh = ah|hh = ah ，其中h = a-1b。 可见，由元素a所确定群中的h的左陪集ah与子群的左陪集关系 所确定的等价类 是完全相同的，即ah = 。,6.1.4 子群、陪集与拉格朗日定理,对于右陪集关系 可类似地讨论。 根据左陪集的定义，可得到下列结论： (1) 若为群的子群，则h为中的左陪集。 因为若e是的幺元，则 eh=eh|hh=h。 (2) 若是群的子群，对任意ag，则aah。 因为eh，故a=aeah。,6.1.4 子群、陪集与拉格朗日定理,(3) 若是群的子群，则h的每个左陪集与h的基数相同。 令f(ah)h如下: f(h)= ah， 其中hh 则f是双射。 满射是显然的，下面再证它是单射。 若ah1 = ah2，h1，h2h，则根据群的可约律知h1 = h2，即f(h1)= f(h2)导出h1 = h2。,6.1.4 子群、陪集与拉格朗日定理,例6.21 设是对称群的子群，其中h = p1，p4，则群中的h的左陪集有： p1h = p1p1，p4 = p1p1，p1p4 = p1，p4 p2h = p2p1，p4 = p2p1，p2p4 = p2，p6 p3h = p3p1，p4 = p3p1，p3p4 = p3，p5 p4h = p4p1，p4 = p4p1，p4p4 = p4，p1 p5h = p5p1，p4 = p5p1，p5p4 = p5，p3 p6h = p6p1，p4 = p6p1，p6p4 = p6，p2,6.1.4 子群、陪集与拉格朗日定理,因此，h的左陪集共有三个： p1h = p4h = p1，p4 p2h = p6h = p2，p6 p3h = p5h = p3，p5 对称群中的h的右陪集类似求出： hp1 = hp4 = p1，p4 hp2 = hp5 = p2，p5 hp3 = hp6 = p3，p6 可见，h的左陪集不同于它的右陪集。,6.1.4 子群、陪集与拉格朗日定理,例6.22 设是群的子群，其中h = 0，2，则群中的h的左陪集有： 0h = 0+40，2 = 0+40，0+42 = 0，2 1h = 1+40，2 = 1+40，1+42 = 1，3 2h = 2+40，2 = 2+40，2+42 = 2，0 3h = 3+40，2 = 3+40，3+42 = 3，1 因此，h的左陪集有二，它们是0，2和1，3，由于是abel群，故h的右陪集同样也是0，2和1，3。,6.1.4 子群、陪集与拉格朗日定理,对于右陪集有同样结论，不重复了。下面介绍有关左陪集的定理。 定理6.31 若是群的子群，则ah = h ah。 证明：充分性：若ah，则ahh，这是因为是群，h对于具有封闭性。反向的包含也成立，因为若hh，则h=a(a-1h)，此处a-1hh，这是因为是群的子群且a，hh。由此导出hah。因此，hah。故ah = h。 必要性：假设ah = h，因为幺元eh，故a=aeah= h，即得，ah。,6.1.4 子群、陪集与拉格朗日定理,下面的定理提供了对于两个左陪集相等的一种判断。 定理6.32 若是群的子群，则 ah=bhb-1ah 证明：充分性：若b-1ah，则由定理6.31可得 (b-1a) hh 由此对任意h1h，存在h2h，使得 h2=(b-1a) h1 ，于是 a h1= bh2 这表明在左陪集ah中的每个元素a h1与一个形如bh2的元素相等，即它亦在左陪集bh中，故 ah=bh,6.1.4 子群、陪集与拉格朗日定理,必要性：假设ah=bh，则若a h1为ah中任意元素，必存在h2h，使得a h1= bh2 于是b-1a= h2h1-1，又因为h2h1-1h，故b-1ah。 推论6.2 左陪集ah中的任何元素a1均可决定该陪集，或者说，陪集中的每个元素都可作为陪集的代表。 因为若a1ah，则存在h1h，使得a1 = ah1，于是，a-1a1 = h1h。 再根据定理6.32知，a1h=ah。,6.1.4 子群、陪集与拉格朗日定理,定理6.33 若是群的子群，则或者ahbh = 或者ah = bh。 证明：假设ahbh ，则存在cahbh，因而存在h1h，使得c= ah1，同理对某个h2h，有c= bh2，因此 ah1= bh2 于是 b-1a= h2h1-1 因为 h2h1-1h，故b-1ah。 故由定理6.32得：ah = bh。,6.1.4 子群、陪集与拉格朗日定理,由于g中每个元素a必在h的左陪集ah中，从定理6.33又知道，g中每个元素恰好能属于h的某个左陪集中。因此h的左陪集簇构成g的划分，而且划分中每个块与h具有相同的元素个数。因此可得下面定理： 定理6.34 若是群的子群，则中的h的左陪集簇构成g的一种划分。并且称它为g的对于h的左陪集划分。,6.1.4 子群、陪集与拉格朗日定理,例6.23 设是群的子群，其中h=4i|iz=，-8，-4，0，4，8，则中的h的不同左陪集是： 0h = 0+h = ，-8，-4，0，4，8， = 0 1h = 1+h = ，-7，-3，1，5，9， = 1 2h = 2+h = ，-6，-2，2，6，13， = 2 3h = 3+h = ，-5，-1，3，7，11， = 3 可见，h的左陪集恰是四个模4同余类。此时z对于h的左陪集划分为 z = 0123,6.1.4 子群、陪集与拉格朗日定理,假若群为有限群，其子群是，且|g|=n，|h|=m，则g的对于h的左陪集划分可表为g = a1ha2hakh，其中k为不同的左陪集个数，称为h在g中的指标。由于每个左陪集皆有m个元素，故g具有km个元素，即n = mk，这便得到著名拉格朗日(j.l.lagrange)定理： 定理6.35 若是有限群的子群，且|g| = n，|h| = m，则n = mk，其中kz+，z +是正整数集合。 本定理表明，任何有限群的阶均可被其子群的阶所整除。,6.1.4 子群、陪集与拉格朗日定理,推论6.3 任何其阶为素数的有限群必无真子群。 最后应用陪集概念来定义一个子群，它是非常重要的子群正规子群或不变子群。 定义6.23 设是群的子群，若对于g中任意元a，有ah = ha，则称是群的正规子群。 由本定义可知，每个abel群的子群均为正规子群。 请注意，正规子群导出可交换性是比较弱的。这是因为，若hh，并非总有ah = ha，而仅仅知道必存在h1，h2h，使得ah1 = h2a。,6.1.4 子群、陪集与拉格朗日定理,例如，例6.23中的是群的正规子群，也不难证明是对称群的正规子群。 下面定理提供了简便的手段判定一已知子群是否为正规子群，而且它很有用途。 定理6.36 给定群的子群，它是群的正规子群 (a)(ag aha-1h)。 证明：充分性：假设对任意ag，有aha-1h，往证ah = ha。,6.1.4 子群、陪集与拉格朗日定理,令ah ah。因为aha-1h，则对某个h1h，有 aha-1= h1 于是 ah=(aha-1) a = h1a 可见 h1 aha ，故 ahha 只要注意：a-1ha= a-1h(a-1)-1h，可类似地证明haah，于是ah = ha。 必要性：假设对每个ag，有ahha且aha-1 aha-1。则因ah = ha，必存在h1h，使得 ah= h1a,6.1.4 子群、陪集与拉格朗日定理,于是 aha-1=(h1a) a-1=h1 因此 aha-1h，故aha-1h。 本节一开始已经讨论了，一个群的子群所确定的左陪集关系是等价关系。一般地说，它未必是同余关系，那么，满足怎样的条件才能是同余关系呢？下面定理回答了这个问题。 定理6.37 群的正规子群所确定的左(或右)陪集关系 (或 )是同余关系。,6.1.4 子群、陪集与拉格朗日定理,证明：令a b且p q，往证(ap) (bq)。由左陪集关系 的定义可知 b-1ah，q-1ph 因此，存在 h1，h2h，使得 b-1a=h1，q-1p=h2 而 (bq) -1(ap)= (q-1b-1)(ap)= q-1(b-1 a)p= q-1h1p， 又因为是正规子群，故对任意h1p，必存在h3h，使得 h1p= ph3,6.1.4 子群、陪集与拉格朗日定理,由此得 q-1h1p= q-1ph3= h2h3h 故 (bq) -1(ap) h