离散数学 ch5.3同态与同构

5-3代数系统的同态与同构有各种各样的代数系统，但是，有些代数系统表面上看不同，实际它们运算的性质相似、或完全一样。这就是代数系统间的同态、同构问题。一.例1(R+,×)：是正实数R+上的乘法×；（R,+）：是实数R上的加法+。表面上看这两个代数系统完全不同，实际它们运算的性质却完全一样，都满足：交换律、结合律、有幺元、每个元素可逆。那么如何反映它们间的共性呢？通过一个映射f:R+R任何x∈R+,f(x)=lgx1任何x,y∈R+,f(x×y)=lg(x×y)=lgx+lgy=f(x)+f(y)f(1)=lg1=0在（R+,×）：在（R,+）:x=100f(x)=lgx=lg100=2x-1=1/100f(x-1)=lgx-1=lg1/100=-2(R+,×)(R,+)x。y。x×y。。f(x)。f(y)。f(x)+f(y)f(是双射)幺元1。。幺元0100。100-1。。f(100)=2。f(100-1)=-2计算尺的原理：计算尺的设计：就是用对数将乘法运算变成加法运算。339012012活动尺固定尺此尺按对数刻度表1代数系统01010111∨abababbb表2代数系统这两个代数系统表面看上去似乎不同，但是它们实际上是相同的。它们仅仅是元素与运算符的表现形式不同，而它们的实质是一样的。我们将这样的代数系统叫同构。例如：设有两个代数（{0，1}，∨），（{a,b},）其运算表如下：注意：代数系统(X,)和(Y,)同构的必要条件：1.运算(X,)和(Y,)是同类型的。2.X和Y的基数相同，即#X=#Y3.存在双射f:XY，且满足关系式：g(x1x2)=g(x1)g(x2)因为并不是所有双射都满足同态关系式。例如（N4,+）、（X,）中,g:N4X如右图所示，f(1+1)=f(2)=Lf(1)f(1)=AA=S∴f(1+1)≠f(1)f(1)所以g不是同构映射。实际上同构映射必须是幺元对幺元，零元对零元、….我们后边要介绍它的定义。SLN4X0123gRAg是双射二.同构的定义定义：设（X,）,（Y,）是两个同类型的代数系统，和都是二元运算，如果存在一个一一对应的映射g:XY,使得对任何x1,x2∈X，有g(x1x2)=g(x1)g(x2)--（此式叫同态关系式）则称g是从（X,）到（Y,）的同构映射，简称这两个代数系统同构。记作X≌Y。即如果g是双射且满足同态关系式(保持运算)，则g是同构映射如果g是(X,）到(X,）的同构,称之g为自同构。例1:证明：(R+,×)与(R,+)同构，[证]只要证明它们之间存在一个同构映射即可。对(R+,×)与(R,+)有一个映射h：R+R，h(x)=lnx.（1）h是双射:h(x)=lnx.显然（２）h保持运算封闭:h(x×y)=ln(x×y)=lnx+lny=h(x)+h(y)例2：设有两个代数（{0，1}，∨）,（{a,b},）其运算表如下：表1代数系统表2代数系统01010111∨abababbb证明它们是同构的。【证】这两个代数系统之间存在一个一一映射令g:{0,1}{a,b}，g(0)=a，g(1)=b，此映射是一一对应，而且显然对于任何x1，x2有g(x1∨x2)=g(x1)g(x2)所以两个代数系统是同构的。下面再看一个例子：设I是整数集合，R是I上模k(k是正整数)同余关系，因R是I上等价关系，所以得商集I/R，将I/R记作Nk,即：Nk={[0],[1],[2],…,[k-1]}在Nk上定义运算+k和×k，我们分别称之为以k为模的加法和乘法。定义为：任取[x],[y]∈Nk，[x]+k[y]=[(x+y)(modk)][x]×k[y]=[(x×y)(modk)]例如k=4N4={[0],[1],[2],[3]}[2]+4[3]=[(2+3)(mod4)]=[1][2]×4[3]=[(2×3)(mod4)]=[2]下面为了方便，我们将N4={[0],[1],[2],[3]}简记成：N4={0,1,2,3}任何x,y∈N4,x+4y=(x+y)(mod4)补例3证明(N4,+4)与(X,)同构。构造映射f:N4X如下：下面验证f是同构映射。(1)f是双射(2)f保持运算f(1+42)=f(3)=Lf(1)f(2)=RA=L∴f(1+42)=f(1)f(2)f(2+43)=f(1)=Rf(2)f(3)=AL=R∴f(2+43)=f(2)f(3)012300123112302230133012+4SRALSSRALRRALSAALSRLLSRASLN4X0123fRAf是双射f(2+42)=f(0)=Sf(2)f(2)=AA=S∴f(2+42)=f(2)f(2)f(1+43)=f(0)=Sf(1)f(3)=RL=S∴f(1+43)=f(1)f(3)其余类似可验证∴N4≌X下面看看同构的两个代数系统运算表的相同性：将(N4,+4)运算表中的各个元素分别用它的映像代替得到右表，看出此表与(X,)运算的相同性。012300123112302230133012+4SRALSSRALRRALSAALSRLLSRASLN4X0123fRAf是双射SRALSSRALRRALSAALSRLLSRA+4三.代数系统同构的性质任何代数系统(X,),(Y,),X≌Y,f:XY是同构映射,任取x1,x2∈X，有f(x1x2)=f(x1)f(x2)。1.(保持结合律)如果运算可结合，则运算也可结合。证明：任取y1,y2,y3∈Y，因f:XY是满射，所以，x1,x2,x3∈X,使得y1=f(x1),y2=f(x2),y3=f(x3)，已知：x1(x2x3)=(x1x2)x3，欲证：y1(y2y3)＝(y1y2)y3y1(y2y3)=f(x1)(f(x2)f(x3))=f(x1)f(x2x3)=f(x1(x2x3))=f((x1x2)x3)(因可结合)=f(x1x2)f(x3)=(f(x1)f(x2))f(x3)=(y1y2)y3∴也可结合。2.(保持交换律)如果运算可交换，则运算也可交换。证明的方法与1.类似。3.(保持幺元存在性)如果运算有幺元e，则运算也有幺元e，且f(e)=e。即已知（X，）有幺元e，证f(e)是(Y,)的幺元证明：任取y∈Y因f:XY是满射，x∈X,使得y=f(x)yf(e)=f(x)f(e)=f(xe)=f(x)=yf(e)y=f(e)f(x)=f(ex)=f(x)=y所以f(e)是相对的幺元。即f(e)=e。4.(保持零元存在性)如果运算有零元θ，则运算也有零元θ，且f(θ)=θ。即已知（X，）有零元θ，证f(θ)=θ是(Y,)的零元f(θ)证明：任取y∈Y因f:XY是满射，x∈X,使得y=f(x)yf(θ)=f(x)f(θ)=f(xθ)=f(θ)f(θ)y=f(θ)f(x)=f(θx)=f(θ)所以f(θ)是相对的零元。即f(θ)=θ5.(保持逆元存在性)如果（X,）中每个x∈X可逆，即x-1∈X,则（Y,）中每个y∈Y也可逆，即y-1∈Y。且如果y=f(x)，则y-1=(f(x))-1=f(x-1)。(映像的逆元=逆元的映像)证明：任取y∈Y因f:XY是满射，x∈X,使得y=f(x)(只要证出yf(x-1)=e和f(x-1)y=e即可)设运算的幺元e，运算的幺元e。∴f(e)=e。yf(x-1)=f(x)f(x-1)=f(xx-1)=f(e)=ef(x-1)y=f(x-1)f(x)=f(x-1x)=f(e)=e所以y-1=(f(x))-1=f(x-1)。下面是含有两个运算的代数系统的同构的性质的保持问题。定义：令(X,+,×）和（Y,,）是含有两个运算的代数系统，其中+、×、、都是二元运算，如果存在双射f:XY,使得对任何x1,x2∈X，满足f(x1+x2)=f(x1)f(x2)。(注意：+与对应)f(x1×x2)=f(x1)f(x2)。(注意：×与对应)则称这两个代数系统同构。6.(保持分配律)如果运算+对×可分配,则对也可分配。证明：任取y1,y2,y3∈Y因f:XY是满射,x1,x2,x3∈X,使得y1=f(x1),y2=f(x2),y3=f(x3)y1(y2y3)=f(x1)(f(x2)f(x3))=f(x1)f(x2×x3)=f(x1+(x2×x3))=f((x1+x2)×(x1+x3))(因+对×可分配)=f(x1+x2)f(x1+x3)=(f(x1)f(x2))(f(x1)f(x3))=(y1y2)(y1y3)所以对也可分配。四.代数系统间的同构关系≌是等价关系1.≌有自反性：任何代数系统（X,）,有X≌X。证明：因为有双射IX:XX,任取x1,x2∈X，有IX(x1x2)=x1x2=IX(x1)IX(x2)所以X≌X。2.≌有对称性：任何代数系统(X,)(Y,),如果有X≌Y则必有Y≌X。证明：因有X≌Y，∴有双射f:XY,任取x1,x2∈X，有f(x1x2)=f(x1)f(x2)因f是双射，∴有f-1:YX,任取y1,y2∈Y因f:XY是满射，x1,x2∈X,使得y1=f(x1),y2=f(x2)∴x1=f-1(y1),x2=f-1(y2)f-1(y1y2)=f-1(f(x1)f(x2))=f-1(f(x1x2))=f-1f(x1x2)=IX(x1x2)=x1x2=f-1(y1)f-1(y2)∴Y≌X3.≌有传递性：任何代数系统(X,)(Y,),(Z,)如果有X≌Y和Y≌Z，则必有X≌Z。证明：因有X≌Y，∴有双射f:XY,任取x1,x2∈X，有f(x1x2)=f(x1)f(x2)因有Y≌Z，∴有双射g:YZ,任取y1,y2∈Y，有g(y1y2)=g(y1)g(y2)∴有双射h=gf:XZ,任取x1,x2∈X，h(x1x2)=gf(x1x2)=g(f(x1x2))=g(f(x1)f(x2))=g(f(x1))g(f(x2))=gf(x1)gf(x2)=h(x1)h(x2)∴X≌Z∴≌是个等价关系。五.同态的定义设（X,）,（Y,）是两个代数系统，和都是二元运算，如果存在映射f:XY,使得对任何x1,x2∈X，有f(x1x2)=f(x1)f(x2)--（此式叫同态关系式）则称f是从（X,）到（Y,）的同态映射，简称这两个代数系统同态。记作X∽Y。即：如果f是映射且满足同态关系式或保持运算，则称f是同态映射并称（f(X),）为(X,）的同态像。如果f是满射的，称此同态f是满同态。如果f是单射的，称此同态f是单一同态。f是(X,）到(X,）的同态(同构),称之为自同态(自同构)。六.同态性质的保持定理：代数系统(X,）,(Y,),X∽Y,f:XY是同态映射,如果(X,）中满足交换、结合、有幺元、有零元、每个元素可逆,则(f(X),)中也满足上述性质。证明的方法与前一样，所不同的是，不是在Y中取元素，而是在值域f(X)中取元素。因为f不一定是满射的。另外，由于同态关系∽不满足对称性，所以同态性质的保持只是单向的。即Y中的性质，X中不一定有。例1设,现定义函数（1）（2）（3）试问，以上这些函数是否到的同构或到的自同构？;,;21RVRV||)(,:11xxfRRf||)(,:22xxfRRfxxfRRf2)(,:331V2V2V2VRRf:1Ryx,解（1）关于，对任意所以是由到的同态，)()(||||||)(111yfxfyxyxyxf