離散數(shù)學(xué)：半群與含幺半群（獨異點）

1主要內(nèi)容代數(shù)系統(tǒng)的基本概念1半群與含幺半群（獨異點）2群（阿貝爾群與循環(huán)群）3陪集與拉格朗日定理4同態(tài)與同構(gòu)5環(huán)與域62定義1：<S,*>是一個代數(shù)系統(tǒng)，S為非空集合，*是定義在S上的二元運算：*是封閉的，<S,*>稱為廣群；*可結(jié)合的廣群稱為半群；含有幺元的半群，稱為獨異點（含幺半群）；*可交換的半群，稱為交換半群。例：

<R,->是代數(shù)系統(tǒng)，是否是半群？ 因為-在R上封閉，但不可結(jié)合；不是半群！

<R,?>是半群，而且含有幺元1

所以也是獨異點，是可交換的獨異點。3定理1：<S,*>是半群，BS，且*在B上封閉，則<B,*>是半群。通常稱<B,*>是<S,*>的子半群。證明：要證明<B,*>是半群，只要證*在B上封閉、可結(jié)合 已知*在B上封閉∵<S,*>是半群，BS， ∴a,b,cB，a,b,cS，

*在S上可結(jié)合，有a*(b*c)=(a*b)*c，即*在B上可結(jié)合 ∴<B,*>是半群例：

<R,?>是半群，<{2,4},?}是否是半群？<(0,1),?>是否是半群？∵區(qū)間(0,1)R，且?在(0,1)上封閉可結(jié)合， ∴<(0,1),?>是<R,?>的子半群4定理2：<S,*>是半群，若S是有限集,則必有aS，使a*a=a。證明：對bS∵<S,*>是半群，*在S上封閉，∴b*bS

記b2=b*b，則b2*b=(b*b)*b=b*(b*b)=b*b2

記b3=b2*b=b*b2

則b3*b=b2*b*b=b*((b*b)*b)=b*(b2*b)=b*b3……記bn=bn-1*b=b*bn-1……∵S是有限集，∴根據(jù)鴿巢原理，存在j>i，使得bi=bj

記p=j-i(則p≥1)，則j=p+i∴bi=bj=bp+i=bp*bi，∴bi

*b=bp*bi

*b∴bi+1=bp*bi+1，bi+2=bp*bi+1

*b=bp*bi+2…br=bp*br(r≥i)∵p≥1，∴總可以找到k≥1使得kp≥i∴bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp

=b2p*(bp*bkp)=b3p*bkp=…=bkp*bkp∵*在S上封閉，∴bkpS，

令a=bkp，則a*a=a5定理3：<S,*>是獨異點，則在關(guān)于*的運算表中，任何兩行或兩列都是不同的。證明：令e是<S,*>的幺元，則a，bS，且a≠b， ∵e*a=a≠b=e*b，∴任意兩列在e這一行中不同 ∵a*e=a≠b=b*e，∴任意兩行在e這一列中不同*……e……a……b…...e……e……a……b…...a……a……………...b……b……………...6定理4：<S,*>是獨異點，a，bS，且都有逆元，則

(1)(a-1)-1=a；

(2)a*b有逆元，且(a*b)-1=b-1*a-1。證明：令e是<S,*>的幺元，(1)∵

a-1*a=e=a*a-1

，∴a-1與a互為逆元， ∴(a-1)-1=a(2)∵(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)=b-1*(a-1*a)*b =b*e*b-1=b*b-1=e ∴(a*b)-1=b-1*a-17例1：<{a,b},*>是半群，其中a*a=b，求證：

(1)a*b=b*a；(2)b*b=b。證明：(1)a*b=a*(a*a)=(a*a)*a=b*a(2)b*b=b*(a*a)=(b*a)*a ∵<{a,b},*>是半群，∴*在{a,b}上封閉， ∴b*a=a或者b*a=b

若b*a=a，則b*b=(b*a)*a=a*a=b

