Finitely presented monoids

Suppose M is a monoid, and X is a finite subset of M. Let ⟨X⟩ denote the set of all elements that can be represented as a word on X. It is clear that this is a submonoid of M. If it is M itself then M is said to be finitely generated. Similarly, if G is a group then ⟨X⟩, the set of words on X ∪ X^-1 where X^-1 denotes the set {g^-1 : g ∈ X}, is a subgroup, and G is finitely generated as a group if ⟨X⟩=G. Clearly if G is finitely generated as a group it is also finitely generated as a monoid.

A congruence on a monoid M is an equivalence relation ~ on M with the property that x ~ y implies that xz ~ yz and zx ~ zy for all x,y,z ∈ M

If f: M → N is a monoid homomorphism then ~ = {{x,y} ∈ M*M : f(x) = f(y)} is a congruence.

If M is a monoid and ~ is a congruence on M then there is a quotient structure M/~ in which the elements are the equivalence classes of ~ and the multiplication is defined by [x][y]=[xy]. It is routine to show that this gives a monoid structure on M/~ and that the mapping M → M/~ defined by x → [x] is a monoid homomorphism.

If M is a monoid and R is a subset of M×M then there is a congruence ~, which contains R, and which is a subset of any other congruence on M containing R. This is called the congruence generated by R. Two elements x,y ∈ M are said to be directly equivalent under R if there exist elements a,b,u,v ∈ M such that x=aub and y=avb and either (u,v) ∈ R or (v,u) ∈ R. For two elements x,y ∈ M x ~ y if and only if there is a finite sequence of elements x = m₀,m₁,...m_r=y with m_i directly equivalent to m_i+1.

A monoid F is free on the subset X of F if for any monoid M and mapping f:X → M there is a unique monoid homomorphism f':F → M with f'(x) = f(x) for x ∈ X. For any set X the set X* is a free monoid when the operation is concatenation of words.

If X is a set, and R is a subset of X^*×X^* then Mon⟨X | R⟩ is defined to be the quotient monoid X^*/~ where ~ is the congruence on X^* generated by R. A monoid defined by such a presentation is said to be finitely presented if X and R are both finite, and a monoid isomorphic to such a monoid is finitely presentable. The members of R are usually given as a list of equations between words.

A group is just a special kind of monoid, and as one would hope, when a group presentation is converted into an equivalent monoid presentation, the resulting finitely presented monoid is isomorphic to the finitely presented group, even though finitely presented groups are usually defined as quotients of normal subgroups of free groups.