離散第講半群和群的定義和性質(zhì)

離散第講半群和群的定義和性質(zhì)第1頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/142半群定義10.1(1)：<S,*>是一個(gè)代數(shù)系統(tǒng)，其中S是非空集合，*是S上的一個(gè)二元運(yùn)算(運(yùn)算*是封閉的)，如果運(yùn)算*是可結(jié)合的，即對(duì)任意的x,y,z∈S，

滿(mǎn)足(x*y)*z=x*(y*z)則稱(chēng)代數(shù)系統(tǒng)<S,*>為半群。第2頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/143例10.1Sk={x|x∈Z∧x≥k}，<Sk,+>為半群

<Z+,->，<R,/>不是半群

第3頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/144例10.2Σ={a,b}，Σ+為所有由a,b組成的字符串,”·”為字符串的連接運(yùn)算.則<Σ+,·>做成半群。第4頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/145獨(dú)異點(diǎn)定義10.1(2)：設(shè)<S,*>是一個(gè)半群，若存在eS為S中關(guān)于運(yùn)算*的單位元,則稱(chēng)<S,*>為幺半群，也叫做獨(dú)異點(diǎn)。(有時(shí)也把單位元標(biāo)明<S,*,e>)第5頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/146例10.1Sk={x|x∈Z∧x≥k}，<Sk,+>(k>0)？<S0,+>？

不是獨(dú)異點(diǎn)是獨(dú)異點(diǎn)第6頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/147例10.2Σ={a,b}，Σ+為所有由a,b組成的字符串,”·”為字符串的連接運(yùn)算.思考：半群<Σ+,·>是否做成獨(dú)異點(diǎn)？空串Σ*=Σ+{}<Σ*,·>做成獨(dú)異點(diǎn)第7頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/148例10.3冪集<P(B),>？<P(B),>？

<P(B),>？第8頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/14910.4*αβγδζααβγδζββγδζαγγδζαβδδζαβγζζαβγδ是單位元可結(jié)合性在運(yùn)算表中無(wú)特殊體現(xiàn)第9頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1410群(Group)定義10.1（3）：設(shè)<G,*>是一個(gè)代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個(gè)二元運(yùn)算，如果(1).運(yùn)算*是封閉的(2).運(yùn)算*是可結(jié)合的(3).存在單位元e(4).對(duì)于每一個(gè)元素x∈G，存在著它的逆元x-1則稱(chēng)<G,*>是一個(gè)群第10頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1411例10.1Sk={x|x∈Z∧x≥k}，<Sk,+>(k>0)？<S0,+>？

不是群不是群<Z,+>是群第11頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1412例10.2Σ={a,b}，Σ+為所有由a,b組成的字符串,”·”為字符串的連接運(yùn)算.空串Σ*=Σ+{}<Σ*,·>思考：獨(dú)異點(diǎn)<Σ*,·>是否做成群？第12頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1413例10.3冪集<P(B),>？<P(B),>？

<P(B),>？單位元和逆元?第13頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1414例10.4(1-2)(1)

<Z,+>整數(shù)加群(2)<Zn,+n>模n整數(shù)加群思考:<Zn,n>是不是群?第14頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1415例10.4(3-6)(3)

<Mn(R),+>n階實(shí)矩陣加群(4)

<Mn(R),>n階實(shí)可逆矩陣乘法群；(5)所有行列式為1的n階實(shí)可逆矩陣關(guān)于矩陣乘法；(6)集合A={1,2,3}上所有的雙射函數(shù)構(gòu)成集合S3,則關(guān)于映射的復(fù)合作成群.第15頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1416例10.5Klein四元群G={e,a,b,c}eabceeabcaaecbbbceaccbae第16頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1417例10.5(2)Klein四元群G={e,a,b,c}e=(0,0)a=(0,1)b=(1,0)c=(1,1)運(yùn)算o為逐分量模2加法,第17頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1418群的等價(jià)定義定理

(等價(jià)定義)<G,°>,°可結(jié)合，若存在右單位元e，且每個(gè)元素a相對(duì)于e存在右逆元a’，則G是群.證明:封閉性可結(jié)合性單位元？逆元？第18頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1419群的等價(jià)定義定理

(等價(jià)定義)<G,°>,°可結(jié)合，若存在右單位元e，且每個(gè)元素a相對(duì)于e存在右逆元a'，則G是群.證明:證e為左單位元.?a∈G,（要證ea=a）

