离散件11群和环

1、群和环 第一节 运算与代数系统一、运算的概念1。定义：设S是一个非空集合，映射f：Sn S称为集合Sn元运算。 本章只考虑一元和二元运算，即定义中的 n 是 1 或 2。2。运算表示 一元运算主要涉及补运算，并使用习惯的表达方式（如 a ）。1 设是二元运算，它可以用谓词定义，也可以用运算表定义。在表达式中二元运算 ： S 2S使用中缀式表示（如x y）。 下面是用运算表定义运算的例子。设S=a，b，c，d，定义二元运算“”如下： a b c d a a c b d b b d c a c c a d b d d b a c23。二元运算的性质设 * 是集合S上的二元运算， 封闭性： a、b

2、S，a* b S。 交换性： a、b S，a* b =b*a。 结合性： a、b 、cS， (a* b)* c = a* (b* c) 。 幂等性： a S，a* a =a 。设* 和 是集合S上的二元运算， 分配性： a、b 、cS， a* ( b c) = (a* b) (a* c)， a ( b* c) = (a b) * (a c)， 吸收性： a、bS， a* ( a b) = a， a ( a * b) = a 。3二、代数系统 1。定义：由非空集合S及定义在其上的若干运算 1、 2、.、 n构成的系统 S，1、2、.、n 称为代数系统。 例：整数集合上 Z 的代数系统 Z，+、Z

3、， 等，实数集合 R上的代数系统 R，+ 、 R，+，等，幂集合2A上的代数系统2A， 、 2A ，等。4 主要考虑含一或两个二元运算的代数系统。2。代数系统中的特殊元素 设 S，* 是含一个二元运算的代数系统， e S，如果 a S，a* e =e * a = a，就称e是系统的幺元(或单位元) 。 S，如果a S，a* = *a = ，就称是系统的零元。 aS，如果 a* a = a，就称 a 是系统中的幂等元。例：在Z，+中，0是幺元也是幂等元，无零元；在Z，中1是幺元，0是零元； 在2S，中S是幺元， 是零元； 2S，中是幺元， S是零元。5定理： 如果代数系统 S，* 中存在幺元，则

4、幺元是唯一的；如果存在零元，则零元是唯一的。证明：设 e1和 e2是代数系统 S，* 的两个幺元，根据幺元的定义， e1 = e1* e2 =e2。同样，设 1 和 2 是代数系统 S，* 的两个零元，根据零元的定义， 1 = 1* 2 = 2。注意，在同一个集合上定义不同的运算，一般具有不同的幺元和零元。例如， Z，+ 的幺元是0，没有零元。而 Z， 有幺元1和零元0。6 设代数系统 S，* 存在幺元 e。a S，如果存在b S使 a* b = b* a = e，就称b是 a的逆元。例：在Z，+中，a的逆元是-a；在Z，中只有1和-1有逆元； 在2S，中只有S有逆元。定理： 设 S，* 是可

5、结合的、含有幺元 e的代数系统，如果元素 a存在逆元，则逆元是唯一的。证明：设 b和 c是 S，* 中元素 a的两个逆元，那么b = b * e = b* (a* c) = (b * a) * c = e* c = c。 a 的逆元记为 a-1。 73。代数系统 S，* 的分层 如果 S，* 的运算满足封闭性，则称 S，* 为广群； 如果 S，* 为广群，且运算满足结合性，则称 S，*为半群； 如果 S，*为半群，且运算含有幺元，则称 S，*为含幺半群； 如果 S，* 为含幺半群，且每个元素都有逆元，则称S，*为群。8 作业：习题11.1 1、2 (吴子华)or习题十四 4、5 (冯伟森) 附

6、加题：确定 2S，、 2S，、 2S，各属于哪一个层次？9 第二节 半群一、常见半群的例子 1。实数集含幺加半群R，+：封闭、可结合、有幺元 0 。 2。实数集含幺乘半群 R， ：封闭、可结合、有幺元 1。 3。正整数集加半群Z+ ，+：封闭、可结合、无幺元 。10 4。整数集模 n含幺加半群 Zn ， ：封闭、可结合、有幺元 0。 5。整数集模 n含幺乘半群 Zn ， ：封闭、可结合、有幺元 1。 6。在有限字母表上的字符串集*中定义运算“ ”，（称为字符串的连接）。 例如，设=“abc”，=“+*”，则 =“abc+*”。把不含任何字符的字符串称为空串，记为。那么， *， 满足含幺半群的定

