1. Semigroup Presentations

Recall the definitions of congruences, congruence closures, and presentations.

First, let us recall some basic algebraic definitions. A semigroup is a set which is closed under an associative binary operation, a monoid is a semigroup which contains an identity element, and a group is a monoid in which every element has a two-sided inverse.

A semigroup homomorphism is a map f between semigroups S and T such that for all r and s in S, f(rs)=f(r)f(s). A congruence is an equivalence relation on S such that for any two equivalence classes [r] and [s], if q is in [r] and t is in [s], then qt is in [rs]. That is, it is an equivalence relation that is compatible with the multiplication on S, so multiplication of equivalence classes is well-defined. Fundamentally, a partition of S into preimages of each element under a homomorphism defines a congruence (this generalizes the link between normal subgroups and homomorphisms in Group Theory).

Let

\(\mathcal{R}\subseteq S^2\)

be a relation. The equivalence closure of R is the smallest equivalence relation on S containing R and the congruence closure of R is the smallest congruence on S containing R.

A presentation for a semigroup (resp. monoid, group, etc.) is a pair consisting of a set of generators X and a relation on the free semigroup (resp. monoid, group, etc.) generated by X (which is written F with a subscript X). It is usually written

\(\langle X\text{ }|\text{ }\mathcal{R}\rangle.\)

The relation provided defines which words over X are equal to each other in the semigroup. Relations are often written using equalities rather than ordered pairs. Every presentation defines a semigroup S such that

\(S\cong F_X/\overline{\mathcal{R}}\)

where R with an overset bar is the congruence closure of R.

Let us consider an example. We define a monoid with the following presentation (since it is a monoid, we take the free monoid generated by X rather than the free semigroup, so there is no need to specify the existence of the identity or include relations for it):

\(\langle a \text{ }|\text{ } a^5=1 \rangle.\)

This presentation defines the cyclic group of integers modulo 5.

Providing a presentation is a common way to define a semigroup, and perhaps the only way for a large or even infinite one. However, presentations can be impractical to work with computationally. Consider the following presentation for the monoid M:

\(\langle a,b \text{ }|\text{ } (ab)^2a^2=aba,\text{ }b^2(ab)^2=a^2,\text{ }b^2a=a,\text{ }b^2ab=1,\text{ }a^2=a \rangle\)

Could you tell that this actually defines the trivial group? if so, it probably took you a second. If you need proof, observe that

\(b^2a=a\text{ and }b^2ab=1\text{ }\Rightarrow\text{ }ab=1\Rightarrow b=a^{-1}.\)

This means that a is contained in a subgroup of M with identity 1. Then, since a is idempotent, it must be the identity of M. Then b is also the identity, so the group is trivial.

Luckily, there are methods to make these computations easier. The focus of this series will be the Knuth-Bendix algorithm, which can extend a set of relations such that they can be used to rewrite any word into a unique normal form that represents the congruence class of that word defined by the presentation. However, this algorithm is not guaranteed to terminate, as when it does, it in effect solves the word problem, the undecidable problem of determining if two given words are equal under the presentation, for the semigroup it defines. In the subsequent posts in this series, I cover the basics of string rewriting systems before moving on to the Knuth-Bendix algorithm, for which I also provide a Python implementation.