离散数学 第五章 代数系统

1、第三篇第三篇 代数系统代数系统 代数学的历史悠久，早期代数学的研究对象是具 体的，它以方程根的求解与分布为研究中心。但 自从20世纪初以来，代数学的研究对象和研究方 法都发生了重大的变化，形成了抽象代数学。这 一变化可以追溯到19世纪30年代法国数学家伽罗 瓦（Galois）提出的群的概念，证明了高于四次的 一般代数方程的不可解性，并且建立了具体数字 系统的代数方程可用根号求解的判别准则以及不 能用根号求解的数字系统代数方程的实例。 抽象代数学不同于以代数方程求根和根的分布情 况为研究中心的古典代数学，它研究所谓的抽象 代数系统。被处理的对象连同其上定义的运算（ 操作）称为一个代数系统。由于其

2、研究对象的抽 象性，即它不以某一具体对象为研究对象，而是 以一大类具有某种共同性质的对象为研究对象， 因此其研究成果适用于这一类对象中的每个对象 ，从而达到事半功倍的效果。它在较高的观点上 ，把一些形式上很不相同的代数系统，撇开个性 ，抽出共性，用统一的方法描述、研究和推理， 从而得到一些反映事物本质的结论，再把它们应 用到那些系统中去，高度的抽象产生了广泛的应 用。 代数系统这个具有运算的集合，是抽象代数研究 的主要对象，是离散数学的重要组成部分。它广 泛应用于自动机、形式语言、逻辑电路设计、编 码理论等研究中，成为计算机科学中重要的数学 工具。由于抽象代数的内容较多，作为离散数学 的内容之

3、一，本篇主要介绍代数系统的基本概念 和几类典型的代数系统，包括半群、群、环、域 、格和布尔代数。 第第5章章 代数系统代数系统 5.1 代数系统的基本概念 代数系统，也称为代数结构，是一个具有运算的 集合。因此在介绍它之前，先引进一个集合上的 运算的概念。例如，将实数集合R上的每一个数 a0映射成它的倒数 ，或者将R上的每一个数y映 射成 ，就可以将这些映射称为在集合R上的一 元运算；而在集合R上，对任意两个数所进行的普 通加法和乘法，都是集合R上的二元运算，也可以 看作是将R上的每二个数映射成R中的一个数；至 于对集合R上的任意三个数x，y，z，ALGOL算法语 言中的条件算术表达式if x

4、=0 then y else z，就是集 合R上的三元运算。 a 1 y 5.1 代数系统的基本概念 上述一些例子，有一个共同的特征，就是其运算 结果都是在原来的集合R中，我们称那些具有这种 特征的运算是封闭的，简称闭运算。相反地，没 有这种特征的运算就不是封闭的。 很容易举出不封闭运算的例子：一架自动售货机， 能接受五角硬币和壹圆硬币，而所对应的商品是 矿泉水（瓶）、可口可乐（瓶）和冰淇淋（杯）。 当人们投入上述硬币的任何两枚时，自动售货机 将按表5-1所示的供应相应的商品。 5.1 代数系统的基本概念 *五角硬币五角硬币 壹圆硬币壹圆硬币 五角硬币五角硬币 壹圆硬币壹圆硬币 矿泉水矿泉水

5、可口可乐可口可乐 可口可乐可口可乐 冰淇淋冰淇淋 表 5-1 表格左上角的记号*可以理解为一个二元运算的 运算符。这个例子中的二元运算*就是集合五角 硬币，壹圆硬币上的不封闭运算。 定义定义5.1 设A，B是两个集合，若f是从An到B的函 数，则称f为A上的一个n元运算。其中n是自然数， 称为运算的元数或阶。如果BA，则称该n元运 算是封闭的。 5.1 代数系统的基本概念 当n = 1时，称f为一元运算，当n = 2时，称f为二元 运算，等等。 运算的例子很多。例如，在数理逻辑中，否定是 命题集合上的一元运算，合取和析取是命题集合 上的二元运算；在集合论中，集合的补是集合上 的一元运算，并与交

6、是集合上的二元运算；在实 数算术中，加、减、乘、除运算都是二元运算。 有了集合上运算的概念后，便可以定义代数系统 了。 5.1 代数系统的基本概念 定义定义5.2 设A是个非空集合且fi是A上的ni元运算， 其中i = 1，2，m。由A及f1，f2，fm组成的 结构，称为代数结构或代数系统，记作 。 此外，集合A的基数即|A|，定义为代数系统的基 数。如果A是有限集合，则说代数系统是有限代数 系统；否则便说是无穷代数系统。 有时，要考察两个或多个代数系统，这里就有是 否为同类型之说，请看下面定义： 5.1 代数系统的基本概念 定义定义5.3 设两个代数系统和，如果fi和gi(1im)具有相同的