7、义，称为 字含幺半群。11二、半群中元素的幂 由于半群 S， 具有结合性，元素自身运算的表达式可以用幂的形式表示出来。 设 a S，定义：a2 = a a， am+1 = am a 如果系统含有幺元 e，规定a0 = e。 根据幂的定义，容易得到 am an = am+n (am)n = amn当运算为“+”时（即为可交换运算时） a的n次幂记为na。因此，对应于上面两式有ma+na=(m+n)a, n(ma)=(nm)a12三、定理 有限半群 S， 必有幂等元，即存在 a S， a2 = a 。证明要点：如果S中有幺元 e，则 e 就是幂等元。如果S中没有幺元，任取 bS，由S的有限性，必有

8、 bi = bj = b j-i bi ( j i )因此，对任何t i bt = bj-i bt = b2( j-i ) bt = . = bk( j-i ) bt 这里k(j - i) i ,再令t=k(j-i ), 则得到 bt = bt bt 即 bt是幂等元。13四、子半群 1。定义：设S，是半群，非空子集T S，如果 T， 也是半群，则称之为 S 的子半群。 例：整数集加半群 Z，+ 是实数集加半群 R，+ 的子半群。 2。要证明 T， 是 S， 的子半群，只要证明“”在T上封闭就行了。14 例：设S， 是含幺半群，令 T=x | x S (yS) x y=y x，即T是由S中能与

9、所有元素交换运算次序的元素构成的子集。证明 T， 是 S， 的含幺子半群。 证明：首先幺元 e T ，其次对任何a、b T和任何y S ，y (a b ) = (y a) b= a (y b ) = (a b) y 即证得 a b T 。也就证明了 T， 是 S， 的含幺子半群。15 作业：习题11.2 3、4(吴子华)or习题十五 3、4 (冯伟森)16第三节 群和子群一、常见群的例子 1。实数集加群 R，+ ：封闭、可结合、有 幺元 0、数a的逆元是 -a 。 2。非零实数集乘群 R-0， ：封闭、可结 合、有幺元 1、数 a的逆元是1/a 。 3。整数集模 n加群 Zn ， ：封闭、可结

10、合、有幺元 0、i 的逆元是 n -i。174。设Mn是全体n阶满秩阵构成的集合，定义运算“”为矩阵的乘法，那么 Mn， 是n 阶满秩矩阵乘群。根据线性代数知识，运算封闭、可结合、有幺元（n阶单位矩阵）、每个满秩阵的逆就是其逆矩阵。 如果在Mn上定义矩阵的加法运算，则因不封闭不构成满秩矩阵加群。185。当 p是素数时， Zp 0， 是模 p乘群：封闭、可结合、有幺元 1，至于元a 的逆 元，由于 a和 p互素，因此存在 i、j使 a i + p j =1，即 a i 1（mod p）。于是ai=1，这说明 a的逆元是 i 。 对于非素数模 n， Zn 0， 不是群。例如 Z6 0， 中2、3、

11、4都没有逆元。196。3个元素集合A=a, b, c上的全体置换集合S3=(a), (ab), (ac), (bc), (abc), (acb)关于置换的复合构成群: 闭, 结, 有幺元(a). 每个循环的逆就是把循环倒过来的结果.一般, n元集合上的全体置换集合Sn关于复合运算构成群在一般情况下，用 G， 表示群.20二、群中元素的幂 半群中元素幂的记号在群中同样适用，只是群中多了元素的负幂概念。定义： am = (a1) m 三、群的性质1。定理 对群 G， 中任何元素a、b，方程 a x = b 和 y a = b 有解 。证明： 因为 x= a1 b 和 y = b a1分别是方程 a

12、 x = b 和 y a = b的解。212。定理 群 G， 中消去律成立。即对任何a、b、c G，如果 a c = b c 或 c a = c b，则 a=b。 证明: 由a c = b c或 c a = c b两端同时与 c的逆进行运算：(a c) c1 = ( b c) c1 或 c1 (c a) = c1 (c b) 就得到 a = b 。223。推论 群 G， 运算表中每行和每列没有相同的元素。证明要点 由 消去律即得。四、子群 1。定义：设 G， 是群，非空子集H G，如果 H， 也是群，则称之为G的子群。23定理 群和子群有共同的幺元。证明 设群 G， 的幺元为e， H， 的幺元

13、为 t，则对任何x H， e x = x = t x， 由消去律，t = e 。显然, G有2个基本子群: 一个是e ， , 另一个是G， . 称为平凡群.例: 在置换群中, H=(a), (ab)构成其子群.24 2。要证明 H， 是 G， 的子群，可以采用如下方式： 按定义证明 “”在 H上封闭、有幺元、每元有逆元。 定理 H， 是 G， 的子群当且仅当对任何a、b H，a b1 H。证明要点: 必要性由子群定义即得. 对于充分性, 可结合性是继承的; 由a,aH, aa-1= e H, 即幺元在H中;由e,aH, ea-1= a-1 H,即每元的逆存在; 对于封闭性, 只要看看a, bH

