Content deleted Content added
m Dating maintenance tags: {{Cn}} |
Adding local short description: "Semigroup in abstract algebra", overriding Wikidata description "semigroup equipped with an involutive anti-automorphism" |
||
(5 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 9 ⟶ 10:
An example from [[linear algebra]] is a set of real-valued n-by-n square matrices with the matrix-transpose as the involution. The [[Map (mathematics)|map]] which sends a matrix to its [[transpose]] is an involution because the transpose is well defined for any matrix and obeys the law {{nowrap|1=(''AB'')<sup>T</sup> = ''B''<sup>T</sup>''A''<sup>T</sup>}}, which has the same form of interaction with multiplication as taking inverses has in the [[general linear group]] (which is a subgroup of the full linear monoid). However, for an arbitrary matrix, ''AA''<sup>T</sup> does not equal the identity element (namely the [[diagonal matrix]]). Another example, coming from [[formal language]] theory, is the [[free semigroup]] generated by a [[nonempty set]] (an [[Alphabet (computer science)|alphabet]]), with string [[concatenation]] as the binary operation, and the involution being the map which [[String (computer science)#Reversal|reverse]]s the [[linear order]] of the letters in a string. A third example, from basic [[set theory]], is the set of all [[binary relation]]s between a set and itself, with the involution being the [[converse relation]], and the multiplication given by the usual [[composition of relations]].
Semigroups with involution appeared explicitly named in a 1953 paper of [[Viktor Wagner]] (in Russian) as result of his attempt to bridge the theory of semigroups with that of [[semiheap]]s.<ref name="Hollings2014">{{
==Formal definition==
Line 20 ⟶ 21:
Semigroups that satisfy only the first of these axioms belong to the larger class of [[U-semigroup]]s.
In some applications, the second of these axioms has been called [[antidistributive]].<ref name="BrinkKahl1997">{{
==Examples==
# If ''S'' is a [[commutative]] semigroup then the [[identity function|identity map]] of S is an involution.
# If ''S'' is a [[group (mathematics)|group]] then the inversion map * : ''S'' → ''S'' defined by ''x''* = ''x''<sup>−1</sup> is an involution. Furthermore, on an [[abelian group]] both this map and the one from the previous example are involutions satisfying the axioms of semigroup with involution.<ref name="BergChristensen2012">{{
# If ''S'' is an [[inverse semigroup]] then the inversion map is an involution which leaves the [[idempotent]]s [[Invariant (mathematics)|invariant]]. As noted in the previous example, the inversion map is not necessarily the only map with this property in an inverse semigroup. There may well be other involutions that leave all idempotents invariant; for example the identity map on a commutative regular, hence inverse, semigroup, in particular, an abelian group. A [[regular semigroup]] is an [[inverse semigroup]] if and only if it admits an involution under which each idempotent is an invariant.<ref>Munn, Lemma 1</ref>
# Underlying every [[C*-algebra]] is a *-semigroup. An important [[C*-algebra#Finite-dimensional C*-algebras|instance]] is the algebra ''M''<sub>''n''</sub>('''C''') of ''n''-by-''n'' [[matrix (mathematics)|matrices]] over '''[[Complex number|C]]''', with the [[conjugate transpose]] as involution.
Line 32 ⟶ 33:
==Basic concepts and properties==
An element ''x'' of a semigroup with involution is sometimes called ''hermitian'' (by analogy with a [[Hermitian matrix]]) when it is left invariant by the involution, meaning ''x''* = ''x''. Elements of the form ''xx''* or ''x''*''x'' are always hermitian, and so are all powers of a hermitian element. As noted in the examples section, a semigroup ''S'' is an [[inverse semigroup]] if and only if ''S'' is a [[regular semigroup]] and admits an involution such that every idempotent is hermitian.<ref>{{harvcoltxt|Easdown
Certain basic concepts may be defined on *-semigroups in a way that parallels the notions stemming from a [[Regular semigroup|regular element in a semigroup]]. A ''partial isometry'' is an element ''s'' such that ''ss''*''s'' = ''s''; the set of partial isometries of a semigroup ''S'' is usually abbreviated PI(''S'').<ref>{{harvcoltxt|Lawson
Partial isometries can be [[partial order|partially ordered]] by ''s'' ≤ ''t'' defined as holding whenever ''s'' = ''ss''*''t'' and ''ss''* = ''ss''*''tt''*.<ref name="L117"/> Equivalently, ''s'' ≤ ''t'' if and only if ''s'' = ''et'' and ''e'' = ''ett''* for some projection ''e''.<ref name="L117"/> In a *-semigroup, PI(''S'') is an [[ordered groupoid]] with the [[Partial groupoid|partial product]] given by ''s''⋅''t'' = ''st'' if ''s''*''s'' = ''tt''*.<ref>{{harvcoltxt|Lawson
=== Examples ===
In terms of examples for these notions, in the *-semigroup of binary relations on a set, the partial isometries are the relations that are [[difunctional]]. The projections in this *-semigroup are the [[partial equivalence relation]]s.<ref>{{harvcoltxt|Lawson
The [[partial isometry|partial isometries]] in a C*-algebra are exactly those defined in this section. In the case of ''M''<sub>''n''</sub>('''C''') more can be said. If ''E'' and ''F'' are projections, then ''E'' ≤ ''F'' if and only if [[Image (mathematics)|im]]''E'' ⊆ im''F''. For any two projection, if ''E'' ∩ ''F'' = ''V'', then the unique projection ''J'' with image ''V'' and kernel the [[orthogonal complement]] of ''V'' is the meet of ''E'' and ''F''. Since projections form a meet-[[semilattice]], the partial isometries on ''M''<sub>''n''</sub>('''C''') form an inverse semigroup with the product <math>A(A^*A\wedge BB^*)B</math>.<ref>{{harvcoltxt|Lawson
Another simple example of these notions appears in the next section.
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
If in the above construction instead of <math>Y^+\,</math> we use the [[free monoid]] <math>Y^*=Y^+\cup\{\varepsilon\}</math>, which is just the free semigroup extended with the [[empty word]] <math>\varepsilon\,</math> (which is the [[identity element]] of the [[monoid]] <math>Y^*\,</math>), and suitably extend the involution with <math>\varepsilon^\dagger = \varepsilon</math>,
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 133 ⟶ 134:
==References==
* Mark V. Lawson (1998). "Inverse semigroups: the theory of partial symmetries". [[World Scientific]] {{isbn|981-02-3316-7}}▼
* D J Foulis (1958). ''Involution Semigroups'', PhD Thesis, Tulane University, New Orleans, LA. [http://www.math.umass.edu/~foulis/publ.txt Publications of D.J. Foulis] (Accessed on 5 May 2009)
* {{cite book|last=Coxeter|first=H.S.M.|author-link=Donald Coxeter|title=Introduction to Geometry|year=1961}}
* W.D. Munn, ''Special Involutions'', in A.H. Clifford, K.H. Hofmann, M.W. Mislove, ''Semigroup theory and its applications: proceedings of the 1994 conference commemorating the work of Alfred H. Clifford'', Cambridge University Press, 1996, {{isbn|0521576695}}.
* Drazin, M.P., ''Regular semigroups with involution'', Proc. Symp. on Regular Semigroups (DeKalb, 1979), 29–46
* Nordahl, T.E., and H.E. Scheiblich, Regular * Semigroups, [[Semigroup Forum]], 16(1978), 369–377.
* {{citation|last1=Yamada|first1=Miyuki|date=December
* {{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|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}}
* {{PlanetMath attribution|id=8283|title=Free semigroup with involution}}
{{Use dmy dates|date=September 2019}}
|