# Hyperarithmetic statements decidable by induction up to a recursive ordinal

The first version of this question received a helpful answer but was too vague to fully convey what I intended. I hope this version remedies that problem. For any hyperarithmetic set of integers $S$, does there exist a single recursive process that can determine if $s\in S$ for all integers provided it also has access to a notation from Kleene's $\mathcal{O}$ for a sufficiently large (which can vary with $s$) recursive ordinal? More precisely, given any hyperarithmetic set of integers $S$, is there a recursive function $f(s,n)$ where $s$ is an integer and $n$ is an ordinal notation in Kleene's $\mathcal{O}$ and the following holds? (Note if $n\in\mathcal{O}$ then $n_o$ is the ordinal represented by $n$.)\ $$(\forall s\in\omega)(\forall n\in\mathcal{O}) \hspace{.045in}f(s,n)= \mbox{ 0 (false), 1 (true) or 2 (unknown)}$$ $$(\forall s\in\omega)(\forall n\in\mathcal{O}) \hspace{.045in}((s\in S\equiv f(s,n)) \vee f(s,n)=2)$$ $$(\forall s\in\omega)(\exists n\in\mathcal{O})\hspace{.045in}((s\in S\equiv f(s,n))\wedge (\forall m\in\mathcal{O})\hspace{.045in} (n_o\leq m_o \rightarrow (s\in S\equiv f(s,m))))$$

-
the first version: mathoverflow.net/questions/70683/… – Kaveh Jul 29 '11 at 18:56
There's a problem: Kleene's O in its full generality goes beyond any computable theory, because any such theory has a limit computable ordinal which is not provably well ordered. Your question sounds like a strong statement of Cohen's "article of faith" from "Set Theory and the Continuum Hypothesis" that any arithmetic question is resolved by a large enough axiom of infinity (if it is understood that any large axiom of infinity is equivalent to the well-foundedness of a recursive ordinal). So how can your statement be proven? Even replacing "hyperarithmetic" by "pi-0-1" (halting problem)? – Ron Maimon Jul 30 '11 at 18:23
@Ron: I don't see why that is an obstacle to Paul's question having an answer. We can prove things about Kleene's O even if we don't have a complete theory of it. In fact, if in the third condition, if $n_o \le m_o$ is replaced by $n \;\le_\mathcal{O}\; m$ then I do believe we can prove the answer is yes, and nothing in your objection seems to hinge on that detail. – Daniel Mehkeri Jul 31 '11 at 5:43

Well this has gone unanswered for a while, so I'll give a pseudo-answer. First I'll answer yes to a slightly different question, then I'll guess that the answer to the question as stated is no, then I'll make some random comments.

My proposed alterations are: (1) instead of a three-valued computable function, have a two-valued partial computable function ("unknown" becomes a non-terminating computation); (2) replace $n_{\mathcal{O}} \le m_{\mathcal{O}}$ with $n \;\le_\mathcal{O}\; m$. The relation $\le_\mathcal{O}$ is computably enumerable - or rather, there is a two-valued partial computable relation that agrees with $\le_\mathcal{O}$ over the elements of $\mathcal{O}$, and that is sufficient here.

Suppose $A$ is a $\Pi^1_1$ set. As mentioned in the answer to the first question, any membership question can be reduced to a single query to $\mathcal{O}$; there is a computable $g$ such that $(\forall s \in \mathbb{N}) s \in A \leftrightarrow g(s) \in \mathcal{O}$

Suppose $A$ is $\Delta^1_1$. Then not only is it $\Pi^1_1$, but so is $\mathbb{N} \setminus A$. So there is also a computable $h$ such that $(\forall s \in \mathbb{N}) s \not\in A \leftrightarrow h(s) \in \mathcal{O}$

So define $f$ as: $f(s,n) = true$ if $g(s) \;\le_\mathcal{O}\; n$, $f(s,n) = false$ if $h(s) \;\le_\mathcal{O}\; n$, undefined otherwise. This is a partial computable function.