14、, ab= a(b-1) -1H就行了.下面举一个采用第二种方式的例子。25例：设G， 是群,令H=x | x G (yG) x y=y x，证明 H， 是 G， 的子群。证明：首先证明如果a H，则 a1 H。这是因为对任何y G ，由 a y=y a可得 a1 (a y) a1 = a1 (y a) a1 , 即 y a1 = a1 y。 其次，设a、b H ，对任何y G， y (a b1 ) = (y a) b1 = a (y b1 ) = (a b1) y，即证得a b1 H 。也就证明了 H， 是 G， 的子群。26 作业：习题11.3 1、 4、6or习题十五 6、 9、1127

15、第四节 交换群和循环群一、交换群 1。定义 如果群 G， 满足对任何a、b G，a b= b a， 则称G是交换群。例：实数集加群 R，+ 、非零实数集乘群 R-0， 、整数集模 n加群 Zn ， 、素模p乘群 Zp 0，等都是交换群。而 n阶满秩阵乘群 Mn， 则不是交换群。282。定理 群 G， 是交换群当且仅当 对任何a、b G，(a b)2=a2 b2 。证明 如果G是交换群，按定义， (a b)2 = (a b) (a b) = a (a b) b =a2 b2 。反之，如果对任何a、bG，(a b)2=a2 b2 即 a b a b = a a b b ，由消去律就得到 b a=

16、a b。29定理中的条件也可以是“对任何a、b G， (a b)m=am bm”（m 1) 。 交换群习惯上称为加群。二、循环群 1。定义 如果群 G， 中存在元素 a，使对任何 b G， b= ak， 则称G是循环群。 a 称为G的生成元，或者说G是由a生成的。30例：整数集模 n加群 Zn， 是循环群。例如Z6， 中 1、5 是生成元，因为 1 1=2， 1 2=3， 1 3=4， 1 4=5， 1 5=0，即1是生成元。同样，因为 5 5=4， 5 4=3， 5 3=2， 5 2=1， 5 1=0，即5是生成元。31 素模 p乘群Zp 0，也是循环群，例如 Z7 0， 中3、5都是生成元

17、。因为 3 3=2， 3 2=6， 3 6=4，3 4=5， 3 5=1。同样， 5 5=4， 5 4=6， 5 6=2，5 2=3， 5 3=1。32 例：整数集加群 Z，+是循环群。它的生成元是 1和 -1。注意在加群中幂 ak 表示成 ka，因此, 对任何整数 n，都可以表示成 n=n 1 和 n = (-n) (-1)。循环群一定是交换群。如果 a 是循环群 G， 的生成元，可记群为G=(a)。33 注意，如果a是循环群 G， 的生成元，那么 a-1也是生成元。因为 a = (a-1) -1 。2。定理 每个群都包含循环子群。 证明要点 设 a 是群 G， 的元素，H=ak | k Z

18、=(a)。那么 H， 就是G的 一个循环子群。 这是群中很重要的一种子群，它是由群的 一个元素生成的。34 例：在模 6 加群 Z6， 中, 由 1 或 5 生成 Z6 本身，由 2 或 4 生成子群 0，2，4，由 3 生成子群 0，3。 在 模 7 乘群 Z7 0， 中，由 3或 5 生成 Z7 0自身，而由 2 或 4 生成子群 1，2，4，由 6 生成子群1，6。35三、元素的周期 1。定义 a是群 G， 中元素，e 是单位元，使 an = e 的最小正整数 n，称为 a 的周期。如果不存在这种最小正整数，则说 a 的周期为 。 例：在 Z6， 中 1 和 5 的周期都是 6，2 和

19、4 的周期都是 3，3 的周期是2。36在 Z7 0， 中 3 和 5 的周期都是 6，而 2 和 4 的周期都是 3，6 的周期是2。而整数集加群 Z，+ 的两个生成元 1 和 -1，它们的周期都是 。372。定理 如果群 G， 中元素 a 的周期是 n，那么 am = e n | m； at = ak n | (t-k)； a0 ，a1 ， a2， .，an-1互不相同。证明要点 对于，设 n 除 m的余数是 r，即m= kn + r，于是 am = akn+r = (an)k ar =e，从而 ar = e。又因为 0 r n，所以必须 r=0。对于，由 at = ak 导出at - k

20、 = e，再利用的结果即得。对于，如果有相同的，其指数之差必须能被 n整除，但这是不可能的。38 作业：习题11.4 2、3、4(吴子华)or习题十五 16、17、18 (冯伟森)39第五节 陪集与拉格朗日定理一、陪集1、定义：设是群的子群，aG,记aH=a*h|hH,称aH为子群H(关于a)的左陪集。同样可以定义右陪集, Ha=h*a|hH40例: 对于群 Z7 0， 及其子群H= 1, 6 , 1H=6H=H; 2H= 2, 5 =5H; 3H= 3, 4 =4H.当aH时, aH=Ha=H.当运算*可以交换时, 对任何aG, aH=Ha.一般, aHHa.由左(右)陪集所构成的集合的基数

