第五章 代數(shù)結(jié)構(gòu)

第五章代數(shù)系統(tǒng)1在計算機(jī)科學(xué)里，很多的知識和代數(shù)結(jié)構(gòu)的理論有關(guān)系，比如：加法器、糾正碼、形式語言和推理機(jī)等等，因此，學(xué)好該部分內(nèi)容，為學(xué)習(xí)其他計算機(jī)課程打下了基礎(chǔ)。通過本章學(xué)習(xí)，應(yīng)該掌握以下內(nèi)容：

（1）二元運算的相關(guān)概念和性質(zhì)（2）半群和獨異點的概念及其判定（3）群和子群的概念及其性質(zhì)（4）阿貝爾群和循環(huán)群的概念和性質(zhì)（5）置換群和陪集的概念相關(guān)定理（6）同態(tài)與同構(gòu)的概念及其判定

2前言代數(shù)系統(tǒng)又稱代數(shù)結(jié)構(gòu)，抽象代數(shù)。19世紀(jì)的數(shù)學(xué)家認(rèn)識到，對許多不相聯(lián)系的代數(shù)抽象出它們的共同的內(nèi)容進(jìn)行研究，可以發(fā)現(xiàn)它們具有統(tǒng)一的形式：它們都是由一些元素或者對象組成的集合；服從一種或者幾種運算，最主要的是該元素運算的結(jié)果仍然是該集合的元素。在研究的時候可以不理會具體的元素，只研究抽象的元素和抽象結(jié)構(gòu)的性質(zhì)，因此稱為抽象代數(shù)。31二元運算及其性質(zhì)2代數(shù)系統(tǒng)3半群和獨異點4群與子群5阿貝爾群和循環(huán)群6*置換群與伯恩賽德定理7陪集和拉格朗日定理8同態(tài)與同構(gòu)9環(huán)與域4n元運算：設(shè)S是一個非空集合，n是正整數(shù)，f是從Sn到S的一個函數(shù)，f：Sn→S，則稱f是一個集合S上的n元運算。第一節(jié)代數(shù)系統(tǒng)的引入5注意：當(dāng)n＝1時，稱f為一元運算，n＝2時為二元運算。運算通俗的說，它是一個“工具”或“機(jī)器”，這個機(jī)器對S中的元素進(jìn)行加工變成S中的另外元素。例如2*3＝5，“*”運算將“2”和“3”加工成了“5”。這個定義具有一定的廣泛性和抽象性。6定義5-1.1對于集合A，一個從An到B的映射，稱為集合A上的一個n元運算。如果B?A，則稱該n元運算是封閉的。代數(shù)系統(tǒng)的引入7定義5-1.2一個非空集合A連同若干個定義在該集合上的運算f1,f2,……,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記做<A,f1,f2,……,fk>。8例如正整數(shù)集合I+以及在該集合上的普通加法運算“＋”組成一個代數(shù)系統(tǒng)<I+,+>。一個有限集S，由S的冪集以及冪集上的集合運算：交、并、補(bǔ)所組成的是一個代數(shù)系統(tǒng)。計算機(jī)字長32位，并具有定點加、減、乘、除及邏輯加、邏輯乘各種運算指令。設(shè)有二進(jìn)制數(shù)的232個不同的數(shù)字組成的集合S，則S和計算機(jī)的運算型指令構(gòu)成一個代數(shù)系統(tǒng)。9代數(shù)系統(tǒng)的共性

考察代數(shù)系統(tǒng)<I，+>，這里I是整數(shù)集合，+是普通的加法運算。很明顯，在這個代數(shù)系統(tǒng)中，關(guān)于加法運算，具有以下三個運算規(guī)律，即對于任意的x，y，z∈I，有：

(1)x+y∈I(封閉性)

(2)x+y＝y(tǒng)+x(交換律)

(3)(x+y)+z＝x+(y+z)(結(jié)合律)

10容易找到與<I，+>具有相同運算規(guī)律的一些代數(shù)系統(tǒng)，如下表所示。<I,.><R,+><P(S),∪><P(S),∩>集合I:整數(shù)集合R:實數(shù)集合P(S):S的冪集P(S):S的冪集運算.普通乘法+普通加法∪集合的并∩集合的交封閉性x.y∈Ix+y∈RA∪B∈P(S)A∩B∈P(S)交換律x.y=y.xx+y=y+xA∪B=B∪AA∩B=B∩A結(jié)合律(x.y).z=x.(y.z)(x+y)+z=x+(y+z)(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)11第二節(jié)運算及其性質(zhì)定義5-2.1設(shè)*是定義在集合A上的二元運算，如果對于任意的x，y∈A，都有x*y∈A，則稱二元運算*在A上是封閉的。12例題1設(shè)A＝{x|x=2n,n∈N},問乘法運算是否封閉？加法運算呢？對于任意的2r，2s∈A，r，s∈N；因為，2r?2s＝2r+s∈A；所以，乘法運算是封閉的。對于加法運算是不封閉的；因為，至少有2+22＝6?A。解：13定義5-2.2設(shè)*是定義在集合A上的二元運算，如果對于任意的x，y∈A，都有x*y=y*x,則稱二元運算*在A上是可交換的。

14例題2設(shè)Q是有理數(shù)集合，△是Q上的二元運算，對任意的a，b∈Q，a△b＝a+b-a·b，問運算△是否可交換。

因為:

a△b＝a+b-a·b＝b+a-b·a＝b△a

所以運算△是可交換的。

解：

15定義5.2.3

設(shè)*是定義在集合A上的二元運算，如果對于任意的x，y，z∈A，都有(x*y)*z=x*(y*z)，則稱該二元運算*是可結(jié)合的。16例題3設(shè)A是一個非空集合,★是A上的二元運算,對于任意的a,b∈A,有a★b=b,證明★是可結(jié)合的。對于任意的a，b，c∈A。(a★b)★c＝b★c＝c

而

a★(b★c)＝a★c＝c所以

