This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \subset x,\ \sigma \sigma \sigma \not \subset x$). Here $\subset$ denotes "substring" which should be distinguished from "initial segment" which I'll denote by $\sqsubset$ if the need arises.
So let $C \subset 2^{\omega}$ be the subset of Cantor space consisting of all cube-free sequences. It's uncountable, and easily seen to be closed, hence it contains a perfect set.
Question 1. Is $C$ perfect?
Let's define:
$T_C = \{ \sigma \in 2^{<\omega} : (\exists x \in C)(\sigma \sqsubset x)\}$
$\ \ \ \ \ = \{ \sigma \in 2^{<\omega} : (\forall n > |\sigma|)( \exists \tau \in 2^n )(\sigma \sqsubset \tau,\ \tau$ cube-free$)\}$
$T_P = \{\sigma \in 2^{<\omega} : (\forall \tau \sqsupset \sigma, \tau \in T_C)(\exists \rho_1, \rho_2 \sqsupset \tau$ both in $T_C)(\rho_1 \perp \rho_2)\}$
Question 2. $T_C$ is evidently $\Pi ^0 _1$, but is it in fact recursive?
If we let $P$ denote the maximal perfect subset of $C$ obtained by iteratively removing isolated points of $C$ until this procedure stabilizes (taking intersections at limit stages), then $P$ determines a tree which I believe would be the tree $T_P$ defined above.
Question 3. What is the complexity of the tree determined by $P$?
If $T_P$ is indeed the tree determined by $P$, then the tree determined by $P$ is at worst $\Pi ^0 _3$, but can we do better?
UPDATE: The answers are:
- Yes
- Yes
- Since $C$ is perfect, $P = C$ and so by the answers to 1 and 2, the tree determined by $P$ is just the tree determined by $C$, which is recursive.
I've learnt this after discussing it with Robert Shelton, one of the authors of the paper Gjergji linked to in his response below. In fact, what I've gathered is that there's a function $f$, better than being on the order of $n^2$, such that to determine whether an arbitrary finite string $\sigma$ has a cube-free infinite extension, it suffices to check whether it has one of length $f(|\sigma|)$ (where $|\sigma|$ is the length of $\sigma$). I suppose this would mean furthermore that the tree $T_C$ is not merely recursive, i.e. $\Delta_1$, but in fact $\Delta_0$.
