• Images
• Videos
• Documents
• Books
• Articles

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−1 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−1. Finally, one takes the reflexive and transitive closure of E, which then is 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 } {\displaystyle R=\{u_{1}=v_{1},\ldots ,u_{n}=v_{n}\}} . Thus, for example,

⟨ p , q | p q = 1 ⟩ {\displaystyle \langle p,q\,\vert \;pq=1\rangle }

is the equational presentation for the bicyclic monoid, and

⟨ a , b | a b a = b a a , b b a = b a b ⟩ {\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }

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 {\displaystyle 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 ) {\displaystyle (X;T)}

where

( X ∪ X − 1 ) ∗ {\displaystyle (X\cup X^{-1})^{*}}

is the free monoid with involution on X {\displaystyle X} , and

T ⊆ ( X ∪ X − 1 ) ∗ × ( X ∪ X − 1 ) ∗ {\displaystyle T\subseteq (X\cup X^{-1})^{*}\times (X\cup X^{-1})^{*}}

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

We use this pair of objects to define an inverse monoid

I n v 1 ⟨ X | T ⟩ . {\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle .}

Let ρ X {\displaystyle \rho _{X}} be the Wagner congruence on X {\displaystyle X} , we define the inverse monoid

I n v 1 ⟨ X | T ⟩ {\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle }

presented by ( X ; T ) {\displaystyle (X;T)} as

I n v 1 ⟨ X | T ⟩ = ( X ∪ X − 1 ) ∗ / ( T ∪ ρ X ) c . {\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle =(X\cup X^{-1})^{*}/(T\cup \rho _{X})^{\mathrm {c} }.}

In the previous discussion, if we replace everywhere ( X ∪ X − 1 ) ∗ {\displaystyle ({X\cup X^{-1}})^{*}} with ( X ∪ X − 1 ) + {\displaystyle ({X\cup X^{-1}})^{+}} we obtain a presentation (for an inverse semigroup) ( X ; T ) {\displaystyle (X;T)} and an inverse semigroup I n v ⟨ X | T ⟩ {\displaystyle \mathrm {Inv} \langle X|T\rangle } presented by ( X ; T ) {\displaystyle (X;T)} .

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

F I M ( X ) = I n v 1 ⟨ X | ∅ ⟩ = ( X ∪ X − 1 ) ∗ / ρ X , {\displaystyle \mathrm {FIM} (X)=\mathrm {Inv} ^{1}\langle X|\varnothing \rangle =({X\cup X^{-1}})^{*}/\rho _{X},}

or

F I S ( X ) = I n v ⟨ X | ∅ ⟩ = ( X ∪ X − 1 ) + / ρ X . {\displaystyle \mathrm {FIS} (X)=\mathrm {Inv} \langle X|\varnothing \rangle =({X\cup X^{-1}})^{+}/\rho _{X}.}

Notes

• 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"

References

1. Book and Otto, Theorem 7.1.7, p. 149 ↩