离散数学半群与群

14
2．群方程存在惟一解 定理11.2 G为群，∀ a,b∈G，方程ax=b 和ya=b在G中 有解且仅有惟一解. 证 a− 1b代入方程左边的x 得 a(a− 1b) = (aa− 1)b = eb = b 所以a− 1b是该方程的解. 下面证明惟一性. 假设c是方程ax=b的解，必有ac=b，从而有 −1 −1 −1 c = ec = (a a)c = a (ac) = a b 同理可证b a− 1是方程ya=b的惟一解. 例 设群G=<P({a,b}),⊕>，其中⊕为对称差. 解下列 群方程： {a}⊕X=∅，Y⊕{a,b}={b} −1 −1 解 X={a} ⊕ ∅ ={a} ⊕ ∅ ={a} ， Y={b} ⊕ {a,b} ={b} ⊕ {a,b}={a} 15
6
五、半群与独异点的同态映射
1．定义 定义11.3 （1） 1=<S1,◦>, V2=<S2,∗>是半群， S1→S2. 设V ϕ： 若对任意x,y∈S1 有 ϕ (x◦y)= ϕ (x)∗ ϕ (y) 则称ϕ为半群V1到V2的同态映射，简称同态. （2） 设V1=<S1,◦,e1>,V2=<S2,∗,e2>是独异点， S1→S2. ϕ: 若对任意x, y∈S1有 ϕ (x◦y)= ϕ (x)∗ ϕ (y) 且 ϕ (e1)= e2, 则称 ϕ 为独异点 V1 到 V2 的同态映射，简称同态.
第十一章 半群与群 第一节 半群与独异点
一、半群与独异点的定义
1．定义11.1 （1）设V=<S,◦>是代数系统，◦为二元运算，如果◦运算 是可结合的，则称V 为半群. （2）设 V=<S,◦>是半群，若 e∈S 是关于◦运算的单位元， 则称 V 是含幺半群， 也叫做独异点. 有时也将独异点 V 记 作 V=<S,◦,e>.
21
−1
定理11.7 （判定定理三） 设G为群，H是G的非空有穷子集，则H是G的子群当且 仅当∀ a,b∈H 有ab∈H. 证 必要性显然. 为证充分性， 只需证明a∈H有a− 1∈H. 任取a∈H, 若a = e, 则a− 1 = e∈H. 若a≠e，令S={a,a ,…}，则S⊆ H. 由于H 是有穷集，必有ai = aj（i<j）.根据G 中的消 去律得 a
7
2．实例 设半群V1=<S,·>，独异点V2=<S,·,e>. 其中·为矩阵 乘法，e为2 阶单位矩阵,
a 0 S | a, d R 0 d
令
a 0 a 0 ( ) 0 0 ， 0 d
ϕ 是半群 V1 的自同态， 不是独异点 V2 的自同态， ϕ 因为它 没有将 V2 的单位元映到 V2 的单位元.
19
二．子群的判定定理
定理11.5 （判定定理一） （1）∀ a,b∈H 有ab∈H. （2）∀ a∈H 有a ∈H. 证 必要性是显然的. 为证明充分性，只需证明e∈H. 因为 H 非空，存在 a∈H. 由条件（2）知 a− 1∈H，根据 条件（1）a a− 1∈判定定理二） 设G为群，H是G的非空子集. H是G 的子群当且仅当∀ a,b∈H 有ab− 1∈H. 证 必要性显然. 只证充分性. 因为H非空，必存在a∈H.根据给定条件得aa− 1∈H，即e ∈H. 任取a∈H, 由e,a∈H 得 ea− 1∈H，即a− 1∈H. 任取a,b∈H，知b ∈H. 再利用给定条件得 a(b− 1) − 1∈H，即ab∈H. 综合上述，可知 H 是 G 的子群.
13
二、群的性质
1．群的幂运算规则 定理11.1 设G 为群，则G 中的幂运算满足： （1）∀ a∈G，(a− 1)− 1=a. −1 −1 −1 （2）∀ a,b∈G，(ab) =b a . （3）∀ a∈G，anam=an+m，n,m∈Z. （4）∀ a∈G，(an)m=anm，n,m∈Z. （5）若G 为交换群，则(ab)n=anbn. 证（1）(a− 1)− 1 是a− 1 的逆元，a 也是a− 1 的逆元. 根 据逆元的唯一性，等式得证. −1 −1 −1 −1 −1 （ 2 ） (b a )(ab)= b (a a)b = b b = e, 同 理 (ab)( b− 1a− 1)=e，故 b− 1a− 1 是 ab 的逆元. 根据逆元的唯 一性等式得证.
18
第三节 子群
一、子群的定义
定义11.8 设G是群，H是G的非空子集，如果H关于G中 的运算构成群，则称H是G 的子群, 记作H≤G.若H是G的子 群，且H⊂ G，则称H是G的真子群，记作H<G. 例 nZ（n 是自然数）是整数加群〈Z,+〉的子群. 当 n≠1 时,nZ 是 Z 的真子群.对任何群 G 都存在子群. G 和{e}都 是 G 的子群，称为 G 的平凡子群.
4
2．实例 例 设半群V1=<S,·>，独异点V2=<S,·,e>. 其中·为 矩阵乘法，e 为2 阶 单位矩阵,
a b S | a, b, c, d R c d a 0 T | a R 0 0
1 0 则 T⊆ S，且 T 是 V1=<S,·>的子半群. 是 T 的单位 0 0
例 设G是群，a,b∈G是有限阶元. 证明 （1）|b− 1ab| = |a| （2）|ab| = |ba| 证（1）设 |a| = r，|b− 1ab| = t，则有 −1 r −1 r −1 (b ab) = b a b = b b = e 从而有t|r. 另一方面，由a = (b− 1) − 1 (b− 1ab)b− 1 可知 r|t. 从而有 −1 |b ab| = |a|. （2）设 |ab| = r，|ba| = t，则有 (ab)t+1 = a(ba)t b = ab t 由消去律得 (ab) = e，从而可知，r|t. 同理可证 t|r. 因此 |ab| = |ba|.
1
2．实例 + 例：（1）<Z ,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群， +是普通加法. 这些半群中除<Z+,+>外都是独异点. （2）设n 是大于1 的正整数，<Mn(R),+>和<Mn(R),·> 都是半群，也都是独异点，其中+和·分别表示矩阵加法 和矩阵乘法. （3）<P(B),⊕>为半群，也是独异点，其中⊕为集合的 对称差运算. （4）<Zn, ⊕>为半群，也是独异点，其中 Zn={0,1,…,n−1}，⊕为模n加法. （5）<AA, ◦>为半群，也是独异点，其中◦为函数的复合 运算. （6）<R*,◦>为半群，其中R*为非零实数集合，◦运算定 义如下： ∀ x,y∈R*, x◦y=y 2
12
定义11.7 设G是群，a∈G，使得等式ak=e成立的最小正 整数k称为a的阶，记作|a|=k，称a为k阶元.若不存在这样 的正整数k，则称a为无限阶元. 在<Z6,⊕>中， 和4 是3 阶元， 是2 阶元， 和5 是 2 3 1 6 阶元，0 是1 阶元. 在<Z,+>中，0 是 1 阶元，其它整数的阶都不存在.
元，T 构成独异点，但不是 S 的子独异点，因为 S 的单 位元是 e. 5
四、半群与独异点的直积
定义11.2 设V1=<S1,◦ >，V2=<S2,∗>是半群(或独异点)， 令S=S1×S2，定义S 上的·运算如下：∀ <a,b>,<c,d>∈S, <a,b> · <c,d> = <a◦c,b∗d> 称<S,·>为V1 和V2 的直积，记作V1×V2. 不难证明 V1×V2 是半群.若 V1 和 V2 是独异点，其单位元分 别为 e1 和 e2，则<e1,e2>是 V1×V2 中的单位元，因此 V1×V2 也是独异点.
（3） 若群 G 中的二元运算是可交换的， 则称 阿贝尔 (Abel) 群.
例： <Z,+>和<R,+>是无限群， n,⊕>是有限群， <Z 也是n 阶 群.Klein 四元群是4 阶群.<{0},+>是平凡群. n 阶(n≥2) 实可逆矩阵集合关于矩阵乘法构成的群是非交换群.
11
定义11.6 设G是群，a∈G，n∈Z，则a的n次幂.
3
三、子半群与子独异点
1. 定义与判别方法 半群的子代数叫做子半群，独异点的子代数叫做子独 异点. 子半群的判别方法： V=<S,◦>是半群，T⊆ S，T 非空，如果T 对V 中的运算 ◦封闭，则<T,◦>是V 的子半群. 子独异点的判别方法： V=<S,◦,e>是独异点，T⊆ S，T 非空，如果 T 对 V 中的运 算◦封闭，而且 e∈T，那么<T,◦,e>构成 V 的子独异点.
二、半群与独异点的性质
1．半群<S,◦>中的幂 可以定义元素的幂，对任意x∈S，规定： x1=x xn+1=xn◦x, n∈Z+ 用数学归纳法不难证明x 的幂遵从以下运算规则： xn◦xm=xn+m n m nm + (x ) = x m,n∈Z 2．独异点<S,◦,e>中的幂 对于任意的x∈S，可以定义x 的零次幂，即 0 x =e xn+1=xn◦x n∈N 独异点的幂运算也遵从半群的幂运算规则，其中m 和n 是自然数.
e n 0, a n a n 1 a n0 (a 1 ) m n 0, n m
群中元素可以定义负整数次幂. 在<Z3,⊕>中有 2− 3 = (2− 1)3 = 13 = 1⊕1⊕1 = 0 在<Z,+>中有 (− 2)