离散数学第十二章-代数结构基本概念及性质省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十二章 代数结构概念及性质,12.1 代数结构定义与例,12.2 代数结构基本性质,12.3 同态与同构,12.4 同余关系,12.5 商代数,12.6 积代数,第1页,12.1 代数结构定义与例,在正式给出代数结构定义之前，先来说明什么是在一个集合上运算，因为运算这个概念是代数结构中不可缺乏基本概念。,定义12.1.1,设,S,是个非空集合且函数 或,f,:,S,n,S,，则称,f,为一个,n,元运算。其中,n,是自然数，称为运算元数或阶。当,n,=1时，称,f,为一元运算，当,n,=2时，称,f,为二元运算，等等。,第2页,注意，,n,元运算首先是一个,函数,，其次是个,闭运算,(所谓,闭运算,是指：集合上运算，其运算结果都在原来集合中，我们把含有这种特征运算称作,封闭,，简称,闭运算,)。封闭性表明了,n,元运算与普通函数区分之处。另外，有些运算存在幺元或零元，它在运算中起着特殊作用，称它为,S,中特异元或常数。,第3页,运算例子很多，比如，在数理逻辑中，否定是谓词集合上一元运算，合取和析取是谓词集合上二元运算；在集合论中，并与交是集合上二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。,第4页,在下面讨论代数结构中，主要限于一元和二元运算，将用、,或等符号表示一元运算符；用,、,、,、,、等表示二元运算符，一元运算符经常习惯于前置、顶置或肩置，如,x,、,x,；而二元运算符习惯于前置、中置或后置，如：+,xy,，,x,+,y,，,xy,+。,有了集合上运算概念后，便可定义代数结构了。,第5页,定义12.1.2,设,S,是个非空集合且,f,i,是,S,上,n,i,元运算，其中,i,=1，2，,m,。由,S,及,f,1,，,f,2,，,f,m,组成结构，称为代数结构，记作。,例：设,Z,是整数集，“”是,Z,上普通加法运算，则是一个代数结构。,例：设,R,是实数集,，,“”与“”是实数集,R,上普通加法和乘法运算，则是一个代数结构。第6页,例：我们能够结构下述一个代数结构：,设有一个由有限个字母组成集合,，叫,字母表,，在上任意长字母串，叫做上句子或字符串，串中字母个数,m,叫这个串长度，我们假定当一个字长度,m,=0时用符号,表示，它叫做空串。这么我们能够结构一个在上全部串集合,*,。,其次，我们定义一个在,*,上运算“,/,”并置运算或者连接运算，设,，,*,，则,/,。经过并置运算将两个串联成一个新串，而此联成新串也在,*,内，这么结构 是一个代数结构,第7页,假如令,+,*,，则也是一个代数结构。,这两种代数结构都是计算机科学 中经常要用到代数结构。,第8页,例：设有一计算机它字长是32位，它以定点加、减、乘、除及逻辑加、逻辑乘为运算指令，并分别用0,1,，,0,2,，,0,6,表示之。,则在该计算机中由2,32,有限个不一样数字所组成集合,S,以及计算机运算型机器指令就组成了一个代数结构,。,第9页,所以，一个代数结构需要满足二个条件：(1)有一个非空集合,S,(2)在集合,S,上定义运算一定是封闭,第10页,另外，我们把集合,S,基数即|,S,|，定义为代数结构基数。假如,S,是有限集合，则说代数结构是有限代数结构；不然便说是无穷代数结构.,有时，要考查两个或多个代数结构，这里就有个是否同类型之说，请看下面定义：,第11页,定义12.1.3,设两个代数结构和，假如,f,i,和,g,i,(1,i,m,)含有相同元数，则称这两个代数结构是同类型。,可见，判定两个代数结构是否同类型，主要是对其运算进行考查：,两个代数结构是否有相同个数运算符；,每个相对应运算符是否有相同元数。,第12页,例：代数结构与代数结构是相同类型，因为它们都有一个二元运算符。,例：代数结构与类型是不相同，因为它们运算符个数不一样。,第13页,例：,设,S,是非空集合，,P,(,S,)是它幂集。对任意集合,A,，,B,P,(,S,)上运算,和,以下:,A,B,=(,A,B,)(,B,A,),A,B,=,A,B,则是一代数结构。因为，显然,和,是闭运算。,与是同类型代数结构。,有时还需要在代数结构中集合某个子集上讨论其性质，这就引出子代数结构概念.,第14页,定义12.1.4,设是一代数结构，且非空集,T,S,在运算,f,1,，,f,2,，,f,m,作用下是封闭，且,T,含有与,S,中相同特异元，则称为代数结构子代数。记为,。,例：设,E,是全部偶数所组成集合，则代数结构是一个子代数结构,例：显然，,.,第15页,12.2 代数结构基本性质,所谓代数结构性质即是结构中任何运算所含有性质。以下我们均假设运算为二元运算。,1.结合律,给定，则运算“”满足结合律或“”是可结合，即,(,x,)(,y,)(,z,)(,x,y,z,S,(,x,y,),z,=,x,(,y,z,),第16页,例12.2.1,给定且对任意,ab,A,有,a,b,=,b,。证实运算“”是可结合。,证实：因为对任意,a,，,b,，,c,A,(,a,b,),c,=,b,c,=,ca,(,b,c,)=,a,c,=,c,故(,a,b,),c,=,a,(,b,c,),注意，不是任何代数结构上运算都满足结合律，如整数集上“”运算就不满足结合律。如：5(21)4,不过(52)12.,第17页,2.交换律,给定，则运算“”满足交换律或“”是可交换，即,(,x,)(,y,)(,x,y,S,x,y,=,y,x,)。,例12.2.2,给定，其中,Q,为有理数集合，而且对任意,a,，,b,Q,有,a,b,=,a,+,b,-,a,b,，问运算,是否可交换?,证：,a,b,=,a,+,b,-,a,b,=,b,+,a,-,b,a,b,a,，故运算,是可交换。,第18页,一样，并不是全部代数结构上运算均满足交换律，如矩阵乘法就不满足交换律。,易见，假如一代数结构中运算是可结合和可交换，那么，在计算,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,指数。,下面给出,a,m,归纳定义：,第19页,设有且,a,S,，对于,m,Z,+,，其中,Z,+,表示正整数集合，可有：,(1),a,1,=,a,(2),a,m,+1,=,a,m,a,由此利用归纳法不难证实指数定律：,(1),a,m,a,n,=,a,m,+,n,(2)(,a,m,),n,=,a,mn,这里，,m,n,Z,+,。,类似地定义某代数结构中负幂和给出负指数定律。,第20页,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),第21页,类似地可定义对于是满足左或右分配律.,若对于既满足左分配律又满足右分配律，则称,对于满足分配律,或是可分配。一样可定义对于满足分配律。,由定义不难证实下面定理：,定理12.2.1,给定且是,可交换,。假如对于满足左,或,右分配律，则对于满足分配律。,第22页,例12.2.3,给定，其中,B,=0,1。表12.2.1分别定义了运算和，问运算对于是可分配吗？对于呢？,第23页,形如表12.2.1表经常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。当集合,S,基数很小，尤其限于几个时，代数结构中运算常惯用这种表给出。其优点简明直观，一目了然。,解 能够验证对于是可分配，但对于并非如此。因为,1(01),(10)(11),1,0 1,0,0,第24页,4.吸收律,给定，则,对于满足左吸收律:=(,x,)(,y,)(,x,y,S,x,(,x,y,)=,x,),对于满足右吸收律:=(,x,)(,y,)(,x,y,S,(,x,y,),x,=,x,),第25页,若对于既满足左吸收律又满足右吸收律，则称对于满足吸收律或可吸收。,对于 和吸收律类似地定义。,若对于是可吸收且对于也是可吸收，则和是互为吸收或和同时满足吸收律。,第26页,例12.2.4,给定，其中,N,是自然数集合，和,定义以下：,对任意,a,，,b,N,有,a,b,=,max,a,，,b,a,b,=,min,a,，,b,，试证，和,互为吸收。,证实：不妨假设,a,b,a,(,a,b,),=max,a,，,min,a,，,b,=,a,(,a,b,),a=max,min,a,，,b,，,a,=,a,故对于,满足吸收律。,同理可证，,对于,满足吸收律。故,和,互为吸收。,第27页,5.等幂律与等幂元,给定，则,“”是,等幂,或“”满足等幂律:=(,x,)(,x,S,x,x,=,x,),给定且,x,S,，则,x,是关于“”,等幂元,:=,x,x,=,x,于是，不难证实下面定理：,定理12.2.2,若,x,是中关于等幂元，对于任意正整数,n,，则,x,n,=,x,。,第28页,例122.5,给定，其中,P,(,S,)是集合,S,幂集，和分别为集合并和交运算。验证：和是等幂。,证：对任意,A,P,(,S,)，有,A,A,=,A,和,A,A,=,A,，故和是等幂。,第29页,6.幺元或单位元,给定且,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,)。,第30页,定理12.2.3,给定且,e,l,和,e,r,分别是关于左、右幺元，则,e,l,=,e,r,=,e,且幺元,e,唯一。,例：实数集,R,上代数结构“”运算幺元为1，因为对任意,x,R,有,x,11,x,x,。而“”运算幺元为0，因为对任意,x,R,有,x,00,x,x,。,例：前面例子中关于串并置运算，它单位元素是空串,，因为对任一串,A,，都有,/A,=,A,/,=,A,。,第31页,7.零元,给定及,l,，,r,，,S,，则,l,为关于左零元,:=(,x,)(,x,S,l,x,=,l,),r,为关于右零元,:=(,x,)(,x,S,x,r,=,r,),为关于零元,:=(,x,)(,x,S,x,=,x,=,),第32页,定理12.2.4,给定且,l,和,r,分别为关于左零元和右零元，则,l,=,r,=,且零元,是唯一。,定理12.2.5,给定且|,S,|1。假如,，,e,S,，其中,和,e,分别为关于零元和幺元，则,e,。,第33页,例：代数结构上零元是“0”，因为对于任何整数,x,，都有,x,00,x,0。,例：正整数集Z,+,上运算“min”，叫“取最小”运算。min(a,b)为取a,b最小者。代数结构中对应于运算“min”零元为1。,第34页,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,),第35页,给定及幺元,e,；,x,，,y,S,，则,y,为,x,左逆元:=,y,x,=,e,y,为,x,右逆元:=,x,y,=,e,y,为,x,逆元:=,y,x,=,x,y,=,e,第36页,显然，若,y,是,x,逆元，则,x,也是,y,逆元，所以称,x,与,y,互为逆元。通常,x,逆元表示为,x,-1,。,普通地说来，一个元素左逆元不一定等于该元素右逆元。而且，一个元素能够有左逆元而没有右逆元，反之亦然。甚至一个元素左或右逆元还能够不是唯一。,第37页,定理12.2.6,给定及幺元,e,S,。假如是可结合而且一个元素,x,左逆元,xl,-1,和右逆元,x,r,-1,存在，则,x,l,-1,=,x,r,-1,。,定理12.2.7,给定及幺元,e,S,。假如是可结合而且,x,逆元,x,-1,存在，则,x,-1,是唯一。,第38页,例：代数结构上幺元是“0”，对于任何整数,x,，它逆元是,x,，因为,x,(,x,)0。,例：代数结构中0和1分别为和幺元。对于“”，对每个元素,r,R,都有逆元,r,；对于“”，对每个元素,r,R,都有逆元1/,r(r,0),。,第39页,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,是关于右可约元。,第40页,若既满足左可约律又满足右可约律或既是左可约又是右可约，则称满足可约律或是可约。,若,x,既是关于左可约元又是关于右可约元，则称,x,是关于可约元。可约律与可约元也可形式地定义以下：,第41页,满足可约律,:=(,x,)(,y,)(,z,)(,x,y,z,S,x,(,x,y,=,x,z,y,x,=,z,x,),y,=,z,),x,是关于可约元,:=(,y,)(,z,)(,y,z,S,x,(,x,y,)=,x,z,y,x,=,z,x,),y,=,z,),第42页,例：给定，其,Z,是整数集合，是普通乘法运算。显然，每个非零整数都是可约元，而且运算满足可约律。,第43页,定理12.2.8,给定且是可结合，假如,x,是关于可逆且,x,，则,x,也是关于可约元。,证实,设任意,y,z,S,且有,x,y,=,x,z,或,y,x,=,z,x,。因为是可结合及,x,是关于可逆，则有,x,-1,(,x,y,)=(,x,-1,x,),y,=,e,y,=,y,x,-1,(,x,z,)=(,x,-1,x,),z,=,e,z,=,z,第44页,故得,x,y,=,x,z,y,=,z,，故,x,是关于左可约元。一样可证得,yx,=,z,x,y,=,z,，故,x,是关于右可约元。故,x,是关于可约元。,最终，作一补充说明，用运算表定义一代数结构运算，从表上很能反应出关于运算各种性质。为确定起见，假定及,x,，,y,，,，,e,S,。,第45页,(1)运算含有封闭性，当且仅当表中每个元素都属于,S,。,(2)运算满足交换律，当且仅当表关于主对角线是对称。,第46页,(3)运算是等幂，当且仅当表主对角线上每个元素与所在行或列表头元素相同。,a,b,c,a,a,b,b,c,c,第47页,(4)元素,x,是关于左零元，当且仅当,x,所对应行中每个元素都与,x,相同；元素,y,是关于右零元，当且仅当,y,所对应列中每个元素都与,y,相同；元素,是关于零元，当且仅当,所对应行和列中每个元素都与,相同。,l,m,n,a,x,x,x,x,c,左零元,x,m,n,y,a,y,b,y,c,y,右零元,y,m,n,a,c,零元,第48页,(5)元素,x,为关于左幺元，当且仅当,x,所对应行中元素依次与行表头元素相同；元素,y,为关于右幺元，当且仅当,y,所对应列中元素依次与列表头元素相同；元素,e,是关于幺元，当且仅当,e,所对应行和列中元素分别依次与行表头元素和列表头元素相同。,l,m,n,a,x,l,m,n,c,左幺元,x,m,n,y,a,a,b,b,c,c,右幺元,y,m,n,e,a,a,e,m,n,e,c,c,幺元e,第49页,(6),x,为关于左逆元，当且仅当位于,x,所在行元素中最少存在一个幺元，,y,为关于右逆元，当且仅当位于,y,所在列元素中最少存在一个幺元；,x,与,y,互为逆元，当且仅当位于,x,所在行和,y,所在列元素以及,y,所在行和,x,所在列元素都是幺元。,l,m,n,a,x,e,c,左逆元,m,n,y,a,e,b,c,右逆元,m,x,y,x,e,b,y,e,逆元,第50页,例12.2.8,给定，其中,S,=,，,，,，,，,且,定义如表12.2.5所表示。试指出该代数结构中各元素左、右逆元情况。,表12.2.5,解：是幺元；左逆元和右逆元都是，即与互为逆元；左逆元是而右逆元是；有两个左逆元和；右逆元是，但没有左逆元。,e,e,e,e,e,e,e,e,第51页,12.3 同态与同构,本节将说明两个主要概念同态与同构。在以后各节中，它们会经常被使用到。,第52页,定义12.3.1,设与是,同类型,。称同态于或为同态象，记为,，其定义以下：,:=(,f,)(,f,Y,X,(,x,1,)(,x,2,)(,x,1,x,2,X,f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),同时，称,f,为从到同态映射.,能够看出，同态映射,f,无须是惟一。,第53页,X,x,1,x,2,x,3,x,1,x,3,f,(,X,),y,1,=,f,(,x,1,),f,(,x,1)=,f,(,x,2,),y,3,=,f,(,x,3,),y,1,y,3,Y,同态示意图,f,第54页,例12.3.1,给定和，其中,R,是实数集合，和分别是加法和乘法运算，试证,。,证：关键是找一个同态映射。今结构函数,f,R,R,以下：,f,(,x,)=,a,x,其中,a,0,x,R,则,f,为所求同态映射，这是因为对任意,y,z,R,，有,f,(,y,z,)=,a,y,z,a,y,a,z,f,(,y,),f,(,z,),所以，,第55页,两个同类型代数结构间同态定义不但适合用于含有一个二元运算代数结构，也能够推广到含有多个二元运算任何两个同类型代数结构。比如，对于含有两个二元运算两个同类型代数结构和同态定义以下：,:=(,f,)(,f,Y,X,(,x,1,),(,x,2,)(,x,1,x,2,X,(,f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),第56页,定理12.3.1,假如,且,f,为其同态映射，则,。,因为函数,f,Y,X,不一样性质，将给出不一样种类同态定义。,第57页,定义12.3.2,设,且,f,为其同态映射。,(,i,)假如,f,为满射，则称,f,是从到满同态映射。,(,ii,)假如,f,为单射(或一对一映射)，则称,f,为从到单一同态映射。,第58页,(,iii,)假如,f,为双射(或一一对应)，则称,f,为从到,同构映射,。记为,。,显然，若,f,是从到同构映射，则,f,为从到满同态映射及单一同态映射，反之亦然。,第59页,例12.3.3,设与是同类型，其中,*,为有限字母表上字母串集合，为并置运算，,N,为自然数集合，+为普通加法。若定义,f,：,*,N,为,f,(,x,)=|,x,|其中,x,*,，|,x,|表示字母串长度。,因为对任意,x,，,y,*,，有,f,(,x,y,)=|,x,y,|=|,x,|+|,y,|=,f,(,x,)+,f,(,y,)，故,。,显然，,f,是满射，所以，,f,为从到满同态映射。,第60页,例12.3.4,给定，其中Z,为整数集合，+为普通加法。作函数,f,Z,Z,：,f,(,x,)=,kx,，(此处乘法是普通乘法)其中,x,k,Z,则当,k,0时，因为,f,(,y,+,z,)=,k,(,y,+,z,)=,ky,+,kz,=,f,(,y,)+,f,(,z,)，故,f,为到同态映射。又易知,f,为单射，故,f,为到单一同态映射。,当,k,=-1或,k,=1时，,f,为从到同构映射(我们稍后再来证实)。,第61页,综上能够看出，同态映射含有一个特征，即“保持运算”。对于满同态映射来说，它能够保持运算更多性质，为此，给出以下定理：,定理12.3.2,给定,且,f,为其,满同态,映射，则,(,a,)假如和满足结合律，则,和,也满足结合律。,(,b,)假如和满足交换律，则,和,也满足交换律。,第62页,(,c,)假如对于或对于满足分配律，则,对于,或,对于,也对应满足分配律。,(,d,)假如对于或对于满足吸收律，则,对于,或,对于,也满足吸收律。,(,e,)假如和满足等幂律，则,和,也满足等幂律。,(,f,)假如,e,1,和,e,2,分别是关于和幺元，则,f,(,e,1,)和,f,(,e,2,)分别为关于,和,幺元。,第63页,(,g,)假如,1,和,2,分别是关于和零元，则,f,(,1,)和,f,(,2,)分别为关于,和,零元。,(,h,)假如对每个,x,X,均存在关于逆元,x,-1,，则对每个,fx,),Y,也均存在关于,逆元,f,(,x,-1,)；假如对每个,z,X,均存在关于逆元,z,-1,，则对每个,f,(,z,),Y,也均存在关于,逆元,f,(,z,-1,)。,第64页,定理12.3.2告诉我们，对于满同态映射来说，代数结构许多性质都能保持，如结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向，即假如满同态于，则所含有性质，均含有。但反之不然，即所含有一些性质，不一定含有。不尽要问，在怎样条件下，所含有性质都完全含有呢?为了回答这个问题，需要引出两个代数结构同构概念。,第65页,定义12.3.3,设与是同类型。称同构于，记为,，其定义以下：,:=(,f,)(,f,为从到同构映射),或更详细地定义为：,:=(,f,)(,f,Y,X,f,为双射,f,为从到同态映射),第66页,x,1,x,2,x,1,x,2,f,(,x,1,),f,(,x,2,),f,(,x,1,),f,(,x,2,),同构示意图,f,第67页,例 代数结构与是同构。其中,R,为实数，,R,+,为正实数。,证：关键是找一个双射。对 与，有一个函数,h,：,R,+,R,，,h,(,x,)=ln,x,此函数是双射。因为对每个,x,0,均存在一个,y,=ln,x,R,，同时，对每个,y,R,，均存在一个,x,=,e,y,R,+,.又因为,h,(,y,z,)=ln(,y,z,)=lny,ln,z,=,h,(,y,),h,(,z,),故与是同构。,注,：当然，我们也能够取函数,h,(,x,)=lg,x,，,第68页,续,例12.3.4,给定，其中,Z,为整数集合，+为普通加法。作函数,f,Z,Z,：,f,(,x,)=,kx,，(此处乘法是普通乘法)其中,x,k,Z,，则当,k,=-1或,k,=1时，,f,为从到同构映射。,证：先证实当,k,=-1或,k,=1时,f,为双射。因为对每个,x,Z,均存在一个,y,=,kx,(即,y,=,x,或,y,=-,x,),Z,，同时，对每个,y,Z,，均存在一个,x,=,y,/,k,(即,x,=,y,或,x,=-,y,),Z,。(显然，若,k,取,1以外值，,y,/,k,不一定是整数，或者y/,k,无意义，此时,f,就不是双射了.),又因为,f,(,y,+,z,)=,k,(,y,+,z,)=,ky,+,kz,=,f,(,y,)+,f,(,z,)，,故,f,为到同构映射。,第69页,例 代数结构与是同构。其中,M,H,分别表示低电平、高电平，“”表示或门，它们运算表以下。,证：这两个代数结构间存在一个函数,f,:0,1,M,H,，且,f,(0)=,M,f,(1)=,H,，显然这是一个双射，而且有,f,(,x,y,)=,f,(,x,)+,f,(,y,)。故它们是同构。,0,1,0,0,1,1,1,1,M,H,M,M,H,H,H,H,第70页,例 设,S,=4,5,6,在,S,上二元运算“,”其定义以下表所表示。又有,P,=1,2,3及在,P,上二元运算“,”，其运算表以下表所表示。这么所组成两个代数结构与是同构。,证：这两个代数结构间存在一个函数,f,:4,5,61,2,3，,f,(,x,)=,x,-3，其中,x,S,。,显然这是一个双射，而且有,f,(,x,y,)=,f,(,x,),f,(,y,)。故它们是同构。,4,5,6,4,4,5,4,5,4,5,5,6,4,5,6,1,2,3,1,1,2,1,2,1,2,2,3,1,2,3,第71页,由定义可知，同构条件比同态强，关键是同构映射是双射，即一一对应。而同态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单向了，而对保持运算成为双向。两个同构代数，表面上似乎很不相同，但在结构上实际是没有什么差异，只不过是集合中元素名称和运算标识不一样而已，而它们全部发生“彼此相通”。,第72页,这么，当探索新代数结构性质时，假如发觉或者能够证实该结构同构于另外一个性质已知代数结构，便能直接地知道新代数结构各种性质了。对于同构两个代数结构来说，在它们运算表中除了元素和运算标识不一样外，其它一切都是相同。所以，能够依据这些特征来识别同构代数结构。,第73页,下面给出两个二元运算代数结构同构定义,定义,设两个代数结构,与,，假如它们之间存在一个双射,f,：,X,Y,，使得任意,x,1,x,2,X,，有,f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),则说此两个代数结构是同构。,第74页,例12.3.6,给定，其中,S,=,，,A,，,B,，,C,，和是普通集合运算；又有，这里,T,=1，2，5，10，且对于,a,，,b,T,有,a,b,=,lcm,a,，,b,(最小公倍数)，,a,b,=,gcd,a,，,b,(最大条约数)，表12.3.3至表12.3.6给出四个运算表。试说明.,第75页,表12.3.3表12.3.4,表12.3.5表12.3.6,A,B,C,A,B,C,A,A,A,C,C,B,B,C,B,C,C,C,C,C,C,A,B,C,A,A,A,B,B,B,C,A,B,C,1,2,5,10,1,1,2,5,10,2,2,2,10,10,5,5,10,5,10,10,10,10,10,10,1,2,5,10,1,1,1,1,1,2,1,2,1,2,5,1,1,5,5,10,1,2,5,10,第76页,解：令,f,T,S,：,f,(,)=1，,f,(,A,)=2，,f,(,B,)=5，,f,(,C,)=10。显然，,f,是从,S,到,T,双射。经验证，对任意,x,1,x,2,S,，又有,f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),f,(,x,1,x,2,)=,f,(,x,1,),f,(,x,2,),故与是同构。,第77页,同构是一个关系，而且能够证实它是个等价关系，对此有以下定理：,定理12.3.3,代数结构间同构关系是等价关系。,第78页,证实,显然,，因为恒等映射是同构映射。又若,且,f,为其同构映射，则,f,-1,为从到同构映射。所以，,。再令,及,，则,。这里因为若,f,为到同构映射，,g,为到同构映射，则,g,f,为从到同构映射。可见同构关系满足自反性、对称性和传递性。所以，同构关系是等价关系。,第79页,因为同构关系是等价关系，故令全部代数结构组成一个集合,S,，于是可按同构关系将其分类，得到商集,S,/,。因为同构代数结构含有相同性质，故实际上代数结构所需要研究总体并不是,S,而是,S,/,。,在同态与同构中有一个特例，即含有相同集合任两个代数结构同态与同构，这便是,自同态,与,自同构,。,第80页,定义12.3.4,给定及,f,S,S,。,f,为,自同态,映射:=,f,为从到同态映射。,f,为,自同构,映射:=,f,为从到同构映射。,例12.3.7,在例12.3.4中，当,k,0时，,f,=,kx,是从到自同态映射；当,k,=1或,k,=-1时，,f,=,kx,是从到自同构映射。,第81页,12.4 同余关系,本节主要说明同态与同余关系之间联络。主要内容以下：,定义12.4.1,给定，且,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,有代换性质。,第82页,与此同时，称同余关系,E,等价类为同余类。,由定义可知，同余关系是代数结构集合中一类特殊等价关系，而且在运算作用下，能够保持关系等价类。即在,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,位于同一等价类之中。,第83页,亦即若,x,1,E,=,x,2,E,而且,y,1,E,=,y,2,E,，则,x,1,y,1,E,=,x,2,y,2,E,。,另外，同余关系与运算亲密相关。假如一个代数结构中有多个运算，则需要考查等价关系对于,全部,这些运算是否都有代换性质。假如有，则说该代数结构存在同余关系；不然，同余关系不存在。,第84页,x,1,E,x,1,x,2,x,1,y,1,E,x,1,y,1,x,2,y,2,y,1,E,y,1,y,2,同余关系示意图,第85页,例12.4.1,给定，其中,Z,是整数集合，+和,是普通加、乘法。假设Z,中关系,R,定义以下：,i,1,Ri,2,:=|,i,1,|=|,i,2,|，其中,i,1,、,i,2,Z,试问，,R,为该结构同余关系吗？,第86页,解 显然，,R,为,Z,中等价关系。接着先考查,R,对于+运算代换性质：,若取,i,1,-,i,1,i,2,Z,，则有|,i,1,|=|-,i,1,|和|,i,2,|=|,i,2,|，于是，下式,(,i,1,R,(-,i,1,),(,i,2,Ri,2,),(,i,1,+,i,2,),R,(-,i,1,+,i,2,),不真。这是因为前件为真，后件为假。故,R,对于+运算不含有代换性质。,第87页,至此能够说，,R,不是该结构同余关系。但为了熟悉验证一个关系是否为同余关系，还是来考查,R,对于,代换性质。,令,i,1,i,2,j,1,j,2,Z,且,i,1,Ri,2,和,j,1,Rj,2,。于是，对任意,i,1,i,2,j,1,j,2,都有：,(,i,1,Ri,2,)和(,j,1,Rj,2,),(,i,1,j,1,),R,(,i,2,j,2,),所以，,E,对于,含有代换性质。,第88页,可见，考查一个等价关系,E,对于有多个运算代数结构是否为同余关系，这里有个次序先后问题，选择得好，马上就考查到了,E,对某个运算是不含有代换性质，那么便可立刻断定,E,不是该结构同余关系，不然验证应继续下去，直至碰到不含有代换性质运算为止。假如对于全部运算都有代换性质，则,E,为该结构同余关系。,第89页,在例12.4.1中，首先发觉,R,对于+不含有代换性质，那么可断定,R,不是该结构同余关系。假如你首先验证是,R,对于,代换性质，结果,R,对于,有代换性质，至此你只是有希望,E,是同余关系，但还得继续工作，考查,R,对于+代换性质，由此结果才能判定,R,是否为该结构同余关系。,第90页,有了同余关系概念后，现在能够给出它与同态映射关系了，请看下面定理：,定理12.4.1,设与是同类型且,f,为其同态映射。对应于,f,，定义关系,E,f,以下：,xE,f,y,:=,f,(,x,)=,f,(,y,)，其中,x,，,y,S,则,E,f,是中同余关系，而且称,E,f,为,由同态映射,f,所诱导同余关系,。,因为同态映射不唯一，依据定理12.4.1，能够推知同余关系也是不唯一。,第91页,12.5 商代数,定义12.5.1,给定及其上同余关系,E,，且由,E,对,S,所产生同余类组成一个商集,S,/,E,。若在,S,/,E,中定义一个运算以下：,x,E,y,E,=,x,y,E,其中,x,E,，,y,E,S,/,E,于是组成了一个代数结构，则称为代数结构商代数。,第92页,能够看出，给定一个代数结构，利用结构中同余关系能够结构一个新代数结构即商代数，二者有何联络，下面定理指明这一点，即：,一个代数结构与其上商代数同态,。,第93页定理12.5.1,给定及其上商代数，则,。,证：结构一个映射,g,E,：,S,S,/,E,g,E,(,x,)=,x,E,，其中,x,S,，,E,为中同余关系。于是，对于任意,x,y,S,有,g,E,(,x,y,)=,x,y,E,=,x,E,y,E,=,g,E,(,x,),g,E,(,y,),所以，,g,E,为所求同态映射，从而定理得证.,通常，称,g,E,为从,S,到,S,/,E,上,正则映射,，而且称,g,E,为从到与,E,相关,自然同态映射,，简称,自然同态,。,第94页,另外，轻易看出自然同态,g,E,还是一个满同态映射，依据定理12.3.2可知，代数结构各种性质在其商代数中都被保持了下来。,另外，这个定理还告诉我们，任何一个代数结构总能够找到一个与其同态代数结构，这个同态代数结构就是它商代数。,第95页,现在，能够利用自然同态及,E,f,给出一个相关同构主要定理。,定理12.5.2,设,且,f,为其满同态映射，,E,f,为,f,所诱导同余关系，,g,E,f,是从到与,E,f,相关自然同态，则,。,第96页,12.6 积代数,定义12.6.1,设与是同类型，而成为新代数结构，其中,S,T,是集合,S,和集合,T,笛卡儿积，且,定义以下：,=，其中,s,1,，,s,2,S,，,t,1,，,t,2,T,。,则称为代数结构和积代数，而代数结构和称为因子代数。,第97页,类似地可把积代数定义推广到任何两个同类型代数结构。另外，重复地使用定义中方法，也能够定义任何有限数目标同类型代数结构积代数。,能够看出，两个代数结构积代数，与两个因子代数是同一类型。而且还要注意到，在积代数定义中，是用因子代数中对应运算定义了积代数中运算。,第98页,