离散数学第五章代数结构

1、离散数学课件第五章代数结构第1页，共58页，2022年，5月20日，11点13分，星期五证明: 1）充分性 a,bG，有(ab)(ab)=(aa)(bb) 左端 = a(ba)b 右端 = a*(a*b)*b 即 a(ba)b = a(ab)b 由可约性得，用a-1左上式，再用b-1右上式，得 (ab)=(ba) 2）必要性 从“是阿贝尔群”的结论出发 ，推出“(ab)(ab)=(aa)(bb)”。（证略）第2页，共58页，2022年，5月20日，11点13分，星期五补充：元素的阶（a的阶，记为|a| ）1元素a的幂的定义定义：给定群,aG,若nN,则定义: a0 = e, an+1 = an

2、 * a, a-n = a-1 * a-1 * * a-1= (a-1)n =(an)-1 对m用归纳法可证：am * an = am+n (m,nI), 对k用归纳法可证：(am)k = amk (m,kI)第3页，共58页，2022年，5月20日，11点13分，星期五补充：元素的阶（a的阶，记为|a| ）2元素a的阶的定义 设是群， a G能够使 am=e的最小正整数m，称为a的阶。若m不存在，则说a是无阶的。例1：在整数加群中，0的阶是1，其余元素均无阶。例2：在群中，-1的阶是2，1的阶是1。例3：在整数加群中，求各元素的阶： 1 2 3 4 5 0 6 3 2 3 6 1第4页，共5

3、8页，2022年，5月20日，11点13分，星期五循环群与生成元定义5-5.2 设为群，如果在G中存在元素a,使得G中的任何元素都可表示为a的幂（约定a0=e,ak=a*a*a(k个)）,称为循环群，这时a称为循环群G的生成元。例1：整数加群是循环群，其生成元为 。计算群的生成元是判别一个群是否为循环群的关键。1和-1第5页，共58页，2022年，5月20日，11点13分，星期五循环群举例例：循环群，0o是该循环群的幺元。 60o是该循环群的生成元。(60o)1=60o, (60o)2=60o60o=120o,(60o)3=60o60o60o=180o,(60o)4=240o, (60o)5=

4、300o (60o)6=0o=e, (60o)7=60o, (60o)8=120o, ab表示平面图形连续旋转a和b得到的总旋转角度，并规定旋转360等于原来的状态。300也是生成元：300,240,180,120,60,0第6页，共58页，2022年，5月20日，11点13分，星期五循环群的性质定理 5-5.2 任何一个循环群必定是阿贝尔群。证 设 是一个循环群，a是该群的生成元，则对于任意的x,yG ，必有r,sI，使得 x= ar 和 y = as 而且 xy = aras = ar+s = as+r = asar = yx因此，运算可交换，是阿贝尔群。第7页，共58页，2022年，5月

5、20日，11点13分，星期五循环群中生成元的阶（周期）定理 5-5.3 设为循环群，aG是该群的生成元，如果G的阶数是n ，即|G|= n ，则an = e,且 G=a, a2, a3,., an-2, an-1, an=e其中， e是群的幺元。 n是使得an=e成立的最小正整数，称为元素a的阶或周期。第8页，共58页，2022年，5月20日，11点13分，星期五定理 5-5.3 的证明证明思路:先证a的阶为n。 设对于某个正整数m,mn,有am=e。 那么，由于 是一个循环群，所以对于G中任意的元素都能写为ak (k I),而且k=mq+r,其中q是某个整数,0rm,则有 ak=amq+r

6、=(am)qar =(e)qar =ar 因此，G中每一元素都可写成ar，G中最多有m个元素。与 |G|= n矛盾。所以am=e是不可能的。 再用反证法证明a ， a2 ，. ， an互不相同。 设ai= aj，其中1ijn ，就有aj-i =e ，而且1j-in ，这已经有上面证明是不可能的。第9页，共58页，2022年，5月20日，11点13分，星期五循环群中生成元的阶例1：循环群，60o是生成元； e=0o；6是使(60o)n=e的最小正整数，故60o的周期(阶)为6。例2：是无限循环群, 其中-5,5是均生成元。同理，300的阶也是6。第10页，共58页，2022年，5月20日，11点

