課件代數結構第七章

1、 DM抽象代數Abstract Algebra本部分所要探討的數學結構本部分所要探討的數學結構是是由集合上定義若干運算而由集合上定義若干運算而組成的系統(tǒng)組成的系統(tǒng)稱為代數系稱為代數系統(tǒng)統(tǒng)( (代數結構代數結構) )。 幾個問題用用n n種顏色的珠子做成有種顏色的珠子做成有m m顆珠子的項鏈，問可做成多少顆珠子的項鏈，問可做成多少種不同類型的項鏈種不同類型的項鏈? ?：對一個正多面體的項點或面用對一個正多面體的項點或面用n n種顏色進行著種顏色進行著色，問有多少色，問有多少 種不同的著色方法種不同的著色方法? ? ：用：用n n個開關可以構造出多少種不同的個開關可以構造出多少種不同的開關線路開關

2、線路? ?如何設計高效的檢錯碼與糾錯碼？如何設計高效的檢錯碼與糾錯碼？：五次方程有根嗎？：五次方程有根嗎？某語言某語言L L的語法語義？程序的結構（數據表示？算法構的語法語義？程序的結構（數據表示？算法構造？），根據造？），根據L L編寫的程序是正確的嗎？編寫的程序是正確的嗎？該問題可計算嗎？計算機能該問題可計算嗎？計算機能/ /不能計算嗎？計算復雜不能計算嗎？計算復雜性如何？性如何？重點：重點：難點：難點：6.6.1 集合集合運算運算代數結構代數結構定義定義例例1Z;+,*,-,N,-, T,F; , P(A); ,，*; * 需要滿足的條件？需要滿足的條件？1) 有一個有一個非空集合非空集

3、合S，稱為，稱為載體載體()； 2）一些定義在載體）一些定義在載體S上的運算。上的運算。某個集合上的某個集合上的運算運算在某個集合下的在某個集合下的封閉性封閉性？運算封閉性運算封閉性：若：若 x，yA，有，有x * yA，稱，稱*在在A上是封閉的上是封閉的設設o是集合是集合A上的一個上的一個n元運算，非空集合元運算，非空集合S A，如果對于每一個，如果對于每一個(a1，a2，an)S，都有，都有o(a1，a2，an)S，則稱，則稱S在運算在運算o下是封閉的下是封閉的，或，或o在集合在集合S上是封閉的上是封閉的。 代數結構？代數結構？S;O集合集合S？ 運算運算O？例例2 ： A=xx=2n，n

4、N， 問一般乘法運算問一般乘法運算*在在A上封閉否，加法上封閉否，加法+、除法、除法/ 呢？呢？ 解：解： 2r，2sA， 2r * 2s=2r+sA （） *在在A上運算封閉上運算封閉 2，4A，2+4 A，+在在A上不封閉上不封閉 2，4A，2/4 A， /在在A上不封閉上不封閉 定義定義7.47.4 設設V=, S S, 如果運如果運算算*1,*2,*n在在S上封上封閉閉， ，則則稱稱為為V的的子代數子代數結結構構， ，簡簡稱稱為為V的的子代數子代數(Subalgebra)。 。 根據上述子代數的定根據上述子代數的定義義，代數，代數結結構構V上運上運算算滿滿足的性足的性質質，其子代數，其

5、子代數結結構也構也滿滿足。足。 例例7.77.7 設設N為為自然數集合，自然數集合，為為非非負負奇數集，奇數集，E為為非非負負偶數集，偶數集，則對則對于代數于代數結結構構（ （+為為一一般加法運算），般加法運算），為為其子代數，但其子代數，但不不是其子代數，因是其子代數，因為為后者后者+在在上不上不滿滿足封足封閉閉性。性。 運算性質、特殊元素運算性質、特殊元素滿足封閉性滿足封閉性結合律結合律交換律交換律(左左/右右)分配律、消去律、吸收律分配律、消去律、吸收律冪等元冪等元(Idempotent element)(左左/右右)單位元單位元(Identity element) (左左/右右)零元零

