离散数学课件 第9章 半群和群.docx
《离散数学课件 第9章 半群和群.docx》由会员分享，可在线阅读，更多相关《离散数学课件 第9章 半群和群.docx（29页珍藏版）》请在冰点文库上搜索。
离散数学课件第9章半群和群
第9章半群和群semigroupandgroup
§9.1二元运算复习binaryoperationrevisited
A上二元运算
f：
A×A→A
f处处有定义的函数。
Dom（f）＝A×A，
对任意a，b∈A，f（a，b）∈A，唯一确定。
二元运算常记做＋，－，×，*，◦，等等
对任意a，b∈A，a◦b∈A
说成A对◦封闭。
A＝{a1,a2,……,an}时，二元运算可以用运算表给出。
二元运算的性质
1可换commutative
a*b=b*a
2结合associative
a*（b*c）=（a*b）*c
3幂等idempotent
a*a=a
特殊元素
单位元
对任意a∈A，e*a=a*e＝a.
单位元也叫恒等元
零元
对任意a∈A，0*a=a*0＝0
逆元
对任意a，b∈A，a*b=b*a＝e
a,b互为逆元
代数结构
（A,*）A上定义了二元运算满足
1）封闭性
2）结合律-----------半群
3）有单位元---------独异点
4）有逆元-----------群
5）可交换-----------交换群
例子：
1）（Zn+）,（Zn,）
2）（A*,*）字符串的连接
HomeworkP323－324
16，20，22，24，25，26
§9.2半群semigroup
半群定义：
（S,*）*是S上乘法，满足结合律。
半群的例
（Z，＋），（Z，×），
（N，×），（N，＋），
（Q，＋），（R，×），
（P（S）,∪），（P（S）,∩），
（Mn，＋），（Mn，×），
S上全体映射，对于复合，
（L，∧），（L，∨），L是格
（A*,）,
定理1.
半群中，n个元素的乘积与乘法的次序无关。
幂power：
设（S，*）是半群，a∈S，定义a的幂power：
a1＝a，an=an-1*a.
a0=？
a-n=?
am*an=am+n
（am）n=amn.
子半群subsemigroup子独异点submonoid
设（S，*）是半群，TS，T对*封闭，则（T，*）也是半群，称为（S，*）的子半群。
设（S，*）是独异点，TS，T对*封闭，且e∈T，则（T，*）也是独异点，称为（S，*）的子独异点。
（N，＋），（Z，＋），（Q，＋），（R，＋）前一个是后一个的子半群，也是子独异点。
（N，×），（Z，×），（Q，×），（R，×）前一个是后一个的子半群，也是子独异点。
设（S，*）是半群，（S，*）是（S，*）的子半群。
设（S，*）是独异点，（S，*）是（S，*）的子独异点。
设（S，*）是独异点，（{e},*）是（S，*）的子独异点。
同构isomorphism和同态homomorphism
同构
设（S，*）和（T，*’）是两个半群，
函数f：
S→T是一一对应，a，b∈S，
f（a*b）=f（a）*’f（b）.
称（S，*）和（T，*’）同构，记做
（S，*）（T，*’）.
验证两个半群（S，*）和（T，*’）同构的方法：
定义一个映射f：
S→T，证明
（1）f单，f（a）=f（b）a=b.
（2）f满，Ran（f）=T.
（3）f保持运算f（a*b）=f（a）*’f（b）.
例.令T＝{2n|n∈Z}，则且（Z，＋）（T，×）。
证明.
令f：
Z→T，
对任意n∈Z，f（n）=2n.
（1）f处处有定义.
（2）f单:
f（m）=f（n）,即
2m=2nm=n。
（3）f满.
（4）f保持运算：
f（m+n）=2m+n
=2m×2n=f（m）×f（n）
定理2.若S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元。
同态Homomorphisim
在同构的三个条件中，若仅满足（3）叫做同态。
若仅满足
（1）（3）称为同构嵌入。
若仅满足
（2）（3）叫做满同态。
例20．设A＝{0，1}，则自由半群（A*,）与（A，＋）同态，（A，＋）的二元运算＋由乘法表给出：
＋
0
1
0
0
1
1
1
0
例.（Z,+）（Zn,+）,
（Z,×）（Zn，×）.
定理3.恒等元的满同态像是恒等元
设（S，*），（T，*）是独异点，恒等元分别是e和e’，同态f:
（S，*）（T，*’）,则f（e）=e’.
定理4.子半群的同态像是子半群。
证明.
设f：
（S，*）（T，*’）是半群同态，S’是（S，*）的子半群，
则f（S’）是（T，*’）的子半群。
只要证f（S’）对运算封闭。
设t1,t2∈f（S’），要证t1*’t2∈f（S’）.
存在s1，s2∈S’，
f（s1）＝t1，f（s2）＝t2，
t1*’t2=f（s1）*’f（s2）
=f（s1*’s2）∈f（S’）.
定理5.交换半群的同态像是交换半群。
设f：
（S，*）（T，*’）是到上半群同态，（S，*）是交换半群，
则（T，*’）的交换半群。
证明.任意t1,t2∈T，
要证t1*’t2＝t2*’t1.
存在s1，s2∈S，
f（s1）＝t1，f（s2）＝t2，
t1*’t2=f（s1）*’f（s2）=f（s1*’s2）
＝f（s2*’s1）＝f（s2）*’f（s1）＝t2*’t1.
HomeworkP330－331
13，16，18，19，23，26，28，31
§9.3乘积半群和商半群ProductsandQuotiensSemigroup
定理1.乘积半群
设（S，*）和（T，*’）是两个半群，则（S×T，*”）也是半群。
（s1,t1）*”（s2,t2）=（s1*s2,t1*’t2）.
设（S，*）和（T，*’）是两个独异点，则（S×T，*”）也是独异点，恒等元是（e，e’）。
同余关系（合同关系）congruencerelation
设（S，*）是半群，R是S上等价关系。
R称为S上同余关系：
aRa’,bRb’（a*b）R（a’*b’）.
例1.Z上剩余关系是（Z,＋）上同余关系：
ab（mod2）2|a－b。
证明.ab（mod2）是等价关系。
ab（mod2）,2|a-b,a-b=2k.
cd（mod2）,2|c-d,c-d=2t.
（a+c）－（b+d）=（a-b）+（c-d）=2（k+t）
a+cb+d（mod2）
ab（mod2）是（Z,＋）上同余关系。
Z上剩余关系是（Z,×）上同余关系.
例2．令A＝{0,1},自由半群（A*,）上关系R：
αRβα，β含有同样多个1。
则R是（A*,）上同余关系。
例3．设f（x）=x2-x-2,令（Z，＋）上关系R：
aRbf（a）=f（b）.
R是Z上等价关系，但不是同余关系。
－1R2，f（－1）=f
（2）=0
－2R3，f（-2）=f（3）=4
-1+-2=-3,2+3=5
f（-3）=10,f（5）=18
-1+-2与2＋3不满足R。
定理2.设R是半群（S，*）上同余关系。
定义商集S/R上二元运算*：
[a]*[b]=[a*b]。
则（S/R,*）是半群。
证明.设[a]=[a’],[b]=[b’],
要证[a*b]=[a’*b’]
aRa’,bRb’,由*是同余关系
a*bRa’*b’,因此[a*b]=[a’*b’]，*是映射，二元运算。
还要证*满足结合律：
[a]*（[b]*[c]）=[a]*[b*c]
=[a*（b*c）]=[（a*b）*c]
=[a*b]*[c]=（[a]*[b]）*[c]
因此（S/R,*）是半群。
称S/R为商半群。
推论1.设R是独异点（S，*）上同余关系，则（S/R,*）是独异点。
证明.恒等元e∈S,只要证明[e]是S/R,的恒等元。
任何a∈S，
[a]*[e]=[a*e]=[a]
[e]*[a]=[e*a]=[a].
例5．（Zn,+）,（Zn，×）都是半群，独异点。
Zn＝{[0],[1],[2],……,[n-1]}
[m]+[n]=[m+n]
定理3.令R是半群（S，*）上同余关系,（S/R,*）是商半群。
f：
S→S/R,
f（a）=[a],
则f是满同态，称f为自然同态。
定理4.同态基本定理
设f:
（S，*）→（T，*’）
是两个半群间的满同态映射，令R是S上二元关系：
a,b∈S，aRbf（a）=f（b）.
则
（a）R是（S，*）上同余关系。
（b）（T，*’）（S/R,*）.
HomeworkP337-338
4,10,14,16,22,24
§9.4群Group
群的定义
群（G，*）是一个代数系统，
1）封闭
2）结合律,
2）有单位元e，a*e=e*a=a,
3）对每个a∈G，存在a’∈G，a*a’=a’*a=e,
称a’为a的逆元。
群（G，*）是一个有单位元的独异点，对每个a∈G，存在逆元a’∈G，使a*a’=a’*a=e.
群（G，*）常简记为G，
a*b常简记为ab。
可换群叫Abel群AbelianGroup
群的例
（Z，＋），
（Q，＋），（Q\{0}，×），
（R，＋），（R\{0}，×），
（Zn，＋），
（Mn，＋），
S上全体一一对应，对于复合，
最后一个不是Abel群。
例（R，*）：
a*b=ab/2是Abel群。
群的性质
定理1.群的逆元唯一：
设G是群，任意a∈G，a只有一个逆元，记做a-1。
证明.
设a’，a”都是a的逆，
a’=a’aa”=a”.
定理2.群有消去律：
设G是群，a,b,c∈G,则
（a）ab＝acb＝c，
（b）ba＝cab＝c。
设G={a1,a2,……,an}任意a∈G，aG=G.
定理3.逆律
设G是群，a,b∈G,则
（a）（a-1）-1=a,
（b）（ab）-1=b-1a-1.
（c）（an）-1＝（a-1）n
定理4.方程有唯一解
设G是群，a,b∈G,则
（a）方程ax＝b在G中有唯一解。
（b）方程ya＝b在G中有唯一解。
群G的阶:
|G|.
|G|有限时称G为有限群。
元素的阶
a∈G，a的阶：
使ak＝e的最小的k。
如无这样的k，称a为无限阶。
a无限阶，任意n∈Z+，an≠e.
子群subgroup
HG，H对于G的运算*构成群。
H是G的子群当且仅当
（1）e∈H
（2）a，b∈Hab∈H
（3）a∈Ha-1∈H
H是G的子群当且仅当
a，b∈Hab-1∈H.
子群的例
设G是群，H＝{e}是子群。
G是群，a∈G，H＝{ak|k∈Z}是子群，叫做a生成的子群。
命题.一个群的任意两个子群的交仍是子群。
循环群cyclegroup
存在a∈G，任意x∈G，
x＝ak，k∈Z。
a的阶是n，G＝{e,a,a2,……,an-1}
ak的逆是an-k。
a无限阶，
G＝{……,a-2,a-1,e,a,a2,……}
Z是无限循环群，Zn是n阶循环群。
有限群G是循环群当且仅当存在a∈G，a的阶＝|G|.
（Zn,+）,（Zp*,）
置换群Sn
三角形的自同构群？
A＝{1,2,3},A的所有置换对复合运算构成群：
=
（1）单位元
=（123）3阶元
=（132）
=（23）2阶元
=（13）
=（12）
S3={f1,f2,f3,g1,g2,g3}
称（S3,*）为对称群，Groupofsymeriesofatriangle。
S3的乘法表：
f1
f2
f3
g1
g2
g3
f1
f1
f2
f3
g1
g2
g3
f2
f2
f3
f1
g3
g1
g2
f3
f3
f1
f2
g2
g3
g1
g1
g1
g2
g3
f1
f2
F3
g2
g2
g3
g1
f3
f1
F2
g3
g3
g1
g2
f2
f3
F1
S4四元对称群，是四个元素的置换组成的对称群，共有4！
＝24个置换。
Snn元对称群，是n个元素的置换组成的对称群，有n！
个元素。
Cayley定理：
任意的群都同构与某个对称群的子群。
自由群
群的同构与同态isomorphismandhomomorphismofgroups
同构f:
（G1，*）（G2，*），
f一一对应，保持运算。
|G1|=|G2|,对应元素有相同的阶。
同态f:
（G1，*）（G2，*），
f多一到上，保持运算。
ZZn
Z6≌Z7*
例16．S3与Z6都是6阶群，不同构。
定理5.单位元，逆元，子群在同态下保持
设f:
（G，*）（G’，*’）是同态，
则（a）f（e）=e’,
（b）f（a-1）=f（a）-1,
（c）H是G的子群f（H）是G’的子群。
共轭对应是群的自同态
a∈G,f:
G→G,f（x）=axa-1,f是同态。
HomeworkPP348－349
6，12，19，22，24，28，30，32，33
§9.5乘积群和商群
定理4.设G1，G2是群，则G1×G2是群，乘法定义（a1,b1）（a1,b1）=（a1a2,b1b2）.
乘积群的例
Z2×Z3Z6，
Z2×Z2V（Klein四元群）
Zm×ZnZmniff（m,n）=1.
a≡1（modm）
b≡1（modn）
ab≡1（modmn）
B={0,1}
Bn=B×B×……×B。
定理5.设R是群（G，*）的同余关系，则商（G/R,*）是群。
群的同态定理
（a）设R是群（G，*）的同余关系，则fR：
G→G/R是群同态映射。
（b）设f:
（S，*）→（T，*’）
是两个群间的同态映射，令R是S上二元关系：
a,b∈S，aRbf（a）=f（b）.
则
（1）R是（S，*）上同余关系。
（2）
:
（S/R,*）（T，*’）.
子群的陪集coset
左陪集leftcoset
设H是G的一个子群，a∈G，
令aH＝{ah|h∈H}称为a确定的H的一个左陪集。
右陪集rightcoset
设H是G的一个子群，a∈G，
令Ha＝{ha|h∈H}称为a确定的H的一个右陪集。
例H1={0,3},H2={0,2,4}都是Z6的子群。
H1在Z6中的左陪集有
0+H1={0,3}=H1
1+H1={1,4}
2+H1={2,5}
3+H1={3,6}={0,3}=H1
4+H1={4,7}={1,4}
5+H1={5,8}={2,5}
陪集的性质，设H是G的子群，
命题1.a∈G，aH＝Ha∈H.
证明.
设a∈H，任意h∈H，
由H是G的子群
ah∈H，aHH，
a-1∈H,a-1h∈H，
h＝aa-1h∈aH，HaH。
因此aH＝H
设aH＝H，由H是G的子群
e∈H，a＝ae∈aH＝H，a∈H。
例3.H={f1,g2},是S3的子群，
求H的所有左陪集。
解.
f1H=g2H=H,
f2H=g1H={f2,g1}
f3H=g2H={f3,g2}
例4.Hf2＝{f2,g3}≠f2H
H不是正规子群。
命题2.a,b∈G则aH∩bH＝或aH＝bH.
证明.设aH∩bH≠。
存在h’，h”∈H,ah’=bh”.
任意h∈H，
ah＝ah’h’-1h=bh”h’-1h∈bH，
aHbH.
同理bHaH.因此aH＝bH.
H的所有左陪集组成G的一个划分，G＝∪a∈GaH。
命题3.任a∈G，f:
aH→H，f（ah）=h是一一对应。
命题4.|G|=n,则|H||n.
命题5.|G|=n,a∈G，a的阶＝k，则k|n.
推论设p是素数，a∈Z,~（p|a）,则ap-1≡1.
证明.由~（p|a）,~（a≡0）.a∈Zp*,
设a的阶是k,ak≡1.
Zp*的阶是p-1.
由命题5，k|（p-1）.
ap-1≡1.
正规子群Normalsubgroup
设H是G的一个子群，对任意a∈G，
aH＝Ha，就称H是G的正规子群。
注意
aH＝Ha并不是h∈H，ah＝ha
而是存在h’∈H，ah＝h’a.
命题6.
设G是Abel群，H是G的任意子群，则H是G的正规子群。
证明.任取a∈G，证明aH＝Ha：
任意h∈H，ah＝ha，aHHa，
aHHa，aH＝Ha。
定理1.
设N是G的正规子群，在G上定义一个关系，a，b∈G，
aRba-1b∈N.
则
R是G的同余关系。
N＝[e].
证明.（a）
R是等价关系：
1）a-1a=e∈N，aRa；
2）设aRb，a-1b∈N.
b-1a＝（a-1b）-1∈N.
bRa;
3）设aRb，bRc，
a-1b∈N，b-1c∈N，
a-1c＝（a-1b）（b-1c）∈N
aRc;
R是同余关系：
设aRb，cRd，
a-1b∈N，c-1d∈N，
c-1a-1b∈c-1N=Nc-1，
存在h∈N，c-1a-1b＝hc-1
（ac）-1bd=c-1a-1bd＝hc-1d∈N，
acRbd。
（b）任意x∈N，x-1e＝x-1∈N，
xRe，x∈[e].N[e].
任意x∈[e],xRe,x-1e＝x-1∈N，
x∈N，[e]N.
N=[e].
定理2.
令R是群G的同余关系，H＝[e],则H是正规子群，任意a∈G，aH＝Ha＝[a]。
证明
H=[e]是G的子群。
任取a，b∈[e],有aRe,bRe,
R是同余关系，abRe，ab∈[e],
R是等价关系a-1Ra-1,eRa，
a-1eRa-1a,即a-1Re，a-1∈[e]
R是等价关系,eRe,e∈[e],
任取a∈G,aH＝[a],
任取h∈H，hRe，aRa，
ahRae，ahRa，ah∈[a].
aH[a],
任取b∈[a],bRa,a-1Ra-1
a-1bRa-1a,a-1bRe,a-1b∈[e]=H
b=aa-1b∈aH。
[a]aH。
aH＝[a].
同理可证Ha＝[a].
aH=[a]=Ha,H是正规子群。
定理3.
设f:
GG’是满同态，令ker（f）={a|a∈G，f（a）=e’}.
则
ker（f）是G的正规子群，
G/ker（f）G’.
aRbf（a）=f（b）a-1b∈ker（f）.
HomeworkPP353-354
1,3,6,12,16,18,22,24,29,30,31
习题
1．除单位元外只有二阶元的群是Abel群.
2．有左右消去率的有限半群是群.
3．偶数阶群中有奇数多个二阶元.
4．证明定理3.
5．有多少个8阶群？
§9.6BurnsideLemma伯恩赛德引理，Pόlya定理
9.7.1置换的类型
定义一个n次置换p可以分解为
互不相交的λ1个1轮换，
λ2个2轮换，……，λn个n轮换，
p称为（λ1,λ2,……，λn）型置换,
也称p是1λ12λ2……nλn型置换.
显然有
.
例如p1=
（1）（2,3）（4,5,6,7）,p2=（1,2,3）（4,5）（6,7）
则p1属于11213041506070型
简写为（112141）型
p2属于10223140506070型
简写为（2231）型
3次对称群S3种置换可能的类型
1λ1+2λ2+3λ3=3
（λ1,λ2,λ3）
=（3,0,0），（1,1,0）,（0,0,1）
（1）
（2）（3）∈（3,0,0）
（1,2）（3）,
（1）（2,3）,（1,3）
（2）∈（1,1,0）
（1,2,3）∈（0,0,1）
一个置换群G中，用
D（λ1,λ2,……,λn）表示
（λ1,λ2,……,λn）型置换的个数
定理9.7.1n元对称群Sn中
D（λ1,λ2,……,λn）
=
计算S3,S4中各种类型的置换个数。
以λk（p）表示p的k阶（不相交）轮换的个数，λ（p）表示p的所有（不相交）轮换的个数。
λ（p）=
λ1（p1）=1，λ2（p1）=1，λ4（p1）=1.
λ1（p2）=0，λ2（p1）=2，λ3（p1）=1.
9.7.2置换群的轨道
设G是S={1,2,……,n}的置换群，pG,iS
不动点和不动置换类
不动点
如果p（i）=i,称i是p的一个不动点。
P可以有不止一个不动点。
G中可以有不止一个置换以i为不动点。
p的不动点数=λ1（p）.
不动置换类
G中以i为不动点的所有置换称为i的不动置换类，记为Zi。
例子G是4次对称群S4的子群
G={e,（1,2）,（3,4）,（1,2）（3,4）}
G中
Z1=Z2={e,（3,4）}
Z3=Z4={e,（1,2）}
定理9.7.2
群G中，对任意i,1in,
Zi构成G的子群,|Zi|||G|.
G的轨道
设G是S={1,2,……,n}的置换群，i，jS,如果存在pG,使p（i）=j,就称i,j相连，记做i~j。
所有与i相连的元素的集合记做Ei,Ei也称为i的轨道
~是S上等价关系，Ei是i所在的等价类。
G={e,（1,2）,（3,4）,（1,2）（3,4）}
G中E1=E2={1,2},E3=E4={3,4}.
S中每个元素都有一个轨道，
不同的轨道是互不相交的。
定理9.7.3对任意i,1in,
|Ei||Zi|=|G|.
证明
设pG,pZi是Zi的一个左陪集,如果p（i）=j,则对任意qZi,pq（i）=j,即陪集pZi中任意元素都把i变到j.
Zi的任意一个陪集把i变到一个元素，
Zi不同的陪集把i变到不同的元素。
Zi陪集的个数与Ei中元素个数一样多，因此有
|Ei|=|G|/|Zi|，
|Ei||Zi|=|G|.
9.7.3BurnsideLemma伯恩赛德引理
定理9.7.4（BurnsideLemma伯恩赛德引理）
设G={p1,p2,……,pr}是S={1,2,……,n}的置换群，
L表示G的轨道的个数。
则
L=
证明
记G的置换下不动点的总数为N,
依置换逐个计算
N=
=
.
依S中元素逐个计算
.
于是得到
L|G|=
L=
.
例1
对正方形的4个格子用两种颜色着色，有多少种不同的着色方法，其中经过旋转重合的方案只算一种。
解
不论旋转共有24=16种方案
S={f0,f1,f2,f3,f4,f5,f6,f7,f8,
升级会员 