Inverse semigroup

From Wikipedia, the free encyclopedia

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 of partial symmetries.^[1]

(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^[2] in the Soviet Union in 1952,^[3] and by Gordon Preston in Great Britain in 1954.^[4] Both authors arrived at inverse semigroups via the study of partial one-one transformations of a set: a partial transformation α of a set X is a 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 upon which it "makes sense" to compose them:

dom αβ = [im α $\cap$ dom β]α⁻¹

where α⁻¹ denotes the preimage under α. Partial transformations had already been studied in the context of pseudogroups.^[5] 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.^[6] 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 ${\mathcal {I}}_{X}$ of all partial one-one transformations of a set X forms an inverse semigroup, called the symmetric inverse semigroup (or monoid) on X.^[7] This is the "archetypal" inverse semigroup, in the same way that a symmetric group is the archetypal group. For example, just as every 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⁻¹. Inverses in an inverse semigroup have many of the same properties as inverses in a group, for example, (ab)⁻¹ = b⁻¹a⁻¹. In an inverse monoid, xx⁻¹ and x⁻¹x are not (necessarily) equal to the identity, but they are both idempotent.^[8] An inverse monoid S in which xx⁻¹ = 1 = x⁻¹x, for all x in S (a unipotent inverse monoid), is, of course, a group.

There are a number of equivalent characterisations of an inverse semigroup S:^[9]

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 idempotents commute (that is, the idempotents of S form a semilattice).
Every ${\mathcal {L}}$ -class and every ${\mathcal {R}}$ -class contains precisely one idempotent, where ${\mathcal {L}}$ and ${\mathcal {R}}$ are two of Green's relations.

The idempotent in the ${\mathcal {L}}$ -class of s is s⁻¹s, whilst the idempotent in the ${\mathcal {R}}$ -class of s is ss⁻¹. There is therefore a simple characterisation of Green's relations in an inverse semigroup:^[10]

$a\,{\mathcal {L}}\,b\Longleftrightarrow a^{{-1}}a=b^{{-1}}b,\quad a\,{\mathcal {R}}\,b\Longleftrightarrow aa^{{-1}}=bb^{{-1}}$

Examples of inverse semigroups:

Every group is an inverse semigroup.
The bicyclic semigroup is inverse, with (a,b)⁻¹ = (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:^[11]

$a\leq b\Longleftrightarrow a=eb,$

for some idempotent e in S. Equivalently,

$a\leq b\Longleftrightarrow a=bf,$

for some (in general, different) idempotent f in S. In fact, e can be taken to be aa⁻¹ and f to be a⁻¹a.^[12]

The natural partial order is compatible with both multiplication and inversion, that is,^[13]

$a\leq b,c\leq d\Longrightarrow ac\leq bd$

and

$a\leq b\Longrightarrow a^{{-1}}\leq b^{{-1}}.$

In a 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 α.^[14]

The natural partial order on an inverse semigroup interacts with Green's relations as follows: if s ≤ t and s $\,{\mathcal {L}}\,$ t, then s = t. Similarly, if s $\,{\mathcal {R}}\,$ t.^[15]

On E(S), the natural partial order becomes:

$e\leq f\Longleftrightarrow e=ef,$

so the product of any two idempotents in S is equal to the lesser of the two, with respect to ≤. If E(S) forms a chain (i.e., E(S) is totally ordered by ≤), then S is a union of groups.^[16]

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 θ 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θ)⁻¹ = s⁻¹θ, however, there is no need to do so, since this property follows from the above definition, via the following theorem:

Theorem. The homomorphic image of an inverse semigroup is an inverse semigroup; the inverse of an element is always mapped to the inverse of the image of that element.^[17]

One of the earliest results proved about inverse semigroups was the Wagner-Preston Theorem, which is an analogue of Cayley's Theorem for groups:

Wagner-Preston Theorem. If S is an inverse semigroup, then the function φ from S to ${\mathcal {I}}_{S}$ , given by

dom (aφ) = Sa⁻¹ and x(aφ) = xa

is a faithful representation of S.^[18]

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

$a\,\rho \,b,\quad c\,\rho \,d\Longrightarrow ac\,\rho \,bd.$ ^[19]

Of particular interest is the relation $\sigma$ , defined on an inverse semigroup S by

$a\,\sigma \,b\Longleftrightarrow$ there exists a $c\in S$ with $c\leq a,b.$ ^[20]

It can be shown that σ is a congruence and, in fact, it is a group congruence, meaning that the factor semigroup S/σ is a group. In the set of all group congruences on a semigroup S, the minimal element (for the partial order defined by inclusion of sets) need not be the smallest element. In the specific case in which S is an inverse semigroup σ 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.^[21] 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

$a\in S,e\in E(S),a\,\rho \,e\Longrightarrow a\in E(S).$ ^[22]

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 idempotents) is E-unitary if, for all e in E and all s in S,

