离散数学第六章代数系统.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 代数系统基本概念及性质,离散数学,陈志奎主编,人民邮电出版社,爱因斯坦小时候曾好奇的问他的叔叔：,“,代数是什么,”,？（那时候他只学过算术）他的叔叔回答的很妙：,“,代数是一种懒惰人的算术，当你不知道某些数时，你就暂时假设它为,x,、,y,，然后再想办法去寻找它们。,”,道理一经点破，就好象,“,哥伦布立蛋,”,的故事一样，人人都会做了。,代数是什么？以符号代替数的解题方法就是代数。,代数是从算术精炼出来的结晶，虽平凡但妙用无穷。因此它又叫做广义算术,(generalized arithmetic),或进阶算术,(advanced arithmetic),或普遍算术（,universal arithmetic,）。,什么是代数？,Algebra,一名来自阿拉伯文,al-jabr,，,al,为冠词，,jabr,之意为恢复或还原，解方程式时将负项移至另一边变成正项，也可说是还原，也有接骨术的意思。,中国在,1859,年正式使用代数这个名词（李善商在代微积拾级一书中的序中指出,“,中法之四元，即西法之代数也,”,），在不同的时期有人用算术作为代数的名称，中国古书九章算术其实是一本数学百科全书，代数问题分见于各章，特别是第八章方程，主要是论述线性（一次）联立方程组的解法，秦九韶（,1249的数书九章中有,“,立天元一,”,的术语，天元就是代表未知数，用现在的术语来说就是,“,设未知数为,x,”,。,代数,Algebra,是数学的其中一门分支，可大致分为初等代数学和抽象代数学两部分。,代数的由来,初等代数学：,是指,19,世纪中期以前发展的方程理论，主要研究某一方程,组,是否可解，如何求出方程所有的根,包括近似根,，以及方程的根有何性质等问题。,抽象代数：,是在初等代数学的基础上产生和发展起来的。它起始于十九世纪初，形成于,20,世纪,30,年代。在这期间，挪威数学家阿贝尔,(N.H.Abel),、法国数学家伽罗瓦,(E.Galois),、英国数学家德,摩根,(A.De Morgan),和布尔,(G.Boole),等人都做出了杰出贡献，荷兰数学家范德瓦尔登,(B.L.Van Der Waerden),根据德国数学家诺特,(A.E.Noether),和奥地利数学家阿廷,(E.Artin),的讲稿，于,1930,年和,1931,年分别出版了,近世代数学,一卷和二卷，标志着抽象代数的成熟。,代数系统是以研究数字、文字和更一般元素的运算的规律和由这些运算适合的公理而定义的各种数学结构的性质为中心问题。它对现代数学如扑拓学、泛函分析等以及一些其他科学领域，如计算机科学、编码理论等，都有重要影响和广泛地应用。,代数的由来,PART,01,PART,02,PART,03,代数系统的一般概念,代数系统的基本性质,同态与同构,PART,04,代数系统实例,PART,05,同余、商代数、积代数,内容安排,定义,6.1,设,S,是个非空集合且函数,f,：,S,n,S,，则称,f,为,S,上的一个,n,元运算。其中,n,是自然数，称为运算的元数或阶。,当,n,=1,时，称,f,为一元运算，当,n,=2,时，称,f,为二元运算，等等。,定义,6.2,如果对给定集合的成员进行运算，从而产生了象点，而该象点又是同一集合的成员，则称此集合在该运算下是封闭的，这种性质成为闭包性或封装性。,注意到，,n,元运算是个闭运算，因为经运算后产生的象仍在同一个集合中。封闭性表明了,n,元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算中起着特殊的作用，称它为,S,中的特异元或常数。,6.1,代数系统的定义,运算的例子很多。例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。,6.1,代数系统的定义,运算表：表示有穷集上的一元和二元运算,6.1,代数系统的定义,二元运算的运算表 一元运算的运算表,在本章讨论的代数结构中，主要限于一元和二元运算。将用,、或 等符号表示一元运算符；用,、,、*、等表示二元运算符。一元运算符常常习惯于前置、顶置或肩置，如,x,、,x,；而二元运算符习惯于前置、中置或后置，如：,+,xy,，,x,+,y,，,xy,+,。,有了集合上运算的概念后，便可定义代数系统了。,6.1,代数系统的定义,定义,6.3,设,S,是个非空集合，且,f,i,是,S,上的,n,i,元运算，其中,i,=,1,，,2,，,，,m,。,由,S,及,f,1,，,f,2,，,，,f,m,组成的结构，称为,代数系统,，记作,V,=,。,S,称为代数系统的,载体,，,S,和运算叫做代数系统的成分,.,其中，“定义在,S,上的运算”指设集合,S,，,f,为一个,S,S,的映射，即对任意的,a,S,，存在唯一的,b,S,，使得,b,是,a,在,f,下的像，记为,f,（,a,）,=b,，称,a,是,b,在,f,下的原象。映射,f,又称为函数。,6.1,代数系统的定义,定义,6.4,设,是一个代数系统，且非空集,T,S,在运算,f,1,，,f,2,，,，,f,m,作用下是封闭的，则称,为代数系统,的,子代数系统,，记为,。,定义,6.5,如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是,同类型的代数系统,。如果两个同类型的代数系统规定的运算性质也相同，则称为,同种的,代数系统。,6.1,代数系统的定义,下面举例说明上述各个概念。,例,6.1,，,，,都是代数系统，其中,+,和是,R,上的普通加法和乘法运算，后两个代数系统有两个代数运算。因为，运算,+,在,N,和,Z,中是封闭的，运算,+,和,*,在,R,中是封闭的。,例,6.2,设,S,是非空集合，,P,(,S,),是它的幂集。对任意集合,A,，,B,P,(,S,),上的运算,和,如下,:,A,B,=(,A,-,B,)(,B,-,A,),A,B,=,A,B,则,是一代数系统。因为，显然,和,是闭运算。,6.1,代数系统的定义,例,6.3,是代数系统，其中,M,n,(R),为,n,阶实矩阵，,+,和,分别表示,n,阶,(n2),实矩阵的加法和乘法,.,例,6.4,是代数系统，其中,Z,n,0,1,n,-1,，,和分别表示模,n,的加法和乘法，,x,y,Z,n,，,x,y,=(,x,y,)mod,n,，,x,y,=(,xy,)mod,n,。,有的代数系统定义指定了,S,中的特殊元素，称为,代数常数,例如二元运算的单位元,.,有时也将代数常数作为系统的成分,.,6.1,代数系统的定义,例,6.5,代数系统,有个特殊元素,0,，对加法运算它的参与不影响计算结果，也可记为,；,对于运算和的有特殊元素分别为,和,S,，它们对分别参与和的运算不影响计算结果，同样可记为,。,在结束本节时，声明记号,即为一代数系统，除特别指明外，运算符,f,1,，,f,2,，,，,f,m,均为二元运算。根据需要对,S,及,f,1,f,2,，,，,f,m,可置不同的集合符和运算符。,6.1,代数系统的定义,PART,01,PART,02,PART,03,代数系统的一般概念,代数系统的基本性质,同态与同构,PART,04,代数系统实例,PART,05,同余、商代数、积代数,对于代数系统的性质的考察方法不是一个一个研究各个结构，而是列举一组性质，并且对于具有这些性质的任何代数结构推导可能的结论。把那些被选出的性质看成是公理并且由这些公理推导出的任何有效结论，对于满足这些公理的任何代数结构也都必定成立。,因此，为了作出这样的讨论，将不考虑任何特定的集合，也不给所涉及到的运算赋予任何特定的含义。这种系统的集合及集合上的诸运算仅仅看成是一些符号，或更确切地说，它们都是些抽象对象。因此，与此相应的代数系统，通常称为抽象代数。对于那些特定的代数系统只能是具有基本性质中的某些性质。,6.2,代数系统的基本性质,性质,1,结合律,给定,，运算“”满足结合律或“”是可结合的，,(,x,)(,y,)(,z,)(,x,y,z,S,(,x,y,),z,=,x,(,y,z,),。,例,6.9,给定,且对任意,a,，,bA,有,ab=b,。证明运算“”是可结合的。,6.2,代数系统的基本性质,性质,2,交换律,给定,，运算“”满足交换律或“”是可交换的：,(,x,)(,y,)(,x,y,S,x,y,=,y,x,),例,6.11,给定,其中,Q,为有理数集合，并且对任意,a,，,b,Q,有,a,*,b,=,a,+,b,-,a,b,，问运算*是否可交换,?,可见，如果一代数结构中的运算是可结合和可交换的，那么，在计算,a,1,a,2,a,m,时可按任意次序计算其值。特别当,a,1,=,a,2,=,a,m,=,a,时，则,a,1,a,2,a,m,=,a,m,。称,a,m,为,a,的,m,次幂，,m,称,a,的指数。,6.2,代数系统的基本性质,下面给出,a,m,的归纳定义：,设有,且,a,S,。对于,m,N,+,，其中,N,+,表示正整数集合，可有,(1),a,1,=,a,a,m,+1,=,a,m,a,由此利用归纳法不难证明指数定律：,(1),a,m,a,n,=,a,m,+,n,(2),(,a,m,),n,=,a,mn,这里，,m,，,n,N,+,。,似地定义某代数结构中的负幂和给出负指数定律。,6.2,代数系统的基本性质,性质,3,分配率,一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。,给定,，运算对于*满足左分配律，或者对于*是可左分配的，即,(,x,)(,y,)(,z,)(,x,，,y,，,z,S,x,(,y,*,z,)=(,x,y,)*(,x,z,),。运算对于*满足右分配律，或者对于*是可右分配的，,即,(,x,)(,y,)(,z,)(,x,，,y,，,z,S,(,y,*,z,),x,=(,y,x,)*(,z,x,),。,类似地可定义*对于是满足左或右分配律。,若对于*即满足左分配律又满足右分配律，则称对于*满足分配律或是可分配的。同样可定义*对于满足分配律。,6.2,代数系统的基本性质,由定义不难证明下面定理：,定理,6.2,给定,且是可交换的。如果对于*满足左或右分配律，则对于*满足分配律。,例,6.12,给定,，其中,B,=0,，,1,。表,6.2.1,分别定义了运算和*，问运算对于*是可分配的吗,?*,对于呢？,上表常常称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。对于集合,S,的基数很小，特别是,2,或,3,时，代数结构中运算常常用这种表给出。优点是简明直观，一目了然。,6.2,代数系统的基本性质,0 1,0 1,0 0 0 0 0 1,1 0 1 1 1 1,性质,4,吸收率,给定,，则,对于*满足左吸收律：,(,x,)(,y,)(,x,，,y,S,x,(,x,*,y,)=,x,),对于*满足右吸收律：,(,x,)(,y,)(,x,，,y,S,(,x,*,y,),x,=,x,),若对于*既满足左吸收律又满足右吸收律，则称对于*满足吸收律或者可吸收的。,*对于满足左、右吸收律和吸收律类似地定义。,若对于*是可吸收的且*对于也是可吸收的，则和*是互为吸收的或和*同时满足吸收律。,6.2,代数系统的基本性质,例,6.14,给定,，其中,N,是自然数集合，和*定义如下：,对任意,a,，,b,N,有,a,b,=,max,a,，,b,，,a,*,b,=,min,a,，,b,，试证，和*互为吸收的。,6.2,代数系统的基本性质,性质,5,幺元或单位元,给定,且,e,l,，,e,r,，,e,S,，则,e,l,为关于的左幺元,:(,x,)(,x,S,e,l,x,=,x,),e,r,为关于的右幺元,:(,x,)(,x,S,x,e,r,=,x,),若,e,既为的左幺元又为的右幺元，称,e,为关于的幺元。亦可定义如下：,e,为关于的幺元：,(,x,)(,x,S,e,x,=,x,e,=,x,),6.2,代数系统的基本性质,例,6.15,给定,，表,6.4,，表,6.5,和表,6.6,分别给出*的不同定义的运算表，试指出左幺元、右幺元及幺元。,表,6.4,表,6.5,表,6.6,*,6.2,代数系统的基本性质,定理,6.3,给定,且,e,l,和,e,r,分别关于的左、右幺元，则,e,l,=,e,r,=,e,且幺元,e,惟一。,性质,6,零元,给定,及,l,，,r,，,S,，则,l,为关于*的左零元：,(,x,)(,x,S,l,*,x,=,l,),r,为关于*的右零元：,(,x,)(,x,S,x,*,r,=,r,),为关于*的零元：,(,x,)(,x,S,*,x,=,x,*=),例,6.17,在例,6.15,中，*如表,64,所定义，,是*的零元；*如表,6.2.3,所定义，,和,都是*的左零元；*如表,6.2.4,所定义，,是*的右零元。,6.2,代数系统的基本性质,定理,6.2.4,给定,且,l,和,r,分别为关于的左零元和右零元，则,l,=,r,=,且零元,是惟一的。,定理,6.2.5,给定,且,|,S,|,1,。如果,，,e,S,，其中,和,e,分别为关于的零元和幺元，则,e,。,6.2,代数系统的基本性质,性质,7,等幂律与等幂元,给定,，则“”是等幂的或“”满足等幂律：,(,x,)(,x,S,x,x,=,x,),给定,且,x,S,，则,x,是关于“”的等幂元：,x,x,=,x,于是，不难证明下面定理：,定理,6.6,若,x,是,中关于的等幂元，对于任意正整数,n,，则,x,n,=,x,。,例,6.19,给定,，其中,P,(,S,),是集合,S,的幂集，和分别为集合的并和交运算。验证：和是等幂的,6.2,代数系统的基本性质,性质,8,逆元,给定,且幺元,e,，,x,S,，则,x,为关于的左逆元：,(,y,)(,y,S,x,y,=,e,),x,为关于的右逆元：,(,y,)(,y,S,y,x,=,e,),x,为关于可逆的：,(,y,)(,y,S,y,x,=,x,y,=,e,),给定,及幺元,e,；,x,，,y,S,，则,y,为,x,的左逆元：,y,x,=,y,为,x,的右逆元：,x,y,=,e,y,为,x,的逆元：,y,x,=,x,y,=,e,6.2,代数系统的基本性质,显然，若,y,是,x,的逆元，则,x,也是,y,的逆元，因此称,x,与,y,互为逆元。通常,x,的逆元表为,x,-1,。,一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是惟一的。,例,6.20,给定,，其中,S,=,，,，,，,，,且*的定义如表,6.10,所示。试指出该代数结构中各元素的左、右逆元情况,6.2,代数系统的基本性质,表,6.10,*,定理,6.7,给定,及幺元,e,S,。如果是可结合的并且一个元素,x,的左逆元,x,l,-1,和右逆元,x,r,-,1,存在，则,x,l,-1,=,x,r,-1,。,定理,6.8,给定,及幺元,e,S,。如果是可结合的并且,x,的逆元,x,-1,存在，则,x,-1,是惟一的。,例如在例,6.1,中，显然,中运算,+,和,都是可结合的，而,1,和,0,分别为,和,+,的幺元，故可验证，对于,来说，除,0,外每个元素,r,R,都有逆元,1/,r,；对于,+,而言，对每个元素,r,R,都有逆元,(-,r,),。,6.2,代数系统的基本性质,性质,9,可约率与可约元,给定,且零元,S,，则,满足左可约律或是左可约的：,(,x,)(,y,)(,z,)(,x,，,y,，,z,S,x,x,y,=,x,z,),y,=,z,),，并称,x,是关于的左可约元。,满足右可约律或是右可约的：,(,x,)(,y,)(,z,)(,x,，,y,，,z,S,x,y,x,=,z,x,),y,=,z,),，并称,x,是关于的右可约元。,若既满足左可约律又满足右可约律或既是左可约又是右可约的，则称满足可约律或是可约的。,若,x,既是关于的左可约元又是关于的右可约元，则称,x,是关于的可约元。,6.2,代数系统的基本性质,可约律与可约元也可形式地定义如下：,满足可约律：,(,x,)(,y,)(,z,)(,x,，,y,，,z,S,x,(,x,y,=,x,z,y,x,=,z,x,),y,=,z,),给定,且零元,，,x,S,。,x,是关于的可约元：,(,y,)(,z,)(,y,，,z,S,x,(,x,y,)=,x,z,y,x,=,z,x,),y,=,z,),。,6.2,代数系统的基本性质,例,6.24,给定,，其中,Z,是整数集合，,是一般乘法运算。显然，每个非零整数都是可约元，而且运算,满足可约律。,定理,6.9,给定,且*是可结合的，如果,x,是关于*可逆的且,x,，则,x,也是关于*的可约元。,6.2,代数系统的基本性质,最后，作一补充说明，用运算表定义一代数结构的运算，从表上能很好地反映出关于运算的各种性质。为确定起见，假定,及,x,，,y,，,，,e,S,。,(1),运算*具有封闭性，当且仅当表中的每个元素都属于,S,。,(2),运算*满足交换律，当且仅当表关于主对角线是对称的。,(3),运算*是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元素相同,(4),元素,x,是关于*的左零元，当且仅当,x,所对应的行中的每个元素都与,x,相同；元素,y,是关于*的右零元，当且仅当,y,所对应的列中的每个元素都与,y,相同；元素,是关于*的零元，当且仅当,所对应的行和列中的每个元素都与,相同。,6.2,代数系统的基本性质,(5),元素,x,为关于*的左幺元，当且仅当,x,所对应的行中元素依次与行表头元素相同；元素,y,为关于*的右幺元，当且仅当,y,所对应的列中元素依次与列表头元素相同；元素,e,是关于*的幺元，当且仅当,e,所对应的行和列中元素分别依次地与行表头元素和列表头元素相同。,(6),x,为关于*的左逆元，当且仅当位于,x,所在行的元素中至少存在一个幺元，,y,为关于*的右逆元，当且仅当位于,y,所在列的元素中至少存在一个幺元；,x,与,y,互为逆元，当且仅当位于,x,所在行和,y,所在列的元素以及,y,所在行和,x,所在列的元素都是幺元。,6.2,代数系统的基本性质,6.2,代数系统的基本性质,PART,01,PART,02,PART,03,代数系统的一般概念,代数系统的基本性质,同态与同构,PART,04,代数系统实例,PART,05,同余、商代数、积代数,6.3,同构与同态,6.3.1,同态,定义,6.6,：,设有两个代数系统,，,，其中,*,与,均为二元运算，则称,同态于,，若存在映射,f,：,A,B,，使得对任意的,a,，,b,A,。有：,f,（,a*b,）,=f,（,a,）,f,（,b,）,其中,f,（,a,），,f,（,b,）与,f,（,a*b,）均为,B,中的元素。此时称,f,为代数系统,到代数系统,的一个同态映射。,6.3,同构与同态,例,6.25,：,考虑带加法运算的,自然数,，即代数系统,。保持加法不变的函数有如下性质：,f(a+b)=f(a)+f(b).,不妨取映射,f(x)=3x,，,f,（,x,）就是这样的一个同态，因为,f(a+b)=3(a+b)=3a+3b=f(a)+f(b),。注意这个同态从自然数映射回自然数，代数系统,到代数系统,在,f,（,x,）的映射下是同态的，这个性质也成为,自同态,，,f,（,x,）称为,自同态映射,。,同态不必从集合映射到带相同运算的集合。,6.3,同构与同态,例,6.26,：,考虑保持运算的从带加法的实数集到带乘法的正实数集，即考虑两个代数系统，,和,其中,+,，,*,是普通的加法和乘法，,R,+,表示正实数集合。保持运算的函数满足：,f(a+b)=f(a)*f(b),，因为加法是第一个集合的运算而乘法是第二个集合的运算。指数定律表明,f(x)=e,x,满足如下条件,:2+3=5,变为,e,2,*e,3,=e,5,.,因此取,R,到,R,+,的映射为如上的指数函数，则,和,在,f,（,x,）的映射下是同态的。,同态的一个特别重要的属性是幺元具有保持性。也即，如果幺元存在，它将被保持，一个集合的幺元被映射为另一个集合中的幺元。注意在例,6.10,中，,f(0)=0,而零是加法幺元。在例,6.11,中，,f(0)=1,，因为,0,是加法幺元，而,1,是乘法幺元，代数系统,的幺元被,f,（,x,）映射到,的幺元。,若考虑集合上的多个运算，则保持所有运算的函数可以视为同态。,6.3,同构与同态,例,6.27,：,设,与,是同类型的，其中,*,为有限字母表上的字母串集合，为并置运算，,N,为自然数集合，,+,为普通加法。若定义,f,：,*,N,为,f,(,x,)=|,x,|,其中,x,*,，这里,|,x,|,表示字母串的长度。,解：,因为对任意,x,，,y,*,，有,f,(,x,y,)=|,x,y,|=|,x,|+|,y,|=,f,(,x,)+,f,(,y,),，故,。,显然，,f,是满射，因此，,f,为从,到,的满同态映射。,6.3,同构与同态,例,6.29,：,考察代数系统,U=,和,V=,，其中,*,是普通意义下的乘法运算。定义,f,：,N,0,1,为,证明：,f,是,U,到,V,的同态映射。,设,是,V,1,=,到,V,2,=,的同态映射，如果,是满射，称,V,1,和,V,2,是,满同态,的，记为,V,1,V,2,；如果,是单射，称,V,1,和,V,2,是,单同态,的；,若存在从,V,1,到,V,2,的满同态,，则称,V,2,为,V,1,在,下的,同态象,。,6.3,同构与同态,6.3.2,同构,定义,6.7,设有两个代数系统,，,，若能在集合,A,与,B,之间构造映射,f,，满足如下要求：,(1),y,B,均,x,A,，使得,y=f(x),。,(2),当,x,1,x,2,A,x,1,x,2,有,f(x,1,),f(x,2,),B,f(x,1,),f(x,2,),。,(3),x,1,x,2,A,有,f(x,1,x,2,)=f(x,1,)f(x,2,),。,则称二个代数系统的结构相同，简称同构，记为,。此时，一个系统的运算性质与规律，可以完全迁移到另一个代数系统中。,6.3,同构与同态,由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它们的所有发生“彼此相通”。这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是相同的。因此，可以根据这些特征来识别同构的代数系统。,6.3,同构与同态,一般来说，如果忽略掉同构的对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的。同构是在数学对象之间定义的一类,映射,它能揭示出在这些对象的属性或者操作之间存在的关系。若两个数学结构之间存在同构映射，那么这两个结构叫做是同构的。,6.3,同构与同态,例,6.32,：,V=,，给定,a,Z,，令,则对,所以,是,V,到,V,的同态，即,自同态,。,当,a=0,时，有,称,为,零同态,。,当,a=1,时，有,即恒等映射，它是双射的，这时，,是,V,的,自同构,，同理可证,也是,V,的自同构。,当,且,时，易证,是单射的，这时,是,V,的,单自同态,。,6.3,同构与同态,例,6.34,：,令,与,是同类型的，其中,F,=,f,0,，,f,1,，,f,2,，,f,3,，“”定义如表,6.13,所示；,Z,4,=0,，,1,，,2,，,3,，,+,4,定义如表,6.14,，,试说明,。,表,6.13,f,0,f,1,f,2,f,3,f,0,f,0,f,1,f,2,f,3,f,1,f,1,f,2,f,3,f,0,f,2,f,2,f,3,f,0,f,1,f,3,f,3,f,0,f,1,f,2,表,6.14,+4,0 1 2 3,0 0 1 2 3,1 1 2 3 0,2 2 3 0 1,3 3 0 1 2,6.3,同构与同态,例,6.35,：,给定,，其中,S,=,，,A,，,B,，,C,，和是一般的集合运算；又有,，这里,T,=1,，,2,，,5,，,10,，且对于,a,，,b,T,有,a,b,=lcm,a,，,b,，,a,b,=,gcd,a,，,b,，表,6.15,至表,6.18,给出四个运算表。试说明,其中,lcm,a,，,b,表示,a,和,b,的最小公倍数，,gcd,a,，,b,表示,a,和,b,的最大公约数,表,6.15,A,B,C,A,B,C,A,A,A,C,C,B B C B C,C C C C C,6.3,同构与同态,表,6.,16,A,B,C,A,A,A,B,B,B,C,A B C,表,6.17,1 2 5 10,1 1 2 5 10,2 2 2 10 10,5 5 10 5 10,10 10 10 10 10,表,6.18,1 2 5 10,1 1 1 1 1,2 1 2 1 2,5 1 1 5 5,10 1 2 5 10,6.3,同构与同态,6.3.3,同构与同构的性质,定理,6.10,：,给定,且,f,为其满同态映射，则,(,a,),如果和,*,满足结合律，则,和,也满足结合律。,(,b,),如果和,*,满足交换律，则,和,也满足交换律。,(,c,),如果对于或,*,对于满足分配律，则,对于,或,对于,也相应满足分配律。,(,d,),如果对于,*,或,*,对于满足吸收律，则,对于,或,对于,也满足吸收律。,(,e,),如果和,*,满足等幂律，则,和,也满足等幂律。,(,f,),如果,e,1,和,e,2,分别是关于和,*,的幺元，则,f,(,e,1,),和,f,(,e,2,),分别为关于,和,的幺元。,(,g,),如果,1,和,2,分别是关于和,*,的零元，则,f,(,1,),和,f,(,2,),分别为关于,和,的零元。,(,h,),如果对每个,x,X,均存在关于的逆元,x,-1,，则对每个,f,(,x,),Y,也均存在关于,的逆元,f,(,x1,),；如果对每个,z,X,均存在关于,*,的逆元,Z,-1,，则对每个,f,(,z,),Y,也均存在关于,的逆元,f,(,z,-1,),。,6.3,同构与同态,定理,6.11,:,代数系统间的同构关系是等价关系。,由于同构关系是等价关系，故令所有的代数系统构成一个集合,S,，于是可按同构关系将其分类，得到商集,S,/,。因为同构的代数系统具有相同的性质，故实际上代数系统所需要研究的总体并不是,S,而是,S,/,。,在同态与同构中有一个特例，即具有相同集合的任两个代数系统的同态与同构，这便是自同态与自同构,如例,6.25,和例,6.35,。,6.3,同构与同态,图,6.3,示出了各类同态与同构的关系。图中,H=,同态的集合，,M=,单同态的集合，,P=,满同态的集合，,S=,同构的集合，,N=,子同态的集合，,A=,自同构的集合,.,注意,:M,P=S,S,N=A,(M,N)A,并且,(P,N)A,只包含无限代数结构到自身的同态。,PART,01,PART,02,PART,03,代数系统的一般概念,代数系统的基本性质,同态与同构,PART,04,代数系统实例,PART,05,同余、商代数、积代数,6.4,同余关系,定义,6.8,：,给定,且,E,为,S,中的等价关系。,E,关于有代换性质：,(,x,1,)(,x,2,)(,y,1,)(,y,2,)(,x,1,，,x,2,，,y1,，,y,2,S,x,1,Ex,2,y,1,Ey,2,)(,x,1,y,1,),E,(,x,2,y,2,),。,E,为,中的同余关系：,E,有代换性质。,与此同时，称同余关系,E,的等价类为同余类。,6.4,同余关系,由定义可知，同余关系是代数结构的集合中的等价关系，并且在运算的作用下，能够保持关系的等价类。即在,x,1,y,1,中，如果用集合,S,中的与,x,1,等价的任何其它元素,x,2,代换,x,1,，并且用与,y,1,等价的任何其它元素,y,2,代换,y,1,，则所求的结果,x,2,y,2,与,x,1,y,1,位于同一等价类之中。亦即若,x,1,E,=,x,2,E,并且,y,1,Ey,2,E,，则,x,1,y,1,E,=,x,2,y,2,E,。此外，同余关系与运算密切相关。如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果有，则说该代数结构存在同余关系；否则，同余关系不存在。,6.4,同余关系,定理,6.12,：,设,与,是同类型的且,f,为其同态映射。对应于,f,，定义关系,E,f,如下：,xE,f,y,：,f,(,x,)=,f,(,y,),，,其中,x,，,y,S,则,E,f,是,中的同余关系，并且称,E,f,为由同态映射,f,所诱导的同余关系。,由于同态映射不惟一，根据定理,6(1).4.1,，可以推知同余关系也不惟一。,6.4,同余关系,例,6.37,：,设,与,是同类型的，其中,Z,是整数集合，,B,=0,，,1,，,和,定义如下：,i,=,i,+1,i,Z,b,=(,b,+1)(,mod,2),b,B,又设,f,B,Z,：,f,(,i,)=(,i,)(,mod,2),其中,i,Z,试指出,f,所诱导的同余关系。,6.5,商代数,定义,6.9,：,给定,并且,E,为,S,中的等价关系。,E,关于具有代换性质：,(,x,1,)(,x,2,)(,y,1,)(,y,2,)(,x,1,，,x,2,，,y,1,，,y,2,S,x,1,Ex,2,y,1,Ey,2,)(,x,1,y,1,),E,(,x,2,y,2,),。E,为,中的同余关系：,E,有代换性质。与此同时，称同余关系,E,的等价类为,同余类,。,6.5,商代数,例,6.38,：,给定,，其中,Z,是整数集合，,+,和,*,是一般意义下的加法和乘法。假设,Z,中的关系,R,定义如下：,问，,R,是该结构的同余关系吗，为什么？,6.5,商代数,定义,6.9,：,给定,及其上的同余关系,E,，且由,E,对,S,所产生同余类所构成一个商集,S/E,。若在,S/E,中定义运算,*,如下：,xE*yE=x,yE,其中,xE,，,yE,S/E,于是,构成了一个代数结构，则称,为代数结构,的,商代数,。,例,6.39,给定,，其中,N,是自然数集合，,+,是一般意义下加法。又知,其中，,Z,m,=0,1,，,，,m-1,，,+,m,为模,m,加法。并且在,N,中定义关系,E,：,试证明,E,为,中的同余关系，并给出与,E,相关的自然同态映射,g,E,。,6.6,积代数,定义,6.11,：,设,与,是同类型的，而,成为新的代数结构，其中,ST,是集合,S,和集合,T,的笛卡儿积，且,定义如下：,=,，其中,s,1,，,s,2,S,，,t,1,，,t,2,T,。则称,为代数结构,和,的,积代数,，而代数结构,和,称为,的因子代数。,类似地可把积代数的定义推广到任何两个同类型的代数结构。另外，重复地使用定义中的方法，也可以定义任何有限数目的同类型代数结构的积代数。,可以看出，两个代数结构的积代数，与两个因子代数是同一类型的。而且还要注意到，在积代数的定义中，是用因子代数中的相应运算定义了积代数中的运算。,6.6,积代数,例,6.41,：,设集合,A=a,1,a,2,，,B=b,1,b,2,b,3,，,*,和,分别为,A,B,上的二元运算，其运算表如下，求积代数,UV,，其中,U=,V=.,*,a,1,a,2,a,1,a,1,a,2,a,2,a,2,a,1,b,1,b,2,b,3,b,1,b,1,b,1,b,3,b,2,b,2,b,2,b,3,b,3,b,1,b,3,b,3,6.6,积代数,定理,6.12,：,设,S,1,=,，,S,2,=,是同类型的代数系统，,S=,为,S,1,和,S,2,的积代数。,如果,和,运算可交换（可结合、幂等），那么,运算也是可交换（可结合、幂等）。,如果,e,1,和,e,2,分别（,1,和,2,）是,和,运算的单位元（零元），那么,也是,运算的单位元。,如果,x,和,y,分别是,和,运算的可逆元素，那么,也是,运算的可逆元素，其逆元是,PART,01,PART,02,PART,03,代数系统的一般概念,代数系统的基本性质,同态与同构,PART,04,代数系统实例,PART,05,同余、商代数、积代数,6.7,代数系统实例,按下面的条件，给出尽可能简单的代数系统实例。给出的代数系统须含有一个二元运算，运算可用运算表定义，给出的代数系统可以同时满足,1,个或多个条件。,(1),有幺元；,(2),有零元；,(3),同时有幺元和零元；,(4),有幺元但无零元；,(5),有零元但无幺元；,(6),运算不可交换；,(7),运算不可结合；,(8),有左零元，无右零元；,(9),有右幺元，但无左幺元；,(10),有幺元，每个元素有逆元；,(11),满足幂等性；,(12),满足消去律,END,