《离散数学 教学课件 ppt 作者 李盘林 第07章》由会员分享，可在线阅读，更多相关《离散数学 教学课件 ppt 作者 李盘林 第07章（83页珍藏版）》请在金锄头文库上搜索。
1、第七章 半群与群,7.1 半群和独异点的定义及其性质 7.2 半群和独异点的同态与同构 7.3 积半群 7.4 群的基本定义与性质 7.5 置换群和循环群 7.6 子群与陪集 7.7 群的同态与同构,退出,7.1 半群和独异点的定义及其性质,定义7.1.1 给定，若满足结合律，则称为半群。 可见，半群就是由集合及其上定义的一个可结合的二元运算组成的代数结构。 定义7.1.2 定，若是半群且有幺元或满足结合律且拥有幺元，则称为独异点。,可以看出，独异点是含有幺元的半群。因此有些著作者将独异点叫做含幺半群。有时为了强调幺元e，独异点表为。 如果半群中的集合S是有限的，则称半群为有限半群，对于有限半
2、群可以给出下面有趣定理。 定理7.1.1 为有限半群(x)(xSxx=x) 本定理告诉我们，有限半群存在等幂元。,定义7.1.3 给定半群，若是可交换的，则称是可交换半群。类似地可定义可交换独异点。 定义7.1.4 给定半群和gS，以及自然数集合N，则 g为的生成元:=(x)(xS(n)(nNx=gn) 此时也说，元素g生成半群，而且称该半群为循环半群。 类似地定义独异点的生成元g和循环独异点，并且规定g0=e。,定理7.1.2 每个循环独异点都是可交换的。 可见，是可交换的，故是可交换的。显然，每个循环半群也是可交换的。 对于生成元的概念加以推广便得出生成集的概念。,定义7.1.5 给定半群
3、及GS，则 G为的生成集:=(a)(aSa=(G) |G| 这里(G)表示用G中的元素经的复合而生成的元素。 类似地定义独异点的生成集。,定义7.1.6 给定半群及非空集TS，若T对封闭，则称为的子半群。 类似地定义独异点的子独异点，应注意的是eP。,定理7.1.3 给定半群及任意aS，则是循环子半群。 显然，a是的生成元。故是循环子半群。,定理7.1.4 给定可交换独异点，若P为其等幂元集合，则为子独异点。 定理7.1.5 设为独异点，则关于的运算表中任两列或任两行均不相同。,定理7.1.6 给定独异点，对任意a，bM且a，b均有逆元，则 (1) (a-1)-1=a。 (2) ab有逆元，且
4、(ab)-1=b-1a-1。,7.2 半群和独异点的同态与同构,在本节里，将把代数结构之间的同态与同构的概念应用于半群与独异点。有些定义与性质，几乎完全就是平行地搬过来。主要内容如下：,定义7.2.1 给定两个半群与，则 半群半群:=(f)(fTS(x)( y)(x，ySf(xy)=f(x)f(y) 并称f为从到的半群同态映射。 由定义可以知道，半群同态映射f可以不是唯一的。,与前面的定义类似，根据半群同态映射f是单射(一对一)、满射、双射，把半群同态映射f分别定义半群单一同态映射、半群满同态映射和半群同构映射。 如果两个半群，存在一个同构映射，则称一个半群同构于另一个半群。 由于代数结构之间
5、的满同态具有保持运算的各种性质，对于半群满同态当然完全适用。,下面给出一个半群同态保持等幂性的定理。 定理7.2.1 如果f为从到的半群同态映射，对任意aS且aa=a，则f(a)f(a)=f(a)。,由于半群同态映射是个函数，因此可对半群同态映射进行复合运算，从而产生新的半群同态映射。请看如下定理： 定理7.2.2 如果g是从到的半群同态映射，h是从到的半群同态映射，则h o g是从到的半群同态映射。,定义7.2.2 若g是从到的半群同态映射，则称g为半群自同态映射；若g是从到的半群同构映射，则称g为半群自同构映射。,定理7.2.3 给定半群，如果A=g|g为到的半群自同态映射且o是函数复合运
6、算，则为半群。 由于恒等映射i是复合运算o的幺元，因此可得下面定理：,定理7.2.4 给定半群，若B=h|h为到的半群自同构映射，o为函数复合运算，则是独异点。 定理7.2.5 给定半群，又是从S到S的所有函数在复合运算o下构成的函数半群，则存在从到的半群同态映射g，或者说半群同态于。,上面介绍半群同态及有关定理。下面接着来讨论独异点之间的同态及其有关定理。 定义7.2.3 给定独异点和，则 :=(g)(gTM(x)( y)(x，yMg(xy) =g(x) g(y)g(eM)=eT 并称g为从到的独异点同态映射。,注意，独异点同态区别半群同态就在于保持幺元，即g(eM)=eT。因此，半群同态未
7、必是独异点同态，反之都真。 对于独异点满同态、独异点单同态、独异点同构、以及独异点满同态保持运算性质等，这里也一并略去了。下面给出一个有关同构的定理以结束本节。,定理7.2.6 给定独异点，则存在TMM，使。 本定理表明，一个独异点可与复合运算下的函数独异点同构。,7.3 积半群,把积代数方法应用于特殊一类代数结构：半群，便产生积半群。,定义7.3.1 给定两个半群和。称为和的积半群，其中ST为集合S与T的笛卡儿积，运算定义如下： =，其中s1，s2S，t1，t2T 由于运算是经和定义的，易知，积半群是个半群。,不难证明下列定理： 定理7.3.1 若半群和是可交换的，则也是可交换的。 定理7.
8、3.2 给定半群和，且e1和e2分别是它们的幺元，则积半群含有幺元。换言之，若和是独异点，则是独异点。,定理7.3.3 给定半群和，且1和2分别为它们的零元，则积半群含有零元。 定理7.3.4 给定半群和，且s的逆元s-1，tT的逆元t-1，则积半群中的逆元是。,7.4 群的基本定义与性质,定义7.4.1 给定，若是独异点且每个元素存在逆元，或者是可结合的，关于存在幺元，G中每个元素关于是可逆的，则称是群。 可见，群是独异点的特例，或者说，群比独异点有更强的条件。,定义7.4.2 给定群，若G是有限集，则称是有限群。并且把G的基数称为该有限群的阶数，若集合G是无穷的，则称为无穷群。,由群的定义
9、可知，群具有半群和独异点的性质，这里不再重复罗列了，而且群还有自己独特的性质，仅此讨论如下： 定理7.4.1 是群|G|1无零元。 定理7.4.2 是群中的唯一等幂元是幺元。,定理7.4.3 给定群，则有 (a)(b)(c)(a，b，cG(ab=acba=ca)b=c) 即群满足可约律。,定理7.4.4 给定群，则 (a)(b)(a，bG(!x)(xGax=b)(!y)(yGya=b) 或(a)(b)(a，bG(!x)(!y)(x，yG(ax=bya=b) 即群中方程解是唯一的。,定理7.4.5 是群(a)(b)(a，bG(ab)-1=b-1a-1) 定义7.4.3 给定群，若是可交换的，则称
10、是可交换群或是Abel群。 定理7.4.6 给定群，则 为Abel群(a)(b)(a，bG(ab)2=a2b2,定义7.4.4 给定群，且aG，幺元e，则a的阶或周期为n:=(k)(kI+ ak=e=n)，并称a的阶是有限的；否则，a的阶是无穷的。,定理7.4.7 给定群，且aG的阶n是有限的，则 (m)(mI+k=mn)ak=e 推论：若an=e且没有n的因子d(1dn)使ad=e，则n为a的阶。 定理7.4.8 给定群及aG，则a与a-1具有相同的阶。,7.5 置换群和循环群,本节里，将讨论群论中两种常见而又重要的群：置换群和循环群，特别在研究群的同构群时，置换群扮演着极重要的角色。 在正
11、式讨论置换群以前，需要先作些必要的准备。,定义7.5.1 令X是非空有穷集合，从X到X的双射，称为集合X中的置换，并称|X|为置换的阶。 若X=x1，x2，xn，则n阶置换表为,并称 为置换中的反置换，记为p-1。特别把置换 称为X中的幺置换或恒等置换，记为pe。,此外，用PX表示集合X中的所有置换的集合。 为了说明n个元素的集合可以有多少不同的置换，特给出如下定理： 定理7.5.1 若X=x1，x2，xn，则|PX|=n!,定义7.5.2 给定集合X且pi，pjPX，由X的元素先进行置换pi后继之作置换pj所得到的置换，表为pipj，称pipj是置换pi和pj的复合，是复合置换运算。 可以看
12、出，若把置换看成一种特殊关系时，复合置换pipj就是复合关系piopj，常称之右复合；又若把置换看成函数时，那么复合置换又可表成如下的复合函数即所谓左复合： pipj=pj o pi， 其中o表示函数的复合 于是，对于xX有： (pipj)(x)=(pj o pi)(x)=pj(pi(x),由定义7.5.1可知，置换即是双射，亦即1-1函数，故PX中的元素满足下列四个性质： (1) (p1)(p2)(p1,p2PXp1p2PXp2p1PX) (2) (p1)(p2)(p3)(p1,p2,p3PX(p1p2)p3=p1(p2p3),(3) (pe)(pePX(p)(pPXpep=ppe=p) (
13、4) (p)(pPX(p-1)(p-1PXpp-1=p-1p=pe) (1)表明PX对于是封闭的；(2)表明PX对于是可结合的；(3)表明PX中有幺置换；(4)表明PX中每个置换都有反置换。因此，可知是一个群，并称它为对称群，习惯上记为。若QPX=S|X|，则称由Q和构成的群为置换群。,对称群独立于集合X中各个元素，但却依赖于集合X中的元素个数。这就是说，任何三个其它元素的集合都会生成“同样”的置换，这就是为什么将对称群写成，即的理由。此外，把集合X的基数称为对称群的次数。因此，是三次六阶群，因为|S3|=3!=6。,一般地说来，由n个元素的集合而构成的所有n!个n阶置换的集合Sn与复合置换运
14、算构成群，它便n次n!阶对称群。 应该注意，置换群一般都不是对称群，因为它并不要求一定要包括全部给定阶的置换。例如，三次置换群和都不是对称群，其中p1,p2,p5,p6S3。,若说置换是个关系即有序对集合，那么由置换和构成置换群，它会确立怎样的二元关系呢？下面就来回答这个问题。 定义7.5.3 令是一置换群且QS|X|。称R=所诱导的X上的二元关系。,定理7.5.2 由置换群诱导的X上的二元关系是一等价关系。 定理7.5.3 在有限群中，每行或每列都是G中元素的置换。,一阶群仅有幺元，即。 二阶群除幺元e外，还有一个元素，比如a，则有，其运算表如表7.5.2。由定理7.5.3可知，不可能再有其
15、它运算表。在此预先指出，所有的二阶群都与该群同构。,三阶群，可令，其运算表如表7.5.3。由定理7.5.3知，不可能再有别的运算表。同样，任何三阶群都与它同构。 从运算表可以看出，所有二阶群和三阶群都是Abel群。事实上，四、五阶群也是Abel群，但六阶群未必都是Abel群。,上面讲了由有限集合X到X的双射即置换，以及置换群；下面不再限于X是有限集，换言之，它可以是个无穷集。这时从集合X到X的双射，称之为一一变换或变换。如果令TX表示所有从集合X到X的变换的集合，则显然有TXXX，并且TX类似PX所具有的四条性质，具体如下： (1) (f)(g)(f,gTXfog,gofTX) (2) (f)(g)(h)(f,g,hTX(fog)oh=fo(goh) (3) (i)(iTX(f)(fTXiof=foi=f (4) (f)(fTX(f-1)(f-1TXfof-1=f-1of=i),因而，可证构成群，在代数中称为变换群，显然，置换群是变换群的特例。 请注意，由TX中的一些变换与运算o构成的群，都称为变换群，而只不过是个特殊情形而已。,最后，介绍循环群。 定义7.5.4 给定群及I为整数集合
