离散数学(第15章)陈瑜.ppt

陈瑜 Email chenyu inbox 离散数学 计算机学院 2020 3 26 计算机学院 2 224 第15章 半群与群15 1半群 2020 3 26 计算机学院 3 224 群是一种特殊的代数系统 是最重要的代数系统之一 群的理论广泛应用于数学 物理 化学以及很多人们不太熟悉的领域如社会学等 对计算机科学而言 群在自动化理论 形式语言 语法分析 编码理论等方面都有直接应用 并显示出其强大功能 上一章中已经给出了半群的定义 它要求运算是可结合的 许多常见的代数系统都是半群 甚至是含幺半群 下面是一些典型的半群例子 2020 3 26 计算机学院 4 224 群是一种特殊的代数系统 是最重要的代数系统之一 群的理论广泛应用于数学 物理 化学以及很多人们不太熟悉的领域如社会学等 对计算机科学而言 群在自动化理论 形式语言 语法分析 编码理论等方面都有直接应用 并显示出其强大功能 上一章中已经给出了半群的定义 它要求运算是可结合的 许多常见的代数系统都是半群 甚至是含幺半群 下面是一些典型的半群例子 2020 3 26 计算机学院 5 224 例 满足封闭 可结合 有幺元0的条件 因而是含幺半群 另外 它还满足可换性 每个元x R都有加法逆元 x 因此 也是一个可换群 满足封闭 可结合 有幺元1 因此是含幺半群 注意 因为0无乘法逆元 所以只能是含幺半群 2020 3 26 计算机学院 6 224 例设Mm n表示全休m行n列矩阵构成的集合 是矩阵加法 那么满足封闭 可结合的条件 元素全为0的m行n列矩阵是幺元 因此是含幺半群 此外 Mm n中每个矩阵Am n都有加法逆矩阵 Am n 因而还满足逆元条件 2020 3 26 计算机学院 7 224 例设F是由定义在非空集合S上的全体函数构成的集合 即F f S S 对于函数的复合运算 满足封闭性和可结合性 所以是半群 此外 定义在S上的恒等函数Is是的幺元 所以又是含幺半群 2020 3 26 计算机学院 8 224 例设 是非空有限字母表 是由定义在 上的全体有限长字母串构成的集合 或叫做 上全体字的集合 在 上定义运算为字的连接 则满足封闭和可结合的条件 并且空字是系统的幺元 所以是一个含幺半群 半群或含幺半群在计算机科学中有广泛的应用 尤其在从编译技术发展起来的形式语言与自动机理论领域 含幺半群是很重要的的内容之一 下面是半群的一个简单的应用例子 2020 3 26 计算机学院 9 224 例设一个简单的液晶显示电子表仅有显示时 分的两个功能 有0 1两个按键 按1键时由正常状态转入调分状态 此时按0键m次可以调增分数m 再按1键则转入调时状态 此时按0键n次 则时数增加n 最后再按1键回复到正常状态 这一调节过程如图 b 所示 a b 2020 3 26 计算机学院 10 224 上面的调分和调时过程可表示为 或由符号1和0组成的形如10m10n1的字符串集 即字母表 0 1 上的一个语言L 10m10n1 m n 0 这种字母串可以被电子表中的微处理器 可以看成是一个小小的计算机 识别并执行 其动作原理就是图15 1 1 b 所示的状态图 称为一个有限自动机 它反映了电子表依令而行的规则 语言L被相应地称为这个自动机所识别的语言 2020 3 26 计算机学院 11 224 幂 设是一个半群 由于 满足结合律 可定义幂运算 即对 x S 可定义 x x x x x x x x x x x x x xn xn 1 x x xn 1 x x x x 如果有单位元e 可以定义 x0 e幂运算有如下的公式 见下页 2020 3 26 计算机学院 12 224 定理15 1设是半群 a S m和n是正整数 则 am an am n am n amn 当是含幺半群时 上述结论对任意非负整数m和n都成立 证明 设m是一个固定的正整数 对n进行归纳 对于 当n 1时 由幂的定义可知结论成立 设结论对n k时成立 则am ak 1 am ak a 由幂的定义 am ak a 可结合性 am k a 归纳假设 am k 1 由归纳法可知 结论成立 2020 3 26 计算机学院 13 224 定理15 1设是半群 a S m和n是正整数 则 am an am n am n amn 当是含幺半群时 上述结论对任意非负整数m和n都成立 证明 设m是一个固定的正整数 对n进行归纳 对于 当n 1时 由幂的定义可知结论成立 设结论对n k时成立 则am ak 1 am ak a 由幂的定义 am ak a 可结合性 am k a 归纳假设 am k 1 由归纳法可知 结论成立 2020 3 26 计算机学院 14 224 定理15 1设是半群 a S m和n是正整数 则 am an am n am n amn 当是含幺半群时 上述结论对任意非负整数m和n都成立 证明 设m是一个固定的正整数 对n进行归纳 对于 当n 1时 由幂的定义可知结论成立 设结论对n k时成立 则am ak 1 am ak a 由幂的定义 am ak a 可结合性 am k a 归纳假设 am k 1 由归纳法可知 结论成立 对于 可以类似的进行归纳证明 2020 3 26 计算机学院 15 224 注意 当运算为加法 时 上述定理应写成 ma na m n an ma mn a 2020 3 26 计算机学院 16 224 定理15 2有限半群 S 必有幂等元 即存在a S a2 a 参见教材p183 注意此处的a2的正确含义 a a a2 不是数学中的乘法 2020 3 26 计算机学院 17 224 定理15 2有限半群 S 必有幂等元 即存在a S a2 a 证明 如果S中有幺元e 则e就是幂等元 如果S中没有幺元 任取b S 由集合S的有限性 必有 bi bj bj i bi j i 所以 对任何t i都有 bt bj i bt 注 t i l bt bi l bi b1 b2 j i bt 反复迭代 bk j i bt 此处k j i i 令t k j i 则得到bt bt bt即bt是幂等元 2020 3 26 计算机学院 18 224 定理15 2有限半群 S 必有幂等元 即存在a S a2 a 证明 如果S中有幺元e 则e就是幂等元 如果S中没有幺元 任取b S 由集合S的有限性 必有 bi bj bj i bi j i 所以 对任何t i都有 bt bj i bt 例如 t i l bt bi l bi b1 b2 j i bt 反复迭代 bk j i bt 此处k j i i 令t k j i 则得到bt bt bt即bt是幂等元 2020 3 26 计算机学院 19 224 定理15 2有限半群 S 必有幂等元 即存在a S a2 a 证明 如果S中有幺元e 则e就是幂等元 如果S中没有幺元 任取b S 由集合S的有限性 必有 bi bj bj i bi j i 所以 对任何t i都有 bt bj i bt 例如 t i l bt bi l bi b1 b2 j i bt 反复迭代 bk j i bt 此处k j i i 令t k j i 则得到bt bt bt即bt是幂等元 2020 3 26 计算机学院 20 224 定理15 2有限半群 S 必有幂等元 即存在a S a2 a 证明 如果S中有幺元e 则e就是幂等元 如果S中没有幺元 任取b S 由集合S的有限性 必有 bi bj bj i bi j i 所以 对任何t i都有 bt bj i bt 例如 t i l bt bi l bi b1 b2 j i bt 反复迭代 bk j i bt 此处k j i i 令t k j i 则得到bt bt bt即bt是幂等元 注意 若S不是有限集 则不一定有幂等元 例如 正整数集关于加法运算是一个半群 但是不存在幂等元 含幺半群至少含有一个幂等元 那就是幺元 一个半群甚至含幺半群也可以含有多个幂等元 不难验证是以S为幺元的含幺半群 由于集合交运算是幂等的 所以中每个元都是幂等元 2020 3 26 计算机学院 21 224 子半群 定义15 1如果是半群 T是S的非空子集 且T对运算 是封闭的 则称是半群的子半群 如果是含幺半群 T S e T 且T对运算 是封闭的 则称是含幺半群的子含幺半群 例 半群的子代数 都是的子半群 2020 3 26 计算机学院 22 224 子半群 定义15 1如果是半群 T是S的非空子集 且T对运算 是封闭的 则称是半群的子半群 如果是含幺半群 T S e T 且T对运算 是封闭的 则称是含幺半群的子含幺半群 例 半群的子代数 都是的子半群 2020 3 26 计算机学院 23 224 子半群 定义15 1如果是半群 T是S的非空子集 且T对运算 是封闭的 则称是半群的子半群 如果是含幺半群 T S e T 且T对运算 是封闭的 则称是含幺半群的子含幺半群 例 半群的子代数 都是的子半群 2020 3 26 计算机学院 24 224 例设是一个可换的含幺半群 M是它的所有的等幂元构成的集合 则是的一个子含幺半群 证明 1 显然 M S 2 是含幺半群 所以幺元e存在 又e e e 则e是一个等幂元 即有e M 所以M是非空的 3 e M 4 对任意a b M 有 a b a b a b a b a a b b a a b b a b 即运算 关于集合M是封闭的运算 由 1 2 3 4 知 是的一个子含幺半群 2020 3 26 计算机学院 25 224 例设是一个可换的含幺半群 M是它的所有的等幂元构成的集合 则是的一个子含幺半群 证明 1 显然 M S 2 是含幺半群 所以幺元e存在 又e e e 则e是一个等幂元 即有e M 所以M是非空的 3 e M 4 对任意a b M 有 a b a b a b a b a a b b a a b b a b 即运算 关于集合M是封闭的运算 由 1 2 3 4 知 是的一个子含幺半群 2020 3 26 计算机学院 26 224 例设是一个可换的含幺半群 M是它的所有的等幂元构成的集合 则是的一个子含幺半群 证明 1 显然 M S 2 是含幺半群 所以幺元e存在 又e e e 则e是一个等幂元 即有e M 所以M是非空的 3 e M 4 对任意a b M 有 a b a b a b a b a a b b a a b b a b 即运算 关于集合M是封闭的运算 由 1 2 3 4 知 是的一个子含幺半群 2020 3 26 计算机学院 27 224 例设是一个可换的含幺半群 M是它的所有的等幂元构成的集合 则是的一个子含幺半群 证明 1 显然 M S 2 是含幺半群 所以幺元e存在 又e e e 则e是一个等幂元 即有e M 所以M是非空的 3 e M 4 对任意a b M 有 a b a b a b a b a a b b a a b b a b 即运算 关于集合M是封闭的运算 由 1 2 3 4 知 是的一个子含幺半群 2020 3 26 计算机学院 28 224 例设是一个可换的含幺半群 M是它的所有的等幂元构成的集合 则是的一个子含幺半群 证明 1 显然 M S 2 是含幺半群 所以幺元e存在 又e e e 则e是一个等幂元 即有e M 所以M是非空的 3 e M 4 对任意a b M 有 a b a b a b a b a a b b a a b b a b 即运算 关于集合M是封闭的运算 由 1 2 3 4 知 是的一个子含幺半群 2020 3 26 计算机学院 29 224 习题 P1932 4 6 2020 3 26 计算机学院 30 224 15 2群和子群 2020 3 26 计算机学院 31 224 主要内容 一个非常重要的代数系统 群 主要从以下几个方面来介绍 群的概念和基本性质 群的子群和性质 群中元素的周期和性质 特殊群及其性质 如交换群 Abel群 循环群 陪集和拉格郎日定理 2020 3 26 计算机学院 32 224 在 14 2中已经为群下了定义 把群看成是在含幺半群的基础上加上每元有逆元的条件 其核心内容可用 闭 结 幺 逆 四个字予以概括 下面是一些典型的群的例子 2020 3 26 计算机学院 33 224 例 我们已经知道是含幺半群 由于每个整数a都有加法逆元 a 所以是群 一般叫做整数加群 同理 是实数加群 是有理数加群 对于数的乘法 是含幺半群而不是群 因为整数一般无Z中的乘法逆元 是实数乘群 它的幺元是1 每元的乘法逆元为1 a 2020 3 26 计算机学院 34 224 例 设Zk表示整数集Z上的模k剩余类集合 即 Zk 0 1 2 k 1 在Zk上定义运算和如下 那么 是群 这是因为封闭性和可结合性是明显成立的 0 是幺元 每元 i 的逆元是 k i 群习惯上又称为剩余类加群 2020 3 26 计算机学院 35 224 例设n个元素的集合A上的全体置换构成集合Sn 由第6章中关于置换的讨论 Sn中两个置换的复合仍然是A上的一个置换 因而运算是封闭的 其次 由于函数的复合是可结合的 因而置换的复合也是可结合的 在Sn中存在幺置换 1 使对任何Sn中的置换均有 因而 1 是幺元 把每个元素的x变成y的置换 其逆置换则把元素y变成x 因而每个置换都有逆 由此可知 构成群 这个群一般称为n次对称群 是一类重要的群 群尽管是用 闭 结 幺 逆 四个条件来定义的 但是它还可以用别的形式等价地定义 2020 3 26 计算机学院 36 224 例设n个元素的集合A上的全体置换构成集合Sn 由第6章中关于置换的讨论 Sn中两个置换的复合仍然是A上的一个置换 因而运算是封闭的 其次 由于函数的复合是可结合的 因而置换的复合也是可结合的 在Sn中存在幺置换 1 使对任何Sn中的置换均有 因而 1 是幺元 把每个元素的x变成y的置换 其逆置换则把元素y变成x 因而每个置换都有逆 由此可知 构成群 这个群一般称为n次对称群 是一类重要的群 群尽管是用 闭 结 幺 逆 四个条件来定义的 但是它还可以用别的形式等价地定义 2020 3 26 计算机学院 37 224 群 定理15 2 1如果是半群 并且对 a b G 都存在x y G使x a b a y b 则是群 群中元素的数目称为群的阶 证明 设a G 方程x a a的解为e1 对 t G 方程a y t有解y0 e1 t e1 a y0 e1 a y0 a y0 t即对 t G 必有e1 t t e1是G中的左幺元 同样可以证明G中有右幺元e2 所以G中有幺元e 同理 对 b G 方程x b e有解x0 这个x0是b的左逆元 方程b y e的解是b的右逆元 从而b有逆元 所以 是群 2020 3 26 计算机学院 38 224 群 定理15 3如果是半群 并且对 a b G 都存在x y G使x a b a y b 则是群 群中元素的数目称为群的阶 证明 设a G 方程x a a的解为e1 对 t G 方程a y t有解y0 e1 t e1 a y0 e1 a y0 a y0 t即对 t G 必有e1 t t e1是G中的左幺元 同样可以证明G中有右幺元e2 所以G中有幺元e 同理 对 b G 方程x b e有解x0 这个x0是b的左逆元 方程b y e的解是b的右逆元 从而b有逆元 所以 是群 2020 3 26 计算机学院 39 224 群 定理15 3如果是半群 并且对 a b G 都存在x y G使x a b a y b 则是群 群中元素的数目称为群的阶 证明 设a G 方程x a a的解为e1 对 t G 方程a y t有解y0 e1 t e1 a y0 e1 a y0 a y0 t即对 t G 必有e1 t t e1是G中的左幺元 同样可以证明G中有右幺元e2 所以G中有幺元e 同理 对 b G 方程x b e有解x0 这个x0是b的左逆元 方程b y e的解是b的右逆元 从而b有逆元 所以 是群 2020 3 26 计算机学院 40 224 群 定理15 3如果是半群 并且对 a b G 都存在x y G使x a b a y b 则是群 群中元素的数目称为群的阶 证明 设a G 方程x a a的解为e1 对 t G 方程a y t有解y0 e1 t e1 a y0 e1 a y0 a y0 t即对 t G 必有e1 t t e1是G中的左幺元 同样可以证明G中有右幺元e2 所以G中有幺元e 同理 对 b G 方程x b e有解x0 这个x0是b的左逆元 方程b y e的解是b的右逆元 从而b有逆元 所以 是群 2020 3 26 计算机学院 41 224 群 定理15 3如果是半群 并且对 a b G 都存在x y G使x a b a y b 则是群 群中元素的数目称为群的阶 证明 设a G 方程x a a的解为e1 对 t G 方程a y t有解y0 e1 t e1 a y0 e1 a y0 a y0 t即对 t G 必有e1 t t e1是G中的左幺元 同样可以证明G中有右幺元e2 所以G中有幺元e 同理 对 b G 方程x b e有解x0 这个x0是b的左逆元 方程b y e的解是b的右逆元 从而b有逆元 所以 是群 这个定理说明 在群的定义中幺元及逆元的条件可用方程有解来代替 另外 群定义中的幺元条件可以用存在左幺元 或右幺元 的条件代替 逆元的条件可以用左逆元 或右逆元 代替 2020 3 26 计算机学院 42 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 2020 3 26 计算机学院 43 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 证明 由于群G中每个元素都有逆元a 1 由a b a c a 1 a b a 1 a c 即b c 2020 3 26 计算机学院 44 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 2020 3 26 计算机学院 45 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 证明 反证法 假设a是群G中非幺元的幂等元 即a a a 且a e 因此a a a e 由 1 知a e 矛盾 2020 3 26 计算机学院 46 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 2020 3 26 计算机学院 47 224 定理15 4群G中每个元素都是可消去的 即运算满足消去律 即如果a b a c 则必有b c 群G中除幺元e外无其它幂等元 群G的运算表中任意一行 列 都没有两个相同的元素 重复元素 证明 反证法 假设群G的运算表中某一行 列 有两个相同的元素 设为a 并设它们所在的行表头元素为b 列表头元素分别为c1 c2 这时显然有c1 c2 而a bc1 bc2 由 1 得c1 c2 矛盾 2020 3 26 计算机学院 48 224 补充 例 构造一个3阶群 解 设e是幺元 G e a b 则可构造的3阶群如下 2020 3 26 计算机学院 49 224 定理15 5设是群 a G 构造映射 使得对任意x G 令 则对于函数的复合运算 是群 P185 定理的证明留与读者练习 这个定理说明 可以由一个已知的群来构造出一个新的群 2020 3 26 计算机学院 50 224 例 设X是任意集合 S f X X f是双射函数 即S是X上的所有双射函数的集合 运算 是函数的复合运算 证明是群 证明 1 封闭性 f g S f g是双射 则f g也是双射 因此f g S 故封闭性成立 2 结合律 由函数的运算 满足结合律 因此在S中也满足结合律 2020 3 26 计算机学院 51 224 例 设X是任意集合 S f X X f是双射函数 即S是X上的所有双射函数的集合 运算 是函数的复合运算 证明是群 证明 1 封闭性 f g S f g是双射 则f g也是双射 因此f g S 故封闭性成立 2 结合律 由函数的运算 满足结合律 因此在S中也满足结合律 2020 3 26 计算机学院 52 224 例 设X是任意集合 S f X X f是双射函数 即S是X上的所有双射函数的集合 运算 是函数的复合运算 证明是群 证明 1 封闭性 f g S f g是双射 则f g也是双射 因此f g S 故封闭性成立 2 结合律 由函数的运算 满足结合律 因此在S中也满足结合律 2020 3 26 计算机学院 53 224 例 设X是任意集合 S f X X f是双射函数 即S是X上的所有双射函数的集合 运算 是函数的复合运算 证明是群 证明 续 3 幺元 恒等映射IX S 且 f S 有 IX f f IX f 因此IX是的幺元 4 f g S是双射 则f的逆函数f 1存在 f 1也是双射 即f 1 S 且有 f 1 f f f 1 IX 因此 f的逆函数f 1就是f关于 的逆元 即S的任意元素都有逆元 综合 1 2 3 4 知是群 2020 3 26 计算机学院 54 224 例 设X是任意集合 S f X X f是双射函数 即S是X上的所有双射函数的集合 运算 是函数的复合运算 证明是群 证明 续 3 幺元 恒等映射IX S 且 f S 有 IX f f IX f 因此IX是的幺元 4 f g S是双射 则f的逆函数f 1存在 f 1也是双射 即f 1 S 且有 f 1 f f f 1 IX 因此 f的逆函数f 1就是f关于 的逆元 即S的任意元素都有逆元 综合 1 2 3 4 知是群 2020 3 26 计算机学院 55 224 课外练习 设A R 0 1 在A上定义6个映射如下 对于任意x A有 令G f1 f2 f3 f4 f5 f6 试证明G关于函数的复合运算 构成群 2020 3 26 计算机学院 56 224 子群 定义15 2设是一个群 S是G的一个非空子集 若S也是群 则称是的一个子群 一般来说 对任意的群 都有两个子群 我们称此两个子群为该群的平凡子群 而若有子群 且S e 和S G 则称为的真子群 另外 由群中的一个元素也可生成一个子群 定义为 a k ak 1 2020 3 26 计算机学院 57 224 子群 定义15 2设是一个群 S是G的一个非空子集 若S也是群 则称是的一个子群 一般来说 对任意的群 都有两个子群 我们称此两个子群为该群的平凡子群 而若有子群 且S e 和S G 则称为的真子群 另外 由群中的一个元素也可生成一个子群 为此 需要将群中元素的幂扩充到负指数的形式 即定义为 a k ak 1 2020 3 26 计算机学院 58 224 子群 定义15 2设是一个群 S是G的一个非空子集 若S也是群 则称是的一个子群 一般来说 对任意的群 都有两个子群 我们称此两个子群为该群的平凡子群 而若有子群 且S e 和S G 则称为的真子群 另外 由群中的一个元素也可生成一个子群 为此 需要将群中元素的幂扩充到负指数的形式 即定义为 a k ak 1 2020 3 26 计算机学院 59 224 定理15 6设是一个群 对任意的a G 令S an n Z Z是整数 则是的子群 证明 因为a S 所以显然S是G的非空子集 对任意的an am S 则an am an m 由n m Z 有n m Z 所以an m S 即运算是封闭的 由S是G的子集可得结合律也成立 由于e a0 S 所以S中有幺元 又 an S有逆元a n使an a n e 综上所述 是的子群 2020 3 26 计算机学院 60 224 定理15 6设是一个群 对任意的a G 令S an n Z Z是整数 则是的子群 证明 因为a S 所以显然S是G的非空子集 对任意的an am S 则an am an m 由n m Z 有n m Z 所以an m S 即运算是封闭的 由S是G的子集可得结合律也成立 由于e a0 S 所以S中有幺元 又 an S有逆元a n使an a n e 综上所述 是的子群 2020 3 26 计算机学院 61 224 定理15 6设是一个群 对任意的a G 令S an n Z Z是整数 则是的子群 证明 因为a S 所以显然S是G的非空子集 对任意的an am S 则an am an m 由n m Z 有n m Z 所以an m S 即运算是封闭的 由S是G的子集可得结合律也成立 由于e a0 S 所以S中有幺元 又 an S有逆元a n使an a n e 综上所述 是的子群 2020 3 26 计算机学院 62 224 定理15 6设是一个群 对任意的a G 令S an n Z Z是整数 则是的子群 证明 因为a S 所以显然S是G的非空子集 对任意的an am S 则an am an m 由n m Z 有n m Z 所以an m S 即运算是封闭的 由S是G的子集可得结合律也成立 由于e a0 S 所以S中有幺元 又 an S有逆元a n使an a n e 综上所述 是的子群 2020 3 26 计算机学院 63 224 定理15 2 4设是一个群 对任意的a G 令S an n Z Z是整数 则是的子群 证明 因为a S 所以显然S是G的非空子集 对任意的an am S 则an am an m 由n m Z 有n m Z 所以an m S 即运算是封闭的 由S是G的子集可得结合律也成立 由于e a0 S 所以S中有幺元 又 an S有逆元a n使an a n e 综上所述 是的子群 2020 3 26 计算机学院 64 224 特别把由群的一个元素a生成的子群记为 a 例如在中 由元素2生成的子群 2 是由全体偶数关于加法构成的群 而由元素1生成的子群正好是Z本身 2020 3 26 计算机学院 65 224 定理15 7设是一个群 是的子群 则 1 子群的幺元eS也是群的幺元eG 2 对 a S a在S中的逆元aS 1就是a在G中的逆元aG 1 证明 1 对 a S 由于eS是S的幺元 所以有 eS a a eS a 又S G 所以a G 由eG是G的幺元 所以有 eG a a eG a 由 有 eS a a eS a eG a a eG 由于G满足消去律 所以有 eS eG 2 对 a S 由于S G 所以a G 即a在S中的逆元就是a在G中的逆元 2020 3 26 计算机学院 66 224 定理15 7设是一个群 是的子群 则 1 子群的幺元eS也是群的幺元eG 2 对 a S a在S中的逆元aS 1就是a在G中的逆元aG 1 证明 1 对 a S 由于eS是S的幺元 所以有 eS a a eS a 又S G 所以a G 由eG是G的幺元 所以有 eG a a eG a 由 有 eS a a eS a eG a a eG 由于G满足消去律 所以有 eS eG 2 对 a S 由于S G 所以a G 即a在S中的逆元就是a在G中的逆元 2020 3 26 计算机学院 67 224 定理15 7设是一个群 是的子群 则 1 子群的幺元eS也是群的幺元eG 2 对 a S a在S中的逆元aS 1就是a在G中的逆元aG 1 证明 1 对 a S 由于eS是S的幺元 所以有 eS a a eS a 又S G 所以a G 由eG是G的幺元 所以有 eG a a eG a 由 有 eS a a eS a eG a a eG 由于G满足消去律 所以有 eS eG 2 对 a S 由于S G 所以a G 即a在S中的逆元就是a在G中的逆元 2020 3 26 计算机学院 68 224 定理15 7设是一个群 是的子群 则 1 子群的幺元eS也是群的幺元eG 2 对 a S a在S中的逆元aS 1就是a在G中的逆元aG 1 证明 1 对 a S 由于eS是S的幺元 所以有 eS a a eS a 又S G 所以a G 由eG是G的幺元 所以有 eG a a eG a 由 有 eS a a eS a eG a a eG 由于G满足消去律 所以有 eS eG 2 对 a S 由于S G 所以a G 即a在S中的逆元就是a在G中的逆元 2020 3 26 计算机学院 69 224 定理15 7设是一个群 是的子群 则 1 子群的幺元eS也是群的幺元eG 2 对 a S a在S中的逆元aS 1就是a在G中的逆元aG 1 证明 1 对 a S 由于eS是S的幺元 所以有 eS a a eS a 又S G 所以a G 由eG是G的幺元 所以有 eG a a eG a 由 有 eS a a eS a eG a a eG 由于G满足消去律 所以有 eS eG 2 对 a S 由于S G 所以a G 即a在S中的逆元就是a在G中的逆元 2020 3 26 计算机学院 70 224 定理15 8设是一个群 S是G的一个非空子集 则是的子群的充要条件是 对 a b S 有a b 1 S 证明 设S是G的子群 对 a S 由群的定义知 b 1 S 即有a b 1 S 所以必要性成立 由子群的定义知 需证明如下四点 1 S是非空的子集 2020 3 26 计算机学院 71 224 定理15 8设是一个群 S是G的一个非空子集 则是的子群的充要条件是 对 a b S 有a b 1 S 证明 设S是G的子群 对 a S 由群的定义知 b 1 S 即有a b 1 S 所以必要性成立 由子群的定义知 需证明如下四点 1 S是非空的子集 2020 3 26 计算机学院 72 224 定理15 8设是一个群 S是G的一个非空子集 则是的子群的充要条件是 对 a b S 有a b 1 S 证明 设S是G的子群 对 a S 由群的定义知 b 1 S 即有a b 1 S 所以必要性成立 由子群的定义知 需证明如下四点 1 S是非空的子集 2020 3 26 计算机学院 73 224 2 幺元存在 由于S 所以有a S 由对 a b S 有a b S 取a b 有eG a a S 3 逆元存在 对 a b S 有a b 1 S 对 b S 由eG S 有b eG b S 4 封闭性 对 a b S 由3 知 b S 由条件知 a b S 即a b S 由1 2 3 4 知 是的子群 2020 3 26 计算机学院 74 224 2 幺元存在 由于S 所以有a S 由对 a b S 有a b S 取a b 有eG a a S 3 逆元存在 对 a b S 有a b 1 S 对 b S 由eG S 有b eG b S 4 封闭性 对 a b S 由3 知 b S 由条件知 a b S 即a b S 由1 2 3 4 知 是的子群 2020 3 26 计算机学院 75 224 2 幺元存在 由于S 所以有a S 由对 a b S 有a b S 取a b 有eG a a S 3 逆元存在 对 a b S 有a b 1 S 对 b S 由eG S 有b eG b S 4 封闭性 对 a b S 由3 知 b S 由条件知 a b S 即a b S 由1 2 3 4 知 是的子群 2020 3 26 计算机学院 76 224 例 设是一个群 令 C a a G且对 x G 有 a x x a 证明是的一个子群 证明 1 非空性 对 x G 由于幺元e G存在 所以有 e x x e x 即e C 所以C是非空的 2 封闭性 对 a b C 则有 对 x Ga x x a b x x b a b x a b x a x b a x b x a b x a b 即 a b C 2020 3 26 计算机学院 77 224 例 设是一个群 令 C a a G且对 x G 有 a x x a 证明是的一个子群 证明 1 非空性 对 x G 由于幺元e G存在 所以有 e x x e x 即e C 所以C是非空的 2 封闭性 对 a b C 则有 对 x Ga x x a b x x b a b x a b x a x b a x b x a b x a b 即 a b C 2020 3 26 计算机学院 78 224 例 设是一个群 令 C a a G且对 x G 有 a x x a 证明是的一个子群 证明 1 非空性 对 x G 由于幺元e G存在 所以有 e x x e x 即e C 所以C是非空的 2 封闭性 对 a b C 则有 对 x Ga x x a b x x b a b x a b x a x b a x b x a b x a b 即 a b C 2020 3 26 计算机学院 79 224 3 逆元存在 对 a C 有 对 x G a x x a C G a G 即有 a 1 G 有 a 1 a x a 1 a 1 x a a 1 即有 x a 1 a 1 x 所以a 1 C 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 80 224 3 逆元存在 对 a C 有 对 x G a x x a C G a G 即有 a 1 G 有 a 1 a x a 1 a 1 x a a 1 即有 x a 1 a 1 x 所以a 1 C 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 81 224 3 逆元存在 对 a C 有 对 x G a x x a C G a G 即有 a 1 G 有 a 1 a x a 1 a 1 x a a 1 即有 x a 1 a 1 x 所以a 1 C 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 82 224 例 设是一个整数加群 令 H nk k Z且n是一个取定的自然数 证明是的一个子群 证明 1 非空性 显然 2 封闭性 对 a b H 有a nk1 b nk2 k1 k2 Z a b nk1 nk2 n k1 k2 H k1 k2 Z 3 逆元存在 对 a H 有a nk1 k1 Z 则a a nk1 n k1 H k1 Z 由1 2 3 知是的一个子群 2020 3 26 计算机学院 83 224 例 设是一个整数加群 令 H nk k Z且n是一个取定的自然数 证明是的一个子群 证明 1 非空性 显然 2 封闭性 对 a b H 有a nk1 b nk2 k1 k2 Z a b nk1 nk2 n k1 k2 H k1 k2 Z 3 逆元存在 对 a H 有a nk1 k1 Z 则a a nk1 n k1 H k1 Z 由1 2 3 知是的一个子群 2020 3 26 计算机学院 84 224 例 设是一个整数加群 令 H nk k Z且n是一个取定的自然数 证明是的一个子群 证明 1 非空性 显然 2 封闭性 对 a b H 有a nk1 b nk2 k1 k2 Z a b nk1 nk2 n k1 k2 H k1 k2 Z 3 逆元存在 对 a H 有a nk1 k1 Z 则a a nk1 n k1 H k1 Z 由1 2 3 知是的一个子群 2020 3 26 计算机学院 85 224 例 设是一个群 H1 H2是G的两个子群 证明H H1 H2是G的子群 证明1 非空性 由于H1 H2是G的两个子群 所以有 e H1 e H2 即有e H1 H2 2 封闭性 对 a b H 有a b H1 H2 即a b H1 a b H2 由于H1 H2都是G的子群 所以有 a b H1 a b H2 即有 a b H1 H23 逆元存在 对 a H 有a H1 H2 即a H1 a H2 由于H1 H2都是G的子群 所以有 a 1 H1 a 1 H2 即有 a 1 H1 H2 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 86 224 例 设是一个群 H1 H2是G的两个子群 证明H H1 H2是G的子群 证明1 非空性 由于H1 H2是G的两个子群 所以有 e H1 e H2 即有e H1 H2 2 封闭性 对 a b H 有a b H1 H2 即a b H1 a b H2 由于H1 H2都是G的子群 所以有 a b H1 a b H2 即有 a b H1 H23 逆元存在 对 a H 有a H1 H2 即a H1 a H2 由于H1 H2都是G的子群 所以有 a 1 H1 a 1 H2 即有 a 1 H1 H2 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 87 224 例 设是一个群 H1 H2是G的两个子群 证明H H1 H2是G的子群 证明1 非空性 由于H1 H2是G的两个子群 所以有 e H1 e H2 即有e H1 H2 2 封闭性 对 a b H 有a b H1 H2 即a b H1 a b H2 由于H1 H2都是G的子群 所以有 a b H1 a b H2 即有 a b H1 H23 逆元存在 对 a H 有a H1 H2 即a H1 a H2 由于H1 H2都是G的子群 所以有 a 1 H1 a 1 H2 即有 a 1 H1 H2 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 88 224 例 设是一个群 H1 H2是G的两个子群 证明H H1 H2是G的子群 证明1 非空性 由于H1 H2是G的两个子群 所以有 e H1 e H2 即有e H1 H2 2 封闭性 对 a b H 有a b H1 H2 即a b H1 a b H2 由于H1 H2都是G的子群 所以有 a b H1 a b H2 即有 a b H1 H23 逆元存在 对 a H 有a H1 H2 即a H1 a H2 由于H1 H2都是G的子群 所以有 a 1 H1 a 1 H2 即有 a 1 H1 H2 由1 2 3 知 是的一个子群 2020 3 26 计算机学院 89 224 推广 设是一个群 H1 H2 Hn是G的n个子群 则有H H1 H2 Hn是G的子群 2020 3 26 计算机学院 90 224 复习 若整数m和n关于模d的余数相同 称m和n 关于模d 是同余的 记为 n m mod d同余是整数之间的一种重要关系 模d同余的数的全体构成的集合称为一个同余类 这个集合可以表示成 n d x n x mod d n m kdk为整数 2020 3 26 计算机学院 91 224 复习 Zk表示整数集Z上的模k剩余类集合 即Zk 0 1 2 k 1 例 n 6 则 Zn 0 1 2 3 4 5 0 12 6 0 6 12 18 1 11 5 1 7 13 19 2 10 4 2 8 14 20 2020 3 26 计算机学院 92 224 例 设Zk表示整数集Z上的模k剩余类集合 即Zk 0 1 2 k 1 在Zk上定义运算 和 如下 i j t i j t modk i j t ij t modk 是群 剩余类加群 0 是 的幺元 每元 i 的 逆元是 k i 不是群 因为虽然它满足封闭性和可结合性 且 1 是它的幺元 但是 0 无 逆元 所以它仅仅是一个含幺半群 2020 3 26 计算机学院 93 224 例 设Zk表示整数集Z上的模k剩余类集合 即Zk 0 1 2 k 1 在Zk上定义运算 和 如下 i j t i j t modk i j t ij t modk 是群 剩余类加群 0 是 的幺元 每元 i 的 逆元是 k i 不是群 因为虽然它满足封闭性和可结合性 且 1 是它的幺元 但是 0 无 逆元 所以它仅仅是一个含幺半群 2020 3 26 计算机学院 94 224 例 设Zk表示整数集Z上的模k剩余类集合 即Zk 0 1 2 k 1 在Zk上定义运算 和 如下 i j t i j t modk i j t ij t modk 是群 剩余类加群 0 是 的幺元 每元 i 的 逆元是 k i 不是群 因为虽然它满足封闭性和可结合性 且 1 是它的幺元 但是 0 无 逆元 所以它仅仅是一个含幺半群 2020 3 26 计算机学院 95 224 是不是群呢 不一定 Z4 0 1 2 3 而 2 2 0 Z4 0 不是群 而Z5 0 1 2 3 4 其运算表如右图 运算是封闭的 可结合的 1 是幺元 1 4 的逆元是自身 2 3 互为逆元 因此是群 2020 3 26 计算机学院 96 224 是不是群呢 不一定 Z4 0 1 2 3 而 2 2 0 Z4 0 不是群 而Z5 0 1 2 3 4 其运算表如右图 运算是封闭的 可结合的 1 是幺元 1 4 的逆元是自身 2 3 互为逆元 因此是群 2020 3 26 计算机学院 97 224 是不是群呢 不一定 Z4 0 1 2 3 而 2 2 0 Z4 0 不是群 而Z5 0 1 2 3 4 其运算表如右图 运算是封闭的 可结合的 1 是幺元 1 4 的逆元是自身 2 3 互为逆元 因此是群 2020 3 26 计算机学院 98 224 例 设n个元素的集合A上的全体置换构成集合Sn 证明构成群 n次对称群 证明 1 Sn中两个置换的复合仍然是A上的一个置换 所以运算是封闭的 2 由于函数的复合是可结合的 所以置换的复合也是可结合的 3 Sn中存在幺置换 单位置换 1 使对 Sn 所以 1 是幺元 4 每个置换将x变成y 而逆置换是将y变成x 所以 每个置换都有逆 2020 3 26 计算机学院 99 224 例 设n个元素的集合A上的全体置换构成集合Sn 证明构成群 n次对称群 证明 1 Sn中两个置换的复合仍然是A上的一个置换 所以运算是封闭的 2 由于函数的复合是可结合的 所以置换的复合也是可结合的 3 Sn中存在幺置换 单位置换 1 使对 Sn 所以 1 是幺元 4 每个置换将x变成y 而逆置换是将y变成x 所以 每个置换都有逆 2020 3 26 计算机学院 100 224 例 设n个元素的集合A上的全体置换构成集合Sn 证明构成群 n次对称群 证明 1 Sn中两个置换的复合仍然是A上的一个置换 所以运算是封闭的 2 由于函数的复合是可结合的 所以置换的复合也是可结合的 3 Sn中存在幺置换 单位置换 1 使对 Sn 所以 1 是幺元 4 每个置换将x变成y 而逆置换是将y变成x 所以 每个置换都有逆 2020 3 26 计算机学院 101 224 例 设n个元素的集合A上的全体置换构成集合Sn 证明构成群 n次对称群 证明 1 Sn中两个置换的复合仍然是A上的一个置换 所以运算是封闭的 2 由于函数的复合是可结合的 所以置换的复合也是可结合的 3 Sn中存在幺置换 单位置换 1 使对