清华离散数学(第2版):14.3.1-2
14.3 几个典型的代数系统 14.3.1 半群与独异点 14.3.2 群 14.3.3 环与域 14.3.4 格与布尔代数1 半群与独异点的定义与实例 半群与独异点的幂运算 半群与独异点的子代数和积代数 半群与独异点的同态半群与独异点2半群与独异点的定义定义14.12 (1) 设 V=是代数系统, 为二元运算,如果 运算是可结合的,则称 V 为半群.(2) 设 V=是半群,若 eS 是关于 运算的单位元,则称 V 是含幺半群,也叫做独异点. 有时也将独异点 V 记作 V=. 3实例例1 (1) ,是半群,+是普通加法, 其中除外都是独异点.(2) 设n是大于1的正整数,和都是半群和独异点,其中+和·分别表示矩阵加法和矩阵乘法.(3) 为半群,也是独异点,其中为集合的对称差运算.(4) 为半群,也是独异点,其中Zn=0,1, , n1,为模n加法. (5) 为半群,也是独异点,其中为函数的复合运算.(6) 为半群,其中R*为非零实数集合,运算定义如下:x, yR*, xy = y. 4定义 (1) 在半群中,xS,规定: x1=x, xn+1=xnx,nZ+ (2)在独异点中,xS, x0=e, xn+1=xnx, nN 用数学归纳法不难证明 x 的幂遵从以下运算规则: xnxm=xn+m, (xn)m= xnm, 在半群中 m, nZ+,在独异点中m, nN,半群与独异点的幂运算5半群与独异点的子代数定义 半群与独异点的子代数分别称为子半群与子独异 点. 判定方法: 设V=是半群,TS,T 非空,如果T 对V 中的运算封闭,则是V的子半群. 设V=是独异点,TS,T 非空,如果T 对V 中的 运算封闭,而且 eT,那么 构成 V 的子独异点 . 6是T 的单位元,T 本身可以构成独异点,但不是V2 的子独异点,因为V2的单位元是 e. 实例设半群 V1=,独异点 V2=. 其中·为矩阵乘法,e 为2阶单位矩阵, 且 , 则TS,且T 是V1=的子半群. 7半群与独异点的同态定义14.13(1) 设V1=,V2=是半群,f :S1S2. 若 对任意的 x, yS1有 f (xy) = f (x)f (y) 则称 f 为半群V1到V2的同态映射,简称同态.(2) 设V1=,V2=是独异点,f :S1S2. 若对任意的 x, yS1有 f(xy) = f(x)f(y) 且 f(e1)= e2,则称 f 为独异点V1 到V2 的同态映射,简称同态.8实例则 f 是半群V1=的自同态,但不是独异点V2= 的自同态,因为 f(e)e. 设半群 V1=,独异点 V2=. 其中·为矩阵乘法,e 为2阶单位矩阵, 且 令9群 群的定义与实例 群中的术语 群的性质 子群的定义及判别 群的同态与同构 循环群 置换群10群的定义与实例定义14.14 设是代数系统, 为二元运算. 如果 运算 是可结合的,存在单位元 eG,并且对 G 中的任何元素 x 都有x1G,则称 G 为 群.实例 (1) ,都是群;和不是群. (2) 是群,而不是群. (3) 是群,为对称差运算. (4) ,也是群. Zn= 0,1, , n1,为模 n 加. 11Klein四元群设 G = e, a, b, c ,G上的运算由下表给出,称为 Klein四元群 e a b ceabce a b ca e c bb c e ac b a e 运算表特征: 对称性-运算可交换 主对角线元素都是幺元-每个元素是自己的逆元 a, b, c 中任两个元素运算 都等于第三个元素.12群中的术语定义14.15(1) 若群 G 是有穷集,则称G是有限群,否则为无限群. 群 G 中的元素个数称为群G的 阶,有限群 G 的阶记作|G|. (2) 若群G中的二元运算是可交换的,则称G为交换群或 阿贝尔(Abel)群. 实例:和 是无限群是有限群,也是 n 阶群 Klein四元群是 4 阶群 上述群都是交换群n 阶 (n2) 实可逆矩阵集合关于矩阵乘法构成的群是非交换群. 13群中的术语(续)定义14.16 设G是群,xG,nZ,则 x 的 n 次幂 xn 定义为实例 在中有 23=(21)3=13=111=0 在 中有 (2)3=23=2+2+2=6 14定义14.17 设G是群,xG,使得等式 xk = e 成立的最 小 正整数 k 称为 x 的阶(或周期),记作 |x| = k,称 x为 k 阶元. 若不存在这样的正整数k,则称 x 为无限阶元.实例 在中,2 和 4 是 3 阶元,3 是 2 阶元,1 和 5 是 6 阶元0 是 1 阶元 在中,0 是 1 阶元,其它整数的阶都不存在. 群中的术语(续)15群的性质-幂运算规则定理14.3 设 G 为群, 则 G 中的幂运算满足: (1) xG,(x1)1 = x. (2) x, yG,(xy)1 = y1x1. (3) xG,xnxm = xn+m,n, mZ. (4) xG,(xn)m = xnm,n, mZ. (5) 若G为交换群,则(xy)n = xnyn.证 (1) (x1)1是x1的逆元,x也是x1的逆元. 根据逆元的 惟一性,等式得证. (2) (y1x1)(xy)= y1(x1x)y = y1y = e, 同理 (xy)( y1x1)=e,故y1x1是 xy 的逆元. 根据逆元的惟 一性等式得证.16 等式(5)只对交换群成立. 如果G是非交换群,那么群的性质-幂运算规则(续)说说明: (3) (4) (5) 的证明:用数学归纳法证明对于自然数n和m证等式为真,然后讨论 n 或 m 为负数的情况. (2) 中的结果可以推广到有限多个元素的情况,即 17群的性质-群方程存在唯一解定理14.4 G为群,a,bG,方程 ax=b 和 ya=b 在G 中有解且仅有惟一解. 证 a1b 代入方程左边的 x 得a (a1b) = (a a1) b = eb = b 所以 a1b 是该方程的解. 下面证明唯一性. 假设 c 是方程 ax = b 的解,必有 ac = b,从而有c = ec = (a1a)c = a1(ac) = a1b 同理可证 ba1 是方程 ya = b 的唯一解. 例 设群 G=,其中为对称差. 群方程aX=, Ya,b=b 的解 X=a1=a=a, Y=ba,b1=ba,b=a 18群的性质-消去律定理14.5 G为群,则G中适合消去律,即对任意 a,b,cG 有(1) 若ab=ac,则b=c.(2) 若ba=ca,则b=c. 证 (1) ab=ac a1(ab)=a 1(ac) (a1a)b=(a1a)c b=c (2) 同理可证. 例1 设 G=a1, a2, , an 是 n 阶群,令aiG = ai aj | j =1,2, , n 证明 aiG = G. 证 由群中运算的封闭性有 aiGG. 假设aiGG,即|aiG| 的子群. 当 n1 时, nZ 是 Z 的真子群.对任何群 G 都存在子群. G 和e都是 G 的子群,称为G 的平凡子群. 22子群判定定理判定定理一 定理14.7 设 G 为群,H 是 G 的非空子集. H 是 G 的子群 当 且仅当 a, bH 有 abH,aH 有 a1H. 证 必要性显然,只证充分性. 由于H非空,存在 a 属于H, 因此有a1属于H. 根据已知 必有 aa1属于H, 即 e 属于H. H 满足子群定义. 实例 nZ 是整数加群 的子群. 显然 nZ是 Z 的非空子集. 因为 n 属于 nZ. 任取 nk, nl 属于 nZ,nk+nl = n(k+l),n(k+l)nZ,nknZ 根据判定定理,nZ 是整数加群的子群. 23子群判定定理(续)判定定理二 定理14.8 设 G 为群,H 是 G 的非空子集. H 是 G 的子群 当 且仅当 a,bH 有 ab1H. 证明 只证充分性. 由于 H 非空,必有 xH. 由已知有 xx1H,从而得到 eH. 任取 H 中元素 a, 由 e,aH 得 ea 1H,即a1H. 任取 a,bH, 必有 b1H,从而得到a(b1)1H,即 abH. 根据判定定理一得证. 24重要子群的实例生成子群 定义 设 G 为群,aG,令 H = ak | kZ ,则 H 是 G 的子群,称为由 a 生成的子群,记作.证 首先由 a 知道. 任取am,al,则am(al)1 = amal = aml根据判定定理可知G.实例:整数加群,由2生成的子群是 = 2k | kZ = 2Z群中,由2生成的子群 = 0, 2, 4 Klein四元群G = e, a, b, c 的所有生成子群是:= e , = e, a , = e, b , = e, c . 25群G 的中心C: 设G 为群, C = a | aGxG(ax=xa),则 C 是 G 的 子 群,称为 G 的中心. 证 eC. C是G的非空子集. 任取 a, bC,只需证明 ab1与 G 中所有的元素都可交换 . xG,有 (ab1)x = ab1x = ab1(x1)1 = a(x1b)1 = a(bx1)1= a(xb1) = (ax)b1 = (xa)b1 = x(ab1) 由判定定理可知CG.对于阿贝尔群G,G的中心就等于 G. 对某些非交换群 G,它的中心是 e . 重要子群的实例(续)26子群格定义 设 G 为群,令S=H| HG是 G 的所有子群的集 合,定义 S 上的偏序,x,yS, xyxy,那么 构 成格,称为为 G 的子群格.实实例 Klein四元群 G 和的子群格如下图图所示27群同态的定义与分类定义14.19 设G1,G2是群,f :G1G2,若a,bG1都有f(a b) = f(a) f(b)则称 f 是群G1到G2的同态映射,简称同态. 如果同态 f 为单射函数,则称为单同态; 如果是满射函数,则称为满同态,记作G1G2;如果是双射函数,则称为同构,记作G1G2. 28群同态的实例例4 (1) G1=是整数加群,G2=是模n的整数加 群. 令 f :ZZn,f (x)= x mod n, f 是G1到G2的满同态. x,yZf(x+y) = (x+y)mod n = x mod n ymod n = f(x)f(y)(2) 设G=是模n整数加群,可以证明恰有n个G的自同态,即 fp:ZnZn, fp(x)=(px)mod n,p=0,1, , n1 (3) 设G1,G2是群,e2是G2的单位元. f:G1G2,f(a) = e2, aG1. 则 f 是G1到G2的同态,称为零