Semigroup with involution: Difference between revisions

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 |1998|p. =51}}</ref>
 
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\,</math> emphasizedemphasizes that the union is actually a [[disjoint union]].) In the case were the two sets are finite, their union ''Y'' is sometimes called an ''[[Alphabet (computer science)|alphabet]] with involution''<ref name="EhrenfeuchtHarju1999">{{cite bookharvcoltxt|author1=Andrzej Ehrenfeucht|author2=T. Harju|author3=Grzegorz Rozenberg|title=The Theory of 2-structures: A Framework for Decomposition and Transformation of Graphs|year=1999|publisherpages=World Scientific|isbn=97813-981-02-4042-4|pages=13–1414}}</ref> or a ''symmetric alphabet''.<ref name="Sakarovitch">{{cite bookharvcoltxt|title=Elements of Automata TheorySakarovitch|publisher=Cambridge University Press2009|pages=305–306|author=Jacques Sakarovitch305-306}}</ref> Let <math>\theta:X\rightarrow X^\dagger</math> be a bijection; <math>\theta</math> is naturally [[Function (mathematics)#Restrictions and extensions|extended]] to a bijection <math>{ }\dagger: Y \to Y</math> essentially by taking the disjoint union of <math>\theta</math> (as a set) with its [[inverse function|inverse]], or in [[piecewise]] notation:<ref name="Lipscomb1996">{{cite bookharvcoltxt|author=Stephen Lipscomb|title=Symmetric Inverse Semigroups|year=1996|publisher=American Mathematical Soc.|isbn=978-0-8218-0627-2|pagep=86}}</ref>
 
: <math display=block>y^\dagger =
\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]]:
 
: <math display=block>w = w_1w_2 \cdots w_k \in Y^+</math> for some letters <math>w_i\in Y.</math>
 
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"/>
 
: <math display=block>w^\dagger=w_k^\dagger w_{k-1}^\dagger \cdots w_{2}^\dagger w_{1}^\dagger.</math>
 
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^+\,</math> (and likewise on <math>Y^*\,</math>). The qualifier "free" for these constructions is justified in the usual sense that they are [[universal algebra|universal construction]]s. In the case of the free semigroup with involution, given an arbitrary semigroup with involution <math>S\,</math> and a map <math>\Phi:X\rightarrow S</math>, then a [[semigroup homomorphism]] <math>\overline\Phi:(X\sqcup X^\dagger)^+\rightarrow S</math> exists such that <math>\Phi = \iota \circ \overline\Phi</math>, where <math>\iota : X \rightarrow (X\sqcup X^\dagger)^+</math> is the [[inclusion map]] and [[composition of functions]] is taken in [[Function composition#Alternative notations|diagram order]].<ref name="L172"/> The construction of <math>(X\sqcup X^\dagger)^+</math> as a semigroup with involution is unique up to [[isomorphism]]. An analogous argument holds for the free monoid with involution in terms of [[monoid homomorphism]]s and the uniqueness up to isomorphism of the construction of <math>(X\sqcup X^\dagger)^*</math> as a monoid with involution.
 
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">{{cite bookharvcoltxt|editor1=Manfred Droste Petre|editor2=Werner Kuich Salomaa|editor3=Heiko Vogler|title=Handbook of Weighted Automata|year=2009|publisher=Springer |isbn=978-3-642-01492-5|page=271|author1=Ion Petre |author2=[[Arto Salomaa]] |chapter=Algebraic Systems and Pushdown Automata}}</ref> (This latter choice of terminology conflicts however with the use of "involutive" to denote any semigroup with involution—a practice also encountered in the literature.<ref name="Neeb2000">{{cite book|author=Karl-Hermann Neeb|title=Holomorphy and Convexity in Lie Theory|year=2000|publisher=Walter de Gruyter|isbn=978-3-11-015669-0|page=21}}</ref><ref name="BeltramettiCassinelli2010">{{cite book|author1=Enrico G. Beltrametti|author2=Gianni Cassinelli|title=The Logic of Quantum Mechanics|year=2010|orig-year=1981|publisher=Cambridge University Press|isbn=978-0-521-16849-6|page=178}}</ref>)
 
== Baer *-semigroups ==
Line 125 ⟶ 126:
 
==See also==
* [[Dagger category]] (aka category with involution) — generalizes the notion*-monoids
* [[*-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}}