《離散數(shù)學(xué)》第五章8-9節(jié)

同態(tài)與同構(gòu)：

兩個(gè)代數(shù)系統(tǒng)之間的聯(lián)系，保持原有的形態(tài)和性質(zhì)（本質(zhì)相同，形式不同）1整理ppt1、同態(tài)、同態(tài)象、滿同態(tài)、單一同態(tài)、同構(gòu)定義5-8.1設(shè)<A,★>和<B,*>是兩個(gè)代數(shù)系統(tǒng)，★和*分別是A，B上的二元（n元）運(yùn)算，設(shè)f是A到B的一個(gè)映射，使得對(duì)任意的a1,a2∈A，有f(a1★a2)=f(a1)*f(a2)則稱f為由<A,★>到<B，*>的一個(gè)同態(tài)映射，(簡(jiǎn)稱同態(tài))，稱<A,★>同態(tài)于<B，*>（或稱為f運(yùn)載★到*），記為A～B。把<f(A),*>稱為<A，★>的一個(gè)同態(tài)象。5-8同態(tài)與同構(gòu)2整理ppt例給定代數(shù)系統(tǒng)<R,+>和<R,×>，設(shè)函數(shù)f:R→R，f(x)=2x，證明f是一個(gè)從<R,+>到<R,×>的同態(tài)對(duì)于y,z∈R，應(yīng)有f(y+z)=2y+z=2y×2z=f(y)×f(z)所以函數(shù)f:R→R是一個(gè)從<R,+>到<R,×>的同態(tài)。3整理pptfabca★cb★cAB···f(A)f(a)=f(b)f(c)f(a)*f(c)=f(b)*f(c)

f(A)={x|x=f(a),a∈A}?B由一個(gè)代數(shù)系統(tǒng)到另一個(gè)代數(shù)系統(tǒng)可能存在著多個(gè)同態(tài)。4整理ppt例<I,?>，I是整數(shù)集，?是普通乘法運(yùn)算，其運(yùn)算結(jié)果的特征用另一個(gè)代數(shù)系統(tǒng)<B,⊙>來(lái)表示，B={正、負(fù)、零}，⊙是定義在B上的二元運(yùn)算，正n>0f（n）=負(fù)n<0零n=0⊙正負(fù)零正負(fù)零正負(fù)零負(fù)正零零零零對(duì)于任意的a，b∈I，有f(a?b)=f(a)⊙f(b)，映射f是由<I,?>到<B,⊙>的一個(gè)同態(tài)。即<B,⊙>描述了<I,?>中運(yùn)算結(jié)果的基本特征。5整理ppt定義5-8.2f：<A,★>到<B,*>的一個(gè)同態(tài)，如果f是從A到B的一個(gè)滿射，則f是滿同態(tài)；f是從A到B的一個(gè)入射，則f是稱為單一同態(tài)；f是從A到B的一個(gè)雙射，則f是同構(gòu)映射，并稱<A,★>和<B,*>是同構(gòu)的。記為<A,★>≌<B,*>，簡(jiǎn)記作A≌B如：1.設(shè)f：R→R，定義為對(duì)任意x∈R，f(x)=2x2．設(shè)f:N→Nk,定義為對(duì)任意x∈N,f(x)=x（modk）3．設(shè)H={x|x=dn,d是某一個(gè)正整數(shù)，n∈I},定義映射f：I→H為對(duì)任意n∈I,f(n)=dn6整理ppt例1設(shè)A={a,b,c,d}，B={1,2,3,4}，在A，B上定義的二元運(yùn)算如下所示，證明<A,★>和<B,*>同構(gòu)?！颽bcdabcdabcdbaacbddcabcd*123412341234211324431234證明：設(shè)f(a)=1，f(b)=2，f(c)=3，f(d)=4，由表可得f是<A,★>到<B,*>的同態(tài)，f是一個(gè)雙射函數(shù)，A≌B。如果g(a)=4，g(b)=3，g(c)=2，g(d)=1，g也是由<A,*>到<B,+>的一個(gè)同構(gòu)。7整理ppt當(dāng)兩個(gè)代數(shù)系統(tǒng)是同構(gòu)的，它們之間的映射可以是不唯一的。同構(gòu)的兩個(gè)代數(shù)系統(tǒng)，可看成是本質(zhì)相同但形式不同的代數(shù)系統(tǒng)。如果代數(shù)系統(tǒng)U，V是同構(gòu)的，則從V，U也必定存在一個(gè)同構(gòu)的映射f-1，故U，V是互為同構(gòu)的。8整理ppt2、同態(tài)、自同構(gòu)及相關(guān)性質(zhì)定義5-8.3設(shè)<A,★>是一個(gè)代數(shù)系統(tǒng)，如果f是由<A，★>到<A，★>的同態(tài)，則稱f為自同態(tài)。如果g是由<A，★>到<A，★>的同構(gòu)，則稱g為自同構(gòu)。9整理ppt證明：(1)任何代數(shù)系統(tǒng)<A,*>都可以通過(guò)恒等映射與它自身同構(gòu)，所以同構(gòu)關(guān)系具有自反性。(2)若f是<A,*>到<B,

