第6章 代數(shù)系統(tǒng)基礎

第6章代數(shù)系統(tǒng)基礎第一節(jié) 代數(shù)系統(tǒng)的一般概念第二節(jié) 同態(tài)和同構第三節(jié) 同余關系第四節(jié) 商代數(shù)和積代數(shù)第一節(jié) 代數(shù)系統(tǒng)的一般概念1、代數(shù)系統(tǒng)的定義2、代數(shù)系統(tǒng)滿足的條件3、子代數(shù)系統(tǒng)4、同類型的代數(shù)系統(tǒng)1、代數(shù)系統(tǒng)的定義X:非空集合Ω:X上運算的非空集合V=<X,Ω>:代數(shù)系統(tǒng){ω1，ω2，…，ωn}有限代數(shù)系統(tǒng)|X|為V的階V=<

<X,ω1，ω2，…，ωn>2、代數(shù)系統(tǒng)滿足的條件（1）非空集合X；（2）有一些建立在集合X上的運算；（3）這些運算在集合X上是封閉的。代數(shù)系統(tǒng)舉例<I+，+><ρ(S)，∪，∩><{0,1}，+>是是否代數(shù)系統(tǒng)舉例N4={0，1，2，3},i+4j=(i+j)(mod4)問：<N4

，+4>是代數(shù)系統(tǒng)嗎？+401230123驗證+4在N4集合上是否滿足封閉性0123123023013012由運算表可知運算滿足封閉性<N4

，+4>是代數(shù)系統(tǒng)代數(shù)系統(tǒng)舉例設A={1，2，3，4，6，12}A上的運算*定義為：a*b=|a-b|（1）寫出二元運算的運算表；（2）<A,*>能構成代數(shù)系統(tǒng)嗎？解答由運算表可知*運算在集合A上不封閉所以：

<A,*>不能構成代數(shù)系統(tǒng)*123461212346120123511101241021013932102854320611109860a*b=|a-b|3、子代數(shù)系統(tǒng)V=<S，Ω>:代數(shù)系統(tǒng)S′≠φS′S每一個運算ω∈Ω對S′均封閉V′=<S′，Ω>是一個代數(shù)系統(tǒng)V′為V的子代數(shù)系統(tǒng)子系統(tǒng)或子代數(shù)子代數(shù)系統(tǒng)舉例<I,+>是一個代數(shù)系統(tǒng)設E：偶數(shù)集合則：<E,+>是<I,+>的子代數(shù)系統(tǒng)。4、同型的代數(shù)系統(tǒng)V1=<S1，Ω1>:代數(shù)系統(tǒng)V2=<S2，Ω2>:代數(shù)系統(tǒng)存在一個雙射函數(shù)f:Ω1→Ω2每一個ω∈Ω1和f(ω)∈Ω2,且具有相同的階V1和V2是同型的代數(shù)系統(tǒng)同類型的代數(shù)系統(tǒng)舉例V1=<Nm,+m,m>和V2=<R,+,>是同類型的代數(shù)系統(tǒng)嗎？其中：

i+mj=(i+j)(modm)imj=(ij)(modm)V1和V2是同型的代數(shù)系統(tǒng)第二節(jié)同態(tài)和同構(重點)一、同態(tài)二、同構一、同態(tài)1、同態(tài)的定義2、同態(tài)的舉例3、滿同態(tài)、單一同態(tài)、自同態(tài)1、同態(tài)的定義<A，°><B，*>是兩個同型的代數(shù)系統(tǒng)存在一個映射f：A→B對任意的a,b∈Af(a°b)=f(a)f(b)*運算的象象的運算從<A，°>到<B，*>的一個同態(tài)映射<A，°>與<B，*>同態(tài)2、同態(tài)舉例其中：g:N→{0,1}，且定義為：g(n)=0(nN)證明：<N，×><{0，1}，×>兩個代數(shù)系統(tǒng)同態(tài)證明（1）顯然<N,×>與<{0,1},×>同型的代數(shù)系統(tǒng)；（2）運算的象=象的運算對任意的m,nN，來驗證g(m×n)=g(m)×g(n)g(m×n)=0g(m)×g(n)=0×0=0

