8
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 13, 2010 at 11:37
  • $\begingroup$ Oh, sorry. I wasn't aware that I need to give some motivation. I'll edit my question. $\endgroup$ Dec 13, 2010 at 11:50
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 13, 2010 at 12:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – user6976
    Dec 13, 2010 at 13:48

1 Answer 1

19
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ I think this answer makes the question worth being open. $\endgroup$ Dec 13, 2010 at 16:24
  • $\begingroup$ 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. $\endgroup$ Apr 11, 2011 at 17:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – user6976
    Apr 11, 2011 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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