若b*a=b，則b*b=(b*a)*a=b*a=b證法2：(2)∵<{a,b},*>是半群，{a,b}是有限集，∴必有一個元素x{a,b}，使x*x=x∵a*a=b≠a，∴x≠a∴x=b，即元素b必滿足b*b=b8作業(yè)P190（5）9主要內(nèi)容代數(shù)系統(tǒng)的基本概念1半群與含幺半群（獨異點）2群（阿貝爾群與循環(huán)群）3子群與陪集4同態(tài)與同構(gòu)5環(huán)與域610定義1：每個元素都有逆元的獨異點，稱為群。定義2：若群還滿足交換律，則稱為交換群（阿貝爾群）。定義3：<G,*>是群，若G是有限集，稱<G,*>是有限群；

G中元素的個數(shù)稱為該有限群的階數(shù)，記為|G|；

若G無限，則<G,*>稱為無限群。定義4：<G,*>是群，a是G中任意元素，nN，定義元素a的冪為：

a0=e，a1=a，……，

an+1=an*a，

定義：a-n=(a-1)n(其中a-1是a的逆元)

顯然，am*ak=am+k，(am)k=amk（m,kI）1.群的概念11定義5：<G,*>是群，a是G中任意元素，若存在nZ+，使an=e，則稱元素a的階是有限的，最小的正整數(shù)n稱為元素a的階；

若不存在這樣的正整數(shù)n，則稱元素a具有無限階。解：e1=e，∴e的階是1 a2=a*a=b，

a3=a2*a=b*a=e ∴a的階是3

同理，b的階也是3 a3k=e*eabeabeababbeea例：12例1：判斷<I,?>，<R,+>，<P(S),∪>，<P(S),∩>，<P(S),>

是否是群？解：<I,?>，幺元是1，只有幺元有逆元，其它元素沒逆元，

∴不是群；<R,+>，幺元是0，x+(-x)=0，每個元素都有逆元，

∴是群<P(S),∪>，幺元是?；<P(S),∩>，幺元是S；

都不是群，因為不是每個元素都有逆元。<P(S),>是群，∵?A=A=A?∴?是幺元 AP(S)，有AA=?∴A-1=A， 每個元素都有逆元證明：m=4時，運算表：+4[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]封閉、可結(jié)合、有幺元[0]、每個元素都有逆元

[0]-1=[0]x≠0時，[x]-1=[4-x]∴<Z4,+4>是群，階數(shù)是4例、集合Zm是模m的同余類組成的同余類集，即

Zm={[0],[1],[2],…,[m-1]},

[i]Zm，[j]Zm,定義運算

[i]+m[j]=[(i+j)modm][i]×m[j]=[(i×j)modm]

判斷當(dāng)m=4時代數(shù)系統(tǒng)<Zm,+m>,<Zm,×m>是否為群？若m=4，則：Z4={[0],[1],[2],[3]}其中[0]={…-8,-4,0,4,8…}[1]={…-7,-3,1,5,9…}[2]={…-6,-2,2,6,10…}[3]={…-5,-1,3,7,11…}14小結(jié)：

{群}{獨異點}{半群}{廣群}{代數(shù)系統(tǒng)}

半群在廣群基礎(chǔ)上還要求運算可結(jié)合； 獨異點在半群基礎(chǔ)上要求存在幺元； 群在獨異點基礎(chǔ)上要求每個元素都有逆元?！?[0][1][2][3][0][0][0][0][0][1][0][1][2][3][2][0][2][0][2][3][0][3][2][1]

封閉、可結(jié)合、 有幺元[1]、 但元素[0]、[2]沒有逆元 ∴<Z4,×4>不是群152.群的性質(zhì)1)群中無零元。若|G|=1，規(guī)定G的唯一元素就是幺元，∴無零元；證明：設(shè)<G,*>是群，若|G|>1，假設(shè)<G,*>有幺元e和零元，則≠e xG，x*=*x=≠e∴無逆元 這與<G,*>是群相矛盾，

∴<G,*>中無零元162)<G,*>是群，a,bG，必存在唯一的xG，使得a*x=b證明：

aG，設(shè)a的逆元為a-1 ∵<G,*>是群，∴*在G上是封閉的，∴

a-1*bG

令x=a-1*b，則a*(a-1*b)=(a*a-1)*b=e*b=b

∴

存在x，使得a*x=b

設(shè)另有x1G，使得a*x1=b，則有

x=a-1*b=a-1*(a*x1)=(a-1*a)*x1=

