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



Hyperarithmetic statements decidable by induction up to a recursive ordinal
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](https://mathoverflow.net/questions/70683/hyperarithemtic-statements-decidable-by-induction-up-to-a-recursive-ordinal/70754#70754), 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](http://en.wikipedia.org/wiki/Kleene%27s_O#Properties_of_Paths_in) 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](http://math.stanford.edu/~feferman/papers/conceptualprobs.pdf). 


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


