It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build such a tree $T$ as follows: fix a computably inseparable pair of c.e. sets $A$ and $B$, and allow a binary string $t$ into the tree when the pattern of yes/no answers is consistent with being a separation of $A$ and $B$ in as much as these sets are revealed by stage $|t|$. In this way, incorrect guesses about the separation are eventually killed off, stuck in a finite dead part of the tree, and there can be no computable infinite branch because the sets have no computable separation.)

What I have need of is a strengthening of that classical result to the following:

**Question.** Are there two computable trees $T,S\subset 2^{\lt\omega}$ such that $T$ has an infinite branch not computing any infinite branch through $S$ and $S$ has a branch not computing any branch through $T$?

That is, I want computable trees $S$ and $T$ such that there are infinite binary sequences $s$ and $t$, which are branches through $S$ and $T$, respectively, such that no infinite binary sequence that is Turing computable from $s$ is a branch through $T$ and no infinite binary sequence that is Turing computable from $t$ is a branch through $S$. (So in particular, neither $S$ nor $T$ can have any computable infinite branches.)

pathis infinite, so perhaps it would be better to say "infinite branch" (but this is a technicality). The other problem is that when you say that "$T$ has a branch computing through $T$" it sounds as if the branch is supposed to be computable. It would be better to say just "has an infinite branch $T$". So: are there Kleene trees $S$ and $T$ such that they do not share a common infinite branch? $\endgroup$ – Andrej Bauer Feb 13 '14 at 11:46