离散数学jme-3半群与群1

1、第三部分 代数结构School of Microelectronics, Fudan UniversityJing Minge代数结构1.2.3.4.代数系统半群与群环与域格与代数2第二章半群与独异点群的定义与性质子群半群与群2.4 陪集与日定理正规子群与商群群的同态与同构循环群与置换群2.1 半群与独异点主要内容：半群与独异点的定义，及其子代数的说明。半群与独异点的幂运算。半群与独异点的同态。半群与独异点定义2.1(1)设V是代数系统，为二元运算，如果运算是可结合的，则称V为半群（semigroup）。(2)设V是半群,若eS是关于运算的元,则称V是独异点（monoid），也叫做含幺半群。有

2、时也将独异点V记作V。半群与独异点的实例，。半群，除第一个外都是独异点设n是大于1的正整数,和，其 中+和分别表示矩阵加法和矩阵乘法。半群，独异点,其中为集合的对称差运算。 半群，独异点1.2.3.4.5.6.,其中Zn0,1,n-1,为模n加法。半群，独异点,其中为函数的复合运算。半群，独异点,其中R为非零实数集合,运算定义如下：x,yR, xyy半群例下列集合和运算哪些可以半群？哪些可以独异点？(1)(2)(3)S1=1, 1/2, 2, 1/3, 3, 1/4, ,*为普通乘法S2=0, 1,*为普通乘法。 S3=a1, a2, ,an,nZ,*定义为: ai * aj = ai ,i,

3、 jS3。(4)S4=1, 2, 3, 6, x*y表示求x和y的最小公倍数， x,yS4 。S5=0, 1,*为模2加法。(5)解：S1 不是半群；S2是独异点，幺元为1S3是半群；S4 是独异点，幺元为1。S5是独异点，幺元为07例1 ：设S=a,b,c,在S上的一个二元运算定义如表所示。aaa abbb bccc ca b c验证 是一个半群。解： 从表中可知运算 是封闭的，同时a,b和 c都是左幺元。所以，对于任意的x,y,zS,都有x (y z)=x z=z=y z=(x y) z，因此，是半群。8例3设是有穷字母表，kN，定义下述集合：k=a1a2akai是上所有长度为k的串的集合

4、。当k=0时，0=，表示空串。令 * 表示上所有有限长度的串i0i的集合。在* 上可以定义串的连接运算：1，2* ，1=a1a2am，2=b1b2bn，有12 =a1a2amb1b2bn试分析* 。显然* 关于连接运算一个独异点，称为上的字代数。上的语言L（这里的语言指形式语言，不是一般的自然语言）就是* 的一个子集.半群中元素的幂由于半群V中的运算是可结合的,可以定义元素的幂,对任意xS,规定：x1xxn+1xn x,nZ+用数学归纳法不难证明x的幂遵从以下运算规则：xn xmxn+m(xn)mxnmm,nZ+普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个幂运算规则。独异点中的幂独异点是特

5、殊的半群，可以把半群的幂运算推广到独异点中去。由于独异点V中含有以定义x的零次幂,即x0e元e，对于任意的xS,可xn+1xn xnN不难证明，独异点的幂运算也遵从半群的幂运算规则，只不过m和n不一定限于正整数，只要是自然数就成立。子半群与子独异点半群的子代数叫做子半群。独异点的子代数叫做子独异点。根据子代数的定义不难看出：如果V是半群,TS，只要T对V中的运算封闭，那么就是V的子半群。对独异点V来说，TS，不仅T要对V中的运算封闭,而且eT，这时才独异点。思考：如果eT，能够成独异点吗？V的子例2.2 设半群V1，独异点V2。其中为矩阵乘法，e为2阶矩阵令问是否为V1 V2的子代数？由T S

