Presentation of a monoid
||This article may be confusing or unclear to readers. (March 2011)|
||This article needs attention from an expert in Mathematics. (February 2009)|
In algebra, a presentation of a monoid (or semigroup) is a description of a monoid (or semigroup) in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ (or free semigroup Σ+) generated by Σ. The monoid is then presented as the quotient of the free monoid 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 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.
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 is then a monoid congruence.
In the typical situation, the relation R is simply given as a set of equations, so that . 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 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
is the free monoid with involution on , and
We use this pair of objects to define an inverse monoid
Let be the Wagner congruence on , we define the inverse monoid
presented by as
In the previous discussion, if we replace everywhere with we obtain a presentation (for an inverse semigroup) and an inverse semigroup presented by .
A trivial but important example is the free inverse monoid (or free inverse semigroup) on , that is usually denoted by (respectively ) and is defined by
- Book and Otto, Theorem 7.1.7, p. 149
- 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"