6、元 (Zero element) (左左/右右)逆元逆元 (Inverse) 類類似于初等代數以及集合似于初等代數以及集合論論、數理、數理邏輯邏輯中中討討論論的運算之性的運算之性質質， ，對對于二元運算于二元運算以及以及*： ： 若若對對于任意于任意a, bA有：有：ab=ba, 則則稱稱在在A上是上是可交可交換換的的(或稱或稱滿滿足交足交換換律律)。 。 若若對對于任意于任意aA有：有：aa=a, 則則稱稱在在A上是上是滿滿足足冪冪等律等律的。的。 若若對對于任意于任意a, b, cA有：當有：當ab=ac時時，有，有b=c, 則則稱稱在在A上是上是左可消去的左可消去的(或稱或稱滿滿足左消足

7、左消去律去律)，若，若在在A上是上是滿滿足左可消去律與右可消去足左可消去律與右可消去律，律，則則稱稱在在A上是上是可消去的可消去的(或稱或稱滿滿足消去律足消去律)。 。 若若對對于任意于任意a, b, cA, 有：有：a(b*c)=(ab)*(ac); (b*c)a=(ba)*(ca)。 。則則稱稱對對于于*是是可分配的可分配的(或稱或稱滿滿足分配律足分配律)。 。 若若對對于任意于任意a, b, cA有：有：a(bc)=(ab)c, 則則稱稱為為在在A上是上是可可結結合的合的(或稱或稱滿滿足足結結合律合律)。若集合。若集合A上的二元運算上的二元運算*滿滿足足結結合律合律, 則則我我們們常用常

8、用a*b*c來表示來表示(a*b)*c=a*(b*c)。 。 7.2.37.2.3 代數結構的特殊元素代數結構的特殊元素 1. 1. 單位元單位元 定義定義7.57.5 設設是集合是集合A上的二元運算，如果上的二元運算，如果存在一個元素存在一個元素elA， ，使得使得對對于任意的于任意的aA滿滿足足ela=a， ，則則稱稱el是是A上關于運算上關于運算的的左左單單位元位元； ；如果存在一個元素如果存在一個元素erA， ，使得使得對對于任意的于任意的aA有有aer=a， ，則則稱稱er是是A上關于運算上關于運算的的右右單單位元位元；如果存在一個元素；如果存在一個元素eA， ，使得使得對對于任意于

9、任意的的aA有有ea=ae=a， ，則則稱稱e是是A上關于運算上關于運算的的單單位元位元。 。 定理定理7.17.1 設設是集合是集合A上的二元運算，上的二元運算，又設又設el和和er分別是分別是的左單位元和右單位的左單位元和右單位元，則元，則el=er=e，且，且e是是的惟一的單位元。的惟一的單位元。 2. 2. 逆元逆元 定義定義7.67.6 設設是集合是集合A上有上有單單位元位元e的二元運的二元運算，算，對對于元素于元素aA， ，如果存在一元素如果存在一元素al-1A， ，使使得得al-1a=e， ，則則稱稱a是是左可逆的左可逆的，并稱，并稱al-1是是a的一的一個左逆元；如果存在一元素

10、個左逆元；如果存在一元素ar-1A， ，使得使得aar-1=e， ，則則稱元素稱元素a是是右可逆的右可逆的，并稱，并稱ar-1是是a的一個的一個右逆元，如果存在一元素右逆元，如果存在一元素a-1A， ，使得使得a-1a=aa-1=e， ，則則稱元素稱元素a關于運算關于運算是是可逆的可逆的， ，而稱而稱a-1是是a的一個的一個逆元逆元。 。 定理定理7.27.2 設設是集合是集合A上的具有上的具有單單位元位元e且可且可結結合的二元運算，如果元素合的二元運算，如果元素aA有左逆元和右逆有左逆元和右逆元，元，則則其左、右逆元相等，并且若令其左、右逆元相等，并且若令al-1=ar-1= a-1， ，則

11、則a-1就是就是a惟一的逆元。惟一的逆元。 由逆元的定由逆元的定義義我我們們得知得知， ，如果如果aA有逆元有逆元 a-1， ，則則aa-1=a-1a=e， ，因此因此(a-1)-1=a(即即a是是 a-1的逆的逆元元)。 。 例如，每一個例如，每一個實實數數rR均有一個關于加法運均有一個關于加法運算的逆元算的逆元-r， ，每一個非零每一個非零實實數數rR， ，均有一個關均有一個關于乘法運算的逆元于乘法運算的逆元1/r。 。 顯顯然，然，對對于任何二元運算，于任何二元運算，單單位元是可逆的，位元是可逆的，其逆元就是其逆元就是單單位元本身。位元本身。 3. 3. 零元零元 定義定義7.77.7

12、設設是集合是集合A上的二元運算，如果上的二元運算，如果存在一個元素存在一個元素zlA，使得對于所有的，使得對于所有的aA，有有zla=zl，則稱，則稱zl是是A上關于運算上關于運算的的左零元左零元；如果存在一個元素如果存在一個元素zrA，使得對于所有的，使得對于所有的aA均有均有azr=zr，則稱，則稱zr是是A上關于運算上關于運算的的右零元右零元；如果存在一個元素；如果存在一個元素zA，使得對于所，使得對于所有的有的aA均有均有za=az=z，則稱，則稱z是是A上關于上關于運算運算的的零元零元(Zero Element)。 定理定理7.37.3 若若是集合是集合A上的二元運算，上的二元運算，

13、又設又設zl和和zr分別是分別是的左零元和右零元，的左零元和右零元，則則zl=zr=z，且，且z是是的惟一的一個零元。的惟一的一個零元。 4. 冪等元冪等元 定義定義7.87.8 設設是集合是集合A上的二元運算，如上的二元運算，如果果aa=a，則稱，則稱a是是A上的二元運算上的二元運算的的一個一個冪等元冪等元(Idempotent element)。 顯然，單位元和零元均是冪等元。顯然，單位元和零元均是冪等元。 c) 代數結構代數結構A=a，b，c； 。 用下表用下表定義：定義：。abcaabbbabccaba從運算表可以看出，從運算表可以看出，b是是左單位元，無右單位元；左單位元，無右單位元

14、；a是右零元，是右零元，b是右零元，是右零元，無左零元無左零元; 運算：不滿足交換律？運算：不滿足交換律？ d) 代數代數R，*中，除零元中，除零元0外所有元素均有逆元外所有元素均有逆元 e) A=a，b，c，*由下表定義：由下表定義： *a b ca a a bb a b cc a c cb是單位元是單位元,a的右逆元為的右逆元為c，無左逆元，無左逆元，b的逆元為的逆元為b，c的右逆元為空，左逆元為的右逆元為空，左逆元為a 運算性質、特殊元素運算性質、特殊元素滿足封閉性：滿足封閉性：運算表中每一個元素運算表中每一個元素aS結合律：結合律：構造表來判斷構造表來判斷交換律：交換律：關于主對角線對

15、稱關于主對角線對稱(左左/右右)分配律、消去律、分配律、消去律、吸收律吸收律等冪律等冪律(冪等元冪等元)：主對角線上元素與其所在表頭元素同主對角線上元素與其所在表頭元素同(左左/右右)單位元單位元:某元素某元素x，其相應行，其相應行/列與表列列與表列/行頭元素同行頭元素同(左左/右右)零元零元:某元素某元素x，與其所在的行，與其所在的行/列元素全相同列元素全相同(左左/右右)逆元逆元:首先首先,是否存在單位元？元素是否存在單位元？元素x所在的列所在的列/行的單位元行的單位元相應的行相應的行/列頭元素即其逆元列頭元素即其逆元例例3a）P（S）；）；,對運算對運算，是單位元，是單位元， S是零元，

16、是零元，對運算對運算，S是單位元是單位元 ，是零元。是零元。b）N；+有單位元有單位元0，無零元。，無零元。f）代數結構：）代數結構：A= *k稱為模稱為模k乘法求余（乘法求余（x*ky或記為或記為resk(x*y)。 零元？單位元？關于逆元？零元？單位元？關于逆元？當且僅當當且僅當x與與k互質時，互質時，x有逆元有逆元實數集實數集R上的二元運算上的二元運算*：a*b=a+b-ab是否有單位元、是否有單位元、零元與冪等元，如果有單位元，哪些元素有逆元？零元與冪等元，如果有單位元，哪些元素有逆元？半群半群(Semigroup)、單位半群、單位半群(獨異點獨異點,Monoid)結合性、單位元結合性

