离散数学课件代数系统1.ppt

第六章 代数系统(抽象代数),以前学过许多代数： 初等代数、高等代数(线性代数)、 集合代数、命题代数、等等 它们研究的对象分别是整数、有理数、实数、矩阵、集合、命题等等，以及这些对象上的各种运算。 这一章我们将代数的研究引导到更高的层次，即抛开具体对象去研究代数抽象代数。,就专业知识而言，计算机学科中要培养学生三个能力： 理论抽象设计 理论：就是计算机科学中各种理论课。 抽象：要把实际问题抽象成数学模型(数学系统)。 设计：系统设计、程序设计。 确定数学模型，需要了解有哪些代数结构(系统)。 另外，抽象代数可以培养学生的抽象逻辑思维能力。 本章所讨论的理论，在计算机的编译理论、程序理论、 语义理论、编码理论、计算理论、逻辑设计理论、数据 库理论等都有应用。 本章主要讨论：代数结构(系统)的概念，运算的性质、 代数结构(系统)的同构、半群、独异点、群、环、域等。,6-1 代数结构(系统)的概念,所谓代数结构(系统)，无非是有一个运算对象的集合， 和若干个运算，构成的系统。 一. n元运算 如何定义运算，先看几个我们熟悉的例子： 取相反数运算“-”、集合的补运算“” 以及N上的“+” I I 可见运算“-”、“”、“+” 就是个映射。,1.定义：设X是个集合，f:XnY是个映射，则称f 是X上 的n元运算。(Xn =XX.X -n个X的笛卡尔积)， 如果YX，则称运算f 在X上是封闭的。 f:XY 是个一元运算。前面的 -、是一元运算。 f:X2Y 是个二元运算。+是二元运算。 思考题：下面说法是否正确？ 减法是N上封闭的二元运算。 除法是整数 I上的二元运算。 除法是实数 R上的二元运算。 我们主要讨论二元运算。 通常用、 、 、+等表示抽象的二 元运算。如果用“”表示二元运算f 时， 通常将 f()=z 写成 xy=z 。,2.二元运算的运算表 有时用一个表来表示二元 运算的运算规律。 例如令E=a,b， P(E)上的 运算表如图所示。 再如令X=S,R,A,L其中 S表示开始时的位置； R表示“向右转”； A表示“向后转”； L表示“向左转”； “”表示转动的复合运算； 其运算表如图所示。 从运算表除了可以看清运算的规律外，可以很容易地看 出运算的性质。,二.代数系统的概念,1.代数系统的定义：X是非空集合，X上的m个运算 f1,f2,fm 构成代数系统U, 记作U= ( m1) 注意：这m个运算f1,f2,fm的元数可能不同, 比如f1是一 元运算，f2是二元运算,fm是k元运算。 例如 ， 2.有限代数系统： U= 是个代数系统，如果 X是个有限集合，则称U是个有限代数系统。 3. 同类型代数系统：给定两个代数系统 U= ，V= 如对应的运算fi和 gi的元数相同(i=1,2,3,m), 则称U与V是同类型代数系统。 例如与、与,6-2 二元运算的性质,下面着重讨论一般二元运算的性质： 一. 封闭性 设是X上的二元运算，如果对任何x,yX,均有xyX,则称在X上封闭。 例如在N上加法+和乘法封闭，而减法不封闭。 从运算表可以很容易看出运算是否封闭。 二.交换性 设是X上的二元运算，如果对任何x,yX，均有 xy = yx，则称是可交换的。 大家都知道：加法、乘法、交、并、对称差等运算均是可交换。,从运算表看交换性：是以主对角线为对称的表。 三.幂等元、幂等性 设是X上的二元运算，如果有aX，aa=a，则称a是 幂等元。如果对任何xX,都有xx=x，则称有幂等性. 从运算表看幂等元、幂等性：看主对角线的元素与上表头(或左表头)元素相同。 请看上述的运算表 有幂等性。,四.幺元(单位元、恒等元) 设是X上的二元运算，如果有eLX，使得对任何xX， 有eLx=x，则称eL是相对的左幺元。如果有eRX，使 得对任何xX，有xeR=x ，则称eR是相对的右幺元。 如果eL= eR =e，对任何xX，有ex=xe=x, 称e是相对 的幺元。 对加法+，幺元是0， 对乘法，幺元是1， 对并运算，幺元是， 对交运算，幺元是全集E， 从运算表中找幺元（如表所示） 从运算表找左幺元eL ： eL所在行的各元素均与上表头元 素相同。如S行，所以S是eL 。 从运算表找右幺元eR ： eR所在列的各元素均与左表头元 素相同。如S列，所以S是eR 。,定理6-2.1.设是X上的二元运算，如果有左幺元 eLX，也有右幺元 eRX，则 eL= eR =e ，且幺元 e 是唯一的。 证明：因为 eL是左幺元，又eRX，所以 eLeR=eR 因为eR是右幺元，又 eL X，所以 eLeR= eL 于是 eL= eR =e 。 下面证明幺元的唯一性。 假设有两个幺元e1、e2， 因为e1是幺元，又e2X，所以 e1e2=e2 因为e2是幺元，又 e1 X，所以 e1e2= e1 则 e1= e2 =e 。所以幺元是唯一的。 思考题. 减法运算是否有幺元？,五. 零元 设是X上的二元运算，如果有LX，使得对任何 xX，有Lx=L，则称L 是相对的左零元。如果 有RX，使得对任何xX，有xR=R ，则称R 是相对的右零元。如果L=R=，对任何xX，有 x=x=, 称是相对的零元。 例如：对乘法，零元是0， 对并运算，零元是全集E ， 对交运算，零元是 ， 从运算表找零元 左零元L ：L所在行的各元素均与左表头元素相同。 如行，所以是L 。 右零元R：R所在列的各元素均与上表头元素相同。 如列，所以是R 。 所以=,定理6-2.2. 设是X上的二元运算，如果有左零元LX，也有右零元RX，则L=R =,且零元是唯一的。 证明的方法与前定理类似，从略。 定理6-2.3. 设是代数系统，且|X|1。如果该代数系统中存在幺元e和零元, 则e. 证明：用反证法。假设=e，那么对任意xX, 必有 x = ex =x = e 于是,X中所有元素都是相同的，这与|X|1矛盾。 所以e。,六.可结合性 设是X上的二元运算，如果对任何x,y,zX，有 (xy)z =x(yz)，则称是可结合的。 例：数值的加法、乘法，集合的交、并、对称差， 关系的复合、函数的复合，命题的合取、析取等。 若是可结合的运算，元素x的运算，通常可以写成乘幂的形式。即： xx=x2 x2x=xx2=x3 xmxn=xm+n (xm)n=xmn 思考题：对于加法 +： 13 =( ) 对于乘法： 13 =( ),七.逆元 设是X上有幺元e 的二元运算，aX，如果有bX，使得，ba=e，则称b是a的相对的左逆元，记为aL-1 。如果有bX，使得ab =e，则称b是a的相对的右逆元，记为aR-1 。如果有ba=ab=e, 称b是a的相对的逆元，记为a-1 。也称a与b互为逆元。如x-1X，也称x可逆。 例: 实数集合R上的+和，xR 对加+: x-1 = -x (e=0) 对乘: x-1 =1/x (x0) (e=1) 从运算表找x的左 逆元 xL-1 ： 在x列向下找到e后，再向左到 左表头元素即是xL-1 。 从运算表找x的右逆元 xR-1： 在x行向右找到e后，再向上到 上表头元素即是xR-1 。,定理6-2.3.设是X上有幺元e且可结合的二元运算，如果 xX，x的左、右逆元都存在，则x的左、右逆元必相等， 且x的逆元是唯一的。 证明：设xL-1、 xR-1分别是x的左、右逆元，于是有 xL-1x = x xR-1 =e xR-1 =exR-1 =(xL-1x) xR-1=xL-1(x xR-1)=xL-1e=xL-1 假设x有两个逆元 x1、x2， 所以 x1x= e = x x2 x2 = ex2 =(x1x) x2=x1( x x2)=x1 e =x1 所以x的逆元是唯一的。 定理6-2.4.设是X上有幺元e且可结合的二元运算，如果对 xX，都存在左逆元，则x的左逆元也是它的右逆元。 证明：任取aX，bX，ba=e, cX, cb=e, 于是有 ab=e(ab)=(cb)(ab) =c(ba)b=ceb=cb=e 所以b也是a的右逆元。,八.可消去性 设是X上的二元运算，aX，如果对任何x, yX，有 ax=ay x=y 或者 xa=ya x=y 则称 a相对是可消去的。 例如对乘法而言，a0, a 就是可消去的。即 a0 ax=ay 则可得 x=y. 而集合的和都不满足可消去性。因为 AB=AC 或 AB=AC 不一定有B=C 定理6-2.5. (可消去性的判定定理)设是X上封闭可结合的二元运算，若 aX，且a-1X，则a是可消去的。 证明：如aX，且a-1X，任取x,yX，设有ax=ay 则 a-1(ax)= a-1 (ay) ，因是X上可结合，于是 (a-1 a) x= (a-1 a) y ，所以 ex=ey 即 x=y，所以 a相对是可消去的。 若设有xa=ya ，类似地亦可得 x=y,九.分配律 设和 都是X上的二元运算，若对任何x,y,zX，有 x(yz)=(xy)(xz) ，(yz) x =(y x)(z x) 则称对可分配。 例如： 乘法对加法可分配。 集合的与互相可分配。 命题的与互相可分配。 十.吸收律 设和 都是X上的可交换二元运算，若对任何x,yX，有 x(xy)=x ，x(xy)=x 则与 满足吸收律。 例如：集合的与满足吸收律。 命题的与满足吸收律。,小结：和是代数系统, , 是二元运算： 1.封闭性：x,yX, 有 xyX。 2.可交换性：x,yX, 有 xy=y x。 3.幂等性： xX, 有 xx=x。 4. 有幺元： eX, xX，有 ex=xe=x. 5.有零元: x,xX，有x=x=. 6.可结合性：x,y,zX, 有 (xy)z =x(yz)。 7.有逆元： xX, 有x-1X，使得 x-1x=xx-1=e 8.可消去性： aX，x, yX,有 (ax=ay)(xa=ya) x=y. 9.分配律： 对可分配：x,y,zX，有 x(yz)=(xy)(xz) ，(xy)z =(xz)(yz) 10.吸收律：x,yX，有 x(xy)=x ，x(xy)=x,6-3 代数系统的同态与同构,有各种各样的代数系统，但是，有些代数系统表面上看不同，但它们运算的性质相似、或完全一样。 这就需要探讨代数系统间的同态、同构问题。,二.同态、同构的定义,设,是两个代数系统，和 都是二元运算，如果存在映射f:XY,使得对任何x1 ,x2X，有 f(x1x2)=f(x1)f(x2) -此式叫同态(同构)关系式 则称 f是从到的同态映射，简称这两个代数系统同态。记作XY。 并称为的同态像。 如果f是满射的，称此同态f是满同态。 如果f是入射的，称此同态f是单一同态。 如果f是双射的，称与同构，记作XY。 f是到 的同态(同构),称之为自同态(自同构)。,例1 ：是正实数集合R+上的乘法 ； ： 是实数集合R上的加法+。 表面上看这两个代数系统完全不同，实际它们运算的性质却完全一样，都满足：可交换、可结合、有幺元、每个元素可逆。 构造映射 f: R+R 对任何xR+，构造 f(x)=lgx， f(x) 是双射函数，且 对任何x,yR+， 有f(xy)=lg(xy)=lgx+lgy=f(x)+f(y),f(1)=lg1=0 在： 在 : x=100 f(x)=lgx=lg100=2 x-1 =1/100 f(x-1)=lgx-1 =lg1/100=-2=(f(x)-1,设I是整数集合，R是I上模k(k是正整数)同余关系，因R 是I上等价关系，所以得商集I/R，将I/R记作Nk，即： Nk=0,1,2,k-1 在Nk上定义运算+k和k ，我们分别称之为以k为模的加 法和乘法。定义为： 任取x ,y Nk ， x +k y=(x+y)(mod k) xky=(xy)(mod k) 例如 k=4 N4=0,1,2,3 2 +4 3=(2+3)(mod 4)=1 243=(23)(mod 4)=2 下面为了方便，我们将N4=0,1,2,3简记成： N4=0,1,2,3 任何x,yN4 , x+4 y=(x+y)(mod 4),例2. N4=0,1,2,3,N4上定义运算+4： 任何x,yN4 , x+4 y=(x+y)(mod 4) 其运算表如图所示。 B=0,1, 是B中异或运算。 其运算表如下图所示： 证明 N4B 构造映射 g: N4B 如下： 下面验证 g是同态映射。 g(1+4 2)=g(3)=1 g(1)g(2) =10=1 g(1+4 2)=g(1)g(2) g(2+4 3)=g(1)=1 g(2)g(3)=01=1 g(2+4 3)=g(2)g(3),g(2+4 2)=g(0)=0 g(2)g(2)=00=0 g(2+4 2)=g(2)g(2),其余类似可证 N4B,例3 . 证明与同构。 构造映射 f:N4X ： 下面验证 f是同构映射。 f(1+4 2)=f(3)=L f(1)f(2)=RA=L f(1+4 2)=f(1)f(2) f(2+4 3)=f(1)=R f(2)f(3)=AL=R f(2+4 3)=f(2)f(3),f(2+42)=f(0)=S f(2)f(2)=AA=S f(2+4 2)=f(2) f(2),f(1+43)=f(0)=S f(1)f(3)=RL=S f(1+4 3)=f(1) f(3),其余类似可验证 N4X,注意：代数系统 和同构的必要条件： 1.X和Y的基数相同，即KX=KY。 2. 运算和 是同类型的。 3.存在双射 f:XY，且满足同构关系式。 因为并不是所有双射都满足同构关系式。 例如，例3、中, g:N4X 如右图所示， f(1+4 1)=f(2)=L f(1)f(1)=AA=S f(1+4 1)f(1)f(1) 所以g不是同构映射。 实际上构造同构映射时必须是幺元对幺元、零元对零元、逆元对逆元，,三 .代数系统间的同构关系是等价关系,1.有自反性：任何代数系统 , 有XX。 证明： 因为有双射 IX:XX, 任取x1 ,x2X，有 IX(x1x2)= x1x2 =IX(x1)IX(x2) ，所以 XX。 2.有对称性：任何代数系统 , 如果有XY 则必有YX。 证明：因有XY，所以有双射 f:XY, 对任意x1 ,x2X，有 f(x1x2)= f(x1) f(x2) 由 f是双射，知 f-1 :YX亦是双射函数，任取y1 ,y2Y 因 f :XY是满射，x1 ,x2X, 使得 y1=f(x1), y2=f(x2) 于是 x1=f-1(y1) , x2=f-1(y2) 而 f-1(y1 y2)=f-1(f(x1) f(x2)= f-1(f(x1x2)= f-1f(x1 x2) = IX(x1x2)=x1x2 =f-1(y1)f-1(y2) ，所以YX,3.有传递性：任何代数系统 , 如果有XY 和 YZ，则必有 XZ 。 证明：因有XY，所以有双射 f:XY，对任意x1 ,x2X，有 f(x1 x2)= f(x1) f(x2) 因有YZ ，所以有双射 g:YZ，对任意y1 ,y2Y，有 g(y1 y2)= g(y1)g(y2) 构造双射 h=gf ，h:XZ， 任取x1 ,x2X， 因 h(x1x2)=gf(x1x2)=g(f(x1x2)=g(f(x1) f(x2) ) =g(f(x1) g(f(x2)= g f(x1) g f(x2)=h(x1)h(x2) 所以 XZ 综上是个等价关系。,四. 代数系统同构的性质,任何代数系统, ，XY，f:XY是同构映射，即任取x1 ,x2X，有 f(x1x2) = f(x1) f(x2)。 1. (保持结合律)如果运算可结合，则运算也可结合。 证明：任取y1 ,y2 , y3 Y 因 f :XY是满射，知存在x1 ,x2 , x3X, 使得 y1=f(x1) , y2=f(x2) , y3=f(x3) y1(y2 y3 ) = f(x1) (f(x2) f(x3) = f(x1) f(x2x3) =f(x1(x2x3) =f( x1x2)x3) (因可结合) = f(x1x2) f(x3) = (f(x1)f(x2) f(x3)= ( y1 y2 ) y3 也可结合。 2. (保持交换律)如果运算可交换，则运算也可交换。 证明的方法与1.类似。,3. (保持幺元存在性)如果运算有幺元e，则运算也有幺元e，且f(e )= e 。 证明: 任取yY,因 f :XY是满射,知存在xX, 使得y=f(x) 证明方向为: y f(e)= =y,以及f(e) y=y y f(e) = f(x) f(e) =f(xe) (同构关系式) =f(x) (e为幺元) =y f(e) y=f(e) f(x)=f(ex) =f(x) =y 所以f(e )是相对的幺元，即f(e)= e 。,4. (保持零元存在性)如果运算有零元 ，则运算也有零元 ，且f()= 。 证明：任取yY,因f :XY是满射,知存在xX, 使得 y=f(x) 证明方向为: y f() = f(),以及f() y= = f() 证明过程与上面类似 y f() = f(x) f()=f(x) = f() f() y= f() f(x)=f(x) = f() 所以f() 是相对的零元，即f() =,5. (保持逆元存在性)如果中每个xX可逆，即x-1X，则中每个yY也可逆，即y-1Y。 且如果y=f(x)，则 y-1= (f(x)-1 =f(x-1)。 证明：任取yY,因f:XY是满射,知存在xX, 使得 y=f(x) 证明方向:只要证出 y f(x-1)= e和 f(x-1) y= e 即可 设运算的幺元e ，运算的幺元e ，f(e)= e 。 y f(x-1) = f(x) f(x-1) =f(xx-1) =f(e) = e f(x-1) y=f(x-1) f (x)=f(x-1x)=f(e)= e 所以 y-1= (f(x)-1 =f(x-1)。 可看出上述性质对满同态也是成立的。 下面是含有两个运算的代数系统的同构的性质的保持问题,y y-1 = e y-1 y = e,定义：令和是含有两个运算的代数系统，其中+、 、都是二元运算，如果存在双射 f:XY，使得对任何x1 , x2X，满足 f(x1+x2) = f(x1) f(x2)。(注意：+与对应) f(x1x2) = f(x1) f(x2)。(注意：与对应) 则称这两个代数系统同构。,含有两个运算的代数系统的 同构的性质的保持问题,6. (保持分配律)如果运算+对可分配，则对也可分配。 证明：任取y1 ,y2 , y3 Y 由f :XY是满射，知存在 x1 ,x2 , x3X，使得 y1=f(x1) , y2=f(x2) , y3=f(x3) 证明目标为y1 ( y2 y3 )= (y1y2) (y1y3) 及 ( y1 y2 )y3 = =(y1y3) (y2y3) 开始证明: y1 ( y2 y3 ) =f(x1)(f(x2)f(x3) = f(x1) f(x2x3) (同构关系式) = f(x1+(x2x3) (同构关系式) = f(x1+ x2)(x1+ x3) (+对可分配) = f(x1+x2) f(x1+x3) (同构关系式) = (f(x1)f(x2) (f(x1)f(x3) (同构关系式) = (y1y2) (y1y3) 类似地可证 ( y1 y2 )y3 = (y1y3) (y2y3) 所以对 也可分配。,f(x1+x2) = f(x1) f(x2) f(x1x2) = f(x1)f(x2),x(yz)=(xy)(xz) (xy)z =(xz)(yz),7. (保持吸收律)如果运算+和满足吸收律,则和也满足吸收律 证明：任取y1 ,y2Y,由f:XY是满射,知存在x1,x2X, 使得 y1=f(x1) , y2=f(x2) 证明目标为:y1 ( y1 y2 )= y1与y1 ( y1 y2 )= y1 下面开始证明 y1 ( y1 y2 ) =f(x1)(f(x1)f(x2) = f(x1) f(x1x2) (同构关系式) = f(x1+(x1x2) (同构关系式) = f( x1) (因+和满足吸收律) = y1 y1 ( y1 y2 )=f(x1) (f(x1) f(x2)= f(x1) f(x1 + x2)= f(x1(x1+x2)= f( x1)= y1 注意：同构性质的保持是双向的。 即可将X中运算的性质,保持到Y中运算上.并且,由于是对称的,所以Y中运算的性质,也可以保持到X中的运算上.这就是双向保持.,x(xy)=x x(xy)=x,f(x1+x2) = f(x1) f(x2) f(x1x2) = f(x1)f(x2),五. 同态性质的保持,定理：代数系统, , XY, f:XY是同态映射, 如果中满足交换、结合、有幺元、有零元、每个元素可逆，则在中也满足上述性质。 证明的方法与前一样，所不同的是，不是在Y中取元素，而是在值域f(X)中取元素。因为f不一定是满射的。 另外，由于同态关系不满足对称性，所以同态性质的保持只是单向的。即Y中运算的性质，X中运算不一定有。,六. 同态核,定义：f是从到 的同态映射，(XY)，e和 e 分别是X、Y中幺元。定义集合ker (f)为： ker (f)=x|xXf(x)= e 称ker (f)为 f的同态核。 例 g是到 的同态映射。 ker (g)=0,2,6-4 半群和独异点,按照运算的性质将代数系统分成几类抽象的代数系统。 含有一个运算的：半群、独异点、群 含有两个运算的：环、域 含有三个运算的：布尔代数 一. 半群(Semi-group) 1.定义：S是个非空集合, 是S上的二元运算，如果在S上满足封闭性、可结合性，则称是半群。 例1. , , ,都是半群。,例2. 任何一种语言都有个基本符号表，称之为字母表。 令V是计算机机器语言的字母表，V=0,1,计算机的任何 一条指令，都是个由0和1组成的符号串，由0和1组成的 所有符号串的集合是V+ ，其中 V+ =VV2V3.Vn. 在V+上定义符号串的联结运算，为： 0101 001=0101001 显然运算是可结合的，所以是个半群。 2.交换半群 是半群，如是可交换的，则称它是交换半群。 例： ,都是交换半群。 3.子半群 是个半群，BS，如果在B上封闭，则称是 的子半群。 例是的子半群。,定理6-4.1设是半群，如果S是有限集合，则必存在aS,使得aa=a。 证明：因是有限半群,在S上封闭, 所以任何bS,对任何i1有biS,因i可以取无穷多个值，所以必存在正整数i,j(ij) ,使得bi = bj , 令p=j-i ,显然p1，j=p+i,于是 bi = bj = bp+i = bpbi 即 bi = bpbi bib = bpbib bi+1 = bpbi+1 bi+1b = bpbi+1 b bi+2 = bp bi+2 . 于是对所有大于i的正整数q有： bq = bpbq 因p1，总可以找到k1，使得kpi，于是有 bkp = bp bkp = bp (bp bkp) = ( bp bp ) bkp = b2p bkp = b2p (bp bkp) = b3p bkp = = bkp bkp,令bkp =a, 于是有 aa=a,二. 独异点 ( Monoid ),1.独异点定义：设是个半群，如果对有幺元，则 称是个独异点，也称它是含幺半群。 即独异点满足：封闭性、可结合性、存在幺元。 , 幺元是0 , 幺元是1 ,幺元是E 幺元是 幺元是 所以它们都是独异点。 2.交换独异点 是独异点,如是可交换的,则称它是可交换独异点。 例. ,都是交换独异点。 3.子独异点 是个独异点,B M,如果在B上封闭,且幺元eB,则称是的子独异点。 例：是的子独异点。,定理6-4.2 设是交换独异点，A是M中所有幂等元构成的集合，则是的子独异点。 证明：先证幺元 eA 因为 ee=e，所以e是幂等元，因此eA。 再证在A上封闭 即证明任意a,bA，有abA，即ab也是幂等元 任取a,bA，于是 aa=a， bb=b (ab)(ab) =a(ba)b (结合律) =a(ab)b (可交换) = (aa)(bb) (结合律) = ab (a、b是幂等元) 所以ab也是幂等元，即 abA。 所以是的子独异点。,封闭 含幺元,6-5 群 Group,群是抽象代数中最重要的，所以对它的研究也比较多。 一. 概念 1.群的定义：设是个 代数系统，如果满足封闭、 可结合、有幺元且每个元素 可逆，则称它是个群。 例：, 幺元是0， 每个x的逆元是 -x 。 幺元是 ，因任何XP(E) XX=X-1=X , ,是群。 而 ,都有幺元，但不是群。 2.有限群:令 是群，G是有限集，则称它是有限群.,二.群的性质,群除了具有封闭、结合、有幺元、可逆外，还有些重要 性质。下面就讨论这些性质。 1.群满足可消去性 定理6-5.1设是个群，则对任何a,b,cG, 如果有 ab=ac 则 b=c 。 ba=ca 则 b=c 。 证明:任取a,b,cG, 设有ab=ac 因是个群，所以a-1G, 于是有 a-1(ab)= a-1(ac) (a-1a)b= (a-1a )c eb=ec 所以 b=c 类似可证(2).,2. 群方程有唯一解 定理6-5.2 设是个群，则对任何a,bG, 存在唯一元素 xG, 使得 ax=b 存在唯一元素 yG, 使得 ya=b 证明:先证明式有解 因是个群，对任何a,bG，有a-1G， 所以 a-1bG， 将 a-1b 代入中得： ax= a(a-1b)= (aa-1)b= eb=b 所以x=a-1b是方程的解。 再证明式的解的唯一性 设式有两个解x1, x2G, 于是有 ax1=b ax2=b 所以 ax1= ax2， 由可消去性得 x1=x2 。 类似可证明,封闭、结合 含幺元、可逆,3. 群中无零元。 定理6-5.3设是群，则G中无零元。 证明:当|G|=1时,它的唯一元素视为幺元(群的定义); 假设|G| 2且G中有零元，则对任何xG，有 x x e, 所以零元就不存在逆元, 即不可逆， 这与是群矛盾。 所以群中无零元。 4. 群中除幺元外，无其它幂等元。 定理6-5.4 设是个群，G中除幺元外，无其它幂等元。 证明： 假设有aG是幂等元，即 aaa 于是有 aaae， 由可消去性有 ae， 所以群中除幺元外，无其它幂等元。,封闭、结合 含幺元、可逆,5.定理6-5.5 是个群，对任何a,bG,有 (a-1)-1 =a (ab)-1=b-1a-1 证明. 结论显然成立,因为a-1与a 互为逆元，所以(a-1)-1=a 验证b-1a-1是ab的逆元， (ab)(b-1a-1)=a(bb-1)a-1=aea-1=aa-1=e (b-1a-1)(ab)=b-1(a-1a)b=b-1eb=b-1b=e 所以b-1a-1是ab的逆元，即(ab)-1=b-1a-1 推论： 是个群，对任何aG,有 (an)-1 = (aa.a)-1= (a-1a-1.a-1) = (a-1)n 规定： a-n = (an)-1 = (a-1)n 此外，因为群G中任何xG,有 e=xx-1=x1+(-1) =x0 ,记 x0 =e,封闭、结合 含幺元、可逆,6. 有限群的运算表的特征 定理6-5.6 是个有限群，则G中每个元素在运算 表中的每一行(列)必出现且仅出现一次。 证明. 令G=a1,a2,a3,.,an 的运算表如图： 任取ajG， 证明 aj在任意aiG行 必出现且仅出现一次。 由群方程可解性得 存在唯一元素akG, 使得 aiak=aj 这说明aj在ai行出现(即aj在第i行第k列出现)。 假设aj在ai行出现两次，设在第 t列也出现，则有 aiak=aj 和 aiat=aj 所以 aiak=aiat 由可消去性得at=ak 同理可证G中每个元素在每列必出现且仅出现一次。,三.群的阶与群中元素的阶,1.群的阶：是群,如果KG=n, 则称是n阶群, 如果KG是无限的, 则称是无限阶群。 下面看一看1、2、3阶群运算表的结构： 群, 假定a是幺元 根据有限群运算表的特征，得它们的运算表分别是： 从运算表可以看出： 所有的一阶群都同构； 所有的二阶群都同构； 所有的三阶群都同构。,2 .群中元素的阶 例：群如右图： A=R2 L=R3 S=R4 所以 X=R, R2, R3, R4 定义：设是个群，aG， 如果存在正整数k，使得 ak=e,则称a的阶是有限的。如果存在最小的正整数n，使 得an=e,则称a的阶是n。否则就称a的阶是无限的。 例. 群中,只有幺元0的阶是1,其余元素的阶都是无限的. 因为任何aI，a0，那么a的多少次幂等于0？ 不存在这样的正整数。 上例中：因为S1=S; A2=S; R4=S; L4=S 所以: S的阶为1；A的阶为2； R的阶为4； L的阶为4； 思考题：如果Rk=S，则k 是个怎样的数？,定理6-5.7：是群, aG, 如果a的阶为n ,则 ak=e 当且仅当 k=mn (mI)(即k是n的整数倍) 证明： 充分性，已知k=mn (mI) ak= amn=(an)m= em =e 必要性，已知ak=e ， a的阶为n，即 an=e , 假设k不是n的整数倍，令 k=mn+t, m,tI, 0tn 于是 e= ak= amn+t = (an)mat = eat= at 由于at=e，而 tn，与 a的阶为n矛盾。 所以 k是n的整数倍。即 k=mn (mI)。 思考题：上例中R4=S; L4=S R和L的阶都为4；而R-1=L 由此可以得到什么结论？,定理6-5.8. 群中的元素与其逆元具有相同的阶。 证明： 设是群, 任取aG, 如果a的阶是有限的，设阶为n, an=e ，则 (a-1)n= (an)-1 =e-1 = e 如果还有mn, 使得(a-1)m=e 则 am=(a-1)-1)m= (a-1)m)-1= e-1 = e 因为mn,又am=e ,这与a的阶为n矛盾，所以a-1的阶也为n。 如果a的阶为无限的，而a-1的阶是有限的，设 a-1的阶 是 n，即(a-1)n=e, an=(a-1)-1)n= (a-1)n)-1= e-1 = e 这与a的阶为无限的矛盾。因此a-1的阶也为无限的。 综上，a与a-1具有相同的阶。,6-6. 特殊群,一. 交换群 (阿贝尔群 、Abel群) 定义:设是群,运算是可交换的，则称它是交换群。 例如, ,都是交换群。 定理6-6.1 是交换群，当且仅当 对任何a,bG 有 (ab)(ab)=(aa)(bb) (即(ab)2=a2b2 ) 证明：充分性， 任取a,bG,设有(ab)(ab)=(aa)(bb), 由于a-1,b-1G a-1(ab)(ab)b-1 = a-1(aa)(bb)b-1 (a-1a)ba(bb-1 ) = (a-1a)ab(bb-1 ) ba= ab 所以是交换群. 必要性；设是交换群,任取a,bG (ab)(ab)=a(ba)b=a(ab)b=(aa)(bb),二. 循环群,1.例子:群如右图： A=R2 L=R3 S=R4 所以 X=R, R2, R3, R4 R5 =RR4= R S=R R6=R2,出现循环 2. 定义:设是群,如果存在一个元素gG, 使得对每 个 xG, 都存在整数i, 有x=gi, 则称是个循环群. 并称g是G的生成元. 就是以R为生成元的循环群(以L为生成元也可). 例是群, N4 =0,1,2,3, 也是以1为生成元的循环群. 因为 N4 =14,1,12,13 例是群, I=-3, -2, -1, 0, 1, 2, 3, .也可以写成: I= 1-3,1-2,1-1,10,11 ,12,13 . 1为生成元,2.循环周期: 设是个以g为生成元的循环群，如果 存在最小正整数m，使得gm=e (即m是g的阶)，则称该循环 群的循环周期是m。如果不存在最小正整数m, 使得gm=e (即g的阶是无限的),则称该循环群的循环周期是无限的。 N4 =0,1,2,3=14,1,12,13 14 =0 循环周期是4. I=-3, -2, -1, 0, 1, 2, 3, . I= 1-3,1-2,1-1,10,11 ,12,13 .循环周期是无限的. 这是两个重要的循环群，因为任何循环群的循环周期， 要么是有限的，要么是无限的。 定理6-6.2 设是个以g为生成元的有限循环群,|G|=n, 则gn=e，及G= g1,g2, gn=e且n是g的阶。,证明：先证明任何0in，都有gie。 假设有一个正整数m (mn)，有gm=e 任取xG，设x=gk，令k=mq+r 其中q,rI, 0rm x=gk= gmq+r = gmqgr = (gm)q gr = eq gr = gr (0rm) 由于r的取值 最多有 m个，所以G中元素最多有 m个， mn，这与|G|=n矛盾。所以不存在mn，使得gm=e。 再证明：g1,g2, gn中元素互不相同。 假设有此集合中 gi = gj 这里0ijn，1j-in gj-i = gj(g-1)i = gi(gi)-1=e . 因为j-in 又gj-i=e, 这与的结论矛盾。所以 g1,g2, gn中元素互不相同。 最后证明 gn=e. 因为eG,而n-1个元素 g1,g2, gn-1中无e, 又|G|=n, 于是 必有gn=e。且n是g的阶。 综上有 G= g1,g2, gn =e,因为任何循环群，它的循环周期要么是有限的，为某 个正整数，要么是无限的，因此有下面定理： 定理6-6.2 设是个以g为生成元的循环群， 则 若它的循环周期是无限的，则与同构。 若它的循环周期是k(有限的)，则与同构。 证明：构造映射 f:GI， 对任何giG f(gi)=i (iI) 显然 f是双射的。 令G=, g-3,g-2, g-1,g0 = e, g1, g2, g3. I= , -3, -2, -1, 0 = e, 1, 2, 3, 可写成 I=, 1-3,1-2, 1-1, 10 =0, 11 , 12, 13, 任取gi, gj G，(i,jI) f(gi gj)=f(gi+j)=i+j=f(gi)+f(gj) 所以GI。, 令G= g1,g2, g3 , gk =e 而 Nk =1,2,3,k-1,0 构造映射 f:G Nk , 对任何giG i 当 1i是个以g为生成元的循环群， 任取gi, gj G，(i,jI) gigj = gi+j =gj+i= gjgi 所以是交换群。,f(gi)=,6-7 子群及其陪集,子群就是群中之群。 一. 子群定义： 设是群, S是G的非空子集，如果满足： 任何a,bS 有abS, (封闭) 幺元 eS, (有幺元) 任何aS 有a-1S, (可逆) 则称是的子群。 例如是的子群。 二.平凡子群与真子群 设是群，和也是的子群。 称之为平凡子群。其余真子集构成的子群称之为真子群。,三.证明子群的方法 方法1.用子群的定义，即证明运算在子集上满足封闭、 有幺元、可逆。 方法2. 定理6-7.1设是群, S是G的非空子集，如果满足： 任何a,bS 有abS, (封闭) 任何aS 有a-1S, (可逆) 则是的子群。 证明：只需证明由可逆和封闭可以推出有幺元。 任取aS 由可逆得 a-1S, 又由封闭得 aa-1S 所以幺元 eS, 所以是的子群。,方法3. 定理6-7.2设是群, B是G的有限子集,如果 在B上满足封闭性，则是的子群。 证明： 先证幺元eB， 任取bB,因为在B上封闭，所以对任意 i1 有biB, 因 i可以取无穷多个值, 即这样的元素有无限个，而B中元 素个数有限, 所以必存在正整数i,j (i1, 有bj-i-1B, 使得 bbj-i-1 = bj-i-1b= bj-i=e 所以 b-1= bj-i-1 b) 如果j-i=1 则bj-i =b=e 所以 b-1 =b 所以是的子群。,封闭、含幺元、可逆,方法4. 6-7.3 设是群, S是G的非空子集，如果任何a,bS 有ab-1S, 则是的子群。 证明： 先证eS 任取aS 由已知得 aa-1S, 即eS。 再证可逆性 任取aS 由得eS，由已知得 ea-1S, 即a-1S。 最后证明封闭性 任取a,bS 由得b-1S ，由已知得a(b-1)-1S, 即得 abS 所以是的子群。,封闭、含幺元、可逆,例： 已知和 是群 的子群，求证 是、和的子群。 证明：用方法4 因为和 是群 的子群 所以幺元eH1H2 ，即 H1H2 任取a,bH1H2 (目标:往证a b-1H1H2) 则 a,bH1 且a,bH2 因为和 是群 的子群 所以 b-1H1 ， b-1H2 ， 于是 ab-1H1 ，ab-1H2 ，即有 ab-1H1H2 因 H1H2 H1，H1H2 H2 ，H1H2 G， 所以 是、和的子群。,四. 子群的陪集,看下面的例子,例： N6=0,1,2,3,4,5， 群的运算表如图： H1=0 H2=0,3 H3=0,2,4,从, , 的运算表看出它们是的子群。它们的阶分别是1，2，3阶，为6的因子。,定义设是群的子群，aG，定义集合: aH=ah|hH Ha=ha|hH 则称aH(Ha)为a确定的H在G中的左(右)陪集。,例：是的子群。 H3=0,2,4， 求H3的各个左陪集。 0H3 = 0+60, 0+62, 0+64=0,2,4 1H3 =1+60, 1+62, 1+64=1,3,5 2H3 =2+60, 2+62, 2+64=2,4,0 3H3 =3+60, 3+62, 3+64=3,5,1 4H3 =4+60, 4+62, 4+64=4,0,2 5H3 =5+60, 5+62, 5+64=5,1,3,可以看出： 0H3=2H3=4H3 =0,2,4 1H3=3H3=5H3