7、13分，星期五例3：循环群，其中Nk=0,k-1，x表示N中的模k等价类，x+ky=(x+y)mod k。求的幺元、生成元，并求生成元的周期。解：任意xN4，必有x+40=x，故0为该群的幺元；1和3都是生成元，周期都是4。(1)1=1,(1)2=2, (1)3=3, (1)4=0(3)1=3,(3)2=2, (3)3=1, (3)4=0思考：为什么2不是生成元？的生成元？第11页，共58页，2022年，5月20日，11点13分，星期五例4：设G=,，*的运算表如下，证是循环群。* 证：从运算表可验证是群。从表中可看出是幺元。：2=, 3=, 4=：2=, 3=, 4=：2=, 3=， 4=故

8、生成元为： ，故是循环群。第12页，共58页，2022年，5月20日，11点13分，星期五练习1证明：循环群的任何子群必定也是循环群。证 设是循环群，其生成元是a。设是 的子群，且Se。那么，存在最小正整数m，使得amS，对于任意的aiS，必有i=tm+r(tI+，0rm)，故ar=ai-tm=ai*(amt)-1S。又因为m是使amS的最小正整数，所以r只能取值为0，所以i=tm，即ai= (am)t。这说明，S中任一元素都是am的乘幂。因此，是以am为生成元的循环群。第13页，共58页，2022年，5月20日，11点13分，星期五练习2设是一个独异点，并且对于G中的每一个元素x都有x*x=

9、e，其中e是幺元，证明是一个阿贝尔群。证 1)证G中每个元素均有逆元。 任意xG都有x*x=e，故x-1=x。 2)证运算满足交换律。 任意a,bG都有(a*b)-1=a*b a*b = (a*b)-1 = b-1*a-1 = b*a 运算满足交换律。 综上所述，是一个阿贝尔群。第14页，共58页，2022年，5月20日，11点13分，星期五练习3设G=1,2,3,4,5,6，G上的二元运算7 如表所示。问是循环群吗？若是，求其生成元。7123456112345622461353362514441526355316426654321生成元为：3,5第15页，共58页，2022年，5月20日，1

10、1点13分，星期五5-7 陪集与拉格朗日定理(群的分解)定义5-7.1 设为群,A,B(G),且A， B，记 AB= ab aA,bB和 A-1= a-1 aA 分别称为A，B的积和A的逆。定义5-7.2 设为的子群，那么对任一aG，称aH=a*hhH为H的左陪集(left coset),记为aH;称Ha=h*ahH为H的右陪集(right coset),记为Ha。第16页，共58页，2022年，5月20日，11点13分，星期五陪集举例例1.求出关于子群的所有左陪集,右陪集。解:令H=0,3,则左陪集: 右陪集:0H=0,3=3H H0=0,3=H31H=1,4=4H H1=1,4=H42H=

11、2,5=5H H2=2,5=H5从中可以看出：0H,1H,2H是G的一个划分。第17页，共58页，2022年，5月20日，11点13分，星期五陪集的性质设是的子群,a,bG则aH=bH或aHbH=。证: 对于aH和bH，只有两种情况： aHbH= aHbH 对于第二种情况，设faHbH h1，h2H，使f=a*h1=b*h2 a=b*h2*h1-1bH xaH则h3H,x=a*h3=b*h2*h1-1*h3bH aHbH，同理bHaH aH=bH第18页，共58页，2022年，5月20日，11点13分，星期五拉格朗日定理定理5-7.1(拉格朗日定理) 设为有限群的子群，|G|=n, |H|=m

12、, 那么|G|/|H| = n/m是整数，即m|n 。 第19页，共58页，2022年，5月20日，11点13分，星期五拉格朗日定理的推论推论1 任何质数阶的群不可能有非平凡子群。推论2 设为n阶有限群，那么对于任意aG,a的阶必是n的因子且必有an=e,这里e是群的幺元。如果n为质数，则必是循环群。第20页，共58页，2022年，5月20日，11点13分，星期五拉格朗日定理推论2的证明证:若aG的阶是r,则e,a a2, a3 , ,ar-1是G的子群且该子群的阶为r，由拉格朗日定理可知r整除n，所以a的阶必是n的因子。故n=rt(tI+),故an=e。 设为质数阶群，则 aG 且 ae，

