离散数学课件 第9章 半群和群.docx

1、离散数学课件 第9章 半群和群第9章 半群和群semigroup and group9.1 二元运算复习binary operation revisitedA上二元运算 f：AAA f处处有定义的函数。 Dom（f）AA， 对任意a，bA，f(a，b)A，唯一确定。二元运算常记做，*，等等对任意a，bA，abA 说成A对封闭。Aa1,a2,an时，二元运算可以用运算表给出。二元运算的性质 1可换commutative a*b=b*a 2 结合associative a*(b*c)=(a*b)*c 3 幂等idempotent a*a=a特殊元素单位元对任意aA，e*a=a*ea. 单位元也叫恒

2、等元零元对任意aA，0*a=a*00 逆元对任意a，bA，a*b=b*aea,b互为逆元代数结构(A,*)A上定义了二元运算满足1)封闭性2)结合律-半群3)有单位元-独异点4)有逆元-群5)可交换-交换群例子：1) (Zn +), (Zn,)2) (A*, *) 字符串的连接Homework P32332416，20，22，24，25，269.2 半群semigroup 半群定义：(S,*) *是S上乘法，满足结合律。半群的例 (Z，），（Z，）， （N，），（N，）， （Q，），（R，）， （P(S),），（P(S), ）， （Mn，），（Mn，）， S上全体映射，对于复合， （L，），（

3、L，），L是格 （A*, ）, 定理1. 半群中，n个元素的乘积与乘法的次序无关。幂power：设（S，*）是半群，aS，定义a的幂power： a1a， an=an-1*a.a0=？a-n=?am*an=am+n(am)n=amn.子半群subsemigroup 子独异点submonoid设（S，*）是半群，TS，T对*封闭，则（T，*）也是半群，称为（S，*）的子半群。设（S，*）是独异点，TS，T对*封闭，且eT，则（T，*）也是独异点，称为（S，*）的子独异点。（N，），（Z，），（Q，），（R，）前一个是后一个的子半群，也是子独异点。（N，），（Z，），（Q，），（R，）前一个是后一

4、个的子半群，也是子独异点。设（S，*）是半群，（S，*）是（S，*）的子半群。设（S，*）是独异点，（S，*）是（S，*）的子独异点。设（S，*）是独异点， (e,*)是（S，*）的子独异点。同构isomorphism和同态 homomorphism同构设（S，*）和（T，*）是两个半群，函数f：ST是一一对应，a，bS， f(a*b)=f(a)*f(b).称（S，*）和（T，*）同构，记做（S，*）（T，*）.验证两个半群（S，*）和（T，*）同构的方法：定义一个映射f：ST，证明(1) f 单，f(a)=f(b)a=b.(2) f 满，Ran(f)=T.(3) f保持运算f(a*b)=f(

5、a)*f(b).例. 令T2n | nZ，则且（Z，）（T，）。证明. 令f：ZT， 对任意nZ，f(n)= 2n.（1） f处处有定义.（2） f单:f(m)=f(n), 即 2m=2nm=n。（3） f满.（4） f保持运算： f(m+n)= 2m+n =2m2n =f(m)f(n)定理2. 若S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元。同态Homomorphisim在同构的三个条件中，若仅满足(3)叫做同态。若仅满足(1)(3)称为同构嵌入。若仅满足(2)(3)叫做满同态。例20 设A0，1，则自由半群（A*, ）与（A，）同态，（A，）的二元运算由乘法表给出： 0100

6、1110例. (Z,+) (Zn,+), (Z,) （Zn，）.定理3. 恒等元的满同态像是恒等元设（S，*），（T，*）是独异点，恒等元分别是e和e，同态f:（S，*）（T，*）, 则f(e)=e.定理4.子半群的同态像是子半群。证明.设f：（S，*） （T，*）是半群同态，S是（S，*）的子半群，则f(S)是（T，*）的子半群。只要证f(S)对运算封闭。设t1,t2f(S)，要证t1*t2f(S).存在s1，s2S， f(s1)t1，f(s2)t2， t1*t2= f(s1)*f(s2) = f(s1*s2)f(S).定理5.交换半群的同态像是交换半群。设f：（S，*） （T，*）是到上半

7、群同态，（S，*）是交换半群，则（T，*）的交换半群。证明. 任意t1,t2T， 要证t1*t2t2*t1. 存在s1，s2S， f(s1)t1，f(s2)t2， t1*t2= f(s1)*f(s2)= f(s1*s2) f(s2*s1)f(s2)*f(s1)t2*t1.Homework P33033113，16，18，19，23，26，28，319.3 乘积半群和商半群Products and Quotiens Semigroup定理1. 乘积半群设（S，*）和（T，*）是两个半群，则（ST，*”）也是半群。 (s1, t1)*” (s2, t2)=( s1*s2, t1*t2 ).设（S，

8、*）和（T，*）是两个独异点，则（ST，*”）也是独异点，恒等元是（e，e）。同余关系（合同关系） congruence relation设（S，*）是半群，R是S上等价关系。R称为S上同余关系：aRa, bRb(a*b)R(a*b).例1. Z上剩余关系是(Z,)上同余关系：ab（mod 2） 2 | ab。证明. ab（mod 2）是等价关系。ab（mod 2）, 2 | a-b, a-b=2k.cd（mod 2）, 2 | c-d, c-d=2t.(a+c)(b+d)=(a-b)+(c-d)=2(k+t)a+c b+d（mod 2）ab（mod 2）是(Z,)上同余关系。Z上剩余关系是(

9、Z,)上同余关系. 例2令A0,1,自由半群（A*,）上关系R： R，含有同样多个1。则R是（A*,）上同余关系。例3设f(x)=x2-x-2, 令（Z，）上关系R：aRb f(a)=f(b).R是Z上等价关系，但不是同余关系。 1R2，f(1)=f(2)=0 2R3，f(-2)=f(3)=4-1+-2=-3, 2+3=5 f(-3)=10, f(5)=18 -1+-2 与 23 不满足R。定理2. 设R是半群（S，*）上同余关系。定义商集S/R上二元运算*：a*b=a*b。则（S/R,*）是半群。证明. 设a=a, b=b,要证a*b= a*baRa, bRb,由*是同余关系a*bRa*b,

10、因此a*b= a*b，*是映射，二元运算。还要证*满足结合律：a*(b*c)=a*b*c=a*(b*c)=(a*b)*c=a*b*c=(a*b)*c因此（S/R,*）是半群。称S/R为商半群。推论1. 设R是独异点（S，*）上同余关系，则（S/R,*）是独异点。证明.恒等元eS,只要证明e是S/R,的恒等元。任何aS，a*e=a*e=ae*a=e*a=a.例5（Zn,+）,(Zn，)都是半群，独异点。Zn0,1,2,n-1m+n=m+n定理3.令R是半群（S，*）上同余关系,（S/R,*）是商半群。f：SS/R, f(a)=a,则f是满同态，称f为自然同态。定理4.同态基本定理设f:（S，*）

11、（T，*）是两个半群间的满同态映射，令R是S上二元关系：a,bS，aRbf(a)=f(b).则(a) R是（S，*）上同余关系。(b) (T，*)(S/R,*).Homework P337-3384,10,14,16,22,249.4 群Group群的定义群（G，*）是一个代数系统，1) 封闭2） 结合律,2） 有单位元e， a*e=e*a=a,3) 对每个aG，存在aG，a*a=a*a=e, 称a为a的逆元。群（G，*）是一个有单位元的独异点，对每个aG，存在逆元aG，使a*a=a*a=e.群（G，*）常简记为G，a*b常简记为ab。可换群叫Abel群 Abelian Group群的例 (Z

12、，）， （Q，），（Q0，）， （R，），（R0，）， （Zn，）， （Mn，）， S上全体一一对应，对于复合，最后一个不是Abel群。例（R，*）：a*b=ab/2是Abel群。群的性质定理1. 群的逆元唯一：设G是群，任意aG，a只有一个逆元，记做a-1。证明.设a，a”都是a的逆，a=aaa”=a”.定理2. 群有消去律：设G是群，a,b,cG,则（a） abacbc，（b） bacabc。设G=a1,a2,an 任意aG，aG=G.定理3. 逆律设G是群，a,bG, 则(a) (a-1)-1=a,(b) (ab)-1=b-1a-1.（c）(an)-1(a-1)n定理4. 方程有唯一解设

13、G是群，a,bG,则(a) 方程axb在G中有唯一解。(b) 方程yab在G中有唯一解。群G的阶: |G|.|G|有限时称G为有限群。元素的阶aG，a的阶：使ake的最小的k。如无这样的k，称a为无限阶。a无限阶，任意nZ+，ane.子群subgroup HG，H对于G的运算*构成群。H是G的子群当且仅当（1） eH（2） a，bHabH（3） aHa-1HH是G的子群当且仅当 a，bHab-1H.子群的例设G是群，He是子群。G是群，aG，Hak | kZ是子群，叫做a生成的子群。命题. 一个群的任意两个子群的交仍是子群。循环群cycle group存在aG ，任意xG，xak，kZ。a的阶

14、是n，Ge,a,a2,an-1 ak的逆是an-k。a无限阶，G,a-2,a-1,e,a,a2,Z是无限循环群，Zn是n阶循环群。有限群G是循环群当且仅当存在aG，a的阶|G|.(Zn,+), (Zp*,)置换群Sn三角形的自同构群？A1,2,3, A的所有置换对复合运算构成群：=(1) 单位元=(1 2 3) 3阶元=(1 3 2) =(2 3) 2阶元=(1 3) =(1 2)S3= f1,f2,f3,g1,g2,g3称(S3 ,*)为对称群，Group of symeries of a triangle。S3 的乘法表：f1f2f3g1g2g3f1f1f2f3g1g2g3f2f2f3f1

15、g3g1g2f3f3f1f2g2g3g1g1g1g2g3f1f2F3g2g2g3g1f3f1F2g3g3g1g2f2f3F1S4 四元对称群，是四个元素的置换组成的对称群，共有4！24个置换。Sn n元对称群，是n个元素的置换组成的对称群，有n！个元素。Cayley定理：任意的群都同构与某个对称群的子群。自由群群的同构与同态isomorphism and homomorphism of groups同构f: （G1，*）（G2，*），f一一对应，保持运算。|G1|=|G2|, 对应元素有相同的阶。同态f: （G1，*）（G2，*），f多一 到上，保持运算。ZZnZ6Z7*例16S3与Z6都是6

16、阶群，不同构。定理5. 单位元，逆元，子群在同态下保持设f:(G，*)(G，*)是同态，则 （a） f(e)=e, (b) f(a-1)=f(a)-1, (c) H是G的子群f(H)是G的子群。共轭对应是群的自同态aG , f:GG , f(x)=axa-1, f是同态。Homework PP3483496，12，19，22，24，28，30，32，339.5乘积群和商群定理4. 设G1，G2是群，则G1G2是群，乘法定义(a1,b1)(a1,b1)=(a1a2,b1b2).乘积群的例Z2Z3Z6，Z2Z2V （Klein 四元群）ZmZnZmn iff (m, n)=1.a1（mod m）b

17、1（mod n）ab1（mod mn）B=0,1Bn=BBB。定理5. 设R是群（G，*）的同余关系，则商（G/R,*）是群。群的同态定理（a） 设R是群（G，*）的同余关系，则fR：GG/R是群同态映射。 (b)设f:（S，*）（T，*）是两个群间的同态映射，令R是S上二元关系：a,bS，aRbf(a)=f(b).则(1) R是（S，*）上同余关系。(2) :(S/R,*) (T，*).子群的陪集coset左陪集left coset设H是G的一个子群，aG，令aHah | hH称为a确定的H的一个左陪集。右陪集right coset设H是G的一个子群，aG，令Haha | hH称为a确定的H

18、的一个右陪集。例H1=0,3, H2=0,2,4都是Z6的子群。H1在Z6中的左陪集有 0+ H1 =0,3= H1 1+ H1 =1,4 2+ H1 =2,5 3+ H1=3,6=0,3= H1 4+ H1 =4,7=1,4 5+ H1 =5,8=2,5陪集的性质，设H是G的子群，命题1.aG，aHHaH.证明.设aH，任意hH，由H是G的子群ahH， aHH，a-1H, a-1hH，haa-1haH， HaH。因此aHH设aHH，由H是G的子群eH，aaeaHH，aH。例3. H=f1,g2, 是S3的子群，求H的所有左陪集。解. f1H =g2H=H, f2H =g1H=f2,g1 f3

19、H=g2H=f3,g2例4. Hf2f2,g3f2HH不是正规子群。命题2.a,bG则aHbH或aHbH.证明.设aHbH。存在h，h”H, ah=bh”.任意hH，ahah h-1h =bh” h-1hbH，aHbH.同理bHaH.因此aHbH.H的所有左陪集组成G的一个划分，GaGaH。命题3.任aG，f:aHH，f(ah)=h是一一对应。命题4. |G|=n, 则|H| | n.命题5. |G|=n,aG， a的阶k，则k | n.推论 设p是素数，aZ, (p|a),则 ap-11.证明. 由(p|a), (a0). aZp*,设a的阶是k, ak1.Zp*的阶是p-1.由命题5，k|

20、(p-1).ap-11.正规子群Normal subgroup设H是G的一个子群，对任意aG，aHHa，就称H是G的正规子群。注意aHHa并不是hH，ahha而是存在hH，ahha.命题6. 设G是Abel群，H是G的任意子群，则H是G的正规子群。 证明.任取aG，证明aHHa：任意hH，ahha，aHHa，aHHa，aHHa。定理1. 设N是G的正规子群，在G上定义一个关系，a，bG， aRb a-1bN. 则R是G的同余关系。Ne.证明. （a）R是等价关系：1)a-1a=eN，aRa；2)设aRb，a-1bN. b-1a(a-1b) -1N. bRa;3)设aRb，bRc， a-1bN，