$es\in E\Longrightarrow s\in E.$

Equivalently,

$se\in E\Rightarrow s\in E.$ ^[23]

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.^[24]

Theorem. Let S be an inverse semigroup with semilattice E of idempotents, and minimum group congruence σ. Then the following are equivalent:^[25]

S is E-unitary;
σ is idempotent pure;
$\sim$ = σ,

where $\sim$ is the compatibility relation on S, defined by

$a\sim b\Longleftrightarrow ab^{{-1}},a^{{-1}}b$ are idempotent.

McAlister's Covering Theorem. Every inverse semigroup S has a E-unitary cover; that is there exists an idempotent separating surjective homomorphism from some E-unitary semigroup T onto S.^[26]

Central to the study of E-unitary inverse semigroups is the following construction.^[27] Let ${\mathcal {X}}$ be a partially ordered set, with ordering ≤, and let ${\mathcal {Y}}$ be a subset of ${\mathcal {X}}$ with the properties that

${\mathcal {Y}}$ is a lower semilattice, that is, every pair of elements A, B in ${\mathcal {Y}}$ has a greatest lower bound A $\wedge$ B in ${\mathcal {Y}}$ (with respect to ≤);
${\mathcal {Y}}$ is an order ideal of ${\mathcal {X}}$ , that is, for A, B in ${\mathcal {X}}$ , if A is in ${\mathcal {Y}}$ and B ≤ A, then B is in ${\mathcal {Y}}$ .

Now let G be a group which acts on ${\mathcal {X}}$ (on the left), such that

for all g in G and all A, B in ${\mathcal {X}}$ , gA = gB if, and only if, A = B;
for each g in G and each B in ${\mathcal {X}}$ , there exists an A in ${\mathcal {X}}$ such that gA = B;
for all A, B in ${\mathcal {X}}$ , A ≤ B if, and only if, gA ≤ gB;
for all g, h in G and all A in ${\mathcal {X}}$ , g(hA) = (gh)A.

The triple $(G,{\mathcal {X}},{\mathcal {Y}})$ is also assumed to have the following properties:

for every X in ${\mathcal {X}}$ , there exists a g in G and an A in ${\mathcal {Y}}$ such that gA = X;
for all g in G, g ${\mathcal {Y}}$ and ${\mathcal {Y}}$ have nonempty intersection.

Such a triple $(G,{\mathcal {X}},{\mathcal {Y}})$ is called a McAlister triple. A McAlister triple is used to define the following:

$P(G,{\mathcal {X}},{\mathcal {Y}})=\{(A,g)\in {\mathcal {Y}}\times G:g^{{-1}}A\in {\mathcal {Y}}\}$

together with multiplication

$(A,g)(B,h)=(A\wedge gB,gh)$ .

Then $P(G,{\mathcal {X}},{\mathcal {Y}})$ is an inverse semigroup under this multiplication, with (A,g)⁻¹ = (g⁻¹A, g⁻¹). One of the main results in the study of E-unitary inverse semigroups is McAlister's P-Theorem:

McAlister's P-Theorem. Let $(G,{\mathcal {X}},{\mathcal {Y}})$ be a McAlister triple. Then $P(G,{\mathcal {X}},{\mathcal {Y}})$ is an E-unitary inverse semigroup. Conversely, every E-unitary inverse semigroup is isomorphic to one of this type.^[28]

F-inverse semigroups

An inverse semigroup is said to be F-inverse if every element has a unique maximal element above it in the natural partial order, i.e. ever σ-class has a maximal element. Every F-inverse semigroup is an E-unitary monoid. McAlister's covering theorem has been refined by M.V. Lawson to:

Theorem. Every inverse semigroup has an F-inverse cover.^[29]

McAlister's P-theorem has been used to characterize F-inverse semigroups as well. A McAlister triple $(G,{\mathcal {X}},{\mathcal {Y}})$ is an F-inverse semigroups if and only if ${\mathcal {Y}}$ is a principal ideal of ${\mathcal {X}}$ and ${\mathcal {X}}$ is a semilattice.

Free inverse semigroups

A construction similar to a free group is possible for inverse semigroups. A presentation of the free inverse semigroup on a set X may be obtained by considering the free semigroup with involution, where involution is the taking of the inverse, and then taking the quotient by the Vagner congruence

$\{(xx^{{-1}}x,x),\;(xx^{{-1}}yy^{{-1}},yy^{{-1}}xx^{{-1}})\;|\;x,y\in (X\cup X^{{-1}})^{+}\}.$

The word problem for free inverse semigroups is much more intricate than that of free groups. A celebrated result in this area due to W. D. Munn who showed that elements of the free inverse semigroup can be naturally regarded as trees, known as Munn trees. Multiplication in the free inverse semigroup has a correspondent on Munn trees, which essentially consists of overlapping common portions of the trees. (see Lawson 1998 for further details)

Any free inverse semigroup is F-inverse.^[30]

