冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材(第32讲

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

冯伟森Email:fws365@http:// 2013年7月4日星期四

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

主要内容

同态与同构 同态核

环 特殊环 环的同构与同态

域

2013-7-4

计算机学院

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

同态与同构本节研究的是一个代数系统与另外一个代 数系统之间的关系，即撇开集合元素和运算的 具体差异，只考虑两代数系统的运算性质上的 差异，或者说在什么条件下两代数系统无差异 或者相似。 代数系统之间的这种相互关系是通过映射 来反应的。映射有单射、满射和双射，相应本 节讲的是单同态、满同态和同构以及性质。

2013-7-4

计算机学院

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

定义15.9 设〈X,*〉与〈Y, о〉是两个代数系统， 如在集合X与Y之间存在映射f:X Y,使得对 a,b X,有： f(a*b)=f(a)оf(b) 则称f是从〈X,*〉到〈Y,о〉的同态映射，简 称为同态，此时代数系统〈X,*〉与代数系统 〈Y,о〉称为同态的，记为X∽Y。 f(X) Y 称为X的一个同态象。如果

2013-7-4

计算机学院

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

① f : X Y 是 一 个 单 射 ， 则 称 f 是 从 〈X,*〉 到 〈Y,о〉的单一同态； ② f : X Y 是 一 个 满 射 ， 则 称 f 是 从 〈X,*〉 到 〈Y,о〉的满同态； ③ f : X Y 是 一 个 双 射 ， 则 称 f 是 从 〈X,*〉 到 〈Y,о〉的同构，记为X≌Y。 若集合X=Y,则此时对应的同态和同构分 别称为自同态、单一自同态、满自同态和自同 构。

2013-7-4

计算机学院

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

例15-6.1 证明代数系统〈R+ ,×〉与〈R,+〉是同构的。 证 明 ： 设 f : R+ R , 且 f ( x ) =ln ( x ) , 则 ： 1.f是一个R+ R的映射； 2. 对 y R, 均 x=ey R+, 使 得 f(x)=ln(x)=ln(ey)=y , 所以f是一个满射； 3. 对 x y R+, 有 ln(x) ln(y) , 所 以 f 是 一 个 单射 ； 由1、2、3知：f是一个双射。 4.对 x,y R+,有： f(x×y)=ln(x×y)=ln(x)+ln(y)=f(x)+f(y) 由1、2、3、4知：f是一个双射且满足 f(x*y)=f(x)оf(y) ∴ R+ ≌ R2013-7-4 计算机学院 6

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

例15-6.2 在自然数加半群〈N,+〉与剩余类加群 <Z2 , >之间定义映射f:N Z2 如下： [0] ,当n是 偶 数 f ( n) [1] ,当n是 奇 数

证明f是N到Z2的满同态映射。证明：∵ 对 n1,n2 N , 1)当n1和n2同奇偶时，f(n1+n2)=[0],而f(n1)和f(n2)要 么同为[0],要么同为[1],从而f(n1) f(n2)=[0]; 2)当n1和n2不同奇偶时，f(n1+n2)=[1],而f(n1)和f(n2) 中一个为[0],一个为[1],从而f(n1) f(n2)=[1]; ∴ N~Z2 ,而 f ( x ) 显然是一个满射，所以，结论成立。2013-7-4 计算机学院 7

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

性定理15.15

质

设〈X,*〉与〈Y,о〉是两个代数系统，f:X Y是一个 该定理说明同态映射不仅确 同态映射，则： 定了不同集合元素间的对应 关系，而且还保持了代数系 1) 如果运算‘*’在X中是封闭的 运算‘о’在f(X) 统的

运算性质。因此，能够 Y中是封闭的； 建立同态映射的代数系统之 2)〈X,*〉满足结合律 〈f(X),о〉满足结合律； 间有着很大的一致性。 3)〈X,*〉满足交换律 〈f(X),о〉满足交换律; 4)〈X,*〉满足消去律 〈f(X),о〉满足消去律； 5)〈X,*〉存在幺元e1 〈f(X),о〉存在幺元e2; 6)〈X,*〉存在零元θ1 〈f(X),о〉存在零元θ2; 7)在X中每元关于运算‘*’ 有逆元 f(X)中每元关于运算‘о’ 有逆元。2013-7-4 计算机学院 8

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