(a★b)★c＝a★(b★c)

證明：17說明：如果運算滿足交換律，則在計算時可以按元素任意次序運算，如果某運算既有結(jié)合律又有交換律，則在運算時會帶來很多方便。例：自然數(shù)加法。矩陣的乘法，函數(shù)的合成運算不具有交換律。18并非所有的代數(shù)系統(tǒng)都有結(jié)合律，例如：<I,->表示整數(shù)集和該集上的減法運算，它沒有結(jié)合律。在有結(jié)合律的代數(shù)系統(tǒng)中，可以省去表示結(jié)合律的括號。19定義5-2.4設(shè)*、△是定義在集合A上的兩個二元運算，如果對于任意的a，b，c∈A，都有

a*(b△c)=(a*b)△(a*c)(b△c)*a=(b*a)△(c*a)則稱運算*對于運算△是可分配的。20例題4設(shè)集合A={α,β}，在A上定義兩個二元運算*和△，如表所示。運算△對運算*可分配嗎?運算*對△呢?*αβααβββα△αβαααβαβ解

容易驗證運算△對于運算*是可分配的。但是運算*對于運算△是不可分配的，因為

β*(α△β)＝β*α＝β

而

(β*α)△(β*β)＝β△α＝α21定義5-2.5

設(shè)*，#是定義在集合A上的兩個可交換二元運算，如果對于任意的a，b∈A，都有

a*(a#b)=a

a#(a*b)=a則稱運算*和運算#滿足吸收律。22例題5設(shè)集合N為自然數(shù)的全體,在N上定義兩個二元運算*和★,對于任意x,y∈N,有：

x*y=max(x,y)

x★y=min(x,y)驗證*和★的吸收律。對于任意a，b∈N：

a*(a★b)＝max(a，min(a，b))＝a

a★(a*b)＝min(a，max(a，b))＝a因此，*和★滿足吸收律。解23注意：∧、∨滿足吸收律∪、∩滿足吸收律24定義5-2.6設(shè)*是定義在集合A上的一個二元運算,如果對于任意的x∈A,都有x*x=x,則運算*是等冪的。例題6設(shè)P(S)是集合S的冪集,在P(S)上定義兩個二元運算,集合的并運算∪和集合的交運算∩，驗證這兩個運算是等冪的。對于任意的A∈P(S)，有A∪A＝A和A∩A＝A；因此運算∪和∩都滿足等冪律。解：25幺元定義5-2.7設(shè)*是定義在集合A上的一個二元運算；如果有一個元素el∈A，對于任意的元素x∈A，都有el*x=x，則稱el為A中關(guān)于運算*的左幺元；如果有一個元素er∈A，對于任意的元素x∈A都有x*er=x，則稱er為A中關(guān)于運算*的右幺元；如果A中的某一個元素e，它既是左幺元又是右幺元，則稱e為A中關(guān)于運算*的幺元。

顯然，對于任意元素x∈A，有e*x=x*e=x。26例：<I,+>表示整數(shù)集上的加法運算組成的代數(shù)系統(tǒng)，那么左幺元和右幺元均為0。<I,*>表示整數(shù)集上的乘法運算組成的代數(shù)系統(tǒng)，那么左幺元和右幺元均為1。27例題7：設(shè)集合S={α，β，γ，δ}，在S上定義的兩個二元運算*和Δ，試指出左幺元和右幺元。解：由上表可以看出β、δ都是S中關(guān)于*的左幺元，而α是S中運算Δ的右幺元。*αβγδαδαβγβαβγδγαβγγδαβγδΔαβγδααβδγββαγδγγγαβδδγβγ28定理5-2.1設(shè)*是定義在集合A上的一個二元運算，且在A中有關(guān)于運算*的左幺元el和右幺元er，則el=er=e，且A中的幺元是唯一的。因為，el

和er分別是A中關(guān)于運算*的左幺元和右幺元；所以，el=el*er=er=e。設(shè)另有一個幺元e1∈A，則e1=e1*

e=e。證明:29零元定義5-2.8設(shè)*是定義在集合A上的一個二元運算；如果有一個元素θl∈A，對于任意的元素x∈A都有θl*x=θl，則稱θl為A中關(guān)于運算*的左零元；如果有一個元素θr∈A,對于任意的元素x∈A，都有x*θr=θr,則稱θr為A中關(guān)于運算*的右零元；如果A中的一個元素θ，它既是左零元又是右零元，則稱θ為A中關(guān)于運算*的零元。顯然，對于任一元素a∈A，有θ*a=a*θ=θ。30例題8：設(shè)集合S＝{淺色，深色}，定義在集合上的二元運算*如表所示，指出零元和幺元。*淺色深色淺色淺色深色深色深色深色深色是S中關(guān)于運算*的零元；淺色是S中關(guān)于運算*的幺元。解：31定理5-2.2設(shè)*是定義在集合A上的一個二元運算，且在A中存在關(guān)于運算*的左零元和右零元。那么，左右零元相等，且A中的零元是唯一的。32定理5-2.3設(shè)<A，*>是一個代數(shù)系統(tǒng)，且集合A中元素的個數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元θ。則它們必然不相等。反證法假設(shè)θ=e那么對于任意的x∈A，必有：

x=e*x=θ*x=θ=e于是A中所有的元素都是相同的。這與A中含有多個元素相矛盾。證明:33定義5-2.9設(shè)代數(shù)系統(tǒng)<A，*>，*是定義在集合A上的一個二元運算，且e是A中關(guān)于運算*的幺元。如果對于A中的任一元素a，存在著A中的某個元素b，使得b*a=e，那么稱b為a的左逆元；如果a*b=e成立，那么稱b為a的右逆元；如果一個元素b，它既是a的左逆元又是a的右逆元，那么就稱b是a的一個逆元。逆元34對于任意元素<x，y><1，0>*<x，y>=<1*x，0+y>=<x，y><x，y>*<1，0>=<x*1，y+0>=<x，y>因此，元素<1，0>為該運算的幺元。例題設(shè)Q是有理數(shù)集合，作笛卡爾積S=Q×Q，*是S上的二元運算。<a，b>*<x，y>=<ax，b+y>。求*運算的幺元和逆元。解：35對于任意元素<x，y>；當(dāng)x≠0時：<1/x,-y>*<x,y>=<(1/x)*x，-y+y>=<1,0><x,y>*<1/x,-y>=<x*(1/x)，y+(-y)>=<1,0>故，當(dāng)x≠0時，<1/x,-y>為元素<x,y>的逆元。當(dāng)x=0時：任何元素和0相乘都等于0，因此，沒有逆元。36說明：如果b是a的逆元，那么a也是b的逆元，簡稱為a與b互為逆元。今后，一個元素x的逆元記為x-1

。一般來說一個元素的左逆元不一定等于右逆元，而且一個元素可以有左逆元而沒有右逆元，甚至一個元素的左（右）逆元可以不是唯一的。37例題9：設(shè)集合S＝{α，β，γ，δ，ξ}，定義在S上的一個二元運算*如表所示，指出各個元素的左右逆元的情況。*αβγδξααβγδξββδαγδγγαβαβδδαγδγξξδαγξ38α是幺元；β的左逆元和右逆元都是γ；即β和γ互為逆元；δ的左逆元是γ而右逆元是β；β有兩個左逆元γ和δ；ζ的右逆元是γ，但ζ沒有左逆元。解：39定理5-2.4設(shè)代數(shù)系統(tǒng)<A，*>，這里*是定義在A上的一個二元運算，A中存在幺元e，且每一個元素都有左逆元。如果*是可結(jié)合的運算，那么，這個代數(shù)系統(tǒng)中任何一個元素的左逆元必定也是該元素的右逆元，且每個元素的逆元是唯一的。

40

證明：設(shè)任意a∈A，b是a的左逆元。設(shè)c是b的左逆元。因為：(b*a)*b＝e*b＝b所以

e＝c*b＝c*((b*a)*b)＝(c*(b*a))*b＝((c*b)*a)*b＝(e*a)*b＝a*b因此，b也是a的右逆元。41設(shè)元素a有兩個逆元b和b'那么：b＝b*e＝b*(a*b')＝(b*a)*b'＝e*b'＝b'因此，a的逆元是唯一的。42例題10：試構(gòu)造一個代數(shù)系統(tǒng)，使得其中只有一個元素具有逆元。設(shè)m,n∈I,T={x|x∈I,m≤x≤n}；那么，代數(shù)系統(tǒng)<T,max>中有一個幺元是m。只有一個m有逆元，因為m＝max<m,m>。解：43例題11對于代數(shù)系統(tǒng)<R，·>。這里R是實數(shù)的全體，·是普通的乘法運算，是否每個元素都有逆元。

