第五章 代数系统

第五章代数系统1第五章代数系统代数通常被认为是符号的操作，其发展分为两个历史阶段。古典代数（19世纪以前）：“每一个符号总是代表一个数”近世代数（19世纪以后）：符号可以代表任何东西，把在任意性质的元素上所进行的代数运算作为研究的基本对象。近世代数发展中的代表人物：挪威数学家阿贝尔（N.H.Abel)、法国数学家伽罗瓦（E.Galois)、英国数学家德·摩根(A.De.Morgan)和布尔(G.Boole).2第五章代数系统由集合上定义若干个运算而组成的系统,通称代数系统.代数系统是近世代数研究的中心问题，是数学中最重要、最基础的分支之一，其理论不仅是许多数学研究的基础，而且在通信理论、系统工程等领域都有着广泛的应用。特别在计算机科学领域，是诸如程序设计、数据结构、形式语言、编码理论、逻辑电路设计等领域必不可少的理论基础。35.1代数系统的引入集合A上的运算一元运算三元二元小于等于x的最大数大于等于x的最小数a的倒数ifx=0thenyelsez4定义1n元运算对于集合A,一个从An到B的映射,称为集合A上的一个n元运算.若B

A则称该n元运算是封闭的.*一元二元五一元桔子水可口可乐二元五可口可乐冰淇淋例<I,+>整数集合上的加法运算封闭<I-{0},+>不封闭(如：-3+3=0)不封闭5定义2代数系统一个非空集合A连同若干个定义在该集合上的运算f1,f2,…,fk所组成的系统称为一个代数系统,记作<A,f1,f2,…,fk>.例6例1时钟代数给定代数系统V=<Im,>，其中Im={1，2，…,m}为一元运算V通常称为时钟代数从1开始,能逐步产生Im中每一个元素,1是生成元。7例2模m同余运算8例3：函数的复合运算9例3：函数的复合运算10115.2运算及其性质12运算的性质设,是定义在集合A上的二元运算,如果对于任意的x,y,z

A,1.若总有x

y

A，则称二元运算在A上是封闭的；2.若总有x

y=y

x，则称是可交换的；3.若总有(x

y)z=x

(y

z)，则称是可结合的；4.若总有x

(y

z)=(x

y)(x

z)

(y

z)x=(y

x)(z

x)

则称运算对是可分配的；13运算的性质5.若总有x

(x

y)=x

x

(x

y)=x

则称运算和运算满足吸收律；6.若总有x

x=x，则称运算是幂等的。14例N,I,Q,R上的普通加法和乘法：幂集P(S)上的∩和∪：命题逻辑中的和：封闭、可交换、可结合、乘法对加法是可分配。封闭、可交换、可结合、互相可分配、满足吸收律和幂等律封闭、可交换、可结合、互相可分配、满足吸收律和幂等律15幺元设是定义在集合A上的二元运算,若有el

A,对于任意的x

A,er

Ax

er=xe

Ae

x=x

e=x都有el

x=x，则称el为A中关于运算的左幺元；右幺元；幺元。16例α为幺元、为左幺元17定理设是定义在集合A上的二元运算,且在A中有关于运算的左幺元el和右幺元er，则el=er=e，且A中的幺元是唯一的。证明el=el

er=er

=e设另有一幺元e1,则e1=e1

e

=e18零元设是定义在集合A上的二元运算,若有

l

A,对于任意的x

A,

r

Ax

r=

r

A

x=x

=都有

l

x=

l，则称el为A中关于运算的左零元；右零元；零元。19定理设是定义在集合A上的二元运算,且在A中有关于运算的左零元

l和右零元

r，则

l=

r=

，且A中的零元是唯一的。证明

l=

l

r=

r

=设另有一零元

1,则

1=

1

=20定理设代数系统<A,>,且|A|>1。如果该代数系统中存在幺元e和零元，则e。证明用反证法。设e=,则对于任意的

x

A,必有x=ex=x==e于是A中只有一个元素，与假设矛盾。21逆元设代数系统<A,>,是定义在A上的二元运算,且e是A中关于运算的幺元。如果对于a

A,

b

A,a

b=e，如果b既是a的左逆元又是a的右逆元，则称b是a的逆元，记为a-1=b.显然a和b互为逆元.使b

a=e，则称b为a左逆元；右逆元；22定理设代数系统<A,>,这里是定义在A上的一个二元运算，A中存在幺元e,且每一个元素都有左逆元。如果是可结合的,则该代数系统中任何一个元素的左逆元必定是该元素的右逆元，且每个元素的逆元是唯一的。1)如果b是a的左逆元，则b是a的右逆元；2)每个元素的逆元唯一，即如果a有两个逆元b和c，

