离散数学教学群论

离散数学教学群论第1页，课件共34页，创作于2023年2月近世代数—第八章群论§8.1半群和独异点§8.2群、阿贝尔群及性质结束§8.3循环群和置换群

§8.4群的同态和同构第2页，课件共34页，创作于2023年2月例1．a)〈N，x〉〈{0，1}，x〉是半群，是独异点,且是〈R，x〉的子半群,子独异点,〈R，-〉不是半群

*abaabbab§8.1半群和独异点b)设s={a，b}，*定义如右表：即a，b都是右零元∵x,y,zs①x*ys∴运算封闭②x*（y*z）=x*z=z

（x*y）*z=z∴结合律成立

∴〈s，*〉是一半群，该半群称为二元素右零半群

第3页，课件共34页，创作于2023年2月1、有限半群必有等幂元

证明：设〈s，*〉是半群有限集，需证as，有a*a=abs，因为运算封闭，b2=b*bsb3，b4…ss有限ｉ，j，j>ｉ有bi=bjbi=bj=bj-i*bi令p=j－i当q≥i,bq=bp·bq（１）又∵p≥1∴k有kp≥i

由（１）bkp=bp*bkp=bP*(bP*bkp)=…=bkp＊bkp∴令a=bkps则a*a=a

∴bkp是等幂元二、半群的性质

二、半群的性质第4页，课件共34页，创作于2023年2月2、独异点运算表中任何两行两列均不相同证明：设独异点的么元为e，a，bs，ab∵a*eb*e＜ｓ，＊＞运算表中ａ，ｂ两行不同，由ａ，ｂ任意性，运算表中任两行不同∵e*ae*b＜ｓ，＊＞运算表中ａ，ｂ二列不同由ａ，ｂ任意性，运算表中任两列不同．二、半群的性质第5页，课件共34页，创作于2023年2月二、半群的性质3、若〈s，*〉的么元为e,a，bs，若a，b均有逆元，则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=ab)∵(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）*b＝e∴b-1*a-1是a*b的左逆元∴（a*b）-1=b-1*a-1返回目录第6页，课件共34页，创作于2023年2月

群论是抽象代数发展充分的一个分支，广泛应用于计算，通讯，计算机科学，是我们这一章的重点。§8.2群、阿贝尔群及性质一、群的定义

1、定义：对二元运算*满足下列四条性质的代数系统A=〈G，*〉，称为群

1)运算封闭，即a,b,G，a*bG2)结合律，即a,b,cG，a*（b*c）=（a*b）*c3)存在么元e，即aG，e*a=a*e=a4)G中每个元素存在逆元即aG，a-1G,使a*a-1=a-1*a=e第7页，课件共34页，创作于2023年2月若G是有限集，称〈G，*〉为有限群，｜G｜称为群的阶数，若G是无限集，称〈G，*〉为无限群

一、群的定义2、有限群3、阿贝尔群

若*满足交换律，称〈G，*〉为阿贝尔群，或可交换群或加法群，（此时，‘*’符号可用‘+’代替，a-1可写为-a，么元e可写为0）第8页，课件共34页，创作于2023年2月例1．〈I，+〉是一个群。考虑是否为阿贝尔群？证明：①〈I，+〉运算封闭②∵普通加法+满足结合律③其中0为么元④

aI，-a是a的逆元一、群的定义第9页，课件共34页，创作于2023年2月b)〈Q+，x〉是阿贝尔群,

〈Nk，+k〉是阿贝尔群,〈Nk，xk〉不是群（∵0没有逆元）一、群的定义

c)设P是集合A的双射函数集合，则〈P，复合运算〉是一个群，但不是阿贝尔群d）运算max，min一般不能用作群的二元运算因为对应运算max，min，逆元不存在第10页，课件共34页，创作于2023年2月二、群的性质二、群的性质1、有关半群和独异点的性质在群中全部成立,（a*b）-1=b-1*a-1

阿贝尔群半群独异点群第11页，课件共34页，创作于2023年2月若〈G，*〉是一个群，则a，bGa）存在唯一的x，使得a*x=bb）存在唯一的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*bb）略二、群的性质2、Th2:第12页，课件共34页，创作于2023年2月3、

可逆必可约，反之不成立

Th3:（a）a*b=a*c=>b=c

（b）b*a=c*a=>b=c证：∵a*b=a*c=>a-1*（a*b）=a-1*（a*c）

=>b=c二、群的性质第13页，课件共34页，创作于2023年2月4、Th5:么元是群中唯一的等幂元

