离散数学第七讲群、环、域.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, ，1,6.7 群,不是群（0无逆元）,是群,是群,定义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一般地不能用作群的二元运 算, 因为如果载体多于一个元素, 逆运算不能定义。,群是半群和独异点的特定情况, 有关半群和独异点的性 质在群中也成立, 群的性质还有： 定理1: 如果G , *是一个群, 则对

3、于任何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) 同理可证。,一、群的定义和性质,定理 2： 如果G, *是一个群, 则对于任何a、b、 cG, 证： 因为群

4、的每一元素都有逆元, 本定理显然成立。 定理3：么元是群中唯一等幂元素。 证：如果x是等幂元素, 则 么元是群中唯一等幂元素。,一、群的定义和性质,定理4：群G , *的运算表中的每一行或每一列都是G中 元素的一个置换。 证：i)首先, 证明运算表中的行或列所含G的一个元素不可 能多于一次。（反证法） 如果对应于元素a的那一行中有两个元素都是k, 即a * b1=a * b2=k,根据定理2有b1=b2, 而b1b2,矛盾。 对于列也一样可以证明。,一、群的定义和性质,定理4：群G , *的运算表中的每一行或每一列都是G中 元素的一个置换。 证： ii)其次, 要证明G的每一个元素都在运算表的

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

6、* 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。 推论： 思考：一阶群、二阶群、三阶群各有几个？,一、群的定义和性质,为了继续介绍群的性质, 我们首先定义群G, *的 任意元素a的幂。 如果nN, 则 由以上定义可知, 对任意m、kI, am, ak都是有意义 的,另外群中结合律成立, 不难证明以下指数定律成立:,(m、kI) (m、kI),一、群的定义和性质,定义4:设G ,*是一个群, 且aG, 如果存在正整数n使 an=e, 则称

7、元素的阶是有限的, 最小的正整数n称为元 素a的阶。 如果不存在这样的正整数n, 则称元素a具 有无限阶。 如： 群的么元e的阶？ 群I,+中各元素的阶？,一、群的定义和性质,1,么元0的阶为1，非零元素有无限阶。,定理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

8、=e的最小正整数, 而0tn, 所以t=0, 得k=mn。证毕。 这样, 如果an =e, 并且没有n的因子d(1dn)能使ad =e, 则n是元素a的阶。例如, 如果a8 =e, 但a2 e, a4 e, 则 8必定是a的阶。,一、群的定义和性质,定理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。,一、群的定义和性质,定理9: 在有限群G , * 中, 每一个元素

9、具有一有限阶, 且阶数至多是|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|。 证毕。,一、群的定义和性质,定义5：给定n个元素组成的集合A, A上的置换所构成的群 称为n次置换群; A上所有置换构成的群称为n次对 称群。 定义6：在群G, *中,如果存在一个元素gG, 对于每 一个元素aG都有一个相应的iI, 能把a表示成 gi形式,则称G , *是

10、一个循环群，g是该循环 群的生成元。 例： I,+ A=0,1,2,3,A,+4 定理10：每个循环群是可交换的。,二、置换群和循环群,是循环群，生成元为1，-1,是循环群，生成元为1和3,定理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形

11、式, 但rm, 所以G中至多有m个不同元素, 这与|G|=n矛盾。 所以gm=e而mn是不可能的。,二、置换群和循环群,定理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。 证毕。,二、置换群和循环群,定义7: 设G , *

12、是一个群, S是G的非空子集, 并满足以 下条件: (1) 对任意a、bS有a * bS ; (2) 对任意aS有a-1 S; (3) eS, e是G ,*的么元, 则称S ,*是G ,*的子群。 如 I ,+是R ,+的子群， N ,+不是。 任意群G ,*均有两个平凡子群：e,*和G ,*。,三、子群,定理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 , *的子群。,三、子群,定理13

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 , *的子群。,三、子群,定理14：设G, *是一个群, S是G的非空子集，如果对于 S中的任意元素a、b, 有a * b-1S, 那么S , * 是G , *的子群

14、。 证: (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 。 得证。,三、子群,定义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)

15、=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。,四、群同态,可以省略,定义9:设h是从G , *到H , *的群同态,如果G的 一个子集K 的每一元素都被映入H的么元eH , 再没有 其它元素映入eH , 则K 称为同态h的核, 记为ker(h)。 定理15：从群G , *到群H, *的同态h的核ker(h) 形成群G , *的子群。 证：(a) 如果a、bker(h),

