离散数学(第二版)第5章代数结构

第5章代数结构代数系统的组成半群与独异点群子群与同态特殊的群陪集与同余关系环和域第5章 代数结构第5章代数结构5.1.1运算与代数系统在学习初等代数时,我们引入了自然数集合N、整数集合Z、有理数集合Q、实数集合R、复数集合C等数集。在这些数集中，着重研究的是集合上的各种运算,如+(加)、－(减)、×(乘)、÷(除)等运算。在实际工程应用中需要处理的对象并不都是单纯的整数、有理数、实数或复数。这些对象相互作用生成一个新的对象亦可定义为元素间的运算。5.1

代数系统的组成第5章代数结构在研究集合时,常常要研究所谓集合上的“运算”及该运算所具有的性质,如封闭性(closure)、交换律(alternative

law)、分配律(distributive

law)、结合律(associative

law)、同态(homomorphism)、同构(isomorphism)等。因此，在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算(operation)。第5章代数结构定义5.1.1设A、B是非空集合，函数f：An→B称为集

合A上的一个n元运算。当n=1时，称f为一元运算；当n=2时，称f为二元运算(binary

operation)。定义5.1.2设A、B是非空集合，

f：

An→B是集合A上的一个n元运算。若⊆B

A，

则称该

n元运算是封闭的。当集合A是有限集时，例如A={a1,a2,…,an}时，A上的一元代数运算Δ和二元代数运算的运算结果分别用如表5.1.1(a)和(b)所示。第5章代数结构表5.1.1第5章代数结构形如表5.1.1的表常常被称为运算表，它由运算符、行表头元素、列表头元素及运算结果四部分组成。当集合A的元素很少，特别限于少数几个时，代数系统中的运算常常用这种表给出。其优点是简明直观，一目了然。表5.1.2第5章代数结构定义5.1.3设A是一个非空集合，fi是A上的ni元运算，其中i=1，2，…，m。由A及f1,f2,…，fm组成的系统称为代数系统，记为〈A，f1,f2,…，fm〉。集合A称为代数系统〈A,f1,f2,…,fn〉的载体。例2设Z是整数集合，N4是Z中由模4的同余类组成的同余类集，在N4上定义两个二元运算+4和×4分别如下：对于任意的［i］，［j］∈N4，有［i］

+4［j］=［(i+j)(

mod

4)］［i］

×4［j］=［(i×j)(

mod

4)］第5章代数结构试给出代数系统〈N4，+4，×4〉的运算+4和×4的运算表。解 N4

={［0］，

［1］，

［2］

，

［3］}，

运算+4和×4的运算表如表5.1.3所示。表5.1.3第5章代数结构定义5.1.4设两个代数系统〈A，f1,f2,…，fm

〉和〈T，g1,g2,…，gm

〉，如果fi和gi(1≤i≤m)具有相同的元数，则称这两个代数系统是同类型的。〈A，f1,f2,…，fm

〉代表一个代数系统，除特别指明外，其中运算符fi为一元或二元运算。根据需要对A及f1,f2,…，fm可置不同的集合符和运算符。第5章代数结构5.1.2运算的性质与代数常元代数系统的性质与运算的性质密切相关。对于实数集上的四则运算，大家可自如使用结合律、交换律、分配律、消去律等运算规律。显然，任意对象和运算构成的代数系统并不一定具备上述运算规律。下面将讨论二元运算的各种运算规律及代数常元。定义5.1.5给定代数系统〈A，*〉，*是A上封闭的二元运算，如果对于任何x，y∈A，均有x*y=

y*x则称运算*满足交换律或*是可交换的。第5章代数结构定义5.1.6给定代数系统〈A，*〉，*是A上封闭的二元运算，如果对于任何x，y，z∈A，均有(x*y)*z=x*(y*z)则称运算*满足结合律或*是可结合的。第5章代数结构，*〉，定义5.1.7

给定代数系统〈A，

和*是A上封闭的二元运算，如果对于任何x，y，z∈A，均有x*(y

z)=(x*y)

(x*z)则称运算*对于

满足左分配律，

或者*对于

是可左分配的。如果对于任何x，y，z∈A，均有(y

z)*x

=(y*x)

(z*x)满足右分配律，

或者*对于

是可右分则称运算*对于配的。*对于

既满足左分配律又满足右分配律，

则称*对于满足分配律或是可分配的。第5章代数结构定理5.1.1设〈A，，*〉是代数系统，和*是A上封闭的二元运算，

且*是可交换的。如果*对于

满足左分配律(或右分配律)，

则*对于

满足分配律。证明

不妨设*对于

满足左分配律，

任取x，

y，

z∈A，均有x*(y

z)=(x*y)

(x*z)，则(y

z)*x=

x*(y

z)=(x*y)

(x*z)=(y*x)(z*x)故*对于

也满足右分配律，

因此*对于

满足分配律。同理可证，

如果*对于

满足右分配律，

则*对于

满足分配律。证毕第5章代数结构，*〉，定义5.1.8

给定代数系统〈A，

和*是A上封闭的二元运算，

且

和*是可交换的。如果对于任何x，

y∈A，均有x