证：若x是等幂元素，则：x=e*x=（x-1*x）*x=x-1*（x*x）＝x-1*x=e

二、群的性质5、Th4:群〈G，*〉的运算表中的每一行或每一列是G中元素的置换

定义：有限集合s到s的一个双射，称为s的一个置换

第14页，课件共34页，创作于2023年2月定理：群〈G，*〉的运算表中的每一行或每一列是G中元素的置换证：①先证运算表中每一行（列）中的元素不能出现二次（单射）

二、群的性质∵若a*b1=a*b2=k，且b1b2，与可约性矛盾②再证G中任一元素在任一行（列）中均出现（满射）∵考察对应于a的那一行，bG，则b=a*（a-1*b）∴b出现在a那一行，由ａ，ｂ任意性得证．③因〈G，*〉中有么元，∴任二行（列）均不相同（即各个置换均不相同）证毕第15页，课件共34页，创作于2023年2月6、有限群举例①

一阶群仅有1个②

二阶群仅有1个

③

三阶群仅有1个

④四阶群仅有2个（证略）*eee*eaeeaaae*eabeeabaabebbea二、群的性质第16页，课件共34页，创作于2023年2月7、Th1:群中不可能有零元证：当│G│=1，它的唯一元素视为么元当G>1且〈G，*〉有零元，则xG，都有x*=*x=e

无逆元，这与G是群矛盾二、群的性质第17页，课件共34页，创作于2023年2月8、设〈G，x〉是一个群，则〈G，*〉是阿贝尔群的充要条件是证：充分性：若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，*〉是阿贝尔群二、群的性质a，bG，有（a*b）*（a*b）=（a*a）*（b*b）第18页，课件共34页，创作于2023年2月必要性：若〈G，*〉是阿贝尔群，则a，bG，ａ*b=b*a∴a*（a*b）*b=a*（b*a）*a∴（a*a）*（b*b）=（a*b）*（a*a）二、群的性质第19页，课件共34页，创作于2023年2月

§8.3循环群和置换群一.循环群定义定义:设<G,*>是一个群,若存在gG,使得aG,iI（I为整数集），有a=gi,则称<G,*>是一个循环群,g是<G,*>的生成元。可称<G,*>是由g生成的,。二.性质1.每个循环群是阿贝尔群证:设g是<G,*>的生成元则a,bG,a=gr,b=gsa*b=gr*gs=gr+s=gs*gr=b*a下一页第20页，课件共34页，创作于2023年2月2.<G,*>是由g生成的有限循环群,若|G|=n,即g的阶为n,则G={g1,g2,,gn}

证:a)证g的阶为n。先证：若m<n,则gm≠e

（反证法）若m<n,且gm=e,gkG,k=mq+r,0≤r<m∴gk=gmq+r=gmqgr=gr∴G中最多有m个不同元素,这与|G|=n矛盾，所以g的阶为nb)证G中的元素全不相同证:若gi=gj,1≤i<j≤ngj-i=e∵0≤j-i<n∴这与a)矛盾

c)∵giG且|G|=n,1≤i≤n∴G={g1,,gn}∵<G,*>是一个群,故必有么元，∴gn=eG={g0,g1,

g2,

,gn-1}下一页第21页，课件共34页，创作于2023年2月例1例1.a)<I,+>是无限循环群,其中-1,1均是生成元

b)<{5j|jI},+>是无限循环群,其中-5,5是均生成元

c)Nk={[0],,[k-1]}，<Nk,+k>是有限循环群,其中[1]是生成元,与k互质的任一数也是生成元，这里Nk={[0],,[k-1]},[x]是I中的模k等价类+k定义为:[x]+k[y]=[x+y]+4[0][1][2][3] [3][0][0][1][2][3] [3]2=[6]=[2] [1][1][2][3][0] [3]3=[5]=[1] [2][2][3][0][1] [3]4=[4]=[0] [3][3][0][1][2]下一页二.循环群性质第22页，课件共34页，创作于2023年2月例2.设G={α,β,γ,δ}，证<G,*>是循环群*αβγδααβγδββαδγγγδβαδδγαβ证:∵γ2=β,γ3=δ,γ4=α∴运算表可改写如下:*αγγ2γ3ααγ

γ2γ3γγγ2γ3αγ2γ2γ2αγγ3γ3α

γγ2

由上表看出G={α,β,γ,δ}是一个循环群下一页第23页，课件共34页，创作于2023年2月置换群三、置换群一.复合运算1.定义:一个具有n个元素的集合S,将S上所有n!个不同的置换所生成的集合记作Sn①例:A={1,2}有二个置换1=122=1212