>的同構(gòu)映射且<A,*>≌<B,

>，則f的逆f-1是<B,

>到<A,*>的同構(gòu)映射且<B,

>≌<A,*>，所以同構(gòu)關(guān)系具有對(duì)稱性。(3)設(shè)f是<A,*>到<B,

>的同構(gòu)映射，g是<B,

>到<C,★>的同構(gòu)映射，則g?f是<A,*>到<C,★>的同構(gòu)映射，所以同構(gòu)關(guān)系具有傳遞性。由以上(1)，(2)，(3)知同構(gòu)關(guān)系是等價(jià)關(guān)系。定理5-8.1設(shè)G是代數(shù)系統(tǒng)的集合，則G中代數(shù)系統(tǒng)之間的同構(gòu)關(guān)系是等價(jià)關(guān)系。10整理ppt定理5-8.2設(shè)f是從代數(shù)系統(tǒng)<A,★>到<B,*>的同態(tài)映射。(a)如果<A,★>是半群，那么在f作用下，同態(tài)象<f(A),*>也是半群。(b)如果<A,★>是獨(dú)異點(diǎn)，那么在f作用下，同態(tài)象<f(A),*>也是獨(dú)異點(diǎn)。(c)如果<A,★>是群，那么在f作用下，同態(tài)象<f(A),*>也是群。11整理ppt證明：(a)若f是由<A,★>到<B,*>的一個(gè)同態(tài)映射，則f(A)

B(1)封閉性：

a,b

f(A)，必有x,y

A使得f(x)=a，f(y)=b，在A中必有z=x★y，a*b=f(x)*f(y)=f(x★y)=f(z)f(A)。(2)可結(jié)合性：

a,b,c

f(A)，必有x,y,z

A使得f(x)=a，f(y)=b，f(z)=c★在A上是可結(jié)合的，所以a*(b*c)=f(x)*(f(y)*f(z)=f(x)*f(y★z)=f(x★(y★z))=f((x★y)★z)=f(x★y)*f(z)=(f(x)*f(y))*f(z)=(a*b)*c。<A,★>是半群，在f作用下，同態(tài)象<f(A),*>也是半群12整理ppt(b)設(shè)<A,★>是獨(dú)異點(diǎn)，e是A中的幺元，考察f(e)：

a

f(A)，必有xA使得f(x)=a，所以a*f(e)=f(x)*f(e)=f(x★e)=f(x)=a=f(e★x)=f(e)*f(x)=f(e)*a。那么f(e)是f(A)中的幺元。所以<f(A),*>是獨(dú)異點(diǎn)。<A,★>是獨(dú)異點(diǎn)，在f作用下，同態(tài)象<f(A),*>也是獨(dú)異點(diǎn)13整理ppt(c)設(shè)<A,★>是群，

a

f(A)，必有xA使得f(x)=a，因?yàn)?lt;A,★>是群，所以x有逆元x-1，且f(x-1)

