In group theory, an inverse semigroup (occasionally called an inversion semigroup[1]) S is a semigroup in which every element x in S has a unique inverse y in S in the sense that and, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.
(The convention followed in this article will be that of writing a function on the right of its argument, e.g. x f rather than f(x), and composing functions from left to right—a convention often observed in semigroup theory.)
Inverse semigroups were introduced independently by Viktor Vladimirovich Wagner[2] in the Soviet Union in 1952,[3] and by Gordon Preston in the United Kingdom in 1954.[4] Both authors arrived at inverse semigroups via the study of partial bijections 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:
\operatorname{dom}\alpha\beta=[\operatorname{im}\alpha\cap\operatorname{dom}\beta]\alpha-1
l{I}X
The inverse of an element x of an inverse semigroup S is usually written x-1. Inverses in an inverse semigroup have many of the same properties as inverses in a group, for example, . In an inverse monoid, xx-1 and x-1x are not necessarily equal to the identity, but they are both idempotent. An inverse monoid S in which, 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:
l{L}
l{R}
l{L}
l{R}
l{L}
l{R}
al{L}b\Longleftrightarrowa-1a=b-1b, al{R}b\Longleftrightarrow aa-1=bb-1
Unless stated otherwise, E(S) will denote the semilattice of idempotents of an inverse semigroup S.
Multiplication table example. It is associative and every element has its own inverse according to, . It has no identity and is not commutative.
| a | b | c | d | e | |
|---|---|---|---|---|---|
| a | a | a | a | a | a |
| b | a | b | c | a | a |
| c | a | a | a | b | c |
| d | a | d | e | a | a |
| e | a | a | a | d | e |
An inverse semigroup S possesses a natural partial order relation ≤ (sometimes denoted by ω), which is defined by the following:
a\leqb\Longleftrightarrowa=eb,
a\leqb\Longleftrightarrowa=bf,
The natural partial order is compatible with both multiplication and inversion, that is,
a\leqb,c\leqd\Longrightarrowac\leqbd
a\leqb\Longrightarrowa-1\leqb-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, for all x in the domain of α.
The natural partial order on an inverse semigroup interacts with Green's relations as follows: if and s
l{L}
On E(S), the natural partial order becomes:
e\leqf\Longleftrightarrowe=ef,
If E(S) is finite and forms a chain (i.e., E(S) is totally ordered by ≤), then S is a union of groups. If E(S) is an infinite chain it is possible to obtain an analogous result under additional hypotheses on S and E(S).[6]
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, for all s,t in S. The definition of a morphism of inverse semigroups could be augmented by including the condition, 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.
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
l{I}S
dom (aφ) = Sa-1 and x(aφ) = xais a faithful representation of S.[7]
Thus, any inverse semigroup can be embedded in a symmetric inverse semigroup, and with image closed under the inverse operation on partial bijections. Conversely, any subsemigroup of the symmetric inverse semigroup closed under the inverse operation is an inverse semigroup. Hence a semigroup S is isomorphic to a subsemigroup of the symmetric inverse semigroup closed under inverses if and only if S is an inverse semigroup.
Congruences are defined on inverse semigroups in exactly the same way as for any other semigroup: a congruence ρ is an equivalence relation that is compatible with semigroup multiplication, i.e.,
a\rhob, c\rhod\Longrightarrowac\rhobd.
Of particular interest is the relation
\sigma
a\sigmab\Longleftrightarrow
c\inS
c\leqa,b.
A congruence ρ on an inverse semigroup S is called idempotent pure if
a\inS,e\inE(S),a\rhoe\Longrightarrowa\inE(S).
One class of inverse semigroups that 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\inE\Longrightarrows\inE.
se\inE ⇒ s\inE.
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.
Theorem. Let S be an inverse semigroup with semilattice E of idempotents, and minimum group congruence σ. Then the following are equivalent:
\sim
\sim
a\simb\Longleftrightarrowab-1,a-1b
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.[8]
Central to the study of E-unitary inverse semigroups is the following construction. Let
l{X}
l{Y}
l{X}
l{Y}
l{Y}
\wedge
l{Y}
l{Y}
l{X}
l{X}
l{Y}
l{Y}
Now let G be a group that acts on
l{X}
l{X}
l{X}
l{X}
l{X}
l{X}
The triple
(G,l{X},l{Y})
l{X}
l{Y}
l{Y}
l{Y}
Such a triple
(G,l{X},l{Y})
P(G,l{X},l{Y})=\{(A,g)\inl{Y} x G:g-1A\inl{Y}\}
(A,g)(B,h)=(A\wedgegB,gh)
P(G,l{X},l{Y})
McAlister's P-Theorem. Let
(G,l{X},l{Y})
P(G,l{X},l{Y})
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. every σ-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.
McAlister's P-theorem has been used to characterize F-inverse semigroups as well. A McAlister triple
(G,l{X},l{Y})
l{Y}
l{X}
l{X}
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-1x,x), (xx-1yy-1,yy-1xx-1) | x,y\in(X\cupX-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.
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. More precisely, an inverse semigroup is precisely a groupoid in the category of posets that is an étale groupoid with respect to its (dual) Alexandrov topology and whose poset of objects is a meet-semilattice.
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:
The class of generalised inverse semigroups is the intersection of the class of locally inverse semigroups and the class of orthodox semigroups.
Amongst the non-regular generalisations of an inverse semigroup are:[10]
This notion of inverse also readily generalizes to categories. An inverse category is simply a category in which every morphism has a generalized inverse such that and . An inverse category is selfdual. The category of sets and partial bijections is the prime example.[11]
Inverse categories have found various applications in theoretical computer science.[12]