半群
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在数学中,半群是闭合于结合性二元运算之下的集合 S 构成的代数结构。
半群的运算经常指示为乘号,也就是 或简写为 xy 来指示应用半群运算于有序对 (x, y) 的结果。
半群的正式研究开始于二十世纪早期。自从1950年代,有限半群的研究在理论计算机科学中变得特别重要,因为在有限半群和有限自动机之间有自然的联系。
定义
集合S和其上的二元运算·:S×S→S。若·满足结合律,即:∀x,y,z∈S,有(x·y)·z=x·(y·z),则称有序对(S,·)为半群,运算·称为该半群的乘法。实际使用中,在上下文明确的情况下,可以简略叙述为“半群S”。
相关概念
- 幺半群(独异点)
- 若S上的乘法有幺元(单位元),即:∃1∈S,使得∀s∈S,1·s=s·1=s。则S称为幺半群(独异点)。
- 嵌入
- 任何半群S都可以嵌入到幺半群(通常指示为)中,简单的通过邻接(adjoining)一个不在S中的元素e,并定义es=s=se对于所有s∈S∪e。
- 交换半群可以嵌入到群中当且仅当它有消除性质。
例子
- 作为一种平凡的情形,空集是一个半群。
- 正整数带有加法运算。
- 闭合在半群运算下的任何半群的子集。这种子集叫做子半群。
- 运算是幂等的半群叫做带。
- 运算是幂等的和交换的半群是半格。
- 任何环的理想,给定乘法运算。任何环包括了整数、有理数、实数、复数或四元数,带有在环中的值的函数(包括序列)、多项式和矩阵。
- 在某个固定字母表 Σ 上的所有有限字符串的集合,带有字符串串接运算。如果包括了空串,则它实际上是幺半群,叫做“Σ 上的自由幺半群”;如果排除了空串,则就是半群,叫做“Σ上的自由半群”。特别地:当 |Σ| = 1 时,Σ上的自由幺半群(在同构意义下)即为自然数带有其加法构成的半群(N,+)(同时也是幺半群);而Σ上的自由半群(在同构意义下)则是正整数带有其加法构成的半群(N*,+)。
- 变换半群 : 任何有限半群 S 都可以被表示为最多 |S|+1 个状态的(状态)集合 Q 的变换。S 的每个元素 x 是 Q 到自身的映射 x: Q → Q,序列 xy 定义为 q(xy) = (qx)y 对于 Q 中的每个 q。序列明显的是结合性运算,等价于函数复合。这种表示是任何自动机或有限状态机(FSM)的基础。
- 双环半群。
- C0-半群。
- 正规半群。
- 逆半群。
历史
半群的正式研究比其他起步于十九世纪中期的代数结构如群或环要晚一些。一些来源[1][2]把(法语的)这个术语归功于 J.-A. de Séguier 在1904年在《Élements de la Théorie des Groupes Abstraits》(《抽象群论基础》)中的首次使用。这个术语的英语使用是在1908年 Harold Hinton 的《有限次序群的理论》中。在1970年,叫做《半群论坛》的新期刊(目前由Springer Verlag编辑)成为少见的完全关于半群理论的数学期刊之一。
Anton Suschkewitsch 经常被归功获得了关于半群的第一个非平凡的结果。他1928年的论文《Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit》(《关于没有唯一可逆性规则的有限群》) 确定了有限简单半群的结构并证明了有限半群的极小理想(或Green关系 J-类)是简单的[2]。在这个基点之上,半群理论的基础进一步由 David Rees、James Alexander Green、Evgenii Sergeevich Lyapin、Alfred H. Clifford 和 Gordon Preston 建立。后面二人在 1961 年出版了半群理论的专论。
有限半群理论比它的无限对应者要更加发达。这特别根源于语法半群概念,和继而在半群的伪品种和已经被证明在自动机理论中特别多产的所谓的形式语言品种之间的联系[3]。
参见
引用
- John M. Howie is the author of two books, published twenty years apart, which are often cited as a basic reference in the mathematical community.
- Howie, John M. Fundamentals of Semigroup Theory. Clarendon Press. 1995. ISBN 978-0-19-851194-6.
- Howie, John M. Introduction to Semigroup Theory. Academic Press. 1976. ISBN 978-0-12-754633-9.
- Two volumes of Samuel Eilenberg have also been a common reference for the applications of semigroup theory in theoretical computer science.
- Eilenberg, Samuel. Automata, Languages, and Machines (Vol.A). Academic Press. 1973. ISBN 978-0-12-234001-7.
- Eilenberg, Samuel. Automata, Languages, and Machines (Vol.B). Academic Press. 1976. ISBN 978-0-12-234002-4.
- The algebraic theory of semigroups, A. H. Clifford and G. B. Preston. American Mathematical Society, 1961 (volume 1), 1967 (volume 2).
- Semigroups: an introduction to the structure theory, Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
- Semigroup Forum is the best-known periodical devoted specifically to the subject of semigroups.
注释
- ^ https://web.archive.org/web/19991003231318/http://members.aol.com/jeff570/s.html Earliest Known Uses of Some of the Words of Mathematics
- ^ 2.0 2.1 http://www-users.york.ac.uk/~cdh500/suschkewitsch3.pdf[永久失效链接] An account of Suschkewitsch's paper by Christopher Hollings
- ^ Varieties of Formal Languages, J.É. Pin, Plenum Press, 1986.
|