几个典型的代数系统教程文件.doc

几个典型的代数系统精品文档第六章 几个典型的代数系统本章讨论几类重要的代数结构：半群、群、环、域、格与布尔代数等我们先讨论最简单的半群 6.1 半群 定义 6.1 称代数结构为半群（semigroups），如果 * 运算满足结合律当半群含有关于 * 运算的么元，则称它为独异点（monoid），或含么半群 例6.1 ，都是半群，后两个又是独异点 半群及独异点的下列性质是明显的定理6.1 设为一半群,那么（1）的任一子代数都是半群，称为的子半群 （2）若独异点的子代数含有么元e,那么它必为一独异点,称为的子独异点 证明简单，不赘述 定理6.2 设,是半群,h为S到S的同态,这时称h为半群同态对半群同态有 （1）同态象为一半群 （2）当为独异点时，则为一独异点. 定理6.3 设为一半群,那么 （1）为一半群，这里SS为S上所有一元函数的集合， 为函数的合成运算 （2）存在S到SS的半群同态 证（l）是显然的 为证（2）定义函数h:SSS：对任意aS h（a）= fa fa：SS 定义如下: 对任意xS， fa（x）= a*x 现证h为一同态对任何元素a,bS h(a*b)fa*b （l11） 而对任何xS， fa*b（x）= a*b*x = fa（fb（x）= fafb （x） 故fa*b = fafb ,由此及式（l11）即得 h（a*b）= fa*b = fafb h（a） h（b）本定理称半群表示定理。它表明，任一半群都可以表示为（同态于）一个由其载体上的函数的集合及函数合成运算所构成的半群。这里同构于 - 的一个子代数6.2 群群是最重要的代数结构类，也是应用最为广泛的代数结构类.我们以后要深入研究的代数结构环和域也都是以群为基础的.6.2.1 群及其基本性质 定义6.6 称代数结构为群（groups）,如果 （1）为一半群 （2）中有么元e. （3）中每一元素都有逆元 或者说，群是每个元素都可逆的独异点群的载体常用字母G表示 ，因而字母G也常用于表示群 定义 6.7 设 为一群 （1）若 * 运算满足交换律，则称G为交换群或阿贝尔群（Abel group）阿贝尔群又称加群，常表示为（这里的 + 不是数加，而泛指可交换二元运算回忆: *常被称为乘）加群的么元常用0来表示，常用-x来表示x的逆元. （2） G为有限集时，称G为有限群（finite group）,此时G的元素个数也称G的阶（order）；否则，称G为无限群（infinite group） 例6.6 （1）（整数集与数加运算）为一阿贝尔群（加群）,数0为其么元.不是群因为所有非零自然数都没有逆元. （2）（正有理数与数乘）为一阿贝尔群，1为其么元. 不是群，因为数0无逆元 （3）为一k阶阿贝尔群, 数0为其么元 . （4）设P为集合A上全体双射函数的集合， 为函数合成运算.那麽 为一群A上恒等函数E A为其么元。一般不是阿贝尔群. 群的下列基本性质是明显的. 定理1l.9 设为群，那麽 （1）G有唯一的么元，G的每个元素恰有一个逆元 （2）关于x的方程a*xb，x*ab都有唯一解（3）G的所有元素都是可约的因此，群中消去律成立：对任意a,x,ySa*x = a*y 蕴涵 x = y ; x*a = y*a 蕴涵 x = y （4）当G e时, G无零元（5）么元e是G的唯一的等幂元素. 证（1）,（2）,（3）是十分明显的 （4）若G有零元,那么它没有逆元，与G为群矛盾。（注意，G = e时,e既是么元，又是零元.）（5）设G中有等幂元x，那么 x*x = x 又 x = x*e 所以 x*x = x*e 由（3）得x = e 。由（3）我们得知，特别地，当G为有限群时，* 运算的运算表的每一行（列）都是G中元素的一个全排列从而有限群的运算表中没有一行（列）上有两个元素是相同的因此，当G分别为1，2，3阶群时, * 运算都只有一个定义方式(即,不计元素记号的不同,只有一张定义 * 运算的运算表,如表6.2所示),于是可以说,1,2,3阶的群都只有一个. 定理6.10对群的任意元素 a,b， （1）(a-1)-1a（2）(a*b) -1b-1*a-1 （3）(ar) -1 = (a1)r（记为ar）（r为整数） 证（2）(a*b) *(b-1*a-1) = a*(b *b-1)*a-1 = e (b-1*a-1)*(a*b) = b-1*(a-1*a)*b = e 因此a*b的逆元为b-1*a-1，即(a*b) -1b-1*a-1（3）对r归纳.r = 1时命题显然真.设(ar) -1 = (a1)r,即(a1)r 是ar的逆元.那么 ar+1*(a1)r+1 = ar*(a*a-1)*(a1)rar*(a1)r = e (a1)r+1* ar+1 = (a1)r*(a-1*a)* ar(a1)r* ar = e 故ar+1 的逆元为(a1)r+1，即(ar+1) -1 = (a1)r+1归纳完成, （2）得证. 对群的任意元素 a,我们可以定义它的幂：a0=e，对任何正整数m，am+1=am*a，又据定理6.1O，在群中可引入负指数幂的概念：a-m= (a-1)m，且容易证明: 定理6.11 对群的任意元素 a,b，及任何整数m，n, （l）a m*a n = am+n （2）(a m) n = amn 如果我们用aG和Ga分别表示下列集合aG = a*g | gG， Ga = g*a | gG那么我们有以下定理 定理 6.12 设为一群,a为 G中任意元素，那么aG = G = Ga特别地，当G为有限群时，* 运算的运算表的每一行（列）都是G中元素的一个全排列证 aG G是显然的 设 gG，那么a1*gG，从而a*(a1*g) aG，即 gaG因此 GGa aG = G得证Ga = G同理可证这一事实的一个明显推论是：当G为有限群时，* 运算的运算表的每一行（列）都是G中元素的一个全排列.从而有限群的运算表中没有一行（列）上有两个元素是相同的因此，当G为1，2，3阶群时, * 运算都只有一个定义方式(即,不计元素记号的不同,只有一张定义 * 运算的运算表,如表6.2所示),于是可以说,1,2,3阶的群都只有一个. 表6.2*e*ea*eabEeeeaeeabaaeaabebbea 对群还可以引入元素的阶的概念. 定义6.8 设为群，aG，称 a 的阶(order)为n，如果an = e,且n为满足此式的最小正整数.上述n不存在时,称a有无限阶.例6.7(1) 任何群G的幺元e的阶为1, 且只有幺元e的阶为1。(2) 中幺元0的阶为1，而整数a 1 0时,a有无限阶.(3) 中1的阶是6,2的阶是3,3的阶是2,4的阶是3,5的阶是6. 关于元素的阶有以下性质. 定理6.13 有限群G的每个元素都有有限阶,且其阶数不超过群G的阶数 | G | .证 设a为G的任一元素,考虑 e = a0 ,a1 ,a2 , ,aG这 | G |+1个G中元素.由于G中只有 | G |个元素,因此它们中至少有两个是同一元素,不妨设 ar = as (0 r s | G | )于是as-r = e,因此a有有限阶,且其阶数至多是s-r,不超过群G的阶数| G | .定理6.14 设为群,G中元素a的阶为k,那么,an = e当且仅当k整除n .证 先证充分性 设 ak e，k整除n，那么n = kr（r为整数），因为ak e，所以an = akr = (ak )r = e r = e 。 再证必要性 设 an e，n = mk r，其中m为n除以 k的商，r为余数，因此0 rk 。于是eanamk+ramk*arar因此,由k的最小性得r = 0，k整除n 定理6.15 设为群，a为G中任一元素，那么a与a-1具有相同的阶证 只要证 a具有阶n当且仅当a-1具有阶n 。由于逆元是相互的，即(a-1)-1a，同此只需证：当a具有阶n时，a-1 也具有阶n 。 设a的阶是n，a-1的阶是m 。由于(a-1)n(an)-1e -1 e 故mn 。又因为a m(a-1)m)-1 e -1 e 故nm 。因此，nm 。6.2.2 子群、陪集和拉格朗日定理定义6.9 设为群称为G的子群(subgroups)，如果为G的子代数 ，且为一群 子群有下列特征性(判别法) 定理6.16设为群，那么为子群的充分必要条件是 （l）G的么元eH （2）若a，bH ，则a*bH （3）若aH，则a-1H 证 先证必要性 设H为子群那么（2）是显然的（因H为子代数）为证（l）,设的么元为e,那么e* e= e。由于在G中只有e是等幂元,故e = e , eH得证 .为证（3）设中任一元素a的H中逆元为b,那么a*b = b*a = e,由逆元的唯一性,b就是a在G中的逆元,即b = a-1H. 充分性是明显的.事实上只要条件（2），（3）便可使为子群,因为H不空时条件（2）（3）蕴涵条件（l）.因此，可用（2）,（3）来判别非空子集H是否构成G的子群。 显然,对任何群G , 及均为其子群,它们被称为平凡子群,其它子群则称为非平凡子群或真子群 例6.8 （l）群有非平凡子群 和 （2）设EI,E为偶数集。那么为的子群,但不是的子群.对于有限群,子群的判别更为简单.定理6.17 设为有限群,那么当G的非空子集H对 * 运算封闭时, 即为G的子群.证 由于G为有限群,H必为有限集.设 | H | = r,aH.考虑 a1 ,a2 , ,ar+1, 它们都在H中(H对*运算封闭),因此必定有ai = aj (0 i j r+1 ),从而aj-i = e,故eH .若H =e,为G的子群得证.若H e,设a为H中任一不同于e的元素.同上可证,有k2使ak = e,从而有 a*ak-1 = ak-1*a = e因此, ak-1= a-1 H. 据定理6.16,为G的子群得证 由于我们采用的上述证明方法仅仅依赖H的有限性,可见本定理可加强为:设为群，H为G的非空有限子集，且H对 * 运算封闭,那么为的子群.和子群概念直接相关的是陪集的概念 定义6.10 设为的子群，那么对任一 gG，称gH为H的左陪集(left coset) 称Hg为H的右陪集(right coset).这里 gH = g*h | hH ，Hg = h*g | hH 关于左（右）陪集我们有以下定理 定理6.18 设为的子群，那麽 （1）当gH时， gH = H（Hg = H）。 （2）对任意gG，| gH | = | H |（ | Hg | = | H | ）. 证（l）由定理6.12立得. 为证（2），只要证H与gH之间存在双射定义函数f:HgH如下:对任何一hH， f（h）= g*h设h1h2 ，那么f（h1）= g*h1,f（h2）= g*h2，若f（h1）= f（h2），那么由可约性即得h1=h2，与h1h2矛盾f为单射得证.f为满射是显然的.因此f为双射| gH | = | H | 得证同理可证 | Hg | = | H | 定理ll.19 设为的子群，a，bG，那么,或者aH = bH（Ha = Hb），或者aHbH = （HaHb = ） I 证 设aHbH ，那么有h1,h2H使得 a*h1 = b*h2 .于是ab*h2*h1-1。为证aHbH ，设xaH。那么有h3H，使得x = a*h3 = b*(h2*h1-1*h3) bH . aHbH得证. 同理可证bHaH .于是aH = bH得证对于右陪集Ha，Hb，同上可证平行的命题 由于对每一元素g G，ggH (gHg)，gHG（HgG），因此据以上讨论可以看出，子群H的全体左（右）陪集构成G的一个划分，且划分的各单元与H（亦即陪集eH，He）具有同样数目的元素由此可导出下列重要的拉格朗日定理（Lagrange theorem）. 定理6.20 设为有限群的子群，那么H的阶整除G的阶 证 由以上讨论知 | G | = k | H | ，其中k为不同左（右）陪集的数目.定理得证.注意，拉格朗日定理之逆不能成立。我们将指出一个12阶群、它没有6阶的子群（见练习6.3第11题之（3）.因此，据此定理只可判别一子代数“非子群”,却不可用它来判别一子代数“是子群”。 例6.9 拉格朗日定理可用于证明下列事实： （1）有限群中任何元素的阶均为G的阶的因子。 设a为G中任一元素,a的阶为r那么必为G的r阶子群，因此r整除 | G | 。 （2）质数阶的群没有非平凡子群 利用陪集还可定义陪集等价关系 定义6.11 设为群的子群。定义 G上H的左(右)陪集等价关系。对任意a,bG ab当且仅当a，b在H的同一左（右）陪集中 显然，确为一等价关系关于有下列事实。 定理6.21 设为群G上H的左（右）陪集等价关系，那么 ab当且仅当 a-1*bH 证 设ab，则有gG，使a，bgH，因而有hl,h2H,使得a = g*h1，bg*h2 .于是 a-1*b = (g*h1)-1*(g*h2) = h1-1*h2 H 反之，设a-1*bH,即有hH 使a-1*b = h 。因而b = a*haH 。而aaH显然，故a，b在同一左陪集aH中，ab真对右陪集等价关系同理可证上述定理6.2.3 循环群 定义6.13 称为循环群(cyclic group)，如果 G为群，且G中存在元素g,使 G以g为生成集，即 G的任何元素都可表示为g的幂（约定e = g0），这时g称为循环群G的生成元（generater）例6.12 （1）为循环群，1或（l）为其生成元 . （2）令 A =2i | iI，那么(为数乘 )是循环群 ，2是生成元 （3）为循环群，1，2，3，4都可以是生成元 关于循环群的下列性质是明显的 定理6.26 设为循环群，g为生成元，那么 （1） G为阿贝尔群 （2） G的 h同态像是以 h（g）为生成元的循环群 （3） G为无限循环群时必同构于 （4） G为有限循环群时，必有 G = e，g，g2,，gn-1其中n = | G |，也是g的阶从而n阶循环群必同构于 定理 6.27 循环群的子群都是循环群 证 设为g生成的循环群，为其子群当然，H中元素均可表示为gr形 （1）若He,显然H为循环群 （2）若He，那么H中有gi(i0)由于H为子群，H中必还有g-i .因此，不失一般性，可设i为正整数，并且它是H中元素的最小正整数指数现证H为gi生成的循环群 设gj为H中任一元素令jmi+r，其中m为i除j的商，r为剩余，0ri于是 gj = gmi+rgmi*gr gr= g-mi*gj由于gj, g-miH，（因gmiH），故grH，根据i的最小性，r 0，从而 gj = gmi = (gi)m， H为循环群证讫 根据上述定理，立即可以推得以下定理 定理6.28 设为g生成的循环群 （1）若G为无限群，则G有无限多个子群，它们分别由g0,g1,g2, g3,生成 （2）若G为有限群，| G | n，且n有因子 k1,k2,k3,kr，那么G有r个循环子群，它们分别由 gk1,gk2,gk3,生成.（注意这r个子群中可能有相同者） 例6.13 （1）有循环子群： ， ， ，,， （2）有循环子群： ， ， , 6.2.4 置换群 定义6.14 称有限集上的双射函数为置换称任意集合上的双射函数为变换 例6.14设A = l,2，那么A上有两个置换： 当A = 1,2,3时, A上有6个置换： 一般地，A = a1，a2，an时，A上有 n!个置换置换 p满足 p(ai)aji时，可表示为 置换的合成运算通常用记号 表示之，对置换的独特表示形式计算它们的合成时，可像计算两个关系的合成那样来进行例如： = = 因此,应当注意 （pipj）（x）= pj（pi（x） 对于置换的合成运算而言，A上置换的全体中有么元-恒等函数,又称么置换，且每一置换都有逆置换，因此置换全体构成一个群。 定义6.15 将n个元素的集合A上的置换全体记为S，那么称群为n次对称群（symmetric group），它的子群又称为n次置换群（permutation group） 对置换群稍作推广便有变换群的概念. 定义6.16 对任意集合A定义集合S S = f | fAAf为双射那么群及其子群称为变换群，其中 为函数的合成运算 像定理6.3那样，可以证明下列群表示定理 定理6.30 每个群均同构于一个变换群，特别地,每一个有限群均同构于一个置换群. 证 设为任一群,对G中每一元素a，定义双射函数fa:GG如下。 fa（x） a*x（请读者自行证明fa确为双射）令 F = fa | aG 现证为群（ 为函数合成运算） （l）F对 运算封闭。设faF，fbF,那么aG，bG考虑fafb。：对任意xG， fafb（x）fa(fb(x) a*b*x fa*b（x）即 fafb fa*b 。由于a*bG，fa*b F,故fafb F （2） 运算显然满足结合律 （3） 运算有么元fe Fe为群G的么元。 （4）F中每一元素fa均有逆元fa-1这是因为由aG知a-1G，从而fa-1F，并且对任意xG，faf a-1（x）= a*a-1*xx = e*x = fe（x），即faf a-1= fe 。再证与同构为此定义函数h:GF，使得对任一xG，h(x) = fx 显然h为双射（请读者自证）.另仿(1)可证h保运算,即对G中任意元素x,y，有h(x*y)= fx*y = fxfy = h(x) h(y)6.3 环和域这一节我们要讨论含有两个二元运算的代数结构，环和域.6.3.1 环 下文中符号，表示一般二元运算，分别称为加、乘运算（未必是数加和数乘），并对它们沿用数加、数乘的术语及运算约定，例如,a，b的积表示为ab，n个a的和a+a表示为na, n个a的积表示为an 等 定义6.17 称代数结构为环（ring），如果 （1）是阿贝尔群（或加群） （2）是半群 （5）乘运算对加运算可分配，即对任意元素a,b,c R， a（bc） ab+ac , （bc）a = ba+ca 例6.16 （1）(I为整数集，+,为数加与数乘运算)为一环 （2）为环，因为我们已知为加群，为半群，此外， ak（b+ kc）= ak (b+c)mod k) =（a（b+c）（mod k）（mod k） =（a（b+c）（mod k） =（ab+ac）（mod k） = ab（mod k）+ kac（mod k） = akb + k akc （其中x（mod k）表示x除以k的剩余）且同理可证（b+ kc）k a = bka + k cka . （3）所有整数分量的n n方阵集合Mn与矩阵加运算（+）及矩阵乘运算（）构成一环，即， 为环（4）所有实系数多项式（以x为变元）的集合Rx与多项式加，乘运算构成环，即为环 （5）(其中0为加法么元、乘法零元)为一环，称为零环。（其它环至少有两个元素） （6）(其中0为加法么元、乘法零元，e为乘法么元)为一环 环有下列基本性质定理6.31 设为环，0为加法么元,那么对任意a,b,cR （1）0a = a0 = 0 (加法么元必为乘法零元) （2）（-a）b = a（-b）= -ab（-a表示a的加法逆元,下同） （3）（-a）（-b）= ab （4）若用ab表示a+(-b),则 （a-b）cacbc , c（a-b）ca-cb 证（1） 0a0+(-a)0 = a(0+0)+(-a)0 = a0+ a0+(-a)0 = a0 同理可证0a = 0 . （2）(-a)b = ab+(-ab)+(-a)b = (a+(-a)b+(-ab) = 0b+(-ab) = -ab 同理可证a（-b）= -ab . （3）仿（2）可证 （4）(a-b)c (a+(-b)c = ac+(-b)cac+(-bc) = ac-bc同理可证c(a-b)cacb 注意, 中乘运算未必满足交换律，也未必有么元（但一定有零元）定义6.18 环中运算满足交换律时，称 R为交换环（commutative rings），当运算有么元时，称R为含么环（ring with unity） 例6.16中（1）,（2） ，（4）是含么交换环，（3）是含么环. 环不仅必有零元，还可能有下述所谓零因子 定义6.19 设为环，若有非零元素 a，b满足 ab = 0，则称a,b为R的零因子（divisor of 0），并称R为含零因子环，否则称R为无零因子环例6.17 在环中, 0是零元,2,3为零因子，因为2630在环中有零因子 和 因为 = 它是矩阵加的么元 6.3.2域定义6.28 称为域（fields）,如果为一环,且为阿贝尔群由于群无零因子（为什么？），因此域必定是整环事实上，域也可定义为每个非零元素都有乘法逆元的整环 例6.23 为域，但不是域，因为在整数集中整数没有乘法逆元为域，1和4的逆元是4和1,2和3互为逆元.但不是域，它甚至不是整环，同为它有零因子，例如2，3，它们没有乘法逆元域有以下基本性质 定理 6.44 为域当且仅当 p为质数 证 设p不是质数，那么由上例可知Np有零因子（p的因子），故不是域 反之，当p为质数时，可证Np中所有非零元素都有p运算的逆元，从而含么交换环为域 设q是Np中任一非零元素，那么q与p互质据数论事实,有整数m,n使mp + nq = 1 从而(mp+nq)(mod p) = 1即mp(mod p) +p nq(mod p) = 10 + n(mod p) p q(mod p)= 1, 或 n(mod p) p q= 1因此,q有逆元n(mod p) . 定理得证. 定理6.45 有限整环都是域 证 设为有限整环，由于为有限含幺交换半群,据定理6.17的证明，为阿贝尔群,因而为域 定理6.46 设为域,那么F中的非零元素在中有相同的阶. 证 当中每个元素都是无限阶时,定理当然真当中有非零元素a具有有限阶n，欲证中任一元素b的阶亦必是n 。 事实上(nb)a = b(na) = 0，而F无零因子,且a 0故nb = 0，因此b的阶不超过n (a的阶) 现设 b的阶为m。由(ma)b=a(mb) = 0,可知ma = 0, 因此a的阶(n)不超过m（b的阶）.故a的阶等于b的阶6.4 格6.1.1 格有序集 格是一种特殊的有序集，因此我们先从有序集方面引入格的概念。对有序集的任一子集可引入上确界和下确界的概念，但并非每个子集都有上确界或下确界，例如在图6.1中哈斯图所示的有序集里，a，b没有上确界，c，d没有下确界。不过，当某子集的上、下确界存在时，这个上、下确界是唯一确定的。定义6.1称有序集为格（lattice），如果L中的任何两个元素的子集都有上确界和下确界。 通常用ab表示a，b的上确界，用ab表示a，b的下确界， 和分别称为保联（join）和保交（meet）运算。由于对任何a，b，ab及ab都是L中确定的成员，因此 , 均为L上的运算 a b c d d ca b 图6.1例 6.1 （1）对任意集合A，有序集为格，其中保联、保交运算即为集合的并、交运算，即 BCBC , BCBC （2）设I+表示正整数集，| 表示I+上整除关系，那么为格，其中保联、保交运算即为求两正整数最小公倍数和最大公约数的运算，即 mnlcm（m,n）， mngcd（m,n） (3) 全序集（链）都是格，其中保联、保交运算可如下规定：对任何a，bL。 （4）设P为命题公式集合，逻辑蕴涵关系 为P上的序关系（指定逻辑等价关系为相等关系），那么，为格，对任何命题公式 A，B， AB = AB，AB = AB（等式右边的，为逻辑运算符）。 现设表示序关系的逆关系，那么据逆关系的性质可知：定理6.1当为格时，亦为格,且它的保联、保交运算,对任意a,bL满足 ab = ab , ab = ab于是，我们有下列对偶原理。 定理6.2A为格上的真表达式，当且仅当A*为上的真表达式，这里A*称为A的对偶式，即将A中符号，分别改为，后所得的公式，而 ab意即ba 。 回忆命题演算、集合代数中所述对偶定理，上述定理的意义是十分清楚的。 例6.2 格中的真表达式AB A有对偶真表达式ABA。格中真表达式pq q有对偶真表达式q pq 。现在我们深入地讨论格的性质。在有必要时，下文将同时给出对偶的两个真表达式. 定理6.3设为格，那么对L中任何元素a,b,c 有 （l）aab， bab aba， abb （2）若ab，ac，则abc 若ba，ca，则bca （3）若ab，cd，则acbd，acbd （4）若ab，则acbc，acbc 证（l），（2）由运算，的定义立得 （3）设ab， cd，我们只证acbd，将acbd 的证明留给读者。 由（1）bbd，dbd，于是 abd，cbd（由的传递性）。于是由（2）得acbd 。 （4）这是（3）的特例. 定理6.4设为格，那么对L中任意元素a,b,c 有 （1）aa = a ，aaa (幂等律) （2）ab = ba ，ab = ba （交换律）（3）a（bc）=（ab）c a（bc）=（ab）c (