离散数学 群（半群，群，交换群,循环群，对称群，置换群,置换,交代群,轮换）详细,复习笔记
半群:
设G是一个非空集合，若·为G上的二元代数运算，且满足结合律，则称该代数系统(G,·)为半群
性质:非空,封闭,结合律
独异点:
含有单位元的半裙
练习题：
例:设S是一个非空集合，p(S)是S的幂集，∩和U是p(S)上的交运算和并运算，则
(p(S),∩)为半群，也是独异点。单位元：全集
((S),U)为半群。也是独异点。单位元：空集
证明半群的三个步骤：非空，封闭，结合律
例:设S是一个非空集合，规定S上的运算如下:a^b=b，其中a、b是S中任意元素。
证明他是半群:
1,非空:显然非空
2,封闭:任意a,b属于S,a*b=b,显然封闭
3,结合律:a*(b*c)=(a*b)*c=c
例:.对于自然数集N、整数集Z、有理数集O、实数集R、正整数集Z+以及数的加法+、减法-、乘法x:
(1)代数系统(Z,-)、(Q,-)、(R,-)不是半群。因为数的减法运算不满足结合律。
(2)代数系统(Z+,+)是半群不是独异点。因为Z中不含数的加法运算单位元。
(3)代数系统(N,+)、(N,x)、(Z,+)、(Z,x)、0.+)、(Q,*)、(R,+)、(R,x)、(Z+ ,x)都是半群，也都是独异点。
群:
设(G,·)为半群，如果满足下面条件:
(1)G中有一个元素1，使得对于G中任意元素a，都有1·a=a·1=a;
(2)对于G中任意a，都可找到G中一个元素a-，使得a·a^(-1)=a^(-1).a =1:
则称(G,·)为群。元素1称为G的单位元或壹元:a^(-1)称为a的逆元。如果群G包含的元素个数有限，则称G为有限群，否则称G为无限群
简记:半群+单位元(对称中心,对称轴)+逆元(对称过去后的点，仍在集合内)
在整数集合上,加法是群,乘法是半群,不是群,因为除了1和-1,其他的元素都没有逆元
练习题：
例.G={1,-1}关于整数乘法运算构成一个群
非空，封闭，乘法有结合律，然后是单位元 1，逆元都是自己
例.G={1,-1,i,-}关于复数乘法运算构成一个群,其中 i=(-1)^(1/2)
非空，封闭，乘法有结合律，然后是单位元 1，i的逆元：-i ,-i : i . ...
例.N阶非奇异实数方阵的集合关于矩阵乘法运算构成一个群。
例.集合Z={1,2,3,4}，二元代数运算*定义如下:对任意a、b属于Z，a*b=(a*b)/5的余数这里x、
/为普通整数乘法和除法，(Z-;*)是否为群?
1,非空
2,封闭显然
3,结合律(普通的乘法有结合律且(a*b)/5*(c*d)/5)=(a*b*c*d)/5
4,单位元 1
5,2的逆元:3 3的逆元:2 4的逆元:4
经典例题：
例:设p是一个素数，F,{0,1,…,p-1}，F’=F,-{0},证明集合F’对于乘法:a*b=(a*b (mod p))构成一个群。
1,非空
2,封闭因为模p所以范围都在p内,由于是素数所以在(1到p-1)内没有相乘出来是p的倍数的
3,结合律:结合律
4,单位元:1
5,逆元:由费马小定理:如果p是素数,a与p互质,有 a^(p-1)=1mod(p),所以有a^(-1)=a^(p-2)
例:设n是一个合数，Z.={0,1,..,n-1}，Z+:Z.-{0}请说明集合Z+对于乘法:a*b=(a*b (mod n)不构成一个群
1,不封闭,因为是合数,所以存在a,b属于Z+,a*b=0
但是如果题目改成Z-为Z+为和p互素的数
1,非空,2封闭,3,结合律都满足,4,单位元1,5,逆元为a*x=1 mod p(有解的条件为a,p互质)
例:设n是正整数，Z={0,1.….n-1}，规定Z上的模n加法运算+如下:
当a+b<n时a+b=a+b 当a+b>n时a+b=a+b-n
其中a、b是Z,中任意元素，+、-为数的加减，则(Z,+)为群，称为模n整数加法群。
相类似的还有模p的剩余类,也构成一个群
例:设(G，)是一个半群，如果对所有的a,b属于G，只要a≠b必有a*b≠b*a。证明:
(1)任意a属于G，有a*a=a;
(2)任意a,b属于G，有a*b*a=a;
(3)任意a,b,c属于G，有a*b*c=a*c.
1,因为只有a不等于b的时候,a*b != b*a,所以如果有a*b=b*a,那么一定是a=b,所以让b=a*a
因为是半群,所以有a*(a*a)=(a*a)*a,所以a=b,即a*a=a
2.a*(a*b*a)=(a*a)*(b*a)=a*b*a
(a*b*a)*a=(a*b)*(a*a)=a*b*a
所以a*(a*b*a)=(a*b*a)*a,由题:a*b*a=a
3,a*b*b*c=a*b*c
a=a*b*a c=c*b*c a*c=a*b*a*c*b*c
B*(a*c)*b=a*c
a*(a*c)*c=a*C
得证
群的3个结论
1,群中的单位元是唯一一个幂等元
2,群的大小如果大于1,则没有零元（等于1的话，零元和单位元一体）
3,群中满足消去律
练习题
例:证明:在偶数元的有限群G中必存在元素a!=e使得a^2=e(其中e是群的单位元)
一个元素和他的逆元成对存在,假设他们互不不相等
假设有n对逆元对,一个单位元
元素个数就是1+2*n为奇数,所以一定存在至少一个(可以是更多的奇数个)自己就是自己的单位元,比如上面的例题Z5(1,2,3,4)的模5乘法群里面,2和3互逆,4逆元为自己,
例:设G={2^n*3^m叫m,n属于Z}.G关于普通数的乘法构成一个群。
由于对于乘法来说就是指数的加法,整数上的加法是群,那这个也是群
群的4个判定法（重要）:
1,半群(非空,封闭,结合律)+单位元+任意元有逆
2,半群(...)+左/右单位元 + 有左/右逆元
证明：我们假设el,er是左右单位元，a的左逆元为 b ，b*a=el，假设b的左逆元为c,c*b=el
先证左右单位元一致：el*er =er=el
对于a*b=(c*b)*a*b=c*b =el 所以b也是a的右逆元
3,半群(...)+对任意a,b属于G,均有 x*a=b,a*y=b(排列,可除性)(即存在b*a^-1和a^(-1)*b)
4,半群(...)+有限+对任意a,b属于G,右 a*x=a*y x*a=y*a 都可以推出 x==y (左右消去律)
练习题：
例:给定正整数m，令G={kmlk属于Z}证明:(G,+)是一个群。
1,非空 2,封闭 任意a,b属于z,有m(a+b)也属于z 3,结合律成立
4,左单位元 0 5,a的左逆元 -a
例:设(G,*)是群，u属于G，在G上定义另一个二元运算。，使得a o b=a*u^-1*b(任意a、b属于G)
证明:(G,o)也是群。
证明:
1,非空 2,封闭显然,因为*是群(G,*)的运算 3,结合律也是
4,对任意a,b属于G，存在x=b*a^-1*u，使得x o a=b*a^-1*u*u^-1*a=b，
存在y=u*a^-1*b，使得a o y=a*u^-1*u*a^-1*b=b，满足可除条件。
三大指数定律和求逆法则
1,a^m * a^n=a^(m+n) 第一指数
2,(a^m)^n=a^(mn) 第二指数
3,(a*b)^-1 = b^-1 * a^ -1
(但是不一定有 (a*b)^2=a^2 * b^2,这个得是交换群才可以) 第三指数
交换群(Abel群):
如果群(G,*)的*满足交换律
交换群的判别:
半群 + 任意a,b属于G,b/a(b*a^-1)属于G(对比群的第三个判定法b*a^-1 ,a^-1 *b)
或者是群+交换律
练习题:
例:(Z,+)、(Q,+)、(R,+)、(C,+)都是无限Abe1群。
例:(Q,·)、(R,·)、(C,·)也是无限交换群，
上面两个例都是用的对应的普通加法和乘法具有的交换律的性质
例:元素为实数或复数的n(n>1)阶可逆矩阵的全体关于矩阵的乘法组成群，都是非交换群，叫全线性群，记为GL(n,R)或GL(n,C)
经典例题
例:设(G,*)是一个群，若群G的每一个元素都满足方程x^2=1(其中1是G的单位元)，那么G是Abel群，
任意a,b属于G,有a*a=1 所以a^-1=a
a*b=(a*b)^-1=b^-1 * a^-1 =b*a
加法和乘法有交换律,所以对于整数多项式的加法是交换群,整数多项式的乘法是交换半群(因为0无逆元)
---------------------------------------------------------------------------------------------------------------------------------
证明:每个有限半群至少有一个幂等元。
半群有非空,封闭,结合律的性质
任意a属于S ;则a,a^2,a^3,....,a^(n+1)均属于S.
故存在a^i=a^j，其中1<=i<j<=n+1，(鸽巢原理)
存在k(整数)有，k(j-i)>=i，a^[2k(j-i)]=a^[2k(j-i)-i]a^i=a^[2k(j-i)-i]a^j=a^[2(k-1)(j-i)]=...=a^[k(j-i)]
那么b=a^[k(j-i)]是幂等元。令p=j-i 则 a^(kp)就是幂等元
---------------------------------------------------------------------------------------------------------------------------------
置换:
设M为非空有限集合，M的一个一对一变换f称为一个置换。如果IM|=n，则f称为n元置换或n阶置换(G中所有元素的一个排列)
M={a1,a2.....an}其置换为
其中bi=6(ai)
如果是6(ai)=ai,那么就是恒等置换 I
M的置换一共有n!个(全排列)
练习题
例:证明:设(G,*)是有限群，则此群的运算表中每一行以及每列都是G中所有元素的一个排列。
我们任取一个元素a作为左操作数,然后任意取一个G中的元素b,一定存在y,使得a*y=b,y=a^-1 *b
所以一定是一个排列(判定条件3的第四个)
a作右操作数也一样
例:设M={1，2，3}，则有3!=6个3元置换
置换的乘积:
假如有两个置换f,g fg(x)=f(g(x))
置换乘积的性质
1,有结合律
2,有单位元(I)
3,有逆元(上下颠倒)
(所以部分置换可以构成群:置换群)
例:
(从左到右乘)
n次对称群:
n元置换的全体作成的集合S,对置换的乘法作成一个群
当n=1时，M={a}，S{a}关于置换乘法作成1次对称群为Abel群;
当n=2时，M={a,b}，S2{{a,b},{b,a}}成2次对称群，为Abel群;
当n=3时，S.不是交换群，是一个6元群
轮换
上面的(1)的形式叫做轮换,表示一个置换内部的1个循环关系
轮换的长度是r(循环长度)
如果不止一个循环就不是轮换
练习题:
例:
不是,有多个循环
多个循环的表示方式(132)(45) -->数字都不相交
如果相交 ,比如(1 3 4)(3 4 6)表示两个相乘的结果->(13)(46)
注意,没有交换律,交换后的乘积结果和现在的不一致,具体交换后结果是(14)(36)
例:(341)=(413)对吗?
对,相对的次序都是134
轮换乘积的性质
不相交轮换的乘积可交换:t*g=g*t
相交轮换的乘积不可以交换:比如上面的交换的话就是(14)(36)
任意置换可以写成不相交的不相交的轮换乘积,且唯一(不考虑顺序的话)
例设M={1,2,3,4}，M的24个置换可写成:
I(恒等置换)
(1 2),(1 3),(1 4),(2 3),(2 4),(3 4)
(1 2 3),(1 3 2),(1 2 4),(1 4 2),(1 3 4),(1 4 3)，(2 3 4)，(2 4 3)
(1 2 3 4)，(1 2 4 3)，(1 3 2 4)，(1 3 4 2),(1 4 2 3)，(1 4 3 2);
对换:
(长度为2的轮换)
任意的轮换可以表示为r-1个对换的乘积
比如:(a1,a2...a,)=(a ar)(a ar-1)...(a a3)(a a2)
或者(a1a2...a,)=(a1 a2)(a2 a3)...(ar-2 ar-1)(ar-1 ar)
任意置换也肯定至少有一个方法可以表示为一些对换
(12)=(12)(13)(13)
练习题:
例:
原式=(123)(456)=(12)(23)(45)(56)
对于(12) 只能写作3,5,7...个对换之积
不能写作2,4,6......个对换之积
奇置换 和 偶置换:
定性数:对于t=元素总数-轮换的个数(包括长度为1的)
如果t是奇数就是奇置换,只能表示为奇数个对换的积
偶数就是偶置换,只能表示为偶数个对换的积
对换是奇置换
置换可以表示为t个对换
练习题:
比如G={1,2,3,4,5,6}.M=(1 3 4)(25)可以表示为(13)(34)(25)/(14)(13)(25)
例:集合M={1,2,3,4,5,6}，置换
,t1,t2,t3是集合M上的对换(这里允许t1=t2=t3;)那么是否t1*t2*t3*t=t?如果是t1*t2*t?如果是t1*t?
第一个不可能，第二个可能，第三个不可能
置换的逆和原置换保持一样的奇偶性
思考:(重要)
如果(a b)是集合M上的对换，T是集合M上的奇置换，那么(ab)t是什么置换? 偶置换
T是集合M上的偶置换，那么(ab)t是奇置换
设t的定性数为n-k
(1)若a、b分别出现在t的两个不同轮换中,设τ=(a a1....as)(b b1....bi), 则 (ab)t=(a a1....as b b1....bi)比t少一个轮换，所以(ab)t的定性数为n-(k-1)。
eg:G={1,2,3,4,5,6} .t=(134)(25) 定性数为3 f=(15)f*t=(13452)定性数为 4
(2)若a和b同时出现在的一个轮换中:设τ=(a a1....as)(b b1....bi),则(ab)t=(a a1....as b b1....bi)
比t多一个轮换，所以(ab)t的定性数为n-(k+1)
置换σ、T的奇偶性与其乘积σT的奇偶性关系:
偶x偶=偶，奇x奇=偶，奇x偶=奇，偶x奇=奇。
因为对换是奇置换，所以奇数个对换之积是奇置换，偶数个对换之积是偶置换
奇置换的个数和偶置换的个数
设M的元数为n，若n>1，则奇置换的个数和偶置换的个数相等，都等于n!/2
n次交代群:
所有n元偶置换作成的集合，乘法构成一个群，个数是n!/2。
置换群：
是由若干个n阶置换关于置换乘积运算所构成的群是n次对称群的一个子群。
(下面是ai列举的找置换群的方法,总结就是先平凡,后循环,然后非循环...)
练习题:
例：
- (153)(46) (243)(56)
- 都是lcm(2,3)=6
- t和6都是奇置换,所以t^-1也是奇置换 所以是奇置换
例:设多项式f=(x1+x2)(x3+x4)，找出使f保持不变的所有下标的置换，这些置换在置换的乘法下是否构成群?
解:由加法交换律和乘法交换律可得到使f保持不变的所有下标的置换的集合为:
G={(1)(2)(3)(4),(1 2)(3)(4)，(1)(2)(3 4),(1 2)(3 4),(1 3)(2 4)，(14)(23)，(1324)，(1423)}。
G是S,的有限非空子集;可以验证置换乘法在G上是封闭的:
