Skip to main content
2 of 3
added 110 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Does every cofinal branch through Kleene's O compute true arithmetic?

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 indices 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, which asserts 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 that same as the question whether the path itself, when used as an oracle, can compute true arithmetic.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k