离散数学 复习 详细(子群,元素的周期,循环群,合同)

子群:

定义:

设(G,·)是一个群，H属于G,如果(H,·)仍是一个群，则(H,·)叫做(G,·)的子群。如果G的一个子群H不等于G，即H是G的真子集，则(H,·)叫做(G,·)的真子群

平凡子群和非平凡子群:

任意群都有两个子集一定是群 (平凡子群):{e} {G},其他的是非平凡子群

性质:

(1)G的子群H具有与G相同的运算。

(2)一般地，在群G中成立的运算律，在子群H中仍然成立。

(反过来未必:比如子群{1},有幂等律,但是原群未必就也有幂等律)

(3)群G一般都有两个明显的子群，称为G的平凡子群

①由其单位元素组成的子群{1}，称为G的单位子群

②G本身。

其余的子群(如果有的话)称为非平凡子群

思考:H是群(G,*)的一个子集，且*运算在H上具有封闭性，那么:

(1)*运算在H上满足结合律? 对

(2)*运算在H中有单位元?未必,得有限才可以

(3)如果*运算在H中有单位元，H中每个元素都有*运算逆元?未必,理由同上

比如:取整数加法群(Z,+)的子集(N,+)，这里N表示自然数集合,里面有单位元0,但是不是群

练习题:

例子:

(mZ,+)是整数加法群(Z,+)的一个子群。

(R,+)、(Q,+)(Z,+)都是(C,+)的真子群。

(R*,*)(Q*,*)都是(C*,*)的真子群。

行列式等于1的所有n阶矩阵是所有n阶非奇异矩阵的乘法群的真子群。

当n>1时，n次交代群是n次对称群的真子群

(C*m*)不是(C,+)的子群。

设Z6={0,1,2,3,4,5}，则Z在整数模6加法下是一个群，它有[4]个子群，其中有[2]个真子群，有2个平凡子群。

{0}和{0,1,2,3,4,5}       {0,3}和{0,2,4}

设(G,*)是群，对G中任意a，令H={x|x*a=a*x,x属于G}试证明(H,*)是(G,*)的子群。

1,有单位元e 非空

2,任意x,y属于H,有x*a=a*x ,y*a=a*y   x*y*a=x*a*y=a*x*y  所以封闭

3,结合律也满足,

4,有逆:任意x 满足x*a=a*x,同时右乘 x^-1  x*a*x^-1 =a,

再同时左乘x^-1---> a*x^-1=x^-1*a  

5单位元,由1,得证

(4,可除:  任意a,b属于H,存在x,y . ax=b,ya=b  ->x=a^-1 b y=b*a^-1,因为逆元存在,得证)

H称为a在G中的中心化子

子群的判定:

1,非空+封闭+结合律+含有单位元+任意元有逆元

(其中,单位元就是G中单位元,逆元也是G中对应的逆元)

2,非空,封闭,有对应逆元

(任取a属于H,有a^2.a^3...由于鸽巢原理,一定存在a^i=a^j->p=j-i .a^p*a^i=a^i,单位元就是a^p,逆元就是a^(p-i))

3,非空 + 任意a,b属于H,有a*b^-1属于H(a^-1 * b属于H 也可以)

(充分性:a*b^-1属于H,说明,b有逆元,如果a=b,就会存在单位元)

4,元素有限+封闭(鸽巢原理可证明)

练习题:

例:给定整数m，证明(mz,+)是一个群。

非空and 封闭(任意a,b属于mZ,a=ml,b=mn a+b=m(l+n))

逆元为 -a

也可以是非空＋ (任意a=ml,b=mn   a-b=m(l-n)也属于mz)

例:证明任意两个子群的交集仍是子群

1,非空,肯定有单位元

2,任取a,b属于两个子群的交集  ,因为满足群的性质,一定存在 a*b^-1属于两个子群,也就是说一定存在他们的交集中 得证

经典例题:

例11.设H和K都是群G的子群，令HK={xy|x属于H,y属于K}，KH={yx|y属于K,x属于H}。试证若HK=KH，则HK是G的子群

1,显然有单位元

2,假设x=h*K;y=h1*k1显然x,y都属于HK,y^-1=k1^-1 * h1^-1 ,x*y^-1=h*((k*k1^-1)*h1^-1)

显然k2=k*k1^-1属于 k, 又因为HK=KH  也就是说存在k2*h1^-1=h3*k3

也就是x*y^-1=h*k2*h1^-1=(h*h3)*k3=h4k3属于HK,得证

例:设G是n次对称群，判断其非空子集是否是群只需验证运算是否封闭。试判断下面哪些子集在置换的乘法下是群?(AC)

所有偶置换的集合 所有奇置换的集合 {I, (1 2)} {I,(12),(13)}

例:设G是一个群，H是G的一个子群。a属于G。试证:aHa^-1={aha^-1|h属于H}是G的子群。(aHa^-1也称为H一个的共轭子群)

1,非空,因为a*e*a^-1=e

2,封闭X=a*x*a^-1,Y=a*y*a^-1 ,X*Y=a*(x*y)*a^-1 显然封闭

3.逆元:任意X,Y属于aHa^-1 ,也就是X=a*x*a^-1,Y=a*y*a^-1 ,Y^-1=a*y^-1*a显然逆元也属于子群

(2,判别法3:X*Y^-1=a*x*y^-1*a^-1,也属于子群)

(补充知识,只有正规子群的共轭子群是自己本身)

元素的周期:

定义:

最小的p让a^p=e,周期是p,如果不存在这样的数,那么周期就是0/∞

练习题:

