近世代数中英对照学习一、字母表atom：原子automorphism：自同构binary operation：二元运算Boolean algebra：布尔代数bounded lattice：有界格center of a group：群的中心closure：封闭commutative(Abelian) group：可交换群，阿贝尔群commutative(Abelian) semigroup：可交换半群comparable：可比的complement：补concatenation：拼接congruence relation：同余关系cycle：周期cyclic group：循环群cyclic semigroup：循环半群determinant：行列式disjoint：不相交distributive lattice：分配格entry：元素epimorphism：满同态factor group：商群free semigroup：自由半群greatest element：最大元greatest lower bound：最大下界，下确界group：群homomorphism：同态idempotent element：等幂元identity：单位元，么元identity：单位元，么元inverse：逆元isomorphism：同构join：并kernel：同态核lattice：格least element：最小元least upper bound：最小上界，上确界left coset：左陪集lower bound：下界lower semilattice：下半格main diagonal：主对角线maximal element：极大元meet：交minimal element：极小元minimal generating set：最小生成集monomorphism：单同态normal subgroup：正规子群，不变子群octic group(group of symmetries of the square)：八阶群，平方对称群orbit：轨道order：群的阶，元素的阶partially ordered set (poset)：偏序集partition：分割quotient semigroup：商半群retract：收缩retraction map：收缩映射semigroup with identity, monoid：含么半群，独异点semigroup：半群semilattice：子半格string, word：字符串，单词subgroup：子群sublattice：子格subsemigroup：子半群symmetric group：对称群total ordering, chain, linear ordering：全序，链，线序upper bound：上界upper semilattice：上半格二、本章内容及教学要点：8.1Partially Ordered Sets Revisited教学内容：poset，(least)upper bound，greatest element，(greatest)lower bound，least element，maximal(minimal) element，upper(lower) semilattice8.2Semigroups and Semilattices教学内容: semigroup，Abelian semigroup，monoid，subsemigroup，free semigroup，minimal generating set，congruence relation，quotient semigroup，semilattice，idempotent element8.3 Lattices教学内容：lattice，sublattice，bounded lattice，distributive lattice，Boolean algebra，complement，atom8.4 Groups教学内容：group，identity，inverse，commutative(Abelian) group，order，subgroup，cyclic group，left coset8.5 Groups and Homomorphisms教学内容：monomorphism，epimorphism，isomorphism，normal subgroup，octic group(group of symmetries of the square)定理证明及例题解答三、前言代数的概念与方法是研究计算机科学和工程的重要数学工具. 众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等等. 近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具. 在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型理论中，在描述机器可计算的函数、研究计算复杂性、刻画抽象数据结构、研究程序设计学中的语义学、设计逻辑电路中有着十分广泛的应用.为什么要研究代数系统？代数是专门研究离散对象的数学，是对符号的操作.它是现代数学的三大支柱之一（另两个为分析与几何）.代数从19世纪以来有惊人的发展，带动了整个数学的现代化.随着信息时代的到来，计算机、信息都是数字（离散化）的，甚至电视机．摄像机、照相机都在数字化.知识经济有人也称为数字经济.这一切的背后的科学基础，就是数学，尤其是专门研究离散对象的代数.代数发端于“用符号代替数”，后来发展到以符号代替各种事物.在一个非空集合上，确定了某些运算以及这些运算满足的规律，于是该非空集合中的元素就说是有了一种代数结构.现实世界中可以有许多具体的不相同的代数系统. 但事实上，不同的代数系统可以有一些共同的性质. 正因为此，我们要研究抽象的代数系统，并假设它具有某一类具体代数系统共同拥有的性质.任何在这个抽象系统中成立的结论，均可适用于那一类代数系统中的任何一个.代数学历史悠久. 代数的发展可分成两个阶段. 19世纪这前的代数称为古典代数，19世纪至今的代数称为近世代数（抽象代数）.远在古希腊时期，人们就知道可以用符号代表所解问题中的未知数，并且这些符号可以像数一样进行运算，直到获得问题的解.古典代数的基本研究对象是方程，它是以讨论方程的解法为中心. 在古典代数中，每一个符号代表的总是一个数，但这个数可以是整数也可以是实数. 古典代数的主要目标是用代数运算解一元多次方程. 它成功地解决了一元二次、一元三次和一元四次方程的求解问题.19世纪初，人们逐渐认识到，符号不仅可以代表数，而且可以代表任何事物. 在这种思想认识的支配下，人们开始将任意集合上所进行的代数运算作为研究的对象，从而出现了近世代数体系和方法.19世纪30年代，在寻找一元五次方程根式求解方法的过程中，年青的法国数学家伽罗瓦(E. Galois)首次得出了群的概念—用置换群的方法彻底证明了高于四次的代数方程的根式不可解性. 起初他的奇思妙想和巧妙方法虽然并不被当时人接受和理解，却发展出了一门新的学科—抽象代数学.抽象代数学的研究对象是抽象的，它不是以某一具体事物为研究对象，而是以一大类具有共同性质的事物为研究对象. 因此其研究成果适用于这一类事物中的每一个，从而收到事半功倍之效.抽象代数学的主要内容是研究各种各样的代数系统.它把一些形式上很不相同的代数系统，用统一的方法描述、研究和推理，从而得到反映出它们共性的一些本质的结论，然后再把这些结论应用到具体的代数系统中. 从而抽象产生了广泛的应用.抽象代数学在计算机中有着十分重要的应用. 100多年来，随着科学的发展，抽象代数越来越显示出它在数学的各个分支、物理学、化学、力学、生物学等科学领域的重要作用. 抽象代数的概念和方法也是研究计算科学的重要数学工具.有经验和成熟的计算科学家都知道，除了数理逻辑外，对计算科学最有用的数学分支学就是代数，特别是抽象代数. 抽象代数是关于运算的学问，是关于计算规则的学问.在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而抽象代数研究的中心问题就是一种很重要的数学结构—代数系统：半群、群、格与布尔代数等等. 计算科学的研究也离不开抽象代数的应用：半群理论在自动机理论和形式语言中发挥了重要作用；有限域理论是编码理论的数学基础，在通讯中起过重要的作用；至于格和布尔代数则更不用说了，是电子线路设计、电子计算机硬件设计和通讯系统设计的重要工具.另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识.这一章我们将介绍近世代数中最基本的代数系统：群和半群，它们在计算学科中有十分广泛的应用：半群在形式语言和自动机理论中有着重要的应用，群则可应用于编码理论之中.四、中英对照8.1 Partially Ordered Sets Revisited定义8.1.1 A relation R on A is a partial ordering(偏序) if it is reflexive, antisymmetric, and transitive.If the relation R on A is a partial ordering, then (A,R) is a partially ordered set or poset (偏序集)with ordering R.由于集合中的偏序关系是Z，R上的“≤”、“≥”的推广，故常用“≤”表示一般的偏序关系，偏序集用(A, ≤)表示. Note that the symbol ≤ is being used to denote the distinct partial orders.定义8.1.2Two elements a and b of the partially ordered set (S,≤) are comparable if either a≤b or b≤a. If every two elements of a poset (S, ≤) are comparable,then ≤ is a total ordering.在一个偏序集中，往往有一些特殊元素需要加以注意和研究：定义8.1.3Let (A, ≤) be a poset and B a nonempty subset of A. An element a in A is called an upper bound of B(B的上界)if b≤a for all b in B. The element a is called a least upper bound(B 的上确界) of B if (1) a is an upper bound of B and (2) any other upper bound a1of B, if exists, then a≤a1.An element a in B is called a greatest element(B的最大元) of B if x≤a for all x in B.An element a in A is called a lower bound of B(B的下界)if a≤b for all b in B. The element a is called a greatest lower bound(B的下确界) of B if (1) a is a lower bound of B and (2) any other lower bound a1 of B, if exists, then a1≤a. An element a in B is called a least element(B的最小元) of B if a≤x for all x in B.定义8.1.4Let (A, ≤) be a poset and B a nonempty subset of A. An element a in B is called a maximal element of B(B的极大元)if for every element b of B, a≤b implies a=b. An element a in B is called a minimal element of B(B的极小元)if for every e lement b of B, b≤a implies a=b.例8.1.1 Let A be the poset of nonnegative real numbers with the usual partial order ≤.Then 0 is a minimal element of A. There are no maximal element of A. The poset Z with the usual partial order ≤ has no minimal elements a nd no maximal elements.例8.1.2 Let A={a,b,c}. Then in the poset (P(A),⊆), the empty set Φis a least element of A, and the set A is a greatest element of A.例8.1.3 设A=P({a，b，c})，偏序关系为集合的包含关系“⊆”，B={{b，c}，{a，c}}，则B的上界为{a，b，c}，下界为{c}，Ф；最大(小)元不存在，极大(小)元都是{b，c}，{a，c}.例8.1.4 设A={2，3，4，6，7，8，12}，A上的偏序关系为|(整除关系)；B={8，12}，C={2，4，12}，则B无上界，下界为2，4；最大(小)元无，极大(小)元8，12；C的上界12，下界为2；最大元为12，最小元为2，极大元12，极小元为2.定理8.1.1 Let A be a finite nonempty p oset with partial order ≤. Then A has at least one maximal element and at least one minimal element.定理8.1.2 A poset has at most one greatest element and at most one least element.定理8.1.3 Let (A, ≤) be a poset. Then a nonempty subset B of A has at most one lub and at most glb.(设(A, ≤)为偏序集，Φ≠B⊆A. 若B有上(下)确界，则它们是惟一的)证明定理8.1.3定义8.1.5 A poset A for which all two-element subsets have a least upper bound in A is called an upper semilattice(上半格).In an upper semilattice A, we can define a binary operation ∨(+) as a∨b=lub{a,b}. Then (A, ∨) is an algebraic structure.定义8.1.6 A poset A for which all two-element subsets have a greatest lower bound in A is called an lower semilattice(下半格).In a lower semilattice A, we can define a binary operation ∧(〃) as a∧b=glb{a,b}. Then (A, ∧) is an algebraic structure.定理8.1.4(a)Let A be a n upper semilattice. Then for all a,b,c∈A, a∨(b∨c)=(a∨b)∨c, a∨a=a and a∨b=b∨a.(b) Let A be a lower semilattice.Then for all a,b,c∈A, a∧(b∧c)=(a∧b)∧c, a∧a=a and a∧b=b∧a.ASSIGNMENTS：PP209-210：6，8，9，10，11，12，30，328.2Semigroups and Semilattices定义8.2.1 A binary operation(二元运算)on the set S is a function f: S×S→S.A binary operation exhibits the property of closure wherein the result of the operation on two members a and b of S is also a member of S.定义8.2.2 A set S with a binary operation﹡on S such that for all a,b and c in S, (a﹡b)﹡c=a﹡(b﹡c) is called a semigroup(半群) and is denoted by (S,﹡) of simply S if the operation is understood.设(S,﹡)是一个代数结构. 若﹡是一个可结合的二元运算，即：∀a，b，c∈S，(a﹡b)﹡c=a﹡(b﹡c)，则称(S,﹡)为半群.定义8.2.3Let (S,﹡) be a semigroup. If a﹡b=b﹡a for all a,b in S, then (S,﹡) is called a(commutative) Abelian semigroup(可交换半群，阿贝尔半群). If there is an element 1 in (S,﹡) such that 1﹡a=a﹡1=a for all a in S, then 1 is called the identity(单位元，么元) of (S,﹡) and (S,﹡) is called a semigroup with identity or a monoid(含么半群，独异点).例8.2.1 (Z,+)，(Z,×)都是半群；(Z,－)不是半群；设A为任一集合，则(P(A),∪)，(P(A),∩)都是半群. (Z,+)，(Z,×)，(P(A),∪)，(P(A),∩)都是可交换半群. (Z,+)，(Z,×)都是含么半群，么元分别是0和1. (P(A),∪)，(P(A),∩)也都是含么半群，么元分别是Φ和A.定义8.2.4Let (S,﹡) be a semigroup and T be a nonempty subset of S.If ﹡is a binary operation on T, then T is a subsemigroup(子半群) of S.(T, ﹡) is a subsemigroup of (S, ﹡) if and only if T is a nonempty subset of S and for every a, b∈T, a﹡b∈T.例8.2.2 ({所有偶数},+)是(Z，+)的子半群.例8.2.3 Let S be the set of all functions from a nonempty set A to itself with the binary operation composition of functions. Then S is a semigroup and the identity function I:A→A, defined by I(a)=a for all a∈A, is the identity of A so that S is a monoid.例8.2.4 设A是有限个符号组成的集合，称为字母表，A上的串就是A 中有限个字母组成的有序集合，空串记为 .A*表示A上的串集合，A*上的连接运算 定义为α,β∈A*，α β=αβ，则(A*, )是一个含么半群，称为由A上的自由半群(The free semigroup on the alphabet A).例8.2.5 Let Z n={[0],[1],[2],…,[n-1]} be the set of integers modulo n. Then (Z n,+) and (Z n,〃) are both commutative monoid.定义8.2.5Let (S,﹡) be a semigroup and a be a element of S. Define a n recursively by a1=a and a n=a﹡a n-1 for n>1.Obviously, a k﹡a m=a k+m for all integers k,m>0.定义8.2.6Let (S,﹡) be a semigroup and a be a element of S. Let the set <a>={a n:n>0}={a,a2,a3,…}.Then <a> is a subsemigroup of S. It is called the cyclic semigroup generated by a(由a生成的循环子半群).定理8.2.1 Let (S,﹡) be a semigroup and a1,a2,…,a k∈S.Let A={a1,a2,…,a k} and A*=<a1,a2,…,a k> be the set consisiting of all finite products of a1,a2,…,a k.Then A* is a semigroup. Furthermore, A* is the smallest semigroup of S containing A.定义8.2.7The semigroup A* is called the semigroup generated by A. If for every proper subset B of A, B*≠A*, then A is called a minimal generating set of A*(最小生成集).定义8.2.8Let (S,﹡) and (T,〃) be semigroups and f:S→T be a function such that f(a﹡b)=f(a)〃f(b) for all a,b in S. The function f is called a homomorphism from S to T (从S到T的同态映射).定理8.2.2 Let (S,﹡) and (T,〃) be semigroups and f:S→T be a homomorphism from S to T.(a) If S1 is a subsemigroup of S, then f(S1) is a subsemigroup of T.(b) If T1 is a subsemigroup of T, then f-1(T1) is a subsemigroup of S.定义8.2.9Let (S,﹡) be a semigroup and R be an equivalence relation on S. If R has the property that if aRb and cRd then (a ﹡c)R(b﹡d) for all a,b,c,d ∈S, Then R is called a congruence relation(同余关系).定理8.2.3 The equivalence classes of a congruence relation R on a semigroup （S,﹡) form a semigroup under the binary operation 。