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

1离散数学（二）袁细国西安电子科技大学[e-mail]同态和同构代数的同态与同构11同态代数的性质2主要内容:同态与同构的概念重点:同态代数的性质难点:重点和难点:一、同态与同构两个代数在结构上是一致的,大致地说,有以下3点要求:(1)两个代数必须有相同的构成成分;(2)两个代数的运算和常数必须遵循相同的规则;(3)两个代数的载体必须有相同的基数。这种结构上的一致性,数学上叫同构,可以用与代数的“运算”和“常数”密切相关的一个双射函数来精确地刻画。一、同态与同构同构定义:设A=S,*,△,k和A′=S′,*′,△′,k′是同构的,如果存在一双射函数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的每一运算都保持，简称为运算保持一、同态与同构同态定义:设A=S,*,△,k和A′=S′,*′,△′,k′是具有相同构成成分的代数,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′的同态,h(S),*′,△′,k′称为A在映射h下的同态象。一、同态与同构同态的分类:根据函数h的特点，可将同态分成如下几类：(1)如果h是单射，那么称h是单一同态;(2)如果h是满射的,那么称h是满同态;(3)如果h是双射的,那么称h是从A到A′的同构;(4)如果A=A′,那么称h是自同态;(5)如果A=A′且h是同构,那么称h是自同构。一、同态与同构同态的图示:hA=S,*,△,k同态象h(S),*',△',k'A'=S',*',△',k'h是从A到A′的同态,h(S),*′,△′,k′称为A在映射h下的同态象一、同态与同构例1(a)：R＋：正实数集，R：实数集，试证明：R＋,·,1与R,+,0同构。证明：设f∶R＋→R,f(x)=logx,由于(1)证明f∶R＋→R双射。易见f∶R＋→R单射,因为对数函数单调增加；f∶R＋→R满射：任意y∈R,存在x=ey∈R＋,使得f(x)=logey=y;(2)运算保持。对所有x，y∈R,均有f(x·y)=log(x·y)=logx+logy=f(x)+f(y)；(3)常元运算保持。f(1)=log1=0。所以R＋,·,1与R,+,0同构。一、同态与同构例1(b)：集合A={1,2,3,4},函数f∶A→A,f={1,2,2,3,3,4,4,1},f0表示A上的恒等函数；f1表示f；f2表示合成函数f·f；f3表示f2·f；f4表示f3·f；则f4=f0。设F={f0,f1,f2,f3},则代数F,·,f0可以用左下方的运算表给定,这里f0是么元。集合N4={0,1,2,3},+4是模4加法,代数N4,+4,0用右下方的运算表给定,这里0是么元。·f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2+4012300123112302230133012试证明这两个代数同构。一、同态与同构例1(b)证明：F,·,f0，F={f0,f1,f2,f3};N4,+4,0，N4={0,1,2,3}作映射h∶F→N4,h(fi)=i(i=0,1,2,3)(1)h∶F→N4双射；(2)h(f0)=0；(3)任取fi，fj∈F，i，j∈N4,因为h(fi)=i，h(fj)=j,所以h(fi·fj)=h(fi+j)=h(f(i+j)mod4)=(i+j)mod4=i+4j=h(fi)+4h(fj)。所以,代数F,·,f0和N4,+4,0同构。一、同态与同构例1(c)：证明代数N,+和I+,·是不同构的。证明：使用反证法。假设h是从N,+到I+,·的一个同构。因为h是从N到I+的一个满函数,必有x∈N(x≥2)和某质数p(p≥3),使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。因为0＜1≤x-1＜x,所以，在映射h下,1至少是两个元素的象,得出h不是双射函数,因此N,+和I+,·不同构。一、同态与同构定理1：设h是从A=S,*,△,k到A′=S′,*′,△′,k′的同态,那么A的同态象h(S),*′,△′,k′是A′的子代数。证明：为证同态象h(S),*′,△′,k′是A′的一个子代数,只要证明:(1)h(S)⊆S′。这从h:S→S′函数的事实得出。h(S)⊆S′(2)据同态定义,h(k)=k′,因为k∈S,得出k′=h(k)∈h(S),即k′∈h(S)。(3)h(S)关于运算*′是封闭的。因为如果a,b∈h(S),那么存在x、y∈S,使h(x)=a和h(y)=b。所以a*′b=h(x)*′h(y)=h(x*y)=h(z)∈h(S)(由于x*y=z∈S)。(4)h(S)关于运算△′是封闭的。对任意a∈h(S),存在元素x∈S,使h(x)=a,所以△′a=△′h(x)=h(△x)∈h(S)(由于△x∈S)。证毕。二、同态代数的性质定理2设h是从代数A=S,*,×到A′=S′,*′,×′的同态,这里*,*′,×,×′都是二元运算,A″=h(S),*′,×′是A的同态象。(a)若*可交换(可结合),则在A″中,*′也是可交换(可结合)。(b)对*,若A有么元e(零元0),则对*′,代数A″中有么元h(e)(零元h(0))。(此时h(e)不一定是代数A′中的实际么元,除非h是满同态。)(c)对于*,若一个元素x∈S具有逆元x-1,则对于*′,在代数A″中,元素h(x)具有逆元h(x-1)。(d)若运算*对运算×是可分配的,则在A″中运算*′对运算×′也是可分配的。二、同态代数的性质定理2(a)的证明：因为h：S→h(S)是代数A到A″满同态，所以h(S)中任一元素可写成h(x)的形式，其中x∈S。对于任意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(x1)*′(h(x2)*′h(x3))所以,*′是可交换(或可结合的)。二、同态代数的性质例2：设S={a,b,c,d},S′={0,1,2,3},代数A=S,*和B=S′,由下表定义:*abcdaabcdbbbddccdcdddddd012300110111212123230123**可以验证在函数h:S→S′中，其中h(a)=0,h(b)=1,h(c)=0,h(d)=1，保持运算。因此,h:S→S′是A到B的同态。二、同态代数的性质例2：设S={a,b,c,d},S′={0,1,2,3},代数A=S,*和B=S′,由下表定义:*abcdaabcdbbbddccdcdddddd012300110111212123230123**(1)同态象{0,1},⊛保持代数A的可结合性,但代数B=S′,⊛却是不可结合的,因为(0⊛1)⊛2=1⊛2=2,0⊛(1⊛2)=0⊛2=1。(2)代数A中有么元a和零元d,因此h(a)=0和h(d)=1分别是同态象{0,1},⊛的么元和零元,但它们不是代数B的么元和零元,B中的么元是3,无零元。作业:P174习题6.3第4,8题18谢谢同学们!