Connections with category theory

The above composition of partial transformations of a set gives rise to a symmetric inverse semigroup. There is 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.^[31] More precisely, an inverse semigroup is precisely a groupoid in the category of posets which is an étale groupoid with respect to its (dual) Alexandrov topology and whose poset of objects is a meet-semilattice.

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 idempotents 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:^[32]

Regular semigroups: 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 idempotents forms a subsemigroup.
Generalised inverse semigroups: a regular semigroup S is called a generalised inverse semigroup if its idempotents form a normal band, i.e., xyzx = xzyx, for all idempotents x, y, z.

The class of generalised inverse semigroups is the intersection of the class of locally inverse semigroups and the class of orthodox semigroups.^[33]

Amongst the non-regular generalisations of an inverse semigroup are:^[34]

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

Notes

↑ Lawson 1998.
↑ 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.
↑ First a short announcement in Wagner 1952, then a much more comprehensive exposition in Wagner 1953.
↑ Preston 1954a,b,c.
↑ See, for example, Golab 1939.
↑ Schein 2002 : 152.
↑ Howie 1995 : 149.
↑ Howie 1995 : Proposition 5.1.2(1).
↑ Howie 1995 : Theorem 5.1.1.
↑ Howie 1995 : Proposition 5.1.2(1).
↑ Wagner 1952.
↑ Howie 1995 : Proposition 5.2.1.
↑ Howie 1995 : 152–3
↑ Howie 1995 : 153.
↑ Lawson 1998 : Proposition 3.2.3.
↑ Clifford & Preston 1967 : Theorem 7.5
↑ Clifford & Preston 1967 : Theorem 7.36.
↑ Howie 1995 : Theorem 5.1.7. Originally, Wagner 1952 and, independently, Preston 1954c.
↑ Howie 1995 : 22
↑ Lawson 1998 : 62
↑ Lawson 1998 : Theorem 2.4.1.
↑ Lawson 1998 : 65
↑ Howie 1995 : 192.
↑ Lawson 1998 : Proposition 2.4.3.
↑ Lawson 1998 : Theorem 2.4.6.
↑ Grillet p. 248
↑ Howie 1995 : 193–4
↑ Howie 1995 : Theorem 5.9.2. Originally, McAlister 1974a,b.
↑ Lawson 1998 p. 230
↑ Lawson 1998, p.230
↑ Lawson 1998 : 4.1.8.
↑ Howie 1995 : Section 2.4 & Chapter 6.
↑ Howie 1995 : 222.
↑ Fountain 1979.

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.
J. B. Fountain (1979). "Adequate semigroups". Proceedings of the Edinburgh Mathematical Society 22 (02): 113–125. doi:10.1017/S0013091500016230.
St. Golab (1939). "Über den Begriff der "Pseudogruppe von Transformationen"". Mathematische Annalen 116: 768–780. doi:10.1007/BF01597390.
R. Exel (1998). "Partial actions of groups and actions of inverse semigroups". Proceedings of the American Mathematical Society 126 (12): 3481–3494. doi:10.1090/S0002-9939-98-04575-4.
V. Gould, "(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.
D. B. McAlister (1974a). "Groups, semilattices and inverse semigroups". Transactions of the American Mathematical Society (American Mathematical Society) 192: 227–244. doi:10.2307/1996831. JSTOR 1996831.
D. B. McAlister (1974b). "Groups, semilattices and inverse semigroups II". Transactions of the American Mathematical Society (American Mathematical Society) 196: 351–370. doi:10.2307/1997032. JSTOR 1997032.
M. Petrich, Inverse semigroups, Wiley, New York, 1984.
G. B. Preston (1954a). "Inverse semi-groups". Journal of the London Mathematical Society 29 (4): 396–403. doi:10.1112/jlms/s1-29.4.396.
G. B. Preston (1954b). "Inverse semi-groups with minimal right ideals". Journal of the London Mathematical Society 29 (4): 404–411. doi:10.1112/jlms/s1-29.4.404.
G. B. Preston (1954c). "Representations of inverse semi-groups". Journal of the London Mathematical Society 29 (4): 411–419. doi:10.1112/jlms/s1-29.4.411.
B. M. Schein (1981). "Obituary: Viktor Vladimirovich Vagner (1908–1981)". Semigroup Forum 28: 189–200. doi:10.1007/BF02676643.
B. M. Schein (2002). "Book Review: "Inverse Semigroups: The Theory of Partial Symmetries" by Mark V. Lawson". Semigroup Forum 65: 149–158. doi:10.1007/s002330010132.
V. V. Wagner (1952). "Generalised groups". Proceedings of the USSR Academy of Sciences 84: 1119–1122. (Russian) English translation:
V. V. Wagner (1953). "The theory of generalised heaps and generalised groups". Matematicheskii Sbornik. Novaya Seriya 32 (74): 545–632. (Russian)