13、a的阶数可整除|G|,但是|G|为质数,所以a的阶数等于群的阶数。 a,a2,ar=G 是循环群第21页，共58页，2022年，5月20日，11点13分，星期五拉格朗日定理练习例1.试证奇数阶群所有元素之积等于幺元。证: 设是一个群,e为幺元,则 在G中不存在这样的元素a：ae，a=a-1 若a=a-1 则a2=e 是的子群 又因为|a,e|=2，所以由拉格朗日定理可得： 2整除|G|，这与G是奇数阶群矛盾。 所以，aG，若ae,a、a-1总是成对出现 G=e,a1,a1-1,a2,a2-1,an,an-1，其中aiai-1 e*a*a1-1*an*an-1 = e第22页，共58页，2022

14、年，5月20日，11点13分，星期五拉格朗日定理练习例2.任何一个四阶群只可能是循环群或者Klein四元群。（P211）证 设四阶群为。其中e是幺元。当四阶群含有一个四阶元素时，这个群就是循环群。 当四阶群不含有四阶元素时，则由推论2可知，除幺元e外，a,b,c的阶一定都是2（幺元是唯一的一阶元）。a*b不可能等于a,b或e，否则根据消去律，将导致b=e,a=e或a=b的矛盾。所以a*b只能等于c。同样地有b*a=c以及a*c=c*a=b,b*c=c*b=a。因此，这个群是Klein四元群。第23页，共58页，2022年，5月20日，11点13分，星期五四阶群（只有两个）Klein四元群：e

15、e a b c e e a b c a a e c b b b c e a c c b a e四阶循环群：e e a b c e e a b c a a b c e b b c e a c c e a b第24页，共58页，2022年，5月20日，11点13分，星期五练习：P211-(5)1、证A非空设的幺元为e，则有 e*H*e-1=H故 eA .2、证 a,bA，a*b-1A = H, 故a*b-1A 第25页，共58页，2022年，5月20日，11点13分，星期五练习：P211-(8)apt-1(apt-1)p第26页，共58页，2022年，5月20日，11点13分，星期五5-8 同态与

16、同构定义5-8.1 设和是两个代数系统，f是从A到B的一个映射， a1,a2A，有 f(a1a2)=f(a1)f(a2)（先算后映=先映后算）则称f为由代数结构到的同态映射，称同态于，记为AB。称为的一个同态象。其中 f(A)=x|x= f(a),a A B第27页，共58页，2022年，5月20日，11点13分，星期五（G，*) (S，o)aba*bf(a)f(b)f(a)of(b)同态象f 通过映射建立了两个代数系统之间的联系。第28页，共58页，2022年，5月20日，11点13分，星期五同构(同态双射)定义5-8.2 当同态映射f分别是入射（单射）、满射、双射时，分别称f是单一同态、满

17、同态、同构映射。如果存在一个从到的同构映射,则称代数系统与同构,记作AB。定义5-8.3 设是一个代数系统，如果f是到的同态,称f为A的自同态。如果是到的同构,称f为A的自同构。 第29页，共58页，2022年，5月20日，11点13分，星期五同构举例例：设H=x|x=dn,dI+,nI,定义映射f: I-H 为对任意I ，有f(n)=dn ，那么，f是到的一个同构，即 IH。例：设fk: I I,fk(x)=kx，其中I为整数集合。fk(x1+x2)=k(x1+x2)=k*x1+k*x2=fk(x1)+fk(x2)fk是从到的自同态,若k0,则fk是单一同态,若k=1,则fk是到的自同构。第

