离散数学王元元习题解答(12)

第十一章 群、环、域

11.1 半群

内容提要

11.1.1 半群及独异点

定义 11.1 称代数结构为半群（semigroups），如果 ? 运算满足结合律．当半群含有关于 ? 运算的么元，则称它为独异点（monoid），或含么半群．

定理11.1 设为一半群,那么

（1）的任一子代数都是半群，称为的子半群．

（2）若独异点的子代数含有么元e,那么它必为一独异点,称为的子独异点．

定理11.2 设,是半群,h为S到S’的同态,这时称h为半群同态．对半群同态有

（1）同态象为一半群．

（2）当为独异点时，则为一独异点.

定理11.3 设为一半群,那麽

SS

（1）为一半群，这里S为S上所有一元函数的集合，○ 为函数的合成运算．

S

（2）存在S到S的半群同态．

11.1.2 自由独异点

定义 11.2 称独异点为自由独异点（free monoid）,如果有A?S使得 （1）e?A．

（2）对任意u?S，x?A,u?x ? e . 自由独异点（free monoid）,如果有A?S使得 （3）对任意u,v?S，x,y?A,若u?x = v?y,那么u = v,x = y．

（4） S由A生成,即S中元素或者为e, 或者为A的成员，或者为A的成员的“积”: ai1?a i2???aik (ai1,a i2,?,aik?A)

集合A称为S的生成集．顺便指出，当半群有生成集A＝｛a｝时，称为循环半群（cyclic semigroups）。

定理11.4 设为一自由独异点，A为它的生成集，g:S?A?M→M为一已知函数，m为M中已知元素，那么下列等式组定义了一个S到M的函数f； ??f(e)?m

f(w?x)?g(w,x,f(w))?其中w?S,x?A 。

定理11.5 设和为两个自由独异点，A，B分别为它们的生成集，且 ? A ? = ? B ?，那么和同构。

1

?11.1.3 半群及高斯半群

定义11.3 设为一半群，那么

（l）当 ? 满足交换律时，称为交换半群（commutative semigroups）。 （2）当S中元素均可约时，称 S为可约半群（cancelable semigroups）． （3）称S中元素a是b的因子（factor），如果有S中元素c，d，使 b = a?c，b＝d?a．

（4）在可约交换独异点中，若a是b的因子，同时 b又是 a的因子，那么称a, b相伴（correlate）．

定理11.6 设为可约交换独异点,那么S中相伴关系～为上同余关系．

定理11.7 设为可约交换独异点。

（1）S中元素a，b相伴，当且仅当有可逆元c（c有逆元）,使 a = b?c． （2）S中所有可逆元构成一个相伴类（相伴关系等价类）．

（3）S的相伴类具有相同的基数．

定理11.8 可约交换独异点的商半群（～为相伴关系）为一可约交换独异点，且 ?S/～? = ? S ?/?[e]~? 。

定义11.4 设为可约交换独异点．若a是S中不可逆元素，且除了a及所有可逆元为其因子外没有别的因子，那么称a为既约元，否则称a为可约元．

定义11.5 可约交换独异点称为高斯半群(Gauss semigroup)，如果S中不可逆元素均可分解为若干个（有限个）既约元素的积，且这种分解在相伴意义下是唯一的，即若a有两个分解

a = p1?p2???pr = q1?q2???qs 则r = s,且（适当变换运算次序）总可使pi与qi相伴。

习题解答

练习11.1

1． 证明：含么半群的可逆元素集合构成一子半群，即为半群的子半群． 证. 对任意x，y ? inv（S）, 则存在x-1,y-1?S 使x*x-1=x-1*x=e, y*y-1=y-1*y= e 。又半群中*运算满足结合律，因而

(x*y)*(y-1*x-1)=x*(y*y-1)*x-1=x*e*x-1=x*x1=e

同理(y-1*x-1) *(x*y)= y-1*(x-1*x)*y= e，于是 (x*y)-1=y-1*x-1?S ，即inv（S）对*封闭,从而 < inv（S）,*> 为< S , *>的子代数 。由定理11.1， < inv（S）,*>为< S , *>的子半群。

2． 设为一半群，z?S为左（右）零元．证明：对任一x?S,x?z(z?x)亦为左（右）零元。

证. 因为z为S的左（右）零元，于是，对任意a ? S,z* a = z（a*z = z）。考虑任一x?S，由于< S , *>是半群，于是*满足结合律，因而