該代數(shù)系統(tǒng)中的幺元是1，除了零元素0外，所有的元素都有逆元。解：44例題12對于代數(shù)系統(tǒng)<Nk，+k>，這里Nk＝{0，1，2，…，k-1}，+k是定義在Nk上的模k加法運算，定義如下：

對于任意x，y∈Nk

x+ky=x+yx+y-k若x+y<k若x+y≥k試問：是否每個元素都有逆元。解:可以驗證，+k是一個可結(jié)合的二元運算，Nk中關(guān)于運算+k的幺元是0，Nk中的每一個元素都有唯一的逆元，即0的逆元是0，每個非零元素x的逆元是k-x。

45注意：<A，*>是一個代數(shù)系統(tǒng)，*是A上的一個二元運算，那么該運算的有些性質(zhì)可以從運算表中直接看出。

運算*具有封閉性，當(dāng)且僅當(dāng)運算表中的每個元素都屬于A。運算*具有可交換性，當(dāng)且僅當(dāng)運算表關(guān)于主對角線是對稱的。運算*具有等冪性，當(dāng)且僅當(dāng)運算表的主對角線上的每一元素與它所在行(列)的表頭元素相同。46A關(guān)于*有零元，當(dāng)且僅當(dāng)該元素所對應(yīng)的行和列中的元素都與該元素相同。A中關(guān)于*有幺元，當(dāng)且僅當(dāng)該元素所對應(yīng)的行和列依次與運算表的行和列相一致。設(shè)A中有幺元，a和b互逆，當(dāng)且僅當(dāng)位于a所在行，b所在列的元素以及b所在行，a所在列的元素都是幺元。47作業(yè)：p185（3）48第三節(jié)半群定義5-3.1設(shè)<A，f1，f2，…，fk>是一個代數(shù)系統(tǒng)，若定義在該集合上的運算f1，f2，…，fk都滿足封閉性，那么<A，f1，f2，…，fk>稱為廣群。1廣群特殊情形：如果*是S上的一個二元運算，*運算是封閉的，則稱代數(shù)系統(tǒng)<S,*>為廣群。492半群定義5-3.2一個代數(shù)系統(tǒng)<P，*>，其中P是非空集合，*是P上的一個二元運算。如果滿足：（1）運算*是封閉的。（2）運算*是可結(jié)合的，即對任意的a，b，c∈P，滿足(a*b)*c=a*(b*c)則稱代數(shù)系統(tǒng)<P，*>為半群。50顯然，封閉性滿足。對于任意的x，y，z∈A，(x△y)△z=max(max(x,y),z)