21、b-1cN， a-1c(a-1b)(b-1c)N aRc;R是同余关系：设aRb，cRd， a-1bN，c-1dN， c-1 a-1bc-1N=Nc-1，存在hN，c-1 a-1bhc-1 (ac)-1bd=c-1a-1bdhc-1dN，acRbd。(b)任意xN，x-1ex-1N， xRe，xe. N e. 任意xe, xRe, x-1ex-1N， xN，e N.N=e.定理2. 令R是群G的同余关系， He,则H是正规子群，任意aG，aHHaa。证明 H=e是G的子群。任取a，be, 有aRe, bRe,R是同余关系，abRe，abe,R是等价关系a-1Ra-1,eRa，a-1eRa-1a

22、,即a-1Re，a-1eR是等价关系,eRe, ee, 任取aG, aHa,任取hH，hRe，aRa，ahRae，ahRa，aha.aH a,任取ba, bRa, a-1Ra-1a-1bRa-1a, a-1bRe, a-1be=Hb=aa-1baH。a aH。aHa.同理可证Haa.aH=a=Ha, H是正规子群。定理3.设f:GG是满同态，令ker(f)= a | aG，f(a)=e .则ker(f)是G的正规子群，G/ker(f)G.aRbf(a)=f(b) a-1bker(f).Homework PP353-3541,3,6,12,16,18,22,24,29,30,31习题1 除单位元

