離散數(shù)學第五章第五節(jié)

1、1,第5-5講 同態(tài)與同構(gòu),1. 例子2.同態(tài)3.同構(gòu)4.同態(tài)代數(shù)系統(tǒng)間的關系5.同態(tài)核6. 第5-5講 作業(yè),,,,,2,1、例子（1）,設?、?、?是帶正電荷的粒子，?、?是中性粒子，?是帶負電荷的粒子，下表描述了這些粒子間相互作用的結(jié)果：,令A={?,?,?,?,?,?}，則是一個代數(shù)系統(tǒng)。如果只考慮帶電粒子的正負特性，則這些粒子相互作用的結(jié)果可用另一個系統(tǒng)(B={1,0,-1})概括地描述。,,,,,3,1、例子（2

2、）,在代數(shù)系統(tǒng)和之間，可建立從A到B的映射f,,對任意a1,a2?A, 有 f(a1 ? a2)=f(a1)* f(a2)例如， f(? ? ?)=f(?)=0， f(?)*f(?)=1*(-1)= 0。所以， f(? ? ?)=f(?)*f(?)這時，稱f為代數(shù)系統(tǒng)到的一個同態(tài)。,,,,,4,1、例子（3）,f(?)=f(?)=f(?)=1,f(?)=f(?)=0,f(?)=-1,

3、? ? ?= ? ; 1*(-1)=0 f(? ? ?)=f(?)= 0 =1*(-1)= f(?)*f(?),,,,,5,2、同態(tài),定義1 設和是兩個代數(shù)系統(tǒng)， ?和*分別是A和B上的二元運算。如果存在映射f:A?B,對任意a1,a2?A,有f(a1?a2)=f(a1)*f(a2),則稱f是到的一個同態(tài)映射，簡稱同態(tài)。并稱同態(tài)于，記作A?B；稱為的一個同態(tài)象。,,,,,6,3、同構(gòu),定義2 設f是到一個同態(tài)，如果f是

4、A到B的滿射(入射)f，則稱f是到滿同態(tài)(單一同態(tài))。如果f為雙射，則稱f為同構(gòu)映射，并稱與同構(gòu)，記作A?B。,例1 設R是實數(shù)集，R+為正實數(shù)集合，說明代數(shù)系統(tǒng)與是同構(gòu)的。,解：為說明與是同構(gòu)的，必須建立R+ 到R的雙射f,并且對任意x1,x2?R+,有 f(x1?x2)=f(x1)+f(x2) 可令f:R+?R,f(x)=lnx,則f是R+ 到R的雙射，且 f(x1?x2)=ln（x1?x2）=lnx1+lnx2

5、 =f(x1)+f(x2)所以，代數(shù)系統(tǒng)與是同構(gòu)的。,,,,,7,4、同態(tài)(同構(gòu))代數(shù)系統(tǒng)間的關系(1),,,,,定理1 設f是代數(shù)系統(tǒng)到一個同態(tài)，如果是半群(獨異點、群)，則同態(tài)象也是半群（獨異點、群）。,證：以群為例進行證明。 因f是同態(tài)， 所以f(A)?B。對任意b1,b2?f(A),有a1,a2?A,使得 f(a1)=b1, f(a2)=b2, 那么 b1*b2 =f(a1)* f(a2)=f(a1

6、?a2)?f(A)。所以*運算在f(A)上封閉。 對任意b1,b2 ,b3 ?f(A),有a1,a2 ,a3 ?A,使得f(a1)=b1, f(a2)=b2, f(a3)=b3, 那么b1*(b2*b3)=f(a1)*(f(a2)*f(a3))=f(a1)*f(a2?a3)=f(a1?(a2?a3))=f((a1?a2)?a3)=f(a1?a2)*f(a3)=(f(a1)*f(a2))*f(a3)=(b1*b2)*b3所以*

7、運算在f(A)上可結(jié)合。,8,4、同態(tài)(同構(gòu))代數(shù)系統(tǒng)間的關系(2),,,,,定理1 設f是代數(shù)系統(tǒng)到一個同態(tài)，如果是群，則同態(tài)象也是群。,證(續(xù))：設e是的幺元，對任意b?f(A),有a?A,使得f(a)=b, 那么 b*f(e)=f(a)*f(e)=f(a?e)=f(a)=b。同時， b*f(e)=f(a?e)=f(e?a)=f(e)*f(a)=f(e)*b所以，f(e)是的幺元。 對任意b?f(A),有a?A,使得f