x△(y△z)=max(x,max(y,z))由于兩個式子最后的結(jié)果都是x，y，z中的最大數(shù)，因此，(x△y)△z=x△(y△z)。所以，△滿足封閉性和可結(jié)合性。故，<A，△>是半群。例對于給定某集合A，在該集合上定義運算△為：x△y=max(x,y)，驗證<A，△>是否構(gòu)成半群。解：51定理5-3.1設(shè)<S，*>是一個半群，B?S且*在B上是封閉的，那么<B，*>也是一個半群。通常稱<B，*>是半群<S，*>的子半群。3子半群因為*在S上是可結(jié)合的，而B?S且*在B上封閉，所以*在B上也是可結(jié)合的。因此，<B，*>是一個半群。證明：52例題3設(shè)·表示普通的乘法運算，那么<[0，1]，·>、<[0，1)，·>和<I，·>都是<R，·>的子半群。首先，運算·在R上是封閉的，且是可結(jié)合的，所以<R，·>是一個半群。其次，運算·在[0，1]、[0，1)和I上都是封閉的，且[0，1]?R，[0，1)?R，I?R。因此，由定理5-3.1可知<[0，1],·>、<[0，1),·>和<I，·>都是<R，·>的子半群。

解：534半群的性質(zhì)定理5-3.2設(shè)<S，*>是一個半群，如果S是一個有限集，則必有a∈S，使得a*a＝a。

證明：

5455565獨異點

定義5-3.3含有幺元的半群稱為獨異點。

例：代數(shù)系統(tǒng)<R，+>是一個獨異點，因為，<R，+>是一個半群，且0是R中關(guān)于運算+的幺元。

代數(shù)系統(tǒng)<I，·>，<I+，·>，<R，·>都是具有幺元1的半群，因此它們都是獨異點。

代數(shù)系統(tǒng)<N一{0}，+>雖是一個半群，但關(guān)于運算+不存在幺元，所以，這個代數(shù)系統(tǒng)不是獨異點。

57定理5-3.3設(shè)<S，*>是一個獨異點，則在關(guān)于運算*的運算表中任何兩行或兩列都是不相同的。

證明：設(shè)S中關(guān)于運算*的幺元是e。因為對于任意的a，b∈S且a≠b時，總有

e*a＝a≠b＝e*b和

a*e＝a≠b＝b*e所以，在*的運算表中不可能有兩行或兩列是相同的。58例題4設(shè)I是整數(shù)集合，m是任意正整數(shù)，Zm是由模

m的同余類組成的同余類集，在Zm上定義兩個二元運算+m和×m分別如下：

對于任意的[i]，[j]∈Zm

[i]+m[j]＝[(i+j)(modm)]

[i]×m[j]＝[(i×j)(modm)]試證明：在這兩個二元運算的運算表中任何兩行或兩列都不相同。

59證明：考察代數(shù)系統(tǒng)<Zm，+m>和<Zm，×m)。(1)

由運算+m和×m的定義，可知它們在Zm上都是封閉的。(2)對于任意[i]，[j]，[k]∈Zm([i]+m[j])+m[k]＝[i]+m([j]+m[k])＝[(i+j+k)(modm)]([i]×m[j])×m[k]＝[i]×m([j]×m[k])＝[(i×j×k)(modm)]即+m，×m都是可結(jié)合的。60(3)因為[0]+m[i]＝[i]+m[0]＝[i]所以，[0]是<Zm，+m>中的幺元。因為[1]×m[i]＝[i]×m[1]＝[i]所以[1]是<Zm，×m>中的幺元。因此，代數(shù)系統(tǒng)<Zm，+m>，<Zm，×m>都是獨異點。由定理5-3.3可知，這兩個運算的運算表中任何兩行或兩列都不相同。61上例中，如果給定m＝5，那么，+5和×5的運算表分別如表5-3.2和表5-3.3所示。

顯然，上述運算表中沒有兩行或兩列是相同的。

62定理5-3.4設(shè)<S,*>是一個獨異點，對于任意的a，b∈S，且a，b均有逆元，則：(1)(a－1)－1＝a(2)a*b有逆元，且(a*b)-1=b-1*a-1證明：因為a-1是a的逆元，即a*a-1=a-1*a=e

所以(a-1)-1＝a(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)=e所以，(a*b)-1=(b-1*a-1)63作業(yè)：P190(5)64第四節(jié)群與子群定義5-4.1設(shè)<G，*>是一個代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個二元運算，如果滿足下面的條件：（1）運算*是封閉的。（2）運算*是可結(jié)合的。（3）存在幺元e。（4）對于每一個元素x∈G，存在著它的逆元x-1。則稱<G，*>是一個群。1群65例

對于<Z，+>來說，Z是全體整數(shù)構(gòu)成的集合，+是普通加法。(1)+對于Z來說是封閉的；(2)+可結(jié)合的；(3)0∈Z是幺元；(4)對任意元素x∈Z，都有-x∈Z，使得x+(-x)=0；因此，<Z，+>滿足上面所有的條件。所以，<Z，+>是一個群。66同理，<R，+>也是群。但是，<R，*>不是群。因為1是<R，*>的幺元，但是對于0∈R就沒有逆元。67例題1設(shè)R＝{0°，60°，120°，180°，240°，300°}表示在平面上幾何圖形繞形心順時針旋轉(zhuǎn)角度的六種可能情況，設(shè)★是R上的二元運算，對于R中任意兩個元素a和b，a★b表示平面圖形連續(xù)旋轉(zhuǎn)a和b得到的總旋轉(zhuǎn)角度。并規(guī)定旋轉(zhuǎn)360°等于原來的狀態(tài)，就看作沒有經(jīng)過旋轉(zhuǎn)。驗證：<R，★>是一個群。68解由題意，R上二元運算★的運算表如表所示。

由表可見，運算★在R上是封閉的。對于任意的a，b，c∈R，(a★b)★c表示將圖形依次旋轉(zhuǎn)a，b和c，而a★(b★c)表示將圖形依次旋轉(zhuǎn)a和b，c，而總的旋轉(zhuǎn)角度都等于a+b+c(mod360°)，因此，(a★b)★c＝a★(b★c)。0°是幺元。60°，120°，180°的逆元分別是300°，180°，240°。因此，<R，★>是一個群。692有限群

定義6-4.2設(shè)<G，*>是一個群。如果G是有限集，那么稱<G，*>為有限群，G中元素的個數(shù)通常稱為該有限群的階數(shù)，記為|G|；如果G是無限集，則稱<G，*>為無限群。例題1中所述的<R，★>就是一個有限群，且，|R|＝6。

