most recent 30 from http://mathoverflow.net 2013-05-25T00:51:13Z http://mathoverflow.net/feeds/question/49244 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49244/give-an-example-of-monoid-with-property-m2-m3 Grzegorz Kossakowski 2010-12-13T11:10:47Z 2011-04-11T17:18:44Z

<p>Give an example of finitely generated, infinite monoid $M$ with property that for all $m \in M$ we've got $m^2 = m^3$.</p> <p>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.</p> <p>I thought someone could propose more direct construction that would give better insight into methods of constructing such algebraic structures.</p> <p>In a case there's no better solution I'm planning to share my own with brief explanation of methods used in that construction.</p>

http://mathoverflow.net/questions/49244/give-an-example-of-monoid-with-property-m2-m3/49257#49257 Mark Sapir 2010-12-13T13:36:02Z 2011-04-11T17:18:44Z

<p>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 <a href="http://mathworld.wolfram.com/Thue-MorseSequence.html" rel="nofollow">sequence</a>, 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 </p> <p>$$x^2=x^3.$$ </p>