离散数学 第五、六、七讲 群、环、域.ppt

《离散数学 第五、六、七讲 群、环、域.ppt》由会员分享，可在线阅读，更多相关《离散数学 第五、六、七讲 群、环、域.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、群的定义和性质 定义1：群G,*是一代数系统,其中二元运算*满足:(1)运算*是可结合的；(2)存在么元e；(3)对每一aG,存在一个元素a-1,使 a-1*a=a*a-1=e 如 Q,1 Q+,1 1,，16.7 6.7 群群不是群（0无逆元）是群是群1 定义2：如果G是有限集合,则称G,*是有限群;如果G 是无限集合,则称G,*是无限群。有限群G的 基数|G|称为群的阶数。如 1,是有限群，阶数为1；I,+是无限群。定义3：如果群G,*中的运算*是可交换的,则称 该群为可交换群,或称阿贝尔群。如 I,+是阿贝尔群。一、群的定义和性质2 例1：Q+,1 设A是任一集合,P表示A上的双射函

2、数集合,”。”表示函数合成，“-1”表示求逆运算，P,。,-1,IA N,max 代数Nk,+k,-1,0 代数Nk,k一、群的定义和性质是Abel群是一个群,通常这个群不是阿贝尔群。是群,这里x-1=k-x不是群,因为0元素没有逆元 不是群。运算max和min一般地不能用作群的二元运 算,因为如果载体多于一个元素,逆运算不能定义。3 群是半群和独异点的特定情况,有关半群和独异点的性质在群中也成立,群的性质还有：定理1:如果G,*是一个群,则对于任何a、bG,(a)存在一个唯一的元素x,使得a*x=b。(b)存在一个唯一的元素y,使得y*a=b。证：证：(a)至少有一个x满足a*x=b,即x=

3、a-1*b,因为 a*(a-1*b)=(a*a-1)*b=e*b=b 如果x是G中满足a*x=b的任意元素,则 x=e*x=(a-1*a)*x=a-1*(a*x)=a-1*b 所以,x=a-1*b是满足a*x=b的唯一元素。(b)同理可证。一、群的定义和性质4 定理 2：如果G,*是一个群,则对于任何a、b、cG,证：因为群的每一元素都有逆元,本定理显然成立。定理3：么元是群中唯一等幂元素。证：如果x是等幂元素,则 么元是群中唯一等幂元素。一、群的定义和性质5 定理4：群G,*的运算表中的每一行或每一列都是G中 元素的一个置换。证：i)i)首先首先,证明运算表中的行或列所含证明运算表中的行或列

4、所含G G的一个元素不可的一个元素不可 能多于一次。（反证法）能多于一次。（反证法）如果对应于元素a的那一行中有两个元素都是k,即a*b1=a*b2=k,根据定理2有b1=b2,而b1b2,矛盾。对于列也一样可以证明。一、群的定义和性质6 定理4：群G,*的运算表中的每一行或每一列都是G中 元素的一个置换。证：ii)ii)其次其次,要证明要证明G G的每一个元素都在运算表的每一行的每一个元素都在运算表的每一行 和每一列中出现。和每一列中出现。考察对应于元素a的那一行,设b是G中的任一元素,由于b=a*(a-1*b),所以b必定出现在对应于a的那一行中。对于列也可同样证明。一、群的定义和性质7

5、定理4：群G,*的运算表中的每一行或每一列都是G中 元素的一个置换。证：iii)iii)最后最后,因为因为G G,*,*中含有么元中含有么元,所以没有两行所以没有两行 或两列是完全相同的。或两列是完全相同的。综合以上结果便得出:运算表中每一行都是G的元素的 一个置换,并且每一行都是不同的置换。同样的结论适合 于列。证毕。定理5：群中没有零元。一、群的定义和性质8 定理6:如果G,*是一个群,则对于任何a、bG,(a*b)-1=b-1*a-1证:由于 (a*b)*(b-1*a-1)=a*(b*b-1)*a-1 =a*a-1=e 而这里逆元是唯一的,所以(a*b)-1=b-1*a-1。推论：思考：

