《离散数学第十二章 代数结构基本概念及性质精选文档.ppt》由会员分享，可在线阅读，更多相关《离散数学第十二章 代数结构基本概念及性质精选文档.ppt（98页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学第十二章离散数学第十二章 代数结构基本概念代数结构基本概念及性质及性质本讲稿第一页，共九十八页12.1 代数结构的定义与例代数结构的定义与例在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运算这个概念是代数结构中不可缺少的基本概念。定义12.1.1 设S是个非空集合且函数 或 f:Sn S，则称 f 为一个n元运算。其中n是自然数，称为运算的元数或阶。当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。本讲稿第二页，共九十八页注意，n元运算首先是一个函数，其次是个闭运算(所谓闭运算是指：集合上的运算，其运算结果都在原来的集合中，我们把具有这种特征的运算称作
2、封闭的，简称闭运算)。封闭性表明了n元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算中起着特殊的作用，称它为S中的特异元或常数。本讲稿第三页，共九十八页运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。本讲稿第四页，共九十八页在下面讨论的代数结构中，主要限于一元和二元运算，将用、或等符号表示一元运算符；用、等表示二元运算符，一元运算符常常习惯于前置、顶置或肩置，如x、x；而二元运算符习惯于前置、中置或后置，如
3、：+xy，x+y，xy+。有了集合上运算的概念后，便可定义代数结构了。本讲稿第五页，共九十八页定义12.1.2 设S是个非空集合且fi是S上的ni元运算，其中i=1，2，m。由S及f1，f2，fm组成的结构，称为代数结构，记作。例：设Z是整数集，“”是Z上的普通加法运算，则是一个代数结构。例：设R是实数集，“”与“”是实数集R上的普通加法和乘法运算，则是一个代数结构。本讲稿第六页，共九十八页例：我们可以构造下述的一个代数结构：设有一个由有限个字母组成的集合，叫字母表，在上任意长的字母串，叫做上句子或字符串，串中字母的个数m叫这个串的长度，我们假定当一个字的长度m=0时用符号表示，它叫做空串。这
4、样我们可以构造一个在上的所有串的集合*。其次，我们定义一个在*上的运算“/”并置运算或者连接运算，设，*，则/。通过并置运算将两个串联成一个新的串，而此联成的新串也在*内，这样构造的 是一个代数结构本讲稿第七页，共九十八页如果令+*，则也是一个代数结构。这两种代数结构都是计算机科学 中经常要用到的代数结构。本讲稿第八页，共九十八页例：设有一计算机它的字长是32位，它以定点加、减、乘、除及逻辑加、逻辑乘为运算指令，并分别用01，02，06表示之。则在该计算机中由232有限个不同的数字所组成的集合S以及计算机的运算型机器指令就构成了一个代数结构。本讲稿第九页，共九十八页因此，一个代数结构需要满足二
5、个条件：(1)有一个非空集合S(2)在集合S上定义的运算一定是封闭的本讲稿第十页，共九十八页此外，我们把集合S的基数即|S|，定义为代数结构的基数。如果S是有限集合，则说代数结构是有限代数结构；否则便说是无穷代数结构.有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义：本讲稿第十一页，共九十八页定义12.1.3 设两个代数结构和，如果fi和gi(1im)具有相同的元数，则称这两个代数结构是同类型的。可见，判定两个代数结构是否同类型，主要是对其运算进行考察：两个代数结构是否有相同个数的运算符；每个相对应的运算符是否有相同的元数。本讲稿第十二页，共九十八页例：代数结构与代数结构
6、是相同类型的，因为它们都有一个二元运算符。例：代数结构与的类型是不相同的，因为它们的运算符的个数不同。本讲稿第十三页，共九十八页例：设S是非空集合，P(S)是它的幂集。对任意集合A，BP(S)上的运算和如下:AB=(AB)(BA)AB=AB则是一代数结构。因为，显然和是闭运算。与是同类型代数结构的。有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数结构的概念.本讲稿第十四页，共九十八页定义12.1.4 设是一代数结构，且非空集TS在运算f1，f2，fm作用下是封闭的，且T含有与S中相同的特异元，则称为代数结构的子代数。记为。例：设 E是所有偶数所组成的集合，则代数结构是的一个子代
7、数结构例：显然，.本讲稿第十五页，共九十八页12.2 代数结构的基本性质代数结构的基本性质所谓代数结构的性质即是结构中任何运算所具有的性质。以下我们均假设运算为二元运算。1.结合律给定，则运算“”满足结合律或“”是可结合的，即(x)(y)(z)(x,y,zS(xy)z=x(yz)本讲稿第十六页，共九十八页例例12.2.1 给定且对任意a，bA有ab=b。证明运算“”是可结合的。证明：因为对任意a，b，cA(ab)c=bc=ca(bc)=ac=c故(ab)c=a(bc)注意，不是任何代数结构上的运算都满足结合律，如整数集上“”运算就不满足结合律。如：5(21)4,但是(52)12.本讲稿第十七页
8、，共九十八页2.交换律给定，则运算“”满足交换律或“”是可交换的，即(x)(y)(x,ySxy=yx)。例例12.2.2 给定，其中Q为有理数集合，并且对任意a，bQ有ab=a+b-ab，问运算是否可交换?证：ab=a+b-ab=b+a-ba b a，故运算是可交换的。本讲稿第十八页，共九十八页同样，并不是所有代数结构上运算均满足交换律，如矩阵的乘法就不满足交换律。易见，如果一代数结构中的运算是可结合和可交换的，那么，在计算a1a2am时可按任意次序计算其值。特 别 当 a1 a2 am a时，则a1a2amam。称am为a的m次幂，m称a的指数。下面给出am的归纳定义：本讲稿第十九页，共九十
9、八页设有且aS，对于mZ+，其中Z+表示正整数集合，可有：(1)a1=a(2)am+1=ama由此利用归纳法不难证明指数定律：(1)aman=am+n(2)(am)n=amn这里，m,nZ+。类似地定义某代数结构中的负幂和给出负指数定律。本讲稿第二十页，共九十八页3.分配律一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。给定，称运算对于满足左分配律，或 者 对 于 是 可 左 分 配 的，如 果 有(x)(y)(z)(x,y,zSx(yz)=(xy)(xz)同理，称运算对于满足右分配律或对于是可右分配的，如果有(x)(y)(z)(x,y,zS(yz)x=(yx)(zx)本
10、讲稿第二十一页，共九十八页类似地可定义对于是满足左或右分配律.若对于既满足左分配律又满足右分配律，则称对于满足分配律或是可分配的。同样可定义对于满足分配律。由定义不难证明下面定理：定理定理12.2.1 给定且是可交换的。如果对于满足左或右分配律，则对于满足分配律。本讲稿第二十二页，共九十八页例例12.2.3 给定，其中B=0,1。表12.2.1分别定义了运算和，问运算对于是可分配的吗？对于呢？本讲稿第二十三页，共九十八页形如表12.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。当集合S的基数很小，特别限于几个时，代数结构中运算常常用这种表给出。其优
11、点简明直观，一目了然。解 可以验证对于是可分配的，但对于并非如此。因为1(01)(10)(11)1 0 1 0 0本讲稿第二十四页，共九十八页4.吸收律给定，则对于满足左吸收律:=(x)(y)(x,ySx(xy)=x)对于满足右吸收律:=(x)(y)(x,yS(xy)x=x)本讲稿第二十五页，共九十八页若对于既满足左吸收律又满足右吸收律，则称对于满足吸收律或可吸收的。对于 和吸收律类似地定义。若对于是可吸收的且对于也是可吸收的，则和是互为吸收的或和同时满足吸收律。本讲稿第二十六页，共九十八页例例12.2.4 给定，其中N是自然数集合，和定义如下：对任意a，bN有ab=maxa，b，a b=mi
12、na，b，试证，和互为吸收的。证明：不妨假设aba(ab)=maxa，mina，b=a(ab)a=maxmina，b，a=a故对于满足吸收律。同理可证，对于满足吸收律。故和互为吸收的。本讲稿第二十七页，共九十八页5.等幂律与等幂元给定，则“”是等幂的或“”满足等幂律:=(x)(xSxx=x)给定且xS，则x是关于“”的等幂元:=xx=x于是，不难证明下面定理：定定理理12.2.2 若x是中关于的等幂元，对于任意正整数n，则xn=x。本讲稿第二十八页，共九十八页例例12.2.5 给定，其中P(S)是集合S的幂集，和分别为集合的并和交运算。验证：和是等幂的。证：对任意A P(S)，有AA=A和AA
13、=A，故和是等幂的。本讲稿第二十九页，共九十八页6.幺元或单位元给定且el，er，eS，则el为关于的左幺元:=(x)(xSelx=x)er为关于的右幺元:=(x)(xSxer=x)若e既为的左幺元又为的右幺元，称e为关于的幺元。亦可定义如下：e为关于的幺元:=(x)(xSex=xe=x)。本讲稿第三十页，共九十八页定定理理12.2.3 给定且el和er分别是关于的左、右幺元，则el=er=e且幺元e唯一。例：实数集R上的代数结构的“”运算的幺元为1，因为对任意xR有x11xx。而“”运算的幺元为0，因为对任意xR有x00 xx。例：前面例子中关于串的并置运算，它的单位元素是空串，因为对任一串
14、A，均有/A=A/=A。本讲稿第三十一页，共九十八页7.零元给定及l，r，S，则l为关于的左零元:=(x)(xSlx=l)r为关于的右零元:=(x)(xSxr=r)为关于的零元:=(x)(xSx=x=)本讲稿第三十二页，共九十八页定定理理12.2.4 给定且l和r分别为关于的左零元和右零元，则l=r=且零元是唯一的。定定理理12.2.5 给定且|S|1。如果，eS，其中和e分别为关于的零元和幺元，则e。本讲稿第三十三页，共九十八页例：代数结构上的零元是“0”，因为对于任何整数x，均有x00 x0。例：正整数集Z+上的运算“min”，叫“取最小”运算。min(a,b)为取a,b的最小者。代数结构
15、中对应于运算“min”的零元为1。本讲稿第三十四页，共九十八页8逆元给定且幺元e，xS，则x为关于的左逆元:=(y)(ySxy=e)x为关于的右逆元:=(y)(ySyx=e)x为关于可逆的:=(y)(ySyx=xy=e)本讲稿第三十五页，共九十八页给定及幺元e；x，yS，则y为x的左逆元:=yx=ey为x的右逆元:=xy=ey为x的逆元:=yx=xy=e本讲稿第三十六页，共九十八页显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表示为x-1。一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元
16、还可以不是唯一的。本讲稿第三十七页，共九十八页定定理理12.2.6 给定及幺元eS。如果是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。定定理理12.2.7 给定及幺元eS。如果是可结合的并且x的逆元x-1存在，则x-1是唯一的。本讲稿第三十八页，共九十八页例：代数结构上的幺元是“0”，对于任何整数x，它的逆元是x，因为 x(x)0。例：代数结构中0和1分别为和的幺元。对于“”，对每个元素rR都有逆元r；对于“”，对每个元素 rR都有逆元1/r(r 0)。本讲稿第三十九页，共九十八页9.可约律与可约元给定且零元S，则满 足 左 可 约 律 或 是 左 可 约
17、 的:=(x)(y)(z)(x,y,zSxxy=xz)y=z)，并称x是关于的左可约元。满 足 右 可 约 律 或 是 右 可 约 的:=(x)(y)(z)(x,y,zSxyx=zx)y=z)，并称x是关于的右可约元。本讲稿第四十页，共九十八页若既满足左可约律又满足右可约律或既是左可约又是右可约的，则称满足可约律或是可约的。若x既是关于的左可约元又是关于的右可约元，则称x是关于的可约元。可约律与可约元也可形式地定义如下：本讲稿第四十一页，共九十八页满足可约律:=(x)(y)(z)(x,y,zSx(xy=xzyx=zx)y=z)x是关于的可约元:=(y)(z)(y,zSx(xy)=xzyx=zx
18、)y=z)本讲稿第四十二页，共九十八页例：给定，其Z是整数集合，是一般乘法运算。显然，每个非零整数都是可约元，而且运算满足可约律。本讲稿第四十三页，共九十八页定理12.2.8 给定且是可结合的，如果x是关于可逆的且x，则x也是关于的可约元。证明 设任意y,zS且有xy=xz或yx=zx。因为是可结合的及x是关于可逆的，则有x-1(xy)=(x-1x)y=ey=yx-1(xz)=(x-1x)z=ez=z本讲稿第四十四页，共九十八页故得xy=xzy=z，故x是关于的左可约元。同样可证得yx=zxy=z，故x是关于的右可约元。故x是关于的可约元。最后，作一补充说明，用运算表定义一代数结构的运算，从表
19、上很能反映出关于运算的各种性质。为确定起见，假定及x，y，eS。本讲稿第四十五页，共九十八页(1)运算具有封闭性，当且仅当表中的每个元素都属于S。(2)运算满足交换律，当且仅当表关于主对角线是对称的。本讲稿第四十六页，共九十八页(3)运算是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元素相同。abcaabbcc本讲稿第四十七页，共九十八页(4)元素x是关于的左零元，当且仅当x所对应的行中的每个元素都与x相同；元素y是关于的右零元，当且仅当y所对应的列中的每个元素都与y相同；元素是关于的零元，当且仅当所对应的行和列中的每个元素都与相同。lmnaxxxxc左零元xmnyaybycy右零
20、元ymnac零元本讲稿第四十八页，共九十八页(5)元素x为关于的左幺元，当且仅当x所对应的行中元素依次与行表头元素相同；元素y为关于的右幺元，当且仅当y所对应的列中元素依次与列表头元素相同；元素e是关于的幺元，当且仅当e所对应的行和列中元素分别依次与行表头元素和列表头元素相同。lmnaxlmnc左幺元xmnyaabbcc右幺元ymneaaemnecc幺元e本讲稿第四十九页，共九十八页(6)x为关于的左逆元，当且仅当位于x所在行的元素中至少存在一个幺元，y为关于的右逆元，当且仅当位于y所在列的元素中至少存在一个幺元；x与y互为逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素
21、都是幺元。lmnaxec左逆元mnyaebc右逆元mxyxebye逆元本讲稿第五十页，共九十八页例例12.2.8 给定，其中S=，且的定义如表12.2.5所示。试指出该代数结构中各元素的左、右逆元情况。表12.2.5解：是幺元；的左逆元和右逆元都是，即与互为逆元；的左逆元是而右逆元是；有两个左逆元和；的右逆元是，但没有左逆元。e e e e e e e e 本讲稿第五十一页，共九十八页12.3 同态与同构同态与同构本节将阐明两个重要概念同态与同构。在以后各节中，它们会经常被使用到。本讲稿第五十二页，共九十八页定义12.3.1 设与是同类型的。称同态于或为的同态象，记为 ，其定义如下：:=(f)
22、(fYX(x1)(x2)(x1,x2Xf(x1x2)=f(x1)f(x2)同时，称f为从到的同态映射.可以看出，同态映射f不必是惟一的。本讲稿第五十三页，共九十八页 X x1x2x3 x1x3f(X)y1=f(x1)f(x1)=f(x2)y3=f(x3)y1y3Y同态示意图f本讲稿第五十四页，共九十八页例例12.3.1 给定和，其中R是实数集合，和分别是加法和乘法运算，试证 。证：关键是找一个同态映射。今构造函数fRR如下：f(x)=ax,其中a0,xR则f为所求的同态映射，这是因为对任意y,zR，有f(yz)=ayz ay az f(y)f(z)因此，本讲稿第五十五页，共九十八页两个同类型的
23、代数结构间的同态定义不仅适用于具有一个二元运算的代数结构，也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二元运算的两个同类型代数结构和的同态定义如下：:=(f)(fYX(x1)(x2)(x1,x2X(f(x1x2)=f(x1)f(x2)f(x1x2)=f(x1)f(x2)本讲稿第五十六页，共九十八页定理12.3.1 如果 且f为其同态映射，则 。由于函数fYX的不同性质，将给出不同种类的同态定义。本讲稿第五十七页，共九十八页定义12.3.2 设 且f为其同态映射。(i)如果 f 为满射，则称 f 是从到的满同态映射。(ii)如果f为单射(或一对一映射)，则称f为从到的
24、单一同态映射。本讲稿第五十八页，共九十八页(iii)如果f为双射(或一一对应)，则称f为从到的同构映射。记为。显然，若 f 是从到的同构映射，则 f 为从到的满同态映射及单一同态映射，反之亦然。本讲稿第五十九页，共九十八页例12.3.3 设与是同类型的，其中*为有限字母表上的字母串集合，为并置运算，N为自然数集合，+为普通加法。若定义 f：*N为 f(x)=|x|其中x*，|x|表示字母串的长度。因为对任意 x，y*，有f(xy)=|xy|=|x|+|y|=f(x)+f(y)，故 。显然，f是满射，因此，f为从到的满同态映射。本讲稿第六十页，共九十八页例12.3.4 给定，其中Z为整数集合，+
25、为一般加法。作函数fZZ：f(x)=kx，(此处乘法是一般乘法)其中x,kZ则当k0时，由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)，故f为到的同态映射。又易知f为单射，故f为到的单一同态映射。当k=-1或k=1时，f为从到的同构映射(我们稍后再来证明)。本讲稿第六十一页，共九十八页综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说，它能够保持运算的更多性质，为此，给出如下定理：定理12.3.2 给定 且 f 为其满同态映射，则(a)如果和满足结合律，则和也满足结合律。(b)如果和满足交换律，则和也满足交换律。本讲稿第六十二页，共九十八页(c)如果对于或对
26、于满足分配律，则对于或对于也相应满足分配律。(d)如果对于或对于满足吸收律，则对于或对于也满足吸收律。(e)如果和满足等幂律，则和也满足等幂律。(f)如果e1和e2分别是关于和的幺元，则f(e1)和f(e2)分别为关于和的幺元。本讲稿第六十三页，共九十八页(g)如果1和2分别是关于和的零元，则f(1)和f(2)分别为关于和的零元。(h)如果对每个xX均存在关于的逆元x-1，则对每个f(x)Y也均存在关于的逆元f(x-1)；如果对每个zX均存在关于的逆元z-1，则对每个f(z)Y也均存在关于的逆元f(z-1)。本讲稿第六十四页，共九十八页定理12.3.2告诉我们，对于满同态映射来说，代数结构的许
27、多性质都能保持，如结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的，即如果满同态于，则所具有的性质，均具有。但反之不然，即所具有的某些性质，不一定具有。不尽要问，在怎样条件下，所具有的性质都完全具有呢?为了回答这个问题，需要引出两个代数结构同构的概念。本讲稿第六十五页，共九十八页定义12.3.3 设与是同类型的。称同构于，记为，其定义如下：:=(f)(f为从到的同构映射)或更详细地定义为：:=(f)(fYXf为双射f为从到的同态映射)本讲稿第六十六页，共九十八页 x1x2 x1x2f(x1)f(x2)f(x1)f(x2)同构示意图f本讲稿第六十七页，共九十八页例 代数
28、结构与是同构的。其中R为实数，R+为正实数。证：关键是找一个双射。对 与，有一个函数h：R+R，h(x)=lnx此函数是双射的。因为对每个x0,均存在一个y=lnxR，同时，对每个yR，均存在一个x=ey R+.又因为h(yz)=ln(yz)=lnylnz=h(y)h(z)故与是同构的。注：当然，我们也可以取函数h(x)=lgx，本讲稿第六十八页，共九十八页续例12.3.4 给定，其中Z为整数集合，+为一般加法。作函数fZZ：f(x)=kx，(此处乘法是一般乘法)其中x,kZ，则当k=-1或k=1时，f为从到的同构映射。证：先证明当k=-1或k=1时f为双射。因为对每个xZ,均存在一个y=kx
29、(即y=x或y=-x)Z，同时，对每个yZ，均存在一个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为到的同构映射。本讲稿第六十九页，共九十八页例 代数结构与是同构的。其中M,H分别表示低电平、高电平，“”表示或门，它们的运算表如下。证：这 两 个 代 数 结 构 间 存 在 一 个 函 数f:0,1M,H，且f(0)=M,f(1)=H，显然这是一个双射，而且有f(xy)=f(x)+f(y)。故它们是同构的。01001111M HMM HHHH本讲
30、稿第七十页，共九十八页例 设S=4,5,6,在S上的二元运算“”其定义如下表所示。又有P=1,2,3及在P上的二元运算“”，其运算表如下表所示。这样所构成的两个代数结构与是同构的。证：这 两 个 代 数 结 构 间 存 在 一 个 函 数f:4,5,61,2,3，f(x)=x-3，其中xS。显然这是一个双射，而且有f(xy)=f(x)f(y)。故它们是同构的。45 6445 4545 5645 61 231 1 212 1 223 1 23本讲稿第七十一页，共九十八页由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那
31、样对保持运算是单向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它们的所有发生“彼此相通”。本讲稿第七十二页，共九十八页这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的两个代数结构来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是相同的。因此，可以根据这些特征来识别同构的代数结构。本讲稿第七十三页，共九十八页下面给出两个二元运算的代数结构的同构定义定义 设两个代数结构与，如果它们之间存在一个
32、双射f：XY，使得任意x1,x2X，有f(x1 x2)=f(x1)f(x2)f(x1 x2)=f(x1)f(x2)则说此两个代数结构是同构的。本讲稿第七十四页，共九十八页例12.3.6 给定，其中S=，A，B，C，和是一般的集合运算；又有，这里T=1，2，5，10，且对于a，bT有a b=lcma，b(最小公倍数)，a b=gcda，b(最大公约数)，表12.3.3至表12.3.6给出四个运算表。试说明.本讲稿第七十五页，共九十八页表12.3.3表12.3.4 表12.3.5表12.3.6 AB C AB CAAAC CBBCB CCCCC C AB C AA AB B BCAB C1 251
33、01 1 25102221010551051010101010101 25101 1 11121212511551012510本讲稿第七十六页，共九十八页解：令 fTS：f()=1，f(A)=2，f(B)=5，f(C)=10。显然，f是从S到T的双射。经验证，对任意x1,x2S，又有f(x1x2)=f(x1)f(x2)f(x1x2)=f(x1)f(x2)故与是同构的。本讲稿第七十七页，共九十八页同构是一个关系，而且可以证明它是个等价关系，对此有如下定理：定理12.3.3 代数结构间的同构关系是等价关系。本讲稿第七十八页，共九十八页证明 显然，因为恒等映射是同构映射。又若且f为其同构映射，则f-
34、1为从到的同构映射。因此，。再令及，则。这里因为若f为到的同构映射，g为到的同构映射，则gf为从到的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构关系是等价关系。本讲稿第七十九页，共九十八页由于同构关系是等价关系，故令所有的代数结构构成一个集合S，于是可按同构关系将其分类，得到商集S/。因为同构的代数结构具有相同的性质，故实际上代数结构所需要研究的总体并不是S而是S/。在同态与同构中有一个特例，即具有相同集合的任两个代数结构的同态与同构，这便是自同态与自同构。本讲稿第八十页，共九十八页定义12.3.4 给定及fSS。f为自同态映射:=f为从到的同态映射。f为自同构映射:=f为从到
35、的同构映射。例12.3.7 在例12.3.4中，当k 0时，f=kx是从到的自同态映射；当k=1或k=-1时，f=kx是从到的自同构映射。本讲稿第八十一页，共九十八页12.4 同余关系同余关系本节主要阐明同态与同余关系之间的联系。主要内容如下：定义12.4.1 给定，且E为S中的等价关系。E有代换性质:=(x1)(x2)(y1)(y2)(x1,x2,y1,y2Sx1Ex2y1Ey2)(x1y1)E(x2y2)。E为中的同余关系:=E有代换性质。本讲稿第八十二页，共九十八页与此同时，称同余关系E的等价类为同余类。由定义可知，同余关系是代数结构的集合中的一类特殊的等价关系，并且在运算的作用下，能够
36、保持关系的等价类。即在x1y1中，如果用集合S中的与x1等价的任何其它元素x2代换x1，并且用与y1等价的任何其它元素y2代换y1，则所求的结果x2y2与x1y1位于同一等价类之中。本讲稿第八十三页，共九十八页亦即若x1E=x2E并且y1E=y2E，则x1y1E=x2y2E。此外，同余关系与运算密切相关。如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果有，则说该代数结构存在同余关系；否则，同余关系不存在。本讲稿第八十四页，共九十八页x1Ex1x2x1y1Ex1y1x2y2y1Ey1y2同余关系示意图本讲稿第八十五页，共九十八页例12.4.1 给定，其中Z是
37、整数集合，+和是一般加、乘法。假设Z中的关系R定义如下：i1Ri2:=|i1|=|i2|，其中i1、i2Z试问，R为该结构的同余关系吗？本讲稿第八十六页，共九十八页解 显然，R为Z中的等价关系。接着先考察R对于+运算的代换性质：若取i1,-i1,i2Z，则有|i1|=|-i1|和|i2|=|i2|，于是，下式(i1R(-i1)(i2Ri2)(i1+i2)R(-i1+i2)不真。这是因为前件为真，后件为假。故R对于+运算不具有代换性质。本讲稿第八十七页，共九十八页至此可以说，R不是该结构的同余关系。但为了熟悉验证一个关系是否为同余关系，还是来考察R对于的代换性质。令i1,i2,j1,j2Z且i1
38、Ri2和j1Rj2。于是，对任意i1,i2,j1,j2都有：(i1Ri2)和(j1Rj2)(i1j1)R(i2j2)因此，E对于具有代换性质。本讲稿第八十八页，共九十八页可见，考察一个等价关系E对于有多个运算的代数结构是否为同余关系，这里有个次序先后问题，选择得好，马上就考察到了E对某个运算是不具有代换性质，那么便可立刻断定E不是该结构的同余关系，否则验证应继续下去，直至遇到不具有代换性质的运算为止。如果对于所有运算都有代换性质，则E为该结构的同余关系。本讲稿第八十九页，共九十八页在例12.4.1中，首先发现R对于+不具有代换性质，那么可断定R不是该结构的同余关系。如果你首先验证是R对于的代换
39、性质，结果R对于有代换性质，至此你只是有希望E是同余关系，但还得继续工作，考察R对于+的代换性质，由此结果才能判定R是否为该结构的同余关系。本讲稿第九十页，共九十八页有了同余关系的概念后，现在可以给出它与同态映射的关系了，请看下面定理：定理12.4.1 设与是同类型的且 f 为其同态映射。对应于f，定义关系 Ef 如下：xEfy:=f(x)=f(y)，其中x，yS则Ef是中的同余关系，并且称Ef为由同态映射 f 所诱导的同余关系。由于同态映射不唯一，根据定理12.4.1，可以推知同余关系也是不唯一。本讲稿第九十一页，共九十八页12.5 商代数商代数定义12.5.1 给定及其上的同余关系E，且由
40、E对S所产生同余类构成一个商集S/E。若在S/E中定义一个运算如下：xEyE=xyE 其中xE，yES/E于是构成了一个代数结构，则称为代数结构的商代数。本讲稿第九十二页，共九十八页 可以看出，给定一个代数结构，利用结构中的同余关系可以构造一个新的代数结构即商代数，两者有何联系，下面定理指明这一点，即：一个代数结构与其上的商代数同态。本讲稿第九十三页，共九十八页定理12.5.1 给定及其上的商代数，则 。证：构造一个映射gE：SS/EgE(x)=xE，其中 xS，E为中的同余关系。于是，对于任意x,yS有gE(xy)=xyE=xE yE=gE(x)gE(y)因此，gE为所求的同态映射，从而定理
41、得证.通常，称gE为从S到S/E上的正则映射，并且称gE为从到的与E相关的自然同态映射，简称自然同态。本讲稿第九十四页，共九十八页此外，容易看出自然同态gE还是一个满同态映射，根据定理12.3.2可知，代数结构的各种性质在其商代数中都被保持了下来。另外，这个定理还告诉我们，任何一个代数结构总可以找到一个与其同态的代数结构，这个同态的代数结构就是它的商代数。本讲稿第九十五页，共九十八页现在，可以利用自然同态及Ef给出一个有关同构的重要定理。定理12.5.2 设 且 f 为其满同态映射，Ef为 f 所诱导的同余关系，gEf是从到的与Ef相关的自然同态，则。本讲稿第九十六页，共九十八页12.6 积代数积代数定义12.6.1 设与是同类型的，而成为新的代数结构，其中ST是集合S和集合T的笛卡儿积，且定义如下：=，其中s1，s2S，t1，t2T。则称为代数结构和的积代数，而代数结构和称为的因子代数。本讲稿第九十七页，共九十八页类似地可把积代数的定义推广到任何两个同类型的代数结构。另外，重复地使用定义中的方法，也可以定义任何有限数目的同类型代数结构的积代数。可以看出，两个代数结构的积代数，与两个因子代数是同一类型的。而且还要注意到，在积代数的定义中，是用因子代数中的相应运算定义了积代数中的运算。本讲稿第九十八页，共九十八页