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

一、群的定义和性质 定义1：群G,*是一代数系统,其中二元运算*满足:(1)运算*是可结合的；(2)存在么元e；(3)对每一aG,存在一个元素a-1,使 a-1*a=a*a-1=e 如 Q,1 Q+,1 1,，1,6.7 群,不是群（0无逆元）,是群,是群,1,*,定义2：如果G是有限集合,则称G,*是有限群;如果G 是无限集合,则称G,*是无限群。有限群G的 基数|G|称为群的阶数。如 1,是有限群，阶数为1；I,+是无限群。定义3：如果群G,*中的运算*是可交换的,则称 该群为可交换群,或称阿贝尔群。如 I,+是阿贝尔群。,一、群的定义和性质,2,*,例1：Q+,1 设A是任一集合,P表示A上的双射函数集合,”。”表示函数合成，“-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=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)首先,证明运算表中的行或列所含G的一个元素不可 能多于一次。（反证法）如果对应于元素a的那一行中有两个元素都是k,即a*b1=a*b2=k,根据定理2有b1=b2,而b1b2,矛盾。对于列也一样可以证明。,一、群的定义和性质,6,*,定理4：群G,*的运算表中的每一行或每一列都是G中 元素的一个置换。证：ii)其次,要证明G的每一个元素都在运算表的每一行 和每一列中出现。考察对应于元素a的那一行,设b是G中的任一元素,由于b=a*(a-1*b),所以b必定出现在对应于a的那一行中。对于列也可同样证明。,一、群的定义和性质,7,*,定理4：群G,*的运算表中的每一行或每一列都是G中 元素的一个置换。证：iii)最后,因为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。推论：思考：一阶群、二阶群、三阶群各有几个？,一、群的定义和性质,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,则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=(an)-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,*中,如果存在一个元素gG,对于每 一个元素aG都有一个相应的iI,能把a表示成 gi形式,则称G,*是一个循环群，g是该循环 群的生成元。例：I,+A=0,1,2,3,A,+4定理10：每个循环群是可交换的。,二、置换群和循环群,是循环群，生成元为1，-1,是循环群，生成元为1和3,15,*,定理11：设G,*是由gG生成的有限循环群,如果|G|=n,则gn=e,G=g,g2,g3,gn=e 且n是使gn=e的最小正整数。证:(1)先证 n是使gn=e的最小正整数。假定有正整数mn使 gm=e,则对G中任一元素gk,设k=mq+r,0rm,于是 gk=gmq+r=(gm)q*gr=e*gr=gr 这意味着G中每一元素都可写成gr形式,但rm,所以G中至多有m个不同元素,这与|G|=n矛盾。所以gm=e而mn是不可能的。,二、置换群和循环群,16,*,定理11：设G,*是由gG生成的有限循环群,如果|G|=n,则gn=e,G=g,g2,g3,gn=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的非空子集,并满足以 下条件:(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,根据定理“有限群中每一个元素有一有限阶”可知 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,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,再没有 其它元素映入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|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是任意 两个左陪集,那么,或 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中没有相同的元素，|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)。,五、陪集和拉格朗日定理,29,*,定理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：任何质数阶的群不可能有非平凡子群。证明：如果有非平凡子群，则该子群的阶必定是原来群的阶 的一个因子，这就与原来群的阶是质数相矛盾。推论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,*称为正规子群。注意:(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 中。再者,容易证明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，16,38,*,一、环的定义及性质定义1：若代数系统R,+,的二元运算+和具有下列 三个性质:(1)R,+是阿贝尔群(加法群),(2)R,是半群,(3)乘法在加法+上可分配。即对任意元素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 环和域,是环,是环,39,*,定理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：R,+,是一个环,如果对于某些非零元素 a,bR,能使ab=0,则称R,+,是含零 因子环,a、b称为零因子,无零因子的环称为无 零因子环。如N8,+8,8是含零因子环。,一、环的定义及性质,41,*,定理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：给定环R,+,如果R,是可交换的,称 R,+,是可交换环;如果R,是含么半 群,称R,+,是含么环。如果R,+,是可交换的,含么而无零因子环,则称它是整环。例2:(1)I,+,(2)N7,+7,7(3)N8,+8,8,一、环的定义及性质,是整环,是整环,不是整环,43,*,定义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 或 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,现证akbakc。用反证法,若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，13,49,*,