(x*y)=xx*(x

y)=x和运算*满足吸收律或可吸收的。则称运算第5章代数结构定义5.1.9给定代数系统〈A，*〉，其中*是集合A上封闭的二元运算，如果对于任何x∈A，均有x*x=x，则称运算*是等幂的；如果存在x∈A，使得x*x=x，则称x是关于运算*的等幂元。对于等幂元，不难证明以下定理。定理5.1.2若x是代数系统〈A，*〉中关于*的等幂元，则对于任意正整数n，均有xn=x。第5章代数结构定义5.1.10给定代数系统〈A，*〉，其中*是集合A上封闭的二元运算。如果存在el

∈A，使得对于任何x∈A，均有el*x=x，则称el

是A上关于运算*的左幺元或左单位元；

如果存在er

∈A，使得对于任何x∈A，均有x*er

=x，则称er是A上关于运算*的右幺元或右单位元；如果存在e∈A，使得对于任何x∈A，均有x*e=e*x=x，则称e是A上关于运算*的幺元(identity)或单位元。第5章代数结构定义5.1.11给定代数系统〈A，*〉，其中*是集合A上封闭的二元运算。如果存在θl

∈A，使得对于任何x∈A，均有θl*x=θl，则称θl

是A上关于运算*的左零元；如果存在θr

∈A，使得对于任何x∈A，均有x*θr

=θr，则称θr是A上关于运算*的右零元；如果存在θ∈A，使得对于任何x∈A，均有θ*x=x*θ=θ，则称θ是A上关于运算*的零元(zero)。第5章代数结构幺元或零元在代数系统中起着特殊的作用，通常称它们为A中的特异元或代数常元。对于存在代数常元的代数系统，为了突出代数常元，也经常将代数常元写在运算的后面。如例2的代数系统〈N4，+4,×4〉可以记为代数系统〈N4，+4,×4,［0］，［1］〉，其中［0］为+4的幺元和×4的零元，［1］为×4的幺元。这样含有代数常元的代数系统具有三个组成要素：载体、运算、代数常元。第5章代数结构表5.1.4第5章代数结构定理5.1.3给定代数系统〈A，*〉，其中*是集合A上的二元运算。若el和er分别是关于*的左、右幺元，则el=er，且*存在唯一幺元e。证明

(1)首先证明el

=er

。由于el和er

分别是关于*的左、右幺元，故er

=el

*er

=el第5章代数结构(2)证明*存在唯一幺元e。令e=er

，显然e为*运算的幺元。设e1，e2∈A都是*运算的幺元，显然e1=e1*e2=e2故*运算存在唯一幺元。证毕第5章代数结构定理5.1.4给定代数系统〈A，*〉，其中*是集合A上的二元运算。若θl

和θr

分别是关于*的左、右零元，则θl

=θr

，且*存在唯一零元θ。证明

(1)证明θl

=θr。由于θl

和θr

分别是关于*的左、右零元，故θl

=θl

*θr

=θr第5章代数结构(2)证明*存在唯一零元θ。令θ=θr

，显然θ为*运算的零元。设θ1，θ2∈A都是*运算的零元，显然θ1=θ1*θ2=θ2故*存在唯一零元θ。证毕第5章代数结构定理5.1.5给定代数系统〈A，*〉，且|A|＞1。如果θ，e∈A，其中θ和e分别为关于*的零元和幺元，则θ≠e。证明用反证法。设θ=e,则x∈A，必有x=x*e=x*θ=θ=e，于是A中的所有元素都是相同的，即|A|=1。这与|A|＞1相矛盾，故θ≠e。证毕第5章代数结构定义5.1.12给定代数系统〈A，*〉，其中*是集合A上封闭的二元运算，e为关于*的幺元。对于任何x∈A，如果存在yl

∈A，使得yl*x=e，则称yl是x的左逆元；如果存在yr∈A，使得x*yr

=e，则称yr

是x的右逆元；如果存在y∈A，使得x*y=y*x=e，则称y是x的逆元(inverse

elements)。显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表示为x－1。第5章代数结构定理5.1.6给定代数系统〈A，*〉，其中*是集合A上封闭的二元运算，e为关于*的幺元。如果*是可结合的，且

A上每一个元素都有左逆元，则这个代数系统中任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元是唯一的。证明设a,b,c∈A,且b是a的左逆元，c是b的左逆元。因为(b*a)*b=e*b=b第5章代数结构所以a*b=(e*a)*b=((c*b)*a)*b=(c*(b*a))*b=c*((b*a)*b)=c*b=e因此，b也是a的右逆元。第5章代数结构设元素a有两个逆元b与c，则b=b*e=b*(a*c)=(b*a)*c=e*c=c因此，a的逆元是唯一的。证毕第5章代数结构定义5.1.13给定代数系统〈A，*〉，*是集合A上封闭的二元运算。存在x∈A，且x不是运算*的左零元，对于任何y,z∈A，如果x*y=x*z，则有y=z，称x是关于*的左可约元。存在x∈A，且x不是运算*的右零元，对于任何y,z∈A，如果y*x=z*x，则有y=z，称x是关于*的右可约元。对于任何x，y，z∈A，且x不是运算*的左零元，如果x*y=x*z，则有y=z，称运算*满足左可约律。第5章代数结构(4)对于任何x，y，z∈A，且x不是运算*的右零元，如果y*x

=z*x，则有y=z，称运算*满足右可约律。(5)若x既是关于*的左可约元又是关于*的右可约元，则称x为关于*的可约元。若运算*既满足左可约律又满足右可约律，则称*满足可约律。第5章代数结构半群定义5.2.1给定代数系统〈S，*〉，*是S上的二元运算，如果满足：*在S上封闭。*在S上可结合，则称〈S，*〉为半群(semigroup)。5.2