21

A={1,2,3}有6个置换

P0p1p2p3p4p5123

123123123123123123213321132231312下一页第24页，课件共34页，创作于2023年2月二元运算②二元运算pipj表示先进行置换pj,再进行置换pi,称左复合pipj表示先进行置换pi,再进行置换pj,称右复合例:左复合123123123

=321213231右复合123123123

=321213312下一页第25页，课件共34页，创作于2023年2月<Sn,>是一个群证:(1)封闭性p1,p2Sn，须证p1p2Sn∵若a,bS且ab则当a,b被p2置换为c,d时,必有cd

当c,d被p1置换为e,f时,必有efp1p2将S中任二个不同元素映射到S中的二个不同元素p1p2Sn(有限集A上的单射必为满射)(2)运算满足结合律

p1，p2，p3Sn,xS有p3(x)=y，p2(y)=z,p1(z)=u,

则(p1p2)p3(x)=u,p1(p2p3)(x)=p1(z)=up1(p2p3)=(p1p2)p3(3)恒等置换为么元

(4)pSn,xS,存在逆元p-1,其中若p(x)=y则p-1(y)=x.所以，<Sn,>是一个群下一页第26页，课件共34页，创作于2023年2月例:p1=123p1-1=123p1p1-1=123312231123四、置换群与对称群定义:<Sn,>的任何子群称为集合S上的一个置换群<Sn,>称为S上的对称群。例:设S={1,2,3}，试写出S的所有的置换群及对称群解:S上对称群Sn={p0,p1,p2,p3,p4,p5}置换群以p1为生成元<{p1,p0},>的对称群,以p2为生成元<{p2,p0},>对称群以p3为生成元<{p3,p0},>对称群,以p4为生成元<{p4,p5,p0},>对称群。下一页第27页，课件共34页，创作于2023年2月同态与同构

§8.4群的同态与同构一.同构与同态1.同构定义代数A=<S,*>和A’=<S’,*’>若1)存在从S到S’的双射函数h2)a,bS有h(a*b)=h(a)*’h(b)则称代数A与代数A’是同构的,记为<A,*>≌<A’,*’>注:1)A与A’同构,则调换符号能从A得到A’,可以认为它们是相同的代数;2)若e是A的么元,则h(e)是A’的么元

∵yS’,xS,y=h(x)y*’h(

e)=h(x)

*’h(e)=h(x*e)=y

若o是A的零元,则h(o)是A’的零元下一页第28页，课件共34页，创作于2023年2月一.同构与同态例1.证<R+,>同构于<R,+>证:i)令h:R+R,h(x)=㏒x

则因对数函数单调增h是单射yR,x=2y使y=㏒2y=h(x)h是满射h是从R+到R的双射

ii)h(ab)=㏒（ab）=㏒a+㏒b=h(a)+h(b)<R+,,1>同构于<R,+,0>下一页第29页，课件共34页，创作于2023年2月一.同构与同态例2.证明<N,+>和<I+,x>不同构证:反证法设h是<N,+>到<I+,x>的一个同构映射,x>2

则:p=h(x)=h(x+0)=h(x)h(0)1)7=h(7)=h(7+0)=h(7)h(0)h(7)=1或h(0)=12)7=h(7)=h(6+1)=h(6)h(1)h(6)=1或h(1)=1

1至少是两个元素的象,这与h是双射矛盾

<N,+>和<I+,x>不同构下一页第30页，课件共34页，创作于2023年2月证:G={g0,g1,g2,g3,}f:NG,f(n)=gnf(n1+n2)=gn1+n2=gn1*gn2=f(n1)*f(n2)一、同构与同态

例3.证明<N,+>同构于无限阶循环群<G,*>

2.同构关系是一个等价关系3.同态定义设A=<S,*>和A’=<S’,*’>若(1)h:SS’是一函数(2)a,bS，有h(a*b)=h(a)*’h(b)则称h是从A到A’的一个同态函数,若h是单射,满射,双射,则分别称h是单一同态,满同态,同构。特别地，若A=A’,且h是同构,称h是自同构下一页第31页，课件共34页，创作于2023年2月例1例1.a)fk:II,fk(x)=kx，其中I为整数集合∵fk(x1+x2)=k(x1+x2)=kx1+kx2=fk(x1)+fk(x2)fk是从<I,+>到<I,+>的自同态,若k0,则fk是单一同态,若k=1,则fk是<I,+>到<I,