离散数学+高等里离散数学课件CHAPT17

1、离离 散散 数数 学学 1第十七章群离离 散散 数数 学学 2目录 群是由非空集合与一个定义在该集合上的二元运算所组成的代数系统。本章介绍： 17.1 群的概念 17.2 子群 17 3 置换群 17.4 陪集与Lagrange定理 17.5 同态与同构离离 散散 数数 学学 317.1 群的概念离离 散散 数数 学学 4群的定义 定义定义17.1.1：设G是一个非空集合，在该集合上有一个二元运算“”。如果该运算满足： 对任意a, bG，有abG； 对任意a, b,cG ，有(ab)c = a(bc) 存在 eG，使对任意aG ，有ea = ae = a； 对任意aG，存在a1G，使得aa1

2、= a1a = e； 则称G为一个群，其中e称为G的单位元， a1称为a的逆元。封闭性结合律有单位元有逆元以后就把群的代数运算称为乘法。P10离离 散散 数数 学学 5群的例子n 例1：G=a，乘法为 aa = a。n aa = aG，满足封闭性；n (aa)a= aa = a(aa)，满足结合律；n 由aa = a可知a是单位元，即e = a；n 由aa = a可知a的逆元就是a，即a1=a；nG是一个群。称为单位元群。n例2：设G是全体整数的集合，于是G对普通加法构成群。n 对m, nG，有m + nG，满足封闭性；n (m + n) + l = m + (n + l)，满足结合律；n 存

3、在单位元0，因为0 + m = m + 0 = m；n 对mG，有mG，m+(m)=m+m=0； nG是一个群。n例3：设G是全体整数的集合，于是G对普通乘法不构成群。n 若G是群，则G的单位元必定是1，但是对于mG，当| m | 1时，m的逆元不存在； nG不是一个群。n例4：设G是全体实数的集合(0除外)，于是，不难验证G对普通乘法构成群。离离 散散 数数 学学 6群的大小 群G的大小是指集合G的大小。对于一个群G， (1)若G是无限集，则称G为无限群； (2)若G是有限集，则称G为有限群。对于有限群，又进一步地称 (3)G为n阶群，若| G | = n。离离 散散 数数 学学 7幂运算

4、由于群对乘法满足结合律，因此多个元素的连乘是有意义的，并可采用任意的计算顺序。 n个相同元素a连乘所得的结果称为a的n次方幂，记为an。 规定：a0 = e，an = ( an )1。容易验证am an = am+n (第一指数律)；(am) n = am n (第二指数律)。离离 散散 数数 学学 8交换群 群的乘法满足结合律，是构成群的必要条件，但是并不要求满足交换律。 若群G的乘法还同时满足交换律，即对任意 a, bG，ab = ba，则称G为Abel (阿贝尔) 群或交换群。 对于交换群，我们有(a b) m = am bm (第三指数律)。因为， (a b) m =ababab=aa

5、abbb= am bm m个m个m个离离 散散 数数 学学 9单位元和逆元的唯一性 定理定理17.1.1：任何群的单位元是唯一的；群中每个元素的逆元也是唯一的。 证明：设群G的单位元为e，于是对aG，有ae = ea = a (17.1) 若另有e满足对aG，有ae = ea = a (17.2)。 则由 a 的任意性，在(17.1)中令a = e,得ee=ee=e;在(17.2)中令a = e，得ee=ee=e,于是e = ee = e。故e = e。 对aG，设b满足ab=ba=e(满足逆元的条件)，则b=be=b(aa1)=(ba)a1= a1。 故b = a1。离离 散散 数数 学学

6、10左单位元和左逆元 定理定理17.1.2：群定义中的条件和可减弱为： (3)G中有左单位元e，即对aG，ea = a； (4)对aG，有左逆元，即a1G，a1a = e。 证明：先证左逆元a1即右逆元，即a a1 = e。 a1G，存在bG，使ba1 = e。于是 aa1 = eaa1 = (ba1)(aa1) = b(a1a)a1 = bea1=ba1=e。 再证左单位元e也是右单位元。对aG，有ae = a(a1a) = (aa1)a = ea = a。 所以左单位元即右单位元，左逆元即右逆元。离离 散散 数数 学学 11可除条件 定理定理17.1.3：群中条件和等价于可除条件：对a,

7、bG，有x, yG，使得xa = b，ay = b。注意：左除和右除一般是不相同的。可除条件说明了什么？可除条件说明了方程： xa = b 和 ay = b在群中都是有解的。这也是群的一个重要性质。n证明：设G为群，对a, bG，令x = ba1, y = a1b, 则有:nxa =(ba1)a = b(a1a)= be = b；ay = aa1b = eb = b。n 反之可除条件成立。任取cG，有xG满足xc = c。令x为eG。又对aG,有yG使cy = a,于是ea = ecy =cy = a，即e为左单位元。n 又对aG，有xG，使xa=e。令x为a1，即a1是a的左逆元。所以G构成

