第8章-群和半群

第8章半群和群8.1半群和独异点半群和独异点的定义子半群和子独异点半群同态和独异点同态代数系统A=＜S，*＞，若*是满足结合律的二元运算，则A称为半群。若*同时满足交换律，则称为阿贝尔半群。存在幺元的半群称为独异点，也称(含)幺半群，单位半群。若*同时满足交换律，则称为阿贝尔独异点。8.1.1半群和独异点的定义例∑+,·是最典型的半群，只满足结合律∑*,·,ε是最典型的独异点，只满足结合律，有幺元N,+,0是独异点，可交换独异点SS,◦,1S是独异点，不满足交换律，部分元素有逆元*abaabbabb)设S={a，b}，*定义如右表：即a，b都是右零元∵x,y,zS①x*yS∴运算封闭②x*（y*z）=x*z=z（x*y）*z=z∴结合律成立∴〈S，*〉是一半群，该半群称为二元素右零半群半群的性质:1.独异点运算表中任何两行或两列均不相同证明：设独异点S,*的幺元为e，a,bS，若ab∵a*eb*e,＜S,*＞运算表中a,b两行不同，由a,b任意性，运算表中任两行不同∵e*ae*b,＜S,*＞运算表中a,b两列不同，由a,b任意性，运算表中任两列不同．2.有限半群一定含有幂等元证明：设〈S，＊〉是半群,S是有限集，需证aS，有a＊a=abS，因为运算封闭，b2=b＊bS,b3,b4…SS有限i，j∈N+，ji有bi=bjbi=bj=bj-i＊bi令p=j－ibi=bj=bp*bi当q≥i,bq=bp·bq(1)又∵p≥1∴k∈N+有kp≥i由(1)bkp=bp＊bkp=bp＊(bp＊bkp)=bp＊(bp＊(bp＊bkp))=...=bp＊…bp＊bkp=bkp＊bkp∴令a=bkpS则a＊a=a∴a是幂等元.k个8.1.2子半群和子独异点设S,*为半群，T为S的非空子集。若T关于*封闭，则称T,*是S,*的子半群，记为T≤S。设S,*,e为独异点，T为S的非空子集。若T关于*封闭，且e∈T,则称T,*,e是S,*,e的子独异点，记为T≤S。例半群I,·有子半群Ev,·，Od,·独异点I,·,1有子独异点Od,·,1独异点∑*,·,ε,设A⊆∑，则A*,·,ε是∑*,·,ε的子独异点；独异点∑*,·,ε，设T={s|||s||10},T,·是∑*,·,ε的子半群，但不是子独异点；独异点N,+,0，设nN={nm|mN},nN,+,0是N,+,0的子独异点；独异点SS,◦,1S，其中S上的单射集合，满射集合和双射集合都是SS,◦,1S的子独异点。定理设S,*,e为可交换独异点，T为S中所有幂等元的集合，则T,*,e是S,*,e的子独异点。证：(1)T对于*的封闭性∀a,b∈T,a*a=a,b*b=b,又由于*是可交换、可结合的，所以(a*b)*(a*b)=a*(b*a)*b=a*a*b*b=a*b∴(a*b)也是幂等元，a*b∈T.(2)e∈T.∵e*e∈T,∴e∈T.所以T,*,e是S,*,e的子独异点。8.1.3半群同态和独异点同态定义设S1,*和S2,•是半群，函数h:S1→S2.若∀a,b∈S1,有h(a*b)=h(a)•h(b),则称h为从S1,*到S2,•的半群同态。设M1,*,e1和M2,•,e2是独异点，函数h:M1→M2.若∀a,b∈M1,有h(a*b)=h(a)•h(b),且h(e1)=e2,则称h为从M1,*,e1到M2,•,e2的独异点同态。例8.1.4设∑={a,b},∑*,·,ε上的函数h:∑*→∑*定义如下：i)h(ε)=ε;ii)h(a·s)=ab·h(s),h(b·s)=ba·h(s)则h是∑*,·,ε上的自同态。证：对s用归纳法证明∀s,t∈∑*:h(s·t)=h(s)·h(t)i)s=ε时,h(ε·t)=h(t)=ε·h(t)=h(ε)·h(t),ii)假设s=x时成立，即h(x·t)=h(x)·h(t)则当s’=a·x时，h(s’·t)=h(a·x·t)=ab·h(x·t)=ab·h(x)·h(t)=h(a·x)·h(t)=h(s’)·h(t)当s’=b·x时同理可证。∴∀s,t∈∑*:h(s·t)=h(s)·h(t)又h(ε)=ε，所以h是∑*上的自同态。定理半群S,*与SS,◦同态证：定义h:S→SS为：∀a∈S,h(a)=fa,其中fa:S→S,∀x∈S,fa(x)=a*x,则h是同态映射，因为：∀a,b∈S,∀c∈Sh(a*b)(c)=fa*b(c)=(a*b)*c=a*b*c(h(a)◦h(b))(c)=(fa◦fb)(c)=fa(fb(c))=a*(b*c)=a*b*c所以h(a*b)(c)=(h(a)◦h(b))(c)，即h(a*b)=h(a)◦h(b).所以h是同态映射，半群S,*与SS,◦同态。例8.1.5定理（独异点表示定理）任意独异点都同构于某一变换独异点设S为集合，SS,◦,1S的子独异点称为变换独异点。任意独异点都同构于某一变换独异点。证：设S,*,e是任一独异点。(1)作h:S→SS,afa,则由定理8.1.2知，h是半群同态。又因为h(e)=fe=1S,所以h是从S,*,e到SS,◦,1S的独异点同态。(2)(同构)i)h是单射.a,b∈S,若h(a)=h(b)，即fa=fb,则fa(e)=fb(e),a*e=b*e,即a=b.ii)h不一定是满射，其值域h(S)⊆SS但，由定理7.2.3，h(S),◦是SS,◦的子代数。（h(S)对合成运算◦封闭）又∵1S=h(e)∈h(S),∴h(S),◦,1S是SS,◦,1S的子独异点。h:S→SS，限制在h(S)上为满射。所以，S,*,e同构于h(S),◦,1S。8.2群的定义及性质群的定义群的判定群的性质元素的阶8.2.1群的定义代数系统〈G，*〉，其中二元运算*满足下列性质：1)结合律，即a,b,cG，a*（b*c）=（a*b）*c2)存在幺元e，即aG，e*a=a*e=a3)G中每个元素存在逆元即aG，a-1G,使a*a-1=a-1*a=e则〈G，*〉称为群。若G是有限集，称〈G，*〉为有限群，｜G｜称为群的阶；若G是无限集，称〈G，*〉为无限群。有限群阿贝尔群若*满足交换律，称〈G，*〉为阿贝尔群，或可交换群或加法群。此时，‘*’符号可用‘+’代替；a-1可写为-a；a的n次幂an可写为na;幺元e可写为0N,+,0不是群，除0以外的元素无逆元I,+,0是阿贝尔群I,*,1不是群，0没有逆元Q,*,1不是群，0没有逆元Q+,*,1是阿贝尔群Nk,+k,0是阿贝尔群，Nk,xk,1不是群，0没有逆元•设B(X,X)是集合X上的双射函数集合，则B(X,X),◦,1X是一个群，但不是阿贝尔群•{M|M∈Mn∧detM≠0},∙,1n对行列式非零的n阶方阵M，存在M-1,M∙M-1=M-1∙M=1nN4={0,1,2,3},模4加法+4的运算表如下：+4N4,+4,0是阿贝尔群Nk,+k,0是阿贝尔群m+kn=m+nmodk-m=k-m；m+k(k-m)=(m+k-m)modk=0计算机中的整数实际上就是Nk;-m的补码是k-m，这样：n-232m=(n-m)mod232=(n+(232-m))mod232=n+232(232-m)8.2.2群的判定定理1设G,*为半群，若(1)有左单位元，即el∈G,a∈G,el*a=a;(2)每个元素有左逆元，即a∈G,al∈G,al*a=el,则G,*是群。证：i)先证a∈G,a*al=el.∵al∈G,∴a’∈G,a’*al=el.则a*al=el*(a*al)=(a’*al)*(a*al)=a’*(al*a)*al=a’*el*al=a’*al=elii)再证el也是右单位元a∈G,a*el=a*(al*a)=(a*al)*a=el*a=a所以el是单位元；a∈G，al是a的逆元。所以G,*是群。定理2设G,*是半群，若a,b∈G，方程a*x=b,y*a=b在G中都有解，则G,*是群。证：（利用定理1）i)取a∈G，设el为y*a=a的一个解，el*a=a;b∈G,设c为a*x=b的一个解，a*c=b,则，el*b=el*(a*c)=(el*a)*c=a*c=b,所以，el是左单位元。ii)a∈G,令al为y*a=el的一个解，则al*a=el，则al是a的左逆元。由定理1,G,*是群。定理3设G,*是有限半群，若G中消去律成立，则G,*是群。证：设G={a1,a2,...,an}.i)先证a,b∈G，a*x=b在G中有解。作G’={a*a1,a*a2,...,a*an},则G’⊆Gi,j,若ai≠aj，则a*ai≠a*aj(消去律的逆否)，则|G’|=n,所以G’=G,因为b∈G,故b∈G’即存在k∈N,1=k=n，使得a*ak=b,所以方程a*x=b在G中有解。ii)同理可证方程y*a=b在G中有解.由定理2，G,*是群。有关半群和独异点的性质在群中全部成立阿贝尔群半群独异点群8.2.3群的性质若群〈G，*〉的幺元为e,a，bG，则a)（a-1）-1=a；b)（a*b）-1=b-1*a-1证明：a)∵a*a-1=e∴a是a-1的左逆元a-1*a=e∴a是a-1的右逆元∴(a-1)-1=ab)∵(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e∴b-1*a-1是a*b的右逆元又∵(b-1*a-1)*(a*b)=b-1*(a-1*a)*b＝e∴b-1*a-1是a*b的左逆元∴(a*b)-1=b-1*a-1若〈G，*〉是一个群，则a，bGa）存在唯一的x，使得a*x=bb）存在唯一的y，使得y*a=b证：a）存在性:令x=a-1*b，则a*(a-1*b)=a*a-1*b=e*b=b唯一性:若a*x=b，则a-1*a*x=a-1*b∴x=a-1*bb）同理可证。幺元是群中唯一的幂等元证：若x是幂等元，则：x=e*x=（x-1*x）*x=x-1*（x*x）=x-1*x=e群中消去律成立证：群中每个元素都可逆，则每个元素都可约，所以消去律成立。群中不可能有零元.证：若|G|=1，它的唯一元素视为幺元若|G|1，且G，*有零元，则xG，都有x*=*x=e无逆元，这与G是群矛盾.群〈G，*〉的运算表中的每一行(列)是G中元素的一个置换。(定义：有限集合S到S的一个双射，称为S的一个置换.)证：i)先证一个元素在运算表中每一行(列)中不能出现两次(单射)∵若a*b1=a*b2=k，且b1b2，与可约性矛盾ii)再证G中任一元素在任一行（列）中均出现（满射）∵考察对应于a的那一行，bG，则b=a*（a-1*b）∴b出现在a那一行.由a,b任意性,得证．iii)因〈G，*〉中有幺元，∴任两行（列）均不相同（即各个置换均不相同）证毕。有限群举例①一阶群仅有1个②二阶群仅有1个③三阶群仅有1个④四阶群仅有2个*eee*eaeeaaae*eabeeabaabebbea*eabceeabcaabcebbceacceab*eabceeabcaaecbbbceaccbae例设〈G，*〉是一个群，则〈G，*〉是阿贝尔群的充要条件是:a，bG，有(a*b)*(a*b)=(a*a)*(b*b)证：充分性：若a，bG，因为满足(a*b)*(a*b)=(a*a)*(b*b)所以，a-1*(a*b)*(a*b)*b-1=a-1*(a*a)*(b*b)*b-1∴b*a=a*b∴〈G，*〉是阿贝尔群必要性：若〈G，*〉是阿贝尔群，则a，bG，a*b=b*a∴a*（a*b）*b=a*（b*a）*a∴（a*a）*（b*b）=（a