Presentation of a monoid

In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set Template:Math of generators and a set of relations on the free monoid Template:Math (or the free semigroup Template:Math) generated by Template:Math. The monoid is then presented as the quotient of the free monoid (or the free semigroup) by these relations. This is an analogue of a group presentation in group theory.

As a mathematical structure, a monoid presentation is identical to a string rewriting system (also known as a semi-Thue system). Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).

A presentation should not be confused with a representation.

Construction

The relations are given as a (finite) binary relation Template:Mvar on Template:Math. To form the quotient monoid, these relations are extended to monoid congruences as follows:

First, one takes the symmetric closure Template:Math of Template:Mvar. This is then extended to a symmetric relation Template:Math by defining Template:Math if and only if Template:Mvar = Template:Mvar and Template:Mvar = Template:Mvar for some strings Template:Math with Template:Math. Finally, one takes the reflexive and transitive closure of Template:Mvar, which then is a monoid congruence.

In the typical situation, the relation Template:Mvar is simply given as a set of equations, so that $R=\{u_1=v_1,\dots ,u_n=v_n\}$. Thus, for example,

$⟨p,q|pq=1⟩$

is the equational presentation for the bicyclic monoid, and

$⟨a,b|aba=baa,bba=bab⟩$

is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as $a^i{b}^j(ba{)}^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

$(X;T)$

where

$(X\cup X^{-1}{)}^{*}$

is the free monoid with involution on $X$, and

$T\subseteq (X\cup X^{-1}{)}^{*}\times (X\cup X^{-1}{)}^{*}$

is a binary relation between words. We denote by $T^{\mathrm{e}}$ (respectively $T^{\mathrm{c}}$) the equivalence relation (respectively, the congruence) generated by T.

We use this pair of objects to define an inverse monoid

${\mathrm{I}\mathrm{n}\mathrm{v}}^1⟨X|T⟩.$

Let ${\rho }_X$ be the Wagner congruence on $X$, we define the inverse monoid

${\mathrm{I}\mathrm{n}\mathrm{v}}^1⟨X|T⟩$

presented by $(X;T)$ as

${\mathrm{I}\mathrm{n}\mathrm{v}}^1⟨X|T⟩=(X\cup X^{-1}{)}^{*}/(T\cup {\rho }_X{)}^{\mathrm{c}}.$

In the previous discussion, if we replace everywhere $(X\cup X^{-1}{)}^{*}$ with $(X\cup X^{-1}{)}^{+}$ we obtain a presentation (for an inverse semigroup) $(X;T)$ and an inverse semigroup $\mathrm{I}\mathrm{n}\mathrm{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 $\mathrm{F}\mathrm{I}\mathrm{M}(X)$ (respectively $\mathrm{F}\mathrm{I}\mathrm{S}(X)$) and is defined by

$\mathrm{F}\mathrm{I}\mathrm{M}(X)={\mathrm{I}\mathrm{n}\mathrm{v}}^1⟨X|\varnothing ⟩=(X\cup X^{-1}{)}^{*}/{\rho }_X,$

or

$\mathrm{F}\mathrm{I}\mathrm{S}(X)=\mathrm{I}\mathrm{n}\mathrm{v}⟨X|\varnothing ⟩=(X\cup X^{-1}{)}^{+}/{\rho }_X.$

References

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford Template:ISBN
• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, Template:ISBN.
• Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993, Template:ISBN, chapter 7, "Algebraic Properties"