离散数学-群

第7章群、环和域《离散数学》课程讲义课件大连海事大学计算机科学与技术学院本章及第8章讨论一些具体的代数系统：群、环、域、格与布尔代数等内容。具有一个二元运算的群；具有两个二元运算的环和域；具有两个二元运算的格；具有两个二元运算和一个一元运算的布尔代数；我们只讲一下群。7.1半群与独异点1.半群与独异点定义7.1.1给定S，*，*是S上的二元运算，（1）若*是可结合的，则称S，*为半群。注：半群就是由集合及其上定义的一个可结合的二元运算组成的代数系统。（2）若*是可结合的且具有幺元e，则称S，*为含幺半群或独异点，并记作S,*,e.例7.1.1N，+，N，×是半群，也是含幺半群。例7.1.3ρ(S),∪是半群,幺元是Φ，ρ(S),∩也是半群,幺元是S,都是含幺半群P196习题-2x□(y□z)=x□(y*a*z)=x*a*(y*a*z)=(x□y)□z=(x*a*y)□z=(x*a*y)*a*z(由*可结合的）2.可交换半群定义7.1.2若S，*是半群，若运算*是可交换的，则称S，*为可交换半群。例N，+，N，×是半群，且是可交换半群。例设S为非空集合，则〈ρ(S)，∩〉,〈ρ(S)，∪〉（1）运算“∩”和“∪”可结合，是半群；（2）运算“∩”存在幺元S，“∪”存在幺元Φ，是含幺半群；（3）运算“∩”和“∪”可交换，是可交换半群；故〈ρ(S)，∩〉和〈ρ(S)，∪〉是可交换含幺半群。3子半群(定义7.1.3)设S,*是半群，且非空HS.若运算*在H上是封闭的，则H，*也是一个半群，称H，*是S，*的子半群。设S,*,e是含幺半群，且HS.若运算*在H上封闭且eH，则称H,*,e是S,*,e的子含幺半群(子独异点)。例R，×是半群，IR，且×在集合I上封闭，则I，×是R，×的子半群。例S，*是一个半群，*运算的运算表如左下：d是幺元；{d},*,{c,d},*,{b,c,d},*是其含幺子半群；{b,c},*,{c},*是其子半群；{a,b},*不是其子半群。*abcdadcaabbbbbcccccdabcd定理7.1.1设S,*是一个半群，若S是个有限集，则必有aS，使得a*a=a.定理7.1.2设S,*,e是一个含幺半群，则关于运算*的运算表中任何两行或两列都是不相同的。定理7.1.3设S,*是一个可交换含幺半群，H是S的等幂元素所构成的集合，则H,*是S,*的子含幺半群。证由幺元eS且是等幂的，所以eH；设a,bH,因H中元素都是等幂的，故a*a=a,b*b=b,可得(a*b)*(a*b)=(a*b)*(b*a)=a*(b*b)*a=a*b*a=a*a*b=a*b说明a*b也是等幂的，故a*bH，即*对于H是封闭的。故H,*是S,*的子含幺半群。4循环半群定义7.1.4给定半群S,*(或含幺半群S,*,e),若存在g∈S，对任意a∈S，都有n∈N，使得a=gn，则称该半群为循环半群（或循环含幺半群）。称g为循环半群的生成元，亦称元素g生成了循环半群。例代数系统I+,+是个循环半群，它的生成元是1.例7.1.8P172循环半群证明定理7.1.4任何一个循环半群（或含幺循环半群）都是可交换半群（或含幺可交换半群）。定理7.1.5设S,*是一个半群，H是S中任一元素的幂所构成的集合，则H,*是S,*的子半群，且是个循环子半群。(该定理的证明自己练习)5半群同态定义7.1.5设U=X,ο和V=Y,*是两个半群，ο和*都是二元运算，函数f：X→Y，若对任意的x,y∈X，有：f(xοy)=f(x)*f(y)(运算的象=象的运算）则称f是代数系统U到V的一个半群同态映射（简称同态）与代数系统同态概念完全一样。定理7.1.6设f为从代数系统X，ο和Y，*满同态映射，若X，ο是半群（或含幺半群，可交换半群），则Y，*也是半群（或含幺半群，可交换半群）。由满同态单方向地保持性质可直接得到结论。7.2群的定义及基本性质1.群的基本概念群的定义设G，*是一个代数系统，若二元运算*满足（1）可结合性（结合律）半群（2）存在幺元（单位元素）含幺半群（3）G中每个元素都存在逆元.群则称代数系统G，*是群。注：群是半群和含幺半群的特例。有限群设G，*是一个群，若集合G是无限集,则称G，*是无限群。否则称为有限群，|G|称为群的阶。阿贝尔群设G，*是一个群，若*是可交换的,则称群G，*为可交换群或阿贝尔群。例R，×不是群；而R-{0}，×是群。例7.2.1I，+是阿贝尔群。例7.2.2G={α，β，γ，δ}，验证G，*是群。可验证运算*是可结合的，α是幺元，且每个元素都可逆，*可交换，故是阿贝尔群，|G|=4,4阶群。*αβγδααβγδββαδγγγδβαδδγαβ2.群的基本性质定理群中无零元；定理设G，*是一个群，对于任意a,b∈G，方程a*x=b和y*a=b在G中都有唯一解。定理设G，*是半群（或满足结合律），对任意a,b∈G，若方程a*x=b和y*a=b在G中有解，则G，*是群。定理设G，*是一个群，对于任意的a,b,c∈G，有(a*b=a*c)b=c,(b*a=c*a)b=c(消去律）定理设G，*是一个群，对于任意a,b∈G，有(a*b)-1=b-1*a-1(运算的逆=逆的运算的交换）定理群的运算表中每一行或每一列都是G中元素的双变换。G中每个元素在每一行必出现且仅出现一次。例P198习题-18若群G,*中每个元素的逆是其自身，证该群是阿贝尔群。证只需证运算*可交换。对任意的a,b∈G,a*b=a-1*b-1=(b*a)-1=b*a故G,*是阿贝尔群。例7.2.4P175:自己练习例P198习题-17S,*是有限可交换含幺半群，且对任意的a,b,c∈S，若a*b=a*cb=c.证S,*是阿贝尔群。证只需证S中每个元素都可逆。因S,*是有限可交换含幺半群，所以S是有限集。不妨令S={a1,a2,…,an},对任意a∈S，有{a*a1,a*a2,…,a*an}S,又由对任意的ai,aj∈S，若a*ai=a*aj,可推得ai=aj.所以a*ai互不相同，即{a*a1,a*a2,…,a*an}=S又S中有幺元e,故必存在某个ak∈S,使a*ak=e.又*可交换，a*ak=ak*a=e,即a-1=ak,由a任意，每个元素都可逆，即S,*是群，又因可交换，故是阿贝尔群。3群同态的例子参见P177例7.2.67.3循环群与变换群1循环群定义设G,*是群，若G中的每个元素都是G中某个固定元素a的整数幂，则称群G,*为循环群。称群是由a生成的,记为G=(a).元素a称为群G的生成元。例1整数加群I,+是循环群：1是其生成元1m=m,1-m=-m-1也是其生成元。故I=(1)=(-1).例2G={…,5-2,5-1,1,5,25,…}，则G,×是群，是循环群故G=（5）.讨论一下循环群的结构：命题1:设循环群G=(a)，若a的所有不同的整数幂都互不相等，则G中含有无限多个元素，且有G=(a)={…,a-2,a-1,a0,a1,a2,…}命题2:设循环群G=(a)，若a的所有不同的整数幂中有两个是相等的，则G中存在最小的正整数n使得an=e，且有G=(a)={a0,a1,a2…,an-1}定义设群G,*中任一元素a，若存在使an=e的最小的正整数n，则称a的周期(或阶)为n。若正整数n不存在，则称a的周期（或阶）是无限的。注周期的概念是对群中任一元素来定义的，任意群其幺元的周期一定是1。对循环群，有时称其生成元的周期为循环群的周期。例整数加群I,+,其幺元0的周期是1,其他元素周期无限.其为循环群，生成元是1,故该循环群的周期为无限。例Zm,+m是群,且是周期为m的循环群(剩余类加法群)Zm={[0],[1],[2],…,[m-1]},[i]+m[j]=[(i+j)(modm)];[i],[j]∈Zm证明：见P179例7.3.3的证明定理设循环群G=(a),若a为无限周期，则(a)与I,+同构；若a的周期为m，则(a)与Zm,+m同构；注循环群只有两种，生成元的周期无限时，它与整数加群代数相等；生成元的周期为m时，它与模为m的剩余加群代数相等。例定理任何一个循环群必是阿贝尔群。证设G=(a)，则G中任一元素都可写成a的幂的形式。对任意x,y∈G，x*y=am*an=am+n=an*am=y*x*可交换，故是阿贝尔群。群中元素周期的性质：定理设a是群G,*一个元素，若a的周期为n,则am=en|m（n整除m）定理群中元素a和它的逆元a-1必具有相同的周期。定理在有限群G,*中，每个元素都有一个有限周期，且每个元素的周期不超过该群的阶|G|。2变换群定义集合A上的一些双变换的集合与复合运算构成的群叫做变换群。（A的双变换指A上的双射函数）Cayley定理任一个群与一个变换群同构。*对群的研究归结为对变换群的研究3置换群定义含n个元素的有限集A上的一些置换的集合与复合运算构成的群叫做置换群。A的所有置换的集合与复合运算构成的群叫做叫做A的n次对称群。（A的置换指有限集合A上的双射函数）定理任一个有限群与一个置换群同构。*对有限群的研究归结为对置换群的研究7.4子群1子群定义定义设G，*是一个群，H是G的非空子集，若H，*也是一个群，则称H，*是G，*的子群。简称H是G的子群。注G,*和{e},*都是G，*的子群，称为平凡子群，其他的子群称为非平凡子群（或真子群）。判断H是子群的步骤：（1）封闭性；（2）含幺元；（3）每个元素均可逆；2判断子群的方法定理群G,*的非空子集H构成G的子群的充要条件：（1）封闭性：a,b∈Ha*b∈H;（2）可逆性:a∈Ha-1∈H.定理群G,*的非空子集H构成G的子群的充要条件：若a,b∈H,则a*b-1∈H.特别地，对于有限群，定理若H,*是有限群G,*的子代数，则H,*是有限群G,*的子群。例P189例7.4.5设G,*是一个群，令C={a∈G|a*x=x*a,x∈G},证明C,*是G,*的一个子群。证显然CG,下面证封闭性和可逆性。①封闭性：若a,b∈C,证a*b∈C。对任意x∈G，(a*b)*x=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b==x*(a*b)故a*b∈C;②可逆性：若a∈C,证a-1∈C。明显e∈C，对任x∈G，a-1*x=a-1*x*a*a-1=a-1*(x*a)*a-1=a-1*(a*x)*a-1=(a-1*a)*x*a-1=x*a-1故a-1∈C;因此C是G的子群。（习题-25与之类似）3子群的陪集与拉格朗日定理(P185)1）陪集定义（定义7.4.2）设H,*是群G,*的子群，a是G中的任意元素，则：①把集合aH={a*h|h∈H}称为G中的子群H的左陪集；而把集合∑={aH|a∈G}称G关于子群H的左商集。②把集合Ha={h*a|h∈H}称为G中的子群H的右陪集；而把集合∑’={Ha|a∈G}称G关于子群H的右商集。2）陪集性质定理7.4.4设H,*是群G,*的子群，则：①若a∈bH,则aH=bH；②若a∈Hb,则Ha=Hb；定理7.4.5设H,*是群G,*的子群，则H的左/右商集：∑={aH|a∈G}或∑’={Ha|a∈G}恰为群G的一个划分。3）拉格朗日定理定理设G是含n个元素的有限群，H为G中含m个元素的子群，即|G|=n，|H|=m，则m|n(m是n的因子）。推论1：任何质数阶的群不可能有非平凡子群。推论2：设G，*是n阶有限群，则对于任意的a∈G，a的周期必是n的因子且必有an=e。例P189例7.4.7