6、，且T对矩阵乘法 是封闭的，所以是V1的子半群。易见在中存在着自己的元e=，所以也一个独立点，但它不是V2=的子独异点，因为V2中的元 e T。半群与独异点的直积定义2.2设V1 , V2 是半群(独异点)，在V1V2上定义二元运算如下：,V1V2 , 称是V1与V2的直积。 证明 是半群(独异点) 。半群与独异点的同态定义2.3(1)设V1,V2是半群,: S1S2。若对任意的x,yS1有(xy)(x)(y)则称为半群V1到V2的同态,简称同态(homomorphism)。(2)设V1,V2是独异点, : S1S2.若对任意的x,yS1有(xy)(x)(y) 且(e1)e2,则称为独异点V1

7、到V2的同态,简称同态。省略表达为了书写的简便，有时经常省略上述表达式中的算符和，而简记为(xy)(x)(y)应该记住，该表达式中左边的xy是在V1中的运算，而右边的 (x) (y)是在V2中的运算。自同态例2.2 设半群V1，独异点V2。其中为矩阵乘法，e为2阶令 : S S,矩阵问：是 V1，V2的自同态吗？18对任意的有即因此，是半群V1到自身的同态，称为V1的自同态。的自同态,因为但不是独异点它没有将V2的单位元映到V2的单位元。注意：而不是V2的单位元。本节的主要内容集合S和运算集合S和运算元）。半群的条件（封闭性、结合律）。独异点的条件（封闭性、结合律、半群与独异点的两条幂运算规则

8、：xn (xn)mxnm 。xmxn+m，半群S的非空子集A运算封闭）。子半群的条件（A对于S中独异点S的非空子集A子独异点的条件（A对于S中运算封闭，元属于A）。的判别：(xy)(x)(y)，对于独异点要同态加上(e)e。2.2 群的定义与性质主要内容：群是特殊的半群和独异点。群论中常用的概念或术语：有限群、无限群、平凡的幂和阶。换群、元素群的性质：幂运算规则、消去律、群方程的唯一解、有关元素的阶的性质。群的定义定义2.4 设是代数系统，为二元运算。元eG，如果运算是可结合的，存在并且对G中的任何元素x都有x-1G, 则称G为群（group）。判断，。，是群设n是大于1的正整数,和，其1.2

9、.中+和分别表示矩阵加法和矩阵乘法。,其中为集合的对称差运算。+是群，不是群是群3.4.5.6.,其中Zn0,1,n-1,为模n加法。是群,其中为函数的复合运算。|A|2时，不是群,其中R为非零实数集合,运算定义如下：x,yR, xyy不是群例1： 设R=0，60，120，180，240，300表示在平面上几何图形绕形心顺时针旋 转角度的六种可能情况，设*是R上的二元运算，定义如下： a ba b 360oa b 360oa b a b 360o验证是一个群。25Klein四元群设Ga,b,c,d，为G上的二元运算，见下表。e为G中的元；运算是可结合的；运算是可交换的；G中任何元素的自己；就是

10、它G是一个群.在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。称这个群为Klein四元群,简称四元群。eabce a bceabcecbceabae应用：纠错码编码例4某二进制码的码字x=x1x2x3x4x5x6x7由7位，其中x1，x2 ，x3和x4为数据位，x5， x6和x7为校验位，并且满足：x5=x1 x2 x3， x6=x1x2x4， x7=x1x3x4这里的是模2加法。设G为所G上定义二元运算如下：x,yG，xy=z1z2z3z4z5z6z7，zi=xi yi，i=1,2, ,7字的集合，证明群。证明：（1）封闭性x=x1x2x7，y=y1y2y7，xy=z1z2z

