Semi group presentation $<a, b | a^{2} = b^{2} = 0, aba = a, bab = b>$

Question

Another semi group question here, trying to get my head around the topic.

Consider the semi group $S=\left<a, b | a^{2} = b^{2} = 0, aba = a, bab = b\right>$

I need to prove that $S$ has order $5$.

The way I did it was to consider $a$ and $b$: we have to apply either $a$ or $b$ to these elements so $a.a=0$ and $a.b=ab$ $b.a=ba$ $b.b=0$ gives us three new elements for so far we have $\{a,b,ab,0,ba\}$. Now consider $ab$: we have to apply either $a$ or $b$ to this; applying $a$ we get $aba$ which is $b$ so not a new element; applying $b$ we get $abb=0$ so not a new element. Finally consider $ba$ (as we know applying $a$ or $b$ to $0$ gives $0$): applying $a$ to $ba$ we get $0$; applying $b$ to $a$ we get $ab$ which gives us no new elements.

Thus we have at most $5$ elements; are they all distinct though! I mean I can see they are but how do we know that say $ab \neq ba$ or whatever? How can I show that all these elements are distinct?

Cheers guys

Answer 1

The machinery of term-rewriting systems is useful here. A term-rewriting system is a bunch of rules of the form $foo \to bar$ where $foo$ and $bar$ are words. The rule $foo \to bar$ means that one can rewrite a word such as $qwefoorty$ to $qwebarrty$ by replacing an instance of $foo$ of our choosing in the word by $bar$ at the same position.

A word is called reduced with respect to a term-rewriting system if none of the rules of the term-rewriting system match any subword of the word. Reducing a word means applying rules of the term-rewriting system until you get a reduced word.

A term-rewriting system is called confluent if the order of application of rules does not matter---a TRS is confluent if every word corresponds via rewriting rules to a unique reduced word.

Suppose no infinite chain of reductions is possible for any word. Newman's lemma states that a term-rewriting system is confluent if and only if there is no word that can be reduced in a single step to two different words that cannot be reduced to the same word. (That is, if $a \to b$ or $a \to c$ in a single step, then there is a $d$ that both $b$ and $c$ can be reduced to.)

The critical pair lemma states that it's sufficient to check only the words that are overlaps of two left-hand sides of rules to prove "local confluence," which is the hypothesis of Newman's lemma.

In your example, you have the rewrite rules $aa \to 0$, $bb \to 0$, $aba \to a$, and $bab \to b$. (I made the longer side reduce to the shorter side so that there are trivially no infinite reduction chains.)

We need to check all overlaps of two rule left-hand sides. An overlap is a word of the form $uvw$ such that $v$ is nonempty and $uv$ and $vw$ are each left-hand sides of rules. The possible overlaps are $aaba$, $abaa$, $bbab$, and $babb$. Note that $aaba \to 0ba$ or $aaba \to aa$; both words can be reduced to $0$, so there is no failure with $aaba$.

The reasoning for the other three words proceeds similarly; it follows that this rewriting system is confluent. So two words are distinct if and only if they reduce to the same thing, which means we need only enumerate the reduced words. You already did that.

Answer 2

This is a presentation of the Brandt semigroup $B_2$, which can be described as the semigroup generated by the two following matrices $$ a = \begin{pmatrix} 0&1 \\ 0&0 \end{pmatrix}, \quad b = \begin{pmatrix} 0&0 \\ 1&0 \end{pmatrix}, $$ under the usual multiplication of matrices. Thus $B_2 = \{a, b, ab, ba, 0\}$ with $$ a = \begin{pmatrix} 0&1 \\ 0&0 \end{pmatrix}, \quad b = \begin{pmatrix} 0&0 \\ 1&0 \end{pmatrix}, \quad ab = \begin{pmatrix} 1&0 \\ 0&0 \end{pmatrix}, \quad ba = \begin{pmatrix} 0&0 \\ 0&1 \end{pmatrix}, \quad 0 = \begin{pmatrix} 0&0 \\ 0&0 \end{pmatrix} $$ The relations $a^2= 0$, $b^2 = 0$, $aba = a$ and $bab = b$ are trivially satisfied.