例:模6整数加法群(Z6,+)中，0的周期是[1]，1的周期是[6]，2的周期是[3]，3的周期是[2]，4的周期是[3]，5的周期是「6]。

例:模7整数加法群(Z-,+)中，0的周期是[1]，1的周期是[7]，2的周期是[7]，3的周期是[7]，4的周期是[7]，5的周期是[7]，6的周期是[7]。

思考:他们和元素数的关系是?

周期数都只能是元素数的约数

并且,如果元素是元素数的质因数,那么周期就是n/x(反过来说,一群阶为n的群,一定存在其质因数周期的元素)

Eg:元素有4个的群只有两种(元素周期为1,2,2,4的,是一个循环群,元素周期为1,2,2,2的,克莱因四元群)

(补充,循环群是交换群,循环群是由生成元a生成的一个群)

比如模6加法群,2: 3  但是 4的周期:3   (4不是6的质因数)

4次对称群中(1234)的周期是4，

因为(1 2 3 4)^2=(1 3)(2 4)

(12 3 4)^3=(1 4 3 2)

(1 2 3 4)^4=I

两个结论:

1,单位元周期数为1

2,任意一个元素的周期和他的逆元周期一致

练习题:

例15.设(G,·)是群，x、y属于G，且y·x·y-1=x^2,其中x≠1,y的周期是2，试求x的周期

(x^2)^2=y*x^2*y^-1=y*(y*x*y^-1)*y^-1=x所以周期是3

若群G中元素a的周期为k，则

1)1, a1. a2. a....ak-1.为k个不同元素

2)a^m=1当且仅当 k|m;

3)a^s=a^t当且仅当k|(s-t)。

思考题:

2^22=4^11

因为(1234)^4=I  所以答案是I

例题:

生成子群:

设a是群G的一个元素。于是a的所有幂的集合a^n，n=0,士1,士2....做成G的一个子群，记为(a)。此群称为由a生成的子群。

练习题

例:在模6加法群(Z6,+):

(0)={0}; (1)={0,1,2,3,4,5}; (2)={0,2,4};

(3)={0,3}; (4)={0,2,4}; (5)={0,1,2,3,4,5};

例:设G是4次对称群，由(12)生成的子群为{I，(12)}。

4次对称群中((1 2 3 4))=?

(1 2 3 4)^0=I (1 2 3 4)^1=(1 2 3 4) (1 2 3 4)^2=(1 3)(2 4)

(1 2 3 4)^3=(1 4 3 2) (1 23 4)^4=I

设Z6={0,1,2,3,4,5}，请问在模6加法群(Z6,+e)的所有子群中:

(1)包含元素0的最小子群是? {0}

(2)包含元素1的最小子群是?   {Z6}

(3)包含元素2的最小子群是? (0,2,4)

(4)包含元素3的最小子群是? (0,3)

(5)包含元素4的最小子群是? (0,2,4)

(6)包含元素5的最小子群是?{G}

循环群(巡回群):

群G为一个循环群或巡回群，如果G可以由它的某元素a生成，即有a属于G使得G=(a)，a称为群G的生成元,所以a确定的子群(a)可称为由a生成的循环子群

循环群一定是交换群,且(a)的大小就是G中a的周期

练习题:

例:以下哪些是循环群?ABCDE

A,整数加法群(Z,+) B,<{1,-1},*> C,<{1,-1,i,-i},*>

D,模6整数加法群Z6 E,模7整数加法群Z7 F,Klein四元群 G四次对称群S4

模m整数加法群(Z,+)共有多少个生成元?

有欧拉函数f(x),从1开始的与x互质的数的多少

计算公式是f(x)=x*(1-1/p1)(1-1/p2)...(1-1/pn)

两个结论

(1)无限循环群(a)一共有两个生成元a及a^-1

(2)n元循环群(a)中，元素a是(a)的生成元的充要条件是(n,k)=1。所以(a)一共有f(n)个生成元素。

引入:给定集合Z6={0,1,2,3,4,5}，田为模6加法Z,的一个子群H={0,3}

对于:0,3 * H 仍然是H

对于1,4 + H 是(1,4)不是子群

对于2,5+ H  是(2,5)不是子群

但是这几个将集合划分为了3块

合同:

定义:

设G是群，H是G的子群，a、b属于G若有h∈H，使得a=bh，则称a合同于b(右模H)记为a=b(右mod H)。

合同表示属于一个类的,是一种等价关系的表示...H是划分的依据

等价关系可以确定等价类，等价类可以构成商集，商集是一种对原集合的划分

陪集:

群G在合同关系(右模H)下的一个等价类叫做H的一个右陪集。

不同的子群会产生出不同的右模合同关系,也就会得到不同的右陪集

练习题

给定群G及其子群H，怎样求G中元素a所在右陪集? a*H

例:设G是三次对称群，H是由(123)生成的子群:H={I, (1 2 3), (1 3 2)}。

求(1 2 3)所在右陪集。

一些结论:

(1)若H为G的有限子群，则|aH|=|H|。

(2)子群H本身也是H的一个右陪集。

(3)a在右陪集aH中(a属于aH)。

根据这点，把a叫做右陪集aH的一个陪集代表。

(4)aH=H的充分必要条件是a属于H。

(5)对任意b属于aH，都有aH=bH。这点说明右陪集aH中任一元素都可以取做陪集代表

(6)aH=bH的充分必要条件是(a^-1*b属于H,b^-1*a属于H)

(7)任意两个右陪集aH和bH或者相等或者不相交。

(8)如果G是交换群,那么左右陪集没有区别

求所有陪集的一个方法:穷举任何一个不属于H的元素得到的交集然后去并集