则b=c.证明思路23证明设a,b,c

A,且b是a的左逆元，c是b的左逆元，则b是a的右逆元设元素a有两个逆元b和c，则a的逆元是唯一的24例:求幺元、零元、逆元N,I,Q,R上的普通加法+和乘法*+：幺元0，a-1=-a；*：幺元1，零元0，a-1=1/a；命题公式集合上的和：幺元F，零元T：幺元T，零元F幂集P(S)上的∪和∩∪：幺元，零元S∩：幺元S，零元25例在<Q,>中,Q为有理数集.对所有的a,bQ,ab=a+b-ab试讨论<Q,>的运算性质,有幺元、零元、逆元?解对于所有a,b,cQ,

26例（续）3)幺元e4)零元5)逆元x时27例已知为A上的二元运算,它的幺元也是零元,问A是什么集合?设a

A,且a为A上的幺元和零元，对任意的x

A，有a

x=x

a=x（幺元）a

x=x

a=a（零元）x=a,即A={a},A必为单元素集。解：28例设A上的二元运算满足结合律,且对a,b

A由ab=ba得a=b.试证：对任意的自然数n,有an=a.证明 对n用归纳法当n=1时,a1=a，n=2时,a2=aa因为满足结合律a

(aa)=(aa)a又因ab=ba得a=b，aa=a,即a2=a设n=k时ak=a成立ak+1=aka=aa=a所以对任意的n,有an=a成立。29运算表与运算的性质设代数系统<A,>，运算的性质可以从运算表中看出封闭性：表中的每个元素都属于A;交换性：表关于主对角线对称；幂等性：主对角线上的每一个元素与它所在行（列）的表头元素相同；有零元：该元素所对应的行和列中的元素都与该元素相同；30运算表与运算的性质（续）有幺元：该元素所对应的行和列依次与运算表的行和列相一致；设A中有幺元，a和b互逆，当且仅当位于a所在行，b所在列的元素以及b所在行，a所在列的元素都是幺元。31例判断运算*的性质封闭可交换幺元:aa的逆元是a,b和c互为逆元*abcaabcbbcaccab325.3半群33广群、半群一个代数系统<S,>,其中S是非空集合，是S上的一个二元运算，如果运算是封闭的，则称代数系统<S,>为广群。如果运算是封闭的、可结合的,则称代数系统<S,>为半群。是半群不是半群例34例设集合Sk={x|x

I

x

k},k

0,判断<Sk,+>是否为半群,其中+是普通的加法;如果k0？当k

0时，<Sk,+>是半群。因为+在Sk上是封闭的、可结合的。如果k

0时，<Sk,+>不是半群，如：k

=-3x

-3时（-3）+（-2）=-5S-3，运算不封闭。解35定理设<S,>是一个半群，B

S且在B上是封闭的，那么<B,>也是一个半群。通常称<B,>是半群<S,>的子半群。设<S,>是一个半群，如果S是一个有限集合，则必有aS,

使得aa=a。即S中必有等幂元。因为S是有限集,所以必定存在j

i,使得bi=bj令p=j-i,便有bi=bp

bi证明思路36证明因为<S,>是一个半群,对于任意的bS,

由封闭性可知：b2=bb

S,b3=b2b=bb2

S…因为S是有限集,所以必定存在j

i,使得bi=bj令p=j-i,便有bi=bp

bi,所以对于q

i,有bq=bp

bq因为p

1，所以总可以找到k

1，使得kp

i对于S中的元素bkp，就有所以S中存在元素a=bkp使得aa=a.37独异点（含幺半群）含有幺元的半群称为独异点.（封闭结合幺元）例：幺元为0幺元为1幺元为

幺元为S幺元为恒等函数38定理设<S,>是一个独异点,则在的运算表中任何两行或两列都是不相同的.证明设幺元是e,因为对于任意的a,b

S,且 ab时，总有 e

a=ab=e

b（无两列同） a

e=ab=b

e（无两行同）所以在的运算表中不可能有两行或两列是相同的。eabeeabaabebbea39例已知<Zm,+m>试证明运算+m的运算表中任何两行和两列都不相同,其中Zm={[0],[1],…,[m-1]},mÎI 只要说明<Zm,+m>是独异点即可。 1)封闭：根据定义+m在Zm上是封闭的。 2)可结合：对任意[i],[j],[k]

