赵洪銮《离散数学》第五章5,7节.ppt

1,复习,一、代数系统的性质与特殊元素 二、特殊的代数系统： 半群 独异点 群 三、子系统： 子半群 子群,2,1、阿贝尔群 定义5-5.1：如果群中的运算*是可交换的，则称该群为阿贝尔群(Abel)，或称交换群。 思考：与群的关系 满足哪些条件,5-5 阿贝尔群和循环群,3, 满足封闭性和可结合性 f0是 的幺元； f0，f2的逆元是自身，f1 ，f3互逆， 由运算表可知是可交换的。 是一个阿贝尔群,例1：设S=a,b,c,d，双射函数f：f(a)=b，f(b)=c，f(c)=d，f(d)=a，构造复合函数，f0(x)= x，f1=f，f2=f(f(x)，； 构造集合F=f0, f1, f2, f3，证明是一个阿贝尔群。,证明： F=f0，f1，f2，f3上的运算表如下,4,定理5-5.1：设是一个群，是阿贝尔群的充要条件是对任意的a, bG，有(a*b)*(a*b)=(a*a)*(b*b)。,证明：充分性： a*(a*b)*b = ( a*a )*(b*b ) = (a*b)*(a*b) = a*(b*a)* b a-1*(a*(a*b)*b)*b-1= a-1*(a*(b*a)*b)*b-1， 得： a*b=b*a 可交换 是阿贝尔群。 必要性：设是阿贝尔群，则对任意的a, bG 有 a*b=b*a 则 (a*a)*(b*b)=a*(a*b)*b =a*(b*a)*b=(a*b)*(a*b),5,定义5-5.2：设为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为循环群，元素a称为循环群G的生成元。 即 G是由a生成的循环群xG，iZ使x=ai,2、循环群,6,例：设是由下面的运算表定义的四阶群，G是否为循环群。,b1=b b2=b*b=a b3=a*b=c b4=c*b=e,c1=c c2=c*c=a c3=a*c=b c4=b*c=e,循环群的生成元不唯一,7,定理5-5.2：任何一个循环群必定是阿贝尔群,证明：设是一个循环群，它的生成元是a，那么对于任意的x, yG， 必有r, sI，使得 x=ar， y=as x*y= ar * as= ar+s = y*x， 是一个阿贝尔群。,8,定理5-5.3 设是一个由元素aG生成的有限循环群。如果G的阶数是n，即|G|=n，则an=e，且G=a, a2, a3, , an-1, an=e，其中，e是中的幺元，n是使an=e的最小正整数(称n为元素a的阶)。,证明: (1)不存在m，m是循环群，xG，有x=ak(kI) 且k=mq+r，其中q是k/m的商，r是余数，显然0 r m 所以有ak=amq+r=(am)q*ar=ar 与|G|=n相矛盾,9,(2)a，a2，an各不相同 假定ai=aj，且1 ijn，有aj-i=e 且1j-in，这在前面证明是不可能的，故a，a2，an各不相同，因此G=a, a2, , an=e,为群，则其为循环群的充要条件是在G中存在一个阶为n的元素a，其中|G|=n。,10,例3 设G=，在G上定义二元运算*，求证是一个循环群。,证明：由运算表可知，*是封闭的。 是幺元， 、的逆元分别是、 。 在这个代数系统中，有 2 = ， 3 = ， 4 = ， 2 = ， 3 = ， 4 = 又(x*y)*z=(i*j)*k=(i+j)+k =i+(j+k)=x*(y*z) 所以*是可结合的。 即是一个群。 群是由或生成的循环群。,11,引言： 群的每一个子系统，并不一定都是它的子群，拉格朗日定理阐明了群与子群之间的一种重要关系，根据这个定理，能够求出成为子群的那些子系统。群的任意子群将G分解成H在G中的陪集。,5-7 陪集与拉格朗日定理,12,分别称为A，B的积和A的逆。,定义5-7.1 设是一个群，A，BP (G)且A，B，,例如： ，A=1,2, B=6,7,8, 则 AB=? 当A=1，则 AB=? A-1=? 注： A、B的积与迪卡尔积之间似乎？,一、基本定义,13,定义5-7.2 令是群的子群且aG，则集合aH (Ha)，称为由元素a所确定H在群中的左陪集(右陪集)，简称为H关于a的左陪集(右陪集)，记为aH(Ha)。元素a称为左陪集aH(Ha)的代表元素。,aH=a*h|hH,14,设H=p1, p4，则说明是的子群，求中H的左陪集。,例 S=p1，p2，p3，p4，p5，p6 ,为群，其运算表,p1H=p1 * p1, p4=p1 * p1, p1 * p4=p1, p4 p2H=p2 * p1, p4=p2 * p1, p2 * p4=p2, p6 p3H=p3 * p1, p4=p3 * p1, p3 * p4=p3, p5 p4H=p4 * p1, p4=p4 * p1, p4 * p4=p4, p1 p5H=p5 * p1, p4=p5 * p1, p5 * p4=p5, p3 p6H=p6 * p1, p4=p6 * p6, p1 * p4=p6, p2,p1, p4, p2, p6, p3, p5构成S的一个划分。,15,例 设是群的子群，其中 H=4i|iI=, -8, -4, 0, 4, 8, ，则中的H的不同陪集是： 0H=0+H=, -8, -4, 0, 4, 8, ， 1H=1+H=, -7, -3, 1, 5, 9, ， 2H=2+H=, -6, -2, 2, 6, 10, ， 3H=3+H=, -5, -1, 3, 7, 11, ， I=0 1 2 3,16,定理5-7.1(拉格朗日定理) 设是群的一个子群，那么 (a) R=|aG, bG且a-1*bH是G中的一个等价关系。对于aG，若记aR=x|xG且R 则 aR =aH,证明： (1)证R为等价关系， aG，a-1*aH，R自反 R，a-1*bH，(a-1*b)-1H，b-1*aH, R对称 R, R，则a-1*bH， b-1*cH，于是(a-1*b) * (b-1*c)= a-1*c H, 故 R. 传递 (2) b aR当且仅当R，即a-1*bH，也即baH， 所以aR=aH,二、拉格朗日定理,17,证明(b) R是等价关系，则a1R，a2R，akR为G的一个划分，即a1H, a2H, , akH为G的一个划分。 从而|G|=|a1H|+|a2H|+|akH| 又对于b1，b2H，且b1b2，有ai*b1ai*b2，（为什么） 所以|aiH|=|H|， a1Ha2HakH=G ，ij aiHajH= 故 n=|G|=|a1H|+|a2H|+|ak