离散数学 代数系统.ppt

代数结构 代数系统 本章将研究一类特殊的数学结构 由集合上定义若干个运算而组成的系统 代数系统 代数结构 系统 的概念 一 n元运算例子 取相反数运算 集合的补运算 以及N上的 II 1 定义 设X是个集合 f Xn X是个映射 则称f是X上的n元运算 f X X是个一元运算 f X2 X是个二元运算 思考题 下面说法是否正确 减法 是N上的二元运算 除法 是整数I上的二元运算 除法 是实数R上的二元运算 主要讨论二元运算 通常用 等表示抽象的二元运算 如果用 表示二元运算f时 通常将f z写成x y z 2 二元运算的运算表可用一个表来表示二元运算的运算规律 例如令E a b P E 上的 运算表如图所示 如令X S R A L 其中S表示开始时的位置 R表示 向右转 A表示 向后转 L表示 向左转 表示转动的复合运算 其运算表如图所示 二 代数系统的概念 1 代数系统的定义 X是非空集合 f1 f2 fm分别是X上k1 k2 km元运算 ki为整数 称集合X和运算f1 f2 fm所构成的系统为一个代数系统U 或一个代数结构 简称一个代数 记作U m 1 2 有限代数系统 U 是个代数系统 如果X是个有限集合 则称U是个有限代数系统 3 同类型代数系统 给定两个代数系统U V 如对应的运算fi和gi的元数相同 i 1 2 3 m 则称U与V是同类型代数系统 一 交换性 定义 设 是X上的二元运算 如果对任何x y X 有x y y x 则称 是可交换的 例 对任意的a b N 定义a b ab则 不满足交换性 例 设Q为有理数集合 是Q上的二元运算 对任意的a b Q 定义a b a b ab问 是否可交换 从运算表看交换性 是个以主对角线为对称的表 二 等幂元 等幂性 定义 设 是X上的二元运算 如果存在a X 使得a a a 则称a是等幂元 如果对任何x X 都有x x x 则称 有等幂性 例 N上定义的加法 是否具有等幂性 从运算表看等幂元 等幂性 看主对角线的元素与上表头 或左表头 元素相同 三 单位元 幺元 恒等元 定义 设 是X上的二元运算 如果存在eL X 使得对任何x X 有eL x x 则称eL是相对 的左单位元 如果存在eR X 使得对任何x X 有x eR x 则称eR是相对 的右单位元 如果eL eR e 对任何x X 有e x x e x 称e是相对 的单位元 例 单位元是 单位元是 单位元是 单位元是 单位元是 单位元是 例 A a b c d 在A上定义两个运算如下所示 试指出左 右单位元 A中关于 的左单位元为 A中关于 的右单位元为 A中关于 的左单位元为 A中关于 的右单位元为 从运算表找左单位元eL eL所在行的各元素均与上表头元素相同 从运算表找右单位元eR eR所在列的各元素均与左表头元素相同 定理1 设 是X上的二元运算 如果有左单位元eL X 也有右单位元eR X 则eL eR e 且单位元e是唯一的 证明 因为eL是左单位元 又eR X 所以eL eR eR因为eR是右单位元 又eL X 所以eL eR eL于是eL eR e 假设有两个单位元e1 e2 因为e1是单位元 又e2 X 所以e1 e2 e2因为e2是单位元 又e1 X 所以e1 e2 e1则e1 e2 e 所以单位元是唯一的 思考题 减法运算是否有单位元 四 零元 定义 设 是X上的二元运算 如果有 L X 使得对任何x X 有 L x L 则称 L是相对 的左零元 如果有 R X 使得对任何x X 有x R R 则称 R是相对 的右零元 如果 L R 对任何x X 有 x x 称 是相对 的零元 例如 对乘法 零元 对加法 零元 对并运算 零元是 对交运算 零元是 从运算表找左零元 L L所在行的各元素均与左表头元素相同 从运算表找右零元 R R所在列的各元素均与上表头元素相同 定理2 设 是X上的二元运算 如果有左零元 L X 也有右零元 R X 则 L R 且零元 是唯一的 定理3 是代数系统 且集合A中元素个数大于1 如果该代数系统中存在单位元e和零元 则 e 证明 假设 e 则 对任意x A 有x e x x e即A中所有元素都相同 所以 A 1 矛盾 五 可结合性 定义 设 是X上的二元运算 如果对任何x y z X 有 x y z x y z 则称 是可结合的 是可结合的运算的 相同元素x的 运算 通常可以写成乘幂的形式 如下 x x x2x2 x x x2 x3思考题 对于加法 13 对于乘法 13 例设A是非空集合 对任意的a b A 定义a b b 证明 是可结合的 例 对任意的a b c N 定义a b ab 问 是否可结合 定理 设A是非空集合 是A上的二元运算且满足结合律 则对任意的正整数m和n 有xm xn xm n xm n xmn 六 逆元 定义 设 是X上有单位元e的二元运算 x X 如果有xL 1 X 使得 xL 1 x e 则称xL 1是x相对 的左逆元 如果有xR 1 X 使得x xR 1 e 则称xR 1是x相对 的右逆元 如果xL 1 xR 1 x 1 有x 1 x x x 1 e 称x 1是x相对 的逆元 并称x可逆 也称x 1与x互为逆元 例实数集合R上的 和 x R对加 x 1 对乘 x 1 设S a b c d e 定义S上的一个二元运算 如下 试指出中各元素的左 右逆元 单位元为 a的左 右逆元 逆元为 b的左逆元为 b的右逆元为 b的逆元为 c的左逆元为 c的右逆元为 c的逆元为 d的左逆元为 d的右逆元为 d的逆元 e的左逆元为 e的右逆元为 e的逆元为 abcde 从运算表找x的左逆元xL 1 在x列向下找到单位元e后 再向左到左表头元素即是xL 1 从运算表找x的右逆元xR 1 在x行向右找到e后 再向上到上表头元素即是xR 1 定理3 设 是X上有单位元e且可结合的二元运算 如果x X x的左 右逆元都存在 则x的左 右逆元必相等 且x的逆元是唯一的 证明 设xL 1 xR 1分别是x的左 右逆元 于是有xL 1 x x xR 1 exR 1 e xR 1 xL 1 x xR 1 xL 1 x xR 1 xL 1 e xL 1假设x有两个逆元x1 x2 所以x1 x e x x2x2 e x2 x1 x x2 x1 x x2 x1 e x1所以x的逆元是唯一的 定理4 设 是X上有单位元e且可结合的二元运算 如果 x X 都存在左逆元 则x的左逆元也是它的右逆元 证明 任取a X b X b a e c X c b e 于是有a b e a b c b a b c b a b c e b c b e所以b也是a的右逆元 七 可消去性 定义 设 是X上的二元运算 a X 如果对任何x y X 有 a x a y x a y a x y 则称a相对 是可消去的 定理5 可消去性的判定定理 设 是X上可结合的二元运算 如a X 且a 1 X 则a是可消去的 证明 如a X 且a 1 X 任取x y X 设有a x a y则a 1 a x a 1 a y a 1 a x a 1 a y所以e x e yx y a相对 是可消去的 如果有x a y a类似可得x y 八 分配律 定义 设 和 都是X上的二元运算 若对任何x y z X 有x y z x y x z 或 x y z x z y z 则称 对 可分配 设A a b 在A上定义两个二元运算 和 如下表所示 运算 对于 运算可分配吗 运算 对于运算 呢 ab abaabaaabbabab解 运算 对运算 是可分配的 a a a a a a a a a a a a b a b a a a a b a b b a a a a b a b b b b b a a b b b b b a b b b b b a b b b a a b a a b a b a 这两个运算都满足交换律 所以运算 对运算 是可分配的 但运算 对运算 不可分配 九 吸收律 定义 设 和 都是X上的二元运算 若对任何x y X 有x x y x和x x y x则 与 满足吸收律 例 在自然数N上定义两个二元运算 和 对任意的x y有x y max x y x y min x y 问运算 和 是否满足吸收律 和是代数系统 是二元运算 1 可交换性 x y X 有x y y x 2 等幂性 x X 有x x x 3 有单位元 e X x X 有e x x e x 4 有零元 x x X 有 x x 5 可结合性 x y z X 有 x y z x y z 6 有逆元 x X 有x 1 X 使得x 1 x x x 1 e7 可消去性 a X x y X 有 a x a y x a y a x y 8 分配律 对 可分配 x y z X 有x y z x y x z 或 x y z x z y z 9 吸收律 x y X 有x x y x和x x y x 从运算表找运算的性质 设是代数系统 则运算 具有封闭性 当且仅当运算表中的每个元素都属于A 运算 具有交换性 当且仅当运算表关于主对角线是对称的 运算 具有等幂性 当且仅当运算表的主对角线上的每一元素与它所在行 列 的表头元素相同 A关于 有零元 当且仅当该元素所对应的行和列中的元素都与该元素相同 A中关于 有单位元 当且仅当该元素所对应的行和列依次与运算表的行和列相一致 设A中有单位元 a和b互逆 当且仅当位于a所在的行 b所在的列的元素以及位于b所在的行 a所在的列的元素都是单位元 例 对于实数集合R 下表所列的二元运算是否具有左边一列中的那些性质 请在相应的位置上填写 是 或 否 问 上述四个运算是否具有交换性和等幂性 其等幂元 单位元 零元 可逆元素是否存在 半群和独异点 幺群 一 半群 Semi group 1 定义 S是个非空集合 是S上的二元运算 如果 在S上满足结合律 则称是半群 例设A a b c d 在A上定义两个二元运算如下 问和是否是半群 例2 任何一种语言都有个基本符号表 称之为字母表 令V是计算机机器语言的字母表 V 0 1 计算机的任何一条指令 都是个由0和1组成的符号串 由0和1组成的所有符号串的集合是V 其中V V V2 V3 Vn 在V 上定义符号串的联结运算 为 0101 001 0101001显然运算 是可结合的 所以是个半群 2 交换半群是半群 如 是可交换的 则称它是交换半群 3 子半群是个半群 B S 如果 在B上封闭 则称是的子半群 定理 设是半群 如果S是有限集合 则必存在a S 使得a a a 证明 因是有限半群 在S上封闭 所以任何b S 对任何i 1有bi S 因S是有限集合 所以必存在正整数i j i j 使得bi bj 令p j i 显然p 1 j p i 于是bi bj bp i bp bi所以对任意在q i 设q i s 有bq bi s bi bs bp bi bs bp bi s bp bq因p 1 总可以找到整数k 1 使得kp i 于是有bkp bp bkp bp bp bkp bp bp bkp b2p bkp b2p bp bkp b3p bkp bkp bkp令bkp a 于是有a a a 二 独异点 幺群 Monoid 1 独异点定义 设是个半群 如果对 有单位元 则称是个独异点 也称它是幺群 2 交换幺群 是独异点 如 是可交换的 则称它是交换幺群 3 子幺群 是个幺群 B M 如果 在B上封闭 且单位元e B 则称是的子幺群 定理 设是独异点 且S有限 则在关于 的运算表中 任何两行或两列都不相同 证明 对任意的a b S a b a e a b b e 说明两行不同 e a a b e b 说明两列不同 群Group 一 概念1 群的定义 设是个代数系统 如果 满足可结合 有单位元且每个元素可逆 则称它是个群 2 有限群 令是群 G是有限集 则称它是有限群 二 群的性质 1 群满足可消去性定理1设是个群 则对任何a b c G 如果有 a b a c则b c b a c a则b c 证明 任取a b c G 设有a b a c因是个群 所以a 1 G 于是有a 1 a b a 1 a c a 1 a b a 1 a ce b e c所以b c 2 群方程可解性定理2设是个群 则对任何a b G 存在唯一元素x G 使得a x b 存在唯一元素y G 使得y a b 证明 先证明 式有解因是个群 对任何a b G 有a 1 G a 1 b G 用a 1 b代入 中的x得 a x a a 1 b a a 1 b e b b所以x a 1 b是方程 的解 再证明 式的解的唯一性设 式有两个解x1 x2 G 于是有a x1 ba x2 b所以a x1 a x2 由可消去性得x1 x2 3 群中无零元 定理3设是个群 如果cardG 2 则G中无零元 证明 如果G中有零元 则对任何x G 有 x 由于cardG 2 e所以不会有y G 使得 y e 即 不可逆 所以G中无零元 4 群中除单位元外 无其它等幂元 定理4设是个群 G中除单位元外 无其它等幂元 证明 假设有a G是等幂元 即a a a又a 1 G 于是有a 1 a a a 1 a a 1 a a ee a e所以a e 5 定理5是个群 对任何a b G 有 a 1 1 a a b 1 b 1 a 1证明 结论显然成立 a b b 1 a 1 a b b 1 a 1 a e a 1 a a 1 e b 1 a 1 a b b 1 a 1 a b b 1 e b b 1 b e所以b 1 a 1是a b的逆元 即 a b 1 b 1 a 1推论 是个群 对任何a G 有 an 1 a a a 1 a 1 a 1 a 1 a 1 n a n所以 an 1 a 1 n a n此外 因为群G中任何x G 有e x x 1 x1 1 x0 x0 e 6 有限群的运算表的特征定理6是个有限群 则G中每个元素在 运算表中的每一行 列 必出现且仅出现一次 证明 令G a1 a2 a3 an 的运算表如图 任取aj G 由群方程可解性得存在唯一元素ak G 使得ai ak aj这说明aj在ai行出现假设aj在ai行出现两次 设在第t列也出现 则有ai ak aj和ai at aj所以ai ak ai at由可消去性得at ak同理可证G中每个元素在每列必出现且仅出现一次 四 子群 一 子群定义 设 G 是群 S是G的非空子集 如果 S 满足 任何a b S有ab S 封闭 单位元e S 有单位元 任何a S有a 1 S 可逆 则称 S 是 G 的子群 记S G 二 平凡子群与真子群设 G 是群 e 和 G 也是 G 的子群 称之为平凡子群 其余真子集构成的子群称之为真子群 记S G 证明子群的方法方法1 用子群的定义 方法2 定理设 G 是群 S是G的非空子集 如果 S 满足 任何a b S有ab S 封闭 任何a S有a 1 S 可逆 则 S 是 G 的子群 证明 任取a S由可逆得a 1 S 又由封闭得aa 1 S所以单位元e S 所以 S 是 G 的子群 方法3 定理设 G 是群 B是G的有限子集 如果 在B上满足封闭性 则 B 是 G 的子群 证明 先证单位元e B 任取b B 因为 在B上封闭 所以对任意i 1有bi B 由于B中元素个数有限 所以必存在正整数i j i1 有bj i 1 B 使得bbj i 1 bj i 1b bj i e所以b 1 bj i 1b 如果j i 1则bj i b e所以b 1 b所以 B 是 G 的子群 方法4 设 G 是群 S是G的非空子集 如果任何a b S有ab 1 S 则 S 是 G 的子群 证明 先证e S任取a S由已知得aa 1 S 即e S 再证可逆性任取a S由 得e S 由已知得ea 1 S 即a 1 S 最后证明封闭性任取a b S由 得b 1 S 由已知得a b 1 1 S 即得ab S所以 S 是 G 的子群 例 已知 H1 和 H2 是群 G 的子群 求证 H1 H2 是 H1 H2 和 G 的子群 证明 因为 H1 和 H2 是群 G 的子群 所以幺元e H1 H2 H1 H2 任取a b H1 H2 推出ab 1 H1 H2 则a b H1a b H2 因为 H1 和 H2 是群 G 的子群 所以b 1 H1 b 1 H2 ab 1 H1 ab 1 H2 ab 1 H1 H2因H1 H2 H1 H1 H2 H2 H1 H2 G 所以 H1 H2 是 H1 H2 和 G 的子群 例 设G是群 a G 令H y y a a y y G 求证 H G 证明 方法1 用子群定义 a 任取y1 y2 H 有y1a ay1y2a ay2 而 y1y2 a y1 y2a y1 ay2 y1a y2 ay1 y2 a y1y2 y1 y2 H 满足封闭性 b 因ea ae e H c 任取y H 有ya ay 由于y 1 G 所以y 1a y 1ae y 1a yy 1 y 1 ay y 1 y 1 ya y 1 y 1y ay 1 eay 1 ay 1 y 1 H H G 例 设G是群 a G 令H y y a a y y G 求证 H G 方法4 因为ae ea 所以e H 即H 任取y1 y2 H 有y1a ay1y2a ay2 因为G是群 所以y2 1 G 因此 y1y2 1 a y1y2 1 ae y1y2 1a y2y2 1 y1y2 1 ay2 y2 1 y1y2 1 y2a y2 1 y1 y2 1y2 ay2 1 y1eay2 1 y1a y2 1 ay1 y2 1 a y1y2 1 y1y2 1 H H G 五 群的阶与群中元素的阶 1 群的阶 G 是群 如果cardG n 则称 G 是n阶群 如果cardG是无限的 则称 G 是无限阶群 1 2 3阶群运算表的结构 群 e e a e a b 根据有限群运算表的特征 得它们的运算表分别是 从运算表可以看出 所有的一阶群都同构 所有的二阶群都同构 所有的三阶群都同构 2 群中元素的阶定义 设 G 是个群 a G 使得an e的最小的正整数n 称为a的阶或周期 记O a n 若没有这样的正整数存在 则称a的阶是无限的 并记O a 思考题 如果Rk S 则k是个怎样的数 定理 G 是群 a G 如果O a n 则ak e当且仅当k mn m I 证明 充分性 已知k mn m I ak amn an m em e 必要性 已知ak e 因为O a n 即an e 假设k不是n的整数倍 令k mn tm t I 0 t nt k mnat ak mn ak a mn e an m e m e由于at e 而t n 与a的阶为n矛盾 所以k是n的整数倍 即k mn m I 思考题 上例中R4 S L4 SR和L的阶都为4 而R 1 L由此可以得到什么结论 定理 群中的元素与其逆元具有相同的阶 即O a O a 1 证明 设 G 是群 任取a G 如果a的阶是有限的 设阶为n an e 则 a 1 n a n an 1 e 1 e如果还有m n 使得 a 1 m e则am a 1 1 m a 1 m a 1 m 1 e 1 e因为m n 又am e 这与a的阶为n矛盾 a 1的阶也为n 如果a的阶为无限的 而a 1的阶是有限的 设a 1的阶是n 即 a 1 n e an a 1 1 n a 1 n a 1 n 1 e 1 e这与a的阶为无限的矛盾 a 1的阶也为无限的 所以a与a 1具有相同的阶 定理 有限群中 每个元素的阶都是有限的 证明 设G e a1 an 1 则e的阶为1 对任意的a G a e由于消去律成立 有ai ai 1由于a a2 an G所以存在k 使得ak e 特殊群 一 交换群 阿贝尔群 Abel群 定义 设 G 是群 运算 是可交换的 则称它是交换群定理 G 是交换群 当且仅当对任何a b G有 ab ab aa bb 即 ab 2 a2b2 证明 充分性 任取a b G设有 ab 2 a2b2由于a 1 b 1 Ga 1 ab ab b 1 a 1 aa bb b 1 a 1a ba bb 1 a 1a ab bb 1 ba ab所以 G 是交换群 必要性 设 G 是交换群 任取a b G ab ab a ba b a ab b aa bb 定理 设 G e 是群 若除单位元外其他元素都是2阶元 则G是Abel群 证明 对任意的a G 有a2 e所以对任意的a b G 有 ab 2 e 而a2b2 ee e所以 ab 2 a2b2即G是Abel群 例 Klein四元群 例 设 G 是群 a b G 有a3b3 ab 3 a4b4 ab 4 a5b5 ab 5 证明 G 是交换群 证明 任取a b G a 1 b 1 G由a4b4 ab 4 a 1 a4b4 b 1 a 1 ab 4b 1 a 1a a3b3 bb 1 a 1a ba 3 bb 1 a3b3 ba 3又已知a3b3 ab 3 ba 3 ab 3类似由a5b5 ab 5 得a4b4 ba 4又已知a4b4 ab 4 ba 4 ab 4又由 ba 3 ab 3得 ba 3 ab 3 ba 4 ba 3 ab 4 ab 3 ba ab所以 G 是交换群 二 循环群 一类常用的最简单的群 2 定义 设 G 是群 如果存在一个元素g G 使得对每个x G 都存在整数i 有x gi 则称是个循环群 并称g是G的生成元 即G gi i I 其中g0 e g i g 1 i 例子 例 N4 4 是群 N4 0 1 2 3 例 I 是群 结论 生成元不唯一 注 若群的元素个数至少为2 则单位元不会是生成元 例 设N7 1 2 3 4 5 6 N7 7 是循环群吗 如是 指出生成元 定理 任何一个循环群是Abel群 证明 设G gk k I 对任意的x y G 存在r t I使得x gr y gtxy grgt gr t gt r gtgr yx所以 G是Abel群 定理设 G G n 则O g n 且G g1 g2 gn e 证明 先证明任何0 gk k I 所以对任意的k 令k mq r其中q r I 0 r m 则对任意的x Gx gk gmq r gmqgr gm qgr eqgr gr 0 r m 由于r的取值最多有m个 所以G中元素最多有m个 m n 这与 G n矛盾 所以不存在m n 使得gm e 定理设 G G n 则O g n 且G g1 g2 gn e 再证明 g1 g2 gn 中元素互不相同 假设存在i j 0 i j n 使得gi gj 则gj i gjg i gi gi 1 e因为j i n又gj i e与 矛盾 所以 g1 g2 gn 中元素互不相同 最后证明gn e 因为e G 而n 1个元素g1 g2 gn 1中无e 又 G n 于是必有gn e 由 1 O g n 所以最后得G g1 g2 gn e 循环群的生成元 定理 关于循环群的生成元有 1 I 0 的生成元只能是1或 1 2 Nn n 的生成元只能是a 其中 a n 1 证明 1 设I 因为1 I 所以存在k I 使得a a a 1 k个a相加 所以a只能是1或 1 2 设Nn 因为 1 Nn 所以存在k I 使得 a n a n n a 1 k个 a 相加 即 ka 1 所以存在p I 使得ka pn 1 即 a n 1 陪集与Lagrange定理 设 G 是群 H G 在G的元素之间确定一个二元关系R 对 a b G R a 1b H则R是G的二元关系 且是等价关系 因此R可以唯一确定G的一个划分 其划分就是子群H的陪集 一 子群的陪集例N6 0 1 2 3 4 5 群的运算表如图 H1 0 H2 0 3 H3 0 2 4 1 定义 设H G 对任意a G 定义集合 aH ah h H Ha ha h H 称为由a确定的H在G中的左 右 陪集 结论 一般地aH Ha 但若运算 满足交换律 则aH Ha 例 是的子群 H3 0 2 4 求H3的各个左陪集 例 设G I H km k I 则H G 求H的左右陪集 例 设S3中子群H 1 12 求H的左右陪集 二 陪集的性质 定理 设H G 则 1 H eH a aH证明 因为e H 所以 有eH eh h H h h H H 又a ae ah h H ah所以a aH 2 aH H 证明 因为H是G的子群 所以 对任意的h1 h2 H 若h1 h2 则ah1 ah2 a G所以aH中没有共同元素 所以 aH H 二 陪集的性质 3 a H aH H证明 因为a H 所以aH ah h H h h H H又由于 aH H 所以aH H 因为a ae aH而aH H 所以a H 二 陪集的性质 4 对 x aH 有aH xH证明 由于x aH 所以 存在h1 H 使得x ah1 所以a xh1 1 对任意的y xH xh h H 存在h2 H使得y xh2 有y xh2 ah1 h2 a h1h2 aH所以aH xH 对任意的y aH ah h H 存在h3 H使得y ah3 有y ah3 xh1 1 h3 x h1 1h2 xH所以xH aH 所以aH xH 二 陪集的性质 5 aH bH a bH b aH b 1a H a 1b H证明 充分性设b aH由性质 4 得aH bH 必要性已知aH bH b be bH而aH bH b aH 6 对任何a b G 有aH bH或者aH bH 证明 假设aH bH 设x aH bH 则x aH且x bH 由性质 4 有aH bH 三 子群的指数和Lagrange定理 定理 设G是群 H G SL aH a G SR Ha a G 则存在SL到SR的双射 证明 设f aH Ha 1 SL SR 1 因为a1H a2H a1 1a2 H Ha1 1 Ha2 1所以f是单射 2 对 Ha SR 取a 1H SL 则f a 1H Ha 所以f是满射 由 1 和 2 f是双射定义 设G是群 H G 群G关于H的左 右 陪集个数 称为H在G中的指数 记为 G H 五 子群的阶数 拉格朗日定理 Lagrange定理 定理 Lagrange定理 设G是有限群 H G 则 G H G H 证明 设 G H m 则存在a1 a2 am G 使得G 1maiH且aiH ajH i j 因为 aiH H 所以 G aiH m H H G H 推论1设G是有限群 H G 则 H G 推论2设G是有限群 且 G n 则对任意的a G 有O a n且an e 若n为素数 则G为循环群 证明 任取a G 且a e 由于有限群中元素的阶都是有限的 令a的阶是m 构造集合H a a2 a3 am e 任取ai aj H aiaj ai j 如果i j m 则ai j H 如果i j m 则0 i j 2m 令i j t m 0 t mai j at m atam ate at H所以ai j H 所以运算在H上封闭 因H是有限集合 所以H是G的子群且H是循环群 而 H m 由Lagrange定理得m是n的因子 即n km k I 所以an akm am k ek e 若n为素数 则m 1或n 但由于a e 所以H G 即G为循环群 例确定所有可能的四阶群 代数系统的同态与同构 一 例1 是正实数R 上的乘法 是实数R上的加法 它们运算的性质完全一样 都满足 可交换 可结合 有单位元 每个元素可逆 那么如何反映它们间的相同性呢 通过一个映射f R R任何x R f x lgx 是双射 任何x y R f x y lg x y lgx lgy f x f y f 1 lg1 0在 在 x 100f x lgx lg100 2x 1 1 100f x 1 lgx 1 lg1 100 2 f x 1 x y x y f x f y f x f y f 幺元1 幺元0 100 100 1 f 100 2 f 100 1 2 二 同态 同构的定义 定义 设 是两个代数系统 和 都是二元运算 如果存在映射f X Y 使得对 x1 x2 X 有f x1 x2 f x1 f x2 同态 同构 关系式则称f是从到的同态映射 简称这两个代数系统同态 记作X Y 并称为的同态像 如果f是满射的 称此同态f是满同态 如果f是入射的 称此同态f是单一同态 如果f是双射的 称与同构 记作X Y f是到的同态 同构 称之为自同态 自同构 设I是整数集合 R是I上模k k是正整数 同余关系 因R是I上等价关系 所以得商集I R 将I R记作Nk 即 Nk 0 1 2 k 1 在Nk上定义运算 k和 k 我们分别称之为以k为模的加法和乘法 定义为 任取 x y Nk x k y x y modk x k y x y modk 为了方便 将N4 0 1 2 3 简记成 N4 0 1 2 3 任何x y N4 x 4y x y mod4 例2 N4 0 1 2 3 N4上定义运算 4 任何x y N4 x 4y x y mod4 其运算表如图所示 B 0 1 是B中异或运算 其运算表如下图所示 证明N4 B 构造映射g N4 B如下 下面验证g是同态映射 g 1 42 g 3 1g 1 g 2 1 0 1 g 1 42 g 1 g 2 g 2 43 g 1 1g 2 g 3 0 1 1 g 2 43 g 2 g 3 同态代数系统运算表的相似性 将运算表中的各个元素分别用它的映像代替得到右表 看出此表与运算表的相似性 例3 证明与同构 构造映射f N4 X如下 下面验证f是同构映射 f 1 42 f 3 Lf 1 f 2 R A L f 1 42 f 1 f 2 f 2 43 f 1 Rf 2 f 3 A L R f 2 43 f 2 f 3 同构的两个代数系统运算表的相同性 将运算表中的各个元素分别用它的映像代替得到右表 看出此表与运算的相同性 三 代数系统间的同构关系 是等价关系 1 有自反性 任何代数系统 有X X 证明 因为有双射IX X X 任取x1 x2 X 有IX x1 x2 x1 x2 IX x1 IX x2 所以X X 2 有对称性 任何代数系统 如果有X Y则必有Y X 证明 因有X Y 有双射f X Y 任取x1 x2 X 有f x1 x2 f x1 f x2 因f是双射 有f 1 Y X 任取y1 y2 Y因f X Y是满射 x1 x2 X 使得y1 f x1 y2 f x2 x1 f 1 y1 x2 f 1 y2 f 1 y1 y2 f 1 f x1 f x2 f 1 f x1 x2 f 1 f x1 x2 IX x1 x2 x1 x2 f 1 y1 f 1 y2 Y X 3 有传递性 任何代数系统 如果有X Y和Y Z 则必有X Z 证明 因有X Y 有双射f X Y 任取x1 x2 X 有f x1 x2 f x1 f x2 因有Y Z 有双射g Y Z 任取y1 y2 Y 有g y1 y2 g y1 g y2 有双射h g f X Z 任取x1 x2 X h x1 x2 g f x1 x2 g f x1 x2 g f x1 f x2 g f x1 g f x2 g f x1 g f x2 h x1 h x2 X Z 是个等价关系 四 代数系统同构的性质 任何代数系统 X Y f X Y是同构映射 任取x1 x2 X 有f x1 x2 f x1 f x2 1 保持结合律 如果运算 可结合 则运算 也可结合 证明 任取y1 y2 y3 Y因f X Y是满射 x1 x2 x3 X 使得y1 f x1 y2 f x2 y3 f x3 y1 y2 y3 f x1 f x2 f x3 f x1 f x2 x3 f x1 x2 x3 f x1 x2 x3 f x1 x2 f x3 f x1 f x2 f x3 y1 y2 y3 也可结合 2 保持交换律 如果运算 可交换 则运算 也可交换 3 保持单位元存在性 如果运算 有单位元e 则运算 也有单位元e 且f e e 证明 任取y Y因f X Y是满射 x X 使得y f x y f e f x f e f x e f x yf e y f e f x f e x f x y所以f e 是相对 的单位元 即f e e 4 保持零元存在性 如果运算 有零元 则运算 也有零元 且f 证明 任取y Y因f X Y是满射 x X 使得y f x y f f x f f x f f y f f x f x f 所以f 是相对 的零元 即f 5 保持逆元存在性 如果中每个x X可逆 即x 1 X 则中每个y Y也可逆 即y 1 Y 且如果y f x 则y 1 f x 1 f x 1 证明 任取y Y因f X Y是满射 x X 使得y f x 设运算 的单位元e 运算 的单位元e f e e y f x 1 f x f x 1 f x x 1 f e e f x 1 y f x 1 f x f x 1 x f e e 所以y 1 f x 1 f x 1 定理 设f是代数系统到代数系统的同构映射 a 如果是半群 那么在f的作用下 同态像也是半群 b 如果是独异点 那么在f的作用下 同态像也是独异点 c 如果是群 那么在f的作用下 同态像也是群 六 同态核 定义 f是从到的同态映射 X Y e 和e 分别是X Y中单位元 定义集合ker f 为 ker f x x X f x e 称ker f 为f的同态核 例g是到的同态映射 ker g 0 2 定理设f是从群到群的同态映射 则f的同态核K是X的子群 证明 因为f e e 所以e K设a b K 则f a b f a f b e e e 所以a b K对任意的a Kf a 1 f a 1 e 1 e 故a 1 K 因此 是的子群 定义 令和是含有两个运算的代数系统 其中 都是二元运算 如果存在双射f X Y 使得对任何x1 x2 X 满足f x1 x2 f x1 f x2 f x1 x2 f x1 f x2 则称这两个代数系统同构 6 保持分配律 如果运算 对 可分配 则 对 也可分配证明 任取y1 y2 y3 Y因f X Y是满射 x1 x2 x3 X 使得y1 f x1 y2 f x2 y3 f x3 y1 y2 y3 f x1 f x2 f x3 f x1 f x2 x3 f x1 x2 x3 f x1 x2 x1 x3 f x1 x2 f x1 x3 f x1 f x2 f x1 f x3 y1 y2 y1 y3 所以 对 也可分配 7 保持吸收律 如果运算 和 满足吸收律 则 和 也满足吸收律 证明 任取y1 y2 Y因f X Y是满射 x1 x2 X 使得y1 f x1 y2 f x2 y1 y1 y2 f x1 f x1 f x2 f x1 f x1 x2 f x1 x1 x2 f x1 因 和 满足吸收律 y1y1 y1 y2 f x1 f x1 f x2 f x1 f x1 x2 f x1 x1 x2 f x1 因 和 满足吸收律 y1 五 同态性质的保持 定理 代数系统 X Y f X Y是同态映射 如果中 满足交换 结合 有单位元 有零元 每个元素可逆 则中 也满足上述性质 另外 由于同态关系 不满足对称性 所以同态性质的保持只是单向的 即Y中 的性质 X中 不一定有 环与域 一 环 Ring 1 定义 给定代数系统 若R上二元运算 和 满足 是交换群 称为加法群 是半群 乘法半群 对 可分配 即对任何a b c R 有a b c a b a c a b c a c b c 称是个环 判断 是否为环 2 环的运算法则设是环 a b c R 符号的约定 对 单位元用0表示 称为零元 a的逆元用 a表示 称为负元 对 单位元用1表示 若单位元存在 a的逆元用a 1表示 若a的逆元存在 a b a b a a a a 0 0 a a 0 a a a a b c a c b c b a b a b a b a b证明 可以由群的性质得 a b b a a b a 0 0 a 0证明 0 a 0 a 0 a 0 0 a 0 a 0 a 0 a 0 a 0 a 0 a 0 a 0 0 a 0 a b a b a b 证明 a b a b a a b 0 b 0所以 a b a b a b a b a b c a b a c a b a c a b c a c b c 零因子 定义 设是环 a b R 且a 0 b 0 但有a b 0 则称a是R的一个左零因子 b是R的一个右零因子 若a即是左零因子 又是右零因子 则称a为R的一个零因子 例 是环 求环中的一个左零因子 一个右