[FOM] Avoiding patterns/RCA/WKL
George McNulty
mcnulty at mailbox.sc.edu
Tue Nov 13 17:03:15 EST 2012
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
More information about the FOM
mailing list