7、 元数，则称这两个代数系统是同类型的。 可见，判定两个代数系统是否同类型，主要是对 其运算进行考察。 下面举例说明上述各个概念。 5.1 代数系统的基本概念 例例5.1 设S是非空集合，P(S)是它的幂集。对任意集 合A，BP(S)上的运算和定义如下: AB =(A-B)(B-A) AB = AB 则是一个代数系统，并且是一个封 闭的代数系统。 5.1 代数系统的基本概念 例例5.2 设是由有限个字母组成的集合，称为字母 表。由中的字母组成的有序集合，称为上的串 。串中的字母个数m称为该串的长度。m = 0时， 叫做空串，用表示之。用*表示上的串集合。 在*上定义一个并置或者连接运算，用表示之

8、 。如、*，则 = 。那么，是 一代数系统。如果令+=*-，则也是一 个代数系统。 5.1 代数系统的基本概念 例例5.3 设有一台字长为8位的计算机，它以定点加 、减、乘、除以及逻辑加和逻辑乘为运算指令， 并分别用01，02，06表示之。则在计算机中由 28个不同数字所组成集合S同该机中运算指令构成 一代数系统。 5.1 代数系统的基本概念 例例5.4 设Z是整数集合，+是普通的加法运算，则是一个代数系统。显然，在这个代数系统中 ，关于“+”运算，具有以下三个运算规律，即对于 任意的x，y，zZ，有 （1）x+yZ，（封闭性） （2）x+y=y+x（交换律） （3）(x+y)+z=x+(y+

9、z)（结合律） 容易找到与具有相同运算规律的一些代数 系统，如表5-2所示。 5.1 代数系统的基本概念 集合集合 运算运算 封闭性封闭性 交换律交换律 结合律结合律 Z为整数集合为整数集合 为普通乘法为普通乘法 xyZ xy = yx (xy)z =x(yz) R为实数集合为实数集合 +为普通加法为普通加法 x+yR x+y = y+x (x+y)+z =x+(y+z) P(S)是是S的幂集的幂集 是集合的是集合的“并并” ABP(S) AB = BA (AB)C =A(BC) P(S)是是S的幂集的幂集 是集合的是集合的“交交” ABP(S) AB = BA (AB)C = A(BC) 表

10、 5-2 在结束本节时，声明记号即 为一代数系统，除特别指明外，运算符f1，f2， fm均为二元运算。根据需要对A及f1，f2，fm可 置不同的集合和运算符。 5.2 运算及其性质 在前面讨论几个具体的代数系统时，已经涉及到 我们所熟知的运算的某些性质。下面，着重讨论 一般二元运算的一些性质。对于代数系统的性质 的考察方法不是一个一个研究各个结构，而是列 举一组性质，并且对于具有这些性质的任何代数 系统推导可能的结论。把那些被选出的性质看成 是公理并且由这些公理推导出的任何有效结论， 对于满足这些公理的任何代数系统也都必定成立 。 5.2 运算及其性质 因此，为了做出这样的讨论，将不考虑任何特

11、定 的集合，也不给所涉及到的运算赋予任何特定的 含义。这种系统的集合及集合上的诸运算仅仅看 成是一些符号，或更确切地说，它们都是些抽象 对象。因此，与此相应的代数系统，通常称为抽 象代数。对于那些特定的代数系统只能是具有这 些基本性质中的某些性质。 5.2 运算及其性质 性质性质1：封闭性：封闭性 设*是定义在集合A上的二元运算 ，如果对于任意的x，yA，都有x*yA，即 (x)(y)(x，yAx* yA)，则称二元运算*在A上 是封闭的。 例例5.5 设A=x|x=2n, nN，问乘法运算是否封闭？ 加法运算是否封闭？ 解：对于任意的2r，2sA，r，sN，因为 2r2s=2r+sA所以乘法

12、运算是封闭的。而对于加法 运算是不封闭的，因为至少有2+22=6A。 5.2 运算及其性质 性质性质2：交换律：交换律 设*是定义在集合A上的二元运算 ，如果对于任意的x，yA，都有x*y=y*x，即 (x)(y)(x，yAx*y = y*x)，则称二元运算*满足 交换律，或称*是可交换的。 例例5.6 给定，其中Q为有理数集合，并且 对任意a，bQ有a b = a + b - ab，问运算 是否 可交换? 解：因为a b = a + b - ab= b+ a - ba= b a 所以运算 是可交换的。 5.2 运算及其性质 性质性质3：结合律：结合律 设*是定义在集合A上的二元运算 ，如果对