e*x1=x1

∴x=x1

∴

使a*x=b成立的x是唯一的。<{a,b,c,d},*>是群,幺元為b，c,dG存在唯一的xG,使得c*x=d，x=c-1*d=d*d=a*abcdabadcbabcdcdcabdcdba173)<G,*>是群，a,b,cG，若a*b=a*c或b*a=c*a，則b=c（消去律）證明略（兩邊同時與a-1進(jìn)行*運算即可）4)在群<G,*>中，只有幺元e是等冪元證明：∵e*e=e，∴

e是等冪元 設(shè)有另一個等冪元a，則a*a=a ∵e*a=a=a*a，由消去律，得a=e5)在有限群<G,*>中，每個元素都具有有限階，且階數(shù)至多是|G|。（證明略）18定義6：S是一個集合，從S到S的一個雙射，稱為S的一個置換。例：設(shè)S={a,b,c,d} f(a)=b,f(b)=c,f(c)=d,f(d)=a是S的一個置換

f(a)=d,f(b)=a,f(c)=b,f(d)=c是S的另一個置換 這兩個置換可表示為：abcdbcdadabcaacdf(a)=a,f(b)=a,f(c)=c,f(d)=d不是置換196)在群<G,*>的運算表中的每一行或每一列都是G的元素的一個置換。證明：(1)G中任一元素b，在G的每一行中必出現(xiàn) 對xG，由封閉性，得x-1*bG， ∵x*(x-1*b)=(x*x-1)*b=b ∴對x行，必定在x-1*b列上出現(xiàn)元素b ∴任一元素b在每一行中都會出現(xiàn)(2)G中每個元素在每行中只出現(xiàn)一次（反證法）

設(shè)cG，在對應(yīng)于a的那行中出現(xiàn)兩次， 則必有b1G，b2G，且b1≠b2，使得a*b1=a*b2=c， 由消去律，得b1=b2，產(chǎn)生矛盾，∴假設(shè)錯 由(1)(2)可知運算表的每一行都是G的一個置換， 同理，每一列也是G的一個置換。*eabeabeababbeea*ea(b1)c(b2)eaceacabceca20例3：構(gòu)造一個三階群解：設(shè)e是幺元，G={e,a,b}， 構(gòu)造三階群<G,*>的運算表如下：構(gòu)造方法：先寫出幺元對應(yīng)的行和列的運算結(jié)果

再按置換要求，填寫其他運算結(jié)果*eabeabeababbeea<G,*>是群,SG且S≠?,若<S,*>也構(gòu)成群,則稱<S,*>是<G,*>的子群。<G,*>是群,<S,*>是<G,*>的子群,若S={e}或S=G,則稱<S,*>是<G,*>的平凡子群。（e是幺元）子群證明略<S,*>是<G,*>的子群，則<G,*>中的幺元必是<S,*>的幺元。定理證明：（按照定義證明）

(1)x,yIE，x=2n1，y=2n2，x+y=2(n1+n2)，∵n1+n2I，∴x+yIE，∴<IE,+>封閉

(2)+在IE上的結(jié)合性是保持的；

(3)0IE，對x=2nIE，0+2n=2n+0=2n，即0+x=x+0=x，∴0是幺元；

(4)對x=2nIE，-x=-2n=2(-n)，-nI，∴-xIE，x+(-x)=(-x)+x=0，∴x-1=x，每個元素都有逆元；∴<IE,+>是群，又∵IEI，∴<IE,+>是<I,+>的子群。例：<I,+>是群,IE={x|x=2n,nI},證明<IE,+>是<I,+>的子群。(1)<B,*>的封閉性是已知的；

(2)<G,*>是群，∴*在G上可結(jié)合，∵BG且B≠?，∴*在B上也是可結(jié)合的；

(3)對bB，∵*在B上封閉，∴b*b=b2B，

b2*b=b3B，……，bnB∵B是有限集，∴存在正整數(shù)i>j，使bi=bjbi=bj=bi+j-i=bi*bj-i=bj-i*bi