半群与独异点第5章代数结构定理5.2.1设〈S，*〉是一个半群，如果S是一个有限集，则存在a∈S，使得a*a=a。证明设|S|=n，b∈S，由运算*的封闭性以及S为有限集可知：根据鸽巢原理，

必有bi=bj

(j＞i)

，

令p=j－i,

显然p≥1,

则有bi=bj

=bp+i=bp*bibi=bp*bibi+1=bp*bi+1…bkp=bp*bkp

(kp≥i

)第5章代数结构再由bkp=bp*bkp递推可得：bkp=bp*bkp=bp*bp*bkp=b2p*bkp=……=

bkp*bkp令a=bkp，则有a=a*a。证毕第5章代数结构5.2.2独异点定义5.2.2给定代数系统〈M，*〉，*是M上的二元运算，如果满足：*在M上封闭；*在M上可结合；*有幺元，则称〈M，*〉为独异点(monoid)。由定义可以看出，独异点是含有幺元的半群。因此通常亦将独异点叫做含幺半群。有时为了强调幺元e的存在性，独异点也可表示为〈M，*，e〉。第5章代数结构定理

5.2.2设〈M，*〉是一个独异点，｜M｜≥2，则在关于运算*的运算表中任何两行或两列都是不相同的。证明设M中关于运算*的幺元是e。对于任何a,b∈M且a≠b，均有e*a=a≠b=e*ba*e=a≠b=b*e所以,在*的运算表中不可能有两行或两列是相同的。证毕第5章代数结构群的定义及其性质定义5.3.1给定代数系统〈G，*〉，*是G上的二元运算，如果满足：*运算在G上封闭；*运算是可结合的；关于*运算存在幺元e；G中每个元素关于*运算都是可逆的，即G中每个元素均存在逆元,则称〈G，*〉是群(Group)。5.3

群第5章代数结构定义5.3.2给定群〈G，*〉，若G是有限集，则称〈G，*〉是有限群。G的基数称为该有限群的阶数(order)。若集合G是无限的，则称〈G，*〉为无限群。第5章代数结构定理5.3.1设〈G，*〉是群，且|G|＞1，则群〈G，*〉无零元。证明设〈G，*〉是群，且|G|＞1，幺元为e，采用反证法。假设群〈G，*〉有零元θ，根据定理5.1.5知，θ≠e，又因为x∈G，均有x*θ=θ*x=θ≠e，所以，零元θ不存在逆元，与〈G，*〉是群矛盾，所以群〈G，*〉无零元。证毕第5章代数结构定理5.3.2在任何一个群〈G，*〉中，幺元是唯一的等幂元。证明因为e*e=e，故e是群〈G，*〉的等幂元，假设a∈G，a是等幂元，由于〈G，*〉是群，a必然存在逆元a－1∈G，则有a=e*a=(a－1*a)*a=a－1*(a*a)=a－1*a=e故幺元e是群〈G，*〉中的唯一等幂元。证毕第5章代数结构定理5.3.3给定群〈G，*〉，则a，b，c∈G，若a*b=a*c或b*a=c*a，必有b=c，即群满足消去律。证明设a*b=a*c，由于〈G，*〉是群，a必然存在逆元a－1∈G，则有a－1*(a*b)=a－1*(a*c)(a－1*a)*b=(a－1*a)*ce*a=e*cb=c同理可证，若b*a=c*a，也必有b=c。证毕第5章代数结构定理5.3.4给定群〈G，*〉，则对于任何a，b∈G：存在唯一的x∈G，使得a*x=b，即方程a*x=b在群〈G，*〉中有唯一解x。存在唯一的y∈G，使得y*a=b，即方程y*a=b在群〈G，*〉中有唯一解y。证明

(1)设a的逆元为a－1，令x=a－1*b,则a*x=a*(a－1*b)=(a*a－1)*b=e*b=b，即x=a－1*b是a*x=b的解。第5章代数结构若另有解x′满足a*x′=b，则a－1*(a*x′)=a－1*bx′=a－1*b=x故方程a*x=b在群〈G，*〉中的解唯一。类似地可以证明(2)，于是定理得证。证毕第5章代数结构定理5.3.5

设〈G，

*〉是群，

则a，

b∈G，

(a*b)－1

=b－1*a－1。证明设a的逆元为a－1，b的逆元为b－1，则

(a*b)*(b－1*a－1)=a*(b*b－1)*a－1=(a*e)*a－1=a*a－1=e(b－1*a－1)*(a*b)=b－1*(a－1*a)*b

=(b－1*e)*b=b－1*b

=e故(a*b)－1=b－1*a－1。证毕第5章代数结构5.3.2群中元素的阶定义5.3.3给定群〈G，*〉，幺元e，对于a∈G，使得

an=e的最小正整数n称为a的阶或周期，记为|a|，并称a的阶是有限的,否则,称a的阶是无限的。第5章代数结构定理5.3.6给定群〈G，*〉，对于任何a∈G，a与a－1具有相同的阶。证明由定理5.3.5可知，对任意正整数k，均有(a－1)k=(ak)－1ak=［(a－1)k］－1(1)(2)由式(1)和式(2)知，a的阶有限当且仅当a－1的阶有限，因此，若a的阶无限，当且仅当a－1的阶无限。下面考察a和a－1的阶均有限的情况：第5章代数结构设a∈G，a的阶是n，a－1的阶是m，则由式(1)知，(a－1)n=(an)－1=e－1=e，则m≤n。由式(2)知，am=［(a－1)m］－1=e－1=e，则n≤m。从而得到，n=m，因此a与a－1具有相同的阶。证毕第5章代数结构定理5.3.7给定群〈G，*〉，a∈G，a的阶为n∈N，k为整数，则ak=e当且仅当k=mn时，其中m为整数。证明充分性。设k=mn，则ak=amn=(an)m=em=e必要性。设ak=e，令k=mn+r，0≤r＜n，则e=ak=amn+r=amn*ar=(an)m*ar=em*ar

=ar又因为a的阶为n，所以得到r=0，即k=mn。证毕第5章代数结构推论若an=e且没有n的因子d(1＜d＜n)，使得ad=e，则a的阶为n。第5章代数结构子群定义5.4.1设〈A，f1,f2,…，fm〉是一代数系统，A′是个非空集合且如果满足：A′⊆

A；运算f1,f2,…，fm在A′上封闭,则称〈A′，f1,f2,…，fm

〉是〈A，f1,f2,…，fm

〉的子代数。5.4

子

群

与

同

态第5章代数结构*〉是群，则称〈H，*〉为群〈G，*〉的子群。对于任何群〈G，*〉，e

是关于*的幺元，〈{e}，*〉和〈G，*〉都是〈G，*〉的子群，并且称为群〈G，*〉的平凡子群(trivial

subgroup)。定义5.4.2给定群〈G，*〉及非空集合H

⊆G，若〈H，第5章代数结构定理5.4.1〈H，*〉是群〈G，*〉的子群，则必有eH=eG，其中eH和eG分别是〈H，*〉和〈G，*〉的幺元，即群与其子群具有相同的幺元。证明

eH是子群〈H，*〉的幺元，任取x∈H，则有x∈G，因此eH

*x

=x=eG*x根据群满足消去律可得，eH=eG。证毕第5章代数结构定理5.4.2给定群〈G，*〉及非空子集HG，则〈H，*〉是〈G，*〉的子群，当且仅当对于任何a，b∈H，有a*b∈H，且对于任何a∈H，有a－1∈H。证明必要性。a，b∈H，因为〈H，*〉是群，*在H上封闭，所以a*b∈H。设eH和eG分别是〈H，*〉和〈G，*〉的幺元，a∈H，又设a在子群〈H，*〉中的逆元为b∈H，因为a*b=eH=eG=a*a－1，所以b=a－1，故a－1∈H。第5章代数结构充分性。由于a，b∈H，有a*b∈H，故H对*运算封闭，运算*的可结合性在H上是可保持的，又由于a∈H，有a－1∈H，故H

中的元素均存在逆元，且a*a－1=e∈H，即H中存在幺元，故〈H，*〉是〈G，*〉的子群。证毕第5章代数结构定理5.4.3给定群〈G，

*〉及非空H

⊆G，

则〈H，

*〉是〈G，

*〉的子群当且仅当

a，

b∈H，

必有a*b－1∈H。证明必要性是显然的。充分性。(1)证明〈G，*〉中的幺元e也是〈H，*〉中的幺元。a∈H，有e=a*a－1∈H，即〈H，*〉中有幺元e。(2)证明H中每个元素都有逆元。a∈H，因为e∈H，则有e*a－1∈H，即a－1∈H。第5章代数结构(3)证明*在H上是封闭的。a，b∈H，由(2)知b－1∈H，则a*b=a*(b－1)－1∈H。(4)运算*的可结合性在H上是可保持的。因此〈H，*〉是〈G，*〉的子群。证毕第5章代数结构*〉是〈G，*〉的子群当且仅当即H对*运算封闭。证明必要性是显然的。定理5.4.4给定群〈G，*〉及非空有限集H

⊆G，则〈H，a，b∈H，均有a*b∈H，充分性。设e是群〈G，*〉的幺元，令|H|=n。(1)

a，b∈H，有a*b∈H，即H对*运算封闭。(2)a∈H，。第5章代数结构根据鸽巢原理，必存在i，j∈{1，2，…，n+1}，1≤i＜j≤n+1且满足ai=aj，因此有，e*ai=aj－i*ai。由〈G，*〉是群，*满足消去律，可得e=aj－i，所以H中有幺元e=aj－i

。利用(2)，如果j－i＞1，则a－1=aj－i－1∈H；如果j－i=1则a=e，即a－1=e－1=e∈H。因此H中任何元素a的逆元a－1∈H。运算*的可结合性在H上是可保持的。综上所述，〈H，*〉是〈G，*〉的子群。证毕第5章代数结构5.4.2同态与同构定义5.4.3设A=〈S,*〉和A′=〈S′,*′〉是两个代数系统，其中，S和S′是集合，*和*′为二元运算。设f是从S到S′的一个映射，若对任意a,b∈S满足：f(a*b)=f(a)*′f(b)则称f为由A到A′的一个同态映射，也称A同态于A′，记为A~A′。通常把〈f(S),*′〉称为A在同态映射f下的同态像。两个代数系统A=〈S,*〉和A′=〈S′,*′〉在同态下的相互关系可以用图5.4.1来直观描述。第5章代数结构图5.4.1第5章代数结构定理5.4.5给定A=〈S，*〉和A′=〈S′,*′〉是两个代数系统，f为从代数系统A到代数系统A′的同态映射，则：如果A=〈S，*〉是半群，则A在映射f下的同态像〈f(A)，*′〉是半群。如果A=〈S，*〉是独异点，则A在映射f下的同态像〈f(A)，*′〉是独异点。如果A=〈S，*〉是群，则A在映射f下的同态像〈f(A)，*′〉是群。第5章代数结构证明