13、于任意的x，y，zA，都有 (x*y)*z=x*(y*z)，即(x)(y)(z) (x，y， zA(x*y)*z=x*(y*z)，则称二元运算*满足结合律 ，或称*是可结合的。 例例5.7 给定，对任意a，bA有a b=b。证 明运算“ ”是可结合的。 证明：因为对于任意的a，b，c有 (a b) c=b c=c，而a (b c)=a c=c 所以(a b) c= a (b c) 5.2 运算及其性质 可见，如果一个代数系统中的运算 是可结合和 可交换的，那么，在计算a1 a2 am时可按任 意次序计算其值。特别当a1 = a2 = = am = a时， 则a1 a2 am = am。称am为

14、a的m次幂，m称a 的指数。下面给出am的归纳定义： 设有且aA。对于mN+，其中N+表示正 整数集合，可有 (1) a1 = a (2) am+1 = am a 5.2 运算及其性质 由此利用归纳法不难证明指数定律： (1) am an = am+n (2) (am)n = amn 这里，m，n N+。 类似地可定义某代数系统中的负幂和给出负指数 定律。 5.2 运算及其性质 性质性质4：分配律：分配律 设*， 是定义在集合A上的两个 二元运算，如果对于任意的x，y，zA，都有 x*(y z)=(x*y) (x*z)和(y z)*x=(y*x) (z*x) 即(x)(y)(z)(x，y，zA

15、x*(y z) =(x*y) (x*z)(y z)*x=(y*x) (z*x)，则称运算* 对于 满足分配律，或者*对于 是可分配的。 一个代数系统若具有两个运算时，则分配律可建 立这两个运算之间的某种联系。 5.2 运算及其性质 例例5.8 给定，其中B=0，1。表5-3分别 定义了运算*和 ，问运算*对于 是可分配的吗? 对于*呢? 解：容易验证运算 对于运算*是可分配的。但是 运算*对于运算 是不可分配的，因为 1*(0 1)=1*0=1，而 (1*0) (1*1)=1 0=0 *0 10 1 00 100 0 11 010 1 表5-3 5.2 运算及其性质 形如表5-3的表常常称为运

16、算表或复合表，它由运 算符、行表头元素、列表头元素及复合元素四部 分组成。对于集合的基数很小，特别是2或3时， 代数系统中运算常常用这种表给出。优点是简明 直观，一目了然。 性质性质5：吸收律：吸收律 设*， 是定义在集合A上的两个 可交换的二元运算，如果对于任意的x，yA，都 有x*(x y)=x 和x (x*y)=x 即(x)(y)(x，yAx*(x y)=xx (x*y)=x),则称 运算*和运算 满足吸收律，或称*对于 以及 对于*是可吸收的。 5.2 运算及其性质 例例5.9 给定，其中N是自然数集合，* 和 定义如下： 对任意a，bN有a*b = max(a，b)，a b = mi

17、n(a， b)，试证，*和 互为吸收的。 证明：对于任意a，bN a*(a b)= max(a，min(a，b)= a a (a*b)= min(a，max(a，b)= a 因此，*和 满足吸收律。 5.2 运算及其性质 性质性质6：等幂律：等幂律 设*是定义在集合A上的一个二元 运算，如果对于任意的xA，都有x*x=x，即 (x)(xAx x=x)，则称运算*是等幂的，或*满 足等幂律，并称x是关于*的等幂元。 例例5.10 给定，其中P(S)是集合S的幂 集，和分别为集合的并和交运算。证明： 和是等幂的。 证明：对于任意的AP(S)，有AA=A和AA=A， 因此运算和都满足等幂律。 关于等

18、幂律，不难证明下面的定理： 5.2 运算及其性质 定理定理5.1 若x是中关于 的等幂元，对于任 意正整数n，则xn = x。 证明留做练习。 性质性质7：幺元：幺元 设*是定义在集合A上的一个二元运 算，如果存在一个元素elA，对于任意的xA，都 有el*x=x，即(x)(xAel*x=x)，则称el为A中关于 运算*的左幺元；如果存在一个元素erA，对于任 意的xA，都有x*er=x，即(x)(xAx*er=x)，则 称er为A中关于运算*的右幺元；如果A中一个元素 e，它既是*的左幺元又是*的右幺元，则称e为A中 关于*的幺元，即(x)(xAe*x = x*e = x)。 5.2 运算及

19、其性质 例例5.11 给定，表5-4，表5-5和表5-6分 别给出*的不同定义的运算表，试指出左幺元、右 幺元及幺元。 解：在运算表5-4中，既是左幺元，又是右幺元 。即为幺元。运算表5-5中，不存在左幺元，和 都是右幺元。运算表5-6中，是左幺元，不存在 右幺元。 表表5-4表表5-5表表5-6 * * * * * * 5.2 运算及其性质 定理定理5.2 给定且el和er分别关于 的左、右 幺元，则el = er = e且幺元e是惟一的。 证明：因为el和er分别是S中关于 的左、右幺元 ，所以 el = el er = er = e 设另有一个幺元e1S，则 e1=e1 e=e 5.2

20、运算及其性质 性质性质8：零元：零元 设*是定义在集合A上的一个二元运 算，如果存在一个元素lA，对于任意的xA， 都有l*x=l，即(x)(xAl*x=l)，则称l为A中 关于运算*的左零元；如果存在一个元素rA，对 于任意的xA，都有x*r=r，即 (x)(xAx*r=r)，则称r为A中关于运算*的右 零元；如果A中一个元素，它既是*的左零元又是 *的右零元，则称为A中关于*的零元，即 (x)(xA*x = x* =)。 5.2 运算及其性质 例例5.12 在例5.11中，*如表5-4所定义，是*的零元 ；*如表5-5所定义，和都是*的左零元；*如表 5-6所定义，是*的右零元。 定理定理

21、5.3 给定且l和r分别为关于 的左零 元和右零元，则l = r = 且零元是惟一的。 本定理的证明可仿照定理5.2，请读者自己完成。 5.2 运算及其性质 定理定理5.4 给定且 |S|1。如果，eS，其 中和e分别为关于 的零元和幺元，则 e。 证明：用反证法。设=e，那么对于任意的xS， 必有 x= e x= x=e 于是，S中的所有元素都是相同的，这与S中含有 多个元素相矛盾。 5.2 运算及其性质 性质性质9：逆元：逆元 给定代数系统， 是定义在 A上的一个二元运算，且e是A中关于运算 的幺元 。如果对于A中的一个元素x存在A中的某个元素y ，使得y x= e，那么称y为的x的左逆元

22、，即 (y)(yAy x =e)；如果x y = e成立，那么称y 为的x的右逆元，即(y)(yAx y=e)；如果一个 元素y，它既是x的左逆元，又是x的右逆元，那么 就称y是x的一个逆元。 显然，若y是x的逆元，则x也是y的逆元，因此称x 与y互为逆元。通常x的逆元表为x-1。 5.2 运算及其性质 一般地说，一个元素的左逆元不一定等于该元素 的右逆元。而且，一个元素可以有左逆元而没有 右逆元，反之亦然。甚至一个元素的左或右逆元 还可以不是惟一的。 例例5.13 给定，其中S=，且*的 定义如表5-7所示。试指出该代数系统中各元素的 左、右逆元情况。 解：是幺元；的左逆元和右逆元都是；即和

23、 互为逆元；的左逆元是而右逆元是；有两个 左逆元和；的右逆元是，但没有左逆元。 5.2 运算及其性质 * * 表5-7 定理定理5.5 给定及幺元eS。如果 是可结 合的并且一个元素x的左逆元xl-1和右逆元xr-1存在， 则xl-1=xr-1。 证明：xl-1= xl-1 e=xl-1 (x xr-1) = (xl-1 x) xr-1 =e xr-1= xr-1 5.2 运算及其性质 定理定理5.6 给定及幺元eS。如果 是可结合 的并且x的逆元x-1存在，则x-1是惟一的。 证明：假设x有两个逆元x-1和x1-1，那么 x-1= x-1 e= x-1 (x x1-1) =( x-1 x)

24、x1-1= e x1-1=x1-1 因此，x的逆元是惟一的。 5.2 运算及其性质 性质性质10：可约律：可约律 给定代数系统， 是定 义在A上的一个可交换的二元运算，且是A中关 于运算 的零元。如果对于A中的任意元素x 和 任意的y，z，若x y = x z，都有y = z，即 (x)(y)(z)(x，y，zSx x y = x z) y = z)，则称x是关于 的可约元，并且称 满足可约 律或是可约的。 例例5.14 给定，其Z是整数集合，是一般乘 法运算。显然，每个非零整数都是可约元，而且 运算满足可约律。 5.2 运算及其性质 定理定理5.7 给定且 是可结合的，如果x是关 于 可逆的

25、且x ，则x也是关于 的可约元。 证明：对于S中的任意元素y，z，若x y = x z， 设x的逆元为x-1，则 x-1 (x y) = x-1 (x z) (x-1 x) y = (x-1 x) z e y = e z y = z 因此，x是关于 的可约元。 5.2 运算及其性质 例例5.15 对于代数系统，其中Nk=0，1，2 ，k-1，+k是定义在Nk上的模k加法运算，定义 如下： 对于任意x，yNk 试问是否每个元素都有逆元。 解：可以验证，+k是一个可结合的二元运算，Nk 中关于运算+k的幺元是0，Nk中的每一个元素都有 惟一的逆元，即0的逆元是0，每个非零元素x的逆 元是k-x。

26、kyxkyx kyxyx yx k 若 若 5.2 运算及其性质 定义定义5.4 设是一代数系统，且非 空集TS在运算f1，f2，fm作用下是封闭的，且T 含有与S中相同的特异元（幺元或零元），则称为代数系统的 子代数，记为 。 最后，作一补充说明，用运算表定义一代数系统的 运算，从表上能很好地反映出关于运算的各种性质 。为确定起见，假定及x，y，eS。 5.2 运算及其性质 (1)运算*具有封闭性，当且仅当运算表中的每个元素 都属于S。 (2)运算*满足交换律，当且仅当运算表关于主对角线 是对称的。 (3)运算*满足等幂律，当且仅当运算表的主对角线上 的每个元素与所在行或列表头元素相同。 (

27、4)元素x是关于*的左零元，当且仅当x所对应的行中 的每个元素都与x相同；元素y是关于*的右零元，当 且仅当y所对应的列中的每个元素都与y相同；元素 是关于*的零元，当且仅当所对应的行和列中的 每个元素都与相同。 5.2 运算及其性质 (5)元素x为关于*的左幺元，当且仅当x所对应的行中 元素依次与行表头元素相同；元素y为关于*的右幺 元，当且仅当y所对应的列中元素依次与列表头元 素相同；元素e是关于*的幺元，当且仅当e所对应 的行和列中元素分别依次地与行表头元素和列表头 元素相同。 (6)x为关于*的左逆元，当且仅当位于x所在行的元素 中至少存在一个幺元，y为关于*的右逆元，当且仅 当位于y

28、所在列的元素中至少存在一个幺元；x与y互 为逆元，当且仅当位于x所在行和y所在列的元素以 及y所在行和x所在列的元素都是幺元。 5.3 同态与同构 本节我们讨论两个代数系统之间的联系。着重研究 两个代数系统之间的同态关系和同构关系，在以后 各节中，它们会经常被使用。 定义定义5.5 设与是同类型的两个代数系 统，若(f )(f YX(x1)(x2)(x1，x2Xf(x1 x2)= f(x1)*f(x2)，则称同态于或为 的同态象，记为 ，同时， 称f为从到的同态映射。 5.3 同态与同构 两个代数系统在同态意义下的相互联系可以由图5.1 来描述。 abca c f(c)f(a)*f(c)=f(

29、b)*f(c) A B b c f(a)=f(b) 图5.1 5.3 同态与同构 例例5.16 考察代数系统，这里Z是整数集合，* 是普通乘法运算。如果我们对计算结果只感兴趣于 正、负、零之间的特征区别，那么，代数系统中运算结果的特征就可以用另一个代数系统的运算结果来描述，其中B=正，负，零， 是 定义在B上的二元运算，如表5-8所示。 作映射f：ZB如下： 正若n0 f(n) = 负若n0 零若n=0 5.3 同态与同构 表 5-8 很明显，对于任意的a，bZ，有 f(a*b)=f(a) f(b) 因此，映射f是到的一个同态映射。 例5.16告诉我们，在中研究运算结果的正、 负、零的特征就等

30、于在中研究这些运算特 征，可以说，代数系统描述了中运 算结果的这些基本特征。而这正是研究两个代数系 统之间是否存在同态的重要意义。 正正 负负 零零 正正 负负 零零 正正 负负 零零 负负 正正 零零 零零 零零 零零 5.3 同态与同构 应该指出，两个代数系统之间的同态映射f不必是惟 一的，即一个代数系统到另一个代数系统可能存在 多个同态映射。 例例5.17 给定和，其中R是实数集合，+ 和分别是加法和乘法运算，试证 。 证明：构造函数fRR如下：f(x)=ax，其中a0，xR 则f为所求的同态映射，这是因为对任意y，zR有 f(y+z)= ay+z= ayaz= f(y)f(z) 因此，

31、 5.3 同态与同构 两个同类型的代数系统间的同态定义不仅适用于具 有一个二元运算的代数系统，也可以推广到具有多 个二元运算的任何两个同类型代数系统。例如，对 于具有两个二元运算的两个同类型代数系统和同态当且仅当 (f)(fYX(x1)(x2)(x1，x2X (f(x1 x2)=f(x1)f(x2)f(x1*x2)= f(x1)f(x2)，并且称f 为从到的同态映射。 5.3 同态与同构 例例5.18 给定，其中Z为整数集合，+和是 一般的加法和乘法运算。又有，这里 Zm=0，1，2，m-1，+m和m分别是模m加 法和模m乘法，它们详细定义如下： a +m b = (a+b)(mod m) a

32、 m b = (ab)(mod m) 其中a，b Zm 现在定义函数fZmZ: f(i)=(i)(mod m)， 其中iZ 试证 。 5.3 同态与同构 证明：因为对任意i1，i2Z，有 f(i1+ i2)=(i1+ i2)(mod m) =(i1)(mod m) +m (i2)(mod m) = f(i1) +m f(i2) f(i1 i2)=(i1 i2)(mod m) =(i1)(mod m) m (i2)(mod m) = f(i1)m f(i2) 故f为所求的同态映射，于是 。 5.3 同态与同构 定理定理5.8 如果 且f为其同态映射，则 。 证明：因为fYX，R(f)Y，故若y1

33、，y2R(f)，则应有 x1，x2X，使得f(x1)= y1和f(x2)= y2，而且存在x3X， 使x1 x2= x3，所以 y1*y2= f(x1)*f(x2)= f(x1 x2)= f(x3)R(f) 可见，集合R(f )在*作用下是封闭的，因此则。 由于函数fYX的不同性质，将给出不同种类的同态 定义。 5.3 同态与同构 定义定义5.6 设 且f为其同态映射。 (1)如果f为满射，则称f是从到的满同 态映射。 (2)如果f为单射(或一对一映射)，则称f为从 到的单一同态映射。 (3)如果f为双射(或一一对应)，则称f为从到 的同构映射。记为 。 显然，若f是从到的同构映射，则f为 从

34、到的满同态映射及单一同态映射 ，反之亦然。 5.3 同态与同构 例例5.19 给定，其中Z为整数集合，+为一般加 法。作函数fZ Z: f(x)= kx 其中x，kZ 则当k 0时，f为到的单一同态映射 。当k = -1或k = 1时，f为从到的同构 映射。 可以看出，同态映射具有一个特性，即“保持运算” 。对于满同态映射来说，它能够保持运算的更多性 质。为此，给出如下定理： 5.3 同态与同构 定理定理5.9 给定且f为其满同态 映射，则 (1)如果 和*满足结合律，则和也满足结合律。 (2)如果 和*满足交换律，则和也满足交换律。 (3)如果 对于*或*对于 满足分配律，则对于 或对于也相

35、应满足分配律。 (4)如果 对于*或*对于 满足吸收律，则对于 或对于也满足吸收律。 (5)如果 和*满足等幂律，则和也满足等幂律。 5.3 同态与同构 (6)如果e1和e2分别是关于 和*的幺元，则f(e1)和 f(e2)分别为关于和的幺元。 (7)如果1和2分别是关于 和*的零元，则f(1)和 f(2)分别为关于和的零元。 (8)如果对每个xX均存在关于 的逆元x-1，则对每 个f(x)Y也均存在关于的逆元f(x-1)；如果对每个 zX均存在关于*的逆元z-1，则对每个f(z)Y也均存 在关于的逆元f(z-1)。 5.3 同态与同构 证明： (1)因为f是从到的满同态映 射，故对任意y1，

36、y2，y3Y，必存在x1，x2，x3 X， 使得f(x1)= y1，f(x2)= y2，f(x3)= y3，而且有 f(x1 (x2 x3)= f(x1)f(x2 x3) = f(x1)(f (x2)f(x3)= y1(y2y3) f(x1 x2) x3)= f(x1 x2)f(x3) =(f(x1)f (x2)f(x3)= (y1y2)y3 5.3 同态与同构 因为x1 (x2 x3)= (x1 x2) x3 于是f(x1 (x2 x3)= f(x1 x2) x3) 因此y1 (y2y3) = (y1y2)y3 可见，由于 满足结合律证明也满足结合律；同 理由*满足结合律，可证也满足结合律。

37、 5.3 同态与同构 (2) 因为f是从到的满同态映 射，故对任意y1，y2Y，必存在x1，x2X，使得 f(x1)= y1，f(x2)= y2，而且有 f(x1 x2)= f(x1) f(x2) = y1y2 f(x2 x1)= f(x2) f(x1) = y2y1 又因为 满足交换律，故x1 x2= x2 x1 于是f(x1 x2)= f(x2 x1) ，因此y1y2 = y2y1 可见，满足交换律；同理由*满足交换律，可证 也满足交换律。 5.3 同态与同构 (3) 因为f是从到的满同态映 射，故对任意y1，y2，y3Y，必存在x1，x2，x3 X， 使得f(x1)= y1，f(x2)=

38、 y2，f(x3)= y3，而且有 f(x1 (x2*x3)= f(x1)f(x2*x3) = f(x1)(f(x2)f(x3)= y1(y2y3) f(x1 x2)*(x1 x3)= f(x1 x2)f(x1 x3) =(f(x1) f(x2)(f(x1)f(x3)= (y1y2)(y1y3) 5.3 同态与同构 又因为 对于*满足分配律，故 x1 (x2*x3)= (x1 x2)*(x1 x3) 于是f(x1 (x2*x3)= f(x1 x2)*(x1 x3) 因此y1(y2y3) = (y1y2)(y1y3) 同理可得(y2y3)y1= (y2y1)(y3y1) 所以，对于满足分配律，类

39、似可以证明对于 也满足分配律。 5.3 同态与同构 (4) 因为f是从到的满同态映 射，故对任意y1，y2Y，必存在x1，x2X，使得 f(x1)= y1，f(x2)= y2，而且有 f(x1 (x1*x2)= f(x1)f(x1*x2) = f(x1)(f(x1)f(x2)= y1(y1y2) f(x1*x2) x1)= f(x1*x2)f(x1) = (f(x1)f(x2)f(x1)= (y1y2)y1 5.3 同态与同构 又因为 对于*满足吸收律，故 x1 (x1*x2)=x1 (x1*x2) x1=x1 于是f(x1 (x1*x2)= f(x1) f(x1*x2) x1)= f(x1)

40、 因此y1(y1y2) = y1 (y1y2)y1 = y1 可见，对于满足吸收律；同理可证对于也满 足吸收律。 5.3 同态与同构 (5) 因为f是从到的满同态映 射，故对任意yY，必存在xX，使得f(x)= y，而且 有f(x x)= f(x)f(x) = yy 又因为 满足等幂律，故x x= x 于是f(x x)= f(x) 因此yy = y 可见，满足等幂律；同理可证也满足等幂律。 不难证明，若x分别是 和*的等幂元，则f(x)是分别 关于和的等幂元。 5.3 同态与同构 (6) 因为f是从到的满同态映 射，故对任意yY，必存在xX，使得f(x)= y，又因 为e1是关于 的幺元，所以

41、有 f(x) =f(x e1)= f(x)f(e1) = yf(e1) f(x) =f(e1 x)= f(e1)f(x) = f(e1)y 即f(e1) y = y f(e1)= y 因此f(e1)是关于的幺元；同理可证f(e2)是关于的 幺元。 5.3 同态与同构 (7) 因为f是从到的满同态映 射，故对任意yY，必存在xX，使得f(x)= y，又因 为1是关于 的零元，所以有 f(1) =f(x 1)= f(x)f(1) = yf(1) f(1) =f(1 x)= f(1)f(x) = f(1)y 即f(1)y = yf(1)= f(1) 因此f(1)是关于的零元；同理可证f(2)是关于的

42、 零元。 5.3 同态与同构 (8) 因为f是从到的满同态映 射，故对任意yY，必存在xX，使得f(x)= y，并且 有 f(e1) =f(x-1 x)= f(x-1)f(x) = f(x-1)y f(e1) =f(x x-1)= f(x)f(x-1) = yf(x-1) 即f(x-1)y = yf(x-1)= f(e1) 由(6)可知，f(e1)是关于的幺元，若取f(x-1)= y-1，便 有f(x-1)f(x) = f(x)f(x-1) 即y-1y = yy-1= f(e1) 5.3 同态与同构 因此f(x-1)是f(x)关于的逆元；同理可证，若对每个 zX均存在关于*的逆元z-1，则对每

43、个f(z)Y也均存 在关于的逆元f(z-1)。 5.3 同态与同构 定理5.9 说明，对于满同态映射，代数系统的许多 性质都能保持，如结合律、交换律、分配律、等幂 律、幺元、零元、逆元等，但这种保持性质是单向 的，即如果满同态于，则所 具有的性质，均具有。但反之不然，即所具有的某些性质，不一定具有。那么 ，在什么样的条件下，所具有的性质也完全具有呢？只有当两个代数系统之间的映 射是双射，即两个代数系统是同构的情况下才完全 具有这些性质。 5.3 同态与同构 同构映射是双射，而同态映射不一定要求是双射。 因此，同构不仅仅象满同态那样保持运算的单向， 而保持运算的双向。两个同构的代数，表面上似乎

44、很不相同，但在结构上实际没有差别，只不过是集 合中的元素名称和运算的标识不同而已。这样，当 探索新的代数系统的性质时，若发现或可证明该结 构同构于另外一个性质已知的代数系统，便能直接 知道新的代数系统的各种性质了。对于同构的两个 代数系统来说，在它们的运算表中除了元素和运算 的标记不同外，其它一切都是相同的。因此，可以 根据这些特征来识别同构的代数系统。 5.3 同态与同构 例例5.20 令与是同类型的，其中F=f 0 ，f 1，f 2，f 3，“”定义如表5-9所示；Z4=0，1 ，2，3，+4定义如表5-10，试证明 。 表5-9 表5-10 f 0 f 1 f 2 f 3+40 1 2

45、3 f 0 f 1 f 2 f 3 f 0 f 1 f 2 f 3 f 1 f 2 f 3 f 0 f 2 f 3 f 0 f 1 f 3 f 0 f 1 f 2 0 1 2 3 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 5.3 同态与同构 解：令 且对任意j=0，1，2，3有 则显然 为双射。根据表5-9和表5-10，对于所有i， j=0，1，2，3有 故 为从到的同态映射。因此， 。 +)(+)()( 44 jifff jiji 5.3 同态与同构 例例5.21 给定，其中S=，A，B，C， 和是一般的集合运算；又有，这里T = 1，2，5，10，且对于a，bT有ab

46、 = lcma，b ，ab = gcda，b，表5-11至表5-14给出四个运算 表。试说明 。 解：令fTS:f()=1，f(A)=2，f(B)=5，f(C)=10，可以 证明f是从到的同构映射， 故： 5.3 同态与同构 表5-11 表5-12 表5-13 表5-14 A B C A B C A B C A B C A A C C B C B C C C C C A B C A A B B A B C 1 2 5 101 2 5 10 1 2 5 10 1 2 5 10 2 2 10 10 5 10 5 10 10 10 10 10 1 2 5 10 1 1 1 1 1 2 1 2 1 1

47、 5 5 1 2 5 10 5.3 同态与同构 同构是一个关系，而且可以证明它是等价关系。 定理定理5.10 代数系统间的同构关系是等价关系。 证明：代数系统可以通过恒等映射与它自身 同构，即自反性成立。若 且对应 的同构映射为f，因为f的逆是由到的 同构映射，即 ，即对称性成立。 若f是由到的同构映射，g是从到的同构映射，那么g和f的复合gf就是 从到的同构映射，即传递性成立。 因此，代数系统间的同构关系是等价关系。 5.3 同态与同构 由于同构关系是等价关系，故令所有的代数系统构 成一个集合S，于是可按同构关系将其分类，得到 商集S/ 。因为同构的代数系统具有相同的性质， 故实际上代数系统

48、所需要研究的总体并不是S而是 S/ 。 在同态与同构中有一个特例，即具有相同集合的任 两个代数系统的同态与同构，这便是自同态与自同 构。 5.3 同态与同构 定义定义5.7 给定及fSS，若f为从到的同态映射，则称f是自同态映射；若f为从到的同构映射，则称f为自同构映射。 例例5.22 在例5.19中，当k 0时，f = kx是从到 的自同态映射；当k = 1或k = -1时，f = kx是从 到的自同构映射。 5.4 同余关系 本节我们讨论同态与同余关系的对应，为此先给出 同余关系的概念。 定义定义5.8 给定代数系统，且E为S中的等价关 系。定义E有代换性质(x1，x2，y1， y2Sx1

49、Ex2y1Ey2(x1 y1)E(x2 y2)。若E有代换性 质，则称E为中的同余关系。并且，称同余 关系E的等价类为同余类。 。 5.4 同余关系 由定义可知，同余关系是代数系统的集合中的等价 关系，并且在运算的作用下，能够保持关系的等价 类。即在x1 y1中，如果用集合S中的与x1等价的任 何其它元素x2代换x1，并且用与y1等价的任何其它元 素y2代换y1，则所求的结果x2 y2与x1 y1位于同一 等价类之中。亦即若x1E = x2E并且y1E = y2E，则 x1 y1E = x2 y2E。此外，同余关系与运算密切相 关。如果一个代数系统中有多个运算，则需要考察 等价关系对于所有这些

50、运算是否都有代换性质。如 果有，则说该代数系统存在同余关系；否则，同余 关系不存在。 5.4 同余关系 例例5.23 给定，其中Z是整数集合，+和是 一般加、乘法。假设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对于+运算不具有 代换性质。 5.4 同余关系

51、 至此可以说，R不是该结构上的同余关系。但为了 熟悉验证一个关系是否为同余关系，还是也考察R 对于运算的代换性质： 令i1，i2，j1，j2Z且i1Ri2和j1Rj2。于是，对任意i1，i2 ，j1，j2都有：(i1Ri2)(j1Rj2) (i1j1)R(i2j2) 因此，R对于运算具有代换性质。 可见，考察一个等价关系E对于有多个运算的代数 系统是否为同余关系，这里有个次序先后问题。 5.4 同余关系 选择得好，即你一下子就考察到了E对某个运算是 不具有代换性质，那么立刻便可断定E不是该结构 的同余关系，否则验证应继续下去，直至遇到不具 有代换性质的运算为止。如果对于所有运算都有代 换性质，

52、则E为该结构的同余关系。在例5.23中，首 先发现R对于+不具有代换性质，那么可断定R不是 该结构的同余关系。如果你首先验证是R对于的代 换性质，结果R对于有代换性质，至此你只是有希 望E是同余关系，但还得继续工作，考察R对于+的 代换性质，由此结果才能判定R是否为该结构的同 余关系。 5.4 同余关系 例例5.24 设A=a，b，c，d，对于由表5-15所确定的 代数系统以及由表5-16所定义的在A上的等 价关系R。容易验证，R是A上的同余关系。这个同 余关系将A划分成同余类为a，b和c，d。 表5-15 表5-16 a b c da b c d a b c d a a d c b a c

53、d c d a b d d b a a b c d 5.4 同余关系 例例5.25设A=a，b，c，d，对于由表5-17所确定的代 数系统以及由表5-16所定义的在A上的等价 关系R，考察R是否为A上的同余关系。 表5-17 解：由于对，R有 =R 因此，由表5-16所定义的在A上的 等价关系R不是一个同余关系。 a b c d a b c d a a d c b a c d c d a b d d b a 5.4 同余关系 由上述两例可知：在A上定义的等价关系R，不一定 是A上的同余关系，这是因为同余关系必须与定义 在A上的二元运算密切相关。 有了同余关系的概念后，现在可以给出它与同态映 射

54、的关系了，请看下面定理： 定理定理5.11 设与是同类型的且f为其同 态映射。对应于f，定义关系Ef如下： xEf y：f(x)= f(y)， 其中x，yS 则Ef是中的同余关系，并且称Ef为由同态映 射f所诱导的同余关系。 5.4 同余关系 证明：不难证明，Ef是S中的等价关系。下面往证Ef 有代换性质。令x1，x2，y1，y2S且x1Ef x2和y1Ef y2。 根据Ef的定义可知： f(x1)= f(x2)和f(y1)= f(y2) 于是f(x1)*f(y1)= f(x2)*f(y2) 又因为f是从到的同态映射，故得 f(x1)*f(y1)= f(x1 y1) ，f(x2)*f(y2)=

55、 f(x2 y2) 再应用Ef的定义，得(x1 y1)Ef (x2 y2) 综上则有(x1Ef x2)(y1Ef y2)(x1 y1)Ef (x2 y2) 5.4 同余关系 由于同态映射不惟一，根据定理5.11，可以推知同 余关系也是不惟一。 形象地说，一个代数系统的同态象可以看作是当抽 去该系统中某些元素的次要特性的情况下，对该系 统的一种粗糙描述。如果我们把属于同一个同余类 的元素看作是没有区别的，那么原系统的性态可以 用同余类之间的相互关系来描述。下面，用一个例 子来说明这一点。 5.4 同余关系 例例5.26 如表5-18所确定的两个代数系统和 。 表5-18 *1 0 -1 1 0 -1 1 1 0 1 0 -1 0 -1 -1 5.4 同余关系 映射 f()=1 f()=1 f()=1 f()=0 f()=0 f()= -1 明显地是由代数系统到的一个同态 映射。假如把代数系统看作是对六个带电 粒子，相互