設(shè)<G,*>的幺元為e，則e*bi=bi=bj-i*bi∴bj-i=e，∵bj-iB∴bj-i是<B,*>的幺元；<G,*>是群，BG且B≠?，若B是有限集，只要*在B上封閉，則<B,*>是<G,*>的子群。定理證明:(4)對bB，當(dāng)j-i=1時，b是<B,*>的幺元，b=b*b∴b-1=b

當(dāng)j-i>1時，bj-i

是<B,*>的幺元，

bj-i=b*bj-i-1=bj-i-1*b∴b-1=bj-i-1∴每個元素都有逆元，∴

<B,*>是群，是<G,*>的子群。*eabcdfe

eabcdfa

abedfcb

beafcdccfdebaddcfaebffdcbae<G={e,a,b,c,d,f},*>是群，且<B={e,a,b},*>是<G,*>的子群。B={e,a,b}G，且<B={e,a,b},*>封閉，所以，<B,*>是群，是<G,*>的子群。<B={e,a,b},*>和<G,*>共享同一個幺元。e-1=e，a-1

=b，b-1

=aa、b互為逆元?；仡櫍?lt;G,*>是群，BG且B≠?，若B是有限集，只要*在B上封閉，則<B,*>是<G,*>的子群。證明：(根據(jù)定義證明)(1)設(shè)e是<G,*>的幺元，對a,aS，由已知得：

a*a-1

S，即eS

，∵a

S，aG，∴a*e=e*a=a，

∴e是<S,*>的幺元；

(2)對aS，∵eS，∴由已知得e*a-1

S，即a-1S，

∴S中的任意元素都有逆元；

(3)對a,bS，由(2)知b-1S，由已知得a*(b-1)-1S

即a*bS，∴*在S上封閉；

(4)*在S上的可結(jié)合性是保持的；

∴<S,*>是群，又∵SG且S≠?，∴<S,*>是<G,*>的子群。定理<G,*>是群，SG且S≠?，若對a,bS，有a*b-1S

，則<S,*>是<G,*>的子群。證明：對a,bHK，即bH且bK，aH

且aK，因為<H,*>和<K,*>是子群：所以：

b-1

H

且b-1

K，即a*b-1

H，

a*b-1K，即a*b-1HK由定理得：<HK,*>是<G,*>的子群。例題設(shè)<H,*>和<K,*>都是群<G,*>的子群，試證明<HK,*>也是<G,*>的子群。<G,*>是群，SG且S≠?，若對a,bS，有a*b-1S

，則<S,*>是<G,*>的子群?！旖粨Q群與循環(huán)群若群<G,*>中的運算*是可交換的,則稱<G,*>是交換群(阿貝爾群)。例：<I,+>是交換群；判斷<Q,?>是不是交換群？不是，因為0沒有逆元，所以<Q,?>不是群，更不是交換群顯然：交換群的運算表是關(guān)于對角線對稱的。交換群*eabeabeababbeea三階群<G,*>的運算表如下，<G,*>為交換群證明：必要性設(shè)<G,*>是交換群，對任意的a,bG，有

a*b=b*a∴(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)<G,*>是群,則<G,*>是交換群的充要條件是:對G中任意元素a，b，有(a*b)*(a*b)=(a*a)*(b*b)。定理證明：充分性對任意的a,bG，有

(a*b)*(a*b)=(a*a)*(b*b)

∵a*(a*b)*b=(a*a)*(b*b)=(a*b)*(a*b)=a*(b*a)*ba*(a*b)*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,*>是交換群313.循環(huán)群定義7：<G,*>是群，若存在aG，使得G中任意元素都由a的冪組成，則稱<G,*>為循環(huán)群；元素a稱為它的生成元。例：令A(yù)={2i|iI}，則<A,?>是否循環(huán)群？是循環(huán)群，1是幺元，2是生成元，每個元素都有逆元例：<I,+>是循環(huán)群， ∵<I,+>是群，0是幺元，

10=0、11=1、12=1+1=2、

13=12+1=1+1+1=3、……、1n=n、…… 1-1=-1、1-2=(1-1)2=1-1+1-1=(-1)+(-1)=-2、……、

1-n=-n、…… ∴1是<I,+>的生成元32同時： ∵(-1)0=0、(-1)1=-1、(-1)2=(-1)+(-1)=-2、……、

(-1)n=-n、…… (-1)-1=1、(-1)-2=(-1-1)2