70小結(jié)：

廣群僅僅是一個具有封閉二元運算的非空集合；半群是一個具有結(jié)合運算的廣群；獨異點是具有幺元的半群；群是每個元素都有逆元的獨異點。即：{群}

{獨異點}

{半群}

{廣群}

由圖說明如下：：713群的性質(zhì)

定理5-4.1群中不可能有零元。證明：當(dāng)群的階為1時，它的唯一元素視作幺元。設(shè)|G|>1且群<G，*>有零元θ。那么，群中任何元素x∈G，都有x*θ＝θ*x＝θ≠e。所以，零元θ就不存在逆元；這與<G，*>是群相矛盾。72定理5-4.2設(shè)<G，*>是一個群，對于a，b∈G，必存在唯一的x∈G，使得a*x＝b。證明：設(shè)a的逆元是a-1，令x=a-1*b則a*x=a*(a-1*b)=(a*a-1)*b=e*b=b若另有一解x1，滿足a*x1=b，則

a-1*(a*x1)=a-1*b即x1=a-1*b73定理5-4.3設(shè)<G，*>是一個群，對于任意的a，b，c∈G，如果有a*b=a*c或者b*a＝c*a，則必有b＝c(消去律)。設(shè)a*b=a*c，且a的逆元是a-1；則有，a-1*(a*b)=a-1*(a*c)(a-1*a)*b=(a-1*a)*c

e*b=e*c

b=c當(dāng)b*a＝c*a，同理可證，b=c。由定理5-4.3可知：群的運算表中沒有兩行(或兩列)是相同的。證明：744置換定義5-4.3設(shè)S是一個非空集合，從集合S到S的一個雙射稱為S的一個置換。

例如，對于集合S＝{a，b，c，d}，將a映射到b，b映射到d，c映射到a，d映射到c是一個從S到S上的一個一對一映射，這個置換可以表示為：即上一行中按任何次序?qū)懗黾现械娜吭?，而在下一行中寫每個對應(yīng)元素的象。abcdbdac75定理5-4.4群<G，*>的運算表中的每一行或每一列都是G的元素的一個置換。證明：首先，證明運算表中的任一行或任一列所含G中的一個元素不可能多于一次。用反證法，如果對應(yīng)于元素a∈G的那一行中有兩個元素都是c，即有

a*b1＝a*b2＝c，且b1≠b2

由定理5-4.3可得b1＝b2，這與b1≠b2矛盾。76其次，要證明G中的每一個元素都在運算表的每一行和每一列中出現(xiàn)?？疾鞂?yīng)于元素a∈G的那一行；設(shè)b是G中的任一元素；由于b＝a*(a-1*b)，所以b必定出現(xiàn)在對應(yīng)于a的那一行中。再由運算表中沒有兩行(或兩列)相同的事實，便可得出：<G，*>的運算表中每一行都是G的元素的一個置換，且每一行都是不相同的。同樣的結(jié)論對于列也是成立的。775等冪元定義5-4.4代數(shù)系統(tǒng)<G，*>中，如果存在a∈G，有a*a＝a，則稱a為等冪元。定理5-4.5在群<A，*>中，除幺元e外，不可能有任何別的等冪元。證明：因為e*e＝e，所以e是等冪元?，F(xiàn)設(shè)

a∈A，a≠e且a*a＝a則有

a＝e*a＝(a-1*a)*a＝a-1*(a*a)＝a-1*a＝e與假設(shè)a≠e相矛盾。

786子群定義5-4.5設(shè)<G,*>是一個群，S是G的非空子集，如果<S,*>也構(gòu)成群，則稱<S,*>是<G,*>的一個子群。定理5-4.6設(shè)<G,*>是一個群，<S,*>是<G,*>的一個子群，那么，<G,*>中的幺元e必定也是<S,*>中的幺元。證明：設(shè)<S,*>中的幺元為e1，對于任一x∈S?G，必有：e1*x＝x＝e*x，故e1＝e。79定義5-4.6設(shè)<G,*>是一個群，<S,*>是<G,*>的子群，如果S＝{e}，或者S＝G，則稱<S,*>為<G,*>的平凡子群。80例題3<I，+>是一個群，設(shè)IE＝{x|x＝2n，n∈I}，證明<IE，+>是<I，+>的一個子群。證明：對于任意的x，y∈IE，不妨設(shè)x＝2n1，y＝2n2，n1，n2∈I則

x+y＝2n1+2n2=2(n1+n2)，而n1+n2∈I，所以

x+y∈IE，即+在IE上封閉。運算+在IE上保持可結(jié)合性。<I，+>中的幺元0也在IE中。對于任意的x∈IE，必有n使得x＝2n，而

-x＝-2n＝2(-n)，-n∈I，所以-x∈IE，而x+(-x)＝0。因此，<IE，+>是<I，+>的一個子群。817子群的判定法定理5-4.7設(shè)<G，*>是一個群，B是G的非空子集，如果B是一個有限集，那么，只要運算*在B上封閉，<B，*>必定是<G，*>的子群。

證明：

設(shè)b是B中的任一個元素。若*在R上封閉，則元素b2＝b*b，b3＝b2*b，…都在B中。由于B是有限集，所以必存在正整數(shù)i和j，不妨假設(shè)i<j使得bi=bj，即bi=bi

*bj-i。

82

這就說明bj-i是<G，*>中的幺元，且這個幺元也在子集B中。如果，j-i>1，那么由bj-i=b*bj-i-1，可知bj-i-1是b的逆元，且bj-i-1∈B；如果j-i＝1，那么由bi=bi*b可知b就是幺元，而幺元是以自身為逆元的。因此，<B，*>是<G，*>的一個子群。8384證明：

8586定理5-4.8設(shè)<G，△>是群，S是G的非空子集，如果對于S中的任意元素a和b有a△b-1∈S，則<S，△>是<G，△>的子群。

