离散数学-同态和同构省名师优质课赛课获奖课件市赛课一等奖课件

离散数学(二)第二讲计算机学院:焦晓鹏1/15同态和同构代数同态与同构11同态代数性质2主要内容:同态与同构概念重点:

同态代数性质难点:重点和难点:2/15一、同态与同构两个代数在结构上是一致,大致地说,有以下3点要求:

(1)两个代数必须有相同组成成份;(2)两个代数运算和常数必须遵照相同规则;

(3)两个代数载体必须有相同基数。

这种结构上一致性,数学上叫同构,能够用与代数“运算”和“常数”亲密相关一个双射函数来准确地刻画。3/15一、同态与同构同态定义:设A=<S,*,△,k>和A′=<S′,*′,△′,k′>是含有相同组成成份代数,h是一个函数。假如满足(1)h∶S→S′；(2)对全部a，b∈S,都有h(a*b)=h(a)*′h(b)；(3)对全部a∈S均,有h(△a)=△′h(a)；(4)

h(k)=k′；则称h是从A到A′同态,<h(S),*′,△′,k′>称为A在映射h下同态象。在h作用下，A每一运算都保持，简称为运算保持4/15一、同态与同构同态分类:依据函数h特点，可将同态分成以下几类：(1)假如h是单射，那么称h是单一同态;(2)假如h是满射,那么称h是满同态;(3)假如h是双射,那么称h是从A到A′同构;(4)假如A=A′,那么称h是自同态;(5)假如A=A′且h是同构,那么称h是自同构。5/15一、同态与同构同态图示:hA=<S,*,△,k>同态象<h(S),*',△',k'>A'=<S',*',△',k'>h是从A到A′同态,<h(S),*′,△′,k′>称为A在映射h下同态象6/15一、同态与同构例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>同构。7/15一、同态与同构例1(b)：集合A={1,2,3,4},函数f∶A→A,f={<1,2>,<2,3>,<3,4>,<4,1>},f0表示A上恒等函数；f

1表示f；f

2表示合成函数f·f；f

3表示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是么元。试证实这两个代数同构。·f0f

1f

2f

3f0f0f

1f

2f

3f

1f

1f

2f

3f0f

2f

2f

3f0f

1f

3f

3f0f

1f

2+40123001231123022301330128/15一、同态与同构例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>同构。9/15一、同态与同构例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+,·>不一样构。10/15一、同态与同构定理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)。

证毕。11/15二、同态代数性质定理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″中运算*′对运算×′也是可分配。12/15二、同态代数性质定理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))所以,*′是可交换(或可结合)。证毕。13/15二、同态代数性质例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同态。

(1)同态象<{0,1},⊛>保持代数A