第5章群、環(huán)和域
　　接下來的兩章將介紹常見的幾種代數(shù)結(jié)構(gòu)，它們是用代數(shù)方法建立的數(shù)學模型.本章著重討論具有一個二元運算的代數(shù)系統(tǒng)，包括半群、獨異點和群以及具有兩個二元運算的代數(shù)系統(tǒng)，包括環(huán)和域.群、環(huán)和域在組合計數(shù)、編碼理論、形式語言與自動機理論等學科中都發(fā)揮了重要作用，而群是抽象代數(shù)中最古老且發(fā)展得最完善的代數(shù)系統(tǒng).在計算機科學中，對于代碼的查錯和糾錯、自動機理論等各個方面的應(yīng)用的研究，群是其基礎(chǔ).
　　本章的主要內(nèi)容為半群、獨異點和群的定義和基本性質(zhì)，子群及其陪集，環(huán)和域的定義和基本性質(zhì)等.
　　5.1半群和獨異點〖*4/5〗5.1.1半群和獨異點的基本概念定義5.1設(shè)S是一個非空集合，�呈荢上的一個二元運算，如果運算�呈强山Y(jié)合的，則稱代數(shù)系統(tǒng)是半群.
　　若在半群中，運算�碀M足交換律，則稱為交換半群.
　　例如，(1)代數(shù)系統(tǒng)和、和、和都是半群，且都是交換半群.但和不是半群，因為運算不滿足結(jié)合律.
　　(2)代數(shù)系統(tǒng)，都是半群，是交換半群,不是交換半群.
　　(3)代數(shù)系統(tǒng)<2U；∪>和<2U；∩>都是半群，且都是交換半群.
　　(4)設(shè)S={R|R是集合A上的關(guān)系}，則對于關(guān)系的復合運算��，代數(shù)系統(tǒng)是半群，但不是交換半群.
　　若F={f|f是A上的函數(shù)}，則對于函數(shù)的復合運算��，代數(shù)系統(tǒng)也是半群，但不是交換半群.
　　【例5.1】設(shè)S是非空集合，對任意的x，y∈S，定義x�硑=y，則代數(shù)系統(tǒng)是半群，但不是交換半群.
　　【例5.2】設(shè)代數(shù)系統(tǒng)是半群，a∈S，如果對任意的x，y∈S，每當a�硏=a�硑都有x=y，則稱元素a是左可約的.試證明，如果a，b是左可約的，則a�砨也是左可約的.
　　證明對任意的x，y∈S，假設(shè)有(a�砨)�硏=(a�砨)�硑.
　　因為是半群，所以�呈强山Y(jié)合的，有(a�砨)�硏=a��(b�硏)，(a�砨)�硑=a��(b�硑)則由假設(shè)有a��(b�硏)=a��(b�硑)因為a是左可約的，所以b�硏=b�硑.
　　又因為b是左可約的，所以x=y.
　　即對任意的x，y∈S，如果(a�砨)�硏=(a�砨)�硑，則有x=y.所以由左可約的定義可知，a�砨也是左可約的.
　　因為半群中運算�呈强山Y(jié)合的，所以可以定義元素的冪.
　　定義5.2設(shè)是一個半群，則對任意的x∈S和任意正整數(shù)n，定義x的n次冪為x1=x，xn+1=xn�硏（n∈Z+）（5.1）并稱n為x的指數(shù).
　　對任意的正整數(shù)m，n和任意的x∈S，有xm�硏n=xm+n，(xm)n=xmn（5.2）定理5.1設(shè)是一個有限的半群，則必有a∈S，使得a是一個冪等元.
　　證明對任意的x∈S，因為是半群，故由運算�车姆忾]性和結(jié)合律知，x2=x�硏∈S，x3=x2�硏=x�硏2∈S，…因為S是有限集，所以根據(jù)鴿籠原理知，必存在正整數(shù)j>i，使得xi=xj.
　　令p=j-i，便有xi（=xj=xp+i）=xp�硏i.
　　由此可得xq=xp�硏q（正整數(shù)q≥i）.
　　因為p≥1，所以總可以找到正整數(shù)k≥1，使得kp≥i.
　　對于S中的元素xkp，就有xkp=xp�硏kp
　　=xp��(xp�硏kp)
　　=x2p�硏kp
　　=…
　　=xkp�硏kp.此即證得，在S中存在元素a=xkp，使得a�砤=a.■
　　定義5.3若半群中的運算�秤袉挝辉�，則稱該半群為含幺半群，常稱為獨異點.
　　若獨異點中的運算�碀M足交換律，則稱該獨異點為交換獨異點.
　　例如，(1)代數(shù)系統(tǒng)和、和、和都是獨異點，且都是交換獨異點.但和不是獨異點.
　　(2)代數(shù)系統(tǒng)，都是獨異點，是交換獨異點，不是交換獨異點.
　　(3)代數(shù)系統(tǒng)<2U；∪>和<2U；∩>都是獨異點，且都是交換獨異點.
　　(4)設(shè)S={R|R是集合A上的關(guān)系}，則對于關(guān)系的復合運算��，代數(shù)系統(tǒng)是獨異點，但不是交換獨異點.
　　若F={f|f是A上的函數(shù)}，則對于函數(shù)的復合運算��，代數(shù)系統(tǒng)也是獨異點，但不是交換獨異點.
　　注意:
　　(1)獨異點中唯一的單位元常記為e.
　　(2)設(shè)為獨異點，則關(guān)于運算�车倪\算表中沒有兩行或兩列是相同的.
　　事實上，對任意的x，y∈S，當x≠y時，總有x�砮=x≠y=y�砮和e�硏=x≠y=e�硑，所以在�车倪\算表中不可能有兩行或兩列是相同的.
　　在獨異點中也可定義元素的冪.
　　定義5.4設(shè)是一個獨異點，則對任意的x∈S和任意非負整數(shù)n，定義x的n次冪為x0=e，xn+1=xn�硏（n∈N）（5.3）并稱n為x的指數(shù).
　　對任意的非負整數(shù)m，n和任意的x∈S，有xm�硏n=xm+n，(xm)n=xmn（5.4）定義5.5在獨異點中，如果存在元素g∈S，使得S中的每一元素a都能寫成gi（i∈N）的形式，則稱獨異點為循環(huán)獨異點，元素g稱為該循環(huán)獨異點的生成元.
　　【例5.3】試證是循環(huán)獨異點，并求其生成元.
　　證明是獨異點，且0是加法運算的單位元.
　　對任意的i∈N，若i≠0，則i=1+1+…+1（i個1相加）=1i；若i=0，則有0=10.
　　故為循環(huán)獨異點，其生成元為1.
　　【例5.4】是一個獨異點，其中S={1，a，b，c，d}，�呈荢上的二元運算，其運算表如表5.1所示.表5.1
　　��1abcd11abcdaaabddbbbdaaccdabbdddabb因為1是單位元，a是冪等元，b3=d3=a，因此1，a，b，d的任意非負整數(shù)次冪最多只能表示S中4個不同元.而c0=1，c1=c，c2=b，c3=a，c4=d所以獨異點是一個循環(huán)獨異點，其中c是生成元.
　　定理5.2每一個循環(huán)獨異點都是交換獨異點.
　　證明設(shè)為循環(huán)獨異點且g為其生成元，則對任意的x，y∈S，存在m，n∈N，使得x=gm，y=gn.于是x�硑=gm�砱n=gm+n=gn+m=gn�砱m=y�硏所以是交換獨異點.■
　　定理5.3設(shè)是一個有限的獨異點，則對每一個x∈S存在正整數(shù)j，使得xj是一個冪等元.
　　證明見定理5.1的證明.■
　　例如,例5.4中1，a，b3（=a），d3（=a），c3（=a）是冪等元.
　　定理5.4設(shè)是獨異點，a，b∈S且可逆，則
　　(1)(a-1)-1=a.
　　(2)(a�砨)-1=b-1�砤-1.
　　證明(1)設(shè)a-1是a的逆元，則有a�砤-1=a-1�砤=e，因此a-1可逆，且(a-1)-1=a.
　　(2)設(shè)a-1是a的逆元，b-1是b的逆元，因為(a�砨)��(b-1�砤-1)=a��(b�砨-1)�砤-1=a�砮�砤-1=a�砤-1=e，
　　(b-1�砤-1)��(a�砨)=b-1��(a-1�砤)�砨=b-1�砮�砨=b-1�砨=e，所以a�砨可逆，且(a�砨)-1=b-1�砤-1.■
　　5.1.2子半群和子獨異點
　　定義5.6設(shè)是一個半群，若是的子代數(shù)，則稱為的子半群.
　　設(shè)是一個獨異點，若是的子代數(shù)，且單位元e∈H，則稱為的子獨異點.
　　由定義知，子半群（子獨異點）是一個半群（獨異點）；半群（獨異點）是自身的一個子半群（子獨異點）.此外，<{e}；��>也是獨異點的子獨異點.
　　【例5.5】對于半群的任一元素x∈S，令集合H={x，x2，x3，…}，則是的子半群.
　　【例5.6】對于半群，Z+的子集A2={2n|n∈Z+}，A3={3n|n∈Z+}，A4={4n|n∈Z+}，…都是的子半群.
　　【例5.7】對于獨異點，子集A2，A3，A4，…（同例5.6）均不能形成的子獨異點；而B2={2n|n∈N}，B3={3n|n∈N}，B4={4n|n∈N}，…都能形成的子獨異點.
　　定理5.5設(shè)是一個交換獨異點，則S的所有冪等元的集合H形成的一個子獨異點.
　　證明由于S中單位元e適合e2=e，所以e∈H，于是H是S的非空子集且包含S中的單位元e.
　　對任意的x，y∈H，由x2=x，y2=y和運算�呈强山粨Q的得知(x�硑)2=x2�硑2=x�硑因此x�硑∈H，于是H對于運算�呈欠忾]的，從而是的一個子獨異點.■
　　【思考5.1】設(shè)代數(shù)系統(tǒng)和都是獨異點，若H�罶，則是的子獨異點嗎？
　　5.1.3半群和獨異點的同態(tài)
　　代數(shù)系統(tǒng)的同態(tài)（單同態(tài)、滿同態(tài)）、同構(gòu)和積代數(shù)的概念以及一些有關(guān)的結(jié)論可以推廣到半群和獨異點中.
　　定理5.6設(shè)h是從代數(shù)系統(tǒng)V1=到代數(shù)系統(tǒng)V2=的滿同態(tài)，其中運算�澈同�都是二元運算，則
　　(1)若V1是（交換）半群，則V2也是（交換）半群.
　　(2)若V1是（交換）獨異點，則V2也是（交換）獨異點.
　　推論5.1（交換）半群的同態(tài)像是（交換）半群，（交換）獨異點的同態(tài)像是（交換）獨異點.
　　定理5.7給定代數(shù)系統(tǒng)V1=和V2=，其中運算�澈同�都是二元運算，則
　　(1)若V1和V2是（交換）半群，則V1×V2也是（交換）半群.
　　(2)若V1和V2是（交換）獨異點，則V1×V2也是（交換）獨異點.
　　5.2群〖*4/5〗5.2.1群的基本概念〖*2〗1.群的定義定義5.7設(shè)是一個代數(shù)系統(tǒng)，如果G上的二元運算�碀M足下列條件，則稱是一個群，簡記成群G.
　　(1)運算�呈强山Y(jié)合的;
　　(2)存在單位元e∈G;
　　(3)G中所有元素都可逆.
　　如果群的運算�呈强山粨Q的，則稱該群為交換群或阿貝爾群.
　　例如，代數(shù)系統(tǒng)、、、、<2U；∪>、<2U；∩>都是群，且為交換群.但、、、都不是群，因為不是所有元都可逆.
　　【例5.8】代數(shù)系統(tǒng)為群，且為交換群.
　　證明(1)先證運算滿足結(jié)合律.
　　對任意的a，b，c∈Nn，令a+b=nm1+resn(a+b)，b+c=nm2+resn(b+c)則有
　　(a�輓b)�輓c=resn(a+b)�輓c=resn(resn(a+b)+c)