Content deleted Content added
m Linked Lawson citations with Template:Harvcoltxt |
Adding local short description: "Semigroup in abstract algebra", overriding Wikidata description "semigroup equipped with an involutive anti-automorphism" |
||
(3 intermediate revisions by one other user not shown) | |||
Line 1:
{{Short description|Semigroup in abstract algebra}}
In [[mathematics]], particularly in [[abstract algebra]], a '''semigroup with involution''' or a '''*-semigroup''' is a [[semigroup]] equipped with an [[Involution (mathematics)|involutive]] [[anti-automorphism]], which—roughly speaking—brings it closer to a [[group (mathematics)|group]] because this involution, considered as [[unary operator]], exhibits certain fundamental properties of the operation of taking the inverse in a group:
Line 79 ⟶ 80:
==Free semigroup with involution ==
As with all varieties, the [[category theory|category]] of semigroups with involution admits [[free object]]s. The construction of a free semigroup (or monoid) with involution is based on that of a [[free semigroup]] (and respectively that of a free monoid). Moreover, the construction of a [[free group]] can easily be derived by refining the construction of a free monoid with involution.<ref name="L51">{{harvcoltxt|Lawson
The [[Generator (mathematics)|generators]] of a free semigroup with involution are the elements of the union of two ([[equinumerous]]) [[disjoint sets]] in [[Bijection|bijective correspondence]]: <math>Y=X\sqcup X^\dagger</math>. (Here the notation <math>\sqcup
\begin{cases}
\theta(y) & \text{if } y \in X \\
Line 91 ⟶ 92:
Now construct <math>Y^+\,</math> as the [[free semigroup]] on <math>Y\,</math> in the usual way with the binary (semigroup) operation on <math>Y^+\,</math> being [[concatenation]]:
The bijection <math>\dagger</math> on <math>Y</math> is then extended as a bijection <math>{ }^\dagger:Y^+\rightarrow Y^+</math> defined as the string reversal of the elements of <math>Y^+\,</math> that consist of more than one letter:<ref name="EhrenfeuchtHarju1999"/><ref name="Lipscomb1996"/>
This map is an [[#Formal definition|involution]] on the semigroup <math>Y^+\,</math>. Thus, the semigroup <math>(X\sqcup X^\dagger)^+</math> with the map <math>{ }^\dagger\,</math> is a semigroup with involution, called a '''free semigroup with involution''' on ''X''.<ref name="L172">{{harvcoltxt|Lawson|1998|p=172}}</ref> (The irrelevance of the concrete identity of <math>X^\dagger</math> and of the bijection <math>\theta</math> in this choice of terminology is explained below in terms of the universal property of the construction.) Note that unlike in [[#ex6|Example 6]], the involution ''of every letter'' is a distinct element in an alphabet with involution, and consequently the same observation extends to a free semigroup with involution.
Line 102 ⟶ 103:
we obtain a '''free monoid with involution'''.<ref name="Lipscomb1996"/>
The construction above is actually the only way to extend a given map <math>\theta\,</math> from <math>X\,</math> to <math>X^\dagger\,</math>, to an involution on <math>Y^+
The construction of a [[free group]] is not very far off from that of a free monoid with involution. The additional ingredient needed is to define a notion of [[reduced word]] and a [[rewriting]] rule for producing such words simply by deleting any adjacent pairs of letter of the form <math>xx^\dagger</math> or <math>x^\dagger x</math>. It can be shown than the order of rewriting (deleting) such pairs does not matter, i.e. any order of deletions produces the same result.<ref name="L51"/> (Otherwise put, these rules define a [[Confluence (abstract rewriting)|confluent]] rewriting system.) Equivalently, a free group is constructed from a free monoid with involution by taking the [[quotient (universal algebra)|quotient]] of the latter by the [[Congruence relation|congruence]] <math>\{ (yy^\dagger, \varepsilon) : y\in Y\}</math>, which is sometimes called the '''Dyck congruence'''—in a certain sense it generalizes [[Dyck language]] to multiple kinds of "parentheses" However simplification in the Dyck congruence takes place regardless of order. For example, if ")" is the inverse of "(", then <math>()=)(=\varepsilon</math>; the one-sided congruence that appears in the Dyck language proper <math>\{ (xx^\dagger, \varepsilon) : x\in X\}</math>, which instantiates only to <math>()=\varepsilon</math> is (perhaps confusingly) called the '''Shamir congruence'''. The quotient of a free monoid with involution by the Shamir congruence is not a group, but a monoid <!--with involution?-->; nevertheless it has been called the '''free half group''' by its first discoverer—[[Eli Shamir]]—although more recently it has been called the '''involutive monoid''' generated by ''X''.<ref name="Sakarovitch"/><ref name="DrosteKuich2009">{{
== Baer *-semigroups ==
Line 125 ⟶ 126:
==See also==
* [[Dagger category]] (aka category with involution) — generalizes
* [[*-algebra]]
* [[Special classes of semigroups]]
Line 140 ⟶ 141:
* {{citation|last1=Yamada|first1=Miyuki|date=December 1982|title=P-systems in regular semigroups|journal=[[Semigroup Forum]]|volume=24|issue=1|pages=173-187}}
* {{citation|last1=Easdown|first1=David|last2=Munn|first2=Walter Douglas|year=1993|title=On semigroups with involution|journal=Bulletin of the Australian Mathematical Society|volume=48|issue=1|doi=10.1017/S0004972700015495|pages=93-100}}
* {{cite book|first=Stephen|last=Lipscomb|title=Symmetric Inverse Semigroups|year=1996|publisher=American Mathematical Soc.|isbn=978-0-8218-0627-2}}
* {{cite book|last1=Brink|first1=Chris|last2=Kahl|first2=Wolfram|last3=Schmidt|first3=Gunther|title=Relational Methods in Computer Science|date=1997|publisher=Springer|isbn=978-3-211-82971-4}}
* {{cite book|last=Lawson|first=Mark|year=1998|title=Inverse semigroups: the theory of partial symmetries|publisher=[[World Scientific]]|isbn=981-02-3316-7}}
* {{cite book|first1=Andrzej|last1=Ehrenfeucht|first2=T.|last2=Harju|first3=Grzegorz|last3=Rozenberg|title=The Theory of 2-structures: A Framework for Decomposition and Transformation of Graphs|year=1999|publisher=World Scientific|isbn=978-981-02-4042-4}}
* S. Crvenkovic and Igor Dolinka, "[http://people.dmi.uns.ac.rs/~dockie/papers/031.pdf Varieties of involution semigroups and involution semirings: a survey]", Bulletin of the Society of Mathematicians of Banja Luka Vol. 9 (2002), 7–47.
* {{cite book|title=Elements of Automata Theory|year=2009|publisher=Cambridge University Press|first=Jacques|last=Sakarovitch}}
* {{cite book|editor1=Manfred Droste |editor2=Werner Kuich |editor3=Heiko Vogler|title=Handbook of Weighted Automata|year=2009|publisher=Springer |isbn=978-3-642-01492-5|first1=Ion|last1=Petre|first2=Arto|last2=Salomaa|author-link2=Arto Salomaa|chapter=Algebraic Systems and Pushdown Automata}}
* {{cite book|first1=C.|last1=van den Berg|first2=J. P. R.|last2=Christensen|first3=P.|last3=Ressel|title=Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions|year=2012|publisher=Springer Science & Business Media|isbn=978-1-4612-1128-0}}
* {{cite book|first=Christopher|last=Hollings|title=Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups|year=2014|publisher=[[American Mathematical Society]]|isbn=978-1-4704-1493-1}}
|