[FOM] Avoiding patterns/RCA/WKL

[George McNulty]

Perhaps the simplest proof of Axel Thue's result here is to produce a 
endomorphism  h on the free semigroup with 3 free generators that 
preserves square-freeness.  Thue provided one in 1912.  If  h  maps
the letter  a  to a word beginning with  a,   then simply iterating
a, h(a), h(h(a)), ...
produces initial segments of an infinite squarefree word on 3 letters.

The desired morphism  h  can be explicitly specified by declaring what
the images of the three letters are. The key fact that needs to be 
established is that  h  preserves squarefreeness if and only if the
images under  h  of squarefree words of length no more than  3  are all 
squarefree.  Once this is done, it is not hard to come up with 
particular squarefreeness preserving morphisms.

So I suppose the question is what does it take to prove the key fact 
mentioned above.

George McNulty


On 11/12/2012 03:08 PM, pax0 at seznam.cz wrote:
> It is well-known that there is an infinite word not containing a square (avoiding the pattern xx)
> over the three letter alphabet {0,1,2}.
> My question is: Do we need WKL over RCA for this result?
> The intuition is that there is a finitely branching tree of square-free prefixes in which we have to find an infinite branch.
> But is WKL really used here?
> Thank you, Jan Pax
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom