课件代数结构第七章

1、 DM抽象代数Abstract Algebra本部分所要探讨的数学结构本部分所要探讨的数学结构是是由集合上定义若干运算而由集合上定义若干运算而组成的系统组成的系统称为代数系称为代数系统统( (代数结构代数结构) )。 几个问题用用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、运算所满足的性质，不关心具体的运算，而对于遵循相同运算规律的系统只需要研的性质，不关心具体的运算，而对于遵循相同运算规律的系统只需要研究其中一个就可以了解其它的系统究其中一个就可以了解其它的系统.抽象抽象代数代数！考察下列代数考察下列代数: A1= I; ; A2= Q;+ ; A3= R+;min ;A4= P(S); ; A5= P(S); . 此此5个代数都有相同的构成成分个代数都有相同的构成成分:同样个数的运算且对应运算元数相同样个数的运算且对应运算元数相 (1个二元运算个二元运算); 满足同样的公理规则满足同样的公理规则(交换律交换律,结合律结合律);存在单位元。存在单位元。 称具有

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的一个同态的一个同态/满同态满同态/单同态单同态/同构映射，并称同构映射，并称V1与与V2 同态同态(Homomorphic) /满同态满同态/单同态单同态/同构的同构的(Isomorphic) 。 例例6：代数代数结结构构 R+; * , R;+ 同构同构吗吗？ 证明：证明：显然，显然， 与与为为同型代数结构同型代数结构，下面证明二者之间存在双射关系且满足同态方程。下面证明二者之间存在双射关系且满足同态方程。i)建立双射关系：建立双射关系： 令令h:R+R,h(x)=lnx 显然，

23、显然，h是单射是单射 y R, x=ey使使y=lney =lnx=h(x) h是满射是满射 h是从是从R+到到R的双射的双射ii)h满足同态方程：满足同态方程： a,bR+ ,h(a*b)=ln(a*b)=lna+lnb=h(a)+h(b)综上综上，同构于同构于这样，利用同态这样，利用同态/ /同构同构关系，可以关系，可以转移运算转移运算，复杂的代数系统可以压复杂的代数系统可以压缩为另一简单的代数系缩为另一简单的代数系统。统。AABBff*+思考思考：请你举例说明上述：请你举例说明上述系统转换思想。系统转换思想。数学、信号处理中的一些变换：数学、信号处理中的一些变换：l拉普拉斯变换拉普拉斯变

24、换l时频分析时频分析l坐标变换坐标变换l离散余弦变换离散余弦变换l小波变换小波变换例例7a) 请判断请判断T,F; ,T,F; 是否同构。是否同构。b) 请判断请判断*; ,N;+是否同构，运算是否同构，运算“”表示字符串的连接，表示字符串的连接， “+” 为一般的加法运算。为一般的加法运算。c) 代数结构代数结构I;+,*,Nm;+m, *m是否同态？其中，是否同态？其中， 运算运算+m, *m分别是模分别是模m加、乘。加、乘。d)I;+,2I;+同构吗？同构吗？e) 设设与与是代数结构，其中是代数结构，其中I+为正整数集，为正整数集，E+为正偶为正偶数集，数集，*分别为一般的乘法运算，分别

25、为一般的乘法运算，h为为R上的映射，对任意上的映射，对任意xI+， h(x)=2x。试证明：。试证明：h不是不是到到的同构映射，并证明的同构映射，并证明与与不同构。不同构。 b) b) 代数结构代数结构与与是同态关系。是同态关系。 证明：显然它们是同型函数，并存在一个映证明：显然它们是同型函数，并存在一个映射：射：f(s)=|s|，其中，其中s为由为由*中元素所组成的串，中元素所组成的串，|s|为串为串s的长度。此映射是多一对应的，且对任的长度。此映射是多一对应的，且对任意意s1，s2*, 显然有：显然有： f(s1s2)=|s1s2|=| s1|+| s2|=f(s1)+f(s2)， 所以所

26、以与与同态，并且还是满同同态，并且还是满同态。态。 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 同态与同构的性质同态与同构的性质定理定理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 对于同态对于同态 满同态满同态单向保持性质单向保持性质XYf 集合上的等价关系？集合上的等价关系？ 等价类等价类商集商集添加运算之后添加运算之后？ 1 为什么研究为什么研究同

29、余关系同余关系？等价关系等价关系同余关系同余关系补码、随机数、文件系统、补码、随机数、文件系统、hashhash、密码、检错码密码、检错码欧拉函数和费马定理欧拉函数和费马定理同态三角形同态三角形（同态基本定理）（同态基本定理）V=V=V/h=h(满同态满同态)g (自然满同态自然满同态)f (同构同构)集合论：集合论： 函数函数等价关系等价关系划分划分代数结构：代数结构： 同态同态同余关系同余关系可允许划分可允许划分变换变换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) 是一个代数系统是一个代数系统,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、态代数结构（商代数）？态代数结构（商代数）？同余关系同余关系商代数商代数(Quotient algebra) 代数结构：代数结构：V= （o为一元运算）为一元运算）V上同余关系：上同余关系：商代数：商代数：V/=运算运算o的定义？的定义？ o(x)=o(x)代数结构：代数结构：V= （o为二元运算）为二元运算）V上同余关系：上同余关系：商代数：商代数：V/=运算运算*的定义？的定义？ x o y=xoy6.3.2 同同态态基本定理基本定理设代数结构设代数结构V=, V=, h是从是从V到到V的满同态映射，的满同态映射，则则1) 在在S上定义一个关系上定义一个关系h，使得当且仅当，使得当且仅当h

36、(x)=h(y)时时xhy，则，则h是是V上的同余关系（上的同余关系（同余定理同余定理）；）；2) 由由h可以得到可以得到V的商代数的商代数，记为，记为V/h，且存在，且存在V到到V/h的满同态映射的满同态映射(自然同态自然同态)g；3) V/h与与V同构。同构。同同态态三角形三角形V=V=V/h=h(满同态满同态)g (自然满同态自然满同态)f (同构同构)集合论：集合论： 函数函数等价关系等价关系划分划分代数结构：代数结构： 同态同态同余关系同余关系可允许划分可允许划分 同态三角形的同构性的证明：同态三角形的同构性的证明：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 满足同态方程满足同态方程由于由于 f(xh yh)=f(xoyh)=h(xoy)=h(x)*h(y)=f(xh)*f(yh)所以，前述运算与双射满足同态方程。所以，前述运算与双射满足同态方程。综上，综上， 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；