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

第9章半群和群semigroupandgroup§9.1二元运算复习binaryoperationrevisitedA上二元运算f：A×A→Af处处有定义的函数。Dom（f）＝A×A，对任意a，b∈A，f(a，b)∈A，唯一确定。二元运算常记做＋，－，×，*，◦，等等对任意a，b∈A，a◦b∈A说成A对◦封闭。A＝{a1,a2,……,an}时，二元运算可以用运算表给出。二元运算的性质1可换commutativea*b=b*a2结合associativea*(b*c)=(a*b)*c3幂等idempotenta*a=a特殊元素单位元对任意a∈A，e*a=a*e＝a.单位元也叫恒等元零元对任意a∈A，0*a=a*0＝0逆元对任意a，b∈A，a*b=b*a＝ea,b互为逆元代数结构(A,*)A上定义了二元运算满足1)封闭性2)结合律-----------半群3)有单位元---------独异点4)有逆元-----------群5)可交换-----------交换群例子：1)(Zn+),(Zn,)2)(A*,*)字符串的连接HomeworkP323－32416，20，22，24，25，26§9.2半群semigroup半群定义：(S,*)*是S上乘法，满足结合律。半群的例(Z，＋），（Z，×），（N，×），（N，＋），（Q，＋），（R，×），（P(S),∪），（P(S),∩），（Mn，＋），（Mn，×），S上全体映射，对于复合，（L，∧），（L，∨），L是格（A*,）,定理1.半群中，n个元素的乘积与乘法的次序无关。幂power：设（S，*）是半群，a∈S，定义a的幂power：a1＝a，an=an-1*a.a0=？a-n=?am*an=am+n(am)n=amn.子半群subsemigroup子独异点submonoid设（S，*）是半群，TS，T对*封闭，则（T，*）也是半群，称为（S，*）的子半群。设（S，*）是独异点，TS，T对*封闭，且e∈T，则（T，*）也是独异点，称为（S，*）的子独异点。（N，＋），（Z，＋），（Q，＋），（R，＋）前一个是后一个的子半群，也是子独异点。（N，×），（Z，×），（Q，×），（R，×）前一个是后一个的子半群，也是子独异点。设（S，*）是半群，（S，*）是（S，*）的子半群。设（S，*）是独异点，（S，*）是（S，*）的子独异点。设（S，*）是独异点，({e},*)是（S，*）的子独异点。同构isomorphism和同态homomorphism同构设（S，*）和（T，*’）是两个半群，函数f：S→T是一一对应，a，b∈S，f(a*b)=f(a)*’f(b).称（S，*）和（T，*’）同构，记做（S，*）（T，*’）.验证两个半群（S，*）和（T，*’）同构的方法：定义一个映射f：S→T，证明(1)f单，f(a)=f(b)a=b.(2)f满，Ran(f)=T.(3)f保持运算f(a*b)=f(a)*’f(b).例.令T＝{2n|n∈Z}，则且（Z，＋）（T，×）。证明.令f：Z→T，对任意n∈Z，f(n)=2n.（1）f处处有定义.（2）f单:f(m)=f(n),即2m=2nm=n。（3）f满.（4）f保持运算：f(m+n)=2m+n=2m×2n=f(m)×f(n)定理2.若S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元。同态Homomorphisim在同构的三个条件中，若仅满足(3)叫做同态。若仅满足(1)(3)称为同构嵌入。若仅满足(2)(3)叫做满同态。例20．设A＝{0，1}，则自由半群（A*,）与（A，＋）同态，（A，＋）的二元运算＋由乘法表给出：＋01001110例.(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,t2∈f(S’)，要证t1*’t2∈f(S’).存在s1，s2∈S’，f(s1)＝t1，f(s2)＝t2，t1*’t2=f(s1)*’f(s2)=f(s1*’s2)∈f(S’).定理5.交换半群的同态像是交换半群。设f：（S，*）（T，*’）是到上半群同态，（S，*）是交换半群，则（T，*’）的交换半群。证明.任意t1,t2∈T，要证t1*’t2＝t2*’t1.存在s1，s2∈S，f(s1)＝t1，f(s2)＝t2，t1*’t2=f(s1)*’f(s2)=f(s1*’s2)＝f(s2*’s1)＝f(s2)*’f(s1)＝t2*’t1.HomeworkP330－33113，16，18，19，23，26，28，31§9.3乘积半群和商半群ProductsandQuotiensSemigroup定理1.乘积半群设（S，*）和（T，*’）是两个半群，则（S×T，*”）也是半群。(s1,t1)*”(s2,t2)=(s1*s2,t1*’t2).设（S，*）和（T，*’）是两个独异点，则（S×T，*”）也是独异点，恒等元是（e，e’）。同余关系（合同关系）congruencerelation设（S，*）是半群，R是S上等价关系。R称为S上同余关系：aRa’,bRb’(a*b)R(a’*b’).例1.Z上剩余关系是(Z,＋)上同余关系：ab（mod2）2|a－b。证明.ab（mod2）是等价关系。ab（mod2）,2|a-b,a-b=2k.cd（mod2）,2|c-d,c-d=2t.(a+c)－(b+d)=(a-b)+(c-d)=2(k+t)a+cb+d（mod2）ab（mod2）是(Z,＋)上同余关系。Z上剩余关系是(Z,×)上同余关系.例2．令A＝{0,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=5f(-3)=10,f(5)=18-1+-2与2＋3不满足R。定理2.设R是半群（S，*）上同余关系。定义商集S/R上二元运算*：[a]*[b]=[a*b]。则（S/R,*）是半群。证明.设[a]=[a’],[b]=[b’],要证[a*b]=[a’*b’]aRa’,bRb’,由*是同余关系a*bRa’*b’,因此[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,*）是独异点。证明.恒等元e∈S,只要证明[e]是S/R,的恒等元。任何a∈S，[a]*[e]=[a*e]=[a][e]*[a]=[e*a]=[a].例5．（Zn,+）,(Zn，×)都是半群，独异点。Zn＝{[0],[1],[2],……,[n-1]}[m]+[n]=[m+n]定理3.令R是半群（S，*）上同余关系,（S/R,*）是商半群。f：S→S/R,f(a)=[a],则f是满同态，称f为自然同态。定理4.同态基本定理设f:（S，*）→（T，*’）是两个半群间的满同态映射，令R是S上二元关系：a,b∈S，aRbf(a)=f(b).则(a)R是（S，*）上同余关系。(b)(T，*’)(S/R,*).HomeworkP337-3384,10,14,16,22,24§9.4群Group群的定义群（G，*）是一个代数系统，1)封闭2）结合律,2）有单位元e，a*e=e*a=a,3)对每个a∈G，存在a’∈G，a*a’=a’*a=e,称a’为a的逆元。群（G，*）是一个有单位元的独异点，对每个a∈G，存在逆元a’∈G，使a*a’=a’*a=e.群（G，*）常简记为G，a*b常简记为ab。可换群叫Abel群AbelianGroup群的例(Z，＋），（Q，＋），（Q\{0}，×），（R，＋），（R\{0}，×），（Zn，＋），（Mn，＋），S上全体一一对应，对于复合，最后一个不是Abel群。例（R，*）：a*b=ab/2是Abel群。群的性质定理1.群的逆元唯一：设G是群，任意a∈G，a只有一个逆元，记做a-1。证明.设a’，a”都是a的逆，a’=a’aa”=a”.定理2.群有消去律：设G是群，a,b,c∈G,则（a）ab＝acb＝c，（b）ba＝cab＝c。设G={a1,a2,……,an}任意a∈G，aG=G.定理3.逆律设G是群，a,b∈G,则(a)(a-1)-1=a,(b)(ab)-1=b-1a-1.（c）(an)-1＝(a-1)n定理4.方程有唯一解设G是群，a,b∈G,则(a)方程ax＝b在G中有唯一解。(b)方程ya＝b在G中有唯一解。群G的阶:|G|.|G|有限时称G为有限群。元素的阶a∈G，a的阶：使ak＝e的最小的k。如无这样的k，称a为无限阶。a无限阶，任意n∈Z+，an≠e.子群subgroupHG，H对于G的运算*构成群。H是G的子群当且仅当（1）e∈H（2）a，b∈Hab∈H（3）a∈Ha-1∈HH是G的子群当且仅当a，b∈Hab-1∈H.子群的例设G是群，H＝{e}是子群。G是群，a∈G，H＝{ak|k∈Z}是子群，叫做a生成的子群。命题.一个群的任意两个子群的交仍是子群。循环群cyclegroup存在a∈G，任意x∈G，x＝ak，k∈Z。a的阶是n，G＝{e,a,a2,……,an-1}ak的逆是an-k。a无限阶，G＝{……,a-2,a-1,e,a,a2,……}Z是无限循环群，Zn是n阶循环群。有限群G是循环群当且仅当存在a∈G，a的阶＝|G|.(Zn,+),(Zp*,)置换群Sn三角形的自同构群？231A＝{1,2,3},A的所有置换对复合运算构成群：1123123f=(1)单位元2123231f=(123)3阶元3123312f=(132)1123132g=(23)2阶元2123321g=(13)2123213g=(12)S3={f1,f2,f3,g1,g2,g3}称(S3,*)为对称群，Groupofsymeriesofatriangle。S3的乘法表：f1f2f3g1g2g3f1f1f2f3g1g2g3f2f2f3f1g3g1g2f3f3f1f2g2g3g1g1g1g2g3f1f2F3g2g2g3g1f3f1F2g3g3g1g2f2f3F1S4四元对称群，是四个元素的置换组成的对称群，共有4！＝24个置换。Snn元对称群，是n个元素的置换组成的对称群，有n！个元素。Cayley定理：任意的群都同构与某个对称群的子群。自由群群的同构与同态isomorphismandhomomorphismofgroups同构f:（G1，*）（G2，*），f一一对应，保持运算。|G1|=|G2|,对应元素有相同的阶。同态f:（G1，*）（G2，*），f多一到上，保持运算。ZZnZ6≌Z7*例16．S3与Z6都是6阶群，不同构。定理5.单位元，逆元，子群在同态下保持设f:(G，*)(G’，*’)是同态，则（a）f(e)=e’,(b)f(a-1)=f(a)-1,(c)H是G的子群f(H)是G’的子群。共轭对应是群的自同态a∈G,f:G→G,f(x)=axa-1,f是同态。HomeworkPP348－3496，12，19，22，24，28，30，32，33§9.5乘积群和商群定理4.设G1，G2是群，则G1×G2是群，乘法定义(a1,b1)(