(x*z)* a=x*（z* a）=x*z ， a * (z *x) = （a *z）* x= z * x 故x*z(z *x)为< S , *>的左（右）零元。

2

3．设为一半群，a，b，c为S中给定元素，证明:若a，b，c满足

a?c = c?a , b?c = c?b

那么，(a?b)?c = c?(a?b).。

证. 因为< S , *>为一半群，于是*运算满足结合律，又由已知a?c = c?a , b?c = c?b，故

(a*b)*c=a*(b*c)=a*(c*b)=(a*c)*b=(c*a)*b=c*(a*b)

4．设<{a,b},?>为一半群，且a?a = b 证明: （1）a?b = b?a （2）b?b = b

证. (1) 因为<{a,b} , *>为一半群，于是*运算满足结合律，又a*a=b，因而 a*b=a*(a*a)=(a*a)*a=b*a

(2) 因为< {a,b}, *>为半群，于是*运算封闭.设b*b≠b 则 b*b=a 。于是 ①若令a*b = b*a = a ，则

b*b = b*a*a = a*a = b 。 ②若令a*b = b*a = b， 则

b*b = a*a*b = a*b = b 综合①② ，b*b=b。

5．代数结构<{a,b,c,d},?>中运算 ? 如表11.1规定．

表 11.1 a b c d ? a a b c d b b c d a c c d a b d d a b c

（1）已知 ? 运算满足结合律，证明<{a,b,c,d},?>为一循环独异点．

（2）把{a,b,c,d}中各元素写成生成元的幂．

证.（1）由运算表11.1知，a为代数结构的幺元，又b2=c，b3=b2*b=c*b=d b4=b3*b=d*b=a 故b为其生成元。又*运算满足结合律，因此<{a,b,c,d},*>为循环独异点。

（2）解：由（1）知，b为其生成元，a=b0, b=b1, c=b2, d=b3， 同理可验证，d也为其生成元，a=d0, b=d3,c=d2, d=d1。

6．证明：循环半群必定是交换半群（参阅定义11.3之（1））。

证. 设< S , *>为循环半群，a为其生成元，则对任意x,y ? S 均有K1，K2 ?N, 使 x = a K1 , y = a K2

从而x* y = a K1 * a K2= a K1+ K2= a K2+ K1= a K2* a K1= y *x，因而< S , *>为交换半群。

7．证明：独异点元素可逆当且仅当它是么元的因子（参阅定义11.3之（3））。

-1 -1 -1

证. (?)设代数结构< S , * >为独异点，x? S可逆，则x? S，且x * x= x* x = e，于是x是e的因子。

(?)设x ?S为幺元e的因子，则存在a,b?S使e= a* x，e= x * b ，这说明a,为x的左逆元，

3

b为x的右逆元。又< S , * >的独异点，*满足结合律，由定理10.6 a=b为 x的逆元.，即x可逆。

8. 设为一半群，且对任意x,y?S，若x ? y则x?y ? y?x .

（1）求证S中所有元素均为等幂元（a称为等幂元,如果a?a = a ）。 （2）对任意元素x，y?S，x?y?x = x , y?x?y = y。

证.（1）对任意a ? S,假设a*a?a, 则由已知,(a *a)*a ?a*(a*a) 此与半群结合律矛盾, 故a*a= a ，即S中所有元素均为等幂元。

（2）假设 x?y?x ?x，则由已知，(x?y?x)*x?x*( x?y?x) ,但

(x?y?x)*x=(x*y)*(x*x)= x?y?x，x*( x?y?x)= (x*x)*(y*x)= x?y?x, 矛盾，故 x?y?x ?x 。

同理可证y?x?y = y 。

?9。设为一半群,且S中有元素a ,使得对于任意x?S ,均有S中元素u，v满足 a?u = v?a = x 证明 ：为一独异点。（提示:考虑x = a时的 u和v。）

证. 考虑x = a时的 u和v。由题意知,对元素a ? S,有u a, v a ?S满足：a*u a= v a* a= a。 由题意，对于任意x?S ,均有ux, vx?S满足： a* ux,= vx *a=x 由为半群，运算*满足结合律， 从而有

v a*x = v a*(a* ux) = (v a*a)* ux =a* ux = x x *ua = (vx*a)* ua = vx*(a* ua ) = vx*a = x

这说明v a，ua分别为的左右幺元，再由定理10.1，有幺元 e = v a= ua ，故 半群为独异点。