17、、單位元例例5a) 代數結構代數結構N；*,0，1；*是半群，是獨異點嗎？是是半群，是獨異點嗎？是R; *的子半群的子半群,子獨異點嗎？子獨異點嗎？代數結構代數結構R; -是半群嗎？是半群嗎？*，-為一般乘法、減法為一般乘法、減法b) 設設s=a，b，*定義如右表，定義如右表，是半群嗎是半群嗎? 注意到注意到a，b都是右零元都是右零元 x,y,z s x*y s 運算封閉運算封閉 x*（y*z）=x*z=z （x*y）*z=z 結合律成立結合律成立 是一半群，該半群稱為二元素右零半群是一半群，該半群稱為二元素右零半群*abaabbab練習練習1 獨異點運算表中任何兩行兩列均不相同獨異點運算表中

18、任何兩行兩列均不相同.2 是一個半群嗎是一個半群嗎?3 若半群若半群A，*的單位元為的單位元為e, a，b A，若若a，b均有均有逆元，則逆元，則 1)（a-1）-1=a; 2)（a*b）-1=b-1*a-1 。 試證明之試證明之.4 有限半群必有冪等元有限半群必有冪等元? 有限有限半群必有冪等元半群必有冪等元.證明證明 設設是有限半群，需證是有限半群，需證 a S，有，有a*a=a。對對 b S，由運算封閉性，有，由運算封閉性，有b2=b*b S,進一步可得進一步可得b3，b4， S。又又S有限，故存在有限，故存在i，j N，j 使得使得bi=bj。從而利用半群的可結合性有從而利用半群的可結

19、合性有 bi=bj=bj-i*bi。現令現令p=j-i，則對任意，則對任意q N，qi時時, 有有bq= bq-i*bi=bq-i*bj=bq- i*bj-i*bi=bq-i*bp*bi=bp*bq。又又p1，則存在，則存在qi，q N，且有，且有k N，使，使 q=kp，從而有從而有bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp，令令a=bkp S 則則a*a=a，即，即a=bkp是是的冪等元。的冪等元。為什么需要研究代數結構之間的關系？為什么需要研究代數結構之間的關系？ 在研究代數結構的過程中，所關心的常常是代數結過中運算所滿足在研究代數結構的過程中，所關心的常常是代數結過中

20、運算所滿足的性質，不關心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)只需要研的性質，不關心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)只需要研究其中一個就可以了解其它的系統(tǒng)究其中一個就可以了解其它的系統(tǒng).抽象抽象代數代數！考察下列代數考察下列代數: A1= I; ; A2= Q;+ ; A3= R+;min ;A4= P(S); ; A5= P(S); . 此此5個代數都有相同的構成成分個代數都有相同的構成成分:同樣個數的運算且對應運算元數相同樣個數的運算且對應運算元數相 (1個二元運算個二元運算); 滿足同樣的公理規(guī)則滿足同樣的公理規(guī)則(交換律交換律,結合律結合律);存在單位元。存在單位元。 稱具有

21、上述性質的代數是同一類稱具有上述性質的代數是同一類(代數結構的類代數結構的類) 映射 例例 5V1=與V2=兩個代數結構之間存在一個映射：g：0,1 M,H對于 a,b 0,1,有有g(a Vb)=g(a)*g(b)V01001111*MHMMHHHH 對于兩代數結構設對于兩代數結構設V1=和和 V2= 1)是是的代數結構的代數結構（運算個數、對應的運算的元數都相同）（運算個數、對應的運算的元數都相同） 2)存在從存在從A到到B的一個的一個/f 3)運算性質保持（保運算性，滿足運算性質保持（保運算性，滿足：對于：對于ki元運算元運算Oi(i=1，2，r)，若任意，若任意(x1，x2，xki)A

22、ki，都有，都有 f(Oi(x1，x2，xki)= *i(f(x1)，f(xki)， 則稱則稱f是是V1到到V2的一個同態(tài)的一個同態(tài)/滿同態(tài)滿同態(tài)/單同態(tài)單同態(tài)/同構映射，并稱同構映射，并稱V1與與V2 同態(tài)同態(tài)(Homomorphic) /滿同態(tài)滿同態(tài)/單同態(tài)單同態(tài)/同構的同構的(Isomorphic) 。 例例6：代數代數結結構構 R+; * , R;+ 同構同構嗎嗎？ 證明：證明：顯然，顯然， 與與為為同型代數結構同型代數結構，下面證明二者之間存在雙射關系且滿足同態(tài)方程。下面證明二者之間存在雙射關系且滿足同態(tài)方程。i)建立雙射關系：建立雙射關系： 令令h:R+R,h(x)=lnx 顯然，

23、顯然，h是單射是單射 y R, x=ey使使y=lney =lnx=h(x) h是滿射是滿射 h是從是從R+到到R的雙射的雙射ii)h滿足同態(tài)方程：滿足同態(tài)方程： a,bR+ ,h(a*b)=ln(a*b)=lna+lnb=h(a)+h(b)綜上綜上，同構于同構于這樣，利用同態(tài)這樣，利用同態(tài)/ /同構同構關系，可以關系，可以轉移運算轉移運算，復雜的代數系統(tǒng)可以壓復雜的代數系統(tǒng)可以壓縮為另一簡單的代數系縮為另一簡單的代數系統(tǒng)。統(tǒng)。AABBff*+思考思考：請你舉例說明上述：請你舉例說明上述系統(tǒng)轉換思想。系統(tǒng)轉換思想。數學、信號處理中的一些變換：數學、信號處理中的一些變換：l拉普拉斯變換拉普拉斯變

24、換l時頻分析時頻分析l坐標變換坐標變換l離散余弦變換離散余弦變換l小波變換小波變換例例7a) 請判斷請判斷T,F; ,T,F; 是否同構。是否同構。b) 請判斷請判斷*; ,N;+是否同構，運算是否同構，運算“”表示字符串的連接，表示字符串的連接， “+” 為一般的加法運算。為一般的加法運算。c) 代數結構代數結構I;+,*,Nm;+m, *m是否同態(tài)？其中，是否同態(tài)？其中， 運算運算+m, *m分別是模分別是模m加、乘。加、乘。d)I;+,2I;+同構嗎？同構嗎？e) 設設與與是代數結構，其中是代數結構，其中I+為正整數集，為正整數集，E+為正偶為正偶數集，數集，*分別為一般的乘法運算，分別

25、為一般的乘法運算，h為為R上的映射，對任意上的映射，對任意xI+， h(x)=2x。試證明：。試證明：h不是不是到到的同構映射，并證明的同構映射，并證明與與不同構。不同構。 b) b) 代數結構代數結構與與是同態(tài)關系。是同態(tài)關系。 證明：顯然它們是同型函數，并存在一個映證明：顯然它們是同型函數，并存在一個映射：射：f(s)=|s|，其中，其中s為由為由*中元素所組成的串，中元素所組成的串，|s|為串為串s的長度。此映射是多一對應的，且對任的長度。此映射是多一對應的，且對任意意s1，s2*, 顯然有：顯然有： f(s1s2)=|s1s2|=| s1|+| s2|=f(s1)+f(s2)， 所以所

26、以與與同態(tài)，并且還是滿同同態(tài)，并且還是滿同態(tài)。態(tài)。 e)證明證明 顯然，顯然，h是是I+到到E的雙射，對任意的雙射，對任意x，yI+，有，有h(x*y)=2xy，但但h(x)*h(y)=4xy, 顯然顯然h(x*y)h(x)*h(y)。故，故，h不是不是到到的同構映射。的同構映射。h不是不是到到的同構的同構映射映射能說明能說明與與就一定不同構嗎？就一定不同構嗎？ 不一定，因不一定，因為為，同構定，同構定義義中只要求中只要求“ “保持運算保持運算” ”的的映射存在，但未要求所有雙射都是映射存在，但未要求所有雙射都是“ “保持運算保持運算” ”的，因的，因此，必此，必須證須證明明這這種種“ “保持

27、運算保持運算” ”的雙射不存在，才能的雙射不存在，才能說說明明與與不同構。不同構。7.2.2 同態(tài)與同構的性質同態(tài)與同構的性質定理定理7.4 設設g為代數結構為代數結構到到的同構映射，的同構映射，即存在一個一即存在一個一一映射一映射g:XY，使得，使得 x1,x2 X，則有，則有g(x1x2)=g(x1)*g(x2)。 若若存在單位元存在單位元ex，則則亦存在單位元亦存在單位元ey，且有，且有ey = g(ex) 。 證明：證明：對對 y Y， x Y，使得，使得y=g(x),于是，由于是，由與與同構，且同構，且有單位元有單位元ex，有有 g(ex)*y= g(ex)*g(x)=g(exx)=

28、g(x),且且y*g(ex)= g(x)*g(ex) =g(xex)=g(x)，故故g(ex)*y= y*g(ex)=y。所以所以的存在單位元的存在單位元ey且且 g(ex)= ey。性質保持性質保持1 對于同構：對于同構： 保持結合律、交換律、分配律；單位元、逆元、零元相應存在保持結合律、交換律、分配律；單位元、逆元、零元相應存在（教材的證明請自學）（教材的證明請自學）同構關系是一種等價關系？同構關系是一種等價關系？2 對于同態(tài)對于同態(tài) 滿同態(tài)滿同態(tài)單向保持性質單向保持性質XYf 集合上的等價關系？集合上的等價關系？ 等價類等價類商集商集添加運算之后添加運算之后？ 1 為什么研究為什么研究同

29、余關系同余關系？等價關系等價關系同余關系同余關系補碼、隨機數、文件系統(tǒng)、補碼、隨機數、文件系統(tǒng)、hashhash、密碼、檢錯碼密碼、檢錯碼歐拉函數和費馬定理歐拉函數和費馬定理同態(tài)三角形同態(tài)三角形（同態(tài)基本定理）（同態(tài)基本定理）V=V=V/h=h(滿同態(tài)滿同態(tài))g (自然滿同態(tài)自然滿同態(tài))f (同構同構)集合論：集合論： 函數函數等價關系等價關系劃分劃分代數結構：代數結構： 同態(tài)同態(tài)同余關系同余關系可允許劃分可允許劃分變換變換6.3.1 同余關系同余關系 原始含義（示例）：原始含義（示例）： 代數結構代數結構在在Z上的關系上的關系R定義如下：定義如下： xRy xy(mod k)， 且滿足如下推

30、理：且滿足如下推理： xRy且且 zRw (x+z)R(y+w)（*） 這樣，上述利用這樣，上述利用余數相等余數相等建立的滿足（建立的滿足（*）推理式的）推理式的關系關系R稱為稱為同余關系同余關系。推廣推廣1 命題邏輯公式的等值關系是邏輯代數上的同余關命題邏輯公式的等值關系是邏輯代數上的同余關系嗎？系嗎？2 恒等關系是集合代數上的同余關系嗎？恒等關系是集合代數上的同余關系嗎？3 , R=(x, y)|x/y=2m, mZ同余關系同余關系(Congruence) 是一個代數系統(tǒng)是一個代數系統(tǒng),R是是A上的等價關系上的等價關系,若若 R, R R，稱，稱R是是A上的上的同余關系同余關系(R對對于運

31、算于運算*滿足滿足代換性質代換性質).同余關系將同余關系將A劃分得到的等價類稱為劃分得到的等價類稱為 可允許劃分可允許劃分(同余類同余類)： 對于代數結構對于代數結構, =A1,A2,An是是A上的一個劃分，若對于上的一個劃分，若對于任意的劃分塊任意的劃分塊Ai, Aj ,存在存在Ak ,使得：使得：Ai*Aj Ak,則稱為可允許劃則稱為可允許劃分。分。例例12：，在，在I上定義上定義R: R|x|=|y|, 問問R是是的等價關系嗎？是否是同余關系的等價關系嗎？是否是同余關系?解解: 1)自反性自反性： x I, |x|=|x| ，從而，從而 R 2)對稱性對稱性： x,y I，若，若 R則則

32、|x|=|y|，從而，從而 R 3)傳遞性傳遞性： x,y,z I，若，若 R, R 由由|x|=|y|=|z| 知知 R 所以所以 R是一等價關系。是一等價關系。 對對 x1,y1,x2,y2 I，若，若 R, R， 但但 R不一定成立，例如，不一定成立，例如， R, R但但 R 綜上，綜上，R是等價關系但不是同余關系是等價關系但不是同余關系定理定理 設設R是代數結構是代數結構上的上的等價關系等價關系，*為為二元運算，對于二元運算，對于 a，b S/R, 其中其中S/R是是可允許劃分可允許劃分定義定義a ob=a*b則則o為為S/R上的上的二元運算二元運算當且僅當當且僅當R為為上上同余關系同

33、余關系。 證明證明 必要性必要性 設設o為為上二元運算。對上二元運算。對 a, b, c, d S,若若aRb，cRd，即，即a=b,c=d, 則則a oc=b od, 又有又有a oc=a*c, b od=b*d。從而。從而a*c=b*d。于是于是a*cRb*d。故。故R為為上同余關系。上同余關系。充分性充分性 設設R為為上同余關系，任意上同余關系，任意a,b S/R， 顯然顯然a ob=a*b S/R，即，即o在在S/R上滿足封閉性，還需證對任意上滿足封閉性，還需證對任意a,b S/R，a ob值唯一。值唯一。注意到，注意到，a ob=a*b，a*b值是惟一的，值是惟一的，a*b是惟一的。

34、因此，需要證明若是惟一的。因此，需要證明若a，b取其它代表元，如取其它代表元，如a,b，其值，其值a*b與與a*b是否相等。是否相等。對對 a a, b b,有有aRa, bRb, 則則a*bRa*b 。于是。于是a ob=a*b =a*b=a ob。這說明。這說明a ob的運算結果與等價類的代表元無關，值是唯一的運算結果與等價類的代表元無關，值是唯一的。的。故故o是是S/R上的二元運算。上的二元運算。綜上，命題得證。綜上，命題得證。6.3.2 同余關系同余關系商代數商代數(Quotient Algebra)思考思考是否可以根據是否可以根據 上的同余關系定義一個上的同余關系定義一個的滿同的滿同

35、態(tài)代數結構（商代數）？態(tài)代數結構（商代數）？同余關系同余關系商代數商代數(Quotient algebra) 代數結構：代數結構：V= （o為一元運算）為一元運算）V上同余關系：上同余關系：商代數：商代數：V/=運算運算o的定義？的定義？ o(x)=o(x)代數結構：代數結構：V= （o為二元運算）為二元運算）V上同余關系：上同余關系：商代數：商代數：V/=運算運算*的定義？的定義？ x o y=xoy6.3.2 同同態(tài)態(tài)基本定理基本定理設代數結構設代數結構V=, V=, h是從是從V到到V的滿同態(tài)映射，的滿同態(tài)映射，則則1) 在在S上定義一個關系上定義一個關系h，使得當且僅當，使得當且僅當h

36、(x)=h(y)時時xhy，則，則h是是V上的同余關系（上的同余關系（同余定理同余定理）；）；2) 由由h可以得到可以得到V的商代數的商代數，記為，記為V/h，且存在，且存在V到到V/h的滿同態(tài)映射的滿同態(tài)映射(自然同態(tài)自然同態(tài))g；3) V/h與與V同構。同構。同同態(tài)態(tài)三角形三角形V=V=V/h=h(滿同態(tài)滿同態(tài))g (自然滿同態(tài)自然滿同態(tài))f (同構同構)集合論：集合論： 函數函數等價關系等價關系劃分劃分代數結構：代數結構： 同態(tài)同態(tài)同余關系同余關系可允許劃分可允許劃分 同態(tài)三角形的同構性的證明：同態(tài)三角形的同構性的證明：1 同型：同型：Vh 與與 V同型？同型？2 雙射：雙射： 定義映射