Zm,([i]+m[j])+m[k]=[i]+m([j]+m[k])=[(i+j+k)(modm)] 3)幺元：[0],因为[0]+m[i]=[i]+m[0]=[i]证明40定理设<S,>是独异点,对于任意a,b

S,且a,b均有逆元，则(a-1)-1=aab有逆元，且(ab)-1=b

-1a

-1证明41例字母表42例字母表在形式语言中,常称非空有限字符集合为字母表。字母表中字符的n重序元为字符串.由m个字符所组成的字符串称为长度为m的字符串。长度为0的字符串称为空串，记为。用表示两个字符串的联结运算。设V*表示字母表V中字符串的集合，V+=V*-{}则<V+,

>是一个半群（封闭，可结合）则<V*,

>是一个独异点（封闭，可结合,幺元为)。43例集合的划分所构成的含幺半群S:非空集合∩(S):S的所有划分的集合P,Q∩(S)P={p1,…,pn}Q={q1,…,qn}P*Q：表示P中每个元素pi与Q中每个元素qj的交的集合（不包含空集），称为划分集运算。<∩(S),*>是含幺半群，幺元是最小划分。如：445.4群与子群45群设<G,>是一代数系统,其中G是非空集合,为G上一个二元运算,若1)是封闭的2)是可结合的3)存在幺元e4)对任一x

G,存在它的逆元x-1则称<G,>是一个群.例<I,+>是群<N,+>,<I,>不是群（无逆）46例设R={0°,60°,120°,180°,240°,300°},表示在平面上几何图形绕形心顺时针旋转角度的六种可能情况。是R上的二元运算，a

b表示平面图形连续旋转a和b得到的总旋转角度。并规定旋转360°等于原来的状态。试验证<R,>是一个群。47解：由题意，运算的运算表如下：060120180240300006012018024030060601201802403000120120180240300060180180240300060120240240300060120240300300060120180240是封闭的，满足结合律，幺元是0，60,120,180的逆元分别是300,240,18048有限群、无限群设<G,>是一个群，如果G是有限集，则称<G,>是有限群，G中元素的个数通常称为该有限群的阶数，记为|G|；如果G是无限集，则称<G,>为无限群。

例上例中|R|=6，是有限群<I,+>是无限群49定理1群<G,>中不可能有零元。证明当群的阶为1时，它的唯一元素视为幺元。当|G|>1且群<G,>中有零元，则对任何xG,都有x=x=e。所以不存在逆元。这与<G,>是群矛盾。50定理2设<G,>是一个群，对于a,b

G，必存在唯一的x

G，使得a

x=b。设a的逆元为a-1证明51定理3（消去律）设<G,>是一个群，对于任意的a,b,c

G，如果有a

b=a

c或者b

a=c

a,则必有b=c。证明设a

b=a

c，且a的逆元是a-1,则有a-1(

a

b)=a-1(

a

c)

e

b=e

c b=c当b

a=c

a时，同理可证b=c。52置换设S是一个非空集合，从集合S到S的一个双射称为S的一个置换。例设<S,>是一个独异点,则在的运算表中任何两行或两列都是不相同的.证明设幺元是e,因为对于任意的a,b

S,且 ab时，总有 e

a=ab=e

b（无两列同） a

e=ab=b

e（无两行同）所以在的运算表中不可能有两行或两列是相同的。eabeeabaabebbea53定理4群<G,>的运算表中的每一行或每一列都是G的元素的一个置换。证明思路：G中元素在任一行（列）中只出现一次;G中的每一个元素都在每一行（列）中出现。1.若对应于aG的那一行中有两个元素都是c,则有

a

b1=a

b2=c且b1

b2,这与定理3(消去律)矛盾。2.考察对应于aG的那一行，设b是G中的任一元素，由于b=a

(a-1b),所以b必定出现在对应于a的那一行中。又因为运算表中没有两行（两列）是相同的，所以定理成立。54定理5在群<A,>中,除幺元e外,不可能有别的等幂元。证明因为e

e=e，所以e是等幂元。设a

A,a

e且a

a=a，则有a=e

a =(a-1

a)

a =a-1

(aa) =a-1

a =e与假设矛盾。55子群与平凡子群子群：设<G,>是一个群,S是G中的非空子集，如果<S,>也构成群，则称<S,>是<G,>的一个子群。平凡子群：设<G,*>是一个群，<S,*>是<G,*>的子群,如果S={e}，或者S=G，则称<S,*>为<G,*>的平凡子群。56定理6设<G,>是一个群,<S,>是<G,>的一个子群，那么<G,>中的幺元e必定也是<S,>中的幺元。证明设<S,>中的幺元是e1,对于任一x