ee=e(e為右單位元)?e(aa')=(aa')?(ea)a'=aa'?ea=a(右乘a'的右逆元)證a'為a的左逆元，設(shè)a'a''=ea''=ea''=(aa')a''=a(a'a'')=ae=a第19頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1420群的性質(zhì)（一元一次方程有解）性質(zhì)1：設(shè)<G,*>是一個(gè)群，任給a,b∈G，必存在唯一的x∈G，使得a*x=b；必存在唯一的x∈G，s.t.

y*a=b.證a-1b是ax=b的解.假設(shè)c為解，則c=ec=(a-1a)c=a-1(ac)=a-1b第20頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1421群的等價(jià)定義2定義：設(shè)<G,*>是一個(gè)半群，a,b∈G，方程a*x=b和y*a=b在G中有解，則G是群。證找右單位元和任意元素的右逆元.任取b∈G,方程bx=b的解記為e.?a∈G,yb=a的解記為c,即cb=a.ae=(cb)e=c(be)=cb=ae為右單位元.?a∈G,方程ax=e有解，得到a的右逆元第21頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1422群的相關(guān)術(shù)語(yǔ)平凡群只含單位元的群{e}有限群與無(wú)限群群G

的階

G的基數(shù)，通常有限群記為|G|交換群或阿貝爾（Abel）群第22頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1423例10.6（交換群）(1)

<Z,+>無(wú)限群;(2)<Z6,+6>模6整數(shù)加群，階為6(3)<Z4,+4>模4整數(shù)加群，階為4(4)Klein四元群G={e,a,b,c}，階為4(5)<P(B),>群，階為|P(B)|第23頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1424元素的冪運(yùn)算定義設(shè)<S,*>是一個(gè)半群，xS,nZ+,定義的x

的n次冪xn為:推廣到獨(dú)異點(diǎn)第24頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1425元素的冪運(yùn)算（推廣到群）定義10.3設(shè)<G,*>是一個(gè)群，xG,n

Z,定義的x

的n次冪xn為:第25頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1426元素的階定義10.4設(shè)G是群，

aG，元素a的階

|a|：使得ak=e成立的最小正整數(shù)k。記作|a|=k,也稱(chēng)a為k階元。與群的階比較有限群的元素都是有限階，比群的階小（為群的階的因子?。。。辉囟际怯邢揠A的群不一定是有限群.第26頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1427例10.6（元素的階）(1)

<Z,+>無(wú)限群，|0|=1(2)<Z6,+6>模6整數(shù)加群，元素的階(3)<Z4,+4>模4整數(shù)加群，元素的階(4)Klein四元群G={e,a,b,c}(5)<P(B),>群中元素的階第27頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1428冪運(yùn)算的性質(zhì)定理10.1冪運(yùn)算規(guī)則

(a-1)-1=a(ab)-1=b-1a-1

anam=an+m(an)m=anm

若G為Abel群，則(ab)n=anbn說(shuō)明：等式1和2證明用到逆元定義和唯一性等式3和4的證明使用歸納法并加以討論等式2可以推廣到有限個(gè)元素之積.第28頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1429群的性質(zhì)（消去律）定理10.2：設(shè)<G,*>是一個(gè)群，對(duì)于任意的a,b,c∈G，如果有a*b=a*c或者b*a=c*a，則必有b=c(消去律)。第29頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1430群的等價(jià)定義定義:滿(mǎn)足(1),(2)及消去律且不含零元的有限代數(shù)系統(tǒng)是群，即滿(mǎn)足消去律且不含零元的有限半群做成群。(1).運(yùn)算*是封閉的(2).運(yùn)算*是可結(jié)合的aG={ag|g∈G}

=G第30頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1431冪等元定義：代數(shù)系統(tǒng)<G,*>中，如果存在a∈G，有a*a=a，則稱(chēng)a為冪等元。第31頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1432有限半群必存在冪等元性質(zhì)：設(shè)<S,*>是一個(gè)半群，如果S是一個(gè)有限集，則必有a∈S，使得a*a=a.思路：(構(gòu)造法)

b∈S，由S對(duì)*封閉及S有限，則對(duì)序列b，b2，b3，…，

bn，…必定存在j>i，s.t.bi=bj，令p=j-i≥1，有bj=bp*bi，即bi=bp*bi.第32頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1433泵原理b0b1b2b3b4b5=b19=b33=…b6=b20=b34=…b7=b21=b35=…b8=b22=b36=…b15b9b10b11b14b16b17第33頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1434冪等元構(gòu)造bi=bp*bi.bi=bkp*bibq=bkp*bq,其中

q=kp*b*b*…*b*b*b*…*bbi=bp*bi=bp*（bp*bi）

=……=bp*……*bp*（bp*bi）bi=bkp*bi,可找到k使得kp≥i設(shè)a=bkp，則a*a=a第34頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1435證明性質(zhì)：設(shè)<S,*>是一個(gè)半群，如果S是一個(gè)有限集，則必有a∈S，使得a*a=a.證明：(構(gòu)造法)

b∈S，由S對(duì)*封閉及S有限，則對(duì)序列b，b2，b3，…，

bn，…必定存在j>i，s.t.bi=bj，令p=j-i≥1，有bj=bp*bi，即bi=bp*bi，且可知對(duì)任給的q≥i有bq=bp*bq。因?yàn)閜≥1，所以總可找到k≥1，s.t.

