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

《离散数学 ch5.3同态与同构.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、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)=

2、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代数系统这两个代数系统表面看上去似乎不同

3、，但是它们实际上是相同的。它们仅仅是元素与运算符的表现形式不同，而它们的实质是一样的。我们将这样的代数系统叫同构。例如：设有两个代数（{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(

4、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是双

5、射且满足同态关系式(保持运算)，则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证明

6、它们是同构的。【证】这两个代数系统之间存在一个一一映射令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[

7、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(

8、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