11、7。首先验证z5=z1z2z3z1z2z3=(x1y1)(x2y2)(x3y3)=(x1x2x3) (y1y2y3)=x5y5=z5同理可证z6=z1 z2z4和z7=z1z3z4 xy=zG，从而证明了封闭性。，于是28（2）结合律x,y,zG，令(xy)z=a1a2a7 x(yz)=b1b2b7，下面证明ai=bi，i=1,2, ,7由于运算满足结合律，因此有ai=(xiyi)zi=xi(yizi)=bi，从而证明了G中满足结合律。（3）（4）元 0000000 xG，x-1=x综合上述， G群。二面体群D4顺时针270顺时针90顺时针180恒等置换对角线24翻转对角线13翻转垂直轴翻转水

12、平轴翻转30二面体群D4一个二面体群，代表一组正多边形的对称，包括旋转对称和反射对称。12D4=43二面体群是有限群中最简单的群组，他们在群论，几何和化学中起到重要作用。31D4=恒等运算保持所有东西不变，记为 id；把正方形向右（顺时针）旋转 90、180 和 270，分别记为 r1、r2和 r3。关于垂直和水平中线的反射记为 fv 和 fh，关于两个对角线的反射记为 fd和 fc。32魔方群魔方的所有可能重新排列形成一个群，叫做魔方群。33群的直积设, 是群，在G1G2上定义二元运算如下：,G1G2 , 称是G1与G2的直积。证明 是群。证明：由于已证明 是独异点，而对任意的G1G2 ,

13、是的，因此G1G2关于运算一个群。群论中常用的概念或术语定义2.5(1)若群G是有穷集,则称G是有限群，否则称为无限群。群G的基数称为群G的阶，有限群G的阶记作|G|。(2)只含元的群称为平凡群。(3)若群G中的二元运算是可交换的，则称G为交换群或(Abel)群。例，Klein四元群，,和,是无限群。是有限群，也是n阶群。 Klein四元群是4阶群。是平凡群。上述除的所有群都是交换群。但n阶(n2)实可逆矩阵的集合关于矩阵乘法的群是非交换群，因为矩阵乘法不满换律。群中元素的n次幂与半群和独异点不同的是：群中元素可以定义负整数次幂。定义2.6 设G是群，aG，nZ，则a的n次幂例 在中有2-3(

14、2-1)3131110在中有 3-5(3-1)5(-3)5(-3)+(-3)+(-3)+(-3)+(-3)-15群中元素的阶定义2.7 设G是群，aG，使得等式ake成立的最小正整数k称为a的阶，记作|a|k，这时也称a为k阶元。若不存在这样的正整数k,则称a为无限阶元。举例在中，2和4是3阶元，3是2阶元，而1和5是6阶元，0是1阶元。在中，0是1阶元，其它的整数都是无限阶元。在Klein四元群中，e为1阶元，其它元素都是2阶元。群的性质群的幂运算规则定理2.1 设G为群,则G中的幂运算满足：(1) aG,(a-1)-1a。(2) a,bG，(ab)-1b-1a-1。aG，anaman+m，

15、n,mZ。aG，(an)manm，n,mZ。若G为交换群，则(ab)nanbn。分析：(1)和(2)可以根据定义证明。(3)、(4)、(5)中的等式,先利用数学归纳法对于自然数n和m证出相应的结果，然后情况。n或m为负数的定理2.1的证明(1) aG,(a-1)-1a。(a-1)-1是a-1的，a也是a-1的。（或者：a-1是a的，a也是a-1的。）的唯一性， (a-1)-1a。根据(2) a,bG，(ab)-1b-1a-1。(b-1a-1)(ab)b-1(a-1a)bb-1be(ab)(b-1a-1)a(bb-1)a-1aa-1e故 b-1a-1是 ab 的。根据的唯一性等式得证。定理2.1

