Presentation of a monoid
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 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 [math]\displaystyle{ R=\{u_1=v_1,\ldots,u_n=v_n\} }[/math]. Thus, for example,
- [math]\displaystyle{ \langle p,q\,\vert\; pq=1\rangle }[/math]
is the equational presentation for the bicyclic monoid, and
- [math]\displaystyle{ \langle a,b \,\vert\; aba=baa, bba=bab\rangle }[/math]
is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as [math]\displaystyle{ a^ib^j(ba)^k }[/math] 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
- [math]\displaystyle{ (X;T) }[/math]
where
[math]\displaystyle{ (X\cup X^{-1})^* }[/math]
is the free monoid with involution on [math]\displaystyle{ X }[/math], and
- [math]\displaystyle{ T\subseteq (X\cup X^{-1})^*\times (X\cup X^{-1})^* }[/math]
is a binary relation between words. We denote by [math]\displaystyle{ T^{\mathrm{e}} }[/math] (respectively [math]\displaystyle{ T^\mathrm{c} }[/math]) the equivalence relation (respectively, the congruence) generated by T.
We use this pair of objects to define an inverse monoid
- [math]\displaystyle{ \mathrm{Inv}^1 \langle X | T\rangle. }[/math]
Let [math]\displaystyle{ \rho_X }[/math] be the Wagner congruence on [math]\displaystyle{ X }[/math], we define the inverse monoid
- [math]\displaystyle{ \mathrm{Inv}^1 \langle X | T\rangle }[/math]
presented by [math]\displaystyle{ (X;T) }[/math] as
- [math]\displaystyle{ \mathrm{Inv}^1 \langle X | T\rangle=(X\cup X^{-1})^*/(T\cup\rho_X)^{\mathrm{c}}. }[/math]
In the previous discussion, if we replace everywhere [math]\displaystyle{ ({X\cup X^{-1}})^* }[/math] with [math]\displaystyle{ ({X\cup X^{-1}})^+ }[/math] we obtain a presentation (for an inverse semigroup) [math]\displaystyle{ (X;T) }[/math] and an inverse semigroup [math]\displaystyle{ \mathrm{Inv}\langle X | T\rangle }[/math] presented by [math]\displaystyle{ (X;T) }[/math].
A trivial but important example is the free inverse monoid (or free inverse semigroup) on [math]\displaystyle{ X }[/math], that is usually denoted by [math]\displaystyle{ \mathrm{FIM}(X) }[/math] (respectively [math]\displaystyle{ \mathrm{FIS}(X) }[/math]) and is defined by
- [math]\displaystyle{ \mathrm{FIM}(X)=\mathrm{Inv}^1 \langle X | \varnothing\rangle=({X\cup X^{-1}})^*/\rho_X, }[/math]
or
- [math]\displaystyle{ \mathrm{FIS}(X)=\mathrm{Inv} \langle X | \varnothing\rangle=({X\cup X^{-1}})^+/\rho_X. }[/math]
Notes
- ↑ Book and Otto, Theorem 7.1.7, p. 149
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:3-11-015248-7.
- Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993, ISBN:0-387-97965-4, chapter 7, "Algebraic Properties"
Original source: https://en.wikipedia.org/wiki/Presentation of a monoid.
Read more |