北京大学：离散数学（一）：15.3-4

1 15.3代数系统的同态与同构 ?同态映射的概念 ?同态映射定义 ?同态映射分类 ?实例 ?同态映射的性质 ?同态映射的合成仍旧是同态映射 ?同态像是映到代数系统的子代数 ?同态像中保持原有代数系统的运算性质 2 同态映射的定义 Axxx xfxfxfoxxxof i ii k kiki ∈? = ,...,, ))(),...,(),((')),...,,(( 21 2121 >=<>=< ',...,',',,...,,, 212211 rr oooBVoooAV与 定义设 是同类型的代数系统，对于i=1,2,…,r，o i 为k i 元运算, 函 数f:A→B, 如果对于所有的运算o i 与o i ’ 则称f 是代数系统V 1 到V 2 的同态映射，简称同态 3 同态映射的定义（续） 4 几点说明 1. 对于二元运算、一元运算、0元运算采用下述表示： 2. 同态映射必须对所有的运算保持等式，包括0元运算 在内，例如 则f 不是V的自同态，因为不保持0元运算 ')( )(')( )(')()( aaf xfxf yfxfyxf = = = ?? oo ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? → ? ? ? ? ? ? ∈ ? ? ? ? ? ? ? ? => ? ? ? ? ? ? ? ? ?=< 00 0 ) 0 0 (,: ,| 0 0 , 10 01 ,, a b a fAAf Rba b a AAV ? ? ? ? ? ? ? ? ≠ ? ? ? ? ? ? ? ? 10 01 ) 10 01 (f 5 同态映射的分类 特殊的同态映射 ?按映射性质分为： ?单同态 ?满同态V 1 ～V 2 ?同构V 1 ?V 2 ?按载体分：自同态 ?综合：单自同态、满自同态、自同构 6 同态映射的实例 (1) V = <Z,+>, f c :Z→Z, f c (x) = cx, c为给定整数 c = 0, 零同态; c = ±1，自同构; 其它c, 单自同态 (2) V = <Z 6 ,⊕>, f p :Z 6 →Z 6 , f p (x) = (px) mod 6, p = 0,1,2,3,4,5 p = 0, f 0 零同态; p = 1, f 1 恒等映射，自同构 p = 2, f 2 = {<0,0>,<1,2>,<2,4>,<3,0>,<4,2>,<5,4>}, p = 3, f 3 = {<0,0>,<1,3>,<2,0>,<3,3>,<4,0>,<5,3>} p = 4, f 4 = {<0,0>,<1,4>,<2,2>,<3,0>,<4,4>,<5,2>} p = 5, f 5 = {<0,0>,<1,5>,<2,4>,<3,3>,<4,2>,<5,1>}自同构 (3) 可以推广到f p :Z n →Z n , 恰好存在n 个自同态 f p (x⊕y) = (p(x⊕y))modn = (px)modn ⊕ (py)modn = f p (x)⊕f p (y) 7 同态性质 ?同态的合成仍旧是同态 ?同态像是映到的代数系统的子代数 ?满同态映射（在同态像中）保持原代数系 统的下述性质： ?交换、结合、幂等、分配、吸收 ?单位元、零元、逆元 ?消去律不一定保持 8 同态的合成仍旧是同态 命题若f:V 1 →V 2 , g:V 2 →V 3 为同态映射，则g°f:V 1 →V 3 也 为同态映射. 证根据集合论的定理，g°f: V 1 →V 3 为映射. 任取V 1 ,V 2 ,V 3 中一组对应的运算o 1 ,o 2 ,o 3 , 设为k 元运算. ?x 1 , x 2 , … , x k ∈V 1 , g°f ( o 1 (x 1 , x 2 , …, x k )) = g ( f( o 1 (x 1 , x 2 , …, x k ) ) ) = g (o 2 ( f(x 1 ), f(x 2 ), …, f(x k ) ) ) = o 3 ( g(f(x 1 )), g(f(x 2 )), …, g(f(x k )) ) = o 3 ( g°f(x 1 ), g°f(x 2 ), …, g°f(x k ) ) 由于运算的任意性，命题得证. 推论代数系统的同构具有自反、对称、传递的性质. 9 同态像是映到代数系统的子代数 是同类型的代数系统，对于i=1,2,…,r，o i 与o i ′是k i 元运算, f:A→B是V 1 到V 2 的同态，则f(A)关于V 2 中的运算构成代 数系统，且是V 2 的子代数，称为V 1 在f 下的同态像. 证f(A)是B 的非空子集.证明f(A) 对V 2 中的所有运算封闭. 若V 2 中有0元运算a′, 则V 1 存在0元运算a, f(a)=a′. 因此 a′∈f(A). 考虑V 2 中任意非0元运算o′( k元运算). 任取f(A)中 元素y 1 ,y 2 ,…,y k ,存在x 1 ,x 2 ,…,x k 使得f(x i )=y i , i=1,2,…,k, 那么 )),...,,(())(),...,(),(('),...,,(' 212121 kkk xxxofxfxfxfoyyyo == 显然上述结果属于f(A). >=<>=< ',...,',',,...,,, 212211 rr oooBVoooAV与 定理1设 10 满同态保持原代数性质 定理2设 >=<>=< ',...,',',,...,,, 212211 rr oooBVoooAV与 是同类型的代数系统，函数f:A→B是V 1 到V 2 的满同态， (1) V 2 中运算保持V 1 中相应运算的下述性质： 交换、结合、幂等、分配、吸收 (2) V 2 中保持V 1 中的单位元、零元、逆元，即 f(e)是V 2 中单位元，e为V 1 中相应运算单位元 f(θ)是V 2 中零元，θ为V 1 中相应运算零元 f(a -1 )是f(a)的逆元 11 几点说明 1.满同态条件重要. 如果不是满同态，有关性质只能在同 态像中成立. 例如 ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? → ? ? ? ? ? ? ∈ ? ? ? ? ? ? ? ? =>?=< 00 0 ) 0 0 (,: ,,| 0 0 , a b a fAAf Rba b a AAV f 不是满同态，将单位元映到f(A)的单位元，不是自身. 其他见书上例题15.22, 15.23. 2. 消去律不一定保持. 书上例题15.24, <Z,?>, <Z 6 ,?>, f(x) = (x) mod 6 12 15.4同余关系与商代数 ?同余关系 ?同余关系与同余类 ?同余关系的实例 ?商代数 ?商代数定义 ?商代数性质 ?同态映射、同余关系与商代数之间的联系 13 同余关系与同余类 定义设V=<A,o 1 ,o 2 ,…,o r > 是代数系统，其中o i 为k i 元 运算，关系～为A上的等价关系，任取A上2k i 个元素 a 1 ,a 2 , …, a ki , b 1 ,b 2 , …, b ki , 如果对于所有的j =1,2,…,k i , a j ～b j 就有 o i (a 1 ,a 2 , … , a ki ) ～ o i (b 1 ,b 2 , … , b ki ) 则称等价关系～对于运算o i 具有置换性质. 如果等价关系～对于V 中的所有运算都具有置换性 质，则称～是V上的同余关系，称A中相关的等价类为 同余类. 14 实例 例1 V=<Z 4 ,⊕>, 有15个等价关系，采用对应的划分表示. 划分{0},{1,2,3} 对应的不是同余关系，因为1～3，但是 1⊕3 ～3⊕3不成立. 同理可以验证以下11个划分对应的也不是同余关系 {1},{0,2,3} {2},{1,3,0} {3},{1,2,0} {0,1},{2,3} {0,3},{1,2} {0},{1},{2,3} {0},{2},{1,3} {0},{3},{1,2} {1},{2},{0,3} {1},{3},{0,2} {2},{3},{0,1} 只有以下3个划分对应于同余关系： {0},{1},{2},{3} {0,1,2,3} {0,2},{1,3} 恒等关系与全域关系都是同余关系，任何代数系统都存在 同余关系. 15 商代数定义 定义设代数系统V=<A,o 1 ,o 2 ,…,o r >，其中o i 为k i 元运算， i =1, 2, … , r. 关系R 为V上的同余关系，V关于R的商代数 记作 )],...,,([])[],...,[],([ 2121 ii kik i aaaoaaao = i o 其中A/R 是关于同余关系的商集. 对于i =1,2,…,r, 运算 定义为 >=< r oooRARV ,...,,,// 21 16 商代数的良定义性 运算的良定义 运算结果与参与运算元素的表示无关 对于任意运算o i , 设为k i 元运算，a j ～b j , j=1,2,…,k i , 则 ])[],...,[],([ )],...,,([ )],...,,([ ])[],...,[],([ 21 21 21 21 i i i i ki ki ki ki bbbo bbbo aaao aaao = = = 17 商代数的性质 设代数系统V, R是V上的同余关系，V 关于R 的 商代数V/R，那么 (1) V/R保持V 的下述性质： 交换、结合、幂等、分配、吸收律 (2) V/R 保持V 的单位元、零元、逆元，即 [e]是商代数的单位元 [θ]是商代数的零元 [a -1 ]=[a] -1 注消去律不一定保持. 例如<Z,×>有消去律，定义等价关 系如下： xRy ? x≡y(mod4). 商代数为V/R=<{[0],[1],[2],[3]},?>. 没有消去律. [2]?[2]=[0]?[2], 但是[0]≠[2]. 18 同态、同余关系与商代数的联系 ?同态映射导出同余关系 ?商代数是原代数的同态像 通过自然映射 ?同态基本定理 代数系统的同态像同构于它的商代数 19 是同类型的代数系统，对于i =1,2,…,r，o i 为k i 元运算, 函数f:A→B为代数系统V 1 到V 2 的同态映射，则由f 导 出的A上的等价关系为V 1 上的同余关系. 证?x, y∈A, x～y ? f(x)=f(y) 任取V 1 上的运算o i ,（k i ≥1），对于任意的a j ～ b j , j =1, 2, … , k i , 同态映射导出同余关系 >=<>=< ',...,',',,...,,, 212211 rr oooBVoooAV与 定理1设 )),...,,(( ,...,2,1),()())(),...,(),((' ))(),...,(),((')),...,,(( 21 21 2121 i i ii ki ijjki kiki bbbof kjbfafbfbfbfo afafafoaaaof = === = ～关于o i 运算具有置换性质，根据o i 的任意性，定理得证. ),...,,( 21 i ki aaao ),...,,( 21 i ki bbbo ～ 20 实例 例2 V=<Z 4 ,⊕>, f i : Z 4 →Z 4 , f i (x) = (ix) mod 4，i = 0,1,2,3 恒等关系If 3 (0)=0, f 3 (1)=3, f 3 (2)=2, f 3 (3)=1 {<0,2>,<2,0>,<1,3>,<3,1>}∪If 2 (0)=f 2 (2)=0, f 2 (1)=f 2 (3)=2 恒等关系If 1 (x)=x, x=0,1,2,3 全域关系 f 0 (x)=0, x=0,1,2,3 导出的同余关系函数 注意：在这个例子中，每个同态都可以导出一个同余关 系；不同的同态，若同态像一样，导出相同的同余关系. 21 定理2设代数系统V=<A,o 1 ,o 2 ,…,o r >，其中o i 为k i 元运算， i=1,2,…,r, R是V上的同余关系，则自然映射 g:A→A/R, g(a)=[a], ?a∈A, 是从V 到V/R 的同态映射. 证设 商代数是原代数的同态像 >=< r oooRARV ,...,,,// 21 ))(),...,(),((])[],...,[],([ )],...,,([)),...,,(( 2121 2121 ii ii kiki kiki agagagoaaao aaaoaaaog == = 考虑o i , 设为k i 元运算. 任取a 1 , a 2 , … , a ki ∈A 由于o i 的任意性，定理得证. 22 定理3 设>=<>=< ',...,',',,...,,, 212211 rr oooBVoooAV与是同类型 的代数系统，对于i=1,2,…,r，o i 与o i ’都是k i 元运算，f:A→B是 V 1 到V 2 的同态，关系R是f导出的V 1 上的同余关系，则V 1 关 于同余关系R的商代数同构于V 1 在f下的同态像，即 >?< ',...','),(/ 211 r oooAfRV 证明思路： (1) 定义h：V 1 /R→f(A), h([a])=f(a) (2) 验证h是良定义的 (3) 验证h是双射的 (4) 验证h是同态映射 同态基本定理 [a]=[b]? aRb ? f(a)=f(b) 23 同态的验证 函数定义 同态定义 函数定义 商代数定义 hahahaho afafafo haaaof aaaoh aaaoh i i i i i ki ki ki ki ki ]))([]),...,([]),([(' ))(),...,(),((' )),...,,(( )]),...,,(([ ]))[],...,[],([( 21 21 21 21 21 = = = = 考虑任意运算，设为k i 元，k i >0, i=1,2,…,r i o 如果是0 元运算[a]∈V 1 /R,则 h([a])=f(a)=a’ 且a’是f(A)中对应的0 元运算 24 同态、同余关系与商代数的联系 定理2 任何商代数都是同态像 定理3 任何同态像在同构意义下是商代数 同余关系、商代数、同态、同态像的对应 同态映射 f:V→V 同态像f(V) 导 出 多对一 一对一 一 对 一 V上同余关系R 商代数V/R 25 实例说明 G 1 = { e, a, b, c }, Klein四元群, G 2 = { e, x } e a b c a e c b b c e a c b a e e a b c e a b c f 1 :G 1 →G 2 f 1 ={<e,e>,<a,e>,<b,x>,<c,x>} f 2 :G 1 →G 2 f 2 ={<e,e>,<b,e>,<a,x>,<c,x>} f 1 (G 1 )= f 2 (G 1 ) = G 2 f 1 导出的同余关系R 1 ：e～a, b～c, G 1 /R 1 ={[e],[b]} f 2 导出的同余关系R 2 ：e～b, a～c, G 2 /R 2 ={[e],[a]} G 1 /R 1 ? G 2 /R 2 26 例3 V=<Z 6 ,⊕>,求V上的同余关系 方法一：确定所有的等价关系，然后判断置换性质 方法二：先找自同态，由同态像确定同余关系 自同态为：f i :Z 6 →Z 6 , f i (x)=(ix) mod 6, i=0,1,2,3,4,5 f 0 的同态像为{0}, f 0 导出的同余关系为全域关系 f 1 和f 5 的同态像为Z 6 ， f 1 导出的同余关系为恒等关系 f 2 和f 4 的同态像为 {0,2,4} f 2 导出的同余关系为: {<0,3>,<1,4>,<2,5>,<3,0>,<4,1>,<5,2>}∪I Z6 f 3 的同态像为{0,3} f 3 导出的同余关系为: {<0,2>,<2,0>,<4,0>,<0,4>,<2,4>,<4,2>, <1,3>,<3,1>,<1,5>,<5,1>,<3,5>,<5,3>}∪I Z6 例题 27 例4 设>?=<>??=< ',',,,,,, 21 kBVkAV o为代数系统， ?<a,b>,<c,d>∈A×B, <a,b>R<c,d> ? a=c (1)证明 R为V 1 ×V 2 上的同余关系 (2)证明 (V 1 ×V 2 )/R ? V 1 证明思路： (1)证明R的自反、对称、传递性 (2)证明R具有置换性质，即令V 1 ×V 2 =<A×B, ?, ?,K>, <a,b> R <c,d>且<a’,b’> R <c’,d’> ? <a,b>?<a’,b’> R <c,d>?<c’,d’> <a,b> R <c,d> ? ?<a,b> R ?<c,d> (3)定义f:V 1 ×V 2 →V 1 , f(<a,b>)=a, 证明f为满同态 (4)证明R是f导出的同余关系，即 f(<a,b>)=f(<c,d>) ? a=c ? <a,b>R<c,d> 例题（续） 28 作业 ?复习要点 ?同态的定义及其性质 ?典型的同态实例 ?商代数的运算是良定义的 ?商代数与原代数的关系 ?书面作业 习题十五，19, 22, 24, 27, 30, 31