16、的证明(3) aG，anaman+m，n,mZ。先考虑n,m都是自然数的情况。任意给定n，对m进行归纳。m0，有ana0aneanan+0成立。假设对一切mN有anaman+m成立，则有 anam+1an(ama)(anam)aan+maan+m+1由归纳法等式得证。下面考虑存在负整数次幂的情况。设n0，m0，令n-t，tZ+，则a-(t-m)am-tan+mam-tan+mtmtmanama-tam(a-1)tam对于n0,m0以及n0,m0的情况同理可证。定理2.1的证明(5) 若G为交换群，则(ab)nanbn。当n为自然数时，对n进行归纳。e ee a0b0。n0，有(ab)0假设(a

17、b)kakbk，则有(ab)k+1(ab)k(ab) (akbk)abak(bka)b(ak+1)(bk+1)ak(abk)b由归纳法等式得证。(aka)(bk)b设n0，则(ab)n (ba)n (ba)-m (ba)-1)m(a-1b-1)m(a-1)m(b-1)ma-mb-manbn定理2.1说明定理2.1(2)中的结果可以推广到有限多个元素的情况,即注意上述定理中的最后一个等式只对交换群成立。如果G是非交换群,那么只有群方程存在唯一解定理2.2 G为群，a,bG，方程axb和yab在G中有解且仅有唯一解。证明：先证a-1b是方程axb的解。将a-1b代入方程左边的x得a(a-1b) (

18、aa-1)beb b所以a-1b是该方程的解。下面证明唯一性。假设c是方程axb的解，必有acb，从而cec (a-1a)c a-1(ac) a-1b有同理可证ba-1是方程yab的唯一解。若对任意的a,bG,必有唯一的x,yG，满足ax=b和 ya =bb一定出现a所在的行里，且一定出现在a所在的列里。45xaabyb思考：群方程存在唯一解这一特点反映在独异点上，会是什么表现？46独异点的性质例：设是一个独异点，则在运算*的运算表中任何两行或两列都是不相同的。证明:设S中关于运算*的幺元是e。因为对于任意的a,bS，当ab时，总有e*a=ab=e*b 和 a*e=ab=b*e即幺元e所在的行

19、和所在的列有不相同元素。所以，在*的运算表中不可能有两行或两列是相同的。47*eabce a b ce aa eb cc bb cc be aa e48例:设Z 是整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集，在Zm上定义两个二元运算+m和m分别如下：对于任意的i, j Zmi +m j=(i+j) (mod m),im j=(ij) (mod m)试证明在这两个二元运算的运算表中任何两行或两列都不相同。49上例中，如果给定m=5，那么，+5和5的运算表分别如下表所示。0123401234+55012340123412340234013401240123012340000001

20、23402413031420432150证明:代数系统和 。由运算+m和m的定义，可知它们在Zm上是封闭的。对于任意i,j,kZm(i +m j) +m k=i +m (j +m k)=(i+j+k) (mod m) (imj) m k=i m(j mk)=(ijk) (mod m)即+m，m都是可结合的。(3) 因为对于任意iZm，0 +m i= i +m 0=i,所以， 0是中的幺元。因为1 m i= i m 1=i,所以1是中的幺元。因此，代数系统，都是独异点。由独异点的性质定理可知，这两个运算的运算表中任何两行或两列都不相同。51例2.5例2.5 设群G，其中为集合的对称差运算。解下列

21、群方程：(1)aX (2)Ya,bb解答：(1) Xa-1 aa(2) Yba,b-1ba,ba群满足消去律定理2.3G为群,则G中适合消去律，即对任意a,b,cG 有(1)若abac，则bc。 (2)若baca，则bc。证明：(1)abac a-1(ab)a-1(ac) (a-1a)b(a-1a)c ebec bc (2)略幺元保持定理证明： 设是一个群，是的一个子群，那么，中的幺元e必定也是中的幺元。证明：设中的幺元为e1, 对于任一xSG,必有e1*x=x=e*x, 由消去律知e1=e。54例2.6例2.6 设G为群，a,bG, kZ+，证明（a-1ba)ka-1ba bkb证明：充分性