21、成为子群的指标.子群 Z7 0，的指标为3.41例: 对于置换群及其子群H=(a), (ab)左陪集有: (a)H=(a), (ab)=(ab)H,(ac)H=(ac), (abc)=(abc)H,(bc)H=(bc), (acb)=(acb)H,右陪集有: H(a)=(a), (ab)=H(ab),H(ac)=(ac), (acb)=H(acb),H(bc)=(bc), (abc)=H(abc),422.左陪集的性质群G中任何元素必属于某个左陪集.因为对任何aG, aaH同一左陪集的元素, 其左陪集相同; 即abH时, baH.因为abH时, aH(bH)H = bH, 同理bHaH任何2个

22、左陪集要么相等,要么不相交.如果aHbH,必有h1和h2使ah1=bh2,即abH, baH.任何2个左陪集等势.据消去律, aH与H等势这几条性质对右陪集同样成立。433。定理：定义群G上的二元关系R=(x,y)|x,y G yxH, 则R是G上的等价关系。证明要点：自反性由性质；对称性、传递性由性质。4。群的陪集分解根据上面定理，可知每个左陪集就是一个等价类。因此左陪集分解式为： G = eH a1H a2H aiH 同理，右陪集分解式为： G = He Ha1 Ha2 Hai 44例 对于群Z70， 及其子群H=1,6,左陪集分解式为：Z70= 1H 2H 3H =1,62,53,4右陪

23、集分解式为:Z70= H1 H2 H3 =1,62,53,445例 对于置换群及其子群H=(a), (ab)左陪集分解式为：S3 = (a)H (ac)H (bc)H =(a), (ab)(ac), (abc)(bc), (acb)右陪集分解式为:S3 = H(a) H(ac) H(bc) =(a), (ab)(ac), (acb)(bc), (abc)465。Lagrange定理：设H是有限群G的子群，那么H的阶是G的阶的因子。证明要点：由陪集性质及群的陪集分解式可得：|G|=(k+1)|H|推论：有限群中每个元素的周期是群的阶的因子。证明要点：因为每个元素a可以生成一个阶与元素周期相同的有

24、限子群(a)。47例。群Z70， 的子群H=1,6由6生成，周期为2；子群T=1，2，4由2或4生成，周期为3。例。置换群的子群H=(a),(ab)由(ab)生成，周期为2；子群T=(a)，(abc)，(acb)由(abc)或(acb)生成，周期为3。486。正规子群定义：设群是群的子群，如果对任何aG都有aH=Ha，则称是的正规子群。显然，交换群的任何子群都是正规子群。定理：H是G的正规子群当且仅当对任何aG，都有aHa-1 H。证明要点：如果H是G的正规子群，则对任何aG，有aH=Ha，即aHa-1 H；反之，如果对任何aG，都有aHa-1 H，则aH Ha，再由陪集等势得到aH=Ha。例

25、: G中与每个元素可交换的元素全体构成G的正规子群。49作业：习题11。5 1、2、4(1)(2) (吴子华)or 习题十五 22、23、25(1) (2) (冯伟森)50第六节 群的同态一、同态的概念 1。定义 设 A， 和 B，* 是两个代数系统，如果存在映射 f：A B，使对任何a1、a2 A， f(a1 a2) = f(a1) * f(a2)， 就说 f是 A到 B的同态映射，或 A(在 f下) 同态于B，并记为A B。当 f是双射时，就说 A同构于 B，并记为A B。A在 f 下的同态像记为 f (A)。51例： Z ， + 同态于 Z6 ， 。因为存在映射 f：Z Z6 ，使对任何

26、a Z， f (a) = a。由此，对任何x、y Z， f (x+y) =x+y=x y=f(x) f(y)， 也就是说 Z 同态于 Z6 。容易看出 f 是满射但不是单射。52例：设2Z为偶数集合，那么 Z，+ 同构于2Z，+ 。因为存在双射 f：Z 2Z ，使对任何a Z，f (a) = 2a（线性函数），并满足对任何x、yZ， f (x+y) =2(x+y)=2x + 2y= f(x) + f(y)。 也就是说，Z同构于 2Z。 532。定理： 设 A， 和 B，* 是两个代数系统，如果A B，同态映射为f，那么 如果“”在A上是封闭的，则 “*”在f(A)上也是封闭的; 如果“”在A上是结合的，则 “*”在f(A)上也是结合的; 如果“”在A上的幺元是 e，则“*”在f(A)上的幺元是f(e); 如果“”在A上每元有逆元，则“*” 在f(A)上每元有逆元。证明要点：对于 ，如果x y A，那么f(x y