Archive:Inverse semigroup: Difference between revisions

No edit summary
 
wikademia>Wikademia
m Text replace - 'w:' to 'Wikipedia:'
 
(26 intermediate revisions by 15 users not shown)
Line 1: Line 1:
An inverse semigroup <math>S</math> is a [[semigroup]] such that for every <math>x \in S</math> there is a unique '''inverse''' <math>y</math> such that <math>x = xyx</math> and <math>y = yxy</math>
In mathematics, an '''inverse semigroup''' ''S'' is a [[semigroup]] in which every element ''x'' in ''S'' has a unique '''inverse'''
''y'' in ''S'' in the sense that ''x = xyx'' and ''y = yxy''.  Inverse semigroups appear in a range of contexts; for
example, they can be employed in the study [[partial symmetries]].<ref>Lawson 1998.</ref>
{{RightToc}}
(The convention followed in this article will be that of writing a function on the right of its argument, and
composing functions from left to right &mdash; a convention often observed in semigroup theory.)
 
== Origins ==
Inverse semigroups were introduced independently by [[Viktor Vladimirovich Wagner]]<ref>Since his father was German, Wagner preferred the German transliteration of his name (with a "W", rather than a "V") from Cyrillic - see Schein 1981.</ref> in the [[Soviet Union]] in 1952<ref>First a short announcement in Wagner 1952, then a much more comprehensive exposition in Wagner 1953.</ref>, and by [[Gordon Preston]] in [[Great Britain]] in 1954<ref>Preston 1954a,b,c.</ref>.  Both authors arrived at inverse semigroups via the study of partial one-one transformations of a [[Set (mathematics)|set]]: a [[partial function|partial transformation]] &alpha; of a set ''X'' is a [[Function (mathematics)|function]] from ''A'' to
''B'', where ''A'' and ''B'' are subsets of ''X''.  Let &alpha; and &beta; be partial transformations of a set
''X''; &alpha; and &beta; can be composed (from left to right) on the largest [[Domain (mathematics)|domain]] upon
which it "makes sense" to compose them:
:dom &alpha;&beta; = [im &alpha; <math>\cap</math> dom &beta;]&alpha;<sup>&minus;1</sup>
where &alpha;<sup>&minus;1</sup> denotes the [[preimage]] under &alpha;.  Partial transformations had already been studied
in the context of [[pseudogroup]]s.<ref>See, for example, Golab 1939.</ref>  It was Wagner, however, who
was the first to observe that the composition of partial transformations is a special case of the multiplication of
[[binary relations]].<ref>Schein 2002 : 152.</ref>  He recognised also that the domain of composition of two partial
transformations may be the [[empty set]], so he introduced an ''empty transformation'' to take account of this. 
With the addition of this empty transformation, the composition of partial transformations of a set becomes an
everywhere-defined [[associative]] [[binary operation]].  Under this composition, the collection
<math>\mathcal{I}_X</math> of all partial one-one transformations of a set ''X'' forms an inverse semigroup, called
the ''symmetric inverse semigroup'' (or monoid) on ''X''.<ref>Howie 1995 : 149.</ref>  This is the "archetypal"
inverse semigroup, in the same way that a [[symmetric group]] is the archetypal [[group (mathematics)|group]].  For
example, just as every [[group (mathematics)|group]] can be embedded in a [[symmetric group]], every inverse
semigroup can be embedded in a symmetric inverse semigroup (see below).
 
== The basics ==
The inverse of an element ''x'' of an inverse semigroup ''S'' is usually written ''x''<sup>&minus;1</sup>.  Inverses in an
inverse semigroup have many of the same properties as inverses in a [[group (mathematics)|group]], for example,
(''ab'')<sup>&minus;1</sup> = ''b''<sup>&minus;1</sup>''a''<sup>&minus;1</sup>.  In an inverse [[monoid]], ''xx''<sup>&minus;1</sup> and
''x''<sup>&minus;1</sup>''x'' are not (necessarily) equal to the identity, but they are both [[idempotent]].<ref>Howie
1995 : Proposition 5.1.2(1).</ref>  An inverse monoid ''S'' in which ''xx''<sup>&minus;1</sup> = 1 =
''x''<sup>&minus;1</sup>''x'', for all ''x'' in ''S'' (a ''unipotent'' inverse monoid), is, of course, a [[group (mathematics)|group]].
 