6、一阶群、二阶群、三阶群各有几个？一、群的定义和性质9 为了继续介绍群的性质,我们首先定义群G,*的 任意元素a的幂。如果nN,则 由以上定义可知,对任意m、kI,am,ak都是有意义 的,另外群中结合律成立,不难证明以下指数定律成立:(m、kI)(m、kI)一、群的定义和性质10 定义4:设G,*是一个群,且aG,如果存在正整数n使 an=e,则称元素的阶是有限的,最小的正整数n称为元 素a的阶。如果不存在这样的正整数n,则称元素a具 有无限阶。如：群的么元e的阶？群I,+中各元素的阶？一、群的定义和性质1么元0的阶为1，非零元素有无限阶。11 定理7：如果群G,*的元素a拥有一个有限阶n,则

7、ak=e,当且仅当k是n的倍数。证:充分性：设k、m、n是整数。如果k=mn,则ak=amn=(an)m=e m=e 必要性：假定ak=e,且k=mn+t,0tn,于是 at=ak-mn=ak*a-mn=e*(an)-m=e*e-m=e 由定义可知,n是使an=e的最小正整数,而0tn,所以t=0,得k=mn。证毕。这样,如果an=e,并且没有n的因子d(1dn)能使ad=e,则n是元素a的阶。例如,如果a8=e,但a2 e,a4 e,则8必定是a的阶。一、群的定义和性质12 定理8:群中的任一元素和它的逆元具有同样的阶。证证:设aG具有有限阶n,即an=e,因此 (a-1)n=a-1n=(a

8、n)-1=e-1=e 如果(a-1)的阶是m,则mn。另一方面 am=(a-1)m-1=e-1=e 因而nm,故m=n。一、群的定义和性质13 定理9:在有限群G,*中,每一个元素具有一有限阶,且阶数至多是|G|。证证:设a是G,*中任一元素。在序列a,a2,a3,a|G|+1中至少有两元素是相等的,不妨设ar=as,这里1sr|G|+1。因为 ar-s=ar*a-s=ar*a-r=ar-r=a0=e 所以,a的阶数至多是r-s|G|。证毕。一、群的定义和性质14 定义5：给定n个元素组成的集合A,A上的置换所构成的群 称为n次置换群;A上所有置换构成的群称为n次对 称群。定义6：在群G,*中