f(A)，f(x)*f(x-1)=f(x★x-1)=f(e)=f(x-1★x)=f(x-1)*f(x)所以f(x-1)是f(x)的逆元。即f(x-1)=f(x)-1所以<f(A),*>是群。<A,★>是群，在f作用下，同態(tài)象<f(A),*>也是群14整理ppt3.同態(tài)核及其相關(guān)性質(zhì)定義5-8.4設(shè)f是由群<G,★>到群<G’,*>的同態(tài)映射，e’是G’中的幺元，記Ker(f)={x|xG且f(x)=e’}，稱Ker(f)為同態(tài)映射f的核，簡(jiǎn)稱f的同態(tài)核。15整理ppt定理5-8.3設(shè)f是由群<G,★>到群<G’,*>的同態(tài)映射，則f的同態(tài)核K是G的子群。證明：(1)設(shè)k1，k2K，則f(k1★k2)=f(k1)*f(k2)=e’*e’=e’所以k1★k2K，封閉性滿足；(2)K是G的子集，<G,★>為群，可結(jié)合性保持；(3)由定理5-8.2得e’=f(e)，eK，所以<K,★>中存在幺元；(4)對(duì)任意的kK，<G,★>是群，由定理2知f(k-1)=f(k)-1=e’-1=e’所以k-1K，即每個(gè)元素都存在逆元；所以f的同態(tài)核K是G的子群。16整理ppt定義5-8.5設(shè)<A,★>是代數(shù)系統(tǒng)，并設(shè)R是A上的等價(jià)關(guān)系，如果當(dāng)<a1,a2>，<b1,b2>∈R時(shí)，蘊(yùn)涵著<a1★b1,a2★b2>∈R，則稱R為A上關(guān)于★的同余關(guān)系。由這個(gè)同余關(guān)系將A劃分成的等價(jià)類就稱為同余類。4.同余關(guān)系及其相關(guān)性質(zhì)17整理ppt例設(shè)代數(shù)系統(tǒng)<A,*>，其中運(yùn)算*定義如下：對(duì)任意的x,yA，有x*y=x，E是A上任意等價(jià)關(guān)系。E是A上的同余關(guān)系嗎？設(shè)a1,a2,b1,b2∈A，且<a1,a2>，<b1,b2>∈E，因?yàn)閍1*b1=a1，a2*b2=a2，所以<a1*b1,a2*b2>=<a1,a2>∈E所以E是A上的同余關(guān)系。18整理ppt定義5-9.1設(shè)<A,★,*>是一個(gè)代數(shù)系統(tǒng)，如果滿足：(1)<A,★>是阿貝爾群，(2)<A,*>半群，(3)運(yùn)算*對(duì)于運(yùn)算★是可分配的。則稱<A,★,*>是環(huán)。例如：<I,+,×>，<R,+,×>，<Q,+,×>都是環(huán)。5-9環(huán)與域一.環(huán)、特殊環(huán)、整環(huán)例<R,+,×>，<I,+,×>，其中×和+有何聯(lián)系?其中★稱作加法，*稱作乘法，但并不是實(shí)際意義上的加乘運(yùn)算，只是和它們的一些性質(zhì)相同。19整理ppt定義5-9.2設(shè)<A,+,·>是環(huán)，如果<A,·>是可交換的，則稱<A,+,·>是交換環(huán)。如果<A,·>含有幺元，則稱<A,+,·>是含幺環(huán)。例如：<Z,+,·>,<Q,+,·>既是交換環(huán)也是含幺環(huán)。20整理ppt在環(huán)<A,+,·>中，根據(jù)<A,·>的特點(diǎn)可定義一些常見(jiàn)的特殊環(huán)。<A,+,·><A,·>

可交換獨(dú)異點(diǎn)

可交換環(huán)含幺交換環(huán)含幺環(huán)21整理ppt定義

設(shè)<R,+,·>是一個(gè)環(huán)，對(duì)于非零元素a,b∈R，如果a·b=θ，其中θ是環(huán)的零元，則稱<R,+,·>是個(gè)含零因子環(huán)。否則為無(wú)零因子環(huán)。例如：<Z,+,·>,<Q,+,·>都是無(wú)零因子環(huán)。22整理ppt例給定環(huán)<N4,+4,×4>+4[0][1][2][3][0][1][2][3][0][1][2][3][1][2][3][0][2][3][0][1][3][0][1][2]×4[0][1][2][3][0][1][2][3][0][0][0][0][0][1][2][3][0][2][0][2][0][3][2][1]23整理ppt定義5-9.3設(shè)<A,+,·>是一個(gè)代數(shù)系統(tǒng)，如果滿足：(1)<A,+>是阿貝爾群，(2)<A,·>是可交換獨(dú)異點(diǎn)，且無(wú)零因子，即對(duì)任意的a,b∈A，a≠θ，b≠θ，必有a·b≠θ(3)運(yùn)算·對(duì)于運(yùn)算+是可分配的。則稱<A,+,·>是整環(huán)。24整理ppt例說(shuō)明<I,+,·>是一個(gè)整環(huán)。證明：(1)<I,+>是阿貝爾群：可交換性(2)<I,·>：可交換獨(dú)異點(diǎn)，且無(wú)零因子(3)·對(duì)+可分配<I,+,·>是整環(huán)。又如：<N6,+6,×6>不是一個(gè)整環(huán)，因?yàn)閇2]×6[3]=[0]而<N7,+7,×7>是一個(gè)整環(huán)25整理ppt二.域、環(huán)與域的關(guān)系定義5-9.4設(shè)<A,+,·>是一個(gè)代數(shù)系統(tǒng)，如果滿足：(1)<A