8、群。离离 散散 数数 学学 12消去律 若G上的乘法运算满足：对a, b, cG，若ab = ac或ba = ca，则有b = c。则称G上的乘法运算满足消去律。 群的运算是满足消去律的。因为： 设G是群，a, b, cG。若ab=ac或ba=ca，则用a1左乘ab=ac，右乘ba=ca，就有b=c。如：a1(ab)= a1(ac), (a1a)b=(a1a)c, b=c。 反之，若G上的运算满足封闭性、结合律和消去律，G是否构成群呢？No！No！No！离离 散散 数数 学学 13 若G上的运算满足封闭性、结合律和消去律，G不一定能够构成群。 如：令G为正整数集合，运算为普通乘法，显然满足封闭

9、性、结合律和消去律，但是我们知道，它不构成群，因为除单位元外，它的元素没有逆元。 但是如果G是一个有限集合，则可以构成一个群。集合满足消去律不一定成群离离 散散 数数 学学 14有限集满足消去律可成群 定理定理17.1.4：设G是有限集，于是群G定义中的,可用消去律代替。n证明：设G=a1, a2, , an, aG，由封闭性有：aaiG,i=1,n,于是，aa1, aa2, , aan G。n又由消去律知，若i j，则aai aaj。因此aa1, aa2, , aan = G。n于是G中任意元b可以写成b = aai的形式，即x=ai是方程ax=b的解。同理可证b=xa在G中有解。因此可除条

10、件成立。故G是群。离离 散散 数数 学学 15群表 表示有限集上二元运算的二维表格称为乘法表。 有限群的乘法表称为群表。n例如：设群G = e, a, b，其运算法则可以表示为下面的群表：eabeeabaabebbean由群的运算满足消去律可知，任何群表中不同的行(列)对应的元素均不相同，而且每个元素在群表中的每行(列)恰好出现一次。n此性质是构成有限群的必要条件，但不是充分的。离离 散散 数数 学学 1617.2 子群离离 散散 数数 学学 17子群的概念 定义定义17.2.1：设G是一个群，H是G的非空子集。如果H对G的运算构成一个群，则称H是G的子群，记为HG。 任何群都至少有两个子群，

11、即H=e以及H=G。它们称为G的平凡子群。 例如：整数集Z对加法构成加法群，而偶数集对于加法就构成加法群Z的子群。离离 散散 数数 学学 18子群的不变性 定理定理17.2.1：设G是群，HG，于是H的单位元就是G的单位元，H中 a 的逆元也就是 a 在G中的逆元。 证明：设e是H的单位元，对aHG有ea=a=ea，即ea=ea，由消去律有e=e。 又aHG ，设 a 的逆元为 b，则有ab=e=aa1，于是b=a1。 由此可知子群的单位元和逆元都没有变。离离 散散 数数 学学 19封闭有限子集构成子群 定理定理17.2.2：设G是群，H是G的非空有限子集，于是，若H对G的乘法运算是封闭的，则

12、H必是G的子群。 证明：由HG知，H关于G的运算满足结合律。 任取aH，由封闭性有：a, a2, a3, H。因H是有限集，必存在正整数 i , j，不妨设ij，使得ai = aj，于是有ai = aiaji , aHG且i0,故由消去律有，ai-1 = ai-1aji , ,于是，a = a aji = ajia， 这说明是aji是H的单位元。离离 散散 数数 学学 20封闭有限子集构成子群 定理定理17.2.2：设G是群，H是G的非空有限子集，于是，若H对G的乘法运算是封闭的，则H必是G的子群。 证明：这说明是aji是H的单位元，即e = aji。n下证a的逆元在H中。n若j i 1, 则

13、由aji =e=aaji1知，aji1H是a的逆元。若j i = 1, 则aji =a =e，a以自身为逆元。n总之由群的定义，H是群，故H是G的子群。离离 散散 数数 学学 21封闭无限子集不一定是子群 群的封闭有限子集是子群，那么群的封闭无限子集是不是也构成子群呢？ 不一定！ 例如，整数集Z对普通加法构成加法群，自然数集N是整数集的子集，并且对普通加法运算是封闭的，但是自然数集对加法并不构成群。因为无单位元和逆元。离离 散散 数数 学学 22无限子集构成子群的条件 定理定理17.2.3：设G是群，H是G的非空子集。如果对a, bH有ab1H，则H是G的子群。 证明：H非空, 有aHG, e

14、=aa1H。 对aH, eH, a1 = ea1H。 对a, bH，由 有b1H，又(b1)1=b，ab = a (b1)1 H。即G的运算在H中封闭。 由于HG，因此G的运算在H中满足结合律。 综上所述，H是G的子群。离离 散散 数数 学学 23子群的交集和并集 一个群的若干个子群的交集仍然是它的子群。 证明：设H和K都是群G的子群。eHK， HK非空。任取a, bHK。H和K都是G的子群，b1H且b1K，于是ab1H且ab1K，从而ab1HK。由定理17.2.3知， HK是G的子群。n但是，群的若干个子群的并集不是它的子群。n例如，加法群Z中，03和04都是Z的子群，而它们的并集0304却

