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 | 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 — 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]] α of a set ''X'' is a [[Function (mathematics)|function]] from ''A'' to | |||
''B'', where ''A'' and ''B'' are subsets of ''X''. Let α and β be partial transformations of a set | |||
''X''; α and β can be composed (from left to right) on the largest [[Domain (mathematics)|domain]] upon | |||
which it "makes sense" to compose them: | |||
:dom αβ = [im α <math>\cap</math> dom β]α<sup>−1</sup> | |||
where α<sup>−1</sup> denotes the [[preimage]] under α. 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>−1</sup>. Inverses in an | |||
inverse semigroup have many of the same properties as inverses in a [[group (mathematics)|group]], for example, | |||
(''ab'')<sup>−1</sup> = ''b''<sup>−1</sup>''a''<sup>−1</sup>. In an inverse [[monoid]], ''xx''<sup>−1</sup> and | |||
''x''<sup>−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>−1</sup> = 1 = | |||
''x''<sup>−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>−1</sup>''s'', whilst the | |||
[[idempotent]] in the <math>\mathcal{R}</math>-class of ''s'' is ''ss''<sup>−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>−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 ≤ (sometimes denoted by ω) | |||
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>−1</sup> and ''f'' to be ''a''<sup>−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–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., α ≤ β if, and only if, the domain of α is contained in the domain of β and | |||
''x''α = ''x''β, for all ''x'' in the domain of α.<ref>Howie 1995 : 153.</ref> | |||
The natural partial order on an inverse semigroup interacts with [[Green's relations]] as follows: if ''s'' ≤ | |||
''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 | |||
≤. If ''E(S)'' forms a [[chain (order theory)|chain]] (i.e., ''E(S)'' is [[totally ordered]] by ≤), 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]] θ from ''S'' to ''T'' | |||
is a morphism if (''s''θ)(''t''θ) = (''st'')θ, for all ''s'',''t'' in ''S''. The definition of a | |||
morphism of inverse semigroups could be augmented by including the condition (''s''θ)<sup>−1</sup> = | |||
''s''<sup>−1</sup>θ, 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]] φ | |||
from ''S'' to <math>\mathcal{I}_S</math>, given by | |||
:dom φ = ''Sa''<sup>−1</sup> and ''x''(''a''φ) = ''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'' ρ 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 σ is a congruence and that the factor semigroup ''S''/σ is, in fact, a group. | |||
Indeed, σ is the ''smallest'' congruence on ''S'' such that ''S''/σ is a group, that is, if τ is any | |||
other congruence on ''S'' with ''S''/τ a group, then σ is contained in τ. The congruence σ 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 ρ 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'' ≤ ''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 σ. Then the following are equivalent:<ref>Lawson 1998 : Theorem 2.4.6.</ref> | |||
*''S'' is ''E''-unitary; | |||
*σ is idempotent pure; | |||
*<math>\sim</math> = σ, | |||
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–4</ref> Let <math>\mathcal{X}</math> be a [[partially ordered set]], with ordering ≤, 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 ≤); | |||
*<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'' ≤ ''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'' ≤ ''B'' if, and only if, ''gA'' ≤ ''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>−1</sup> = (''g''<sup>−1</sup>''A'', ''g''<sup>−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 α and β are composed if, and only if, the image of α is equal to the domain of | |||
β; otherwise, the composition αβ 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=Ü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–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]] | |||