22、（a-1ba)k (a-1ba)(a-1ba)(a-1ba) (a-1ba) a-1b(aa-1)b(aa-1)b(aa-1)ba a-1bka a-1ba (因为 bkb)k个a-1ba由（a-1ba)ka-1ba 得必要性(a-1ba)(a-1ba)(a-1ba)a-1baa-1bkaa-1ba化简得bkb。由消去律得例2.7例2.7 设G为群，a,bG，且 (ab)2a2b2 ，证明abba（证明：由(ab)2a2b2 得ababaabb群）。根据群中的消去律，得 baab，即 abba。例2.8例2.8 设Ga1,a2,an是n阶群，令aiGaiaj|j=1,2,n证明 aiGG。证明

23、：由群中运算的封闭性有aiG G。假设aiG G，即|aiG|n。必有aj,akG 使得aiajaiak （jk）由消去律得 aj=ak,与|G|n。群中元素的阶的性质G为群，aG且|a|r。设k是整数,则定理2.4(1) ake当且仅当 r|k(2) |a|a-1|证明：(1) 充分性。由于r|k，必存在整数m使得kmr，所以有r(ar)m eme。a必要性。根据除法，存在整数m和i使得kmr+i，0ir-1eakamr+i(ar)maieaiai因为|a|r,必有i0。这就证明了r|k。|a|a-1|思考：如何证明元素的阶相等？证明|x|y|的方法：令|x|r，|y|s 验证 (x)se

24、r|s验证 (y)re s|r因此 rs，即 |x|y|。(2) |a|a-1|由(a-1)r(ar)-1e-1e，可知 a-1 的阶存在。令|a-1|t，根据上面的证明有 t|r。这说明a的 而a又是a-1的，故有r|t。的阶是a的阶r的因子。，所以a的阶也是a-1的阶的因子从而证明了rt,即|a|a-1|。例2.9例2.9 设G是群，a,bG是有限阶元。证明(1)|b-1ab|a| (2)|ab|ba|证明：(1)设|a|r,|b-1ab|t，则有(b-1ab)(b-1ab)(b-1ab)b-1arbb-1ebe(r个b-1ab)(b-1ab)r根据定理2.4，可知b-1ab的阶是a的阶的

25、因子，即t|r。另一方面，ab(b-1ab)b-1(b-1)-1(b-1ab)b-1可知,(b-1)-1(b-1ab)b-1的阶是b-1ab的阶的因子，即r|t。从而有|b-1ab|=|a|。(2)|ab|ba|设|ab|r,|ba|t，则有(ab)t+1 (ab)(ab)(ab) a(ba)(ba)(ba)b a(ba)tb aebt+1个abt个ba ab由消去律得(ab)te，从而可知，r|t.同理可证 t|r。因此，|ab|ba|。例2.10例2.10 设G为有限群，则G中阶大于2的元素有偶数个。证明：根据定理2.4可知，对于任意aG，有a2e |a|1 或 |a|2若a2e，则有 a

26、-1a2a-1e，即 aa-1。反之，若aa-1，则有 a2aaaa-1e，这就推出a2e aa-1。 综合上述可知，对G中阶大于2的元素a，必有aa-1。又由于|a|a-1|，所以G中阶大于2的元素一定成对出现。G中若含有阶大于2的元素，一定是偶数个。若G中不含阶大于2的元素，而0也是偶数。本节主要内容集合G和二元运算 封闭性、结合律、群的条件元、每个元素有。特殊群的定义（有限与无限群、Abel群、平凡群）与群的阶。元素的幂与元素的阶群的性质：幂运算规则、消去律、群方程的唯一解、有关元素的阶的性质。2.3 子群子群的定义子群的三个判定方法重要子群的实例 生成群、中心由B生成的子群，子群格子群

