Semigroup with involution: Difference between revisions

Revision as of 15:14, 24 March 2025

Latest revision as of 04:02, 27 April 2025

(4 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 34 ⟶ 35:

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|Munn|1993}}</ref>

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, |1998|p. =116}}</ref> A ''projection'' is an idempotent element ''e'' that is also hermitian, meaning that ''ee'' = ''e'' and ''e''* = ''e''. Every projection is a partial isometry, and for every partial isometry ''s'', ''s''*''s'' and ''ss''* are projections. If ''e'' and ''f'' are projections, then ''e'' = ''ef'' if and only if ''e'' = ''fe''.<ref name="L117">{{harvcoltxt|Lawson, |1998|p. =117}}</ref>

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''&sdot;''t'' = ''st'' if ''s''*''s'' = ''tt''*.<ref>{{harvcoltxt|Lawson, |1998|p. =118}}</ref>

=== 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 |1998|p.=122 and }}</ref><ref>{{harvcoltxt|Lawson|1998|p.=35}}</ref>

The [[partial isometry|partial isometries]] in a C*-algebra are exactly those defined in this section. In the case of ''M''_''n''('''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''_''n''('''C''') form an inverse semigroup with the product <math>A(A^*A\wedge BB^*)B</math>.<ref>{{harvcoltxt|Lawson |1998|p.=120}}</ref>

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 |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.

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^+\,</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}}

* Mark V. Lawson (1998). "Inverse semigroups: the theory of partial symmetries". [[World Scientific]] {{isbn|981-02-3316-7}}

* {{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}}