S

G,必有e1

x=x=e

x,所以e1=e。57定理7设<G,>是一个群,B是G的非空子集,如果B是一个有限集,那么只要运算在B上封闭，<B,>必定是<G,>的子群。证明 设b是B的任一元素。若在B上封闭， 则元素b2=b

b,b3=b2

b,…,都在B中。由于B是有限集，所以必存在正整数i和j,j-i>0，使得bi=bj,即bi=bi

bj-i,则bj-i是<G,>中的幺元且在B中。如果j-i>1,则由bj-i=b

bj-i-1可知bj-i-1是b的逆元且在B中。如果j-i=1,则由bi=bi

b可知b是幺元,其逆元是幺元自身。因此<B,>是<G,>的子群。58定理8设<G,>是群，S是G的非空子集，如果对于S中的任何元素a和b有a

b-1

S,则<S,>是<G,>的子群。 1）任取S中的元素a,aSG,所以e=aa-1S,且a

e=ea=a，即e也是S中的幺元；2）对任意的aS,因为eS,所以e

a-1

S,即a-1

S；

3）对于任意的a,b

S,由上可知b-1

S,而b=(b-1)-1,所以a

b=a

(b-1)-1

S；（封闭）4）运算的可结合性是保持的。因此<S,>是<G,>的子群。证明595.5阿贝尔群和循环群60阿贝尔群如果群<G,>中的运算是可交换的，则称该群为阿贝尔群，或称交换群。例设S={a,b,c,d},在S上定义一个双射函数f:f(a)=b,f(b)=c,f(c)=d,f(d)=a,对于xS,构造复合函数构造集合F={f0,f1,f2,f3},则<F,>是阿贝尔群。61解：集合F中运算的运算表如下：从运算表可以看出运算

关于F是封闭的可结合的；幺元：f0逆元：f0、f2是其自身，

f1、f3互为逆元。由运算表的对称性可知运算是可交换的。因此<F,>是阿贝尔群f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f262定理1设<G,>是一个群，<G,>是阿贝尔群的充要条件是对任意的a,b

G,有(ab)(ab)=(aa)(bb)。证明设对任意a,b

G，有充分性结合律结合律已知因此群<G,>是阿贝尔群。63定理1（续）设<G,>是一个群，<G,>是阿贝尔群的充要条件是对任意的a,b

G,有(ab)(ab)=(aa)(bb)。证明必要性设<G,>是阿贝尔群，则对任意a,bG，有ab=ba结合律已知结合律64循环群设<G,>是群，若在G中存在一个元素a，使得G中的任意元素都是由a的幂组成，则称该群为循环群，元素a称为循环群G的生成元。例f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2生成元:f1群<{0,60,120,180,240,300},>的生成元：60ebceebcbbcecceb生成元:b,c65定理2任何一个循环群必定是阿贝尔群。证明设<G,>是循环群，它的生成元是a，则对任意x,yG，必有r,sI，使得因此群<G,>是阿贝尔群。66例已知则<G,·>为群，且为循环群，生成元为1,267定理3设<G,>是一个由元素a

G生成的有限循环群。如果G的阶数是n，即|G|=n，则an=e，且G={a,a2,a3,...,an-1,an=e}其中e是<G,>中的幺元，n是使an=e的最小的正整数(称n为元素a的阶)。证明假设对于某个正整数m，m<n，有am=e。那么，由于<G,>是循环群，所以G中的任何元素都能写为ak(k

I),而且k=mq+r,其中q是某个正整数，0

r<m，这就有ak=amq+r=(am)q

ar=ar这样G中的每一个元素都可以表示成ar,即G中最多有m个元素，与|G|=n矛盾。68定理3(续)证明用反证法证明a,a2,...,an都不相同。假设ai=aj,其中1i<j

n,就有aj-i=e,而且1

j-i<n,这已由上面证明是不可能的。所以a,a2,...,an都不相同。设<G,>是一个由元素a

G生成的有限循环群。如果G的阶数是n，即|G|=n，则an=e，且G={a,a2,a3,...,an-1,an=e}其中e是<G,>中的幺元，n是使an=e的最小的正整数(称n为元素a的阶)。69例循环群生成元a,b循环群生成元a,cKlein四元群任何一个四阶群只可能是四阶循环群或Klein四元群70例715.7陪集与拉格朗日定理72积和逆设<G,*>是一个群，A,BP(G)且A

,B