即：g(m×n)=g(m)×g(n)(說明g是個同態(tài)映射)所以：<N，×>與<{0，1}，×>同態(tài)3、滿同態(tài)、單一同態(tài)、自同態(tài)(1)如果f是滿射函數(shù)，則稱f為滿同態(tài)；(2)如果f為單射函數(shù)，則稱f為單一同態(tài)；(3)如果U=V，則稱f為自同態(tài)。U=<X，°>V=<Y，*>f是從U到V的同態(tài)映射自同態(tài)舉例其中：g:I→I，且定義為：g(n)=3n(nI)證明：<I，+><I，+>自同態(tài)證明(1)顯然<I，+>與<I，+>是同型的；(2)g(m+n)=g(m)+g(n)？對任意的m,nNg(m+n)=3(m+n)=3m+3n=g(m)+g(n)所以：<I，+>與<I，+>同態(tài),且是個自同態(tài)。g(n)=3n(nI)滿同態(tài)舉例U=<I,+,>，V=<Nm,+m,m>,其中：f:I→Nm對于所有的iI,有：f(i)=(i)(modm)Nm={0,1,2,…,m-1}i+mj=(i+j)(modm)im

j=(i

j)(modm)證明：f是個滿同態(tài)第一步：證明f是個同態(tài)(1)顯然U=<I,+,>和V=<Nm,+m,m>是同型的代數(shù)系統(tǒng)(2)證明f滿足同態(tài)的定義，即：

對任意的i,jI:f(i+j)=f(i)+mf(j)f(ij)=f(i)mf(j)證明:f(i+j)=f(i)+mf(j)f(i+j)=(i+j)(modm)=((i)(modm)+(j)(modm))(modm)=(i)(modm)+m(j)(modm)=f(i)+mf(j)i+mj=(i+j)(modm)f(i)=(i)(modm)證明:f(ij)=f(i)mf(j)f(ij)=(ij)(modm)=((i)(modm)(j)(modm))(modm)=(i)(modm)m(j)(modm)=f(i)mf(j)所以：U=<I,+,>和V=<Nm,+m,m>同態(tài)im

j=(i

j)(modm)f(i)=(i)(modm)第二步：證明f是滿射函數(shù)對于任意的iNm,均有iI，使得：f(i)=(i)(modm)=i

即:Rf=f(I)=Nm所以：U=<I,+,>和V=<Nm,+m,m>是滿同態(tài)f:I→Nm對于所有的iI,有：f(i)=(i)(modm)滿同態(tài)的特點滿同態(tài)保持運算性質單方向運載，即：

<X,°>與<Y,*>滿同態(tài)<X,°>的性質，<Y,*>均保持交換律結合律分配律吸收律幺元零元逆元等冪元定理設f是<X,°>到<Y,*>的滿同態(tài)，則：

(1)若°運算可交換，則*運算也可交換；

(2)若°運算可結合，則*運算也可結合；

(3)若°有幺元e，則*有幺元f(e);(4)若°有零元，則*有零元f();(5)若xX有逆元x-1,則f(x)Y有逆元f(x-1)單一同態(tài)舉例證明：<R，+><R，>g單一同態(tài)g:R→R，對于xR，g(x)=2x證明(1)顯然<R,+>和<R,>同型的代數(shù)系統(tǒng)(2)運算的象=象的運算對于任意的x,yR，有：g(x+y)=2x+y=2x2y=g(x)g(y)(3)來證g是單射函數(shù)

任取x1,x2R,x1≠x2,因為g(x1)=2x1,g(x2)=2x2所以g(x1)≠g(x2)，即g是單射函數(shù)由（1）~（3）知：g是個單一同態(tài)。g:R→R，

g(x)=2x推論<X,°><Y,*>g:X→Y為同態(tài)映射<X,°>的性質<X,°>的同態(tài)象點<g(X),*>均保持二、同構1、同構的定義2、同構的特點3、自同構1、同構的定義<A，°><B，*>同型的代數(shù)系統(tǒng)存在一個雙射映射g：A→B對任意的a,b∈Ag(a°b)=g(a)g(b)*則稱g是從<A，°>到<B，*>的一個同構映射同構舉例S={a,b,c,d},運算°見表(a)P={1,2,3,4},運算*見表(b)則<S,°>與<P,*>同構?！鉧bcdadabdbdbcdcadccdabaa表(a)*123412224211423323141134表(b)解答（1）顯然<S,°>與<P,*>同類型；（2）尋找雙射函數(shù)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行交換一致同構對運算保持相同的性質設U=<X,°>，V=<Y,*>同構，f是U到V的同構，則：(1)若°有幺元e

