《离散数学PPT教学 群论》由会员分享,可在线阅读,更多相关《离散数学PPT教学 群论(34页珍藏版)》请在金锄头文库上搜索。
1、 欢迎进入离 散 数 学 第 八章 群 论近世代数 第八章 群 论8.1 半群和独异点8.2 群、阿贝尔群及性质结束8.3 循环群和置换群8.4 群的同态和同构例1a)N,x0,1,x是半群,是独异点,且是R,x的子半群,子独异点,R,-不是半群* a b a a b b a b8.1 半群和独异点b) 设s=a,b,*定义如右表: 即a,b都是右零元x,y,zs x*ys 运算封闭 x*(y*z)=x*z=z(x*y)*z=z结合律成立s,*是一半群,该半群称为二元素右零半群 1、有限半群必有等幂元 证明:设s,*是半群有限集,需证 as,有a*a=abs ,因为运算封闭, b2=b*bs
2、b3,b4ss有限 ,j,j 有bi=bj bi =bj =bj- i * bi令p=ji 当qi ,bq=bpbq ()又p1 k 有k p i 由() bkp=bp*bkp=bP*(bP*bkp)=bkpbkp令a=bkps 则a*a=a bkp是等幂元二、半群的性质二、半群的性质2、独异点运算表中任何两行两列均不相同证明:设独异点的么元为e,a,bs,aba*eb*e ,运算表中,两行不同,由,任意性,运算表中任两行不同 e*ae*b ,运算表中,二列 不同由,任意性,运算表中任两列不同二、半群的性质二、半群的性质3、若s,*的么元为e,a,bs,若a,b均有逆元,则 a)(a-1)-1
3、=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=eb-1*a-1是a*b的右逆元又(b-1*a-1)*(a*b)=b-1*(a-1*a)*beb-1*a-1是a*b的左逆元(a*b)-1=b-1*a-1返回目录群论是抽象代数发展充分的一个分支,广泛应用 于计算,通讯,计算机科学,是我们这一章的重点 。8.2 群、阿贝尔群及性质一、 群的定义1、定义:对二元运算*满足下列四条性质的代数系统A=G,*,称为群1) 运算封闭
4、,即a,b,G, a*b G2) 结合律,即a,b,cG,a*(b*c )= (a*b)*c3) 存在么元e,即aG,e*a=a*e=a4) G中每个元素存在逆元即aG,a-1 G,使a*a-1=a-1*a=e若G是有限集,称G,*为有限群,G 称为群的阶数,若G是无限集,称G,*为 无限群一、 群的定义2、有限群3、阿贝尔群若*满足交换律,称G,*为阿贝尔群, 或可交换群或加法群,(此时,*符号可用 +代替,a-1可写为-a,么元e可写为0)例1I,+是一个群。考虑是否为阿贝尔群 ?证明:I,+运算封闭 普通加法+满足结合律 其中0为么元 aI,-a是a的逆元一、 群的定义b)Q+,x是阿贝
5、尔群,Nk,+k是阿贝尔群,Nk,xk 不是群(0没有逆元)一、 群的定义c) 设P是集合A的双射函数集合,则P,复合运算是一个群,但不是阿贝尔群d)运算max,min一般不能用作群的二元运算 因为对应运算max,min,逆元不存在 二、 群的性质二、 群的性质1、有关半群和独异点的性质在群中全部成立,(a*b)-1=b-1*a-1 阿贝尔群半群 独异点群若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*b
6、b)略 二、 群的性质2、Th2: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二、 群的性质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的一个 置换 定理:群G,*的运算表中的每一行或每一列是G中元素的置换证: 先证运算表中每一行(列)中的元素不能出现二次(单射)
7、二、 群的性质若a*b1=a*b2=k,且b1b2,与可约性矛盾 再证G中任一元素在任一行(列)中均出现(满 射)考察对应于a的那一行,bG,则b=a*(a-1*b) b出现在a那一行,由,任意性得证因G,*中有么元,任二行(列)均不相同 (即各个置换均不相同) 证毕6、 有限群举例 一阶群仅有1个 二阶群仅有1个 三阶群仅有1个 四阶群仅有2个(证略) * e e e* e a e e a a a e *e a b e e a b a a b e b b e a二、 群的性质7、Th1:群中不可能有零元证:当G=1,它的唯一元素视为么元当G1且G,*有零元,则xG,都有x*=*x=e无逆元,
8、这与G是群矛盾二、 群的性质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*bG,*是阿贝尔群二、 群的性质a,bG,有(a*b)*(a*b)=(a*a)*(b*b)必要性:若G,*是阿贝尔群,则a,bG,*b=b*aa*(a*b)*b=a*(b*a)*a(a*a)*(b*b)=(a*b)*(a*a) 二、 群的性质8.3 循环群和置换群一.循环群定义定义:设是一个群,若存在gG,使得 aG,iI(I为整
9、数集),有a=gi,则称 是一个循环群, g是的生成元。可 称是由g生成的, 。二.性质1. 每个循环群是阿贝尔群证:设g是的生成元则a,bG, a=gr, b=gsa*b=gr*gs=gr+s=gs*gr=b*a下一页2.是由g生成的有限循环群,若 |G|=n,即g的阶为n,则G=g1,g2,gn证:a) 证g的阶为n。先证:若m是一个群,故必有么元, gn=eG=g0 ,g1 , g2 , ,gn-1下一页例1例1.a)是无限循环群,其中-1,1均是生成元b)是无限循环群,其中-5,5是均生成元c)Nk=0,k-1,是有限循环群,其中1是 生成元,与k互质的任一数也是生成元,这里Nk=0,
10、k -1,x是I中的模k等价类+k定义为:x+ky=x+y+4 0 1 2 3 30 0 1 2 3 32=6=2 1 1 2 3 0 33=5=1 2 2 3 0 1 34=4=0 3 3 0 1 2下一页二.循环群性质例2.设G=,,证是循环群 * 证: 2=, 3=,4=运算表可改写如下:* 2 3 2 3 2 3 2 2 2 3 3 2由上表看出G=,是一个循环群下一页置换群三、置换群一.复合运算1.定义:一个具有n个元素的集合S,将S上所有n!个 不同的置换所生成的集合记作Sn例:A=1,2有二个置换1= 1 2 2= 1 21 2 2 1A=1,2,3有6个置换P0 p1 p2 p
11、3 p4 p5 123 123 123 123 123 123 123 213 321 132 231 312下一页二元运算二元运算pipj表示先进行置换pj,再进行置换pi,称左复合pipj表示先进行置换pi,再进行置换pj,称右复合例:左复合123 123 123 =321 213 231右复合123 123 123 =321 213 312下一页是一个群 证:(1)封闭性p1,p2Sn,须证p1p2Sn若a,bS且ab则当a,b被p2置换为c,d时,必有cd当c,d被p1置换为e,f时,必有efp1p2将S中任二个不同元素映射到S中的二个不同元素p1p2Sn(有限集A上的单射必为满射)(
12、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. 所以,是一个群下一页例:p1= 123 p1-1= 123 p1p1-1= 123312 231 123 四、置换群与对称群定义:的任何子群称为集合S上的一个置换群称为S上的对称群。 例:设S=1,2,3,试写出S的所有的置换群及对称群 解: S上对称群Sn=p0,p1,p2,p3,p4,p5置换群以p
13、1为生成元的对称群,以p2为生成元对称群以p3为生成元对称群,以p4为生成元对称群。下一页同态与同构8.4 群的同态与同构一.同构与同态1.同构定义代数A=和A=若1)存在从S到S的双射函数h2)a,bS有h(a*b)=h(a)*h(b)则称代数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的零元下一页一.同构与同态例1.证同构于证: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)同构于下一页一.同构与同态例2.证明和不同构 证:反证法设h是到的一个同构映射,x2则: 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)=11至少是两个元素的象, 这与h是双射矛盾 和不同构下一页证:G=g0,g1,g2,g3, f: