Continuous functions and 2-bushy trees

Question

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison.

A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ has two immediate successors. Is the following true: For every continuous function $f: 4^{\omega} \to 2^{\omega}$, there exists a $2$-bushy tree $T \subseteq 4^{< \omega}$ such that $f \upharpoonright [T]$ is either one-one or constant? Here $[T]$ is the set of branches through $T$.

I am tagging it set-theory + recursion-theory.

Answer 1

Yes.

Let me use the reduction to labelings suggested by Rohit. Let's call a two-bushy tree where $\sigma$ is the root a $2$-branchy tree.

For any continuous function $L$ from $4^{<\omega}$ to $\{0,1\}$, there is a either a three-branchy tree $T$ where $L$ restricted to $[T]$ is the constant function $0$ or a two-branchy tree $T$ where $L$ restricted to $[T]$ is the constant function $1$. This follows by backwards induction on the nodes, starting from nodes where $L$ is constant. If a node has all four children the base of one of these two types of trees, then either three have the first type of tree or two have the second, so it has one of the two types of threes.

As a corollary there is either a $2$-branchy tree $T$ such that $L$ restricted to $T$ is $0$, or a $2$-branchy tree $T$ such that $L$ restricted to $T$ is $1$. Without loss of generality, assume it is $0$. Then let $k$ be the maximum number such that there is a $2$-branchy tree $T$ where $f$ restricted to $[T]$ lands on functions that begin with $k$ zeros. By assumption $k\geq 1$.

If $k=\infty$ we win - there is a tree where $f$ is constant.

So assume $k$ is finite. Suppose there exists a $2$-branchy tree $T'$ such that $f$ restricted to $[T']$ lands on functions that do not begin with $k$ zeros. Then we win. Indeed the first $k$ values of $f(x_0x_1\dots)$ are determined by $x_0x_1\dots x_{N-1}$ for some $N$. Then choose a two-branchy tree of sequences $x_0x_1\dots$ such that if $x_i$ is the leftmost of the two options at $x_0\dots x_{i-1}$ then $x_{Ni}x_{N{i+1}} \dots x_{Ni+N-1}$ is in $T$, and if $x_i$ is the rightmost of the two options then $x_{Ni}x_{N{i+1}} \dots x_{Ni+N-1}$ is in $T'$ (and we might have to switch left and right for $x_0$). Then $f$ restricted to that tree is injective, as we can reconstruct $x_i$ by looking at the $Ni$ through $Ni+k-1$ digits of $f(x_0x_i\dots)$.

If there does not exist such a $2$-branchy tree, then there exists a $3$-branchy tree $T^*$ where $f$ restricted to $T^*$ always begins with $k$ zeroes. Then consider the tree of sequences $x$ that are in $T^*$ and that, after removing the first digit, remain in $T^*$. This is $2$-branchy tree, and $f$ applied to everything in it has $k+1$ zeroes. This contradicts our assumption on $k$.

So we win.