首先證明，G中的幺元e也是S中的幺元。任取S中的元素a，a∈S?G，所以e＝a△a-1∈S，且a△e＝e△a＝a，即e也是S中的幺元。證明：87最后證明，△在S上是封閉的。

對任意的a，b∈S，由上可知b-1∈S而

b＝(b-1)-1所以

a△b＝a△(b-1)-1∈S至于，運算△在S上的可結(jié)合性是保持的因此，<S，△>是<G，△>的子群。

其次證明，S中的每一元素都有逆元。對任一a∈S，因為e∈S，所以：e△a-1∈S，即a-1∈S。88例題5設(shè)<H，*>和<K，*>都是群<G，*>的子群，試證明<H∩K，*>也是<G，*>的子群。

設(shè)任意的a，b∈H∩K，因為<H，*>和<K，*>都是子群，所以b-1∈H∩K。由于*在H和K中的封閉性，所以a*b-1∈H∩K。由定理5-4.8即得<H∩K，*>是<G，*>的子群。證明：89習(xí)題：P197(2)90定義5-5.1如果群<G,*>中的運算*是可交換的,則稱該群為阿貝爾群,或交換群。第五節(jié)阿貝爾群和循環(huán)群1阿貝爾群91設(shè)S＝{a，b，c，d}，在S上定義一個雙射函數(shù)f：f(a)＝b，f(b)＝c，f(c)＝d，f(d)＝a；

對于任一x∈S，構(gòu)造復(fù)合函數(shù)：

f(x)2＝fof(x)＝f(f(x))

f(x)3＝fof

2(x)＝f(f

2(x))

f(x)4＝fof

3(x)＝f(f

3(x))

如果用f

0表示S上的恒等映射，即

f0(x)＝x(x∈S)

很明顯地有f

4(x)＝f

0(x)，記f1＝f，構(gòu)造集合F＝{f

0，f1，f2，f3}；

那么<F，o>是一個阿貝爾群。

例題192對于f中任意兩個函數(shù)的復(fù)合，可以由表給出。

f

0是關(guān)于復(fù)合運算o的幺元。f0的逆元就是它自身，f

1和f

3互為逆元，f

2的逆元也是它自身。由表的對稱性，可知復(fù)合運算o是可交換的。因此，<F，o>是—個阿貝爾群。ofo

f1

f2

f3fo

f1

f2

f3fo

f1

f2

f3f1

f2

f3fo

f2

f3

fo

f1

f3fo

f1

f2解：93例題2設(shè)G為所有n階非奇(滿秩)矩陣的集合，矩陣乘法運算o作為定義在集合G上的二元運算，則<G，o>是一個不可交換群。

任意兩個n階非奇矩陣相乘后，仍是一個非奇矩陣，所以運算o是封閉的。矩陣乘法運算是可結(jié)合的。n階單位陣E是G中的幺元。任意一個非奇陣A存在著唯一的逆陣A-1，使：A-1oA＝AoA-1＝E矩陣乘法是不可交換的。因此，<G，o>是一個不可交換群。解：94定理5-5.1設(shè)<G，*>是一個群，<G，*>是阿貝爾群的充要條件是對任意的a，b∈G，有(a*b)*(a*b)＝(a*a)*(b*b)。

設(shè)對任意a，b∈G，有

(a*b)*(a*b)＝(a*a)*(b*b)。因為

a*(a*b)*b＝(a*a)*(b*b)＝(a*b)*(a*b)＝a*(b*a)*b所以

a-1*(a*(a*b)*b)*b-1＝a-1(a*(b*a)*b)*b-1即得

a*b＝b*a因此，群<G，*>是阿貝爾群。證明：充分性：95必要性設(shè)<G，*>是阿貝爾群，則對任意的a，b∈G，有：

a*b＝b*a因此(a*a)*(b*b)＝a*(a*b)*b＝a*(b*a)*b＝(a*b)*(a*b)

962循環(huán)群定義5-5.2設(shè)<G，*>為群，若在G中存在一個元素a，使得G中的任意元素都由a的冪組成，則稱該群為循環(huán)群，元素a稱為循環(huán)群G的生成元。

例如，60°就是群<{0°，60°，120°，180°，240°，300°}，★>的生成元，因此，該群是循環(huán)群。

97定理5-5.2任何一個循環(huán)群必定是阿貝爾群。

證明：

設(shè)<G，*>是一個循環(huán)群，它的生成元是a。那么，對于任意的x，y∈G，必有r，s∈I，使得：x＝ar和y＝as則

x*y＝ar

*as＝ar+s＝as+r＝as*ar＝y(tǒng)*x因此，<G，*>是一個阿貝爾群。98定理5-5.3設(shè)<G，*>是一個由元素a∈G生成的有限循環(huán)群。如果G的階數(shù)是n，即|G|＝n，則an＝e，且G＝{a，a2，a3，…，an-1，an＝e}，其中，e是<G，*>中的幺元，n是使an＝e的最小正整數(shù)(稱n為元素a的階)。

99假設(shè)對于某個正整數(shù)m，m<n，有am=e。由于<G，*>是一個循環(huán)群，所以G中的任何元素都能寫為ak(k∈I)。又，k=mq+r，其中，q是某個整數(shù)，0≤r<m。因此，ak＝amq+r＝(am)q*ar＝ar。這就導(dǎo)致G中每一個元素都可表示成ar(0≤r<m)。這樣，G中最多有m個不同的元素，與|G|＝n相矛盾。所以，am＝e(m<n)是不可能的。

證明：100進(jìn)一步證明a，a2，…，an都不相同。用反證法。假設(shè)ai＝aj，其中1≤i<j≤n；就有aj-i＝e，而且1≤j-i<n；這已經(jīng)由上面證明是不可能的。所以，a，a2，…，an都不相同。因此，

G＝{a，a2，…，an＝e}101例題3設(shè)G＝{α，β，γ，δ}，在G上定義二元運算*如表5-5.2所示。

