Presentation of a monoid

Construction

The relations are given as a (finite) binary relation R on Σ^∗. To form the quotient monoid, these relations are extended to monoid congruences as follows.

First, one takes the symmetric closure R ∪ R⁻¹ of R. This is then extended to a symmetric relation E ⊂ Σ^∗ × Σ^∗ by defining x ~_E y if and only if x = sut and y = svt for some strings u, v, s, t ∈ Σ^∗ with (u,v) ∈ R ∪ R⁻¹. Finally, one takes the reflexive and transitive closure of E, which is then a monoid congruence.

In the typical situation, the relation R is simply given as a set of equations, so that R = { u 1 = v 1 , ⋯ , u n = v n } . Thus, for example,

is the equational presentation for the bicyclic monoid, and

is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as a i b j ( b a ) k for integers i, j, k, as the relations show that ba commutes with both a and b.

Inverse monoids and semigroups

Presentations of inverse monoids and semigroups can be defined in a similar way using a pair

where

( X ∪ X − 1 ) ∗

is the free monoid with involution on X , and

is a binary relation between words. We denote by T e (respectively T c ) the equivalence relation (respectively, the congruence) generated by T.

We use this pair of objects to define an inverse monoid

Let ρ X be the Wagner congruence on X , we define the inverse monoid

presented by ( X ; T ) as

In the previous discussion, if we replace everywhere ( X ∪ X − 1 ) ∗ with ( X ∪ X − 1 ) + we obtain a presentation (for an inverse semigroup) ( X ; T ) and an inverse semigroup I n v ⟨ X | T ⟩ presented by ( X ; T ) .

A trivial but important example is the free inverse monoid (or free inverse semigroup) on X , that is usually denoted by F I M ( X ) (respectively F I S ( X ) ) and is defined by

or