离散数学 代数系统

第6章代数系统第一节代数系统的一般概念第二节同态和同构第三节同余关系第四节商代数和积代数第五节典型的代数系统第一节代数系统的一般概念1、代数系统的定义2、代数系统满足的条件3、子代数系统4、同类型的代数系统1、代数系统的定义X:非空集合Ω:X上运算的非空集合V=X,Ω:代数系统{ω1，ω2，…，ωn}X,ω1，ω2，…，ωn有限代数系统|X|为V的阶解释：一个非空集合X,连同若干个定义在该集合上的运算ω1，ω2，…，ωn所组成的系统称为代数系统。2、代数系统满足的条件（1）非空集合X；（2）有一些建立在集合X上的运算；（3）这些运算在集合X上是封闭的。代数系统举例I+，+ρ(S)，∪，∩是是代数系统举例N4={0，1，2，3},i+4j=(i+j)(mod4)问：N4，+4是代数系统吗？[phone]验证+4在N4集合上是否满足封闭性0123123023013012由运算表可知运算满足封闭性N4，+4是代数系统代数系统举例设A={1，2，3，4，6，12}A上的运算*定义为：a*b=|a-b|（1）写出二元运算的运算表；（2）A,*能构成代数系统吗？解答由运算表可知*运算在集合A上不封闭所以：A,*不能构成代数系统*1234612123461201235111012410210139321028543206111098603、子代数系统V=S，Ω:代数系统S′≠φS′S每一个运算ω∈Ω在S′上均封闭V′=S′，Ω是一个代数系统V′为V的子代数系统子系统或子代数子代数系统举例I,+是一个代数系统设E：偶数集合则：E,+是I,+的子代数系统。4、同类型的代数系统V1=S1，Ω1:代数系统V2=S2，Ω2:代数系统存在一个双射函数f:Ω1→Ω2每一个ω∈Ω1和f(ω)∈Ω2具有相同的阶同元运算V1和V2是同类型的代数系统类型映射ωf同类型的代数系统举例V1=Nm,+m,m和V2=R,+,是同类型的代数系统吗？其中：i+mj=(i+j)(modm)imj=(ij)(modm)解答双射函数（类型映射）f:f(+m)=+,f(m)=且+m和+、m和均为二元运算所以：V1=Nm,+m,m和V2=R,+,是同类型的代数系统。同类型的代数系统举例V1=Nm,+m和V2=I,+,是同类型的代数系统吗？V1=I,+，-和V2=R,+,是同类型的代数系统吗？其中：“-”为取负运算。（不是）（不是）不存在双射函数不是同元运算不是同元运算第二节同态和同构一、同态二、同构一、同态1、同态的定义2、同态的特点3、满同态、单一同态、自同态1、同态的定义A，∘B，*同类型的代数系统A上的二元运算B上的二元运算存在一个映射g：A→B对任意的a,b∈Ag(a∘b)=g(a)g(b)*运算的象象的运算从A，∘到B，*的一个同态映射A，∘与B，*同态同态的一般定义(略)设V1=S1，Ω1，V2=S2，Ω2是两个同类型的代数系统；f:Ω1→Ω2为类型映射，如果存在函数g：S1→S2，使得对任意的n元运算ω∈Ω1及任意的元素a1,a2,…,an∈S1均有：g(ω(a1,a2,…,an))=ωf(g(a1),g(a2),…g(an))则称V1与V2同态。解释两个代数系统同态：（1）两个代数系统同类型；（2）运算的象=象的运算2、同态的特点（1）g映射可以是内射、单射、满射、双射；（2）g(S1)S2像点集单一同态满同态同构同态示意图S1x1x2x3S2gg(x1)=y1g(x2)=y1g(x3)=y3y1y3g(x1∘x3)=g(x1)*g(x3)=x1∘x3y1*y3y1*y3g(x2∘x3)=g(x2)*g(x3)=y1*y3x2∘x3g(S1)同态举例证明：I，×和B，*是同态的，其中：B={正，负，零}，*运算的运算表如下：*正负零正正负零负负正零零零零零解答(1)显然I，×和B，*是同类型的；(2)g:I→B(3)验证运算的象=象的运算g(I)=i0i0i=0正负零(3)运算的象=象的运算①i0,j0时:g(i×j)=正，g(i)*g(j)=正*正=正②i0,j0时:g(i×j)=负，g(i)*g(j)=正*负=负③i0,j=0时:g(i×j)=零，g(i)*g(j)=正*零=零④i0,j0时:g(i×j)=负，g(i)*g(j)=负*正=负⑤i0,j0时:g(i×j)=正，g(i)*g(j)=负*负=正⑥i0,j=0时:g(i×j)=零，g(i)*g(j)=负*零=零⑦i=0,j0时:g(i×j)=零，g(i)*g(j)=零*正=零⑧i=0,j0时:g(i×j)=零，g(i)*g(j)=零*负=零⑨i=0,j=0时:g(i×j)=零，g(i)*g(j)=零*零=零同态举例其中：g:N→{0,1}，且定义为：g(n)=0(nN)证明：N，×{0，1}，×同态证明（1）显然N,×与{0,1},×同类型；（2）运算的象=象的运算对任意的m,nN运算的象=g(m×n)=0象的运算=g(m)×g(n)=0×0=0所以：N，×与{0，1}，×同态3、满同态、单一同态、自同态(1)如果g为满射函数，则称g为关于类型映射f的满同态；(2)如果g为单射函数，则称g为关于类型映射f的单一同态；(3)若V1=V2，且类型映射f为恒等函数，则称g为关于类型映射f的自同态。自同态举例其中：g:I→I，且定义为：g(n)=3n(nI)证明：I，+I，+自同态证明(1)显然I，+与I，+同类型,且f(+)=+；(2)运算的象=象的运算对任意的m,nN运算的象=g(m+n)=3(m+n)=3m+3n=g(m)+g(n)=象的运算所以：I，+与I，+同态,且是自同态。满同态举例证明：U=I,+,V=Nm,+m,m满同态g:I→Nm对于所有的iI,有：g(i)=(i)(modm)证明类型映射f定义为：f(+)=+m,f()=m(1)显然U=I,+,和V=Nm,+m,m同类型(2)运算的象=象的运算对任意的x,yI:g(x+y)=g(x)+mg(y)g(xy)=g(x)mg(y)证明:g(x+y)=g(x)+mg(y)g(x+y)=(x+y)(modm)=((x)(modm)+(y)(modm))(modm)=(x)(modm)+m(y)(modm)=g(x)+mg(y)证明:g(xy)=g(x)mg(y)g(xy)=(xy)(modm)=((x)(modm)(y)(modm))(modm)=(x)(modm)m(y)(modm)=g(x)mg(y)所以：U=I,+,和V=Nm,+m,m同态证明g是满射函数对于任意的xNm,均有xI，使得：g(x)=(x)(modm)=x所以：U=I,+,和V=Nm,+m,m是满同态满同态的特点满同态对性质的保持是单方向的，即：X,∘与Y,*满同态X,∘的性质，Y,*均保持交换律结合律分配律吸收律幺元零元逆元等幂元交换律、结合律设X,∘与Y,*满同态，则：（1）若∘运算可交换，则*运算也可交换；（2）若∘运算可结合，则*运算也可结合；分配律V1=S1，Ω1V2=S2，Ω2满同态f:类型映射*Ω1∆Ω1*对∆可分配f(*)对f(∆)也可分配Ω2幺元、零元、逆元设X,∘与Y,*满同态，则：(1)若∘有幺元e，则*有幺元g(e);(2)若∘有零元，则*有零元g();(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1)满同态的特点举例I,+,和N3,+3,3满同态，则：(1)＋可交换，f(＋)=+3也可交换；(2)可交换，f()=3也可交换；(3)＋可结合，则f(+)＝+3也可结合；(4)可结合，则f()＝3也可结合；满同态举例（续）(5)对“＋”存在e=0,则:对“+3”存在e=g(0)=0;(6)对“”存在e=1,则:对“3”存在e=g(1)=1;(7)对“”存在零元=0,则:对“3”存在零元=g(0)=0;(8)对“＋”，8的逆元是-8,则:对“+3”g(8)=2g(-8)=g(-9+1)=(-9+1)(mod3)=1(mod3)=1满同态举例（续）2+31=(2+1)(mod3)=0=e2和1互为逆元单一同态举例证明：R，＋R，单一同态实数集合g:R→R对于xRg(x)=2x证明(1)显然R,+和R,同类型(2)运算的象=象的运算对于任意的x,yR，有：g(x+y)=2x+y=2x2y=g(x)g(y)(3)g映射是单射函数y=2x定理V1=G1，Ω1V2=G2，Ω2g为同态映射V3=g[G1]，Ω2为V2=G2，Ω2的子系统象点集V1的同态象点推论X,∘Y,*g为同态映射X,∘的性质X,∘的同态象点g(X),*均保持二、同构1、同构的定义2、同构的特点3、自同构1、同构的定义A，∘B，*同类型的代数系统A上的二元运算B上的二元运算存在一个双射映射g：A→B对任意的a,b∈Ag(a∘b)=g(a)g(b)*运算的象象的运算从A，∘到B，*的一个同构映射A，∘与B，*同构同构的一般定义V1=G1，Ω1V2=G2，Ω2同类型的代数系统f:Ω1→Ω2类型映射存在一个双射映射g：G1→G2对任意的n元运算ω∈Ω1任意的元素a1,a2,…,an∈G1ω(a1,a2,…,an)g()=g(a1),g(a2),…,g(an)ωf()V1与V2同构同构满足的条件（1）同类型（2）g为双射函数（|S1|＝|S2|）（3）运算的象＝象的运算同构举例S={4,5,6},运算∘见表(a)P={1,2,3},运算*见表(b)则S,∘与P,*同构。∘456445454556456*123112121223123表(a)表(b)解答（1）显然S,∘与P,*同类型；（2）寻找双射函数g：S→P方法：特异元素对应特异元素在S,∘中e=6在P,*中e=3g(6)=3g(5)=2g(4)=1g(5)=1g(4)=2或者g1(4)=1,g1(5)=2,g1(6)=3g2(4)=2,g2(5)=1,g2(6)=3（3）运算的象＝象的运算①g1(4)=1,g1(5)=2,g1(6)=3例：g(4∘5)=g(5)=2g(4)*g(5)=1*2=2②g2(4)=2,g2(5)=1,g2(6)=3例：g(4∘6)=g(4)=2g(4)*g(6)=2*3=2g1、g2均为同构映射变换运算表的方法g1一致g21、2列交换1,2行交换一致同构举例S={a,b,c,d},运算∘见表(a)P={1,2,3,4},运算*见表(b)则S,∘与P,*同构。∘abcdadabdbdbcdcadccdabaa表(a)*123412224211423323141134表(b)解答（1）显然S,∘与P,*同类型；（2）寻找双射函数g：S→P由表(a)的第4行和表(b)的第1行可知：g(a)=2,g(b)=4在S,∘中c是等幂元在P,*中3是等幂元g(c)=3g(a)=2,g(b)=4,g(c)=3,g(d)=1变换运算表g1,2列交换2,4列交换1,2行交换2,4行交换一致2、同构的特点（1）g为双射函数；（2）g(X)=YS1x1x2S2gx1∘x2g(x1)*g(x1)g(x1)g(x2)同构对运算保持相同的性质设X,∘与Y,*同构，则：(1)若∘有幺元e,则*有幺元g(e),反之亦然；(2)若∘有零元,则*有零元g(),反之亦然；(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1),反之亦然；(4)若∘运算可交换,则*