9、,如果存在一个元素gG,对于每 一个元素aG都有一个相应的iI,能把a表示成 gi形式,则称G,*是一个循环群，g是该循环 群的生成元。例：I,+A=0,1,2,3,A,+4定理10：每个循环群是可交换的。二、置换群和循环群是循环群，生成元为1，-1是循环群，生成元为1和315 定理11：设G,*是由gG生成的有限循环群,如果|G|=n,则gn=e,G G=g,g2,g3,gn=e e 且n是使gn=e的最小正整数。证:(1)先证 n是使gn=e的最小正整数。假定有正整数mn使 gm=e,则对G中任一元素gk,设k=mq+r,0rm,于是 gk=gmq+r=(=(gm)q *gr=e*=e*g

10、r=gr 这意味着G中每一元素都可写成gr形式,但rm,所以G中至多有m个不同元素,这与|G|=n矛盾。所以gm=e而mn是不可能的。二、置换群和循环群16 定理11：设G,*是由gG生成的有限循环群,如果|G|=n,则gn=e,G G=g,g2,g3,gn=e e 且n是使gn=e的最小正整数。证:(2)再证 g,g2,g3,gn中的元素全不相同。若有gi=gj,不妨设ij,于是gj-i=e。但j-in,这与n是使gn=e的最小正整数矛盾。由于G,*是群,所以G=g,g2,g3,gn,又由(1)得gn=e。证毕。二、置换群和循环群17 定义7:设G,*是一个群,S是G的非空子集,并满足以 下

11、条件:(1)对任意a、bS有a*bS;(2)对任意aS有a-1 S;(3)eS,e是G,*的么元,则称S,*是G,*的子群。如 I,+是R,+的子群，N,+不是。任意群G,*均有两个平凡子群：e,*和G,*。三、子群18 定理12：设G,*是个群,SG,如果(1)若a、bS,则a*bS,(2)若aS,则a-1 S。那么S,*是G,*的子群。证：证：对任意元素aS,由(2)得a-1 S,再由(1)得a*a-1 =eS。所以,S,*是G,*的子群。三、子群19 定理13：设G,*是一个有限群有限群,如果对任意元素a、bS,有a*bS,那么S,*是G,*的子群。证证:设a是S 的任一元素,则aG,根

12、据定理“有限群中每一个元素有一有限阶”可知 a具有阶数r,由于S 对运算*的封闭性,所以a1,a2,ar全在S中,即 ar-1=ar*a-1=e*a-1=a-1 也在S中,这就证明了若aS,则a-1S。根据上面定理12,得出S,*是G,*的子群。三、子群20 定理14：设G,*是一个群,S是G的非空子集，如果对于 S中的任意元素a、b,有a*b-1S,那么S,*是G,*的子群。证证:(1)S 非空，存在aS,a*a-1 S,又 a*a-1=e,e S；(2)对任意 aS,eS,又 e*a-1 S；a-1 S；(3)对任意 a、bS,b-1 S,a*(b-1)-1 S,a*(b-1)-1=a*b

13、,a*bS。得证。三、子群21 定义8:设G,*和H,*是两个群,映射h:G H 称为从G,*到H,*的群同态,如果对任 意a、bG,(1)h(a*b)=h(a)*h(b)(2)h(eG)=eH (3)h(a-1)=h(a)-1(2)h(eG)=h(eG*eG)=h(eG)*h(eG)群中只有么元是等幂的,h(eG)=eH。(3)h(a)*h(a-1)=h(a*a-1)=h(eG)=eH h(a-1)*h(a)=h(a-1*a)=h(eG)=eH h(a-1)=h(a)-1。四、群同态可以省略22 定义9:设h是从G,*到H,*的群同态,如果G的 一个子集K 的每一元素都被映入H的么元eH,再

14、没有 其它元素映入eH,则K 称为同态h的核,记为ker(h)。定理15：从群G,*到群H,*的同态h的核ker(h)形成群G,*的子群。证：证：(a)如果a、bker(h),那么h(a)=h(b)=eH。h(a*b)=h(a)*h(b)=eH*eH=eH 所以,a*bker(h),即ker(h)对运算*封闭。(b)如果aker(h),则h(a-1)=h(a)-1=eH-1=eH,所以,a-1ker(h)。证毕。四、群同态23 定义10：设H,*是群G,*的子群,我们称集合 aH=a*h|hH 为元素aG 所确定的子群 H,*的左陪集。元素a称为左陪集aH 的表示 元素。我们称集合Ha=h*a

15、|hH 为元素aG 所确定的子群H,*的右陪集。元素a称为右 陪集Ha的表示元素。注意：表示元素一定在它所确定的陪集内。表示元素相同的左右陪集未必相等。五、陪集和拉格朗日定理24 例：是的子群，则 3I=I，5I=I，0.5I=+0.5,+1.5,+2.5,。例：设G=RR，R为实数集，G上的一个二元运算+定义为 +=，显然，是一个 具有么元的阿贝尔群。设H=|y=2x，则是的子群。对于G,H关于的左陪集为H。几何意义为：G是笛卡尔平面，H是通过原点的直线 y=2x，陪集H是通过点的且平行于H的 直线。五、陪集和拉格朗日定理25 定理16：设H,*是群G,*的子群,aH 和bH是任意 两个左陪

16、集,那么,或 aH=bH 或 aHbH=。证证：假定 aHbH ,则存在元素c aHbH,于是存在h1、h2H,使c=a*h1=b*h2,因此,a=b*h2*h1-1。设x是aH 中任一元素,于是存在h3H 使x=a*h3,因而x=b*h2*h1-1*h3,因为h2*h1-1*h3 H,所以x是bH中的一个元素。同理可证bH 的任一元素是aH 中的一个元素。这样,aH=bH。又aH 和bH 都是非空集合,aH=bH和aHbH=不可兼得。所以定理得证。五、陪集和拉格朗日定理26 定理17：H的任意陪集的大小是相等的。证证：对任意aG,h1，h2 H,若 h1h2，必有a*h1 a*h2,aH中没

17、有相同的元素，|aH|=|H|。a是任意的，H的任意陪集的大小是相等的。注：H的左陪集集合构成G的一种划分，且划分块大小相同。五、陪集和拉格朗日定理27 定理18：设H,*是群G,*的子群，于是baH,当且仅当 a-1*b H。证证：baH iff 存在 hH,使 b=a*h iff h=a-1*b iff a-1*b H五、陪集和拉格朗日定理28 定理19：（拉格朗日定理）设是群的一个子群，(1)R=|aG,bG且a-1*bH是G中的一个 等价关系。对于aG，若记aR=x|xG且 R,则aR=aH。(2)如果G是有限群，|G|=n，|H|=m，则 m|n(m整除n)。五、陪集和拉格朗日定理2

18、9 定理19：（拉格朗日定理）设是群的一个子群，(1)R=|aG,bG且a-1*bH是G中的一个 等价关系。对于aG，若记aR=x|xG且 R,则aR=aH。五、陪集和拉格朗日定理30 定理19：（拉格朗日定理）设是群的一个子群，(1)R=|aG,bG且a-1*bH是G中的一个 等价关系。对于aG，若记aR=x|xG且 R,则aR=aH。五、陪集和拉格朗日定理31 定理19：（拉格朗日定理）设是群的一个子群，(2)如果G是有限群，|G|=n，|H|=m，则 m|n(m整除n)。五、陪集和拉格朗日定理32 推论1：任何质数阶的群不可能有非平凡子群。证明：如果有非平凡子群，则该子群的阶必定是原来群

19、的阶 的一个因子，这就与原来群的阶是质数相矛盾。推论2：在有限群G，*中，任何元素的阶必是|G|的一个 因子。证明：设任意aG,r是a的阶，则 e,a1,a2,ar-1，*是G，*的子群。所以 r 必是|G|的一个因子。五、陪集和拉格朗日定理33 推论3：一个质数阶的群必定是循环群，并且任一与么元不 同的元素都是生成元。证明：对任意aG,ae,因为该群为质数阶的群，故a的阶必为|G|，所以 G=e,a1,a2,a|G|-1 即该群必是循环群且任一与么元不同的元素都是生成元。五、陪集和拉格朗日定理34 定义11：设H,*是群G,*的子群,对任意元素 aG,如果aH=Ha,则H,*称为正规子群。注

20、意:(1)定义中的aH=Ha是指对每一h1H,都存在h2H,使a*h1=h2*a,并不要求对每一 h H 有 a*h=h*a。(2)所有阿贝尔群的子群都是正规子群;所有平凡子群都是正规子群。六、正规子群和商群35 定理20：正规子群的不同陪集都是G的同余类。证明：设aH 和bH是两个陪集,a1是aH中任一元素,b1是bh 中任一元素,现证明a1*b1全都在H的同一陪集中。设 a1=a*h1，b1=b*h2，hiHa1*b1=(a*h1)*(b*h2)=(a*h1)*(h3*b)=a*(h1*h3)*b =a*(h4*b)=a*b*h5 因此,所有a1*b1都在陪集(a*b)H 中。再者,容易证

21、明a1、a2aH 时有a1-1、a2-1 a-1H。因此由正规子群H诱导出的陪集关系是同余关系。六、正规子群和商群36 定义12：设H,*,-1,e是群A=G,*,-1,e的正规 子群。H 的陪集关系记为。则A/=G/,*,-1,H,这里 G/=aH|aG aH*bH=(a*b)H aH-1=a-1H 称为群G,*关于正规子群H,*的商群。习惯记为A/H=G/H,*六、正规子群和商群37 作业：P206 1，2，3，7，9，11，1638 一、环的定义及性质定义1：若代数系统R,+,的二元运算+和具有下列 三个性质:(1)R,+是阿贝尔群(加法群),(2)R,是半群,(3)乘法在加法+上可分配

22、。即对任意元素a、b、cR,有 a(b+c)=ab+ac,(b+c)a=ba+ca 则称R,+,是个环环。例1：(1)I,+,(2)R(x),+,R(x)是所有实系数的x的多 项式集合。6.8 6.8 环和域环和域是环是环39 定理定理1 1：设R,+,是个环,0是加法么元,则对任意 元素a,b,cR有(a)a0=0a=0(b)(-a)b=a(-b)=-(ab)(c)(-a)(-b)=ab(d)a(b-c)=ab-ac(e)(b-c)a=ba-ca一、环的定义及性质40 定义定义2 2：R,+,是一个环,如果对于某些非零元素 a,bR,能使ab=0,则称R,+,是含零 因子环,a、b称为零因子

23、,无零因子的环称为无 零因子环。如N8,+8,8是含零因子环。一、环的定义及性质41 定理定理2 2：环R,+,无零因子,当且仅当R,+,满足 可约律。证：证：设a,b,cR是任意元素,且a0。(1)必要性。如果ab=ac,那么ab-ac=0,a(b-c)=0,由于无零因子,所以b-c=0,即b=c。所以R,+,满足可约律。(2)充分性。如果bc=0且b0,那么bc=b0,由于满足可约 律,所以c=0。又如果bc=0且c0,那么bc=0c,由于满足 可约律,所以,b=0。可见R,+,无零因子。一、环的定义及性质42 定义定义3 3：给定环R,+,如果R,是可交换的,称 R,+,是可交换环;如果

24、R,是含么半 群,称R,+,是含么环。如果R,+,是可交换的,含么而无零因子环,则称它是整环。例2:(1)I,+,(2)N7,+7,7 (3)N8,+8,8 一、环的定义及性质是整环是整环不是整环43 定义定义4 4：如果F,+,是整环,|F|1,F-0,是群,则F,+,是域。域的定义也可这样叙述:满足 (1)F,+是阿贝尔群,(2)F-0,是阿贝尔群,(3)乘法对加法可分配的代数系统F,+,称为域。例3:(1)Q,+,(2)R,+,(3)I,+,二、域的定义是域是域不是域（I-0,不是阿贝尔群）44 例4：Nk,+k,k是一个域,当且仅当k是质数。证证：必要性。若k不是质数,那么 k=1 或

25、 k=ab。k=1时,N1=0。只有一个元素故不是域;k=ab时,则akb=0,a、b是零因子,所以Nk,+k,k不是域。二、域的定义45 例4：Nk,+k,k是一个域,当且仅当k是质数。证证：充分性。(1)显然Nk,+k是阿贝尔群。(2)证明Nk-0,k是群:(i)对Nk-0中任意元素a和b,akb0,所以 Nk-0对k封闭。(ii)k是可结合运算。(iii)运算k的么元是1。(iv)k是可交换的。(v)对每一元素aNk-0都存在一逆元。二、域的定义46 例4：Nk,+k,k是一个域,当且仅当k是质数。证证：证明对每一元素aNk-0都存在一逆元。设b,c是Nk-0中任二元素,bc,现证akb

26、akc。用反证法,若akb=akc=r,则ab=nk+r,ac=mk+r 不妨设bc,于是nm,ab-ac=nk-mka(b-c)=(n-m)k (1)因a和(b-c)都比k小而k是质数,(1)式不可能成立。这样就证明了若bc,则akbakc。于是a和Nk-0中的k-1个数的模k乘法,其结果都不相 同,但又必须等于1,2,k-1中的一个,故必存在一 元素b,使akb=1。这就证明了任意元素a存在逆元。由(i)(v)得Nk-0,k是阿贝尔群。二、域的定义47 例4：Nk,+k,k是一个域,当且仅当k是质数。证证：(3)乘法k对加法+k可分配,对任意元素a,b,cNk,有 又k可交换,所以乘法在加法上可分配。综上，当k是质数时,Nk,+k,k是域。二、域的定义48 作业：P212 1，3，7，1349