There are a number of equivalent characterisations of an inverse semigroup ''S'':<ref>Howie 1995 : Theorem
5.1.1.</ref>
* Every element of ''S'' has a unique inverse, in the above sense.
* Every element of ''S'' has at least one inverse (''S'' is a [[regular semigroup]]) and [[idempotent]]s commute (that is, the [[idempotent]]s of ''S'' form a [[semilattice]]).
* Every <math>\mathcal{L}</math>-class and every <math>\mathcal{R}</math>-class contains precisely one [[idempotent]], where <math>\mathcal{L}</math> and <math>\mathcal{R}</math> are two of [[Green's relations]].
The [[idempotent]] in the <math>\mathcal{L}</math>-class of ''s'' is ''s''<sup>&minus;1</sup>''s'', whilst the
[[idempotent]] in the <math>\mathcal{R}</math>-class of ''s'' is ''ss''<sup>&minus;1</sup>.  There is therefore a simple
characterisation of [[Green's relations]] in an inverse semigroup:<ref>Howie 1995 : Proposition 5.1.2(1).</ref>
:<math>a\,\mathcal{L}\,b\Longleftrightarrow a^{-1}a=b^{-1}b,\quad a\,\mathcal{R}\,b\Longleftrightarrow
aa^{-1}=bb^{-1}</math>
 
Examples of inverse semigroups:
*Every [[group (mathematics)|group]] is an inverse semigroup.
*The [[bicyclic semigroup]] is inverse, with (''a'',''b'')<sup>&minus;1</sup> = (''b'',''a'').
*Every [[semilattice]] is inverse.
*The [[Brandt semigroup]] is inverse.
*The [[Munn semigroup]] is inverse.
 
Unless stated otherwise, ''E(S)'' will denote the semilattice of idempotents of an inverse semigroup ''S''.
 
== The natural partial order ==
An inverse semigroup ''S'' possesses a ''natural [[partial order]]'' relation &le; (sometimes denoted by &omega;)
which is defined by the following:<ref>Wagner 1952.</ref>
:<math>a \leq b \Longleftrightarrow a=eb,</math>
for some [[idempotent]] ''e'' in ''S''.  Equivalently,
:<math>a \leq b \Longleftrightarrow a=bf,</math>
for some (in general, different) [[idempotent]] ''f'' in ''S''.  In fact, ''e'' can be taken to be
''aa''<sup>&minus;1</sup> and ''f'' to be ''a''<sup>&minus;1</sup>''a''.<ref>Howie 1995 : Proposition 5.2.1.</ref>
 
The natural [[partial order]] is compatible with both multiplication and inversion, that is,<ref>Howie 1995 :
152&ndash;3</ref>
:<math>a \leq b, c \leq d \Longrightarrow ac \leq bd</math>
and
:<math>a \leq b \Longrightarrow a^{-1} \leq b^{-1}.</math>
 
In a [[group (mathematics)|group]], this [[partial order]] simply reduces to equality, since the identity is the
only [[idempotent]].  In a symmetric inverse semigroup, the [[partial order]] reduces to restriction of mappings,
i.e., &alpha; &le; &beta; if, and only if, the domain of &alpha; is contained in the domain of &beta; and
''x''&alpha; = ''x''&beta;, for all ''x'' in the domain of &alpha;.<ref>Howie 1995 : 153.</ref>
 
The natural partial order on an inverse semigroup interacts with [[Green's relations]] as follows: if ''s'' &le;
''t'' and ''s''<math>\,\mathcal{L}\,</math>''t'', then ''s'' = ''t''.  Similarly, if
''s''<math>\,\mathcal{R}\,</math>''t''.<ref>Lawson 1998 : Proposition 3.2.3.</ref>
 
On ''E(S)'', the natural [[partial order]] becomes:
:<math>e \leq f \Longleftrightarrow e = ef,</math>
so the product of any two [[idempotent]]s in ''S'' is equal to the lesser of the two, with respect to
&le;.  If ''E(S)'' forms a [[chain (order theory)|chain]] (i.e., ''E(S)'' is [[totally ordered]] by &le;), then
''S'' is a [[union (set theory)|union]] of [[group (mathematics)|groups]].<ref>Clifford & Preston 1967 : Theorem
7.5</ref>
 
== Homomorphisms and representations of inverse semigroups ==
A [[homomorphism]] (or ''morphism'') of inverse semigroups is defined in exactly the same way as for any other
semigroup: for inverse semigroups ''S'' and ''T'', a [[function (mathematics)|function]] &theta; from ''S'' to ''T''
is a morphism if (''s''&theta;)(''t''&theta;) = (''st'')&theta;, for all ''s'',''t'' in ''S''.  The definition of a
morphism of inverse semigroups could be augmented by including the condition (''s''&theta;)<sup>&minus;1</sup> =
''s''<sup>&minus;1</sup>&theta;, however, there is no need to do so, since this property follows from the above
definition, via the following theorem:
 
'''Theorem.'''  The homomorphic [[image (mathematics)|image]] of an inverse semigroup is an inverse semigroup; the
inverse of an element is always mapped to the inverse of the [[image (mathematics)|image]] of that
element.<ref>Clifford & Preston 1967 : Theorem 7.36.</ref>
 
One of the earliest results proved about inverse semigroups was the ''Wagner-Preston Theorem'', which is an analogue
of [[Cayley's Theorem]] for [[group (mathematics)|groups]]:
 
'''Wagner-Preston Theorem.'''  If ''S'' is an inverse semigroup, then the [[function (mathematics)|function]] &phi;
from ''S'' to <math>\mathcal{I}_S</math>, given by
:dom &phi; = ''Sa''<sup>&minus;1</sup> and ''x''(''a''&phi;) = ''xa''
is a [[faithful representation]] of ''S''.<ref>Howie 1995 : Theorem 5.1.7.  Originally, Wagner 1952 and,
independently, Preston 1954c.</ref>
 
Thus, any inverse semigroup can be embedded in a symmetric inverse semigroup.
 
== Congruences on inverse semigroups ==
[[Congruences]] are defined on inverse semigroups in exactly the same way as for any other semigroup: a
''congruence'' &rho; is an [[equivalence relation]] which is compatible with semigroup multiplication, i.e.,
:<math>a\,\rho\,b,\quad c\,\rho\,d\Longrightarrow ac\,\rho\,bd.</math><ref>Howie 1995 : 22</ref>
 
Of particular interest is the relation <math>\sigma</math>, defined on an inverse semigroup ''S'' by
:<math>a\,\sigma\,b\Longleftrightarrow</math> there exists a <math>c\in S</math> with <math>c\leq
a,b.</math><ref>Lawson 1998 : 62</ref>
It can be shown that &sigma; is a congruence and that the factor semigroup ''S''/&sigma; is, in fact, a group. 
Indeed, &sigma; is the ''smallest'' congruence on ''S'' such that ''S''/&sigma; is a group, that is, if &tau; is any
other congruence on ''S'' with ''S''/&tau; a group, then &sigma; is contained in &tau;.  The congruence &sigma; is
called the ''minimum group congruence'' on ''S''.<ref>Lawson 1998 : Theorem 2.4.1.</ref>  The minimum group
congruence can be used to give a characterisation of ''E''-unitary inverse semigroups (see below).
 
A congruence &rho; on an inverse semigroup ''S'' is called ''idempotent pure'' if
:<math>a\in S, e\in E(S), a\,\rho\,e\Longrightarrow a\in E(S).</math><ref>Lawson 1998 : 65</ref>
 
== ''E''-unitary inverse semigroups ==
One class of inverse semigroups which has been studied extensively over the years is the class of ''E-unitary
inverse semigroups'': an inverse semigroup ''S'' (with [[semilattice]] ''E'' of [[idempotent]]s) is
''E-unitary'' if, for all ''e'' in ''E'' and all ''s'' in ''S'',
:<math>es \in E \Longrightarrow s \in E.</math>
Equivalently,
:<math>se \in E \Rightarrow s \in E.</math><ref>Howie 1995 : 192.</ref>
 
One further characterisation of an ''E''-unitary inverse semigroup ''S'' is the following: if ''e'' is in ''E'' and
''e'' &le; ''s'', for some ''s'' in ''S'', then ''s'' is in ''E''.<ref>Lawson 1998 : Proposition 2.4.3.</ref>
 
'''Theorem.'''  Let ''S'' be an inverse semigroup with [[semilattice]] ''E'' of idempotents, and minimum group
congruence &sigma;.  Then the following are equivalent:<ref>Lawson 1998 : Theorem 2.4.6.</ref>
*''S'' is ''E''-unitary;
*&sigma; is idempotent pure;
*<math>\sim</math> = &sigma;,
where <math>\sim</math> is the ''compatibility relation'' on ''S'', defined by
:<math>a\sim b\Longleftrightarrow ab^{-1},a^{-1}b</math> are idempotent.
 
Central to the study of ''E''-unitary inverse semigroups is the following construction.<ref>Howie 1995 : 193&ndash;4</ref>  Let <math>\mathcal{X}</math> be a [[partially ordered set]], with ordering &le;, and let <math>\mathcal{Y}</math> be a [[subset]] of <math>\mathcal{X}</math> with the properties that
*<math>\mathcal{Y}</math> is a [[semilattice|lower semilattice]], that is, every pair of elements ''A'', ''B'' in <math>\mathcal{Y}</math> has a [[greatest lower bound]] ''A'' <math>\wedge</math> ''B'' in <math>\mathcal{Y}</math> (with respect to &le;);
*<math>\mathcal{Y}</math> is an [[order ideal]] of <math>\mathcal{X}</math>, that is, for ''A'', ''B'' in <math>\mathcal{X}</math>, if ''A'' is in <math>\mathcal{Y}</math> and ''B'' &le; ''A'', then ''B'' is in <math>\mathcal{Y}</math>.
 
Now let ''G'' be a [[group (mathematics)|group]] which [[group action|acts]] on <math>\mathcal{X}</math> (on the left), such that
*for all ''g'' in ''G'' and all ''A'', ''B'' in <math>\mathcal{X}</math>, ''gA'' = ''gB'' if, and only if, ''A'' = ''B'';
*for each ''g'' in ''G'' and each ''B'' in <math>\mathcal{X}</math>, there exists an ''A'' in <math>\mathcal{X}</math> such that ''gA'' = ''B'';
*for all ''A'', ''B'' in <math>\mathcal{X}</math>, ''A'' &le; ''B'' if, and only if, ''gA'' &le; ''gB'';
*for all ''g'', ''h'' in ''G'' and all ''A'' in <math>\mathcal{X}</math>, ''g''(''hA'') = (''gh'')''A''.
 
The triple <math>(G, \mathcal{X}, \mathcal{Y})</math> is also assumed to have the following properties:
*for every ''X'' in <math>\mathcal{X}</math>, there exists a ''g'' in ''G'' and an ''A'' in <math>\mathcal{Y}</math> such that ''gA'' = ''X'';
*for all ''g'' in ''G'', ''g''<math>\mathcal{Y}</math> and <math>\mathcal{Y}</math> have nonempty intersection.
 
Such a triple <math>(G, \mathcal{X}, \mathcal{Y})</math> is called a ''McAlister triple''.  A McAlister triple is
used to define the following:
:<math>P(G, \mathcal{X}, \mathcal{Y}) = \{ (A,g) \in \mathcal{Y}\times G : g^{-1}A \in \mathcal{Y} \}</math>
together with multiplication
:<math>(A,g)(B,h)=(A \wedge gB, gh)</math>.
Then <math>P(G, \mathcal{X}, \mathcal{Y})</math> is an inverse semigroup under this multiplication, with
(''A'',''g'')<sup>&minus;1</sup> = (''g''<sup>&minus;1</sup>''A'', ''g''<sup>&minus;1</sup>).  One of the main results in the study of
''E''-unitary inverse semigroups is ''McAlister's P-Theorem'':
 
'''McAlister's P-Theorem.'''  Let <math>(G, \mathcal{X}, \mathcal{Y})</math> be a McAlister triple.  Then <math>P(G,
\mathcal{X}, \mathcal{Y})</math> is an ''E''-unitary inverse semigroup.  Conversely, every ''E''-unitary inverse
semigroup is [[isomorphic]] to one of this type.<ref>Howie 1995 : Theorem 5.9.2.  Originally, McAlister
1974a,b.</ref>
 
== Connections with category theory ==
The above composition of partial transformations of a set gives rise to a symmetric inverse semigroup.  There is an
another way of composing partial transformations, which is more restrictive than that used above: two partial
transformations &alpha; and &beta; are composed if, and only if, the image of &alpha; is equal to the domain of
&beta;; otherwise, the composition &alpha;&beta; is undefined.  Under this alternative composition, the collection
of all partial one-one transformations of a set forms not an inverse semigroup but an [[inductive groupoid]], in the
sense of [[category theory]].  This close connection between inverse semigroups and inductive groupoids is
embodied in the ''Ehresmann-Schein-Nambooripad Theorem'', which states that an inductive groupoid can always be
constructed from an inverse semigroup, and conversely.<ref>Lawson 1998 : 4.1.8.</ref>
 
== Generalisations of inverse semigroups ==
As noted above, an inverse semigroup ''S'' can be defined by the conditions (1) ''S'' is a [[regular semigroup]],
and (2) the [[idempotent]]s in ''S'' commute; this has led to two distinct classes of generalisations of
an inverse semigroup: semigroups in which (1) holds, but (2) does not, and vice versa.
 
Examples of regular generalisations of an inverse semigroup are:<ref>Howie 1995 : Section 2.4 & Chapter 6.</ref>
*''[[Regular semigroup]]s'': a [[semigroup]] ''S'' is ''regular'' if every element has at least one inverse; equivalently, for each ''a'' in ''S'', there is an ''x'' in ''S'' such that ''axa'' = ''a''.
*''Locally inverse semigroups'': a [[regular semigroup]] ''S'' is ''locally inverse'' if ''eSe'' is an inverse semigroup, for each [[idempotent]] ''e''.
*''Orthodox semigroups'': a [[regular semigroup]] ''S'' is ''orthodox'' if its subset of [[idempotent]]s forms a subsemigroup.
*''Generalised inverse semigroups'': a [[regular semigroup]] ''S'' is called a ''generalised inverse semigroup'' if its [[idempotent]]s form a normal band, i.e., ''xyzx'' = ''xzyx'', for all [[idempotent]]s ''x'', ''y'', ''z''.
 
The [[class (set theory)|class]] of generalised inverse semigroups is the [[intersection (set theory)|intersection]] of the class of
locally inverse semigroups and the class of orthodox semigroups.<ref>Howie 1995 : 222.</ref>
 
Amongst the non-regular generalisations of an inverse semigroup are:<ref>Fountain
1979.</ref>[http://www-users.york.ac.uk/~varg1/finitela.ps]
*(Left, right, two-sided) adequate semigroups.
*(Left, right, two-sided) ample semigroups.
*(Left, right, two-sided) semiadequate semigroups.
*Weakly (left, right, two-sided) ample semigroups.
 
== Further reading ==
For a brief introduction to inverse semigroups, see either Clifford & Preston 1967 : Chapter 7 or Howie 1995 :
Chapter 5.  More comprehensive introductions can be found in Petrich 1984 and Lawson 1998.
 
== Notes ==
{{reflist|2}}
 
== References ==
*A. H. Clifford and G. B. Preston, ''The Algebraic Theory of Semigroups'', Volume 2, Mathematical Surveys of the American Mathematical Society, No. 7, Providence, R.I., 1967.
*{{cite journal | author=J. B. Fountain | title=Adequate semigroups | journal=Proceedings of the Edinburgh Mathematical Society | year=1979 | volume=22 | pages=113–125}}
*{{cite journal | author=St. Golab | title=&Uuml;ber den Begriff der "Pseudogruppe von Transformationen" | journal=Mathematische Annalen | year=1939 | volume=116 | pages=768–780 | doi=10.1007/BF01597390}}
*V. Gould, [http://www-users.york.ac.uk/~varg1/finitela.ps "(Weakly) left E-ample semigroups"]
*J. M. Howie, ''Fundamentals of Semigroup Theory'', Clarendon Press, Oxford, 1995.
*M. V. Lawson, ''Inverse Semigroups: The Theory of Partial Symmetries'', World Scientific, 1998.
*{{cite journal | author=D. B. McAlister | title=Groups, semilattices and inverse semigroups | journal=Transactions of the American Mathematical Society | year=1974a | volume=192 | pages=227–244 | doi=10.2307/1996831 }}
*{{cite journal | author=D. B. McAlister | title=Groups, semilattices and inverse semigroups II | journal=Transactions of the American Mathematical Society | year=1974b | volume=196 | pages=351–370 | doi=10.2307/1997032 }}
*M. Petrich, ''Inverse semigroups'', Wiley, New York, 1984.
*{{cite journal | author=G. B. Preston | title=Inverse semi-groups | journal=Journal of the London Mathematical Society | year=1954a | volume=29 | pages=396–403 | doi=10.1112/jlms/s1-29.4.396 }}
*{{cite journal | author=G. B. Preston | title=Inverse semi-groups with minimal right ideals | journal=Journal of the London Mathematical Society | year=1954b | volume=29 | pages=404–411 | doi=10.1112/jlms/s1-29.4.404 }}
*{{cite journal | author=G. B. Preston | title=Representations of inverse semi-groups | journal=Journal of the London Mathematical Society | year=1954c | volume=29 | pages=411–419 | doi=10.1112/jlms/s1-29.4.411 }}
*{{cite journal | author=B. M. Schein | title=Obituary: Viktor Vladimirovich Vagner (1908&ndash;1981) | journal=Semigroup Forum | year=1981 | volume=28 | pages=189–200 | doi=10.1007/BF02676643 }}
*{{cite journal | author=B. M. Schein | title=Book RevieWikipedia: "Inverse Semigroups: The Theory of Partial Symmetries" by Mark V. Lawson | journal=Semigroup Forum | year=2002 | volume=65 | pages=149–158 | doi=10.1007/s002330010132 }}
*{{cite journal | author=V. V. Wagner | title=Generalised groups | journal=[[Proceedings of the USSR Academy of Sciences]] | year=1952 | volume=84 | pages=1119–1122 }} {{ru icon}} English translation: [http://uk.geocities.com/cdhollings/vagner1.pdf]
*{{cite journal | author=V. V. Wagner | title=The theory of generalised heaps and generalised groups | journal=Matematicheskii Sbornik (N.S.) | year=1953 | volume=32(74) | pages=545–632 }} {{ru icon}}
 
== See also ==
*[[Pseudogroup]]
*[[Partial symmetries]]
*[[Regular semigroup]]
*[[Semilattice]]
*[[Green's relations]]
*[[Category theory]]
 
[[Category:Abstract algebra]]
[[Category:Semigroup theory]]