8、(a)=b, 因是群，則a有逆元a-1，且f(a-1)?f(A), 那么 f(a)*f(a-1)=f(a?a-1)=f(e)=f(a-1?a)=f(a-1)* f(a)因f(e)是的幺元，所以f(a-1)是f(a)的逆元。 所以任意b=f(a)?f(A)有逆元, 即f(a)-1=f(a-1) 。 由上述， 是群。,9,4、同態(tài)(同構(gòu))代數(shù)系統(tǒng)間的關系(3),,,,,定義3 設是代數(shù)系統(tǒng)， f是到的一個同態(tài)（同構(gòu)），則稱

9、f為自同態(tài)（自同構(gòu)）。,定理2：設G是代數(shù)系統(tǒng)的集合，則G中代數(shù)系統(tǒng)間的同構(gòu)關系是等價關系。,證：設任意?G，令f：A?A，f(a)=a，a?A。從而?，即代數(shù)系統(tǒng)間的同構(gòu)關系是自反的。設?，那么存在雙射f：A?B，故f-1：B?A也是雙射，所以?。因而該關系是對稱的。設?，?，則存在雙射f：A?B和 g：B?C,那么g?f：A?C也是雙射，所以?。因而該關系是傳遞的。,10,5、同態(tài)核,定義4 設f是群到群的一個同態(tài)，eH是的幺元

10、,令Ker(f)={x|x?G且f(x)=eH}。稱Ker(f)是同態(tài)映射f的核，簡稱同態(tài)核。,證明：對任意k1,k2?K,有 f(k1?k2)=f(k1)*f(k2)=eH*eH=eH所以k1?k2?K,所以?運算在K上封閉。進而可知?運算在K上可結(jié)合。 又因f是群到群的同態(tài)，根據(jù)定理1，eH=f(e)，這說明e?K，e也是K的幺元。 對任意k?K, f(k)=eH。 f(k-1)=(f(k))-1=(eH)

11、-1= eH所以k-1?K,即K中任意元素有逆元。從而K是G的子群。,定理3 設f是群到群的一個同態(tài)，則f的同態(tài)核K是G的子群。(是的子群),,,,,11,6、同余關系（1）,定義5 設是一個代數(shù)系統(tǒng)，R是A上的等價關系。如果,?R時，有?R，則稱R為A上關于運算*的同余關系。由該同余關系將A劃分成的等價類叫做同余類。,證：設,?R,那么可令： a-b=kn1, c-d=kn2, n1,n2?I所以， (a-b)+(

12、c-d)=k(n1+n2), n1+n2?I即 (a+c)-(b+d)=k(n1+n2)亦即 ?R按定義，R是I上關于運算+的同余關系。,例2 給定代數(shù)系統(tǒng)和I上的模K等價關系R，證明R是I上關于運算+的同余關系。,,,,,12,6、同余關系（2）,注：從同余關系的定義可知，同余關系首先是等價關系。同余關系與代數(shù)系統(tǒng)上的運算有關，所以等價關系不一定是同余關系。,證：,?R,但=?R 按定義，R不

13、是同余關系。,例3 給定代數(shù)系統(tǒng)，A={a,b,c,d},運算*定義如下表，說明A上的等價關系R={,,,,, ,,}，分析R是否為A上關于運算*的同余關系。,,,,,13,6、同余關系（3）,定理4 設是一個代數(shù)系統(tǒng)，R是A上的同余關系。B={A1,A2,…,Ar}是由R誘導的A一個劃分，那么必存在新的代數(shù)系統(tǒng)，它是的同態(tài)象。,證：在B上定義二元運算?：對任意Ai,Aj?B，任取a1?Ai, a2?Aj，如果a1*a2?Ak，則定義A

14、i?Aj=Ak。因R是A上的同余關系，所以上述定義中Ak是唯一確定的。其次，作映射f:A?B,f(a)=Ai,a?Ai。顯然f是滿射。對任意x,y?A,則x,y應屬于某一分塊，可設x?Ai y?Aj，這里1?i,j?r,于是f(x*y)=Ak=Ai?Aj=f(x)。因此，f是由到的滿同態(tài)，即是的同態(tài)象。,本定理證明線索：1、在B上建立運算?；2、證與滿同態(tài)，即要構(gòu)造一個滿射f:A?B, 使 f(x*y)=f(x)?f(y

15、)。,,,,,14,6、同余關系（4）,定理5 設f是到的同態(tài)映射，定義A上的二元關系R：aRb當且僅當f(a)=f(b),則R是A上的同余關系。,證：先證R是A上的等價關系：對任意a?A,因f(a)=f(a)，所以aRa；若aRb,則f(a)=f(b)，亦有f(b)=f(a)，所以bRa；若aRb,bRc,則f(a)=f(b)，f(b)=f(c),于是f(a)=f(c)，所以aRc。 其次，若aRb,cRd,則 f(a*