《第8章群和半群ppt课件.ppt》由会员分享，可在线阅读，更多相关《第8章群和半群ppt课件.ppt（66页珍藏版）》请在三一办公上搜索。
1、第8章 半群和群,8.1 半群和独异点,半群和独异点的定义子半群和子独异点半群同态和独异点同态,代数系统A=S，*，若*是满足结合律的二元运算，则A称为半群。若*同时满足交换律，则称为阿贝尔半群。存在幺元的半群称为独异点，也称(含)幺半群，单位半群。若*同时满足交换律，则称为阿贝尔独异点。,8.1.1 半群和独异点的定义,例是最典型的半群，只满足结合律是最典型的独异点，只满足结合律，有幺元是独异点，可交换独异点是独异点，不满足交换律，部分元素有逆元,b)设S=a，b，*定义如右表：即a，b都是右零元 x,y,zS x*yS 运算封闭 x*（y*z）=x*z=z（x*y）*z=z 结合律成立 S
2、，*是一半群，该半群称为二元素右零半群,半群的性质:1.独异点运算表中任何两行或两列均不相同证明：设独异点的幺元为e，a,bS，若ab a*eb*e,S,*运算表中a,b两行不同，由a,b任意性，运算表中任两行不同 e*ae*b,S,*运算表中a,b两列不同，由a,b任意性，运算表中任两列不同,2.有限半群一定含有幂等元 证明：设S，是半群,S是有限集，需证aS，有aa=a bS，因为运算封闭，b2=bbS,b3,b4S S有限 i，jN+，ji 有bi=bj bi=bj=bj-ibi 令p=ji bi=bj=bp*bi 当qi,bq=bpbq(1)又p1 k N+有kpi 由(1)bkp=b
3、pbkp=bp(bpbkp)=bp(bp(bpbkp)=.=bpbp bkp=bkpbkp 令a=bkpS 则aa=a a是幂等元.,k个,8.1.2 子半群和子独异点,设为半群，T为S的非空子集。若T关于*封闭，则称是的子半群，记为TS。设为独异点，T为S的非空子集。若T关于*封闭，且eT,则称是的子独异点，记为TS。例 半群有子半群，独异点有子独异点,独异点,设A，则 是的子独异点；独异点，设T=s|s|10,是的子半群，但不是子独异点；独异点，设nN=nm|m N,是的子独异点；独异点，其中S上的单射集合，满射集合和双射集合都是的子独异点。,定理 设为可交换独异点，T为S中所有幂等元的
4、集合，则是的子独异点。证：(1)T对于*的封闭性a,bT,a*a=a,b*b=b,又由于*是可交换、可结合的，所以(a*b)*(a*b)=a*(b*a)*b=a*a*b*b=a*b(a*b)也是幂等元，a*bT.(2)eT.e*eT,eT.所以是的子独异点。,8.1.3 半群同态和独异点同态,定义设和是半群，函数h:S1S2.若a,bS1,有h(a*b)=h(a)h(b),则称h为从到的半群同态。设和是独异点，函数h:M1M2.若a,bM1,有h(a*b)=h(a)h(b),且h(e1)=e2,则称h为从到的独异点同态。例8.1.4,设=a,b,上的函数h:*定义如下：i)h()=;ii)h(
5、as)=abh(s),h(bs)=bah(s)则h是上的自同态。证：对s用归纳法证明s,t*:h(st)=h(s)h(t)i)s=时,h(t)=h(t)=h(t)=h()h(t),ii)假设s=x时成立，即h(xt)=h(x)h(t)则当s=ax时，h(st)=h(axt)=abh(xt)=abh(x)h(t)=h(ax)h(t)=h(s)h(t)当s=bx时同理可证。s,t*:h(st)=h(s)h(t)又h()=，所以h是*上的自同态。,定理 半群与同态证：定义h:SSS为：aS,h(a)=fa,其中fa:SS,xS,fa(x)=a*x,则h是同态映射，因为：a,bS,cSh(a*b)(c
6、)=fa*b(c)=(a*b)*c=a*b*c(h(a)h(b)(c)=(fafb)(c)=fa(fb(c)=a*(b*c)=a*b*c所以h(a*b)(c)=(h(a)h(b)(c)，即h(a*b)=h(a)h(b).所以h是同态映射，半群与同态。例8.1.5,定理（独异点表示定理）任意独异点都同构于某一变换独异点设S为集合，的子独异点称为变换独异点。任意独异点都同构于某一变换独异点。证：设是任一独异点。(1)作h:SSS,a fa,则由定理8.1.2知，h是半群同态。又因为h(e)=fe=1S,所以h是从到的独异点同态。,(2)(同构)i)h是单射.a,bS,若h(a)=h(b)，即fa=
7、fb,则fa(e)=fb(e),a*e=b*e,即a=b.ii)h不一定是满射，其值域h(S)SS 但，由定理7.2.3，是的子代数。（h(S)对合成运算封闭）又 1S=h(e)h(S),是的子独异点。h:S SS，限制在h(S)上为满射。所以，同构于。,8.2 群的定义及性质,群的定义群的判定群的性质元素的阶,8.2.1 群的定义,代数系统G，*，其中二元运算*满足下列性质：1)结合律，即a,b,cG，a*（b*c）=（a*b）*c2)存在幺元e，即aG，e*a=a*e=a3)G中每个元素存在逆元 即aG，a-1 G,使a*a-1=a-1*a=e则G，*称为群。,若G是有限集，称G，*为有限
8、群，G称为群的阶；若G是无限集，称G，*为无限群。,有限群,阿贝尔群,若*满足交换律，称G，*为阿贝尔群，或可交换群或加法群。此时，*符号可用+代替；a-1可写为-a；a的n次幂an可写为na;幺元e可写为0,不是群，除0以外的元素无逆元是阿贝尔群不是群，0没有逆元不是群，0没有逆元是阿贝尔群是阿贝尔群，,不是群，0没有逆元设B(X,X)是集合X上的双射函数集合，则是一个群，但不是阿贝尔群 对行列式非零的n阶方阵M，存在M-1,MM-1=M-1M=1n,N4=0,1,2,3,模4加法+4的运算表如下：,+4,是阿贝尔群是阿贝尔群m+kn=m+n mod k-m=k-m；m+k(k-m)=(m+
9、k-m)mod k=0计算机中的整数实际上就是Nk;-m的补码是k-m，这样：n-232m=(n-m)mod 232=(n+(232-m)mod 232=n+232(232-m),8.2.2 群的判定,定理1 设为半群，若(1)有左单位元，即 elG,aG,el*a=a;(2)每个元素有左逆元，即 aG,alG,al*a=el,则是群。,证：i)先证 aG,a*al=el.alG,aG,a*al=el.则a*al=el*(a*al)=(a*al)*(a*al)=a*(al*a)*al=a*el*al=a*al=elii)再证el也是右单位元 aG,a*el=a*(al*a)=(a*al)*a=
10、el*a=a所以el是单位元；aG，al是a的逆元。所以是群。,定理2 设是半群，若a,bG，方程a*x=b,y*a=b在G中都有解，则是群。证：（利用定理1）i)取aG，设el为y*a=a的一个解，el*a=a;bG,设c为a*x=b的一个解，a*c=b,则，el*b=el*(a*c)=(el*a)*c=a*c=b,所以，el是左单位元。ii)aG,令al为y*a=el的一个解，则al*a=el，则al是a的左逆元。由定理1,是群。,定理3 设是有限半群，若G中消去律成立，则是群。证：设G=a1,a2,.,an.i)先证a,bG，a*x=b在G中有解。作G=a*a1,a*a2,.,a*an,
11、则GGi,j,若aiaj，则a*aia*aj(消去律的逆否)，则|G|=n,所以G=G,因为bG,故bG即存在kN,1是群。,有关半群和独异点的性质在群中全部成立,8.2.3 群的性质,若群G，*的幺元为e,a，bG，则 a)（a-1）-1=a；b)（a*b）-1=b-1*a-1 证明：a)a*a-1=e a是a-1的左逆元 a-1*a=e a是a-1的右逆元(a-1)-1=a b)(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e b-1*a-1是a*b的右逆元 又(b-1*a-1)*(a*b)=b-1*(a-1*a)*be b-1*a-1是a*b的左逆元(a*b
12、)-1=b-1*a-1,若G，*是一个群，则a，bG a）存在唯一的x，使得a*x=b b）存在唯一的y，使得y*a=b 证：a）存在性:令x=a-1*b，则a*(a-1*b)=a*a-1*b=e*b=b 唯一性:若a*x=b，则a-1*a*x=a-1*b x=a-1*b b）同理可证。,幺元是群中唯一的幂等元 证：若x是幂等元，则：x=e*x=（x-1*x）*x=x-1*（x*x）=x-1*x=e 群中消去律成立证：群中每个元素都可逆，则每个元素都可约，所以消去律成立。,群中不可能有零元.证：若|G|=1，它的唯一元素视为幺元 若|G|1，且有零元，则xG，都有x*=*x=e 无逆元，这与G
13、是群矛盾.,群G，*的运算表中的每一行(列)是G中元素的一个置换。(定义：有限集合S到S的一个双射，称为S的一个置换.),证：i)先证一个元素在运算表中每一行(列)中不能出现两次(单射)若a*b1=a*b2=k，且b1b2，与可约性矛盾 ii)再证G中任一元素在任一行（列）中均出现（满射）考察对应于a的那一行，bG，则b=a*（a-1*b）b出现在a那一行.由a,b任意性,得证iii)因G，*中有幺元，任两行（列）均不相同（即各个置换均不相同）证毕。,有限群举例 一阶群仅有1个 二阶群仅有1个 三阶群仅有1个 四阶群仅有2个,例 设G，*是一个群，则G，*是阿贝尔群的充要条件是:a，bG，有(
14、a*b)*(a*b)=(a*a)*(b*b)证：充分性：若a，bG，因为满足(a*b)*(a*b)=(a*a)*(b*b)所以，a-1*(a*b)*(a*b)*b-1=a-1*(a*a)*(b*b)*b-1 b*a=a*b G，*是阿贝尔群必要性：若G，*是阿贝尔群，则a，bG，a*b=b*aa*（a*b）*b=a*（b*a）*a（a*a）*（b*b）=（a*b）*（a*a）,8.2.4 元素的阶,元素a的幂的定义 给定群,aG,a的整数次幂可以归纳定义为:a0=e,an+1=ana,nN a-n=a-1 a-1 a-1=(a-1)n,nI+对m用归纳法可证：aman=am+n(m,nI),对
15、k用归纳法可证：(am)k=amk(m,kI),元素的阶的定义 设是一个群,aG,若存在正整数n,使an=e,满足该等式的最小n的称为元素a的阶。并称元素a具有有限阶n,|a|=n.若不存在这样的正整数n,则称元素a具有无限阶。,例.群的幺元e的阶为1,且幺元是阶为1的唯一元素。中除以0外,其余元素的阶为无限阶。,|0|=1,|1|=4,|2|=2,|3|=4.,关于元素阶的一些性质若群,aG具有有限阶n,则若ak=e,当且仅当k是n的倍数.证明:若k是n的倍数,即k=mn,mI 则ak=amn=(an)m=em=e 反之,若ak=e,设k=mn+t,0tn,mI at=ak-mn=ak*(a
16、n)-m=e*(e)-m=e 由定义知:n是使an=e的最小正整数 因0tn t=0 k=mn.证毕,群中任一元素和它的逆元具有同样的阶.证:设aG具有有限阶n,a-1具有有限阶m(a-1)n=a-1n=(an)-1=e-1=e mn am=(a-1)m)-1=e-1=e nm m=n.若a具有无限阶，易证a-1也具有无限阶。,在有限群中,每一元素具有有限阶,且阶数至多为|G|。证:aG,则在序列a,a2,a3,a|G|+1中至少有两个元素相同,不妨设ar=as(1sr|G|+1)则 a-r=a-s 则 ar-s=ar*a-s=ar*a-r=e 所以，元素a的阶数至多为 r-s|G|,设是群，
17、aG,且|a|=n，则|ak|=,(kI).特别地，|a-1|=|a|.,8.3 子群和群同态,子群群同态,8.3.1 子群,设是群，H是G的非空子集，若也是群，则称 是的子群，记为HG.若H是G的真子集，则称 是的真子群，记为H，有子群和.称为平凡子群。,例 a)是的子群,I为整数集b)不是的子群,N是自然数集c)是的子群,子群的性质设是群，HG，则(1)H的单位元就是G的单位元；(2)aH，a在H中的逆元就是a在G中的逆元。,子群的判定是群,H是G的非空子集，则 HG当且仅当(1)a,bH,有a*b H,(2)aH,a-1H.,证:必要性(1)由子群的封闭性可证；(2)aH，a-1=aH-
18、1,a-1H.充分性a)运算封闭a,bT，由前提，a*bTb)结合律继承成立c)aH，a-1H,a*a-1HeHd)a H，有a-1H 是群,是的子群.,是群,H是G的非空子集，则 HG当且仅当a,bH,有a*b-1 H.,证：必要性 HG，a,bH,b-1 H，所以a*b-1 H.充分性 因为a,bH,a*b-1H，i)H非空，有aH,则a-1 H,所以e=a*a-1H.ii)aH，a-1=e*a-1H.iii)a,bH,b-1H,所以a*(b-1)-1=a*b H,所以是群,HG.,设是群,HG,H是有限集,若a,bT,有a*bH,则是的子群证:设|H|=n aH,则a,a2=a*a,.，
19、an,an+1H 因为|H|=n i,j,有 ai=aj,ji aj-i=e,a*aj-i-1=e a)若j-i1 则a的逆元为aj-i-1 H b)若j-i=1,则ai=ai*a,所以a=e,a的逆元为a H,是的子群.,设,是群的子群,试证:是的子群.,证:i)a,bHK,则a,bH 是的子群 a*bH,a,bK,是的子群 a*bK a*bHK ii)aHK,则aH a-1H aK a-1K a-1HK 是的子群.,8.3.2 群同态,设和是群，函数h:GG,若a,bG,有h(a*b)=h(a)*h(b),则称h为从到的群同态。若h是双射，则称h是群同构。设和是群，单位元分别是e和e,作h
20、:GG,ae,则a,bG，有 h(a*b)=e=e*e=h(a)*h(b)h为从到的群同态,称为零同态。例8.3.4,8.4 循环群,生成子群：设是群，aG，令(a)=ai|iI.易证(a)G.(证明封闭性，幺元，逆元)(a)称为由a生成的子群。循环群:设是一个群,若存在aG,使得G=(a),则称是一个循环群,a是的生成元。称是由a生成的。,是无限循环群,其中-1,1均是生成元是无限循环群,其中-5,5是均生成元是有限循环群,其中1是生成元，k为正整数 与k互质的任一数也是生成元Nk=0,k-1 x是整数x的模k等价类,+k定义为:x+ky=x+y 是有限循环群,其中1是生成元 与k互质的任一
21、p对应的p也是生成元,+4 0 1 2 30 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2,3也为生成元：32=6=233=9=134=12=0,循环群的性质：每个循环群是阿贝尔群.证:设g是的生成元 则a,bG,a=gr,b=gs,r,s I a*b=gr*gs=gr+s=gs*gr=b*a,定理8.4.2循环群的结构由其生成元的阶决定.设群G=(a),(1)若|a|无限，则G同构于;(2)若|a|=n,nI+,则G同构于.同阶的循环群必同构,推论1设群G=(a),(1)若G为无限群，则|a|无限，且 G=.,a-2,a-1,e,a,a2,.;(2)若|G|=n
22、,nI+,则|a|=n，且G=e,a,a2,.,an-1.循环群的阶与其生成元的阶相同。推论2 G为n阶有限群，aG，则G=(a)当且仅当|a|=n.,定理8.4.3(循环群的生成元)设群G=(a),(1)若G为无限群，则G只有两个生成元a和a-1(2)若|G|=n，则G=(ar)当且仅当(r,n)=1,证：(1)因为a是生成元，a=(a-1)-1,ai=(a-1)-i，所以，a-1也是生成元。设am G是生成元，则存在t I,(am)t=a,则amt-1=e,因为群G的阶无限，则其生成元a的阶也为无限，所以mt-1=0,m=t=1或m=t=-1.故G只有两个生成元a和a-1.,(2)必要性设
23、G=(ar),因为|G|=n,则其生成元|ar|=n。又|a|=|G|=n，则又|ar|=故(r,n)=1.充分性设(r,n)=1，则存在s,t I，使得rs+nt=1，于是a=ars+nt=(ar)s*(an)t,又|a|=|G|=n，a=(ar)s，故ar也是生成元。,定理8.4.4 设群G=(a),eHG,am是H中a的最小正幂，则(1)H=(am)(2)若G为无限群，则H为无限群。(3)若|G|=n,则m|n且|H|=n/m。,证：(1)aiH,设i=qm+r(0=rm),则ar=ai*(am)-q,所以ar H,又am是H中a的最小正幂，r=0 aiH,ai=(am)q,故H=(am)。(2)G无限，则|a|无限，则|am|无限，所以H无限。(3)若|G|=n,则|a|=n,所以an=eH,又am是H的生成元，an=(am)k,即m|n而|am|=n/m.,定理8.4.5 设群G=(a),|G|=n,则对于n的每一正因子d,有且仅有一个d阶子群。证：存在性|G|=n，则|a|=n，an=e.H=an/d,a2n/d,a3n/d,.,adn/d=e是d阶子群。唯一性设H=(am)也是一个d阶子群，则|am|=d,amd=e n|md,n/d|m.an/d是H的生成元，所以 am H,则H H.|H|=|H|=d,故H=H。,