18、30页，共58页，2022年，5月20日，11点13分，星期五同构举例证明：设f:NNk(k0) ，f(x)=x mod k。证明f是到的满同态。证： 设x1= lk + h1,x2= mk + h2 (h1,h2k) 则f(x1+x2)=(x1+x2)mod k =(h1+h2)mod k = h1+kh2 = f(x1)+kf(x2) f(x1+x2) = f(x1)+kf(x2) f是同态。 又因为f是满射 f是到的满同态。第31页，共58页，2022年，5月20日，11点13分，星期五同态象的性质定理5-8.2 设f是由到的一个同态映射。 （a）如果是半群，那么在f作用下，同态象也是半

19、群。 （b）如果是独异点，那么在f作用下，同态象也是独异点。 （c）如果是群，那么在f作用下，同态象也是群。第32页，共58页，2022年，5月20日，11点13分，星期五定理5-8.2的证明证明思路:先证（a）： 是半群 证运算在f(A)上封闭 设是半群， 是一个代数结构，如果f是由到的一个同态。则f(A) B。对于任意的a，bf(A) ，必有x,yA ，使得 f(x)=a ,f(y)=b 。 在A中必有z=xy,所以 ab=f(x)f(y)=f(xy)=f(z)f(A)第33页，共58页，2022年，5月20日，11点13分，星期五 证在f(A)上满足结合律 对于任意的a,b,cf(A),

20、必有x,y,zA,使得 f(x)=a , f(y)=b , f(z)=c 因为在A上是可结合的，所以 a(bc)=f(x)(f(y)f(z)= f(x) f(yz) = f(x(yz) = f(xy)z) = f(xy)f(z) =(f(x)f(y)f(z) = (ab)c 故 是半群。 第34页，共58页，2022年，5月20日，11点13分，星期五再证（b）： 是独异点 设是独异点,e是A中的幺元,那么f(e)是f(A)中的幺元。因对于任意的af(A),必有xA,使得 f(x)=a 所以 af(e)= f(x)f(e)=f(xe)=f(x)=a = f(ex)=f(e)f(x)=f(e)a

21、 因此f(e)是中的幺元， 是独异点。第35页，共58页，2022年，5月20日，11点13分，星期五最后证（c）： 是群 设是群,对于任意的af(A),必有xA,使得 f(x)=a 因为是群, 所以对于任意的xA,都有逆元x-1A，且f(x-1)f(A),而 f(x)f(x-1)= f(xx-1)=f(e)=f(x-1x) = f(x-1)f(x) 所以， f(x-1)是f(x)的逆元。即 f(x-1) =（ f(x)） -1 因此中的任意元素都有逆元, 是群。 综合上述(a)、(b)、(c)三步，定理证毕第36页，共58页，2022年，5月20日，11点13分，星期五同态核定义5-8.4

22、如果f为代数结构到的一个同态映射， G中有么元e，那么称下列集合为f的同态核，记为K(f)。 K(f)=x xGf(x)e第37页，共58页，2022年，5月20日，11点13分，星期五同态核的性质定理5-8.3 设f为群到群的同态映射， 那么f的同态核K是G的子群。证明思路: 设e是的幺元，e=f(e),故eK。 证运算在K上封闭。 设k1,k2K,则 f(k1k2)= f(k1)f(k2)= e e = e 故k1k2K， 运算在K上封闭。 证K中的元素有逆元。 对任意的kK,f(k-1)= f(k) -1= e-1 = e 故k-1K。 结论得证。第38页，共58页，2022年，5月20

23、日，11点13分，星期五同态核举例例: f:,xN,f(x)=x mod 5则 x,yI,f(x+y)=(x+y)mod 5 = x mod 5+5y mod 5 = f(x)+5f(y)f是从到的同态ker(f)=x|xIf(x)=0=0,5,-5,10,-10,第39页，共58页，2022年，5月20日，11点13分，星期五代数结构的划分同余关系 显然整数集合I上的模k余数相等关系R是等价关系。容易证明，对于a,b,c,dI，R对整数上的加运算满足性质：若xy(mod k)且zw(mod k), 则(x+z)(y+w)(mod k), 称这种特殊的等价关系为同余关系。 将上述同余关系推广，

24、则得到代数结构上一般意义的同余关系。第40页，共58页，2022年，5月20日，11点13分，星期五同余关系与同余类定义5-8.5 设R为中A上的等价关系，若R,RR则称R为A上关于二元运算的同余关系。 由这个等价关系将集合划分成的等价类就称为同余类。例：1、前例上的模k余数相等关系就是同余关系。2、上的恒等关系R是同余关系； 第41页，共58页，2022年，5月20日，11点13分，星期五例：，在I上定义R:R|x|=|y|, R是的同余关系吗?解:1)自反性：xI,|x|=|x| R 2)对称性：x,yI,若R 则 |x|=|y| R 3)传递性：x,y,zI，若 R,R 则 |x|=|y

