《离散数学：同态和同构》由会员分享，可在线阅读，更多相关《离散数学：同态和同构（16页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学( (二二) )第二讲第二讲同态和同构同态和同构代数的同态与同构代数的同态与同构1 11 1同态代数的性质同态代数的性质2 2主要内容主要内容: :同态与同构的概念同态与同构的概念重点重点: : 同态代数的性质同态代数的性质难点难点: :重点和难点重点和难点: :一、同态与同构一、同态与同构两个代数在结构上是一致的两个代数在结构上是一致的, , 大致地说大致地说, , 有以下有以下3 3点要求点要求: : (1) (1) 两个代数的载体必须有相同的基数。两个代数的载体必须有相同的基数。 (2) (2) 两个代数必须有相同的构成成分两个代数必须有相同的构成成分; ; (3) (3
2、) 两个代数的运算和常数必须遵循相同的规则两个代数的运算和常数必须遵循相同的规则; ;这种结构上的一致性这种结构上的一致性, , 数学上叫同构数学上叫同构, , 可以用与代数的“运算”和“常数”密切相关的一个双射函数来精确地刻画。一、同态与同构一、同态与同构同态定义同态定义: : 设A=和A=是具有相同构成成分的代数, h是一个函数是一个函数。如果满足(1) h S S；(2) 对所有对所有a，bS,均有均有h(a*b) = h(a)*h(b)；(3) 对所有对所有aS均均,有有h(a) = h(a)；(4) h(k) = k； 则称h是从是从A到到A的同态的同态, 称为A在映射h下的同态象同
3、态象。在h作用下，A的每一运算都保持，简称为运算保持运算保持一、同态与同构一、同态与同构同态的图示同态的图示: :h是是从从A到到A的同的同态, 称称为A在映射在映射h下的同下的同态象象2024/7/25kSSfkaf(a)bf(b)cf(c)a*bf(a)*f(b)(c) f(c)* 一、同态与同构一、同态与同构同态的分类同态的分类: : 根据函数h的特点，可将同态分成如下几类：(1) 如果h是单射，那么称h是单一同态单一同态; (2) 如果h是满射的, 那么称h是满同态满同态;(3) 如果h是双射的,那么称h是从A到A的同构同构;(4) 如果A=A, 那么称h是自同态自同态; (5) 如果
4、A=A且h是同构, 那么称h是自同构自同构。一、同态与同构一、同态与同构例例1(a)：R：正实数集， R：实数集，试证明： 与同构。证明：证明：设f R R, f(x)=logx, 由于 (1) 证明证明f R R 双射双射。 易见f R R单射,因为对数函数单调增加； fRR满射：任意yR,存在x=eyR,使得f(x)=logey=y; (2) 运运 算算 保保 持持 。 对 所 有 x， y R,均 有 f (xy)=log(xy) =logx+logy=f (x)+f (y)； (3) 常元运算保持常元运算保持。f(1)=log1=0。 所以与同构。一、同态与同构一、同态与同构例例1(b
5、)：集合A=1, 2, 3, 4, 函数fA A, f =, , , , f 0表示A上的恒等函数；f 1表示f；f 2表示合成函数ff；f 3表示f 2f； f 4表示f 3f；则f 4=f 0。设F=f 0, f 1, f 2, f 3, 则代数可以用左下方的运算表给定, 这里f 0是么元。集合N4=0, 1, 2, 3,+4是模4加法,代数用右下方的运算表给定, 这里0是么元。试证明这两个代数同构。f 0f 1f 2f 3f 0f 0f 1f 2f 3f 1f 1f 2f 3f 0f 2f 2f 3f 0f 1f 3f 3f 0f 1f 2+40123001231123022301330
6、12一、同态与同构一、同态与同构例例1(b)证明：证明：，F=f 0, f 1, f 2, f 3;，N4=0, 1, 2, 3 作映射hFN4, h(f i) = i (i=0, 1, 2, 3) (1) hF N4双射； (2) h(f 0) =0； (3)任取f i， f jF， i， j N4, 因为h(f i) = i ， h(f j) = j ,所以 h(f if j) = h(f i+j) = h(f (i+j) mod 4) = (i+j) mod 4 = i +4 j = h(f i) +4h(f j)。 所以, 代数和同构。一、同态与同构一、同态与同构例例1(c)：证明代数
7、和是不同构的。证明：证明：使用反证法。假设h是从到的一个同构。因为h是从N到I+的一个满函数, 必有xN( x2) 和某质数p(p3), 使h(x)=p( I+中有无限多的质数), 因此有以下式子成立：p=h(x)=h(x+0)=h(x)h(0) (1) p=h(x)=h(x-1)+1)=h(x-1)h(1) (2) 但因为p是一质数, 唯一的因子是p和1, 根据(1), h(x)=1或h(0)=1; 根据(2), h(1)=1或h(x-1)=1。因为01x-1x, 所以，在映射h下, 1至少是两个元素的象, 得出h不是双射函数,因此和不同构。一、同态与同构一、同态与同构定理定理 1：设h是从
8、A=到A=的同态, 那么A的同态象是A的子代数。证明：证明：为证同态象是A的一个子代数, 只要证明: (1) h(S)S。这从h: S S函数的事实得出。h(S) S (2) 据同态定义,h(k)=k,因为kS,得出k=h(k)h(S),即kh(S)。 (3) h(S)关于运算关于运算*是封闭的是封闭的。因为如果a,bh(S), 那么存在x、yS, 使h(x)=a和h(y)=b。所以a*b=h(x)*h(y)=h(x*y)=h(z)h(S) (由于x*y=zS)。 (4) h(S)关于运算关于运算是封闭的是封闭的。对任意ah(S), 存在元素xS, 使h(x)=a, 所以a = h(x) =
9、h(x)h(S) (由于xS)。 证毕。证毕。二、同态代数的性质二、同态代数的性质定理定理2 设h是从代数A= 到A= 的同态, 这里*, *, , 都是二元运算, A= 是A的同态象。 (a) 若*可交换(可结合), 则在A中, *也是可交换(可结合) 。 (b) 对 *, 若 A有 么 元 e (零 元 0), 则 对 *, 代 数 A中 有 么 元 h(e) (零元h(0)。(此时此时h(e) 不一定是代数不一定是代数A中的实际么元中的实际么元, 除非除非h是满同态。是满同态。) (c) 对于*,若一个元素xS具有逆元x-1, 则对于*, 在代数A中, 元素h(x)具有逆元h(x-1)。
10、 (d) 若运算*对运算是可分配的, 则在A中运算* 对运算也是可分配的。二、同态代数的性质二、同态代数的性质定理定理2(a)的证明：的证明： 因为h：Sh(S)是代数A到A满同态，所以h(S)中任一元素可写成h(x)的形式，其中xS。 对于任意h(x1) , h(x2) , h(x3) h(S), x1 , x2 , x3 S有h(x1) *h(x2) = h(x1 * x2) = h(x2*x1) = h(x2)*h(x1)所以， (h(x1)*h(x2)*h(x3)=h(x1*x2)*h(x3)=h(x1*x2)*x3) =h(x1*(x2*x3)=h(x1)*h(x2*x3) =h(x
11、1)*(h(x2)*h(x3)所以, *是可交换(或可结合的)。证毕。证毕。二、同态代数的性质二、同态代数的性质例例2：设S = a, b, c, d, S=0, 1, 2, 3, 代数A=和B=由下表定义:*abcdaabcdbbbddccdcdddddd012300110111212123230123* 可以验证在函数h: SS中，其中h(a)=0, h(b)=1, h(c)=0, h(d)=1，保持运算。因此, h: SS是A到B的同态。 (1)同态象保持代数A的可结合性,但代数B=却是不可结合的,因为(0 1) 2=1 2=2, 0 (1 2)=0 2=1。 (2)代数A中有么元a和零
12、元d,因此h(a)=0和h(d)=1分别是同态象的么元和零元, 但它们不是代数B的么元和零元, B中的么元是3, 无零元。6.3本节习题设h是从A=到A=的满同态，证明如果是A的子代数，那么是A的子代数。h h-1-1(T)(T)T Thh-1hA=A=6.3本节习题证明：(i)因为是的子代数，所以T S。故有h-1(T) h-1(S) S。(ii)任取x,yh-1(T),存在x,yT使得h(x)=x,h(y)=y因为x,yS且h是从A到A的同态，所以有 h(x*y)=h(x)*h(y)=x * y T 故x*yh-1(T),即h-1(T)对*运算是封闭的。(iii)因为h(k)=k T,所以k h-1(T)。由(i)(ii)(iii)可知，是的子代数。