,记A,B的积：AB={a*b|aA,bB}A的逆：A-1={a-1|aA}73例<Z4,+4>74陪集设<H,*>是群<G,*>的一个子群，aG,则集合{a}H(H{a})称为由a所确定的H在G中的左陪集（右陪集），简称为H关于a的左陪集（右陪集），记为aH(Ha)。元素a称为陪集aH(Ha)的代表元素。75例76例（续）77例78拉格朗日定理设<H,*>是群<G,*>的一个子群，那么a)R={<a,b>|aG,bG,且a-1*bH}是G中的一个等价关系。对于aG,若记[a]R={x|xG且<a,x>R}则[a]R=aHb)如果G是有限群，|G|=n,|H|=m,则m|n证明略。79推论1任何质数阶的群不可能有非平凡子群。（S={e},或者S=G,<S,*>为<G,*>的平凡子群）证明反证法。如果有非平凡子群，那么该子群的阶必定是原来群的阶的一个因子，与原来群的阶是质数矛盾。80推论2设<G,*>是n阶有限群，那么对于任意的aG，a的阶必是n的因子且必有an=e,这里e是群<G,*>中的幺元。如果n为质数，则<G,*>必是循环群。证明设<H,*>是由a生成的m阶循环子群，则am=e,再由拉格朗日定理必有n=km，故an=(am)k=ek=e.因为质数阶群只有平凡子群，所以质数阶群必定是循环群。81例Klein四元群由运算表可知，*是封闭的、可结合的。幺元：e每个元素的逆元是其自身所以<K,*>是群因为a,b,c都是二阶元，<K,*>不是循环群设K={e,a,b,c},运算*的运算表如下82例试证任何一个四阶群只可能是四阶循环群或者Klein四元群。证明设四阶群为<{e,a,b,c},*>。其中e是幺元。当四阶群含有一个四阶元素时，这个群就是循环群。当四阶群不含有四阶元素时，则由推论2可知，除幺元e外，a,b,c的阶一定都是2。a*b不可能等于a,b,e,否则将导致b=e,a=e或a=b的矛盾，所以a*b=c。同样可以证明b*a=c,a*c=c*a=b,b*c=c*b=a,因此这个群是Klein四元群。835.8同态与同构84同态映射设<A,>和<B,*>是两个代数系统，和*分别是A和B上的二元(n元)运算，设f是从A到B的一个映射，使得a1,a2A，有f(a1

a2)=f(a1)*f(a2)则称f为由<A,>到<B,*>的一个同态映射，称<A,>同态于<B,*>，记作A~B。把<f(A),*>称为<A,>的一个同态象。其中f(A)={x|x=f(a),aA}

B8586例<I,>,<B,>,B={正，负，零}代数系统<B,>描述了<I,>中运算结果的正、负、零特征。87同态的类型设f是由<A,>到<B,*>的一个同态，如果f是从A到B的一个满射,则f称为满同态；f是从A到B的一个入射,则f称为单同态；f是从A到B的一个双射,则f称为同构映射，并称<A,>和<B,*>是同构的，记作A

≌

B.88例89例90例下面几个代数系统同构91例试证<A,>和<B,*>是同构的A={a,b,c,d}B={,,,}同构映射可以不唯一92例求<N4,+4>,<N5*,5>的同构g是<N4,+4>,<N5*,5>的同构93例试证每个n阶循环群，都同构于群<Nn,+n><G,*>为由a

G生成的N阶循环群。G={a,a2,…,an=e}定义映射g:g(1)=a,g(2)=a2,…g(0)=eg为<Nn,+n>到<G,*>的同构。证明94自同态、自同构设<A,>是一个代数系统，如果f是从<A,>到<A,>

的同态，则称f自同态。如果g是由<A,>到<A,>的同构，则称g为自同构。设G是代数系统的集合，则G中代数系统之间的同构关系是等价关系。定理95定理设f是从代数系统<A,>到<B,*>的同态映射，则：如果<A,>是半群，则<f(A),*>也是半群；如果<A,>是独异点，则<f(A),*>也是独异点；如果<A,>是群，则<f(A),*>也是群。一些重要性质在同态象中，特别在同构像中都能够保存下来.96同态映射的核设f是由群<G,>到群<G’,*>的同态映射，e’是G’中的幺元，记Ker(f)={x|xG且f(x)=e’}称Ker(f)为同态映射f的核,简称f的同态核。97定理设f是由群<G,>到群<G’,*>的同态映射，则f的同态核K是G的子群。证明98同余关系设<A,