25、|=|z| R R是一等价关系 x1,y1,x2,y2I，若R,R， 但R不一定成立。 例 ,R，但R, R不是同余关系第42页，共58页，2022年，5月20日，11点13分，星期五同余关系与划分 类似于集合论中等价关系及其相应的划分，同余关系所得到的等价类称为同余类，同余类的集合是同余关系所诱导的一个划分。例：课本P218例6。代数系统, A上的运算见表5-8.5，在A上定义的等价关系R见表5-8.6。（1）R是A上关于的同余关系。如何验证？ R,RR（2）R将A划分为同余类：a,b、c,d（3）R诱导的一个划分为： a,b,c,d 第43页，共58页，2022年，5月20日，11点13分

26、，星期五abcdaaadcbbacdccdabdddbaabcdabcd第44页，共58页，2022年，5月20日，11点13分，星期五练习P222(11):设f和g都是群到群的同态，证明是的一个子群，其中 G= x|xG1 且 f(x)=g(x) 第45页，共58页，2022年，5月20日，11点13分，星期五证：(1) 证G是G1的非空子集 设群的幺元为e，则f(e)是群的幺元，同时g(e)也是群的幺元，故f(e)=g(e)，故eG。 (2) 证任意a,bG,有ab-1G 任意a,bG, 有ab-1G1 ， f(ab-1)= f(a)*f(b-1) = g(a)*g(b-1) = g(ab

27、-1) 故ab-1G。 综上所述， 是的一个子群。第46页，共58页，2022年，5月20日，11点13分，星期五5-9 环与域定义5-9.1 设是一个代数系统，如果满足 （1） 是阿贝尔群 （2） 是半群 （3）乘运算对加运算可分配，即对任意元素a,b,c A ，a(bc)= (a b) (a c) (bc)a = (b a) (c a)称代数结构为环（ring）。一般将称为加运算，记为“+”，将称为乘运算，记为“”。第47页，共58页，2022年，5月20日，11点13分，星期五例1. 1)整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环。 2)实系数多项式对于多项式加法,乘法是

28、个环。第48页，共58页，2022年，5月20日，11点13分，星期五环的性质定理5-9.1 设为环，那么对任意a,b,cA，有 （1） a=a= (加法幺元必为乘法零元) （2） a(-b)=(-a)b=-(ab) （3） (-a)(-b)= ab （4） a (b-c)= (a b) - (a c) （5） (b-c) a = (b a) - (c a)其中是加法幺元,-a表示a的加法逆元,并将a+(-b)记为a-b。第49页，共58页，2022年，5月20日，11点13分，星期五特殊的环定义5-9.2 当环中运算满足交换律时,称为交换环；当运算有幺元时,称A为含幺环。两者都含有时，称A为含幺交换环。第50页，共58页，2022年，5月20日，11点13分，星期五特殊的环（续）定义5-9.3 设是一个代数系统，如果满足：(1) 是阿贝尔群 (2) 是可交换独异点，且无零因子，即对任意的a,bA ,a,b,必有ab。 (3) 运算对于运算+是可分配的。则称 为整环。 若既是交换环、含幺环,也是无零因子环,则称R是整环。例： 1) 是整环 2) 不是整环 (有零因子）第51页，共58页，2022年，5月20日，11点13分，星期五整环的性质定理5-9.2 在整环中的无零因子条件等价于消去律(即对于c和ca=cb