10. 问是否为自由独异点？为什么？问是否为自由独异点？为什么？其中S? N(自然数集)归纳定义如下:

（1）0,4,6?S.

（2）如果x,y?S则x+y?S.

（3）S中元素仅此而已.。

解. 不是自由独异点，因为只有唯一生成集A={1,-1}，但A不满足自由独异点的条件。

也不是自由独异点，因为显然S只有唯一生成集A= {4,6}，但A不满足自由独异点的条件之（3）。

?11．设为一由A生成的自由独异点，是一独异点。证明：对任一函数h：A→T，均存在唯一的函数H:S→T,使得 （1）对任意x?A,h(x) = H(x)．

（2）H为S到T的同态．

证. 对任一函数 h:A→T，设函数H：S→T 满足H（e1）=e2 。 ∵A生成S，

∴对任意x ?S 或x = e1 , 或x =ai1 * ai2 *?* aik , ai1 ai2 ? aik ?A , k?1， 又令，当x ?A时H(x) =h(x)，此外

H(x)=H(ai1 * ai2 *?* aik)=h(ai1) *h( ai2 )*?*h( aik )

4

显然H为S→T 的映射，且对任意u1 ,u2 ?S 若u1 ? e1 ， 则 H(u1 *u2)=H(u2)= e2 * H(u2)= H(e1 )*H(u2 )= H(u1 )*H(u2 ) 若 u2= e1 则

H(u1 *u2) = H(u1) = H(u1) * e2 = H(u1 )*H(e1 ) 若 u1 ?A,u2 ?A 则

H(u1 *u2) = h(u1)* h(u2) = H(u1 )*H(u2 )

若 u1 = ai1 * ai2 *?* aik ， ai1 ，ai2 ? ，aik ?A u2 ?A 则

H(u1 *u2)=H(ai1 * ai2 *?* aik * u2)

=h (ai1 )* h(ai2 )*?* h(aik) *h( u2)

= H(u1 )*H(u2 ) 若u1 ?A,u2= ai1 * ai2 *?* aik 同理可证。

若u1 = ai1 * ai2 *?* aik，u2= ai1 ?* ai2 ?*?* ail ?，ai1 ，ai2 ，?，aik ，ai1 ?， ai2 ?，?，ail??A 则

H(u1 *u2) =H(ai1 * ai2 *?* aik * ai1 ?* ai2 ?*?* ail ?)

=h (ai1 )* h(ai2 )*?* h(aik) *h(ai1 ?)* h(ai2 ?)* h(ail ?) = H(u1 )*H(u2 )

(由于,,都为独异点,故*都可结合) 即H为S到T的同态 且对任意 x ?A, h(x) = H(x) 。

假设另有H’: S→T 也满足对任意x ?A, h(x) = H’(x) 且为S到T的同态，则一定有 H’(e1)= e2= H(e1)

且对任意x ?A,H’(x) = h(x)= H(x)，而对与其余x ?S ， 设

x = ai1 * ai2 *?* aik ， ai1 ，ai2 ，? ，aik ?A则 H’(x) = H’(ai1 * ai2 *?* aik * u2)

= H’ (ai1 )* H’(ai2 )*?* H’(aik) *H’( u2)

= h (ai1 )* h(ai2 )*?* h(aik) *h( u2) = H(x)

故 H’= H ，即满足条件的函数是唯一的.

12．证明：可约交换独异点上的相伴关系为一等价关系． 证. 在可约交换独异点中，对任意a,b,c?S, (1) ∵a=a*e ∴a是a的因子,即a与a相伴， ∴S上相伴关系具有自反性。

(2) 设a 与 b具有相伴关系 ,则a是b的因子，同时b 又是a的因子,于是b与a也相伴。

即S上相伴关系具有对称性,

(3) 设a与b相伴，b与c相伴。则a是b的因子，b又是a的因子；b是c的因子，c也是

b的因子,于是存在x，x1 ，m ，m1使得 b=a*x,b=x*a,a=b*x1,a=x1*b c=b*m,c=m*b,b=c*m1,b=m1*c

从而 c=(a*x)*m=a*(x*m), c=m*(x*a)=(m*x)*a

a=(c*m1)*x1=c*(m1*x1)， a=x1*(m1*c)=(x1*m1)*c

即a是c的因子,同时c又是a的因子，故a 与c相伴。因而相伴关系具有传递性。综上，相伴关系是等价关系。

3m13．设S = {n ? m,n为自然数}，

2

5