37、定義映射f，并證明其為雙射，并證明其為雙射定義映射定義映射f：因為因為h是一個從是一個從S到到S的滿射，的滿射， S/h為可允許劃分，所以為可允許劃分，所以對于每一個對于每一個xh S/h必存在唯一必存在唯一xS，使得，使得x=h(x)，于是可以，于是可以如下定義函數：如下定義函數：f: S/h S ，使得，使得f(xh)=x=h(x)。 f為滿射為滿射：對于任意：對于任意xS ，必存在，必存在 xS，使得，使得h(x) =x，從而存在，從而存在x h S/h，使得，使得f(xh)=h(x)=x ，所以，所以f是滿射。是滿射。f為單射為單射：若：若h(x)=h(y)，則，則xhy，于是，于是x

38、h=yh，所以，所以f是單射是單射3 滿足同態(tài)方程滿足同態(tài)方程由于由于 f(xh yh)=f(xoyh)=h(xoy)=h(x)*h(y)=f(xh)*f(yh)所以，前述運算與雙射滿足同態(tài)方程。所以，前述運算與雙射滿足同態(tài)方程。綜上，綜上， Vh 與與 V同構。同構。思考思考如果上述同構證明過程中，將映射改f改為從S 到S/h ，則如何描述具體證明過程？補充例題補充例題1 設設*是自然數集合是自然數集合N中的二元運算，并定義中的二元運算，并定義x*y=x。試證明。試證明*是可結合的，但不是可交換的。是可結合的，但不是可交換的。2 M為單位半群，證明為單位半群，證明b=a-1的充分必要條件是的

39、充分必要條件是aba=a和和ab2a=e。3 代數結構間的同構關系是等價關系。代數結構間的同構關系是等價關系。4 考慮代數結構考慮代數結構V=Z3 ； 3， 3和和Z3上的等價關系上的等價關系。1) 證明若證明若對于對于 3滿足代換性質，則它對滿足代換性質，則它對 3一定也滿足代換一定也滿足代換性質。性質。2) 找出一個找出一個Z3上的等價關系，它對于上的等價關系，它對于 3滿足代換性質，但對滿足代換性質，但對 3不滿足。不滿足。補充例題補充例題2 M為單位半群，證明為單位半群，證明b=a-1的充分必要條件是的充分必要條件是aba=a和和ab2a=e。證 必要性：將b代入即可得。充分性：利用結

40、合律作以下運算：ab=ab(ab2a)=(aba)b2a=ab2a=e，ba=(ab2a)ba=ab2 (aba)=ab2a=e，所以b=a-1。 證畢補充例題補充例題3 代數結構間的同構關系是等價關系。代數結構間的同構關系是等價關系。證明證明 設設X；，Y；*，Z；+是任意的三個代數結構，是任意的三個代數結構，并設同構關系用并設同構關系用“ ”表示，下面表示，下面 證明滿足自反性、對稱性以及證明滿足自反性、對稱性以及傳遞性。傳遞性。補充例題補充例題 (1) 自反性自反性：顯然有：顯然有X； X；)，即是自反的。，即是自反的。 (2) 對稱性對稱性：如果：如果X； Y；*則必存在一個雙射則必存

41、在一個雙射 g: XY，使，使得若得若x1，x2X，并有：，并有：g(x1x2)=g(x1)*g(x2)根據雙射的定義，必存在一個雙射的逆映射根據雙射的定義，必存在一個雙射的逆映射g-1: YX。現要證對現要證對g-1: YX，若，若y1，y2Y，必有：，必有： g-1(y1*y2)=g-1(y1)g-1(y2)設對任意的設對任意的y1，y2Y必存在必存在x1，x2X，使得，使得g(x1)=y1，g(x2)=y2，亦，亦即即g-1(y1)=x1，g-1(y2)=x2，故有：，故有： g-1(y1*y2) = g-1(g(x1)*g(x2) =g-1(g(x1x2) =x1x2 又又g-1(y1)g-1(y2)=x1x2所以所以g-1(y1*y2)=g-1(y1)g-1(y2)因此，因此，Y；* X；，所以，所以 是對稱的。是對稱的。補充例題補充例題 (3) 傳遞性：傳遞性：如果有如果有X； Y；*，且，且Y；* Z；+，要證明要證明X；