8

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.

Grzegorz Kossakowski
  • 191
  • 1
    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 '10 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 '10 at 11:50
  • 1
    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 http://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 '10 at 12:18
  • 3
    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. –  Dec 13 '10 at 13:48

1 Answers1

19

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.$$

  • 2
    I think this answer makes the question worth being open. – Autumn Kent Dec 13 '10 at 16:24
  • 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 '11 at 17:15
  • 1
    Yes, the set of words that are not subwords of the given infinite word is an ideal in the free monoid, and the monoid I described is the corresponding Rees quotient. –  Apr 11 '11 at 23:37