8
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This sounds like a tree version of Friedberg Muchnik. Does a corresponding web search yield anything? $\endgroup$
    – The Masked Avenger
    Commented Feb 13, 2014 at 5:26
  • $\begingroup$ 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? $\endgroup$
    – Andrej Bauer
    Commented Feb 13, 2014 at 11:46
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Joel David Hamkins
    Commented Feb 13, 2014 at 12:31
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Feb 13, 2014 at 12:32
  • $\begingroup$ I have edited the question to make that more clear. $\endgroup$
    – Joel David Hamkins
    Commented Feb 13, 2014 at 13:27

4 Answers 4

Reset to default
9
$\begingroup$

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},
}
Improve this answer
$\endgroup$
0
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there a simple direct construction of my trees, along the lines of the classical argument I mention? $\endgroup$
    – Joel David Hamkins
    Commented Feb 13, 2014 at 13:28
  • 1
    $\begingroup$ @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 $\endgroup$
    – Carl Mummert
    Commented Feb 13, 2014 at 14:02
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ @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. $\endgroup$
    – Carl Mummert
    Commented Feb 13, 2014 at 13:55
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .