Archive:Inverse semigroup: Difference between revisions
wikademia>CDH Expanded stub. |
wikademia>Wikademia m Text replace - 'w:' to 'Wikipedia:' |
||
| (21 intermediate revisions by 11 users not shown) | |||
| Line 1: | Line 1: | ||
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 | ''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> | 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 | (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 | composing functions from left to right — a convention often observed in semigroup theory.) | ||
== Origins == | == Origins == | ||
Inverse semigroups were introduced independently by [[Viktor Vladimirovich Wagner]] in the [[Soviet Union]] in | 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 | ||
1953.</ref>, and by [[Gordon Preston]] in [[Great Britain]] in | |||
arrived at inverse semigroups via the study of partial one-one transformations of a [[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 | ''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 | ''X''; α and β can be composed (from left to right) on the largest [[Domain (mathematics)|domain]] upon | ||
which it "makes sense" to compose them: | which it "makes sense" to compose them: | ||
:dom αβ = [im α <math>\cap</math> dom β]α<sup> | :dom αβ = [im α <math>\cap</math> dom β]α<sup>−1</sup> | ||
where α<sup> | where α<sup>−1</sup> denotes the [[preimage]] under α. Partial transformations had already been studied | ||
in the context of [[pseudogroup | 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 | 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 | [[binary relations]].<ref>Schein 2002 : 152.</ref> He recognised also that the domain of composition of two partial | ||
| Line 32: | Line 26: | ||
== The basics == | == The basics == | ||
The inverse of an element ''x'' of an inverse semigroup ''S'' is usually written ''x''<sup> | 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, | inverse semigroup have many of the same properties as inverses in a [[group (mathematics)|group]], for example, | ||
(''ab'')<sup> | (''ab'')<sup>−1</sup> = ''b''<sup>−1</sup>''a''<sup>−1</sup>. In an inverse [[monoid]], ''xx''<sup>−1</sup> and | ||
''x''<sup> | ''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> | 1995 : Proposition 5.1.2(1).</ref> An inverse monoid ''S'' in which ''xx''<sup>−1</sup> = 1 = | ||
''x''<sup> | ''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 | There are a number of equivalent characterisations of an inverse semigroup ''S'':<ref>Howie 1995 : Theorem | ||
5.1.1.</ref> | 5.1.1.</ref> | ||
* Every element of ''S'' has a unique inverse, in the above sense. | * 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 | * 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]]. | * 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> | 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> | [[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> | 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 | :<math>a\,\mathcal{L}\,b\Longleftrightarrow a^{-1}a=b^{-1}b,\quad a\,\mathcal{R}\,b\Longleftrightarrow | ||
| Line 52: | Line 46: | ||
Examples of inverse semigroups: | Examples of inverse semigroups: | ||
*Every [[group (mathematics)|group]] is an inverse semigroup. | *Every [[group (mathematics)|group]] is an inverse semigroup. | ||
*The [[bicyclic semigroup]] is inverse, with (''a'',''b'')<sup> | *The [[bicyclic semigroup]] is inverse, with (''a'',''b'')<sup>−1</sup> = (''b'',''a''). | ||
*Every [[semilattice]] is inverse. | *Every [[semilattice]] is inverse. | ||
*The [[Brandt semigroup]] is inverse. | *The [[Brandt semigroup]] is inverse. | ||
| Line 66: | Line 60: | ||
:<math>a \leq b \Longleftrightarrow a=bf,</math> | :<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 | for some (in general, different) [[idempotent]] ''f'' in ''S''. In fact, ''e'' can be taken to be | ||
''aa''<sup> | ''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 : | The natural [[partial order]] is compatible with both multiplication and inversion, that is,<ref>Howie 1995 : | ||
152 | 152–3</ref> | ||
:<math>a \leq b, c \leq d \Longrightarrow ac \leq bd</math> | :<math>a \leq b, c \leq d \Longrightarrow ac \leq bd</math> | ||
and | and | ||
| Line 85: | Line 79: | ||
On ''E(S)'', the natural [[partial order]] becomes: | On ''E(S)'', the natural [[partial order]] becomes: | ||
:<math>e \leq f \Longleftrightarrow e = ef,</math> | :<math>e \leq f \Longleftrightarrow e = ef,</math> | ||
so the product of any two [[idempotent | 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 | ≤. 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 | ''S'' is a [[union (set theory)|union]] of [[group (mathematics)|groups]].<ref>Clifford & Preston 1967 : Theorem | ||
| Line 94: | Line 88: | ||
semigroup: for inverse semigroups ''S'' and ''T'', a [[function (mathematics)|function]] θ from ''S'' to ''T'' | 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 | 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> | morphism of inverse semigroups could be augmented by including the condition (''s''θ)<sup>−1</sup> = | ||
''s''<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: | definition, via the following theorem: | ||
| Line 107: | Line 101: | ||
'''Wagner-Preston Theorem.''' If ''S'' is an inverse semigroup, then the [[function (mathematics)|function]] φ | '''Wagner-Preston Theorem.''' If ''S'' is an inverse semigroup, then the [[function (mathematics)|function]] φ | ||
from ''S'' to <math>\mathcal{I}_S</math>, given by | from ''S'' to <math>\mathcal{I}_S</math>, given by | ||
:dom φ = ''Sa''<sup> | :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, | is a [[faithful representation]] of ''S''.<ref>Howie 1995 : Theorem 5.1.7. Originally, Wagner 1952 and, | ||
independently, Preston 1954c.</ref> | independently, Preston 1954c.</ref> | ||
| Line 132: | Line 126: | ||
== ''E''-unitary inverse semigroups == | == ''E''-unitary inverse semigroups == | ||
One class of inverse semigroups which has been studied extensively over the years is the class of ''E-unitary | 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 | 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'', | ''E-unitary'' if, for all ''e'' in ''E'' and all ''s'' in ''S'', | ||
:<math>es \in E \Longrightarrow s \in E.</math> | :<math>es \in E \Longrightarrow s \in E.</math> | ||
| Line 149: | Line 143: | ||
:<math>a\sim b\Longleftrightarrow ab^{-1},a^{-1}b</math> are idempotent. | :<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 | 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 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>. | *<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>. | ||
| Line 169: | Line 163: | ||
:<math>(A,g)(B,h)=(A \wedge gB, gh)</math>. | :<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 | Then <math>P(G, \mathcal{X}, \mathcal{Y})</math> is an inverse semigroup under this multiplication, with | ||
(''A'',''g'')<sup> | (''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'': | ''E''-unitary inverse semigroups is ''McAlister's P-Theorem'': | ||
| Line 183: | Line 177: | ||
β; otherwise, the composition αβ is undefined. Under this alternative composition, the collection | β; 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 | 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 | 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 | 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> | constructed from an inverse semigroup, and conversely.<ref>Lawson 1998 : 4.1.8.</ref> | ||
== Generalisations of inverse semigroups == | == Generalisations of inverse semigroups == | ||
As noted above, an inverse semigroup ''S'' can be defined by the conditions (1) ''S'' is a [[regular semigroup]], | As noted above, an inverse semigroup ''S'' can be defined by the conditions (1) ''S'' is a [[regular semigroup]], | ||
and (2) the [[idempotent | 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. | 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> | Examples of regular generalisations of an inverse semigroup are:<ref>Howie 1995 : Section 2.4 & Chapter 6.</ref> | ||
*''[[Regular | *''[[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''. | *''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 | *''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 | *''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 | The [[class (set theory)|class]] of generalised inverse semigroups is the [[intersection (set theory)|intersection]] of the class of | ||
| Line 213: | Line 207: | ||
== Notes == | == Notes == | ||
{{reflist|2}} | |||
== References == | == 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. | *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= | *{{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= | *{{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"] | *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. | *J. M. Howie, ''Fundamentals of Semigroup Theory'', Clarendon Press, Oxford, 1995. | ||
*M. V. Lawson, ''Inverse Semigroups: The Theory of Partial Symmetries'', World Scientific, 1998. | *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= | *{{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= | *{{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. | *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 | *{{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 | *{{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 | *{{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=Book | *{{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=V. V. Wagner | title=Generalised groups | *{{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=The theory of generalised heaps and generalised groups | *{{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 == | == See also == | ||
| Line 239: | Line 234: | ||
*[[Green's relations]] | *[[Green's relations]] | ||
*[[Category theory]] | *[[Category theory]] | ||
[[Category:Abstract algebra]] | [[Category:Abstract algebra]] | ||
[[Category:Semigroup theory]] | [[Category:Semigroup theory]] | ||