離散數(shù)學(xué)半群和獨(dú)異點(diǎn)、群與子群課件

1、第二講 半群、群和子群定義 一個(gè)代數(shù)系統(tǒng)，其中S是非空集合，*是S上的 一個(gè)二元運(yùn)算，如果運(yùn)算*是封閉的，則稱代數(shù)系統(tǒng) 為廣群。一. 廣群二. 半群定義 一個(gè)代數(shù)系統(tǒng)，其中S是非空集合，*是S上的 一個(gè)二元運(yùn)算，如果 1）運(yùn)算*是封閉的。 2）運(yùn)算*是可結(jié)合的，即對(duì)任意的x,y,zS，滿足 (x * y) * z = x * (y * z) 則稱代數(shù)系統(tǒng) 為半群。例設(shè)集合Sk=x|x I xk，k0，那么是一個(gè)半群?jiǎn)?？（其?是普通加法運(yùn)算）分析 因?yàn)榧臃ㄟ\(yùn)算在Sk上是封閉的，并且該運(yùn)算可結(jié)合， 所以是一個(gè)半群。注意 若k0，則運(yùn)算+在Sk上是不封閉的。？ 代數(shù)系統(tǒng)是半群?jiǎn)?？呢？定理設(shè)是一個(gè)半

2、群，B S且*在B上是封閉的，那末也是一個(gè)半群。通常稱是半群的子半群。證明 因?yàn)?在S上是可結(jié)合的，而B S 所以*在B上也是可結(jié)合的，又*在B上是封閉的，因此， 也是一個(gè)半群。例 代數(shù)系統(tǒng)，都是的 子半群。定理設(shè)是一個(gè)半群，如果S是一個(gè)有限集，則必有aS，使得a*a=a。證明 因?yàn)槭且粋€(gè)半群。對(duì)于bS ，由*的封閉性可知 b*bS，記b2=b*b b2*b=b*b2S，記b3=b2*b=b*b2 由于S是有限集，所以必存在 ji，使得bi=bj 令p=ji，有bi=bp*bi，所以對(duì)qi，有bq=bp*bq 因?yàn)閜1，所以總可以找到k1，使得kpi 就有bkp= bp*bkp = bp*(b

3、p*bkp) = b2p*bkp = b2p*(bp*bkp) = = bkp*bkp 這就證明了在S中存在元素a= bkp，使得a*a=a.獨(dú)異點(diǎn)定義 含有幺元的半群稱為獨(dú)異點(diǎn)。例 代數(shù)系統(tǒng)是一個(gè)獨(dú)異點(diǎn)。因?yàn)槭前肴?，?是 R中關(guān)于運(yùn)算+的幺元。 代數(shù)系統(tǒng) 都是獨(dú)異點(diǎn)，幺元為1。定理 設(shè)是一個(gè)獨(dú)異點(diǎn)，則在關(guān)于運(yùn)算*的運(yùn)算表中任何 兩行或兩列都是不相同的。證明 設(shè)S中關(guān)于運(yùn)算*的幺元是e。因?yàn)閍,bS且ab，總有 e*a=ab=e*b 和 a*e=ab=b*e 所以，在*的運(yùn)算表中任何兩行或兩列都是不相同的。定理設(shè)是獨(dú)異點(diǎn)，對(duì)于任意a,bS,且a,b均有逆元，則(a-1)-1=aa * b有逆

4、元，且(a * b)-1=b-1 * a-1證明 1) 因?yàn)閍-1是a 的逆元，即 a*a-1=a-1 * a=e 所以， (a-1)-1=a 2) 因?yàn)?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群定義 設(shè)一個(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。 則稱代數(shù)系統(tǒng) 為群。群 獨(dú)異

5、點(diǎn) 半群 廣群有限群定義 設(shè)是一個(gè)群。如果G是有限集，那末稱為 有限群，G中元素的個(gè)數(shù)通常稱為該有限群的階數(shù)，記 為|G|；如果G是無限集，則稱為無限群。例 ，都是群?？疾烊缦麓鷶?shù)系統(tǒng)是否構(gòu)成群，？定理群中不可能有零元。證明 當(dāng)群的階為1時(shí)，它的唯一元素視為幺元。 設(shè)|G|1且群有零元 。那么群中任何元素xG， 都有x*= *x= e，所以，零元就不存在逆元，這與 是群相矛盾。定理 設(shè)是一個(gè)群，對(duì)于a,bG,必存在唯一的xG, 使得a*x=b.證明 1）存在 2）唯一設(shè)a的逆元是a-1,令 x =a-1*b則a*x=a*(a-1*b) =(a*a-1)*b =e*b =b若另有一x1,滿足a*

6、x1=b則 a-1*(a*x1)=a-1*b即x1=a-1*b定理設(shè)是一個(gè)群，對(duì)于任意的a,b,cG，如果有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時(shí)，可同樣證得b=c。定義設(shè)S是一個(gè)非空集合，從集合S到S的一個(gè)雙射稱為S的一個(gè)置換。定理群的運(yùn)算表中的每一行或每一列都是G的元素的一個(gè)置換。證明見書193等冪元證明 因?yàn)閑 * e=e，所以e是

7、等冪元。 假設(shè)存在aA,ae且a * a=a 則有 a=e * a=(a-1 * a) * a=a-1 *(a * a)=a-1 * a=e 與假設(shè)a e相矛盾。定義 代數(shù)系統(tǒng)中，如果存在aG，有a * a=a， 則稱a為等冪元。定理 在群中，除幺元e外，不可能有任何別的等冪元。子群定義 設(shè)是一個(gè)群，S是G的非空子集，如果也 構(gòu)成群，則稱 是的一個(gè)子群。定理 設(shè)是一個(gè)群， 是的一個(gè)子群，那末， 中的幺元 e 必定也是中的幺元。證明 設(shè)中的幺元為e1，對(duì)于任一xS G，必有 e1*x=x=e*x 故，e1=e。 ( 為群，滿足消去律)平凡子群 定義 設(shè)是一個(gè)群， 是的子群，如果 S=e，或者S=

8、G，則稱是的平凡子群。例 是一個(gè)群，設(shè)IE=x|x=2n,nI，證明是 的一個(gè)子群。分析 1）+在IE上封閉。 2）+在IE上可結(jié)合。 3） 有幺元。 4） IE中的每個(gè)元素都有逆元。定理設(shè)是一個(gè)群，B是G的非空子集，如果B是一個(gè)有限集，那末只要運(yùn)算*在B上封閉，必定是的子群。證明 設(shè)e是 中么元，b是B中的任一個(gè)元素。若*在B上 封閉，則元素b2=b*b,b3=b2*b,都在B中。 由于B是有限集，所以必存在正整數(shù)i和j，不妨假設(shè) ij，使得bi=bj，即bi=bi*bj-i。這就說明bj-i是 中的幺元(bi=bi*bj-i = bi * e)，且這個(gè)幺元也在子集B中。 如果j-i1，那末由bj-i=b*bj-i-1可知bj-i-1是b的逆元， 且bj-i-1 B；如果j-i=1，那末由bi=bi*b可知b就是 幺元，而幺元是以自身為逆元的。 因此，是的一個(gè)子群。當(dāng)B不是有限集則結(jié)論不成立：為群，而不為群，雖然在自然數(shù)上是封閉的。定理設(shè)是群，S是G的非空子集，如果對(duì)于S中的任意元素a和b有a*b-1S，則是的子群。證明 1）證明G中的幺元e也是S中的幺元。 任取S中的元素aS G，所以a*a-1 = e S且a*e=e*a =a,即e也是S中的幺元。 2）證明S中的每一個(gè)元