Are there two computable binary trees such that each has a branch not computing any branch through the other?

Question

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

Answer 1

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},
}   

Answer 2

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

https://sgslogic.net/t20/papers/massrand.pdf
Moved from: http://www.personal.psu.edu/t20/papers/massrand.pdf

Answer 3

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

Answer 4

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