15、不是它的子群。离离 散散 数数 学学 24生成的子群 定理定理17.2.4：设G是群，aG，令H = an | nZ(整数集) 于是，H是G的子群，记为H=(a)，并称H是由a生成的子群。 证明：e=a0H，H非空。任取as, atH，则有， as(at)1 = asat = ast H， 故由定理17.2.3知，H = (a)是G的子群离离 散散 数数 学学 25循环群 定义定义17.2.2：设G是群，若有aG，使得(a) = G， 则称G是由a生成的循环群，a称为G的一个生成元。 显然，循环群中的每一个元素都可以表示为a的方幂。 显然，循环群是交换群。离离 散散 数数 学学 26循环群的构

16、造 设G是群，(a)=G，考虑(a)的所有元素：a3, a2, a1, a0, a1, a2, a3, (17.3) 其中a0 = e。关于(17.3)中的元素有两种情形： 所有元素互不相等，即st有as at，则称a的周期(或阶)为无穷大，称(a)为无限循环群。 存在整数s, t，不妨设st，使得as = at 。于是ats = a0 = e，t s 0。若n是使得an = e成立的最小正整数，则称a的周期(或阶)为n，并称(a)为n阶循环群。离离 散散 数数 学学 27循环群举例 例2：加法群Z的生成元有1和1，即Z = ( 1 ) = ( 1 )。而且，两个生成元的周期均为无穷大，所以加

17、法群Z是无限循环群。n例3：设群G = e, a, b, c的n群表如右：eabceeabcaaecbbbcaeccbeanb2=a, b3=c, b4=e, G=(b)。nc2=a, c3=b, c4=e, G=(c)。nG是循环群，b, c是它的两个生成元。离离 散散 数数 学学 28n阶循环群 定理定理17.2.5：若群G中元素a的周期为n，则 e, a, a2, a3, , an1为n个互不相同的元素； am = e当且仅当n | m； as = at当且仅当n | (s t)。 证明：先证。设m = qn+r，0rn，于是am = aqn+r = (an)q ar = ear = a

18、r = e， 0rn, ar=e, 即am=e, 当且仅当r=0, 即n|m。 由知，as = at，当且仅当ast = e，当且仅当n | (s t)。故得证。并由此可知成立。离离 散散 数数 学学 29循环群的子群仍是循环群 定理定理17.2.6：循环群的子群仍是循环群。 证明：设循环群G=(a)，H是G的子群。不妨设H是G的非平凡子群，于是必存在amH，其中m0。令am是H中关于a的最小正幂。 任取asH，设s = t m + r，0rm，于是ar = astm = as (am)t H am是H中a的最小正幂, r=0，即ar =e。 as=(am)t，即H的元素均可表为am的方幂。故

19、 H= ( am )。 离离 散散 数数 学学 30循环群中子群的数量 定理定理17.2.7：无限循环群有无限多个子群，其中除单位元群e是一阶子群外，其余子群均是无限循环群。n 阶循环群的子群的个数等于 n的正因数的个数。 证明：设G = ( a )，H是G的子群。于是根据定理17.2.6，H可写成H = ( am )， 其中，m是H中a的最小正幂。 下面就G是无限群或n阶群分别予以讨论：离离 散散 数数 学学 31无限循环群中子群的数量n定理定理17.2.7(1)：无限循环群有无限多个子群，其中除单位元群e是一阶子群外，其余子群均是无限循环群。 证明：设G是无限循环群，则a的周期为无穷大，任

20、取mZ，am的周期也是无穷大。令Hm为：a3m, a2m, am, a0=e, am, a2m, a3m, 显然Hm是无限循环群。 又对i, jZ，| i | | j |，因a的周期为无穷大，所以HiHj。故G有无穷多个子群。离离 散散 数数 学学 32n阶循环群中子群的数量n定理定理17.2.7(2)： n 阶循环群的子群的个数等于 n的正因数的个数。 证明：设G为n阶循环群，a的周期为n。因m是H中最小正幂，而an=eH，n0,故mn。 令n=q m+t，0tm。于是e = an =aqm at，at=(am)qH，又0tm，故t=0，n=q m。 于是am的周期为q，H = (am)是一

21、个q 阶有限群。 设G另有一个q阶子群H，则H = (am)，于是n=mq=m q。从而m=m，即am=am，H=H。 由此可知，对n的任意因数q，(an/q)就是G的唯一的q阶子群。定理得证。离离 散散 数数 学学 33一个12阶循环群的子群 例如：12阶循环群G= (a) = a1, a2, a3, , a11 , a12 = e。 12的正因数有1, 2, 3, 4, 6, 12，于是G的子群有： (a12/1) = (a12 ) = e ; (a12/2) = (a6) = e, a6 ; (a12/3) = (a4 ) = e, a4 , a8 ; (a12/4) = (a3 ) =

