Presentation of a monoid explained

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 of generators and a set of relations on the free monoid (or the free semigroup) generated by . 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).^[1]

A presentation should not be confused with a representation.

Construction

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

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

In the typical situation, the relation is simply given as a set of equations, so that

R = \{u _{1=v} _{1,\ldots,u} _{n=v} _{n\}} . Thus, for example,\langle p,q\vert pq =1 \rangle is the equational presentation for the bicyclic monoid, and\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 ^{ib} ^{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 , andT\subseteq (X\cup X ^{-1} ) ^{* x} (X\cup X ^{-1} ) ^{*}

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

Inv ^{1} \langle X | T\rangle.

Let

\rho _{X} be the Wagner congruence on X , we define the inverse monoidInv ^{1} \langle X | T\rangle

presented by

(X;T) asInv ^{1} \langle X | T\rangle = (X\cup X ^{-1} ) ^{c} _{X)} .

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 Inv \langle X | T\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 FIM (X) (respectively FIS (X) ) and is defined byFIM (X) = Inv ^{1} \langle X | \varnothing\rangle = ({X\cup X ^{-1} })^*/\rho_X,orFIS (X) = Inv \langle X | \varnothing\rangle = ({X\cup X ^{-1} })^+/\rho_X.

References

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford
• 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, .
• Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993,, chapter 7, "Algebraic Properties"

Notes and References

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