第12讲 代数结构的概念和群 主要内容: 1.了解代数结构、半群、独异点、子代数、代数同态与同构的定义. 2.理解群的有关内容, 如群的定义、Abel群和循环群的定义、子群的定义等.
Chapter 5 代数结构 本章将介绍代数结构的一般概念及常见的几种代数结构, 它是一种用代数方法建立的数学模型. 代数结构 = 代数 = 抽象代数= 近世代数, 它始于19世纪初, 形成于20世纪30年代, 在这期间, 挪威数学家N. H. Abel、法国数学家E. Galois、英国数学家A. De Morgan和G. Boole等人都作出了杰出的贡献.
代数结构研究由一般元素(不仅仅是数字、符号等)组成的集合上的运算,以及运算满足一些给定性质的数学结构的性质. 计算机科学很大部分研究的是“代数”—数据集合上进行操作. 前面讨论的Chapter 1是集合代数, Chapter 2是关系代数, Chapter 3+4是逻辑代数等. 代数结构在计算机科学中起着重要作用,众所周知利用布尔代数可进行逻辑电路设计的分析和优化. 代数结构的研究采用的是形式化方法, 对于培养大家的抽象思维和计算思维能力是非常有用的.
5.1 代数结构简介 1.代数结构的定义 “代数”总是与运算联系在一起的. 5.1 代数结构简介 1.代数结构的定义 “代数”总是与运算联系在一起的. Def 设A是非空集合, f1, f2,…, fk(k 1)是A上的代数(封闭)运算,则集合A连同其上的代数运算称为代数结构(algebra structure)或代数系统(algebra system)或简称代数(algebra),记为(A, f1, f2,…, fk),在已知运算的情况下可简记为A.
对于代数结构的理解, 需注意以下几点： (1)A非空; (2)代数运算; (3)(k + 1)-元组(A, f1, f2,…, fk); (4)运算的元数可以相同. 例5-1(P136): (1)(R, +): Group. (2)(R, +, ): Ring. (3) Boolean Algebra. 有限代数与无限代数?
2.两种最简单的代数结构: 半群及独异点 Def 设*是非空集合S上的2元代数运算, 若*满足结合律, 即对于任意x, y, z S,有(x*y)*z = x*(y*z), 则(S, *)称是半群(semigroup). 例5-2 实数集合R关于其上的乘法运算“”作成一个半群(R, ).
例5-3 设是若干个字母组成的集合,称为字母表,由中有限个字母组成的序列称为上的串,不含任何字母的串称为空串,记为. 令 例5-3 设是若干个字母组成的集合,称为字母表,由中有限个字母组成的序列称为上的串,不含任何字母的串称为空串,记为. 令*是所有上的串组成的集合, 其上的运算◦为 *上的连接运算: 很容易验证: (*, ◦)是半群. 实际上, 上的所有非空串组成的集合+, 关于其上的串的连接运算也构成一个半群(+, ◦).
例5-4 在例5-3中, (*, ◦, )是独异点, 而(+, ◦)不是. Def 5-4 设*是非空集合M上的2元代数运算,若*满足结合律且M关于*有幺元e, 即对于任意xM, 有e*x = x*e = x, 则称(M, *, e)为独异点(monoid). 含幺半群就是独异点. (R, )? 例5-4 在例5-3中, (*, ◦, )是独异点, 而(+, ◦)不是. M
Remarks (1)在(*, ◦ , )中的称为代数常数. 代数结构中的代数常数可以不止一个, 例如在后面将学习的布尔代数就有2个代数常数. 当然也可以没有代数常数. (还要看是否强调该元素) (2) (*, ◦)是半群, (*, ◦ , )是独异点, 它们是两个不同的代数结构. 正因为这样,一个最好的处理方式是将代数常数看作是0元运算,(*, ◦, )有1个0元运算(及1个二元运算),布尔代数有2个0元运算.
这是一种形式化研究方法. 先看一个关于有限半群结论的推导方法. Theorem 5-1 设(S, *)是有限半群, 则(S, *)中存在幂等元素. 先定义任意元素a的正整数方幂: R, : R, +:
Proof 取
3.子代数 讨论代数结构,一种常用的方法是根据其子代数所具有的性质去推测原代数的性质. Def 5-5 设(A, f1, f2,…, fk)是代数结构, S A,若(S, f1, f2,…, fk)是代数结构,则称其为(A, f1, f2,…, fk)的子代数(subalgebra),或在不强调运算情况下简称S是A的子代数. 一般地,要验证S是否是A的子代数,只要验证S关于A中运算是否封闭即可.
例5-5 在例5-1(2)中,有(Z, +, .)是(R, +, .)的子代数, 因为整数集合Z关于加法运算和乘法运算是封闭的. 例5-6 由第1章1-3节很容易知道,(Z8, 8, 1)是独异点,其中Z8 = {0, 1, 2, 3, 4, 5, 6, 7}, 是8模8的乘法运算. 取S = {0, 2, 4}, 这时S关于运算是封闭的, 但因为1 S,即S关于Z8中的0元运算不封闭, 所以S不是Z8的子代数.
4.代数结构的同态与同构 借助于同态映射也是研究代数结构的方法之一: 映射的作用体现. 为了讨论方便,先给出 Def 5-6 设(A, f1, f2,…, fk)和(B, g1, g2,…, gk)是代数结构,若fi与gi有相同的运算元数, i = 1, 2, …, k,则称这两个代数结构是同类型的. 下面给出的是一般的两个代数结构同态的定义,针对具体的重要代数结构还会重新给出定义的.
Def 5-7 设(A, f1, f2,…, fk)和(B, g1, g2,…, gk)是同类型的代数结构,若存在:AB且保持所有运算,即对于ni元运算fi和gi,有 即先(在A中)运算再映射等于先映射再(在B中)运算, 则称为(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的同态映射,称(A, f1, f2,…, fk)和(B, g1, g2,…, gk)同态(homomorphism). 请注意同态映射与同态的区别与联系
例5-7 对于代数结构(Z, +, .)和 ,令 是(Z, +, .)到 的同态映射. Proof 对于任意x, y Z, 因为 所以, 是(Z, +, .)到 的同态映射.
例5-8 证明: (*, ◦ , )与(N, +, 0)同态. Proof 保持2元运算? 保持0元运算?
下述定理说明了研究代数结构同态映射的必要性. Theorem 5-2 设是代数结构(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的同态映射,则 是B的子代数,称为同态映射的同态像. 对于仅一个2元运算的两个代数结构(A, *)和(B, ◦) : (1)若*在A中可交换,则◦在(A)中可交换. (2)若*在A中可结合,则◦在(A)中可结合. (3)若*在A中有幺元e,则◦在(A)中有幺元(e). (4)若*在A中有零元,则◦在(A)中有零元(). (5)若x关于*在A中有逆元x-1,则(x)关于在(A)中有逆元(x-1).
定理5-2说明,代数结构的大部分性质都可以在其同态像中得到保持,于是同态像是在同态映射下的缩影,因此可以通过对往往较简单的同态像的性质的讨论去探测其原像的性质. 下面的例子可以进一步帮助理解同态像是如何对原代数结构进行缩影的.
例5-9 验证: 代数结构(Z, .)与(B, *)同态,其中“.”Z上的乘法运算, B = {正, 负, 零},B上的运算定义见下表: Hint * 正 负 零 正 负 零 负 正 零 零 零 零
(B, *)将整数集合上乘法运算的特征完全表示出来了. 但请注意, 两个同态的代数结构之间可能存在多个同态映射,请自己举例加以说明.
下面给出的是一般的两个代数结构(单同态、满同态)同构的定义. Def 5-8 设是代数结构(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的同态映射, (1)若是单射,则称为(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的单同态映射. (2)若是满射,则称为(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的满同态映射. (3)若是双射,则称为(A, f1, f2,…, fk)到(B, g1, g2,…, gk)的同构映射,称代数结构(A, f1, f2,…, fk)与(B, g1, g2,…, gk)同构(isomorphism):
由定义知, 两个同构的代数结构在本质上是完全相同的, 所不同的仅仅是集合中的元素符号可能不同, 其上的运算符号也可能不同,参见下面的例子. 例5-10 (A, *): * a b a b b a
(B, +): Def 5-9 设是代数结构(A, f1, f2,…, fk)到(A, f1, f2,…, fk)的同态(构)映射, 则称是(A, f1, f2,…, fk)的自同态(构)映射. + 偶 奇 偶 奇 奇 偶
5.2 群 我们知道, 一元四次及以下的方程有求根公式. 在1824年由挪威数学家Niels Henrik Abel (1802~1829)严格证明了一元五次方程不可能根式求解, 后来由正在念大学年仅20岁的法国数学家Evarisfe Galois(1811~1832)用置换群的方法证明了: 一般的一元五次及以上的方程没有求根公式, 完全解决了长达200多年的难题. E. Galois超越时代的天才思想在他去逝约40年后才被人理解和接受, 正是由于他的奇特思想和巧妙方法才有今天的近世代数, 即代数结构.
群除有一个非空集合G外,更重要的是集合G上的代数运算“”及所满足的运算性质. 1.群的定义 群除有一个非空集合G外,更重要的是集合G上的代数运算“”及所满足的运算性质. Def 5-10 设G是非空集合, 是G上的代数运算,若下列3个条件成立,则称为群(group). (1) 满足结合律; (2)G关于有单位元, 通常记为e; (3)G中每一个元素在G中都有逆元. 封闭性,结合性,单位元,逆元.
正如在第1章1. 3节所说, 运算符号可以根据需要选取,当然可以按上节用号表示 正如在第1章1.3节所说, 运算符号可以根据需要选取,当然可以按上节用号表示. 选择“”,是因为群中的运算可以读作“乘”(product, multiplication). 在群的记号(G, )中, 不强调单位元素e, 有关e的结论可从元素的逆元中得到. 同时, 在仅讨论群时, 可以省略运算符号, 但我们不打算这样做. 跟上节一样, 在不强调群的运算符号时, 可以将(G, )记为G.
下面是群的例子. 例5-11 验证: 整数集合Z关于数的加法运算+构成群. Solution 因为Z关于+是封闭的且满足 (1)+运算满足结合律; (2)Z关于+有单位元0: x + 0 = 0 + x = x; (3)Z中每一个元素x Z, 都有逆元- x Z: x + (-x) = (-x) + x = 0. 所以, (Z, +)是群.
同样可知, 实数集合R关于数的加法运算+构成群(R, +) 同样可知, 实数集合R关于数的加法运算+构成群(R, +). 但R关于数的乘法运算不能作成群, 即(R, )不是群, 因为0 R, 但0关于乘法运算没有逆元, 即不存在x R满足: x 0 = 0 x = 1. 例5-12 验证: 非0实数集合R- {0}关于数的乘法运算构成群. Hint 封闭性?
n阶有限群与无限群. 上面两个例子所举的群都是无限群. 下面是有限群的例子. 例5-13 设A = R – {0,1},在A上定义6个映射(P142): Key 运算表?
由群的定义知,群是含有幺元e的半群. 在下面讨论群的性质时,关键是利用“群中任意元素均存在逆元”. Theorem 5-3 设是(G, )群, 则满足消去律. Hint
Abel群 Def 设(G, )是群, 若其运算是可交换的, 则称 (G, )为交换群(commutative group)或Abel群(Abelian group). 容易知道, 例5-11和例5-12是阿贝尔群，例5-13是非阿贝尔群.
循环群(cyclic group): (1)群中元素的整数方幂an(n Z) Remark 方幂运算是对群中的运算来说的. 如在群(Z, +)中, 有:
(2)循环群 设(G, )是群, a G, 若G中任意元素均为元素a的某整数方幂, 即 则称(G, )为循环群(cyclic group) . 容易验证，(Zm，+m)是m阶循环群，(Z, +)是无限循环群.
2. 子群 群的子代数—子群. Def 设(G, )是群, H G,若H关于群G的运算构成群(H, ),则称(H, )是(G, )的子群(subgroup),记为(H, ) (G, ),可简记为H G. 根据定义容易验证(Z, +) (R, +). 对于任意群(G, ),设e为其单位元,则{e}和G都是G的子群,称为G的平凡子群.
子群的判定定理： 定理 设(G, )是群, H G, 则H G当且仅当下列条件成立: (1)x, y H, 有x y H, 且 (2)xH, 则x在G中的逆元x-1 H. Proof 必要性显然. 为证明充分性,根据子群定义, 只需证明G中的单位元eH即可.
例5-14 设(G, )是群, 令Z(G)表示所有与G中元素可交换的元素组成的集合,即Z(G) = {x|xG, a G: xa = ax},则Z(G) G, Z(G)称为G的中心. Proof Z(G)非空? (1)x, y Z(G), 有x y Z(G). (2) x Z(G), 则x在G中的逆元x-1 Z(G). 可以证明Lagrange定理：若G是有限群，H≤G，则|H|||G|.
3 群的同态 借助于映射讨论是研究群的一种重要方法. Def (G1, *)和(G2, ◦)是群:
(1)若是单射,则称为(G1, *)到群(G2, ◦)的单同态映射. (3)若是双射,则称为(G1, *)到群(G2, ◦)的同构映射, 记为(G1, *) (G2, ◦).
例5-15 设(R+, )是正实数集合关于数的乘法运算构成的群, (R, +)是实数集合关于数的加法运算构成的群, 证明: 群(R+, )与群(R, +)同态. Proof : R+ R, (x) = lnx. 对数的作用: 乘法转换为加法?