(3)任取a,b∈f(A)，必存在x,y∈A，使得f(x)=a，f(y)=b，故a*′b=f(x)*′f(y)=f(x*y)∈f(A)故*′运算在f(A)上封闭。任取a,b,c∈f(A)，必存在x,y,z∈A，使得f(x)=a，f(y)=b，f(z)=c，因为*运算在A上是可结合的，所以有a*′(b*′c)=f(x)*′(f(y)*′f(z))=f(x)*′f(y*z)=f(x*(y*z))=f((x*y)*z)=f(x*y)*′f(z)=(f(x)*′f(y))*′f(z)=(a*′b)*′c第5章代数结构设eA是群〈A，*〉的幺元，任取a∈f(A)，必存在x∈A，使得f(x)=a，则f(eA)*′a=f(eA)

*′f(x)=f(eA*x)=f(x)=aa*′f(eA)

=f(x)*′f(eA)=f(x*eA)=f(x)=a故f(eA)是代数系统〈f(A)，*′〉中的幺元。第5章代数结构任取a∈f(A)，必存在x∈A，使得f(x)=a。因为〈A，*〉是群，所以x－1∈A，有f(x－1)∈f(A)，则f(x－1)

*′a=f(x－1)

*′f(x)=f(x－1*x)=f(eA)a*′f(x－1)=f(x)*′f(x－1)=f(x*x－1)=f(eA)故f(x－1)是a的逆元。综上所述，代数系统〈f(A)，*′〉是群。(1)、(2)的证明留作练习。证毕第5章代数结构推论1设g为从群〈G，*〉到群〈H，〉的群同态映射，

若〈S，

*〉是群〈G，

*〉的子群且g(S)={g(a)|a∈S}，则〈g(S)，

〉为群〈H，

〉的子群。证明设〈S，*〉是群〈G，*〉的子群且g(S)={g(a)|a∈S}任取x，y∈g(S)，存在a，b∈S，使得x=g(a)，y=g(b)。由于a*b－1∈S，因此有x

y－1=g(a)

(g(b))－1=g(a)

g(b－1)=g(a*b－1)∈g(S)故〈g(S)，

〉为群〈H，

〉的子群。证毕第5章代数结构推论2

若g是从群〈G，

*〉到代数系统〈H，

〉的满同态映射，则代数系统〈H，〉为群。设f是群〈G，*〉到群〈H，*〉的同态，群〈G，*〉的幺元的像一定是群〈H，*〉的幺元，但群〈H，*〉幺元的原像并不一定唯一。这里引入同态核的概念。第5章代数结构定义5.4.5设f是群〈G，*〉到群〈H，*〉的同态映射，

eH是群〈H，*〉中的幺元，令Kf＝{x|x∈G

∧f(x)＝eH}，称Kf为群同态映射f的同态核(kernal)。第5章代数结构〉的同态映射，定理5.4.6设f为群〈G，*〉到群〈H，则f的同态核Kf是G的子群。证明

设群〈G，

*〉和群〈H，

〉的幺元分别为e1、e2，f的同态核记为Kf，则e2=f(e1),对任意的k1,k2∈Kf，有f(k1*k2)=f(k1)

f(k2)=e2

e2=e2故k1*k2∈Kf，*运算在Kf上封闭。第5章代数结构对任意的k∈Kf，有f(k－1)=［f(k)］－1=(e2)－1=e2故k－1∈Kf，所以f的同态核Kf是G的子群。证毕第5章代数结构定义5.4.6

设A=〈S，

*〉是一个代数系统，

如果f为从

A=〈S，

*〉到A=〈S，

*〉

的同态映射，

则称f为由A到A的一个自同态映射。如果f为从A=〈S，

*〉到A=〈S，

*〉

的同构映射，

则称f为由A到A的一个自同构映射。第5章代数结构定理5.4.7设G为所有具有一个二元运算代数系统的集合，则G中代数系统间的同构关系是等价关系。证明(1)任取〈X，*〉∈G，因为恒等映射是同构映射，即〈X，*〉≌〈X，*〉，显然同构关系是自反的。(2)

任取〈X，

*〉，

〈Y，

〉∈G，

若〈X，

*〉≌〈Y,〉且f为其同构映射，

则f1为从〈Y,

〉到〈X，

*〉的同构映射。因此，

〈Y,

〉≌〈X，

*〉,

即同构关系是对称的。第5章代数结构(3)任取〈X，*〉，〈Y，〉，〈Z，⊙〉∈G，设〉≌〈Z，⊙〉，f为〈X，*〈X，

*〉≌〈Y,

〉，

〈Y,到〈Y，

〉的同构映射，

g为〈Y，

〉到〈Z，

⊙〉的同构映射，

则gf为从〈X，

*〉到〈Z，

⊙〉的同构映射，

即〈X，*〉≌〈Z，⊙〉。因此，传递性成立。可见,同构关系满足自反性、对称性和传递性。因此，同构关系是等价关系。证毕第5章代数结构5.5.1交换群定义5.5.1给定群〈G，*〉，若*是交换的，则称〈G，*〉是交换群(或阿贝尔群、Abel群)。5.5

特

殊

的

群第5章代数结构定理5.5.1设〈G，*〉是一个群，则〈G，*〉是一个交换群当且仅当对于任何a,b∈G，有(a*b)2=a2*b2。证明必要性。设〈G，*〉是一个交换群，任取a,b∈G，则有：(a*b)2=(a*b)*(a*b)=((a*b)*a)*b=(a*(b*a))*b=(a*(a*b))*b=((a*a)*b)*b=(a*a)*(b*b)=a2*b2第5章代数结构充分性。设〈G，*〉是一个群，且对于任何a,b∈G，有(a*b)2=a2*b2，则由：(a*b)*(a*b)=(a*a)*(b*b)a－1*(a*b)*(a*b)*b－1=a－1*(a*a)*(b*b)*b－1(a－1*a)*(b*a)*(b*b－1)=(a－1*a)*(a*b)*(b*b－1)b*a=a*b得出*可交换，所以〈G，*〉是一个交换群。证毕第5章代数结构定理5.5.2设〈G，*〉是一个群，如果对于任何x∈G，有x2=e，则〈G，*〉是一个交换群。证明任取x,y∈G，由已知条件知，(x*y)2=e，x2*y2=e*e=e，从而得到：(x*y)2=x2*y2，根据定理5.5.2，〈G，*〉是一个交换群。证毕第5章代数结构5.5.2置换群定义5.5.2令S是非空有限集合，从S到S的双射p：S→S称为集合S上的置换，|S|称为置换的阶。若S={x1，x2，…，xn}，则一个n阶置换p可表示为设|S|=n，用Sn表示S中的所有置换的集合。显然，Sn含有n!个不同的置换。第5章代数结构在Sn上可以定义两种二元运算∘和

，其中∘称为左复合运算，

称为右复合运算。对于任何pi，pj∈Sn，

pi

pj表∘示先进行pj置换，

再进行pi置换，

pi

pj表示先进行pi置换，

再进行pj置换。事实上，置换既是函数又是二元关系，置换的左复合就是函数的复合运算，而置换的右复合

就是关系的复合运算，对于任意x∈S有：(pi

pj)(x)=(p∘j

pi)(x)=pj(pi(x))为了避免混淆，下面只对右复合

进行讨论，关于左复合有类似的结论。第5章代数结构定理5.5.3〈Sn，

〉是一个群，其中

是置换的右复合运算。证明由于Sn是S上所有n!个不同的置换构成的集合，且每一个置换又都是S上的一个双射，因此由函数和双射的性质很容易得到以下结论：任取pi，pj∈Sn，pi

pj∈Sn，所以

在Sn上是封闭的。任取pi，pj，pk∈Sn，(pi

pj)

pk=pi

(pj

pk)，所以在Sn上是可结合的。第5章代数结构(3)存在恒等置换pe=Is∈Sn，对于任何pi

∈Sn，pe

pi

=pi

pe=pi，所以pe是Sn中关于

的幺元。－1(4)

任取

p

∈S

，

p

存在逆函数p

∈S

，

p

pi

n

i

i

n

i

i－1i=p

－=pe，所以Sn中每个元素关于

存在逆元。故〈Sn,

〉是一个群。证毕第5章代数结构定义5.5.3给定n个元素组成的集合S，S上的若干置换及其置换的右复合运算

所构成的群称为n次置换群(substitution

group)。特别地，置换群〈Sn，

〉称为n次对称群(symmetric

group)。第5章代数结构定理5.5.4设〈G，*〉为群，那么运算表中的每一行和列表头(或每一列和行表头)都构成集合G的一个置换。证明这里只证〈G，*〉的运算表中的每一行和列表头都构成集合G的一个置换。设G={a1，a2，…，an}，任取元素ai∈G，考察ai对应的行ai*a1，ai*a2，…，ai*an。设aj是G中的任一元素，由于aj=ai*(a

－1*aj)，而a

－1*i

iaj∈G，所以aj必定出现在ai对应的行中。再证在ai对应的行中aj只出现一次，可用反证法。第5章代数结构设在ai对应的行中aj出现两次或更多次，即存在ah，ak∈G，且ah≠ak，使得ai*ah＝ai*ak＝aj，由于〈G，*〉为群，满足可约性，又推出ah=ak，产生矛盾。因而证明了是集合G的一个置换。对列的证明过程与上述证明过程类似。证毕第5章代数结构任意n阶群必同构于一个n次置定理5.5.5(Cayley定理)换群。第5章代数结构5.5.3循环群定义5.5.4给定群〈G，*〉，令Z整数集合，若存在g∈G，对于任何a∈G，存在i∈Z，使得a=gi，则称〈G，*〉是循环群(cyclic

group)，称g是循环群〈G，*〉的生成元(generater)，同时称循环群〈G，*〉是由g生成的，把群〈G，*〉常记为(g)。若生成元g的阶(order)有限，则称〈G，*〉为有限循环群，否则称为无限循环群。例如，

〈Z,

+〉是无限循环群，

0是幺元，

1或－1是生成元(注意生成元不唯一，

10=(－1)0=0)。第5章代数结构定理5.5.6每个循环群都是Abel群。证明设〈G，*〉是一个循环群，a是该群的生成元，

对于任意的x,y∈G

，必有r,s∈Z，使得x=ar，y=as，这样就推出：x*y=ar*as=ar+s

=as+r

=as*ar

=y*x从而得到，运算*可交换，即〈G，*〉是阿贝尔群。证毕第5章代数结构定理5.5.7设〈G，*〉是g生成的有限循环群，如果|G|=n，则G={g1，g2，…，gn－1，gn=e}，且n是使gn=e的最小正整数。其中，e是群〈G，*〉的幺元。证明

首先证明g1，

g2，

…，

gn－1

均不等于e。假设存在某个正整数m,

m＜n，

有gm=e。由于〈G，

*〉是一个循

环群，

所以任取a∈G，

存在k∈Z，

使得gk=a。令k=mq+r,

其中q是某个整数,

0≤r＜m,

则有a=gk=gmq+r=(gm)q*ar

=(e)q*ar

=ar第5章代数结构这表明G中每一个元素都可写成gr(0≤r＜m)的形式，这样G中最多有m个不同的元素，这与|G|=n矛盾。所以，如果m＜n，则gm

≠e，故g1，g2,…,gn－1均不等于e。其次证明g1，g2

,…，gn互不相同。假设存在gi=gj，其中1≤i＜j≤n

，则gj－i=e，而且1≤j－i＜n

，这已证明不可立。由于〈G，*〉是群，且|G|=n，g1，g2

，…，gn

∈G，必有G={g1，g2

，…，gn}，又因为群〈G，*〉有幺元e，推出gn=e。证毕第5章代数结构定理5.5.8循环群〈G，*〉的任何子群都是循环群。证明设循环群〈G，*〉的生成元为g，〈H，*〉是〈G，*〉的任意子群。若〈H，*〉是〈G，*〉的平凡子群，则〈H，*〉显然是循环群。若〈H，*〉是〈G，*〉的非平凡子群。设m是满足gm∈H

的最小正整数。对于任意gp∈H，令p＝qm+r(其中0≤r≤m－1，q＞0)，能够得到gr＝gp－qm＝gp*(gm)－q∈H，因为m是gm∈H的最小正整数，所以r＝0，即gp＝(gm)q。这说明H中任意元素都可由gm生成。所以，〈H，*〉是以gm为生成元的循环群。证毕第5章代数结构定理5.5.9任意k阶有限循环群同构于模k加群。证明设〈G，*〉是g生成的k阶有限循环群，|G|=k，则gk=e，G={g0=e，g=g1，g2，…，gk－1}其中，e是群〈G，*〉的幺元。模k加群为〈Nk，+k

〉，其中Nk={［0］,［1］,…,［k－1］}，［x］+k［y］=［x+y］。第5章代数结构作映射f:

G→Nk，

f(gi)=［i］，

0≤i≤k－1，

显然f是双射的。同时任取x,y∈G，令x=gi，y=gj，有f(x*y)=f(gi*gj)=f(gi+j)=f(g(i+j)

mod

k)=［(i+j)mod

k］=［i］+k［j］=f(gi)+kf(gj)=f(x)+kf(y)所以f是〈G，*〉到〈Nk，+k〉的同构映射。证毕第5章代数结构5.6.1陪集与拉格朗日定理定义5.6.1设〈H，*〉是群〈G，*〉的子群，且a∈G，称集合a*H={a*h|h∈H}为由a确定的H在G中的左陪集(left

coset)，简称左陪集，简记为aH,a称为左陪集aH的代表元素。类似地可定义由a确定的H在G中的右陪集Ha(right

coset)。显然，若〈G，*〉是Abel群，并且〈H，*〉是其子群，则aH=Ha，即任意元素的左陪集等于其右陪集，此时aH=Ha可简称陪集。5.6

陪集与同余关系第5章代数结构定理5.6.1设〈H，*〉是群〈G，*〉的子群，对任意a∈G，则a∈aH。证明因为e∈H，故a=a*e∈aH。证毕第5章代数结构定理5.6.2设〈H，*〉为群〈G，*〉的子群，e为群〈G，*〉的幺元，对于任何a,b∈G，则有：H为〈G，*〉中的左陪集。aH=H当且仅当a∈H。b∈aH当且仅当aH=bH。aH=bH当且仅当b－1*a∈H。或者aH=bH,

或者aH∩bH=

∅。第5章代数结构证明

(1)因为若e是〈G，*〉的幺元，则e*H={e*h|h∈H}=H。(2)必要性。假设aH=H。由于a=a*e∈aH=H，故a∈H。充分性。假设a∈H，

显然a－1∈H，

任取x∈aH，

存在h∈H，使得x=a*h，

由于a∈H且〈H，

*〉为群，

故x∈H，

aH

H。任取x∈⊆H，a*a－1*x∈H，令h1=a－1*x,则h1∈H，又因为x=a*a－1*x=a*h1∈aH，

推出H

aH。从而得到，

aH=H。

⊆因此，

aH=H当且仅当a∈H成立。第5章代数结构(3)必要性。设b∈aH，则存在h1∈H，使得b=a*h1，b－1=h

－1*a－1。1任取x∈bH，存在h∈H，使得x=b*h，则x=b*h=a*h1*h=a*(h1*h)∈aH故bH

⊆aH。任取x∈aH，存在h∈H，使得x=a*h，则x=a*h=(b*b－1)*(a*h)=b*(b－1*a*h)1

1=b*(h

－1*a－1*a*h)=b*(h

－1*h)∈bH故aH

⊆bH。因此，aH=bH。

充分性是显然的。因此，b∈aH当且仅当aH=bH成立。第5章代数结构(4)必要性。假设aH=bH，存在h1，h2∈H，使得a*h1=b*h2,这样就有：1

