离散数学(二)拉格朗日定理.pdf

离散数学离散数学 二二 第七讲第七讲 计算机学院计算机学院 焦晓鹏焦晓鹏 拉格朗日定理拉格朗日定理 陪集陪集1 11 1 拉格朗日定理拉格朗日定理2 2 主要内容主要内容 陪集的性质陪集的性质重点重点 重点和难点重点和难点 一 陪集一 陪集 陪集的定义 陪集的定义 设为的子群 对任一a G 定义 aH a H a h h H 称为元素元素a关于关于H的左陪集的左陪集 a 左陪集左陪集aH的表示元素的表示元素 Ha H a h a h H 称为元素元素a关于关于H的右陪集的右陪集 a 右陪集右陪集Ha的表示元素的表示元素 例例1 是的子群 则 3I 3 i i I I 4I 4 i i I I 2 5I 2 5 i i I 3 4I 3 4 i i I 3I 4I 2 5I 3 4I 一 陪集一 陪集 定理定理1 设是群的子群 aH和bH是任意二个左陪集 那么 或aH bH或aH bH 思路 令命题思路 令命题P aH bH 命题命题Q aH bH 要证要证P Q为真 即要证为真 即要证 P Q为真 即要证为真 即要证 aH bH aH bH 证明证明 假设aH bH 我们证明aH bH 设aH bH 那么必存在一个公共元素f 有f aH bH 则存在 h1 h2 H 使f a h1 b h2 因此 a b h2 h1 1 下面证明下面证明aH bH x aH 存在h3 H使得x a h3 因而x b h2 h1 1 h3 根据H 中运算的封闭性知h2 h1 1 h3 H 所以x bH 同理可证同理可证bH aH 因此 因此aH bH 一 陪集一 陪集 定理定理2 设为的子群 则H的任意左陪集的大小 基 数 是相同的 即对任意a b G有 aH bH H 证明证明 假设H h1 h2 hm 那么aH a h1 a h2 a hm 定义函数f H aH 对任何一h H f h a h f H aH单射 对 h1 h2 H 若h1 h2 则a h1 a h2 f H aH为满射是显然的 因此f为双射 故 aH H 得证 一 陪集一 陪集 定理定理3 设是群的子群 则H 的所有左陪集构成G的 一个划分 证明证明 1 证明证明H所有左陪集的并集为所有左陪集的并集为G 即 a G 有 由于H G且G对 封闭可得 下面证明 由可得 Ga GaH Ga GaH Ga GaH aeaaHeH GaGa GaaH 2 2 由定理由定理1 1可知 可知 G G中两个元素的左陪集要么相等要么不相交 中两个元素的左陪集要么相等要么不相交 由由 1 1 和和 2 2 可得 可得 H H的所有左陪集构成的所有左陪集构成G G的一个划分的一个划分 一 陪集一 陪集 例例2 群的子群 H1 H2 H1左陪集 0H1 0 2 4 1H1 1 3 5 2H1 2 4 0 3H1 3 5 1 4H1 4 0 2 5H1 5 1 3 H2左陪集 0H2 0 3 1H2 1 4 2H2 2 5 3H2 3 0 4H2 4 1 5H2 5 2 例例3 是的子群 其中H 0 2 则H的左陪集为 0 H 0 2 2 H 0 2 1 H 1 3 3 H 1 3 于是有 0 H 1 H 0 1 2 3 为N4的一个划分 二 拉格朗日定理二 拉格朗日定理 定理定理4 拉格朗日定理 设是有限群的子群 且 G n H m 那么m n 说明 说明 设H的不同左陪集有 k个 那么n G k H km 推论推论1 质数阶的群没有非平凡子群 说明 说明 和叫做群的平凡子群 推论推论2 在有限群中 任何元素的阶必是 G 的一个因子 说明 说明 如果a G的阶是r 则是的子群 推论推论3 一个质数阶的群必定是循环的 并且任一与么元不同的元 素都是生成元 二 拉格朗日定理二 拉格朗日定理 设G e a b c Klein四元群四元群满足下列条件 1 e的阶为1 a b c的阶均为2 2 a b c中任意两个元素运算的结果为第三个元素 推论推论4 任一四阶群 或为循环群C4 或为Klein四元群 证明 证明 设G e a b c 其中e是幺元 根据拉格朗日定理可知元素阶只 可能是1 2 4 1 若若G中有中有4阶元阶元a 则 a 4 e a a2 a3 C4 表示同构 2 若若G中无中无4阶元素阶元素 则G中除了幺元 剩余的3个元素阶均为2 即a2 b2 c2 e 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四元群 二 拉格朗日定理二 拉格朗日定理 四阶群仅有以下两个 四阶群仅有以下两个 五阶群仅有一个 五阶群仅有一个 循环群循环群Klein四元群四元群 e ea ab bc cd d eeabcd aabcde bbcdea ccdeab ddeabc e ea ab bc c eeabc aabce bbcea cceab e ea ab bc c eeabc aaecb bbcea ccbae 二 拉格朗日定理二 拉格朗日定理 例例3 令A 1 2 3 A上置换的全体S3 pi i 1 2 3 4 5 6 321 321 1 p 312 321 2 p 123 321 3 p 231 321 4 p 132 321 5 p 213 321 6 p 为三次对称群 此六阶群不是阿贝尔群 213 321 132 321 231 321 312 321 312 321 132 321 二 拉格朗日定理二 拉格朗日定理 定理定理5 设是群的子群 于是b aH 当且仅当a 1 b H 证明证明 b aH 当且仅当存在一h H 使b a h 即a 1 b h 因而 b aH当且仅当a 1 b H 设是群的子群 则H 所有不同的左陪集构成G的一个 划分 这个划分可以生成G的一个左陪集等价关系R aRb a 1 b H 验证验证R为等价关系为等价关系 自反性 对称性和传递性自反性 对称性和传递性 1 自反性自反性 a 1 a e H 所以aRa 2 对称性对称性 若aRb 则a 1 b H 所以b 1 a a 1 b 1 H 故bRa 3 传递性传递性 若aRb bRc 则a 1 b H b 1 c H a 1 c a 1 b b 1 c a 1 b b 1 c H 故aRc 二 拉格朗日定理二 拉格朗日定理 例例4 我们来考察 取H p1 p4 是的子群 左陪集 左陪集 p1H p4H p1 p4 p2H p6H p2 p6 p3H p5H p3 p5 可以看出 p1 p4 p2 p6 p3 p5 是S3的一个划分 右陪集 右陪集 Hp1 Hp4 p1 p4 Hp2 Hp5 p2 p5 Hp3 Hp6 p3 p6 可以看出 p1 p4 p2 p5 p3 p6 是S3的一个划分 213 321 132 321 231 321 123 321 312 321 321 321 654 321 ppp ppp p1p2p3p4p5p6 p1p1p2p3p4p5p6 p2p2p1p5p6p3p4 p3p3p6p1p5p4p2 p4p4p5p6p1p2p3 p5p5p4p2p3p6p1 p6p6p3p4p2p1p5 Attention 表示元素相同的左陪集和右 陪集未必相等 例如p2H Hp2 左右陪集 确定的等价关系也未必是的同余 关系 例如 p3 p5 p2 p6 p3 p2 p5 p6 二 拉格朗日定理二 拉格朗日定理 例例4 4 续续 取H p1 p5 p6 是的子群 左陪集 左陪集 p1H p5H p6H p1 p5 p6 p2H p3H p4H p2 p3 p4 可以看出 p1 p5 p6 p2 p3 p4 是S3的一个划分 右陪集 右陪集 Hp1 Hp5 Hp6 p1 p5 p6 Hp2 Hp3 Hp4 p2 p3 p4 可以看出 元素相同的左陪集和右陪集是相同的 H的左陪集等价关系也是一个同余关系 p1p2p3p4p5p6 p1p1p2p3p4p5p6 p2p2p1p5p6p3p4 p3p3p6p1p5p4p2 p4p4p5p6p1p2p3 p5p5p4p2p3p6p1 p6p6p3p4p2p1p5 从例4可以看出 H的左陪集等价关系可以是上的同余关系 也可 以不是 那么在什么情况下它一定是同余关系呢 引入正规子群和商 群 三 正规子群三 正规子群 设是群的子群 对任意元素a G 如果aH Ha 则称为正正 规子群规子群 定义中的aH Ha是指对每一h1 H 都存在h2 H 使a h1 h2 a 并 不要求对每一h H有a h h a 对正规子群来说 左陪集和右陪集相等 所以 可以简称陪集 显然 所有 阿贝尔群的子群都是正规子群 所有平凡子群都是正规子群 设aH和bH是两个陪集 a1是aH中任一元素 b1是bH中任一元