22、 e, a3 , a6 , a9 ; (a12/6) = (a2 ) = e, a2 , a4, a6 , a8 , a10 ; (a12/12) = (a ) = G。离离 散散 数数 学学 34循环群的生成元 定理定理17.2.8：设G=( a )，于是 若a的周期为无穷大，则G只有生成元a和a1。 若a的周期为n，则at是G的生成元当且仅当t与n互质。于是n阶循环群共有(n)个生成元，其中(n)是n的Euler函数。 证明：G=(a)，a是G的生成元。而对于i，ai = (a1) i, 故a1是G的生成元。 设b也是G的生成元，则s, t, 使得b=as, a=bt。于是a=bt=(as

23、)t=ast。因为a的周期无穷大，必有st=1，从而s=1，即b=a或者b=a1。离离 散散 数数 学学 35循环群的生成元 证明： 设a的周期为n，若at是G的生成元，则有G=(a)=(at)，类似地有整数m，使得a = (at)m = atm， 由定理17.2.5知，n | (tm 1)，即tm1=nq，也即tm+nq=1，这说明t与n互质。 反之，若t与n互质，则有整数u, v使得tu + nv = 1。 于是对a，a=a(an)v= a1nv = (at)u，即a可以表示为at的方幂。所以at是G的生成元。 所以，G共有(n)个生成元。离离 散散 数数 学学 36例如： 循环群G=(a

24、)=e,a,a2,a3,a11,因a的周期为12，(12)=4，即与12互质的数为1,5,7,11共4个，因此，G的生成元是：a,a5,a7,a11。下面以a7为例来生成G： a7G， 27=12+2,a27=a12+2=a12a2=ea2=a2 同理，a37=a12+9=a9, a47=a122+4=a4 a57=a122+11=a11, a67=a123+6=a6 a77=a124+1 =a , a87=a124+8=a8 a97=a125+3 =a3, a107=a125+10=a10 a117=a126+5=a5, a127=a0=e离离 散散 数数 学学 3717.3 置换群离离 散

25、散 数数 学学 38置换 定义定义17.3.1：设M是n元有限集。M到M的一个双射称为M上的一个n元置换，简称为置换。 为简单起见，常设M=1, 2, , n，将M上的置换表示为： 1 2 n (1) (2) (n) =n由于是双射，因此(1), , (n)是1,2,n的一个排列。所以n元集合M上一共有n!个n元置换。一般用S n表示这n!个置换作成的集合。离离 散散 数数 学学 39置换的乘法 定义Sn上的乘法运算为：对于, S n，iM， (i) = ( i )，即先执行置换再执行置换。 显然，仍是M上的n元置换。即置换的乘法满足封闭性。n例如：设 =1 2 3 42 1 3 4 =1 2

26、 3 43 2 4 1n则=1 2 3 43 1 4 2=1 2 3 42 3 4 1n由此可知，置换的乘法不满足交换律。(1)=3, (3)=3, (1)= (3)=3 (2)=2, (2)=1, (2)= (2)=1(3)=4, (4)=4, (3)= (4)=4(4)=1, (1)=2, (4)= (1)=2?离离 散散 数数 学学 40置换乘法的性质 满足结合律：() = () 因为对任意iM，有 ()(i) = ()(i) = (i) ()(i) = (i) = (i) 。 Sn的单位元是n元恒等置换 e = 。1 2 n1 2 n显然对Sn，有e = e = 。n对Sn，存在逆元1

