《杭州师范大学《离散数学》课件-第6章 几个典型的代数系统》由会员分享，可在线阅读，更多相关《杭州师范大学《离散数学》课件-第6章 几个典型的代数系统（145页珍藏版）》请在金锄头文库上搜索。
1、第第6章章 几个典型的代数系统几个典型的代数系统 第第6章章 几个典型的代数系统几个典型的代数系统 6.1 半群与群半群与群 6.2 子群子群 6.3 循环群和置换群循环群和置换群 6.4 陪集与拉格朗日定理陪集与拉格朗日定理 6.5 正规子群、商群和同态基本定理正规子群、商群和同态基本定理 6.6 环和域环和域 6.7 例题选解例题选解 习习 题题 六六杭州师范大学离散数学第第6章章 几个典型的代数系统几个典型的代数系统 6.1 半群与群半群与群 半群与群都是具有一个二元运算的代数系统，群是半群的特殊例子。事实上，群是历史上最早研究的代数系统，它比半群复杂一些，而半群概念是在群的理论发展之后
2、才引进的。逻辑关系见图6.1.1。第第6章章 几个典型的代数系统几个典型的代数系统 图6.1.1群半群第第6章章 几个典型的代数系统几个典型的代数系统 定义6.1.1设S，*是代数系统，*是二元运算，如果*运算满足结合律，则称它为半群（semigroups）。换言之，x,y,zS,若*是S上的封闭运算且满足(x*y）*z=x*（y*z），则S，*是半群。许多代数系统都是半群。例如，N,+，Z,P(S),SS,（SS=f|f:SS,是复合运算）均是半群。但Z,-不是半群。第第6章章 几个典型的代数系统几个典型的代数系统 再如，设是有限字母表，+是中的字母串*=+，其中是不含字母的空串，运算是字母
3、串的“连接”运算，则*,是半群。如Com*,puter*,经运算后，得Computer仍是字母串。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.1】,则S,是半群。这里代表普通的矩阵乘法运算。证明对任意的因为且a1a20,所以,因此运算封闭。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.2】,则S,+不是半群。这里+代表普通的矩阵加法运算。证明对任意的取a2=-a1,则且a1+a2=0，所以因此*运算不封闭。所以S,+不是半群。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.3】,则S,不是半群。这里代表普通的矩阵乘法运算。证明取则所以,因此*运算
4、不封闭。所以S,不是半群。第第6章章 几个典型的代数系统几个典型的代数系统 对于半群中的元素，我们有一种简便的记法。设半群S,*中元素a（简记为aS）的n次幂记为an，递归定义如下：a1=a an+1=an*a1n Z+即半群中的元素有时可用某些元素的幂表示出来。因为半群满足结合律，所以可用数学归纳法证明 am*an=amn，(am)n=amn。普通乘法的幂、关系的幂、矩阵乘法的幂等具体的代数系统都满足这个幂运算规则。如果有a2=a，则称a为半群中的幂等元。第第6章章 几个典型的代数系统几个典型的代数系统 定定理理6.1.1若S,*是半群，S是有限集合，则S中必含有幂等元。证明因为S,*是半群
5、，aS,有a2,a3,S。因为S是有限集合，所以必定存在ji,使得ai=aj。令p=j-i,便有ai=aj=ap*ai，所以aq=ap*aq(qi)。因为p1,所以可找到k1,使得kpiakp=ap*akp=ap*(ap*akp)=a2p*akp=a2p*(ap*akp)=akp*akp即在S中存在元素b=akp,使得b*b=b。第第6章章 几个典型的代数系统几个典型的代数系统 下面介绍一些特殊半群。定义6.1.2如果半群S,*中二元运算*是可交换的，则称S,*是可交换半群(commutativesemigroups)。如Z,+,Z,P(S),均是可交换半群。但SS,*,不是可交换半群。定义6
6、.1.3含有关于*运算的幺元的半群S，*，称它为独异点（monoid），或含幺半群，常记为S,*,e(e是幺元)。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.4】Z,+是独异点，幺元是0，Z,+,0;Z,是独异点，幺元是1，Z,1；P(S),是独异点，幺元是，P(S),；*,是独异点，幺元是(空串)，*,；SS,是独异点，幺元是IA，SS,IA；但ZE,不是独异点，因为无幺元，（1ZE，ZE：偶数集）。第第6章章 几个典型的代数系统几个典型的代数系统 定义6.1.4(1)设S，*为一半群,若TS,*在T中封闭，则T，*称为子半群。（2）设S，*为一独异点,若TS,*在T中封闭
7、，且幺元eT,则T，*,e称为子独异点。我们前面提过，对于有穷集合的二元运算，可用运算表来给出。第第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.2一个有限独异点，S,*,e的运算表中不会有任何两行或两列元素相同。证明设S中关于运算*的幺元是e。因为对于任意的a，bS且ab时，总有 e*a=ab=e*b和a*e=ab=b*e。所以，在*的运算表中不可能有两行或两列是相同的。该定理容易理解，因为幺元所在的行、列均与表头相同，所以不会出现两行（列）元素完全相同的情况。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.5】S=a,b,c,*运算的定义如表6.1.1所示，判断S
8、,*的代数结构？解（1）*是S上的二元运算，因为*运算关于S集合封闭。（2）从运算表中可看出a,b,c均为左幺元（3）x,y,zS,有x*(y*z)=x*z=z(x*y)*z=x*z=z第第6章章 几个典型的代数系统几个典型的代数系统 表6.1.1第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.6】Z4,+4,Z4=0，1，2，3=Z/R(R是Z上的模4同余关系)，Z4上运算+4，定义为m，nZ4，m+4n=(m+n)(mod4)，它由表6.1.2给出。判断Z4,+4的代数结构。第第6章章 几个典型的代数系统几个典型的代数系统 解（1）+4运算显然封闭。（2）由+4的定义可知+4
9、可结合。（3）从运算表中可知0是幺元，所以Z4,+4是独异点。但在该表中没有任意两行（列）元素完全相同。半群及独异点的下列性质是明显的。第第6章章 几个典型的代数系统几个典型的代数系统 表6.1.2第第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.3设S，*,T，。是半群,f为S到T的同态,这时称f为半群同态。对半群同态有（1）同态象f(S)，为一半群。（2）当S，*为独异点时，则f(S)，。为一独异点。利用上一章的知识立刻可以得到这些结论。独异点中含有幺元。前面曾提到，对于含有幺元的运算可考虑元素的逆元，并不是每个元素均有逆元的，这一点引出了一个特殊的独异点群。第第6章章 几个典
10、型的代数系统几个典型的代数系统 定义6.1.5如果代数系统G，*满足（1）G，*为一半群；（2）G，*中有幺元e；（3）G，*中每一元素xG都有逆元x-1，则称代数系统G，*为群（groups）。或者说，群是每个元素都可逆的独异点。群的基集常用字母G表示，因而字母G也常用于表示群。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.7】（1）Z,+（整数集与数加运算）为一群（加群）,数0为其幺元。Z,不是群。因为除幺元1外所有整数都没有逆元。（2）N4,4为一4阶群,数0为其么元。（3）A,P(A),是半群，幺元为，非空集合无逆元，所以不是群。(4)A,P(A),是半群，幺元为A，非
11、空集合无逆元，所以不是群。第第6章章 几个典型的代数系统几个典型的代数系统 (5)A,P(A),的幺元为，SP(A),S的逆元是S，所以是群。(6)Q+,（正有理数与数乘）为一群，1为其么元。Q,不是群，因为数0无逆元。因为零元无逆元，所以含有零元的代数系统就不会是群。第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.8】设g=a,b,c,d,*为G上的二元运算，它由表6.1.3给出,不难证明G是一个群。且e是G中的幺元；G中任何元素的逆元就是它自己，在a,b,c三个元素中，任何两个元素运算的结果都等于另一个元素，这个群称为klein四元群。第第6章章 几个典型的代数系统几个典型的
12、代数系统 表6.1.3第第6章章 几个典型的代数系统几个典型的代数系统 【例6.1.9】设G,*是一个独异点,并且每个元素都有右逆元,证明G,*为群。证明设e是G,*中的幺元。每个元素都有右逆元，即xG，yG使得x*y=e，而对于此y，又zG使得y*z=e。由于xG均有x*e=e*x=e，因此z=e*z=x*y*z=x*e=x即 x*y=e=y*z=y*x=e第第6章章 几个典型的代数系统几个典型的代数系统 y既是x的右逆元，又是x的左逆元，故xG均有逆元，G,*为群。对群G，*的任意元素a,我们可以同半群一样来定义它的幂：a0=e，对任何正整数n，an+1=an*a，群的幂运算有下列性质：第
13、第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.4对群G，*的任意元素a,b，有（1）(a-1)-1a（2）(a*b)-1b-1*a-1（3）(an)-1=(a-1)n（记为a-n）（n为整数）第第6章章 几个典型的代数系统几个典型的代数系统 证明（1）因为a-1的逆元是a，即a*a-1=a-1*a=e，所以(a-1)-1a。（2）因为(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=e(b-1*a-1)*(a*b)=b-1*(a-1*a)*b=e所以a*b的逆元为b-1*a-1，即(a*b)-1b-1*a-1。第第6章章 几个典型的代数系统几个典型的代数系统 （3）对n
14、进行归纳。群首先是独异点，所以a n+1=an*a。n=1时命题显然真。设n=k时(a-1)k是ak的逆元为真,即(ak)-1=(a-1)k，那么ak+1*(a-1)k+1=ak*(a*a-1)*(a-1)k ak*(a-1)k=e(a-1)k+1*ak+1=(a-1)k*(a-1*a)*ak(a-1)k*ak=e故ak+1的逆元为(a-1)k+1，即(ak+1)-1=(a-1)k+1。归纳完成,得证。第第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.5对群G，*的任意元素a,b，及任何整数m，n,有（1）am*an=am+n（2）(am）n=amn证明留给读者。群的下列性质是明显
15、的。第第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.6设G，*为群，则（1）G有唯一的幺元，G的每个元素恰有一个逆元。（2）方程a*xb，y*ab都有解且有唯一解。（3）当Ge时,G无零元。第第6章章 几个典型的代数系统几个典型的代数系统 （1）结论是十分明显的。(2)先证a-1*b是方程a*xb的解。将a-1*b代入方程左边的x，得 a*(a-1*b)=(a*a-1)*b=e*b=b所以a-1*b是该方程的解。下面证明唯一性。假设c是方程a*xb的解，必有a*c=b,从而有c=e*c=(a-1*a)*c=a-1*(a*c)=a-1*b唯一性得证。同理可证b-1*a是方程y*ab
16、的唯一解。（3）若G有零元,那么由定理5.1.5知它没有逆元，与G为群矛盾。（注意，G=e时,e既是幺元，又是零元。）第第6章章 几个典型的代数系统几个典型的代数系统 定理6.1.7设G，*为群，则G的所有元素都是可约的。因此，群中适合消去律，即对任意a,x,ySa*x=a*y 蕴涵x=yx*a=y*a 蕴涵x=y第第6章章 几个典型的代数系统几个典型的代数系统 定义6.1.6设G为有限集合时，称G为有限群（finitegroup）,此时G的元素个数也称G的阶数（order）；否则，称G为无限群（infinitegroup）。由定理6.1.7可知，特别地，当G为有限群时，*运算的运算表的每一行（列）都是G中元素的一个全排列。对于有限群，运算可用表给出,称为群表。从而有限群G，*的运算表中没有一行（列）上有两个元素是相同的。因此，当G分别为1，2，3阶群时,*运算都只有一个定义方式(即不计元素记号的不同,只有一张定义*运算的运算表,分别如表6.1.4、6.1.5和6.1.6所示),于是可以说,1,2,3阶的群都只有一个。第第6章章 几个典型的代数系统几个典型的代数系统 表6.1.4*ee
