I am trying to construct an example of a infinite, finitely branching, recursive tree $T$ such that none of its paths has a graph which is $\Delta^0_2$. I denote the set of paths of $T$ by $[T]$. I have shown that if the tree $T$ is recursively bounded, then there is an $f\in [T]$ such that the graph of $f$ is $\Delta^0_2$. So my example needs to be finitely branching but not recursively bounded.

So far my attempt has been trying to mimic the the construction of a recursive binary tree such that no path is recursive. This construction proceeds by taking two disjoint recursively enumerable sets $A$ and $B$ so that there is no recursive set $C$ such that $A\subseteq C$ and $B\cap C=\emptyset$. Then one organizes the tree so that any path will be the characteristic for such a set $C$, whereby none of the paths is recursive.

Now we can certainly obtain two disjoint sets $A, B$ which are $\Sigma^0_2$ but cannot be separated by any $\Delta^0_2$ set by relativizing to $0'$. However, we cannot proceed to construct the tree in the exact same way as in the proceeding paragraph as then we would construct a binary tree, which is recursively bounded by the constantly $2$ function, and so would have a path whose graph is $\Delta^0_2$. So I need a more sophisticated construction, but I am not sure exactly how to go on. In fact, I am not even sure that proceeding in this direction is necessarily the best way to get my desired tree. Any indications on how to proceed with this problem would be greatly appreciated!

  • $\begingroup$ The benefit of non-recursively-bounded trees is that you can code things directly into the labels on the trees. I gave a hint for one possible answer below. $\endgroup$ – Carl Mummert Apr 5 '12 at 21:57

First, you can make a finitely branching computable subtree of $\omega^{<\omega}$ which has only one path, and that path computes $0'$. This path will be $\Delta^0_2$ but it's a start. The construction is like this. The tree will be a subtree of the complete binary tree, but with labeled nodes. At level $e$, the node has to be labeled with a pair of the form $(e,s+1)$, which is a promise that $\phi_{e,s}(e)\downarrow$, or with the pair $(e,0)$, which is a promise that $\phi_e(e)\uparrow$. Of course it can only be labeled $(e,s+1)$ if the promise is true - that keeps this a subtree of the complete binary tree.

We make a node of some length $t$ a dead end if we can tell using not more than $t$ steps that some predecessor node has broken its promise. A sequence of labels is put into the tree if and only if none of its initial subsequences is supposed to be a dead end; that criterion is effective so this is a computable tree. Moreover, because there are at most two labels at each level, and exactly one of them will keep its promise, the tree has only one path. The labels along that path immediately compute $0'$, and $0'$ computes a path through the tree.

Once you have that warm-up result, I believe you can extend it to make a tree whose only path computes $0' \oplus 0''$. Such a path computes $0''$ so it cannot be $\Delta^0_2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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