27、，使得 1 = 1 = e (恒等置换)。 因为对Sn，存在逆映射1,则对iM ,有 1(i)= 1 (i)=i, 1(i)= (1(i)=i离离 散散 数数 学学 41S n称为n元对称群 定理定理17.3.1：n元集合M上的全体n元置换所组成的集合S n对置换的乘法作成一个群，称为n元对称群，其阶为n！。 证明：因S n对置换乘法是封闭的，满足结合律，有单位元(恒等置换)，有逆元，故S n作成群。n例2：S2 = 1，2是一个2阶交换对称群，其中：1 = e =1 21 2，2 = 1 22 1n例3：S3 = 1, 2, , 6是一个6阶非交换对称群，其中i，1i6， 均为三元置换，例如

28、：6 = 1 2 33 1 2n定义定义17.3.2：对称群的子群统称为置换群。离离 散散 数数 学学 42对称群S4 让我们来看看4元对称群S4： 因|S4| = 4! = 24，所以S4有24个置换。 因此S4就是4个元素的全部排列，即S4 = e=1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321 离离 散散 数数 学学 43轮换表示法n在S3中 6 = 1

29、 2 33 1 2n 表示将1映射到3， 将3映射到2，将2映射到1。于是可将6 写成(132)。n这种表示方法称为轮换表示法n定义定义17.3.2：设M=1, 2, , n， Sn，若存在这样一个序列( i1i2ir )，1rn，使得 ( ij ) = ij+1, j=1,2,r-1； ( ir ) = i1；( is ) = is, s=r+1,n。 则称为一个轮换，记为 = ( i1i2ir )，r称为该轮换的长度，记为| = r；特别地，用( 1 )表示恒等变换e。离离 散散 数数 学学 44轮换表示法 简单地说，一个轮换，比如 = (i1 i2 i3 i4)，就是将i1i2i3i4进

30、行循环变换，即将i1变换成 i2，i2变换成i3， i3变换成i4，i4 变换成i1，而其它的元素依然维持不变。n因为轮换是一种循环变换，所以可选取任意一个元素为首。即(i1 i2 i3 i4)=(i2 i3 i4 i1)=(i4 i1 i2 i3)。n长度为长度为2的轮换称为的轮换称为对换对换。如： =1 2 3 4 51 3 2 4 5= ( 2 3 )。离离 散散 数数 学学 45轮换的性质 定义定义17.3.4：设 = (i1i2ir), = (j1j2js)是M的两个轮换。若i1, i2, , ir j1, j2, , js = ，则称和不相交。 命题命题17.3.1：若和是M上两个

31、不相交的轮换，则= ，即不相交的轮换的乘法满足交换律。 证明：设 = (i1i2ir), = (j1j2js)是M的两个不相交的轮换。对k M，k只能是下列三种情形之一：离离 散散 数数 学学 46命题17.3.1的证明 = (i1i2ir), = (j1j2js) ki1,i2,ir，则kj1,j2,js,不妨设 k=it 1 t r，于是， (k)= (it )= (it)= it+1 (k)= (it)= (it+1)= it+1 当t=r时， it+1=i1，故有(k)= (k)。 k j1,j2,js ，则类似地有(k)= (k)。 ki1,i2,ir且 kj1,j2,js,则 (k

32、)= (k)=k, (k)= (k)=k。 综上所述， (k)= (k)，故= 离离 散散 数数 学学 47n并不是任何一个置换都是一个轮换，例如： =1 2 3 4 53 5 4 1 2n就不能表示为一个轮换。n然而，不难看出可以表示为两个轮换的乘积： = (134) (25) = (25) (134)n这里，(134)和(25)是两个不相交的轮换。离离 散散 数数 学学 48置换是轮换的乘积n命题命题17.3.2：任何置换可表示为互不相交的轮换的乘积。除轮换的秩序外，表示是唯一的。 证明：设是M上的置换，|M| = n。 任取i1M，若(i1)=i1，则令1=(i1)；若(i1)=i2，(

33、i2)=i3，。由于M有限且是双射，所以必ir，使得(ir)=i1，则令1=(i1i2 ir)。 若r=n，则= 1，否则有j1i1, i2, , ir， j1M。于是类似地可得到轮换2=(j1j2 js)。 为是双射，1和2不相交。若r+s=n,则 = 1 2 ，否则如上又可得到一个轮换。如此作下去，由于M有限，最后必有= 12m。即 表示成了互不相交的轮换的乘积。离离 散散 数数 学学 49置换是轮换的乘积 （ = 12m） 设=12m，1, 2, m互不相交。 任取其中某个轮换1= (i1i2 ir)，则i1必出现在某个i中，因为轮换中任意元素可排在首位，所以不妨设i1在i中也是排在首位

34、。又因是双射，则1与j有着完全相同的元素序列。所以1= i 。因此i，必有i=j。即除排列的次序外，置换的轮换表示是唯一的。n命题命题17.3.2：任何置换可表示为互不相交的轮换的乘积。除轮换的次序外，表示是唯一的。n证明：再证除轮换的次序外，表示是唯一的。离离 散散 数数 学学 50用轮换表示S4 S4 = 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4321, 4312, 4231 (

35、1)(34)(23)233442(234)244332(243)(24)(12)(12)(34)(123)12233441(1234)12244331(1243)122441(124)133221(132)13344221(1342)(13)(134)(13)(24)13322441(1324)(1432)(142)(143)(14)(23)(1423)(14)n于是可将S4表示为如下的轮换的形式：nS4=e, (34), (23), (24), (234), (243), (12), (123), (124), (1234), (1243), (12)(34), (13), (132), (

36、134), (1342), (1324), (13)(24), (14), (142), (143), (1432), (1423), (14)(23)离离 散散 数数 学学 51轮换可以表示为对换 设= (i1i2 ir)是一个轮换，不难验证： = (i1i2 ir) = (i1ir) (i1ir1) (i1i3) (i1i2) = (i1i2) (i2i3) (ir1ir)n命题命题17.3.3：任何置换可以表示成为一些对换的乘积，但是表示法不唯一。n例如： =1 2 3 4 52 3 1 5 4n= (123)(45)n= (13)(12)(45)n= (12)(23)(45)n= (1

37、2)(13)(45)(13)(23)让我们来验证一个：(12)(13)(45)(13)(23) 12345=(12)(13)(45)(13) 13245=(12)(13)(45) 31245=(12)(13) 31254=(12) 13254 = 23154离离 散散 数数 学学 52用对换表示S4 于是可将S4表示为如下的对换乘积的形式： S4 = e, (12), (13), (14), (23), (24), (34), (123), (124), (132), (134), (142), (143), (234), (243), (13)(24), (12)(34), (14)(23)

38、, (1234), (1243), (1342), (1324), (1432), (1423) (12)(23), (12)(24), (13)(23), (13)(34),(14)(24), (14)(34), (23)(34), (24)(34),(12)(23)(34),(12)(24)(34),(13)(34)(24),(13)(23)(24),(14)(34)(23),(14)(24)(23)离离 散散 数数 学学 53置换的奇偶性 将n元置换表示为对换的乘积，若其对换的个数是奇数，则称为奇置换，否则称为偶置换。 若= (i1i2 ir)是轮换，则 = (i1i2) (i2i3)(

39、ir1ir)是它的一种对换乘积。它含有r 1个对换。 若 = 12r，其中1, 2 , , r 互不相交。令| i | = li，于是含有的对换个数为: r r(li 1) =li r = n r i=1 i=1n所以若n r为奇数，则 为奇置换；若n r为偶数，则为偶置换。离离 散散 数数 学学 54置换的奇偶性不变 命题17.3.4：将n元置换表示成对换的乘积后，其对换个数的奇偶性由 唯一决定。 证明：首先定义一个n元置换 的符号为：sgn() = (1)nr, 其中= 12 r， 1, 2, , r为互不相交的轮换，且| i | = n。进而证明sgn() = sgn() sgn()。

40、为此证明用对换(is, it)左乘置换将使sgn()变号。 设置换可表示为h个互不相交的轮换，于是is和it出现在中的情况只能有如下两种：离离 散散 数数 学学 55置换的奇偶性不变 证明： is和it分别出现在的两个轮换中，即 = (isj1 jl) (itk1 km) 于是： (isit) =(isj1 jl itk1 km)。？(isit)(isj1 jl) (itk1 km) = (isit) j1 jl is k1 kmit = j1 jl it k1 kmis = (isj1 jl itk1 km)n因为sgn() = (1)nh，而(isit)恰比少一个轮换，所以sgn(isit

41、) = (1) sgn()。n is和it出现在的同一个轮换中，即 = (isj1 jl itk1 km)n于是： (isit) =(isj1 jl) (itk1 km)？(isit)(isj1 jl itk1 km) = (isit) j1 jl it k1 kmis = j1 jl is k1 kmit = (isj1 jl )( itk1 km)n从而也有：sgn(isit) = (1) sgn()。离离 散散 数数 学学 56置换的奇偶性不变 证明：总之，用一个对换乘使sgn()变号，等于nr个对换的乘积，故用乘将使sgn()变号nr次，即sgn() = (1)nr sgn() = s

42、gn() sgn()。 由此可知，奇偶性相同的置换的乘积为偶置换，而奇偶性相异的置换的乘积为奇置换。 因为对换是奇置换，所以奇数(偶数)个对换的乘积是奇置换(偶置换)。所以奇(偶)置换只能表示为奇数(偶数)个对换的乘积。离离 散散 数数 学学 57奇偶置换一样多 命题17.3.5：设M是非空有限集，|M|=n1。于是在M的所有n!个n元置换中，奇置换和偶置换是一样多，都等于n!/2。 证明：设1, 2, , m为Sn中所有偶置换。因为n1，故存在一个对换，使得1, 2, , m为Sn中的m个奇置换。又易知i j，否则将导致i =j (ij)的矛盾。所以奇置换不少于偶置换。 同理可以证明偶置换不

43、少于奇置换。于是两者数目相等，即各为n!/2。离离 散散 数数 学学 58交错群 定理17.3.2：设Sn为n(1)元对称群，令An = iSn | i为偶置换。 则An是Sn的子群，称为n元交错群或交代群，其阶为n!/2。n注意：奇置换不能作成子群！离离 散散 数数 学学 59交错群的例 例4：A3 = e, (123), (132)是S3的子群，是三元交错群，其阶为3。 S4=e, (12), (13), (14), (23), (24), (34), (12)(23), (12)(24), (12)(34), (13)(23), (13)(34), (13)(24), (14)(23),

44、 (14)(24), (14)(34), (23)(34), (24)(34), (12)(23)(34), (12)(24)(34), (13)(34)(24), (13)(32)(24), (14)(42)(23), (14)(43)(23) n于是获得S4的所有偶置换，构成了交换群A4：nA4 = e, (12)(23), (12)(24), (12)(34), (13)(23), (13)(34), (13)(24), (14)(23), (14)(24), (14)(34), (23)(34), (24)(34) n这是四元交错群，其阶为12。离离 散散 数数 学学 60交错群的例

45、例5：K = e, (12)(34), (13)(24), (14)(23)是一个4阶的4元置换群，称为Klien四元群。 不难验证： (12)(34)(13)(24) = (13)(24)(12)(34) = (14)(23); (12)(34)(14)(23) = (14)(23)(12)(34) = (13)(24); (13)(24)(14)(23) = (14)(23)(13)(24) = (12)(34)。(12)(34)(13)(24) 1234 = (12)(34)3412 = 4321 = (14)(23)n因此K具有封闭性，所以K是一个群。n注意：K不是四元交错群，而是四元

46、交错群A4 (也是对称群S4)的子群。离离 散散 数数 学学 61交错群的例 例6：G=e,(12),(34),(12)(34),(13)(24), (14)(23), (1324),(1423)是一个8阶4元置换群，S4的子群。 来验证一个偶置换与奇置换的乘积：(12)(34)(1324)=(12)(34)3421=4312=(1423) 对于其它的也不难验证其封闭性。故G是群。 此例说明奇偶置换混在一起也能作成子群。 当n11，Sn的所有子群已全部找出；当n11，只能找出一些具有特殊性质的置换群。离离 散散 数数 学学 6217.4 陪集与 Lagrange定理离离 散散 数数 学学 63

47、集合的乘积 定义17.4.1：设A，B是群G的两个非空子集，集合AB = ab | aA，bB 称为A与B的乘积。 当集合中只含一个元素时，即当A= a或B=b，AB简记为aB 或Ab。 不难验证，集合的乘法满足结合律。离离 散散 数数 学学 64陪集 定义17.4.2：设H是群G的子群，aG，集合aH (Ha)称为由a 确定的H在G中的左(右)陪集，简称为H的左(右)陪集，a 称为 aH(Ha) 的代表元素。 例1：在加法群Z中，所有5的倍数构成Z的一个子群，5Z = , 15, 10, 5, 0, 5, 10, 15, 。于是以2为代表元素的5Z在加法群Z中的左陪集为：2+5Z = , 1

48、3, 8, 3, 2, 7, 12, 17, 。 实际上2+5Z=k | k2(mod 5)。它不是子群。离离 散散 数数 学学 65左陪集的性质 性质1：aH的元素和H一样多。 性质2：aH = H，当且仅当 aH。 性质3：若baH，则aH = bH。 性质4：aH = bH，当且仅当a1bH，a, bG。 性质5：任意两个左陪集aH和bH或者相等，或者互不相交。 同理可知，左陪集的这些性质对于右陪集同样成立。 离离 散散 数数 学学 66aH和H等势 证明：作H到aH的映射 f 如下：f ( x ) = ax 对任意xH。 显然，f 是一个双射，故 |aH| = |H|。 性质1说明：子

49、群H的任何陪集都和H等势，从而所有陪集的大小也都是一样的。 因此，若用子群的陪集来划分一个群，这个划分必定是均匀的。离离 散散 数数 学学 67自己只能代表自己 证明：设 aH = H。 因为H是G的子群，所以eH，从而ae = aaH =H，故aH。 反之，设aH，任取baH，则有hH，使b = ah，但ahH，因此bH。这说明aHH。又任取bH，因H是群，且aH，故ax=b在H中有唯一解(xH,axaH)。于是baH，这说明HaH。总之有aH = H。 这个性质说明H中元素只能代表H自己。离离 散散 数数 学学 68同陪集者，谁作代表都一样 证明：因为 baH，所以有 hH，使得b = a

50、h，于是bH = (ah)H = a(hH)， 又由性质2，hH = H，故 bH = aH。 性质3说明：一个陪集中的任何元素都可以作为该陪集的代表元素，所确定的陪集都是一样的。离离 散散 数数 学学 69陪集相等的充要条件 证明：设a1bH，则有hH使a1b = h，从而b = ah aH，由性质3知，aH = bH。 反之，设aH = bH。因为eH，所以bebH=aH。从而有hH，使be=ah=b，于是 h= a1bH。 此性质给出了判断两个陪集是否相等的充要条件。离离 散散 数数 学学 70不同的陪集互不相交 证明：若aHbH，则有caH，并且cbH，由性质3，得aH = cH且bH

51、 = cH， 故aH = bH 。 由此性质知，不同的陪集是互不相交的。 因此可以用群G的某个子群H的左(右)陪集来对群G进行划分。离离 散散 数数 学学 71群的陪集分解式 设H是群G的子群，取a1=eG，则H=a1H是H在G中的一个陪集； 若a1HG，则取a2G且a2a1H，得到新的陪集a2H，显然a1Ha2H = ； 若a1Ha2HG，则取a3G且a2a1Ha2H，得到新的陪集a3H；显然a3HaiH=，i = 1, 2； 如此下去，便会有：G = a1Ha2HanH (17.10) 式(17.10)便称为G对H的(左)陪集的分解式。离离 散散 数数 学学 72子群的指数 定义17.4.

52、3：群G对其子群H的(左)陪集的分解式中(左)陪集的个数称为H在G中的指数，记为|G: H|或者(G: H)。 当G是有限群时，|G: H|必是有穷的；当G是无限群时，|G: H|是有穷的还是无穷的与H有关。 例如：|Z: nZ| = n，其中, nZ = in | iZ， Z = nZ(1+nZ)(2+nZ)(n1)+nZ)。 例如：设Q为全体有理数对加法作成的加法群，H是所有偶数作成的子群，于是|Q: H|是无穷的。因2i + H就是无穷个不同的左陪集，i = 0, 1, 离离 散散 数数 学学 73Lagrange定理 定理17.4.1：有限群G的子群H的阶是G的阶的因数，且 |G| =

