1 (1) 设V=&S, ? &是代数系统，?为二元运算，如果?运算是可 结合的，则称V为半群. (2) 设V=&S,?&是半群，若e∈S是关于?运算的单位元，则称V 是含幺半群，也叫做独异点. 有时也将独异点V 记作 V=&S,?,e&. (3) 设V=&S,?&是独异点，e?S关于?运算的单位元，若 ?a?S，a?1?S，则称V是群. 通常将群记作G.3实例例1 (1) &Z+,+&,&N,+&,&Z,+&,&Q,+&,&R,+&都是半群，+是普通加 法. 这些半群中除&Z+,+&外都是独异点 (2) 设n是大于1的正整数，&Mn(R),+&和&Mn(R),? &都是半 群，也都是独异点，其中+和? 分别表示矩阵加法和矩阵 乘法 (3) &P(B),?&为半群，也是独异点，其中?为集合对称差运算 (4) &Zn, ?&为半群，也是独异点，其中Zn={0,1,…,n?1}，? 为模n加法 (5) &AA,?&为半群，也是独异点，其中?为函数的复合运算 (6) &R*,?&为半群，其中R*为非零实数集合，?运算定义如 下：?x, y?R*, x?y=y4实例例2 设G={ e, a, b, c }，G上的运算由下表给出，称为Klein 四元群??????????e e a b cabc特征：e a a e b c c bb c c b e a a e1. 满足交换律 2. 每个元素都是自己的逆元 3. a, b, c中任何两个元素运算结 果都等于剩下的第三个元素5有关群的术语定义10.2 (1) 若群G是有穷集，则称G是有限群，否则称为无 限群. 群G 的基数称为群 G 的阶，有限群G的阶记作|G|. (2) 只含单位元的群称为平凡群. (3) 若群G中的二元运算是可交换的，则称G为交换群或阿贝 尔 (Abel) 群.实例： &Z,+&和&R,+&是无限群，&Zn,?&是有限群，也是 n 阶群. Klein四元群是4阶群. &{0},+&是平凡群. 上述群都是交换群，n阶(n≥2)实可逆矩阵集合关于矩阵乘法 构成的群是非交换群.6群中元素的幂定义10.3 设G是群，a∈G，n∈Z，则a 的 n次幂.???e ? n ?1 n a ??a ?(a ?1 )m ?n?0 n?0 n ? 0, n ? ? m群中元素可以定义负整数次幂. 在&Z3,? &中有 ? ?2?3 = (2?1)3 = 13 = 1?1?1 = 0 在&Z,+&中有 (?2)?3 = 23 = 2+2+2 = 67元素的阶定义10.4 设G是群，a∈G，使得等式 ak=e 成立的最小正整数 k 称为a 的阶，记作|a|=k，称 a 为 k 阶元. 若不存在这样的正 整数 k，则称 a 为无限阶元. 例如，在&Z6,?&中， 2和4是3阶元， 3是2阶元， 1和5是6阶元， 0是1阶元. 在&Z,+&中，0是1阶元，其它整数的阶都不存在.8群的性质：幂运算规则定理10.1 设G 为群，则G中的幂运算满足： (1) ?a∈G，(a?1)?1=a (2) ?a,b∈G，(ab)?1=b?1a?1 (3) ?a∈G，anam = an+m，n, m∈Z (4) ?a∈G，(an)m = anm，n, m∈Z (5) 若G为交换群，则 (ab)n = anbn. 证 (1) (a?1)?1是a?1的逆元，a也是a?1的逆元. 根据逆元唯一 性，等式得证. (2) (b?1a?1)(ab)= b?1(a?1a)b = b?1b = e, 同理 (ab)( b?1a?1)=e， 故b?1a?1是ab的逆元. 根据逆元的唯一性等式得证.9群的性质：方程存在惟一解定理10.2?G为群，?a,b∈G，方程ax=b和ya=b在G中有解且 仅有惟一解. 证 a?1b 代入方程左边的x 得 a(a?1b) = (aa?1)b = eb = b 所以a?1b 是该方程的解. 下面证明惟一性. 假设c是方程ax=b的解，必有ac=b，从而有 c = ec = (a?1a)c = a?1(ac) = a?1b 同理可证ba?1是方程 ya=b的惟一解. 例3 设群G=&P({a,b}),?&，其中?为对称差. 解下列群方程： ??????? {a}?X=?，Y?{a,b}={b} 解 X={a}?1??={a}??={a}， Y={b}?{a,b}?1={b}?{a,b}={a}10群的性质：消去律定理10.3 ?G为群，则G中适合消去律，即对任意a,b,c∈G 有 (1) 若 ab = ac，则 b = c. (2) 若 ba = ca，则 b = c. 证明略 例4 设G = {a1, a2, … , an}是n阶群，令 aiG = {aiaj | j=1,2,…,n} 证明 aiG = G. 证 由群中运算的封闭性有 aiG?G. 假设aiG?G，即 |aiG| & n. 必有aj,ak∈G使得 aiaj = aiak （j ≠ k） 由消去律得 aj = ak, 与 |G| = n矛盾.11群的性质：元素的阶定理10.4 ?G为群，a∈G且 |a| = r. 设k是整数，则 (1) ak = e当且仅当r | k (2 )|a?1| = |a| 证 (1) 充分性. 由于r|k，必存在整数m使得k = mr，所以有 ???? ? ?ak = amr = (ar)m = em = e. 必要性. 根据除法，存在整数 m 和 i 使得 ??? ? k = mr+i, 0≤i≤r?1 从而有 e = ak = amr+i = (ar)mai = eai = ai 因为|a| = r，必有i = 0. 这就证明了r | k. (2) 由 (a?1)r = (ar)?1 = e?1 = e 可知 a?1 的阶存在. 令|a?1| = t，根据上面的证明有t | r. a又是 a?1的逆元，所以 r | t. 从而证明了r = t，即|a?1| = |a| 12实例例 5 设G是群，a,b∈G是有限阶元. 证明 (1) |b?1ab| = |a| (2) |ab| = |ba| 证 (1) 设 |a| = r，|b?1ab| = t，则有 ? ?? ?1 r ?1 ?1r个(b ab) ? (b ab)(b ab)...(b ?1ab) ???? ????? ? ? ? b ?1a r b ? b ?1eb ? e从而有t | r. 另一方面，由 a = (b?1)?1(b?1ab)b?1可知 r | t. 从而 有 |b?1ab| = |a|.13实例(2) 设 |ab| = r，|ba| = t，则有 ???(ab) t ?1 ? (ab)(ab)...(ab) ?? ??? ? ?t ? 1个? a(ba)(ba)...(ba)b ?? ??? ? ?t个? a(ba) t b ? aeb ? ab由消去律得 (ab)t = e，从而可知，r | t. 同理可证 t | r. 因此 |ab| = |ba|.1410.2 子群与群的陪集分解定义10.5 设G是群，H是G的非空子集， (1) 如果H关于G中的运算构成群，则称H是G的子群, 记作 H≤G. (2) 若H是G的子群，且H?G，则称H是G的真子群，记作 H&G. 例如 nZ (n是自然数) 是整数加群&Z,+& 的子群. 当n≠1时, nZ是Z的真子群.对任何群G都存在子群. G和{e}都是G的子群，称为G的平凡 子群.15子群判定定理1定理10.5（判定定理一） 设G为群，H是G的非空子集，则H是G的子群当且仅当 (1) ?a,b∈H有ab∈H (2) ?a∈H有a?1∈H. 证 必要性是显然的. 为证明充分性，只需证明e∈H. 因为H非空，存在a∈H. 由条件(2) 知a?1∈H，根据条件(1) aa?1∈H，即e∈H.16子群判定定理2定理10.6 （判定定理二） 设G为群，H是G的非空子集. H是G的子群当且仅当?a,b∈H 有ab?1∈H. 证 必要性显然. 只证充分性. 因为H非空，必存在a∈H. 根据给定条件得aa?1∈H，即e∈H. 任取a∈H, 由e,a∈H 得 ea?1∈H，即a?1∈H. 任取a,b∈H，知b?1∈H. 再利用给定条件得a(b?1) ?1∈H，即 ab∈H. 综合上述，可知H是G的子群.17子群判定定理3定理10.7 （判定定理三） 设G为群，H是G的非空有穷子集，则H是G的子群当且仅当 ?a,b∈H有ab∈H. 证 必要性显然. 为证充分性，只需证明 a∈H有a?1∈H. 任取a∈H, 若a = e, 则a?1 = e∈H. 若a≠e，令S={a,a2,…}，则S?H. 由于H是有穷集，必有ai = aj（i&j）. 根据G中的消去律得 aj?i = e，由a ≠ e可知 j?i&1，由此得 ? ?a j?i?1a = e 和 a a j?i?1 = e 从而证明了a?1 = a j?i?1∈H.18典型子群的实例:生成子群定义10.6 设G为群，a∈G，令H={ak| k∈Z}， 则H是G的子群，称为由 a 生成的子群，记作&a&. 证 首先由a∈&a&知道&a&≠?. 任取am,al∈&a&，则 ?? ?am(al)?1 = ama?l = am?l∈&a& 根据判定定理二可知&a&≤G. 实例： 例如整数加群，由2生成的子群是 &2&={2k | k∈Z}=2Z &Z6,? &中，由2生成的子群&2&={0,2,4} Klein四元群 G = {e,a,b,c}的所有生成子群是： &e&={e}, &a&={e,a}, &b&={e,b}, &c&={e,c}.19典型子群的实例:中心C定义10.7 设G为群,令 C={a| a∈G∧?x∈G(ax=xa)}， 则C是G的子群，称为G的中心.证 e∈C. C是G的非空子集. 任取a,b∈C，只需证明ab?1与G 中所有的元素都可交换. ?x∈G，有 (ab?1)x = ab?1x = ab?1(x?1)?1 = a(x?1b)?1 = a(bx?1)?1 = a(xb?1) = (ax?1)b?1 = (xa)b?1 = x(ab?1) 由判定定理二可知C≤G. 对于阿贝尔群G，因为G中所有的元素互相都可交换，G的中 心就等于G. 但是对某些非交换群G，它的中心是{e}.20典型子群的实例:子群的交例6 设G是群，H,K是G的子群. 证明 (1) H∩K也是G的子群 (2) H∪K是G的子群当且仅当 H?K 或 K?H 证 (1) 由 e∈H∩K 知 H∩K 非空. 任取a, b∈H∩K，则a∈H, a∈K, b∈H, b∈K. 必有ab?1∈H 和 ab?1∈K，从而ab?1∈H∩K. 因此H∩K?G. (2) 充分性显然，只证必要性. 用反证法. 假设 H?K 且K?H，那么存在 h 和 k 使得 ? ?? h∈H∧h?K, k∈K∧k?H 推出 hk ?H. 否则由h?1∈H 得 k=h?1(hk)∈H，与假设矛盾. 同理可证 hk ?K. 从而得到 hk ?H∪K. 与H∪K是子群矛盾.21子群格定义10.8 设G为群, 令 L(G) = {H | H是G的子群} 则偏序集& L(G), ? &称为G的子群格 实例： Klein四元群的子群格如下：图122陪集定义与实例定义10.9 设H是G的子群，a∈G.令 ???????Ha={ha | h∈H} 称Ha是子群H在G中的右陪集. 称a为Ha的代表元素. 例7 (1) 设G={e,a,b,c}是Klein四元群，H=&a&是G的子群. H所有的右陪集是： ?He={e,a}=H, Ha={a,e}=H, Hb={b,c}, Hc={c,b} 不同的右陪集只有两个，即H和{b,c}.23实例(2) 设A={1,2,3}，f1, f2, …, f6是A上的双射函数. 其中 f1={&1,1&,&2,2&,&3,3&}， f2={&1,2&,&2,1&,&3,3&} ??f3={&1,3&,&2,2&,&3,1&}， f4={&1,1&,&2,3&,&3,2&} ??f5={&1,2&,&2,3&,&3,1&}， f6={&1,3&,&2,1&,&3,2&} 令 G = {f1, f2, … , f6}，则G 关于函数的复合运算构成群. 考虑 G 的子群H={f1, f2}. 做出 H 的全体右陪集如下： Hf1={f1?f1, f2?f1}=H , Hf2={f1?f2, f2?f2}=H Hf3={f1?f3, f2?f3}={f3, f5}, Hf5={f1?f5, f2?f5}={f5, f3} Hf4={f1?f4, f2?f4}={f4, f6}, Hf6={f1?f6, f2?f6}={f6, f4} 结论： Hf1=Hf2，Hf3=Hf5，Hf4=Hf6. ????24陪集的基本性质定理10.8 设H是群G的子群，则 (1) He = H (2) ?a∈G 有a∈Ha 证 (1) He = { he | h∈H } = { h | h∈H } = H (2) 任取 a∈G，由a = ea 和 ea∈Ha 得 a∈Ha25陪集的基本性质定理10.9 设H是群G的子群，则?a,b∈G有 ??? ? ?a∈Hb ? ab?1∈H ? Ha=Hb 证 先证a∈Hb ? ab?1∈H ?a∈Hb ? ?h(h∈H∧a=hb) ? ?h(h∈H∧ab?1=h) ? ab?1∈H 再证 a∈Hb ? Ha=Hb. 充分性. 若Ha=Hb，由a∈Ha 可知必有 a∈Hb. 必要性. 由 a∈Hb 可知存在 h∈H 使得 a =hb，即b =h?1a 任取 h1a∈Ha，则有 ???h1a = h1(hb) = (h1h)b∈Hb 从而得到 Ha ? Hb. 反之，任取h1b∈Hb，则有 ???h1b = h1(h?1a) = (h1h?1)a∈Ha 从而得到Hb ? Ha. 综合上述，Ha=Hb得证.26陪集的基本性质定理10.10 设H是群G的子群，在G上定义二元关系R： ?a,b∈G, &a,b&∈R ? ab?1∈H 则 R是G上的等价关系，且[a]R = Ha.证 先证明R为G上的等价关系. 自反性. 任取a∈G，aa?1 = e∈H ? &a,a&∈R 对称性. 任取a,b∈G，则 &a,b&∈R?ab?1∈H?(ab?1)?1∈H?ba?1∈H?&b,a&∈R 传递性. 任取a,b,c∈G，则 &a,b&∈R∧&b,c&∈R ? ab?1∈H∧bc?1∈H ? ac?1∈H ? &a,c&∈R 下面证明：?a∈G，[a]R = Ha. 任取b∈G， b∈[a]R ? &a,b&∈R ? ab?1∈H ? Ha=Hb ? b∈Ha27推论推论 设H是群G的子群, 则 (1) ?a,b∈G，Ha = Hb 或 Ha∩Hb = ? (2) ∪{Ha | a∈G} = G 证明：由等价类性质可得. 定理10.11 设H是群G的子群，则 ????? ?a∈G，H ≈ Ha 证明 略28左陪集的定义与性质设G是群，H是G的子群，H 的左陪集，即 ??????aH = {ah | h∈H}，a∈G 关于左陪集有下述性质： (1) eH = H (2) ?a∈G，a∈aH (3) ?a,b∈G，a∈bH ? b?1a∈H ? aH=bH (4) 若在G上定义二元关系R， ???? ?a,b∈G，&a,b&∈R ? b?1a∈H 则R是G上的等价关系，且[a]R = aH. (5) ?a∈G，H ≈ aH ?29Lagrange定理定理10.12 （Lagrange）设G是有限群，H是G的子群，则 ????????|G| = |H|? [G:H] 其中[G:H] 是H在G中的不同右陪集(或左陪集) 数，称为H在 G 中的指数. 证 设[G:H] = r，a1,a2,…,ar分别是H 的r个右陪集的代表元素， ??? ?G = Ha1∪Ha2∪…∪Har ???????|G| = |Ha1| + |Ha2| + … + |Har| 由|Hai| = |H|，i = 1,2,…,r, 得 ???????|G| = |H|? = |H|? r [G:H]30Lagrange定理的推论推论1 设G是n阶群，则?a∈G，|a|是n的因子，且有an = e. 证 任取a∈G，&a&是G的子群，&a&的阶是n的因子. &a&是由a生成的子群，若|a| = r，则 ???????&a& = {a0=e,a1,a2,…,ar?1} 即&a&的阶与|a|相等, 所以|a|是n的因子. 从而an = e. 推论2 对阶为素数的群G，必存在a∈G使得G = &a&.证 设|G| = p，p是素数. 由p≥2知G中必存在非单位元. 任取a∈G，a ≠ e，则&a&是G的子群. 根据拉格朗日定理， &a&的阶是p的因子，即&a&的阶是 p或1. 显然&a&的阶不是1， 这就推出G = &a&.31Lagrange定理的应用命题：如果群 G 只含 1 阶和 2 阶元，则 G 是Abel群. 证 设a为G中任意元素，有a?1 = a. 任取 x, y∈G，则 xy = (xy)?1 = y?1x?1 = yx， 因此G是Abel群. 例8 证明 6 阶群中必含有 3 阶元. 证 设G是6 阶群，则G中元素只能是1阶、2阶、3阶或6阶. 若G中含有6 阶元，设为a，则 a2是3 阶元. 若G中不含6 阶元，下面证明G中必含有3阶元. 如若不然，G 中只含1阶和2阶元，即?a∈G，有a2=e，由命题知G是Abel 群. 取G中2阶元 a 和 b，a ? b，令 H = {e, a, b, ab}，则H 是 G的子群，但 |H| = 4，|G| = 6，与拉格朗日定理矛盾.32Lagrange定理的应用例9 证明阶小于6 的群都是Abel群. 证 1 阶群是平凡的，显然是阿贝尔群. 2, 3和5都是素数，由推论2它们都是单元素生成的群，都是 Abel群. 设G是4阶群. 若G中含有4阶元，比如说a，则G=&a&，由上 述分析可知G是Abel群. 若G中不含4阶元，G中只含1阶和2 阶元，由命题可知G也是Abel群.3310.3 循环群与置换群定义10.10 设G是群，若存在a∈G使得 ???? ?G={ak| k∈Z} 则称G是循环群，记作G=&a&，称 a 为G 的生成元. 循环群的分类：n 阶循环群和无限循环群. 设G=&a&是循环群，若a是n 阶元，则 ???????G = { a0=e, a1, a2, … , an?1 } 那么|G| = n，称 G 为 n 阶循环群. 若a 是无限阶元，则 ?????G = { a0=e, a±1, a±2, … } 称 G 为无限循环群.34循环群的生成元定理10.13 设G=&a&是循环群. (1) 若G是无限循环群，则G只有两个生成元，即a和a?1. (2) 若G是 n 阶循环群，则G含有?(n)个生成元. 对于任何小 于n且与 n 互质的数r∈{0,1,…,n-1}, ar是G的生成元.?(n)成为欧拉函数，例如 n=12，小于或等于12且与12互素的正整数有4个： 1, 5, 7, 11，所以?(12)=4.35证明证 (1) 显然&a?1&?G. ?ak∈G， ak=(a?1)?k ?&a?1&， 因此G?&a?1&，a?1是G的生成元. 再证明G只有a和a?1这两个生成元. 假设 b 也是G 的生成元， 则 G=&b&. 由a∈G 可知存在整数 t 使得a = bt. 由b∈G = &a& 知存在整数 m 使得 b = am. 从而得到 a = bt = (am)t = amt 由G中的消去律得 amt?1 = e 因为G是无限群，必有mt?1 = 0. 从而证明了m = t = 1或 m = t = ?1，即 b = a 或 b = a?136证明(2) 只须证明：对任何正整数 r ( r≤n)， ar是G的生成元 ? n与r互质.充分性. 设r与n互质，且r≤n，那么存在整数 u 和 v 使得 ???? ????ur + vn = 1 从而 a = aur+vn = (ar)u(an)v = (ar)u 这就推出?ak∈G，ak = (ar)uk∈&ar&，即G?&ar&. 另一方面，显然有&ar&?G. 从而G = &ar&. 必要性. 设ar是G的生成元，则 |ar| = n. 令r与n的最大公约数 为d，则存在正整数 t 使得 r = dt. 因此, |ar| 是n/d的因子，即 n整除n/d. 从而证明了d = 1.37实例例10 (1) 设G={e, a, … , a11}是12阶循环群，则?(12)=4. 小于12且 与12互素的数是1, 5, 7, 11, 由定理10.13可知 a, a5, a7 和 a11是G的生成元. (2) 设G=&Z9,?&是模9的整数加群，则?(9)=6. 小于9且与9互 素的数是 1, 2, 4, 5, 7, 8. 根据定理10.13，G的生成元是1, 2, 4, 5, 7和8. (3) 设G=3Z={3z | z∈Z}, G上的运算是普通加法. 那么G只有 两个生成元：3和?3.38循环群的子群定理10.14 设G=&a&是循环群. (1) 设G=&a&是循环群，则G的子群仍是循环群. (2) 若G=&a&是无限循环群，则G的子群除{e}以外都是无限 循环群. (3) 若G=&a&是n阶循环群，则对n的每个正因子d，G恰好含 有一个d 阶子群.39证明证 (1) 设H是G=&a&的子群，若H={e}，显然H是循环群，否 则取H中的最小正方幂元am，下面证明H=&am&. 易见&am& ? H. 下面证明H?&am&. 为此，只需证明H中任何元素都可表成 am的整数次幂. 任取al∈H，由除法可知存在整数 q 和 r，使得 ???? l = qm+r， 其中 0≤r≤m?1 ????ar = al?qm = al(am)?q 由al, am∈H 且 H 是G 的子群可知ar∈H. 因为am是H中最小正方幂元，必有r = 0. 这就推出 ?????al = (am)q∈&am&40证明(2) 设G=&a&是无限循环群，H是G 的子群. 若H≠{e}可知H = &am&，其中am为H中最小正方幂元. 假若 |H|=t，则 |am|=t， 从而得到amt = e. 这与a为无限阶元矛盾. (3) 设G=&a&是 n 阶循环群，则 G = { a0=e, a1, … , an?1 } 下面证明对于n的每个正因子d都存在一个d阶子群. 易见 H ?? a n / d ? 是G的d 阶子群. 假设H1=&am&也是G的d 阶子 群，其中 am 为 H1中的最小正方幂元. 则由 (am)d = e 可知 n 整 除md，即 n/d 整除 m. 令m = (n/d)? l，l是整数，则有a m ? (a n / d ) l ? H这就推出H1?H. 又由于 |H1| = |H| = d，得H1 = H.41实例例11 (1) G=&Z,+&是无限循环群，其生成元为1和?1. 对于自然数 m∈N，1的m次幂是m，m生成的子群是mZ，m∈N. 即 &0& = {0} = 0Z ? &m& = {mz | z∈Z}= mZ， m&0(2) G=Z12是12阶循环群. 12正因子是1,2,3,4,6和12，G 的子群: 1阶子群??&12&=&0&={0} ? 2阶子群??&6&={0,6} ? 3阶子群? &4&={0,4,8}???????????? ? 4阶子群? &3&={0,3,6,9}?? ? 6阶子群??&2&={0,2,4,6,8,10}? ? 12阶子群? &1&=Z12 ?????42n 元置换及乘法定义10.11 设 S = {1, 2, …, n}, S上的任何双射函数 σ:S→S 称为S上的n元置换. 例如 S={1, 2, 3, 4, 5}, 下述为5元置换? 1 2 3 4 5? ? ?? ? 5 3 2 1 4 ?, ? ? ?? 1 2 3 4 5? ? ?? ? 4 3 1 2 5? ? ? ?定义10.12 设σ,τ是n元置换, σ和τ的复合σ ?τ 也是n元置换, 称为σ与τ 的乘积, 记作σ τ. 例如? 1 2 3 4 5? ? 1 2 3 4 5? ?? ? ? ? 5 1 3 4 2 ?, ? ? ? ? 1 2 5 3 4 ? ? ? ? ? ? ? ?43n元置换的轮换表示设 S = {1, 2, …, n}，对于任何S上的 n 元置换 ?, 存在着一个 有限序列 i1, i2, …, ik, k≥1, (可以取i1=1) 使得 ??? ?(i1) = i2, ?(i2) = i3, …, ?(ik?1) = ik, ?(ik) = i1 令 ?1 = (i1 i2 … ik), 是 ? 分解的第一个轮换. 将 ? 写作 ?1??, 继续对 ?? 分解. 由于S 只有n 个元素, 经过有限步得到 ??? ? = ? 1 ? 2 … ? t 轮换分解式的特征 ? 轮换的不交性 ? 分解的惟一性: 若 ? = ?1?2 …?t 和 ? = ?1?2 …?s 是?的两个轮换表示式，则有 ? { ?1, ?2, …, ?t } = {?1,? 2, …,?s }44实例例12 设S = {1, 2, … , 8},? ??1 2 ? ?? ?5 3 ? ?1 2 ? ?? ?8 1 ?3 4 5 6 7 8? ? 6 4 2 1 8 7? ? 3 4 5 6 7 8? ? 4 2 6 7 5 3? ?则 轮换分解式为： ???? = (1 5 2 3 6) (4) (7 8) = (1 5 2 3 6) (7 8) ?? ? = (1 8 3 4 2) (5 6 7) ??45置换的对换分解设S = {1,2,…,n}，? = (i1 i2 … ik) 是S上的 k 阶轮换， ? 可以 进一步表成对换之积，即 ???? (i1 i2 … ik) = (i1 i2) (i1 i3) … (i1 ik) 任何n元置换表成轮换之积，然后将每个轮换表成对换之积.例如 8 元置换 ? = (1 5 2 3 6) (7 8) = (1 5) (1 2) (1 3) (1 6) (7 8) ? = (1 8 3 4 2) (5 6 7) = (1 8) (1 3) (1 4) (1 2) (5 6) (5 7)46对换分解的特征? 对换分解式中对换之间可以有交，分解式也不惟一. 例如4元置换 ? 1 2 3 4? ? ?? ? 2 3 1 4? ? ? ?可以有下面不同的对换表示： ? ? = (1 2) (1 3)，? ? = (1 4) (2 4) (3 4) (1 4)? 表示式中所含对换个数的奇偶性是不变的. 如果n元置换? 可以表示成奇数个对换之积，则称?为奇置 换，否则称为偶置换，不难证明奇置换和偶置换各有n!/2 个.47n元置换群所有的 n元置换构成的集合Sn关于置换乘法构成群， 称为n 元对称群. n元对称群的子群称为n元置换群.例13 设 S = {1, 2, 3}， 3元对称群 S3={ (1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2) } (1) (1) (1 2) (1 3) (2 3) (1 2 3) (1 3 2) (1 2) (1 3) (1 2) (1 3) (1) (1 2 3) (1 3 2) (1) (1 2 3) (1 3 2) (2 3) (1 2) (1 3) (2 3) (2 3) (1 2 3) (2 3) (1 2 3) (1 3 2) (1 3) (1 2 3) (2 3) (1) (1 2) (1 3) (1 3 2) (1 2) (1) (1 3 2) (1 3 2) (2 3) (1 2) (1 3) (1) (1 2 3)48(1) (1 2) (1 3) (2 3) (1 2 3) (1 3 2)Sn的子群n元交错群An是Sn的子群， An是所有的n元偶置换的集合. 证 恒等置换(1) 是偶置换，所以An非空. 根据判定定理三，只需证明封闭性： 任取?,? ∈An， ?, ? 都可以表成偶数个对换之积，那么? ? 也可以表成偶数个对换之积，所以? ? ∈An. 实例：S3的子群格 S3={(1), (12), (13), (23), (123), (132)}, A3={(1), (123), (132)}, {(1)}, {(1), (12)}, {(1), (13)}, {(1), (23)}.49Polya定理定理10.15 设N={1,2,…,n}是被着色物体的集合, G={?1, ?2, … , ?g}是N上的置换群. 用m种颜色对N中的元素进行着色， 则在G的作用下不同的着色方案数是1 g c (? k ) M? ?m | G | k ?1其中c(?k)是置换?k的轮换表示中包含1-轮换在内的轮换个数.Polya定理主要用于等价类的计数.50Polya定理在组合计数中的应用例14 用两种颜色着色方格图形，允许方 格绕中心转动. 求不同的方案数. 群G中的所有置换是： ?1=(1)，?2=(1234)， ?3=(13)(24)，?4=(1432) 代入Polya定理得 1 4 M ? ( 2 ? 21 ? 2 2 ? 21 ) ? 6 45110.4 环与域定义10.12 设&R,+,? &是代数系统，+和? 是二元运算. 如果满足 以下条件: (1) &R,+&构成交换群 (2) &R,? &构成半群 (3) ? 运算关于+运算适合分配律 则称&R,+,? &是一个环.通常称+运算为环中的加法，? 运算为环中的乘法. 环中加法单位元记作 0，乘法单位元（如果存在）记作1. 对任何元素 x，称 x 的加法逆元为负元，记作?x. 若 x 存在乘法逆元的话，则称之为逆元，记作x?1.52环的实例例15 (1) 整数集、有理数集、实数集和复数集关于普通的加法和 乘法构成环，分别称为整数环Z，有理数环Q，实数环R 和复数环C. (2) n(n≥2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构 成环，称为 n 阶实矩阵环. (3) 集合的幂集P(B)关于集合的对称差运算和交运算构成环. (4) 设Zn＝{0,1, ... , n－1}，?和?分别表示模n的加法和乘 法，则&Zn,?,?&构成环，称为模 n的整数环.53环的运算性质定理10.16 设&R,+,? &是环，则 (1) ?a∈R，a0 = 0a = 0 (2) ?a,b∈R，(?a)b = a(?b) = ?ab (3) ?a,b,c∈R，a(b?c) = ab?ac， (b?c)a = ba?ca (4) ?a1,a2,...,an,b1,b2,...,bm∈R (n,m≥2)???? ?(? ai ) (? b j ) ? ?? ai b ji ?1 j ?1 i ?1 j ?1 n m n m证 (1) ?a∈R有 a0 = a(0+0) = a0+a0 由环中加法的消去律得a0=0. 同理可证0a=0. (2) ?a,b∈R，有 ? ???(?a)b+ab =(?a+a)b = 0b = 0 ?????ab+(?a)b =(a+(?a))b = 0b = 0 (?a)b是ab的负元. 由负元惟一性(?a)b= ?ab，同理a(?b)= ?ab 54证明(4)(4) 证明思路：用归纳法证明 ?a1, a2, ... , an 有(? ai )b j ? ? ai b ji ?1 i ?1?????????nn同理可证, ?b1, b2, ..., bm有ai (? b j ) ? ? ai b jj ?1 j ?1mm于是(? ai )(? b j ) ? ? ai (? b j ) ? ?? ai b ji ?1 j ?1 i ?1 j ?1 i ?1 j ?1nmnmnm55实例例16 在环中计算(a+b)3, (a?b)2解 ?(a+b)3 = (a+b)(a+b)(a+b) ???? ???? = (a2+ba+ab+b2)(a+b) = a3+ba2+aba+b2a+a2b+bab+ab2+b3?? (a?b)2 = (a?b)(a?b) = a2?ba?ab+b256特殊的环定义10.13 设&R,+,? &是环 (1) 若环中乘法 ? 适合交换律，则称R是交换环 (2) 若环中乘法 ? 存在单位元，则称R是含幺环 (3) 若?a,b∈R，ab=0 ? a=0∨b=0，则称R是无零因子环 (4) 若R既是交换环、含幺环、无零因子环，则称R是整环 (5) 设R是整环，且R中至少含有两个元素. 若?a∈R*，其中 R*=R?{0}，都有a－1∈R，则称R是域.57实例例17 (1) 整数环Z、有理数环Q、实数环R、复数环C都是交换 环,含幺环,无零因子环和整环. 除了整数环以外都是域. (2) 令2Z={2z | z∈Z}，则&2Z,+,? &构成交换环和无零因子环. 但不是含幺环和整环. (3) 设n?Z, n?2, 则n阶实矩阵的集合Mn(R)关于矩阵加法和乘 法构成环，它是含幺环，但不是交换环和无零因子环， 也不是整环. (4) &Z6,?,?&构成环，它是交换环, 含幺环, 但不是无零因子 环和整环. 2?3=3?2=0，2和3是零因子. ? 注意：对于一般的n, Zn是整环当且仅当n是素数.58实例例18 设 p为素数，证明Zp是域.证 p为素数，所以 |Zp|≥2. 易见Zp可交换，单位元是1 对于任意的 i, j∈Zp, i ≠ 0有 ????i ? j = 0 ? p 整除 ij ? p| j ? j = 0 所以 Zp 中无零因子，Zp为整环. 下面证明每个非零元素都有逆元. 任取 i∈Zp，i ≠ 0，令? ??????i ?Zp = { i ?j | j∈Zp} 则 i ?Zp = Zp，否则? j, k∈Zp，使得 i ?j = i ? k，由消去律 得 j = k. 由1∈Zp，存在 j∈Zp，使得 i ?j = 1. 由于交换性可知 j 就是 i 的逆元.59第十章 习题课主要内容 ? 半群、独异点与群的定义 ? 群的基本性质 ? 子群的判别定理 ? 陪集的定义及其性质 ? 拉格朗日定理及其应用 ? 循环群的生成元和子群 ? 置换群与Polya定理 ? 环的定义与性质 ? 特殊的环60基本要求? ? ? ? ? ? ? ? ? 判断或证明给定集合和运算是否构成半群、独异点和群 熟悉群的基本性质 能够证明G的子集构成G的子群 熟悉陪集的定义和性质 熟悉拉格朗日定理及其推论，学习简单应用 会用Polya定理进行计数 会求循环群的生成元及其子群 熟悉n元置换的表示方法、乘法以及n元置换群 能判断给定代数系统是否为环和域61练习11. 判断下列集合和运算是否构成半群、独异点和群. (1) a 是正整数，G = {an | n?Z}, 运算是普通乘法. (2) Q+是正有理数集，运算为普通加法. (3) 一元实系数多项式的集合关于多项式加法. 解 (1) 是半群、独异点和群 (2) 是半群但不是独异点和群 (3) 是半群、独异点和群 方法：根据定义验证，注意运算的封闭性62练习22. 设V1= &Z, +&, V2 = &Z, ?&,其中Z为整数集合, + 和? 分别 代表普通加法和乘法. 判断下述集合S是否构成V1和V2的子 半群和子独异点. (1) S= {2k | k?Z} (2) S= {2k+1 | k?Z} (3) S= {?1, 0, 1}解 (1) S关于V1构成子半群和子独异点，但是关于V2仅构成子 半群 (2) S关于V1不构成子半群也不构成子独异点，S关于V2构 成子半群和子独异点 (3) S关于V1不构成子半群和子独异点，关于V2构成子半群 和子独异点63练习33. 设Z18 为模18整数加群, 求所有元素的阶.解： |0| = 1, |9| = 2， |6| = |12| = 3, |3| = |15| = 6, |2| = |4| = |8| = |10| = |14| = |16| = 9, |1| = |5| = |7| = |11| = |13| = |17| =18,说明： ? 群中元素的阶可能存在，也可能不存在. ? 对于有限群，每个元素的阶都存在，而且是群的阶的因子. ? 对于无限群，单位元的阶存在，是1；而其它元素的阶可 能存在，也可能不存在.（可能所有元素的阶都存在，但是 群还是无限群）.64练习44．证明偶数阶群必含2阶元. 由 x2 = e ? |x| = 1 或2. 换句话说, 对于G中元素x，如果 |x| &2, 必有x?1? x. 由于 |x| = |x?1|，阶大于2的元素成对出现，共有偶数个. 那么剩下的 1 阶和 2 阶元总共应该是偶数个. 1 阶元只有 1 个，就是单位元，从而证明了G中必有 2 阶元.65有关群性质的证明方法有关群的简单证明题的主要类型 ? 证明群中的元素某些运算结果相等 ? 证明群中的子集相等 ? 证明与元素的阶相关的命题. ? 证明群的其它性质，如交换性等. 常用的证明手段或工具是 ? 算律：结合律、消去律 ? 和特殊元素相关的等式，如单位元、逆元等 ? 幂运算规则 ? 和元素的阶相关的性质. 特别地，a为1阶或2阶元的充分必要 条件是a?1= a.66证明方法? 证明群中元素相等的基本方法就是用结合律、消去律、单 位元及逆元的惟一性、群的幂运算规则等对等式进行变形 和化简. ? 证明子集相等的基本方法就是证明两个子集相互包含 ? 证明与元素的阶相关的命题，如证明阶相等，阶整除等. 证明两个元素的阶r 和 s 相等或证明某个元素的阶等于r， 基本方法是证明相互整除. 在证明中可以使用结合律、消 去律、幂运算规则以及关于元素的阶的性质. 特别地，可 能用到a为1阶或2阶元的充分必要条件是a?1 = a.67练习55．设G为群，a是G中的2 阶元，证明G中与a可交换的元素构 成G的子群.证 令H= { x | x?G ? xa = ax}, 下面证明H是G的子群. 首先e属于H，H是G的非空子集. 任取x, y ?H，有 (xy?1) a = x(y?1a ) = x(a?1y)?1 = x(ay)?1 = x(ya)?1 = xa?1y?1 = xay?1 = axy?1 = a(xy?1) 因此 xy?1属于H. 由判定定理命题得证.分析： 证明子群可以用判定定理，特别是判定定理二. 证明的步骤是： ? 验证 H 非空 ? 任取 x, y?H，证明xy?1?H68练习66. (1) 设G为模12加群, 求&3& 在G中所有的左陪集 (2) 设 X= {x | x?R, x ?0,1}, 在X上如下定义6个函数： f1(x) = x， f2(x) =1/x, f3(x) = 1?x, f4(x) = 1/(1?x), f5(x) = (x?1)/x, f6(x) = x/(x?1), 则G = {f1, f2, f3, f4, f5, f6}关于函数合成运算构成群. 求子群 H={f1, f2} 的所有的右陪集.解 (1) &3& = {0, 3, 6, 9}, &3&的不同左陪集有3个，即 0+&3& = &3&, 1+&3& = 4+&3& = 7+&3& = 10+&3& = {1, 4, 7, 10} , 2+&3& = 5+&3& = 8+&3& = 11+&3& = {2, 5, 8, 11}. (2) {f1, f2}有3个不同的陪集，它们是： H，Hf3 = {f3, f5}, Hf4 = {f4, f6}.69练习77．设 H1,H2分别是群G 的 r, s 阶子群，若(r,s) = 1，证明 H1?H2 = {e}. 证 H1?H2≤H1，H1?H2 ≤H2. 由Lagrange定理，|H1?H2| 整除r，也整除s. 从而 |H1?H2| 整除 r与s 的最大公因子. 因 为(r,s) = 1, 从而 |H1?H2 | = 1. 即 H1?H2 = {e}. 某些有用的数量结果：设a是群G元素，C为G的中心 N(a)={ x | x?G, xa=ax }， ? |C| 是 |N(a)| 和 |G| 的因子，|a| 是 |N(a)| 和 |G| 的因子 ? |H| = | xHx?1| ? |an| 是 |a| 的因子 ? a2=e ? a=a?1? |a|=1,270练习88．设 i 为虚数单位，即 i 2 = ?1, 令? ? 1 0? ?i 0 ? ? 0 1? ? 0 i ?? G ? ?? ? ? 0 1 ?， ? ? 0 ? i ?, ? ? ? 1 0 ?, ? ? i 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ?则G关于矩阵乘法构成群. 找出G的所有子群. 解 令A, B, C, D分别为? 1 0? ? i 0 ? ? 0 1? ? 0 i ? ? ? 0 1 ?，0 ? i ?, ? ? 1 0 ?, ? i 0 ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ?G的子群有6个，即 平凡子群：&A& = {A}, G 2 阶子群：&-A& = {A, -A}, 4 阶子群：&B& = {A,B,-A,-B}, &C& = {A,C,-A,-C}, &D& = {A,D,-A,-D},A -A B -B C -C D -DA A -A B -B C -C D -D-A -A A -B B -C C -D DB B -B -A A -D D C -C-B -B B A -A D -D -C CC C, -C D -D -A A -B B-C -C C -D D A -A B -BD D -D -C C B -B -A A-D -D D C -C -B B A -A 71练习99．设群G的运算表如表所示，问G是否为循环群？如果是， 求出它所有的生成元和子群. 解 易见 a 为单位元. 由于|G|=6, |b|=6, 所以 b 为生 成元. G=&b&为循环群. |f |=6, 因而 f 也是生成元 |c|=3, |d|=2, |e|=3, 因此 c,d, e不 是生成元. 子群：&a&={a}, &c&={c, e, a}, &d&={d, a}, G .a b c d e f a b c d e f a b c d e f b c d e f a c d e f a b d e f a b c e f a b c d f a b c d e72练习1010. 证明Fermat小定理：设 p为素数，则 p|(np?n)证：考虑一个圆环上等距离穿有 p个珠子，用 n 种颜色对珠 子着色. 考虑围绕中心旋转，则群是 G={ ?1, ?2, … , ?p } ?1=(?)(?)…(?) ?2=(? ? … ?) … ?p=(? ? … ?) 根据Polya定理，不同的着色方案数是 1 p 1 p 1 M ? [n ? ( p ? 1)n ] ? ( n ? n ? pn) p p p?n) 于是 p|(n73练习1111. 在整数环中定义?和◇两个运算, ?a,b∈Z 有 a?b = a+b?1, a◇b = a+b?ab. 证明&Z, ?,◇&构成环证 ?a,b∈Z有a?b, a◇b∈Z, 两个运算封闭. 任取a,b,c∈Z (a?b)?c = (a+b?1)?c = (a+b?1)+c?1 = a+b+c?2 a?(b?c) = a?(b+c?1) = a+(b+c?1)?1 = a+b+c?2 (a◇b)◇c = (a+b?ab)◇c = a+b+c? (ab+ac+bc)+abc a◇(b◇c) = a◇(b+c?bc) = a+b+c? (ab+ac+bc)+abc ?与◇可结合，1为?的单位元. 2?a为a关于?的逆元. Z关于? 构成交换群, 关于◇构成半群. ◇关于? 满足分配律. a◇(b?c) = a◇(b+c?1) = 2a+b+c?ab?ac?1 a◇b)?(a◇c) = 2a+b+c?ab?ac?1 &Z, ?,◇&构成环74练习1212. 判断下列集合和给定运算是否构成环、整环和域, 如果 不构成, 说明理由. (1) A = { a+bi | a,b∈Q }, 其中i2= ?1, 运算为复数加法和乘法. (2) A={ 2z+1 | z∈Z}, 运算为实数加法和乘法 (3) A={ 2z | z∈Z}, 运算为实数加法和乘法 (4) A={ x | x≥0∧x∈Z}, 运算为实数加法和乘法. (5) A ? {a ? b4 5 | a, b ? Q} , 运算为实数加法和乘法解 (1) 是环, 是整环, 也是域. (2) 不是环, 因为关于加法不封闭. (3) 是环, 不是整环和域, 因为乘法没有么元. (4) 不是环, 因为正整数关于加法的负元不存在. (5) 不是环, 因为关于乘法不封闭.75
离散数学ch10―汇集和整理大量word文档,专业文献,应用文书,考试资料,教学教材,办公文档,教程攻略,文档搜索下载下载,拥有海量中文文档库,关注高价值的实用信息,我们一直在努力,争取提供更多下载资源。