kp≥i。因此對(duì)于S中的元素bkp，有bkp＝bp*bkp＝bp*(bp*bkp)＝...=bkp*bkp.設(shè)a=bkp，則a∈S，且a*a=a第35頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1436群中元素的性質(zhì)定理10.3G為群，a∈G,且|a|=r,則(1)ak=e?r|k(2)|a|=|a-1|(3)若|G|=n,則r≤n.證(1)充分性.ak

=arl

=(ar)l=el

=e必要性.k=rl+i,l∈Z,i∈{0,1,…,r-1}?e=ak

=arl+i

=ai

?i=0?r|k(2)(a-1)r=e?|a-1|存在,令|a-1|=t,則t|r.同理r|t.(3)假設(shè)r>n,令G’={e,a,a2,…,ar-1},則G’中元素兩兩不同，否則與|a|=r矛盾.從而|G’|>n，與G’?G矛盾.第36頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1437群中冪等元唯一例：在群<G,*>中，除單位元e外，不可能有任何別的冪等元(即a*a=a)證：e*e=e，∴e為冪等元

現(xiàn)設(shè)a∈G，a≠e且a*a=a則有a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e第37頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1438元素的階的性質(zhì)（1）例：G為群，a∈G，|a|=r,證明|at|=r/(t,r)證：令|at|=s,設(shè)(t,r)=d,t=dp,r=dq,r/(t,r)=r/d=q只要證s=q(at)q

=(at)r/d

=(ar)t/d=ep

=e

s|q(at)s=e?ats=e?r|ts?q|psq|s（p,q互素）第38頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1439元素的階的性質(zhì)（2）例10.7:G為有限群，則G中階大于2的元素有偶數(shù)個(gè)。證：a2=ea2=a-1a

a=a-1，所以階大于2的元素必有a

a-1，且成對(duì)出現(xiàn)。第39頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1440元素乘積的階例:G為群，a,b∈G且可交換，|a|=m,|b|=n，若(m,n)=1,則|ab|=mn.證：設(shè)|ab|=r1)(ab)mn=e?r|mn2)e

=((ab)r)m=(ab)mr=(am)r(bmr)=bmr

?n|mr?n|r,

同理m|r,?mn|r第40頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1441元素乘積的階（2）例10.6:G為群，a,b∈G是有限階元，則：

(1)|b-1ab|=|a|(2)|ab|=|ba|證：(1)|設(shè)|a|=r,|b-1ab|=t

，則1)(b-1ab)r=(b-1ab)

(b-1ab)……(b-1ab)=

b-1arb=b-1eb=e,所以t|r,同理r|t2）

ab=b-1(bab)第41頁(yè)，共49頁(yè)，2023年，2月20日，星期一補(bǔ)充材料模n剩余類(lèi)第42頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1443模n剩余類(lèi)設(shè)Z是整數(shù)集合，n是任意正整數(shù)，Zn是由模n的同余（剩余）類(lèi)組成的集合，在Zn上定義兩個(gè)二元運(yùn)算+m和m:[i],[j]Zn[i]+m[j]=[(i+j)modm][i]m[j]=[(ij)modm]eg.

<Zn,+n>，<Zn,n>

(令n為素?cái)?shù)和不為素?cái)?shù)兩種)第43頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1444整數(shù)同余式定義（同余）：稱(chēng)整數(shù)a模正整數(shù)m同余于整數(shù)b，記為a≡b（modm）是指m|a-b,m稱(chēng)為模數(shù)。

m|a-ba=q1m+r且b=q2m+r，即a和b分別除以m有相同的余數(shù)。“同余”二字的來(lái)源就在于此。第44頁(yè)，共49頁(yè)，2023年，2月20日，星期一2023/4/1445同余關(guān)系相對(duì)于某個(gè)固定模數(shù)m的同余關(guān)系，是整數(shù)間的一種等價(jià)關(guān)系。具有等價(jià)關(guān)系的三點(diǎn)基本性質(zhì)：

自反性：對(duì)任意整數(shù)