离散数学教案 给定<S,O>及01,0r,0∈S,则 01为关于O的左零元：=(x)(x∈S→01Ox=01) 0r为关于O的右零元：=(x)(x∈S→xO0r=0r) 0为关于O的零元：=(x)(x∈S一0Ox=xO0=0) 定理5.2.4给定<S,⊙>且01和0r分别为关于⊙的左零元和右零元，则01= 0r=0且零元0是唯一的。 定理5.2.5给定<S,⊙>且|S|>1。如果0，e∈S,其中0和e分别为关于⊙ 的零元和么元，则0≠e。 8.逆元 给定<S,⊙>且么元e,x∈S,则 x为关于⊙的左逆元：=(3y)(y∈S∧x⊙y=e) x为关于⊙的右逆元：=(3y)(y∈S∧y⊙x=e) x为关于⊙可逆的：=（日y)(y∈S∧y⊙x=x⊙y=e) 给定<S,⊙>及么元e:x,y∈S,则 y为x的左逆元：y⊙x=C y为x的右逆元：=x⊙y=e y为x的逆元：=y⊙x=x⊙y=e 显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的 逆元表为x。 一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可 以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。 定理5.2.6给定<S,⊙>及么元e∈S。如果⊙是可结合的并且一个元素x的左 逆元x和右逆元xr存在，则x1=xr。 定理5.2.7给定<S,⊙>及么元e∈S。如果⊙是可结合的并且x的逆元x存在， 则x是唯一的。 9.可约律与可约元 给定<S,⊙>且零元0∈S,则 ⊙满足左可约律或是左可约的： =(x)(y)(2)(x,y,z∈S∧x≠0八x⊙y=x⊙z)→y=z),并称x是关于⊙ 6
离散数学教案 6 给定<S，○>及θl，θr，θ∈S，则 θl 为关于○的左零元:=( x)(x∈S→θl○x=θl) θr 为关于○的右零元:=( x)(x∈S→x○θr=θr) θ为关于○的零元:=( x)(x∈S→θ○x=x○θ=θ) 定理 5.2.4 给定<S，⊙>且θl 和θr 分别为关于⊙的左零元和右零元，则θl= θr=θ且零元θ是唯一的。 定理 5.2.5 给定<S，⊙>且|S|＞1。如果θ，e∈S，其中θ和 e 分别为关于⊙ 的零元和幺元，则θ≠e。 8．逆元 给定<S，⊙>且幺元 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) 给定<S，⊙>及幺元 e；x，y∈S，则 y 为 x 的左逆元:=y⊙x=e y 为 x 的右逆元:=x⊙y=e y 为 x 的逆元:=y⊙x=x⊙y=e 显然，若 y 是 x 的逆元，则 x 也是 y 的逆元，因此称 x 与 y 互为逆元。通常 x 的 逆元表为 x -1。 一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可 以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。 定理 5.2.6 给定<S，⊙>及幺元 e∈S。如果⊙是可结合的并且一个元素 x 的左 逆元 xl-1 和右逆元 xr -1 存在，则 xl-1 =xr -1。 定理 5.2.7 给定<S，⊙>及幺元 e∈S。如果⊙是可结合的并且 x 的逆元 x -1 存在， 则 x -1 是唯一的。 9.可约律与可约元 给定<S，⊙>且零元θ∈S，则 ⊙满足左可约律或是左可约的: =( x)( y)( z)((x，y，z∈S∧x≠θ∧x⊙y=x⊙z)→y=z)，并称 x 是关于⊙
离散数学教案 的左可约元。 ⊙满足右可约律或是右可约的： =(x)(y)(z)(x,y,z∈Sx≠0Ay⊙x=z⊙x)→y=z),并称x是关于⊙ 的右可约元。 若⊙既满足左可约律又满足右可约律或⊙既是左可约又是右可约的，则称⊙满足 可约律或⊙是可约的。 若x既是关于⊙的左可约元又是关于⊙的右可约元，则称x是关于⊙的可约元。 可约律与可约元也可形式地定义如下： ⊙满足可约律： =(x)(y)(z)(x,y,z∈SAx≠0A(x⊙y=x⊙z∧y⊙x=z⊙x)→y=z) 给定<S,⊙>且零元0，x∈S。 x是关于⊙的可约元： =(y)(z)(y,z∈S∧x≠0∧(x⊙y)=x⊙z∧y⊙x=z⊙x)→y=z)。 定理5.2.8给定<S,O>且O是可结合的，如果x是关于O可逆的且x≠0，则 x也是关于O的可约元。 证明设任意y,z∈S且有xOy=xOz或yOx=zOx。因为O是可结合的及x是关 于O可逆的，则有 xO(xOy)=(xOx)Oy=eOy=y =xO(xOz)=(xOx)Oz =eOz=z 故得xOy=xOz→y=2,同样可证得yOx=zOx一y=2,故x是关于O的可约元。 最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于 运算的各种性质。为确定起见，假定<S,O>及x,y,0,e∈S。 (1)运算O具有封闭性，当且仅当表中的每个元素都属于S。 (②)运算O满足交换律，当且仅当表关于主对角线是对称的。 (③)运算O是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元 素相同。 (④元素x是关于O的左零元，当且仅当x所对应的行中的每个元素都与x相同： 元素y是关于O的右零元，当且仅当y所对应的列中的每个元素都与y相同：元素0 7
离散数学教案 7 的左可约元。 ⊙满足右可约律或是右可约的: =( x)( y)( z)((x，y，z∈S∧x≠θ∧y⊙x=z⊙x)→y=z)，并称 x 是关于⊙ 的右可约元。 若⊙既满足左可约律又满足右可约律或⊙既是左可约又是右可约的，则称⊙满足 可约律或⊙是可约的。 若 x 既是关于⊙的左可约元又是关于⊙的右可约元，则称 x 是关于⊙的可约元。 可约律与可约元也可形式地定义如下： ⊙满足可约律: =( x)( y)( z)(x，y，z∈S∧x≠θ∧((x⊙y=x⊙z∧y⊙x=z⊙x)→y=z)) 给定<S，⊙>且零元θ，x∈S。 x 是关于⊙的可约元: =( y)( z)(y，z∈S∧x≠θ∧((x⊙y)=x⊙z∧y⊙x=z⊙x)→y=z))。 定理 5.2.8 给定<S，○>且○是可结合的，如果 x 是关于○可逆的且 x≠θ，则 x 也是关于○的可约元。 证明 设任意 y,zS 且有 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 故得 x○y=x○zy=z，同样可证得 y○x=z○xy=z，故 x 是关于○的可约元。 最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于 运算的各种性质。为确定起见，假定<S，○>及 x，y，θ，e∈S。 (1)运算○具有封闭性，当且仅当表中的每个元素都属于 S。 (2)运算○满足交换律，当且仅当表关于主对角线是对称的。 (3)运算○是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元 素相同。 (4)元素 x 是关于○的左零元，当且仅当 x 所对应的行中的每个元素都与 x 相同； 元素 y 是关于○的右零元，当且仅当 y 所对应的列中的每个元素都与 y 相同；元素θ
离散数学教案 是关于O的零元，当且仅当日所对应的行和列中的每个元素都与0相同。 (⑤)元素x为关于O的左么元，当且仅当x所对应的行中元素依次与行表头元素 相同：元素y为关于O的右么元，当且仅当y所对应的列中元素依次与列表头元素相 同：元素e是关于O的么元，当且仅当e所对应的行和列中元素分别依次地行表头元 素和列表头元素相同。 (6)x为关于O的左逆元，当且仅当位于x所在行的元素中至少存在一个么元，y 为关于O的右逆元，当且仅当位于y所在列的元素中至少存在一个么元：x与y互为 逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是 么元。 5.3同态与同构 本节将阐明两个重要概念一一同态与同构。在以后各节中，它们会经常被使用到。 定义5.3.1设<X,⊙>与<Y,O>是同类型的。称<X,⊙>同态于<Y,O>或<， O>为<X,⊙>的同态象，记为X,⊙><Y,O>,其定义如下： <X,⊙><Y,O>:=(臼f)(f∈YX∧(x1) (付x2)(x1,x2∈X-→f(x1⊙x2)=f(x1)Of(x2) 同时，称f为从<X,⊙>到<Y,O>的同态映射。 可以看出，同态映射「不必是唯一的。 两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构， 也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二 元运算的两个同类型代数结构<化，⊙，O>和<Y,⊕，⑧>的同态定义如下： <X,⊙，O>=<Y,⊕，⑧>：=(3f)(feYXA(x1) (x2)(x1,x2∈X→(f(x1⊙x2)=f(x1)⊕f(x2)Af(x1Ox2)=f(x1)⑧f(x2) 定理5.3.1如果<X,⊙><Y,O>且f为其同态映射，则<R(f),O>cY,O>。 由于函数feX的不同性质，将给出不同种类的同态定义。 定义5.3.2设<X,⊙><Y,O>且f为其同态映射。 ()如果f为满射，则称f是从<X,⊙>到<Y,O>的满同态映射。 (ii)如果f为单射（或一对一映射），则称f为从<X,⊙>到<Y,O>的单一同态映 射
离散数学教案 8 是关于○的零元，当且仅当θ所对应的行和列中的每个元素都与θ相同。 (5)元素 x 为关于○的左幺元，当且仅当 x 所对应的行中元素依次与行表头元素 相同；元素 y 为关于○的右幺元，当且仅当 y 所对应的列中元素依次与列表头元素相 同；元素 e 是关于○的幺元，当且仅当 e 所对应的行和列中元素分别依次地行表头元 素和列表头元素相同。 (6)x 为关于○的左逆元，当且仅当位于 x 所在行的元素中至少存在一个幺元，y 为关于○的右逆元，当且仅当位于 y 所在列的元素中至少存在一个幺元；x 与 y 互为 逆元，当且仅当位于 x 所在行和 y 所在列的元素以及 y 所在行和 x 所在列的元素都是 幺元。 5.3 同态与同构 本节将阐明两个重要概念——同态与同构。在以后各节中，它们会经常被使用到。 定义 5.3.1 设<X，⊙>与<Y，○>是同类型的。称<X，⊙>同态于<Y，○>或<Y， ○>为<X，⊙>的同态象，记为<X，⊙><Y，○>，其定义如下： <X，⊙><Y，○>:=(f)(f∈YX∧(x1) (x2)(x1，x2∈X→f(x1⊙x2)=f(x1)○f(x2))) 同时，称 f 为从<X，⊙>到<Y，○>的同态映射。 可以看出，同态映射 f 不必是唯一的。 两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构， 也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二 元运算的两个同类型代数结构<X,⊙,○>和<Y,,>的同态定义如下： <X,⊙,○><Y,,>:=(f)(fYX(x1) (x2)(x1,x2X→(f(x1⊙x2)=f(x1)f(x2)f(x1○x2)=f(x1)f(x2))) 定理 5.3.1 如果<X，⊙><Y，○>且 f 为其同态映射，则<R(f)，○><Y，○>。 由于函数 fYX 的不同性质，将给出不同种类的同态定义。 定义 5.3.2 设<X，⊙><Y，○>且 f 为其同态映射。 (i)如果 f 为满射，则称 f 是从<X，⊙>到<Y，○>的满同态映射。 (ii)如果 f 为单射(或一对一映射)，则称 f 为从<X，⊙>到<Y，○>的单一同态映 射
离散数学教案 (iii)如果f为双射（或一一对应），则称f为从<X,⊙>到<Y,O>的同构映射。 记为<X,⊙><X,O>。 显然，若f是从<X,⊙>到<Y,O>的同构映射，则f为从X,⊙>到<Y,O>的满 同态映射及单一同态映射，反之亦然。 例5.3.4给定<1，+>，其中I为整数集合，+为一般加法。 作函数feI:f(x)=kx,其中x,keI 则当k0时，f为<I,+>到<I,+>的单一同态映射。当k=-1或k=1时，f为从<I,+> 到<红，+>的同构映射。 综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说， 它能够保持运算的更多性质，为此，给出如下定理： 定理5.3.2给定<X,⊙，O><Y,⊕，⑧>且f为其满同态映射，则 (a)如果⊙和O满足结合律，则⊕和8也满足结合律。 (b)如果⊙和○满足交换律，则⊕和⑧也满足交换律。 (c)如果⊙对于O或O对于⊙满足分配律，则©对于⑧或⑧对于⊕也相应满足分配 律。 ()如果⊙对于O或O对于⊙满足吸收律，则⊕对于⑧或⑧对于⊕也满足吸收律。 ()如果⊙和O满足等幂律，则⊕和⑧也满足等幂律。 (f)如果e1和e2分别是关于⊙和O的么元，则f(el)和f(e2)分别为关于©和⑧ 的么元。 (g)如果01和62分别是关于⊙和O的零元，则f(01)和f(02)分别为关于⊕ 和⑧的零元。 ()如果对每个x∈X均存在关于⊙的逆元x-1,则对每个f(x)∈Y也均存在关于 ⊕的逆元f(x-1):如果对每个z∈X均存在关于O的逆元z-1,则对每个f(z)∈Y也 均存在关于⑧的逆元f(z-1)。 定理5.3.2告诉我们，对于满同态映射来说，代数系统的许多性质都能保持，如 结合律、交换律、分配律、等幂律、么元、零元、逆元等，但这种保持性质是单向的， 即如果<X,⊙>满同态于<Y,O>,则<X,⊙>所具有的性质，<Y,O>均具有。但反之 不然，即<Y,O>所具有的某些性质，X,⊙>不一定具有。不尽要问，在怎样条件下， <Y,O>所具有的性质<《，⊙>都完全具有呢？为了回答这个问题，需要引出两个代数 9
离散数学教案 9 (iii)如果 f 为双射(或一一对应)，则称 f 为从<X，⊙>到<Y，○>的同构映射。 记为<X,⊙><X, ○>。 显然，若 f 是从<X，⊙>到<Y，○>的同构映射，则 f 为从<X，⊙>到<Y，○>的满 同态映射及单一同态映射，反之亦然。 例 5.3.4 给定<I,+>，其中 I 为整数集合，+为一般加法。 作函数 fII:f(x)=kx，其中 x,kI 则当 k0 时，f 为<I,+>到<I,+>的单一同态映射。当 k=-1 或 k=1 时，f 为从<I,+> 到<I,+>的同构映射。 综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说， 它能够保持运算的更多性质，为此，给出如下定理： 定理 5.3.2 给定<X，⊙，○><Y，，>且 f 为其满同态映射，则 (a)如果⊙和○满足结合律，则和也满足结合律。 (b)如果⊙和○满足交换律，则和也满足交换律。 (c)如果⊙对于○或○对于⊙满足分配律，则对于或对于也相应满足分配 律。 (d)如果⊙对于○或○对于⊙满足吸收律，则对于或对于也满足吸收律。 (e)如果⊙和○满足等幂律，则和也满足等幂律。 (f)如果 e1 和 e2 分别是关于⊙和○的幺元，则 f(e1)和 f(e2)分别为关于和 的幺元。 (g)如果θ1 和θ2 分别是关于⊙和○的零元，则 f(θ1)和 f(θ2)分别为关于 和的零元。 (h)如果对每个 x∈X 均存在关于⊙的逆元 x-1，则对每个 f(x)∈Y 也均存在关于 的逆元 f(x-1)；如果对每个 z∈X 均存在关于○的逆元 z-1，则对每个 f(z)∈Y 也 均存在关于的逆元 f(z-1)。 定理 5.3.2 告诉我们，对于满同态映射来说，代数系统的许多性质都能保持，如 结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的， 即如果<X，⊙>满同态于<Y，○>，则<X，⊙>所具有的性质，<Y，○>均具有。但反之 不然，即<Y，○>所具有的某些性质，<X，⊙>不一定具有。不尽要问，在怎样条件下， <Y，○>所具有的性质<X，⊙>都完全具有呢?为了回答这个问题，需要引出两个代数
离散数学教案 结构同构的概念。 定义5.3.3设<X,⊙>与<Y,O>是同类型的。称<X,⊙>同构于<Y,O>,记为 <X,⊙>=Y,O>,其定义如下 <X,⊙>=<Y,O>:=(白)(f为从<X,⊙>到<灯，O>的同构映射或更详细地定义为： <X,⊙><Y,O>:=(臼f)(f∈YX∧f为双射∧f为从<X,⊙>到<Y,O>的同态映射) 由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同 态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单 向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结 构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它 们的所有发生“彼此相通”。 这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外 一个性质己知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的 两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是 相同的。因此，可以根据这些特征来识别同构的代数系统。 同构是一个关系，而且可以证明它是个等价关系，对此有如下定理： 定理5.3.3代数系统间的同构关系是等价关系。 证明显然<S,⊙<S,⊙>，因为恒等映射是同构映射。又若<S,⊙><T,O> 且f为其同构映射，则为从<T,O>到<S,⊙>的同构映射。因此，<T,O><S, ⊙>。再令<S,⊙><T,O>及<T,O><R,⑧>，则<S,⊙><R,⑧>。这里因为若f 为<S,⊙>到<T,O>的同构映射，g为<T,O>到<R,⑧>的同构映射，则go为从<S, ⊙>到<R,⑧>的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构 关系是等价关系。 由于同构关系是等价关系，故令所有的代数系统构成一个集合S,于是可按同构 关系将其分类，得到商集S/。因为同构的代数系统具有相同的性质，故实际上代 数系统所需要研究的总体并不是S而是S/。 在同态与同构中有一个特例，即具有相同集合的任两个代数系统的同态与同构， 这便是自同态与自同构。 定义5.3.4给定<S,⊙>及f∈SS。 f为自同态映射：=f为从<S,⊙>到<S,⊙>的同态映射。 10
离散数学教案 10 结构同构的概念。 定义 5.3.3 设<X，⊙>与<Y，○>是同类型的。称<X，⊙>同构于<Y，○>，记为 <X，⊙><Y，○>，其定义如下： <X，⊙><Y，○>:=(f)(f 为从<X，⊙>到<Y，○>的同构映射或更详细地定义为： <X，⊙><Y，○>:=(f)(f∈YX∧f 为双射∧f 为从<X，⊙>到<Y，○>的同态映射) 由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同 态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单 向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结 构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它 们的所有发生“彼此相通”。 这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外 一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的 两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是 相同的。因此，可以根据这些特征来识别同构的代数系统。 同构是一个关系，而且可以证明它是个等价关系，对此有如下定理： 定理 5.3.3 代数系统间的同构关系是等价关系。 证明 显然<S，⊙><S，⊙>，因为恒等映射是同构映射。又若<S，⊙><T, ○> 且 f 为其同构映射，则 f -1 为从<T, ○>到<S，⊙>的同构映射。因此，<T, ○><S， ⊙>。再令<S，⊙><T, ○>及<T, ○><R，>，则<S，⊙><R，>。这里因为若 f 为<S，⊙>到<T, ○>的同构映射，g 为<T, ○>到<R，>的同构映射，则 gof 为从<S， ⊙>到<R，>的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构 关系是等价关系。 由于同构关系是等价关系，故令所有的代数系统构成一个集合 S，于是可按同构 关系将其分类，得到商集 S/ 。因为同构的代数系统具有相同的性质，故实际上代 数系统所需要研究的总体并不是 S 而是 S/ 。 在同态与同构中有一个特例，即具有相同集合的任两个代数系统的同态与同构， 这便是自同态与自同构。 定义 5.3.4 给定<S，⊙>及 f∈SS。 f 为自同态映射:=f 为从<S，⊙>到<S，⊙>的同态映射