2

1b－1*a*h1*h

－1=b－1*b*h

*h

－11因此，b－1*a=h2*h

－1∈H。充分性。假设b－1*a∈H。任取x∈aH，存在h∈H，使得x=a*h，则x=a*h=(b*b－1)*(a*h)=b*(b－1*a)*h∈bH故aH

⊆bH。任取x∈bH，存在h∈H，使得x=b*h，则x=b*h=(a*a－1)*(b*h)=a*(a－1*b)*h=a*(b－1*a)－1*h∈aH故bH

⊆aH。所以aH=bH成立。因此，aH=bH当且仅当b－1*a∈H成立。第5章代数结构定理5.6.3若〈H，*〉是群〈G，*〉的子群，则H的每个左陪集与H等势。证明任取左陪集aH，其中a∈G，建立由H到aH的映射如下：f(h)=a*h其中h∈H。f显然是满射，下面证明它是单射。若a*h1=a*h2，h1,h2∈H，则根据群的可约律知h1=h2，即若f(h1)=f(h2)，必有h1=h2。故f是双射的。证毕第5章代数结构定义5.6.2设〈H，*〉是群〈G，*〉的子群，定义G上二元关系R={〈a，b〉|a，b∈G且aH=bH}，称R为〈H，*〉的左陪集关系。第5章代数结构定理5.6.4设〈H，*〉是群〈G，*〉的子群，则〈H，*〉左陪集关系R是一个等价关系，且对于任何a∈G，有［a］R=aH。证明任取a∈G，因为aH=aH，所以〈a，a〉∈R，故R是自反的。任取a，b∈G，且〈a，b〉∈R，则aH=bH，即bH=aH，所以〈b，a〉∈R，故R是对称的。任取a,b,c∈G，且〈a，b〉∈R，〈b，c〉∈R，则aH=bH，bH=cH，即有aH=cH，〈a，c〉∈R，故R是传递的。因此，R是等价关系。对于任何x∈G，

由于x∈［a］R

〈a，

x〉∈R

aH=xH

x∈aH故有［a］R=aH。证毕第5章代数结构定理5.6.5(Lagrange定理)若〈H，*〉是有限群〈G，*〉的子群，且|G|=n，|H|=m，则n=mk，其中k∈Z+，Z+是正整数集合。证明设R为〈H，*〉的左陪集关系，则G关于R的商集G/R={［x］R

|x∈G}，再假设{［x］R

|x∈G}中所有不同的等价类有k个，分别是［a1］R，［a2］R，…,［ak］R，其中a1，a2,…,ak∈G，由于G/R={［x］R

|x∈G}=｛［a1］R，［a2］R，…,［ak］R｝是G的一个划分，这样就得到：n=|G|=|［a1］R∪［a2］R∪…∪［ak］R|=|［a1］R|+|［a2］R|+…+|［ak］R|=|a1H|+|a2H|+…+|akH|=k|H|即n=mk。证毕第5章代数结构推论1任何阶为素数的有限群必不存在非平凡子群。推论2设〈G，*〉是n阶群，对于任何a∈G，若a的阶为r，则r必是n的因子，且有an＝e。证明任取a∈G，且设a的阶为r，即有ar=a0=e，不难证明〈{a0,a1,a2,…,ar－1}，*〉是〈G，*〉的子群，|{a0,a1,a2,…,ar－1}|=r。由拉格朗日定理可知，r是n的因子。令n=mr,其中m、r为正整数，则有an＝arm=(ar)m=em=e。证毕第5章代数结构推论3阶为素数的群〈G，*〉必为循环群，且G中任何非幺元元素均为生成元。证明设〈G，*〉是群，|G|＝p，p是素数，e为幺元。任取a∈G，且a≠e，设a的阶为m，因为m是p的因子且m≠1，所以m=p，G={a1，a2，…，ap=e}，即〈G，*〉是循环群，a是生成元，从而得到：阶为素数的群〈G，*〉必为循环群，且G中任何非幺元元素均为生成元。证毕第5章代数结构*5.6.2正规子群定义5.6.3设〈H，*〉是群〈G，*〉的子群，若对于G中任意元a，有aH=Ha，则称〈H，*〉是群〈G，*〉的

正规子群(normal

subgroup)。由本定义可知，每个Abel群的子群必为正规子群。正规子群〈H，*〉满足aH=Ha并不意味着交换律成立。因为aH=Ha表示对任意的h1∈H，存在h2∈H，使得a*h1=h2*a,并非对任意的h∈H，总有a*h=h*a。第5章代数结构定理5.6.6给定群〈G，*〉的子群〈H，*〉，〈H，*〉是群〈G，

*〉的正规子群当且仅当

a∈G，

h∈H，

均有a*h*a－1∈H。证明必要性。设〈H，

*〉是群〈G，

*〉的正规子群，则

a∈G，

均有aH=Ha，这样对于任何h∈H，

存在h1∈H，

使得a*h=h1*a，于是a*h*a－1=h1∈H。充分性。

a∈G，

h∈H，

均有a*h*a－1∈H。任取x∈aH，

则

h1∈H，

使得x=a*h1，

又有x=a*h1=(a*h1*a－1)*a∈Ha,故aH⊆Ha。同理可证，Ha

⊆aH。因此，Ha=aH，即〈H，*〉是群〈G，*〉的正规子群。证毕第5章代数结构*5.6.3同余关系与商代数定义5.6.4给定代数系统〈