53、 |G: H| |H|。 证明：设G对H的陪集分解式为G = a1Ha2HamH。 由性质1知，|aiH| = |H|，i = 1, m。又由性质5知，aiHajH=，ij。于是|G| = |aiH| ( i = 1, m ) = |H| = m|H| = |G: H| |H|。离离 散散 数数 学学 74几个推论 推论17.4.1：设G是有限群，|G|=n。于是对任意aG，a的周期必为n的因数，且an = e。n证明：设aG的周期为m，于是H=(a)是G的一个m阶(循环)子群。由Lagrange定理，有m|n。令n=qm，则nan = aqm = (am)q = eq =e,n故an = e

54、。n推论17.4.2：任何质数阶的群只有平凡子群。n推论17.4.3：质数阶的群必是循环群。离离 散散 数数 学学 75正规子群 若G是交换群，则对G的子群及aG，有aH = Ha。若G不是交换群，则不一定成立。n定义17.4.4：H是群G的子群，若对aG，有aH = Ha，n称H是G的正规子群或不变子群，记为HG。n显然，群G的平凡子群都是G的正规子群。n如：对称群S3的子群H1=e, (123), (132)是S3的正规子群，但其它非平凡子群都不是正规的。离离 散散 数数 学学 76正规子群的充要条件 定理17.4.2：H是群G的正规子群，当且仅当对任意aG，有aHa1 H。 证明：设H是

