半群
![本頁使用了標題或全文手工轉換](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.
|