离散数学群与子群

离散数学群与子群一、群得概念群与子群就是一种特殊得独异点,也就是一种特殊得半群。

定义5-4、1

设<G,

>就是一个代数系统,其中G就是非空集合,

就是G上一个二元运算,如果 ⑴运算

就是封闭得。 ⑵运算

就是可结合得。 ⑶存在么元e。 ⑷对于每一元素x∈G,存在着她得逆元x-1。则称<G,

>就是一个群(group)。例如:1、〈Q,+〉,〈Z,+〉,〈R,+〉为群,逆元-x2、〈R-{0},*〉,〈P(S),

〉都为群。3、〈N,+〉并不就是群。4、〈Zn,+n〉为群,元素逆元:

x=0,x–1=0;

x

0,x–1=n-xP191例题1;设R={0°,60°,120°,180°,240°,300°}表示在平面上几何图形绕形心顺时针旋转角度得六种可能情况,设★就是R上得二元运算,对于R中任意两个元素a和b,a★b表示平面图形连续旋转a和b得到得总旋转角度。并规定旋转360°等于原来得状态,就看作没有经过旋转。验证<R,★>就是一个群。解:由题意,R上得二元运算★得运算表如上所示,由表知,运算★在R上就是封闭得。对于任意a,b,c

R,(a★b)★c表示将图形依次旋转a,b和c,而a★(b★c)表示将图形依次旋转b,c和a,而总得旋转角度都就是a+b+c(mod360),因此(a★b)★c=a★(b★c),即★运算满足结合性。0o就是幺元。60o,120o,180o逆元分别就是300o,240o,180o因此<R,★>就是个群例:G={a,b,c,e},*如上表所示,就是不就是一个群？易见1)*运算对G就是封闭得,e为幺元。2)可以验证,*运算可结合得。(在a,b,c三个元素中,任何两个元素运算得结果都等于另一个元素,)3)G中任何元素得逆元就就是她自己;

。故〈G,*〉为一个群。此外,运算

就是可交换得,一般称这个群为克莱因(Klein)四元群,简称四元群。思考练习已知:在整数集I上得二元运算

定义为:a,b∈I,a

b=a+b-2

证明:<I,

>为群。么元为:2逆元:x-1＝4-x二、有限群和无限群

定义5-4、2

设<G,

>就是一群。如果G就是有限集,那么称<G,

>为有限群,G中元素得个数通常称为该有限群得阶数,记为|G|;如果G就是无限集,则称<G,

>为无限群。例题1中所述得<R,★>就就是一个有限群,且|R|=6。代数系统<I,+>就是一个无限群,这里I就是所有整数得集合,+就是普通加法运算。<I,+>,<Q,+>,<R,+>就是无限群。<Nk,＋k>就是有限群,就是k阶群。克莱因Klein四元群就是4阶有限群。只含单位元得群称为平凡群。<{0},+>就是平凡群。就是1阶群。代数系统小结:至此,我们可以概括地说:广群仅仅就是一个具有封闭二元运算得非空集合;半群就是一个具有结合运算得广群;独异点就是具有幺元得半群;群就是每个元素都有逆元得独异点。

<G,

>封闭性广群结合性半群含幺元独异点存在逆元群广群半群独异点群群得基本性质由于群得运算可结合,故对任何一个元a,其逆元都就是唯一得,记a-1。

(a-1=a-1*e=a-1*(a*(a-1)’)=(a-1*a)*(a-1)’=(a-1)’)定理5-4、1

群中不可能有零元。证明:当群得阶为1时,她得唯一元素就是视作幺元。设|G|>1且群<G,

>有零元

。那么群中任何元素x

G,都有

x

＝

x

＝

≠e,所以,零元

就不存在逆元,这与<G,

>就是群相矛盾。群中无零元！因为零元无逆元。定理5-4、2设<G,

>就是一个群,对于a,bG,必存在唯一x

G

,使得a

x

＝b。证明:⑴先证解得存在性

设a得逆元就是a-1,令

x

＝a-1

b

(构造一个解)

a

x

＝a

(a-1

b

)

＝(a

a-1

)

b

＝e

b

＝

b⑵再证解得唯一性若另有一解x

1满足a

x

1

＝b

,则

a-1

(a

x

1)＝a-1

b

x

1＝a-1

b群方程存在唯一解定理5-4、3设<G,

>就是一个群,对于任意a,b,c

G,如果a

b=a

c

或者b

a=c

a,则必有b=c(消去律)。证明:设a

b＝a

c,且a得逆元a-1,则有

a-1

(a

b

)＝a-1

(a

c

)(a-1

a)

b

＝(a-1

a)

ce

b

＝

e

c

b

＝c

当b

a=c

a时,可同样证得b=c

。大家有疑问的，可以询问和交流可以互相讨论下，但要小声点三、置换为进一步讨论群性质,引入置换得概念。定义5-4、3

设S为一个非空集合,从集合S到S得一个双射称为S得一个置换。例:集合S={a,b,c,d}置换为a

b,b

d,c

a,d

c

这就是一个从S到S上得一对一映射,可表示为:

abcdbdac定理5、4、4群〈G,*〉得运算表中任一行(列)得元素都就是G中元素得一个置换。且不同行,不同列得置换都不同。证明首先,证明运算表中得任一行或任一列所含G中得一个元素不可能多于一次。用反证法,如果对应于元素a∈G得那一行中有两个元素都就是c,即有a*b1=a*b2=c且b1≠b2由可约性可得b1=b2,这与b1≠b2矛盾。其次,要证明G中得每一个元素都在运算表得每一行和每一列中出现。考察对应于元素a∈G得那一行,设b就是G中得任一元素,由于b=a*(a-1*b),所以b必定出现在对应于a得那一行中。再由运算表中没有两行(或两列)相同得事实,便可得出:<G,*>得运算表中每一行都就是G得元素得一个置换,且每一行都就是不相同得。同样得结论对于列也就是成立得。四、等幂元

定义5-4、4代数结构<G,

>中,如果存在a

G,有a

a=a

,则称a为等幂元。定理5-4、5

在群<G,

>中,除幺元e之外,不可能有任何别得等幂元。证明:因为e

e=e

,所以e就是等幂元。现设a

G,a≠e

且a

a=a

则有

a=e

a=(a

-1

a)

a=a

-1(a

a)=a

-1

a=e

与假设a≠e

且矛盾。五、子群定义5-4、5设<G,*>就是一个群,S就是G得非空子集,如果<S,*>也构成群,则称<S,*>就是<G,*>得一个子群。例:〈Z,+〉为群,取S={2z

z

Z},则〈Ｓ,＋〉为子群。〈｛０｝,＋〉也为〈Z,+〉得子群、例:Klein四元群{e},{e,a},{e,b},{e,c},G都为子群。

定理5-4、6设<G,*>就是一个群,<S,*>就是<G,*>得一个子群,那么,<G,*>中得幺元e必定也就是<S,*>中得幺元。证明:设<G,*>中得幺元为e1

对于任一x∈S

G,必有

e1*x=x=e*x,

故e1=e。五、子群定义5-4、6

设<G,*>就是一个群,<S,*>就是<G,*>得子群,如果S={e},或者S=G,则称<S,*>为<G,*>得平凡子群定理5-4、7〈G,*〉为一个群,B为G得非空子集且B为有限集,则只须*在B上封闭,〈B,*〉就就是〈G,*〉得一个子群。证明:设b就是B得任一个元素。若*在B上封闭,则元素b2=b*b,b3=b2*b,…都在B中。由于B就是有限集,所以必存在正整数i和j,不妨假设i<j,使得