27、的定义定义2.8 设G是群，H是G的非空子集，如果H关于G群，则称H是G的子群(subgroup)，记中的运算作 HG。若H是G的子群，且HG，则称H是G的真子群(proper subgroup)，记作 HG。说明：对任何群G都存在子群。G和e都是G的子群，称为G的平凡子群(trivial subgroup) 。举例：nZ（n是自然数）是整数加群Z,+的子群。当n1时,nZ是Z的真子群。子群的判定定理一定理2.5（判定定理一）设G为群，H是G的非空子集。H是G的子群当且仅当下面的条件成立：a,bH，有 abH。aH，有 a-1H。证明：必要性是显然的。为证明充分性，只需证明eH。（为什么？）因

28、为H非空，必存在aH。由条件(2)可知，a-1H，再使用条件(1)有 aa-1H，即eH。子群的判定定理二定理2.6（判定定理二） 设G为群，H是G的非空子集。H是G的子群当且仅当a,bH有ab-1H。证明：必要性。任取a,bH，由于H是G的子群，必有b-1H， 由封闭性有 ab-1H。充分性。 因为H非空，必存在aH。根据给定条件得 aa-1H，即eH。任取aH，由e,aH 得 ea-1H，即a-1H。任取a,bH，由刚才的证明知 b-1H。再利用给定条件得a(b-1)-1H，即 abH。综合所述，根据判定定理一，可知 H是G的子群。子群的判定定理三定理2.7(判定定理三) 设G为群，H是G

29、的非空子集。如果H是有穷集，则H是G的子群当且仅当 a,bH有abH。证明：必要性是显然的。充分性。只需证明 aH有a-1H。（为什么不证幺元的存在性?）任取aH，若ae，则a-1e-1eH。若ae,令 Sa,a2,，则SH。由于H是有穷集，必有aiaj（i1，由此得aj-i-1ae 和 aaj-i-1e从而证明了 a-1aj-i-1H。由的存在性和封闭性，可知幺元一定存在。子群实例生成子群举例：整数加群，由2生成的子群是2k|kZ2Z群中，由2生成的子群由 200，212，224，23=0，即 0,2,4，(3)Klein四元群Ge,a,b,c的所有生成子群是：e，e,a，e,b，e,c。子

30、群实例中心例2.13 设G为群，令C是与G中所有的元素都可交换的元素的集合，即Ca|aGxG(axxa)则C是G的子群，称为G的中心。证明：由e与G中所有元素的交换性可知，eC。C是G的非空子集。任取a,bC，为证明ab-1C，只需证明ab-1与G中所有的元素都可交换。xG，有a(bx-1)-1(ab-1)xa(x-1b)-1ab-1xab-1(x-1)-1a(xb-1)(ax)b-1 (xa)b-1 x(ab-1)由判定定理二可知，CG。例2.14例2.14 设G是群，H,K是G的子群。证明HK也是G的子群。HK是G的子群当且仅当 HK 或 KH。证明：(1) 由eHK 知 HK非空。任取a

31、,bHK，则 aH，aK，bH，bK。由于H和K是G的子群，必有 ab-1H 和 ab-1K，从而推出 ab-1HK。根据判定定理二，命题得证。(2) HK是G的子群当且仅当 HK 或 KH。充分性是显然的。必要性，用反证法。假设 HK 且 KH，那么存在h和k使得hHhK 这就推出 hkH。若不然，由h-1H盾。同理可证，hkK。 从而得到 hkHK。kKkH并且kh-1(hk)H，与假设矛这与HK是子群。由B生成的子群任取两个子群H1,H2，令BH1H2，如果H1H2， H1H2 ,那么H1H2不是G的子群，而只是G的子集。将G的所有包含B的子群的交记作，即H|BHHG。易见是G的子群，称为由B生成的子群。中的元素恰为如下形式：a1a2ak,kZ+其中ai是B中元素或B中元素的。不难证明，是包含了H1和H2的最小子群。如何找到有限群的全部子群第0层：e是G的平凡子群，也是最小的子群，放在第0层。第1层：任取aG，ae，则是a由生成的子群。如果G且不存在是的真子群，则将放在第1层。 如