Presentation of a monoid

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

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

In the typical situation, the relation {{mvar|R}} is simply given as a set of equations, so that $R=\backslash \{u\_1=v\_1,\backslash ldots,u\_n=v\_n\backslash \}$. Thus, for example,

:$\backslash langle\; p,q\backslash ,\backslash vert\backslash ;\; pq=1\backslash rangle$

is the equational presentation for the bicyclic monoid, and

:$\backslash langle\; a,b\; \backslash ,\backslash vert\backslash ;\; aba=baa,\; bba=bab\backslash rangle$

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

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

:$(X;T)$

where

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

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

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

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

We use this pair of objects to define an inverse monoid

:$\backslash mathrm\{Inv\}^1\; \backslash langle\; X\; |\; T\backslash rangle.$

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

:$\backslash mathrm\{Inv\}^1\; \backslash langle\; X\; |\; T\backslash rangle$

presented by $(X;T)$ as

:$\backslash mathrm\{Inv\}^1\; \backslash langle\; X\; |\; T\backslash rangle=(X\backslash cup\; X^\{-1\})^*/(T\backslash cup\backslash rho\_X)^\{\backslash mathrm\{c\}\}.$

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

:$\backslash mathrm\{FIM\}(X)=\backslash mathrm\{Inv\}^1\; \backslash langle\; X\; |\; \backslash varnothing\backslash rangle=(\{X\backslash cup\; X^\{-1\}\})^*/\backslash rho\_X,$

or

:$\backslash mathrm\{FIS\}(X)=\backslash mathrm\{Inv\}\; \backslash langle\; X\; |\; \backslash varnothing\backslash rangle=(\{X\backslash cup\; X^\{-1\}\})^+/\backslash rho\_X.$

{{Reflist}}

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford {{ISBN|0-19-851194-9}}
• 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, {{ISBN|3-11-015248-7}}.
• Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993, {{ISBN|0-387-97965-4}}, chapter 7, "Algebraic Properties"

{{DEFAULTSORT:Presentation Of A Monoid}}

Category:Semigroup theory