Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)

share|improve this question
This sounds like a tree version of Friedberg Muchnik. Does a corresponding web search yield anything? –  The Masked Avenger Feb 13 '14 at 5:26
I was confused by the question for two reasons. First, in my vocabulary a branch is finite but a path is 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? –  Andrej Bauer Feb 13 '14 at 11:46
Andrej, for me a branch through a tree is a maximal linear ordered subset, and I am only interested in infinite branches here. So a branch is in essence an infinite binary sequence. The question is whether there are computable trees $S$ and $T$, such that there is some infinite binary sequence $s$ that is branch through $S$, such that no infinite binary sequence that is Turing computable from $s$ is a branch through $T$, and a branch $t$ through $T$, such that no infinite sequence Turing computable from $t$ is a branch through $S$. –  Joel David Hamkins Feb 13 '14 at 12:31
In particular, $S$ and $T$ should have no computable infinite branches at all, so this is the sense in which the problem generalizes the classical result I mention at the beginning. –  Joel David Hamkins Feb 13 '14 at 12:32
I have edited the question to make that more clear. –  Joel David Hamkins Feb 13 '14 at 13:27

4 Answers 4

up vote 9 down vote accepted

An earlier reference for a stronger result: Jockusch and Soare gave an example of a pair of $\Pi^0_1$ classes such that any pair of elements consisting of one set from each class forms a minimal pair in the Turing degrees. Here is the bibliographic data from MathSciNet.

@article {MR0282834,
    AUTHOR = {Jockusch, Jr., Carl G. and Soare, Robert I.},
     TITLE = {A minimal pair of {$\Pi _{1}{}^{0}$} classes},
   JOURNAL = {J. Symbolic Logic},
  FJOURNAL = {The Journal of Symbolic Logic},
    VOLUME = {36},
      YEAR = {1971},
     PAGES = {66--78},
      ISSN = {0022-4812},
   MRCLASS = {02.70},
  MRNUMBER = {0282834 (44 \#68)},
MRREVIEWER = {R. L. Goodstein},
share|improve this answer
Great! Thank you very much. –  Joel David Hamkins Feb 15 '14 at 19:30

Yes, this is a question about mass problems. It is basically saying there are incomparable $\Pi^0_1$ sets of $2^\mathbb N$ under weak reducibility (a set P is weakly reducible to Q if every element of Q computables an element of P). In particular, there are incomprable sets under this reduciblity. See this paper (the abstract answers your question).


share|improve this answer
Thanks! MO is truly amazing. –  Joel David Hamkins Feb 13 '14 at 6:15
Is there a simple direct construction of my trees, along the lines of the classical argument I mention? –  Joel David Hamkins Feb 13 '14 at 13:28
@Joel David Hamkins: the paper by Binns has the construction written as a priority argument as Theorem 2.7 - personal.psu.edu/t20/papers/embed.ps –  Carl Mummert Feb 13 '14 at 14:02

Let $\mathcal P_w$ be the collection of Muchnik degrees of $\Pi^0_1$ classes. Stephen Binns in his PhD thesis (2003) showed that every finite distributive lattice embeds in $\mathcal P_w$. In particular (!) $\mathcal P_w$ has two incomparable elements, which is what you need.

On can do this also by following up on @The Masked Avenger's suggestion in a comment:

It is known that for each $\Pi^0_2$ class $P$ (in Cantor space) there is a $\Pi^0_1$ class $Q$ such that the Turing degrees of elements of $Q$ are the degrees of elements of $P$, together with some PA degrees (degrees of completions of Peano Arithmetic). If we start with two c.e. Turing incomparable sets $A$ and $B$, and let $P_A=\{A\}$ and $P_B=\{B\}$, then the corresponding $Q_A$ and $Q_B$ will provide a solution to your question (by the Arslanov completeness criterion.)

share|improve this answer
Thanks very much! –  Joel David Hamkins Feb 13 '14 at 6:16
Thanks very much for your further remarks. –  Joel David Hamkins Feb 13 '14 at 13:29
@Joel David Hamkins: the results of Binns can be extended in a relatively standard way to obtain an infinite sequence of $\Pi^0_1$ classes, whose indices are r.e., such that no join of paths through all but one of the classes computes a path through the remaining class. I used this to prove a little embedding result in this paper: m6c.org/publications/wkl-lind.pdf . See Theorem 3.1 for the precise statement. –  Carl Mummert Feb 13 '14 at 13:55

Here is another example.

Let $P_1$ be a nonempty $\Pi^0_1$-class which only contains Martin-Lof random reals, and $P_2$ be a nonempty $\Pi^0_1$-class in which no path is either of DNR degree or recursive. The existence of $P_2$ can be found in Rod and Denis's book (Thm 12.4.6, page 584).

Now it is obvious no real in $P_2$ computing a real in $P_1$. Let $x$ be a hif random real, then there must be some $y\in P_1$ Turing equivalent to $x$. However, any nonrecursive real Turing below $x$ must be DNR. So no real in $P_2$ can be computed by $y$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.