2
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Using $1$ for the identity (and guessing that's what $0$ is in your presentation), note that $ab = abaa = aa = 1$ and $ba = babb = bb = 1$. $\endgroup$
    – tmyklebu
    Feb 17, 2015 at 15:45
  • $\begingroup$ Is this also true for semigroups? As we are only dealing with sets that have an associative operation here, there is no need for inverses or identities. $\endgroup$
    – ENAFMTH
    Feb 17, 2015 at 15:45
  • $\begingroup$ abaa only equals babb because $a^{2}$ and $b^{2}$ are zeros in our semigroup.. definition of a zero in a semi group, $a$ is a zero if $ab=a=ba$ $\endgroup$
    – ENAFMTH
    Feb 17, 2015 at 15:47
  • $\begingroup$ We arent talking groups here just semigroups there need not be a 1, infact i dont think there is. $\endgroup$
    – ENAFMTH
    Feb 17, 2015 at 15:47
  • $\begingroup$ Ahh ok, no zero isnt the identity in this presentation, its a zero of a semigroup $\endgroup$
    – ENAFMTH
    Feb 17, 2015 at 15:48

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ There is an error in my list of rewrite rules; $0a \to 0$ and $0b \to 0$ and $a0 \to 0$ and $b0 \to 0$ also need to be there. But everything still works fine. $\endgroup$
    – tmyklebu
    Feb 17, 2015 at 21:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.