MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Give an example of monoid with property $m^2 = m^3$

Give an example of finitely generated, infinite monoid $M$ with property that for all $m \in M$ we've got $m^2 = m^3$.

This question comes from the problem I was given during algebraic languages theory class at CS department. I've got construction that is using methods outlined during that class but the structure of the monoid is not very clear.

I thought someone could propose more direct construction that would give better insight into methods of constructing such algebraic structures.

In a case there's no better solution I'm planning to share my own with brief explanation of methods used in that construction.

-
Questions on MathOverflow are generally expected to have some motivation, showing where the problem came from and how it would help you with your research. – Andrew Stacey Dec 13 2010 at 11:37
Oh, sorry. I wasn't aware that I need to give some motivation. I'll edit my question. – Grzegorz Kossakowski Dec 13 2010 at 11:50
This question is likely to get closed (as I write, there are three votes outstanding) not because it is homework, but because it is of a level lower than that usually expected on this site. If it is closed, I recommend that you take it to math.stackexchange.com instead. I would also recommend that you give your construction and ask if there is an alternative description that would help you see better what is going on: that would be a more focussed question and easier to answer than the current question. – Andrew Stacey Dec 13 2010 at 12:18
It is not a homework, it grew up from a homework. But the OP needs to explain what is the construction they did in class (I suspect it is the same as in my answer), and what's unclear in this construction for him. There are many constructions of such monoids, Morse-Hadlund's is still the simplest one. – Mark Sapir Dec 13 2010 at 13:48

This is a classic result of Morse and Hedlund (they actually attribute it to Dilworth). Take the alphabet $\{a,b,c\}$ and an infinite word $W$ in that alphabet which does not contain subwords of the form $uu$ (such an infinite word was first constructed by Thue, search Google for Thue sequence, then by Morse-Hedlund, then by many others, all done independently). Now let $S$ be the set of all finite subwords of $W$ (including the empty word) and symbol $\{0\}$. The product of two words in $S$ is either their concatenation: $u\cdot v=uv$ if $uv\in S$ or 0 otherwise. That is a monoid satisfying the law $x^2=0$ (for all $x\ne 1$), hence
$$x^2=x^3.$$
Semigroups like this, obtained by collapsing an ideal (here $\{a,b,c\}^*-S$) to a new 0 symbol, are called Rees quotient semigroups. By the way, it is Hedlund, not Hadlund. – Ale De Luca Apr 11 2011 at 17:15