离散数学-第2讲-同态与同构ppt课件

《离散数学-第2讲-同态与同构ppt课件》由会员分享，可在线阅读，更多相关《离散数学-第2讲-同态与同构ppt课件（18页珍藏版）》请在装配图网上搜索。

1、1离散数学（二）离散数学（二）袁细国袁细国西安电子科技大学西安电子科技大学1离散数学（二）袁细国同态和同构同态和同构代数的同态与同构代数的同态与同构11同态代数的性质同态代数的性质2主要内容主要内容:同态与同构的概念同态与同构的概念重点重点:同态代数的性质同态代数的性质难点难点:重点和难点重点和难点:同态和同构代数的同态与同构11同态代数的性质2主要内容:同态一、同态与同构一、同态与同构两个代数在结构上是一致的两个代数在结构上是一致的,大致地说大致地说,有以下有以下3 3点要求点要求:(1)(1)两个代数必须有相同的构成成分两个代数必须有相同的构成成分;(2)(2)两个代数的运算和常数必须遵循

2、相同的规则两个代数的运算和常数必须遵循相同的规则;(3)(3)两个代数的载体必须有相同的基数。两个代数的载体必须有相同的基数。这这种种结结构构上上的的一一致致性性,数数学学上上叫叫同同构构,可以用与代数的“运算”和“常数”密切相关的一个双射函数来精确地刻画。一、同态与同构两个代数在结构上是一致的,大致地说,有以下一、同态与同构一、同态与同构同构定义同构定义:设A=和A=是同构的,如果存在一双射函数h，使(1)h:S S；(2)h(a*b)=h(a)*h(b)；(3)h(a)=h(a)；(4)h(k)=k；则称h是从是从A到到A的同构，的同构，A叫做叫做A在映射h下的同构象同构象。在h作用下，A

3、的每一运算都保持，简称为运算保持运算保持一、同态与同构同构定义:在h作用下，A的每一运算都保持，简称一、同态与同构一、同态与同构同态定义同态定义:设A=和A=是具有相同构成成分的代数,h是一个函数是一个函数。如果满足(1)h:S S；(2)h(a*b)=h(a)*h(b)；(3)h(a)=h(a)；(4)h(k)=k；则称h是是从从A到到A的的同同态态,称为A在映射h下的同态象同态象。一、同态与同构同态定义:一、同态与同构一、同态与同构同态的分类同态的分类:根据函数h的特点，可将同态分成如下几类：(1)如果h是单射，那么称h是单一同态单一同态;(2)如果h是满射的,那么称h是满同态满同态;(3

4、)如果h是双射的,那么称h是从A到A的同构同构;(4)如果A=A,那么称h是自同态自同态;(5)如果A=A且h是同构,那么称h是自同构自同构。一、同态与同构同态的分类:一、同态与同构一、同态与同构同态的图示同态的图示:hA=同态象同态象A=h是从是从A到到A的同态的同态,称为称为A在映射在映射h下的同态象下的同态象一、同态与同构同态的图示:hA=同态象一、同态与同构一、同态与同构例例1(a)：R：正实数集，R：实数集，试证明：与同构。证明：证明：设f R R,f(x)=logx,由于 (1)证明证明f R R 双射双射。易见 f R R单射,因为对数函数单调增加；fRR满射：任意yR,存在x=

5、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(a)：R：正实数集，R：实数集，试证一、同态与同构一、同态与同构例例1(b)：集合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

6、,+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+4012300123112302230133012试证明这两个代数同构。试证明这两个代数同构。一、同态与同构例1(b)：集合A=1,2,3,4,一、同态与同构一、同态与同构例例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 N

7、4,因为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(b)证明：，F=一、同态与同构一、同态与同构例例1(c)：证明代数和是不同构的。证明：证明：使用反证法。假设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是一质

8、数,唯一的因子是p和1,根据(1),h(x)=1或h(0)=1;根据(2),h(1)=1或h(x-1)=1。因为01x-1x,所以，在映射h下,1至少是两个元素的象,得出h不是双射函数,因此和不同构。一、同态与同构例1(c)：证明代数和 I+一、同态与同构一、同态与同构定理定理 1：设h是从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

9、),那么存在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)=h(x)h(S)(由于xS)。证毕。证毕。一、同态与同构定理 1：设h是从A=二、同态代数的性质二、同态代数的性质定理定理2 设h是从代数A=到A=的同态,这里*,*,都是二元运算,A=是A的同态象。(a)若*可交换(可结合),则在A中,*也是可交换(可结合)。(b)对*,若A有么元e(零元0),则对*,代数A中有么元h(e)(零元h(0)。(此时

10、此时h(e)不一定是代数不一定是代数A中的实际么元中的实际么元,除非除非h是满同态。是满同态。)(c)对于*,若一个元素xS具有逆元x-1,则对于*,在代数A中,元素h(x)具有逆元h(x-1)。(d)若运算*对运算是可分配的,则在A中运算*对运算也是可分配的。二、同态代数的性质定理2 设h是从代数A=S,*,二、同态代数的性质二、同态代数的性质定理定理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*

11、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(x1)*(h(x2)*h(x3)所以,*是可交换(或可结合的)。二、同态代数的性质定理2(a)的证明：二、同态代数的性质二、同态代数的性质例例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，保持运算。因此,

12、h:SS是A到B的同态。二、同态代数的性质例2：设S=a,b,c,d,二、同态代数的性质二、同态代数的性质例例2：设S=a,b,c,d,S=0,1,2,3,代数A=和B=由下表定义:*abcdaabcdbbbddccdcdddddd012300110111212123230123*(1)同态象保持代数A的可结合性,但代数B=却是不可结合的,因为(0 1)2=1 2=2,0(1 2)=0 2=1。(2)代数A中有么元a和零元d,因此h(a)=0和h(d)=1分别是同态象的么元和零元,但它们不是代数B的么元和零元,B中的么元是3,无零元。二、同态代数的性质例2：设S=a,b,c,d,作业作业:P174 习题习题6.3 第第4,8题题作业:18谢谢同学们谢谢同学们!18谢谢同学们!