*有幺元法f(e)(2)若°有零元

*有零元f()(3)若xX有逆元x-1

f(x)Y有逆元f(x-1),反之亦然；(4)若°運算可交換*運算也可交換(5)若°運算可結合*運算也可結合3、自同構

設f是代數(shù)系統(tǒng)U=<X,°>到V=<Y,*>同構映射，若U=V，則稱f為自同構。第三節(jié) 同余關系

一、代換性質二、同余關系一、代換性質設V=<G,*>是個代數(shù)系統(tǒng)，R是

G上的等價關系。如果對任意的a1,b1,a2,b2

G，有：

a1Rb1∧a2Rb2(a1*a2)R(b1*b2)則稱等價關系R對運算*滿足代換性質。代換性質舉例

<I,+,>為代數(shù)系統(tǒng)，I中的等價關系R如下：對任意的a,bI，aRb

|a|=|b|或R={<a,b>|a,bI，|a|=|b|}問：等價關系R對于運算＋和是否具有代換性質？

解答（1）對加法運算“＋”：設a、-a、bI∵|a|=|-a|aR(-a)∵|b|=|b|bRb|a+b|≠|-a+b|(a+b)(-a+b)R關于“＋”不具有代換性質解答（續(xù)）（2）對乘法運算“×”：設i1、i2、j1、j2I若i1Ri2

則|i1|=|i2|若j1Rj2

則|j1|=|j2|∴|i1×j1|=|i2×j2|∴(i1×j1)R(i2×j2)即：對于乘法運算“×”來說，R具有代換性質。二、同余關系U=<G,*>:代數(shù)系統(tǒng)R:G上的等價關系如果R對于運算*具有代換性質,R為U上的同余關系。滿足代換性質的等價關系——同余關系，相應的等價類稱為同余類。同余關系舉例

給定代數(shù)系統(tǒng)U=<I,+>，定義I中的關系R如下：R={<x,y>|x,yI,x-y可被3整除}

或R={<x,y>|x,yI,x≡y(mod3)}

試證明R是U中的同余關系。證：先證明R是個等價關系(已證明過)，下面來證R滿足代換性質。證R滿足代換性質對任意的x1,x2,y1,y2I,如果x1Rx2且y1Ry2,

來證:(x1+y1)R(x2+y2)<證>

對任意的x1,x2,y1,y2I,如果x1Rx2且y1Ry2則x1-x2和

y1-y2都可被3整除，考察：

(x1+y1)-(x2+y2)=(x1-

x2)+(y1-

y2)上式的右邊可被3整除，所以左邊也可被3整除，故有：

(x1+y1)R(x2+y2)定理U=<X,°>V=<Y,*>f:同態(tài)映射Rf:X上的二元關系，對于任意的x1,x2Xx1Rfx2f(x1)=f(x2)Rf是U上的同余關系證明(1)Rf是等價關系：①自反性：對任意的xXf(x)=f(x)xRx②對稱性：x1Rfx2f(x1)=f(x2)f(x2)=f(x1)x2Rfx1③可傳遞性：x1Rfx2∧x2Rfx3f(x1)=f(x2)∧f(x2)=f(x3)f(x1)=f(x3)x1Rfx3證明（續(xù)）(2)Rf關于°具有代換性質：x1,x2,x3,x4X，如果x1Rfx2且x3Rfx4，來證：

(x1°x3)Rf(x2°x4)<證>

如果x1Rfx2

且x3Rfx4，則f(x1)=f(x2),f(x3)=f(x4)

考察：f(x1°x3)=f(x1)*f(x3)[因f是同態(tài)]=f(x2)*f(x4)=f(x2°x4)故：(x1°x3)Rf(x2°x4)第四節(jié) 商代數(shù)和積代數(shù)（略）一、商代數(shù)二、積代數(shù)一、商代數(shù)1、商代數(shù)的定義2、正則映射1、商代數(shù)的定義給定代數(shù)系統(tǒng)U=<X,°>，R