This meets the second condition because if $f(s,n)=true$ and $n \in \mathcal{O}$ then $g(s) \in \mathcal{O}$ so $s \in A$, and similarly for $f(s,n)=false$. As to the third, if $s \in A$ then $g(s) \in \mathcal{O}$ and $f(s,n)=true$ for all $n \in \mathcal{O}$ such that $n \;\ge_\mathcal{O}\; g(s)$, and similarly if $s \not\in A$.

You didn't say anything about how $A$ is given, like asking for a single $f(A,s,n)$ that takes as input a particular type of code for $A$. So I just directly identified hyperarithmetic sets with $\Delta^1_1$.

I believe the answer to the question as stated is no, and even if we make just the alteration (1) above:

$\mathcal{O}$ gives an infinite number of different notations to each infinite recursive ordinal. Let's say we had a "branch" $\mathcal{B} \subset \mathcal{O}$, by which I mean that $\mathcal{B}$ contains exactly one notation for each recursive ordinal and is totally ordered by $\le_\mathcal{O}$. Now your if your three conditions held, they would still hold with $\mathcal{B}$ replacing $\mathcal{O}$: universal quantifiers just restrict to the subset, and as for the one existential quantifier in the third condition, it follows from the assumed property of $\mathcal{B}$ that some member of $\mathcal{B}$ would satisfy that condition, if $\mathcal{O}$ did.

However Wikipedia implies there does exist such a subset $\mathcal{B}$ which does not even decide all $\Pi^0_1$ sentences. If so, then your three conditions can't hold for that $\mathcal{B}$, so they can't hold for $\mathcal{O}$.

Now for some random comments. There are some very unnatural notations in $\mathcal{O}$. In my positive answer, we're allowed to cook up unnatural notations $g(s)$ and $h(s)$ which basically just encode the sentences $s \in A$ and $s \not\in A$. In my negative answer, we require all notations for greater recursive ordinals to also be able to decide the question, and this includes unnatural notations.

For an example of an unnatural notation: given some formal system $T$, for every $n$ it is decidable whether there is a contradiction in $T$ of size $\le n$. We can basically choose a notation so that $\alpha_n$ is the n'th finite ordinal if there isn't, and something ill-founded if there is. From the assumption that transfinite induction up to $\alpha$ is valid, we can prove $T$ consistent. Conversely from the assumption that $T$ is consistent, we can prove $\alpha$ is well-founded, and that actually its order type is $\omega$. So I could say, any consistent formal system is provably consistent by transfinite induction up to $\omega$ .. but that's a very misleading way to put it!

The question of natural ordinal notations is the second of three conceptual questions that bug Solomon Feferman.

Maybe one could ask if there is some branch $\mathcal{B}$ such that, for all hyperarithmetic sets, the three conditions hold.

-
Thanks for the answer. It covers the question thoroughly but I do have a questions about the Wikipedia entry you reference. I do not understand the informal argument in "There exist $\aleph_0$ paths through $\mathcal{O}$ which are $\Pi^1_1$. Given a progression of recursively enumerable theories based on iterating Uniform Reflection, each such path is incomplete with respect to the set of true $\Pi^0_1$ sentences." I would appreciate a reference or more complete proof? – Paul Budnik Aug 10 '11 at 16:14
Not sure where they got that, or if they stated the result right for that matter. (Hence "pseudo-answer".) Maybe someone more knowledgeable will speak up. – Daniel Mehkeri Aug 11 '11 at 9:28
This post is way late, but I believe I posted the "number of paths through O based on Uniform Reflection". I was referencing the Feferman-Spector paper: "Incompleteness Along Paths in Progressions of Theories. Journal of Symbolic Logic 27 (4):383-390" published in 1962. – Everett Piper Aug 23 '12 at 22:18