- Presentation of a monoid
In
algebra , a presentation of a monoid (or semigroup) is a description of amonoid (orsemigroup ) in terms of a set Σ of generators and a set of relations on thefree 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 agroup presentation ingroup theory The relations are given as a (finite)
binary relation "R" on Σ∗. To form the quotient monoid, these relations are extended tomonoid congruence s 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 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: where
is the
free monoid with involution on , and:
is a binary relation between words. We denote by (respectively ) the
equivalence relation (respectively, thecongruence ) generated by "T".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
:or:.
References
* 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 3110152487.
Wikimedia Foundation. 2010.