55、G的正规子群，于是对任意aG，有aH=Ha，从而对任意h，有hH使得ah=ha，于是aha1=haa1 ，即aha1H。由h的任意性知，aHa1 H。 反之，设对任意的aG，有aHa1H。于是对于a1G也有a1H(a1)1H，即a1HaH。将此式两边左乘a，右乘a1得HaHa1。因此aHa1=H。从而得aH=Ha，即H是G的正规子群。离离 散散 数数 学学 77交错群是对称群的正规子群 例2：交错群An是对称群Sn的正规子群。 证明：因为奇 (偶)置换的逆置换也同样是奇 (偶)置换，而奇偶不同的两个置换之乘积为奇置换，奇偶相同的两个置换之乘积为偶置换，所以任取置换Sn，An1中都是偶置换，即A

56、n1 An 。 故由定理17.4.2知，An是Sn的正规子群。离离 散散 数数 学学 7817.5 同态与同构离离 散散 数数 学学 79同态 定义17.5.1：设A和B分别是两个带二元运算的代数系统， 是一个从A到B的映射，如果对于任意的x，yA，有(xy) = (x) (y) 则称是A到B的同态， (A)称为A的同态像，其中(A) = bB | aA，使(a)=b B 特别，若(A)=B，即是满射，则称A与B同态，记为A B或A B。 离离 散散 数数 学学 80同态的例子 例1：设整数集Z上定义了普通乘法运算，集合S=1, 0, 1上的乘法表如右下： 1 01110100001101n今