說明<G，*>是一個循環(huán)群。

*αβγδααβγδββαδγγγδβαδδγαβ102解：由運算表5-5.2可知運算*是封閉的，α是幺元。β，γ和δ的逆元分別是β，δ和γ?？梢则炞C運算*是可結(jié)合的。所以<G，*>是一個群。從例題3中可以看到：一個循環(huán)群的生成元可以不是唯一的。在這個群中，由于：

γ*γ＝γ2＝β，γ3＝δ，γ4＝α以及

δ*δ＝δ2＝β，δ3＝γ，δ4＝α故群<G，*>是由γ或δ生成的。因此，<G，*>是一個循環(huán)群。

103習(xí)題P200(1)(5)104第七節(jié)陪集和拉格朗日定理定義5.7.1設(shè)<G，*>是一個群，A、B∈P(G)（即：A，B是G的子集）且A≠

，B≠

，記AB={a*b|a∈A，b∈B}和A-1={a-1|a∈A}，分別稱為A，B的積和A的逆。1符號的約定1052陪集定義5-7.2設(shè)<H，*>是群<G，*>的一個子群，a∈G，則集合{a}H(H{a})稱為由a所確定的集合H在G中的左陪集(右陪集)，簡稱H關(guān)于a的左陪集（右陪集），記為aH（Ha）。元素a稱為陪集aH(Ha)的代表元素。

106例1設(shè)G＝R×R，R為實數(shù)集，G上的一個二元運算+定義為：<x1，y1>+<x2，y2>＝<x1+x2，y1+y2>顯然，<G，+>是一個具有幺元<0，0>的阿貝爾群。設(shè)H＝{<x，y>|y＝2x}容易驗證：<H，+>是<G，+>的子群。對于<x0，y0>∈G；H關(guān)于<x0，y0>的左陪集為<x0，y0>H。107這個例子的幾何意義為：G是笛卡爾平面，H是通過原點的直線y＝2x，陪集<x0，y0>H是通過點<x0，y0>且平行于H的直線。如圖所示：1083拉格朗日定理

定理5-7.1(拉格朗日定理)設(shè)<H，*>是群<G，*>的一個子群，那么：

(1)R＝{<a，b>|a∈G，b∈G且a-1*b∈H}是G中的一個等價關(guān)系。對于a∈G，若記[a]R＝{x|x∈G且<a，x>∈R}，則：

[a]R＝aH(2)如果G是有限群，|G|＝n，|H|＝m，則m|n。

109對于任一a∈G，必有a-1∈G，使a-1*a＝e∈H。所以<a，a>∈R。R是自反的。若<a，b>∈R，則a-1*b∈H。因為H是G的子群；故

(a-1*b)-1＝b-1*a∈H。所以，<b，a>∈R。R是對稱的。證明：(1)110若<a，b>∈R，<b，c>∈R；則a-1*b∈H，b-1*c∈H；所以a-1*b*b-1*c＝a-1*c∈H；因而，<a，c>∈R。R是傳遞的。這就證明了R是G中的一個等價關(guān)系。對于a∈G，有：b∈[a]R當(dāng)且僅當(dāng)<a，b>∈R；即當(dāng)且僅當(dāng)a-1*b∈H；而a-1*b∈H就是b∈aH。因此，[a]R＝aH。111(2)由于R是G中的一個等價關(guān)系，所以必定將G劃分成不同的等價類[a1]R，[a2]R，…，[ak]R，使得：

又因，H中任意兩個不同的元素h1，h2，a∈G，必有a*h1≠a*h2；所以|aiH|＝|H|＝m，i＝1，2，…，k。因此：112根據(jù)拉格朗日定理，可得到以下幾個推論：

推論1

任何質(zhì)數(shù)階的群不可能有非平凡子群。

因為，如果有非平凡子群，那么該子群的階必定是原來群的階的一個因子，這就與原來群的階是質(zhì)數(shù)相矛盾。113推論2

設(shè)<G，*>是n階有限群，那么對于任意的a∈G，a的階必是n的因子且必有an＝e，這里e是群<G，*>中的幺元。如果n為質(zhì)數(shù)，則<G，*>必是循環(huán)群。

因為，由G中的任意元素a生成的循環(huán)群為：

H＝{ai|i∈I，a∈G}一定是G的一個子群。如果H的階是m，那么由定理5-5.3可知am＝e，即a的階等于m。

114由拉格朗日定理必有n＝mk，k∈I+，因此，a的階m是n的因子，且有：

an＝amk＝(am)k＝ek＝e

因為質(zhì)數(shù)階群只有平凡子群，所以，質(zhì)數(shù)階群必定是循環(huán)群。

必須注意，群的階與元素的階這兩個概念的不同。

115例題1設(shè)K＝{e，a，b，c}，在K上定義二元運算*如表所示。

證明：<K，*>是一個群，但不是循環(huán)群。

由表可知，運算*是封閉的和可結(jié)合的；幺元是e，每個元素的逆元是自身；所以，<K，*>是群。因為a，b，c都是二階元，故<K，*>不是循環(huán)群。證明：＊eabceabcabceaecbbceacbae116稱<K，*>為Klein四元群

例如，S＝{1，2，3，4}，置換群：

就是一個Klein四元群。

117例題2任何一個四階群只可能是四階循環(huán)群或者Klein四元群。

設(shè)四階群為<{e，a，b，c}，*>。其中e是幺元。當(dāng)四階群含有一個四階元素時，這個群就是循環(huán)群。當(dāng)四階群不含有四階元素時，則由推論2可知，除幺元e外，a，b，c的階一定都是2。證明：118a*b不可能等于a，b或e，否則將導(dǎo)致b＝e，a＝e或a＝b的矛盾，所以a*b＝c。同樣地，有b*a＝c以及a*c＝c*a＝b，b*c＝c*b＝a。因此，這個群是Klein四元群。

