9
$\begingroup$

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any desired computable ordinal. For every number $n\in O$, the $<_O$-predecessors of $n$ in $O$ are a computably enumerable set of natural numbers that is well-ordered by $<_O$, representing a computable ordinal, and every computable ordinal is represented in this way. Meanwhile, the set $O$ itself is not computable nor even hyperarithmetic, for it is $\Pi^1_1$-complete.

I am interested specifically in the complexity of cofinal branches through Kleene's $O$. Let us say that $z$ is a cofinal branch through $O$ if $z\subset O$, the members of $z$ are linearly ordered by $<_O$, and $z$ contains one index of every computable ordinal rank.

My intuition is that such branches must have high Turing degree, but I haven't been able to prove this. For example, because of the close connection between $O$ and computable ordinals, it would seem reasonable to suppose that every cofinal branch can compute WO, the set of Turing machine programs computing a well-ordered relation on $\mathbb{N}$.

Question 1. Does every cofinal branch through Kleene's $O$ compute a $\Pi^1_1$-complete set of natural numbers?

An affirmative answer would imply, in particular, that every cofinal branch $z$ could compute $O$ itself.

Failing this, perhaps every branch can at least compute the set TA of true arithmetic assertions.

Question 2. Does every cofinal branch through Kleene's $O$ compute true arithmetic?

In other words, if I have a cofinal branch $z$ through Kleene's $O$, and I use $z$ as an oracle, can I compute whether a given arithmetic sentence is true in the standard model?

This question arose recently in the seminar I am running with Wesley Wrigley, in connection with some of his work, which concerns the Feferman-Spector theorem, asserting that there are some cofinal branches through $O$ for which the theory that arises by iteratively adding consistency statements is not complete, even for $\Pi^0_1$ arithmetic truth. Notice that the issue of whether this theory is incomplete, however, is not the same as the question whether the path itself, when used as an oracle, can compute true arithmetic.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ An idea: fix a sequence $A=(\alpha_i)_{i\in\omega}$ cofinal in $\omega_1^{CK}$. Now consider the forcing notion $\mathbb{P}$ where conditions are finite sequences $(n_i)_{i<k}$ with $\vert n_i\vert_\mathcal{O}=\alpha_i$ and $n_j<_\mathcal{O}n_{i}$ for all $j<i<k$ (and conditions are ordered by extension as usual). How complicated are the correspondingly generic paths, that is, the $<_\mathcal{O}$-downwards closures of the set of notations occurring in the conditions in the generic filter? (And I think this is independent of choice of $A$.) $\endgroup$
    – Noah Schweber
    May 10, 2020 at 13:28
  • $\begingroup$ This forcing is isomorphic to the forcing to add a Cohen real. But the Turing degree of the branches will not generally be respected by the isomorphism. So I'm not sure how much we can get this way. $\endgroup$
    – Joel David Hamkins
    May 10, 2020 at 13:38
  • 1
    $\begingroup$ Yes, it's not enough to use the isomorphism type of the forcing. But there might still be something we can get from the fact that the set of notations of a given length extending a given notation isn't too complicated. $\endgroup$
    – Noah Schweber
    May 10, 2020 at 13:40
  • $\begingroup$ I see; you want to argue something like this: it is dense that a given TM program does not compute some instance of TA. $\endgroup$
    – Joel David Hamkins
    May 10, 2020 at 13:42
  • 5
    $\begingroup$ A small observation: $O$ is hyperarithmetic in any of its paths $z$. The point is that $n\in O$ iff there's an $<_O$-preserving embedding of the $<_O$-predecessors of $n$ into $z$. That makes $O$ $\Sigma^1_1$ in $z$, and since it's $\Pi^1_1$ even without $z$, it's hyperarithmetic in $z$. There might be some hope for estimating the relevant level of the $z$-hyperarithmetic hierarchy and so dragging this observation down to a level near what you asked about. $\endgroup$
    – Andreas Blass
    May 10, 2020 at 17:52

1 Answer 1

Reset to default
10
$\begingroup$

Goncharov, Harizanov, Knight and Shore investigated the Turing degrees of $\Pi^1_1$ cofinal branches (which they call "paths through $\mathcal{O}$"). They showed there is a $\Pi^1_1$ cofinal branch which does not compute $\emptyset'$, so certainly doesn't compute true arithmetic. On the other hand, H. Friedman showed there is a $\Pi^1_1$ cofinal branch which computes $\mathcal{O}$ (reference can be found in the GHKS paper).

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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