是U上的同余關系,試構造一個新的代數(shù)系統(tǒng)W=<X/R,?>,其中：則稱W為U關于R的商代數(shù)，簡稱商代數(shù)。(2)對于x1,x2X，[x1]R[x2]R=?[x1°x2]R(1)X/R={[x]R|xX}證明驗證<X/R,?>是一個代數(shù)系統(tǒng)(1)封閉性：任取[x1]R、[x2]RX/R[x1]R?[x2]R=[x1°x2]R

∵°對X封閉，x1°x2X,∴

[x1°x2]R

X/R∴?在X/R上封閉[x1]R?[x2]RX/R證明（續(xù)）(2)?是良定的y1[x1]R

y2[x2]R[x1]R?[x2]R=[y1]R?[y2]R[x1]R?[x2]R與等價類的代表元素x1和x2的選取無關y1[x1]R∧y2[x2]Rx1Ry1∧x2Ry2R為同余關系R關于°具有代換性質x1°x2

Ry1°y2[x1°x2]R=[y1°y2]R[x1]R?[x2]R=[y1]R?[y2]R由?定義商代數(shù)舉例給定代數(shù)系統(tǒng)U=<I,+>,R是I中的模3同余關系，即：R={<x,y>|x,yI,x≡y(mod3)},試構造代數(shù)系統(tǒng)U的商代數(shù)。解：I/R={[0]R,[1]R,[2]R}[i]?[j]=[(i+j)(mod3)]于是，構成了商代數(shù)U/R=<I/R,?>商代數(shù)能夠保持原始代數(shù)系統(tǒng)的若干性質(1)如果運算°可交換，則運算?也可交換(2)如果運算°可結合，則運算?也可結合(3)如果運算°有幺元e，則運算?也幺元[e]R……..…..2、正則映射(略)正則映射R:集合G上的等價關系函數(shù)g:G→G/Rg(x)=[x]R定理R:<X,°>上的同余關系g:X→X/R正則映射g是從<X,°>到商代數(shù)<X/R,?>的滿同態(tài)自然同態(tài)g(x)=[x]R證明(1)顯然<X,°>與<X/R,?>同類型；(2)證明：運算的象＝象的運算對任意的x,yXg(x°y)(正則映射定義)=[x°y]R(商代數(shù)定義)=[x]R?[y]R(正則映射定義)=g(x)?g(y)(3)g是滿射函數(shù)：任意的[x]RX/R，在X中至少有一個原象x與之對應，使得：g(x)=[x]R

∴g是滿射函數(shù)證明(續(xù))自然同態(tài)舉例

上例：求代數(shù)系統(tǒng)F=<A,*,⊕>到F的商代數(shù)為<A/R,*R,⊕R>的自然同態(tài)。求解自然同態(tài)g:g(x)=[x]Rg(a1)=g(a3)=[a1]Rg(a2)=g(a5)=[a2]Rg(a4)=[a4]RAa1a2a3a4a5A/R[a1]R[a2]R[a4]Rg定理f:從<X,°>到<Y,*>的同態(tài)映射Rf:<X,°>上的同余關系:xRfyf(x)=f(y)g:從<X,°>到<X/Rf,?>的自然同態(tài)存在從<X/Rf,?>到<f(X),*>的同構映射°g=f示意圖<X,°>x<X/Rf,?>[x]Rf商代數(shù)g<Y,*>f(x)f同態(tài)象點f(X)°g=f同構映射證明

設映射：X/Rf→f(X)，且([x]Rf)=f(x)

證明：(1)顯然同類型；(2)是單射函數(shù)；(3)是滿射函數(shù)；(4)運算的象＝象的運算證明：是單射函數(shù)單射即：象點相同證明原象相同對任意的x,yX若([x]Rf)=([y]Rf) (由的定義）f(x)=f(y) (由xRfyf(x)=f(y))xRfy[x]Rf=[y]Rf∴是單射函數(shù)

證明：是滿射函數(shù)∵f:X→f(X)的滿同態(tài)映射∴對任意的yf(X),必存在xX,使得f(x)=y又∵([x]Rf)＝f(x)=y即：對任意的yf(X)，必存在[x]RfX/Rf

使得：([x]Rf)＝y(tǒng)

∴是滿射函數(shù)。

證明：運算的象＝象的運算對任意的x,y