定理15.16 设〈X,*〉与〈Y,о〉是两个代数 系统，f:X Y是满同态，则： 1) 如果X是半群 Y是半群； 2) 如果X是群 Y是群。 在同态映射下，像源的代数性质都为像集 所具有。但是，像集所具有的代数性质却未必 为像源所具有。(如<Z2 , > 是群，而〈N,+〉不是群) 如果f:X Y是同构映射，则代数系统X与Y 许多性质完全相同。而且代数系统之间的同构 关系是等价关系。2013-7-4 计算机学院 9

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

同态核下面通过考察像源中被映射到像集幺元的 那些元素具有的代数特征来揭示同态的分类特 征。

定义15.10设f是群〈G,*〉到〈H,о〉的同态映射，

令：K=Kerf={a|a G∧f(a)=e′} 其中e′是H的单位元，则称Kerf为f的同态核， f(G)={f(a)|a∈G}称为f的像集。2013-7-4 计算机学院 10

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

定理15.17 设f是群〈G,*〉到〈H,о〉的同态 映射， e,e′分别是G和H的单位元，则同态核 Kerf是G的不变(正规)子群。 证明 由定义Kerf={a|a∈G∧f(a)=e′},因为f 是同态映射，所以有f(e)=e′。故e∈Kerf,所 以Kerf是G的非空子集。 对任意的a,b∈Kerf,由定义有 f(a)=e′,f(b)=e′ 为什么？ 又因为f是同态映射，所以有 f(b-1)=(f(b))-1 -1)=f(a)оf(b-1) f(a*b =f(a)о(f(b))-1=e′оe′-1=e′2013-7-4 计算机学院 11

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

即a*b-1∈Kerf,由定理15.8所以<Kerf,*>是 可以进一步证明，在同态映射下, <G,*>的子群。 像源集G具有陪集分解式， 另一方面，对任意的 k∈Kerf,a∈G,我们有 其中每个 -1)=f(a)оf(k)оf(a-1) f(a*k*a 陪集是像集中某个元素 =f(a)оe′о(f(a))-1=f(a)о(f(a))-1=e′ 的像源。 所以有a*k*a-1∈Kerf,由定理15.14 故<Kerf,*>是<G,*>的不变子群。 在例15-6.2中，[0]是Z2中的幺元，因而映射 的同态核是集合Kerf ={0,2,4,6,‥‥}。2013-7-4 计算机学院 12

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

环和域前面讨论了具有一个二元运算的代数系 统——半群、含幺半群、群、子群。 下面讨论具有两个二元运算的代数系统。 给定两个代数系统<A,+>,<A,*>可将它们组合 成一个具有两个二元运算的代数系统<A,+,*>, 而这两个二元运算符+和*之间是有联系的。 环在计算机科学的很多领域，诸如编码理 论的研究中

起着重要作用；而域，特别是有限 域是纠错码理论的基础。2013-7-4 计算机学院 13

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

环

Ring

定义16.1 一个代数系统<R,+, * >,如果满足： (1)<R,+>是阿贝尔群； (联系两个二元运算， (2)<R, * >是半群； 否则就不是一个系统 (3)运算*在运算+上可分配。即对任意a,b, 而是两个系统) c R有 a*(b+c)=(a*b)+(a*c) (b+c)*a=(b*a)+(c*a) 则称<R,+, *>是一个环。2013-7-4 计算机学院 14

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

例16-1.1 在加法和乘法运算下，整数、实 数、有理数、偶数和复数都能构成环。 <Z,+, × > <R,+, × > <Q,+, × > <E,+, × > <C,+, × > +可以交换，0是+的幺元， i的逆为-i;+, ×可结合, ×对+可分配2013-7-4 计算机学院 15

冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材

例16-1.2 设Zk 表示整数集Z上的模k剩余类集 合，即 Zk={[0],[1],[2],…,[k-1]} <Zk , >是群(剩余类加群), <Zk , >是半群(剩余类乘半群), ∵ 对 [i],[j],[k] Zk 有[i] ([j] [k])=[i(j+k)]=[ij+ik] =[ij] [ik] =([i] [j]) ([i] [k]) ∴ <Zk , , >是环，称为(模k)剩余类环。 特别， k=2时，称为布尔环。2013-7-4 计算机学院 16