Kleene's O is a $\Pi_1^1$ complete set that decides every hyperarithmetic statement. A Turing Machine that uses this set as an oracle to decide a hyperarithmetic question can only look at a finite segment of the oracle before making a decision. The possible questions are all of the form $n$ is or is not a notation for a recursive ordinal. Can every hyperarithmetic question be decided by a single notation for a sufficiently large recursive ordinal?
4

$\begingroup$ Paul, it appears that your question is a little vague. Ali Enayat and I interpreted it in two different ways. Perhaps you could clarify what you mean. $\endgroup$ – François G. Dorais♦ Jul 19 '11 at 17:29

$\begingroup$ I left a comment on François' answer to indicate my interpretation of your question, which might not coincide with your intended question, so please leave a comment on François' answer to clarify the situation. $\endgroup$ – Ali Enayat Jul 19 '11 at 17:34

$\begingroup$ My underlying question is: can every hyperarithmetic question be decided by induction up to some recursive ordinal? $\endgroup$ – Paul Budnik Jul 20 '11 at 15:58

$\begingroup$ @Paul Budnik: I still don't understand exactly what you're asking, so it might be helpful to state it more formally. Possibly the following fact is helpful: if $S$ is hyperarithmetic then there is an ordinal $\alpha<\omega_1^{CK}$ such that for each $n$ there is an ordering $\prec_n$ (uniformly computable from $n$) such that $n\in S$ iff $ot(\prec_n)<\alpha$. $\endgroup$ – Henry Towsner Jul 20 '11 at 22:05

$\begingroup$ ... but there is no ordinal which does that for all hyperarithmetic sentences. So we are confused as to the sequence of queries and replies here. I thought like François: you are given a hyperarithmetic set and a number, you pick a notation and ask the oracle, it tells you whether it is wellfounded, then you answer whether the number belongs to the set. $\endgroup$ – Daniel Mehkeri Jul 21 '11 at 0:39
1
$\begingroup$
$\endgroup$
Every $\Pi^1_1$ set is manyone reducible to Kleene's $\mathcal{O}$. In particular, the universal $\Pi^1_1$ set is manyone reducible to Kleene's $\mathcal{O}$. Therefore, every $\Pi^1_1$ sentence (and in particular hyperarithmetical sentences) can be decided by making a single query to Kleene's $\mathcal{O}$.

1$\begingroup$ I thought the question is asking whether there is a recursive ordinal $\alpha$ such that every hyperarithmetical question can be answered by a Turing machine that has access to an oracle that can tell whether a given notation describes $\alpha$ or not. $\endgroup$ – Ali Enayat Jul 19 '11 at 17:17

$\begingroup$ The wording of the question is a little vague. I see how you could read the question that way. I will ask the OP to clarify. $\endgroup$ – François G. Dorais♦ Jul 19 '11 at 17:28

1$\begingroup$ I forgot to add that under my interpretation the answer to the question is negative based on Kleene's theorem that describes hyperarithmetic sets as those constructed along branches of $\cal{O}$ using the jump operation. $\endgroup$ – Ali Enayat Jul 19 '11 at 17:49

$\begingroup$ Thanks for the answer. Neither it nor the comment is quite the question I intended, but the answer helps. The question I intended is can you get the same answer as the TM with oracle given only a sufficiently large ordinal notation? This means you are able to decide an arbitrarily large initial segment of the oracle given a sufficiently large ordinal notation. Your answer means you only need to decide one question given a sufficiently large ordinal notation. $\endgroup$ – Paul Budnik Jul 19 '11 at 17:56