16、 那么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)。 证毕。,四、群同态,定义10：设H , *是群G , *的子群, 我们称集合 aH = a * h|hH 为元素aG 所确定的子群 H , *的左陪集。元素a称为左陪集aH 的表示 元素。我们称集合Ha=h * a|hH 为元素aG 所确定的子群H , *的右陪集。元素a称为右 陪集Ha的表示元素。

17、注意：表示元素一定在它所确定的陪集内。 表示元素相同的左右陪集未必相等。,五、陪集和拉格朗日定理,例：是的子群， 则 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的 直线。,五、陪集和拉格朗日定理,定理16：设H , *是群G , *的子群,aH 和bH是任意 两个左陪集, 那么, 或 aH =bH 或 aHbH = 。 证：

18、假定 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 = 不可兼得。 所以定理得证。,五、陪集和拉格朗日定理,定理17：H的任意陪集的大小是相等的。 证： 对任意aG, h1，h2 H, 若 h1h2

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

20、。 (2)如果G是有限群，|G|=n，|H|=m，则 m|n(m整除n)。,五、陪集和拉格朗日定理,定理19：（拉格朗日定理）设是群的一个子群， (1)R= | aG, bG且a-1*bH是G中的一个 等价关系。对于aG，若记aR=x | xG且 R,则aR=aH。,五、陪集和拉格朗日定理,定理19：（拉格朗日定理）设是群的一个子群， (1)R= | aG, bG且a-1*bH是G中的一个 等价关系。对于aG，若记aR=x | xG且 R,则aR=aH。,五、陪集和拉格朗日定理,定理19：（拉格朗日定理）设是群的一个子群， (2)如果G是有限群，|G|=n，|H|=m，则 m|n(m整除n)。

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

22、都是生成元。,五、陪集和拉格朗日定理,定义11：设H , *是群G , *的子群, 对任意元素 aG, 如果aH =Ha, 则H , *称为正规子群。 注意:(1)定义中的aH =Ha是指对每一h1H, 都存在h2H, 使a * h1=h2 * a, 并不要求对每一 h H 有 a * h =h * a。 (2)所有阿贝尔群的子群都是正规子群; 所有平凡子群都是正规子群。,六、正规子群和商群,定理20：正规子群的不同陪集都是G的同余类。 证明：设aH 和bH是两个陪集, a1是aH中任一元素, b1是bh 中任一元素, 现证明a1 * b1全都在H的同一陪集中。 设 a1 = a * h1 ，

23、b1 = b * h2， hiH a1*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诱导出的陪集关系是同余关系。,六、正规子群和商群,定义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 ,

24、*关于正规子群H , *的商群。 习惯记为A/H =G/H, *,六、正规子群和商群,作业：P206 1，2，3，7，9，11，16,一、环的定义及性质 定义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 环和域,是环,是环,定理1：设R, +, 是个环, 0是加法么

25、元, 则对任意 元素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,一、环的定义及性质,定义2 ：R, +,是一个环, 如果对于某些非零元素 a,bR, 能使ab=0, 则称R, +, 是含零 因子环, a、b称为零因子, 无零因子的环称为无 零因子环。 如N8 , +8 ,8是含零因子环。,一、环的定义及性质,定理2：环R, +, 无零因子, 当且仅当R, +, 满足 可约律。 证： 设a, b, cR是任意元素, 且a0。 (1

26、)必要性。 如果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, +, 无零因子。,一、环的定义及性质,定义3：给定环R, +,如果R, 是可交换的, 称 R, +, 是可交换环; 如果R, 是含么半 群, 称R, +, 是含么环。如果R, +, 是可交换的, 含么而无零因子环, 则称它是整环。 例2: (1)I, +, (2)N7 ,

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

28、只有一个元素故不是域; k=ab时, 则akb=0, a、b是零因子, 所以Nk, +k, k不是域。,二、域的定义,例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都存在一逆元。,二、域的定义,例4：Nk, +k, k是一个域, 当且仅当k是质数。 证 ：证明对每一元素aNk-0都存在一逆元。 设b,c是Nk-0中

29、任二元素,bc,现证akbakc。 用反证法, 若akb=akc=r, 则ab = nk+r, ac = mk+r 不妨设bc, 于是nm, ab-ac = nk-mk a(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是阿贝尔群。,二、域的定义,例4：Nk, +k, k是一个域, 当且仅当k是质数。 证 ： (3) 乘法k对加法+k可分配, 对任意元素a, b, cNk, 有 又k可交换, 所以乘法在加法上可分配。 综上，当k是质数时, Nk, +k, k是域。,二、域的定义,作业：P212 1，3，7，13,