23、外只有二阶元的群是Abel群.2 有左右消去率的有限半群是群.3 偶数阶群中有奇数多个二阶元.4 证明定理3.5 有多少个8阶群？9.6Burnside Lemma 伯恩赛德引理，Plya定理9.7.1 置换的类型定义 一个n次置换p可以分解为互不相交的1个1轮换 ，2个2轮换 ，n个n轮换，p称为（1,2 ,，n ）型置换,也称p是1122nn型置换.显然有 .例如 p1= (1)(2,3)(4,5,6,7) , p2=(1,2,3)(4,5)(6,7)则p1属于11213041506070 型简写为（112141）型p2属于10223140506070 型 简写为（2231）型3次对称群S

24、3种置换可能的类型11+22 +33=3（1,2 ,3）=（3,0,0），（1,1,0）,(0,0,1) (1)(2)(3) (3,0,0)(1,2)(3), (1)(2,3), (1,3)(2) (1,1,0)(1,2,3) (0,0,1)一个置换群G中，用D(1,2 ,n)表示（1,2 ,n）型置换的个数 定理9.7.1 n元对称群Sn中 D(1,2 ,n) =计算S3,S4中各种类型的置换个数。以k(p)表示p的k阶（不相交）轮换的个数，(p)表示p的所有（不相交）轮换的个数。(p)=1(p1)=1，2(p1)=1，4(p1)=1.1(p2)=0，2(p1)=2，3(p1)=1.9.7.