57、定义映射：ZS如下： 1 m0(m) = 0 m = 0 1 m0n不难验证，对任意x, yZ，有(xy) = (x) (y)。于是是Z到S的同态，而且ZS。离离 散散 数数 学学 81同构 定义17.5.2：设是A到B的同态，若是双射，则称为A到B的同构，并记为A B或A B。 n例2：在实数R上定义普通加法运算，在正实数R+上定义乘法运算，并定义映射: RR+如下：(x) = ex。n显然是R到R+的双射，并且对x, yR，有 (x + y) = ex + y = ex ey = (x)(y)，n于是是R到R+的一个同构映射，即R R+。 n代数结构之间的同构关系 是一个等价关系。离离 散

58、散 数数 学学 82自同态和自同构 定义17.5.3：设是A到B的同态，如果BA，则称为A的自同态。 特别，A到A的同构称为自同构。离离 散散 数数 学学 83群的同态像仍是群 定理7.5.1：设G是一个群，H是一个代数系统， 是G到H的同态，则G的同态像G = (G)是一个群。G的单位元是(e)，(a)的逆元是(a1)，e是G的单位元，aG。 证明：因为G是群，所以G非空，从而G非空。 先证G对乘法封闭。任取a, bG，则有a, bG，使得(a)=a，(b)=b。由是同态有ab = (a)(b) = (ab) 因abG，所以abG。故封闭性成立。离离 散散 数数 学学 84群的同态像仍是群

59、证明：再证G中结合律成立。设a, b, cG，则有a, b, cG，使(a)=a，(b)=b，(c)=b。由G是群，有(ab)c=a(bc)。于是由是同态，有 (ab)c=(a)(b)(c) = (ab)(c)= (ab)c) =(a(bc)= (a)(bc)= (a)(b)(c)=a(bc)。 故(ab)c= a(bc)，即结合律成立。离离 散散 数数 学学 85群的同态像仍是群 证明：现证明G有单位元(e)，e是G的单位元。对aG，有aG使(a)=a。因同态有：(e)a= (e) (a)= (ea) = (a)=a， 即(e)a=a， (e)是G的左单位元。 最后证明G中任意元有逆元。任取

60、aG，则有aG使(a)=a。有的同态性得：(a1)a= (a1) (a)= (a1a) = (e)， 即(a1)a=(e)，即G中任意元有左逆元。 由定理17.1.2可知，G是一个群。离离 散散 数数 学学 86像源与核 像源：若G G，则对任意aG，至少有一个元素aG，使得(a)=a。记I(a) = aG | (a) = a， I(a)称为a的像源。G可以看作是G的浓缩或缩影。 定义17.5.2：设G G，e是G的单位元，e的像源称为的核，记为Ker()，即Ker() = aG | (a) = e。 离离 散散 数数 学学 87第一同态定理n定理17.5.2：设G是群，G G，于是， 的核K