119第八節(jié)同態(tài)與同構(gòu)定義5-8.1設(shè)<A，★>和<B，*>是兩個代數(shù)系統(tǒng)，★和*分別是A和B上的二元運算，設(shè)f是從A到B的一個映射，使得對任意的a1，a2∈A，有：f(a1★a2)=f(a1)*f(a2)則稱f為<A，★>到<B，*>的一個同態(tài)映射，稱<A，★>同態(tài)于<B，*>，記作A～B。把<f(A)，*>稱為<A，★>的一個同態(tài)象。其中

f(A)＝{x|x＝f(a)，a∈A}?B

討論兩個代數(shù)系統(tǒng)之間的聯(lián)系

1同態(tài)

120說明：兩個代數(shù)系統(tǒng)在同態(tài)意義下的相互聯(lián)系可以由圖5-8.1來描述。由一個代數(shù)系統(tǒng)到另一個代數(shù)系統(tǒng)可能存在著多于一個的同態(tài)。1212同態(tài)的分類：滿同態(tài)、單一同態(tài)、同構(gòu)

定義5-8.2設(shè)f是由<A，★>到<B，*>的一個同態(tài)；如果f是從A到B的一個滿射，則f稱為滿同態(tài)；如果f是從A到B的一個入射，則f稱為單一同態(tài)；如果f是從A到B的一個雙射，則f稱為同構(gòu)映射，并稱<A，★>和<B，*>是同構(gòu)的，記作A≌B。

122例例1設(shè)f：R→R定義為對任意x∈R

f(x)＝5x

那么，f是從<R，+>到<R，·>的一個單一同態(tài)。

例2設(shè)f：N→Nk定義為對任意的x∈N

f(x)＝xmodk

那么，f是從<N，+>到<Nk，+>的一個滿同態(tài)。

123例3設(shè)H＝{x|x＝dn，d是某一個正整數(shù)，n∈I}，定義映射f：I→H為對任意n∈I

f(n)＝dn

那么，f是<I，+>到<H，+>的一個同構(gòu)。所以I≌H。124

例題1設(shè)A＝{a，b，c，d}，在A上定義一個二元運算如表5-8.2所示。又設(shè)B＝{α，β，γ，δ}，在B上定義一個二元運算如表5-8.3所示。證明<A，★>和<B，*>是同構(gòu)的。

★abcdabcdabcdbaacbddcabcd＊αβγδαβγδαβγδβααγβδδγαβγδ表5-8.2表5-8.3125考察映射f，使得

f(a)＝α

f(b)＝β

f(c)＝γ

f(d)＝δ

顯然，f是一個從A到B的雙射。由表5-8.2和表5-8.3容易驗證f是由<A，★>到<B，*>的一個同態(tài)。因此，<A，★>和<B，*>是同構(gòu)的。證明：126如果考察映射g，使得

g(a)＝δg(b)＝γ

g(c)＝βg(d)＝α那么，g也是由<A，★>到<B，*>的一個同構(gòu)。

當(dāng)兩個代數(shù)系統(tǒng)是同構(gòu)的話，它們之間的同構(gòu)映射可以是不唯一的。127注意：兩個同構(gòu)的代數(shù)系統(tǒng)只是符號的不同。

同構(gòu)這個概念很重要。形式上不同的代數(shù)系統(tǒng)，如果它們是同構(gòu)的話，那么，就可抽象地把它們看作是本質(zhì)上相同的代數(shù)系統(tǒng)，所不同的只是所用的符號不同。并且，容易看出同構(gòu)的逆仍是一個同構(gòu)。1283自同態(tài)和自同構(gòu)

定義5-8.3

設(shè)<A，★>是一個代數(shù)系統(tǒng)，如果f是由<A，★>到<A，★>的同態(tài)，則稱f為自同態(tài)。如果g是<A，★>到<A，★>的同構(gòu)，則稱g為自同構(gòu)。

1294同態(tài)與同構(gòu)的性質(zhì)

定理5-8.1設(shè)G是代數(shù)系統(tǒng)的集合，則G中代數(shù)系統(tǒng)之間的同構(gòu)關(guān)系是等價關(guān)系。

因為任何一個代數(shù)系統(tǒng)<A，★>可以通過恒等映射與它自身同構(gòu)，即自反性成立。關(guān)于對稱性，設(shè)<A，★>≌<B，*>且有對應(yīng)的同構(gòu)映射f，因為f的逆是由<B，*>到<A，★>的同構(gòu)映射，即<B，*>≌<A，★>。證明：130最后，如果f是由<A，★>到<B，*>的同構(gòu)映射，g是由<B，*>到<C，△>的同構(gòu)映射，那么g

of就是<A，★>到<C，△>的同構(gòu)映射。因此，同構(gòu)關(guān)系是等價關(guān)系。131定理5-8.2設(shè)f是從代數(shù)系統(tǒng)<A，★>到代數(shù)系統(tǒng)<B，*>的同態(tài)映射。

(a)如果<A，★>是半群，那么在f作用下，同態(tài)

象<f(A)，*>也是半群。

(b)如果<A，★>是獨異點，那么在f作用下，同態(tài)象<f(A)，*>也是獨異點。

(c)如果<A，★>是群，那么在f作用下，同態(tài)象<f(A)，*>也是群。

132證明：設(shè)<A，★>是半群且<B，*>是一個代數(shù)系統(tǒng)，如果f是由<A，★>到<B，*>的一個同態(tài)映射，則f(A)?B。對于任意的a，b∈f(A)，必有x，y∈A，使得：

f(x)＝a，f(y)＝b在A中，必有z＝x★y；所以，a*b＝f(x)*f(y)＝f(x★y)＝f(z)∈f(A)(a)133*在f(A)上是可結(jié)合的。因為：對于任意的a，b，c∈f(A)，必有x，y，z∈A，使得：

f(x)＝a，f(y)＝b，f(z)＝c因為★在A上是可結(jié)合的；所以，a*(b*c)＝f(x)*(f(y)*f(z))＝f(x)*f(y★z)＝f(x★(y★z))