25、2 置换群的轨道设G是S=1,2,n的置换群，pG, iS 不动点和不动置换类不动点 如果p(i)=i, 称i是p的一个不动点。P可以有不止一个不动点。G中可以有不止一个置换以i为不动点。 p的不动点数=1(p).不动置换类G中以i为不动点的所有置换称为i的不动置换类，记为Zi。例子 G是4次对称群S4的子群G=e, (1,2), (3,4), (1,2)(3,4) G中Z1=Z2=e, (3,4)Z3=Z4=e, (1,2)定理9.7.2群G中，对任意i, 1in, Zi构成G的子群, |Zi| | |G| .G的轨道设G是S=1,2,n的置换群， i，jS , 如果存在pG, 使p(i)=

26、j, 就称i, j相连，记做ij。所有与i相连的元素的集合记做Ei, Ei也称为i的轨道是S上等价关系，Ei是i所在的等价类。G=e, (1,2), (3,4), (1,2)(3,4) G中E1=E2=1,2, E3=E4=3,4.S中每个元素都有一个轨道，不同的轨道是互不相交的。定理9.7.3 对任意i, 1in, |Ei| |Zi|=|G|.证明设pG,pZi是Zi的一个左陪集, 如果p(i)=j,则对任意qZi, pq(i)=j, 即陪集pZi中任意元素都把i变到j.Zi的任意一个陪集把i变到一个元素，Zi不同的陪集把i变到不同的元素。Zi陪集的个数与Ei中元素个数一样多，因此有 |Ei| =|G|/|Zi|， |Ei| |Zi|=|G|.9.7.3 Burnside Lemma伯恩赛德引理定理9.7.4(Burnside Lemma 伯恩赛德引理)设G=p1,p2,pr 是S=1,2,n的置换群，L表示G的轨道的个数。则 L=证明记G的置换下不动点的总数为N,依置换逐个计算 N=.依S中元素逐个计算 .于是得到 L|G|=, L=.例1对正方形的4个格子用两种颜色着色，有多少种不同的着色方法，其中经过旋转重合的方案只算一种。解 不论旋转共有24=16种方案 S=f0,f1,f2,f3,f4,f5,f6,f7,f8,