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?
$\begingroup$
$\endgroup$
7
-
$\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. DoraisJul 19, 2011 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 EnayatJul 19, 2011 at 17:34
-
$\begingroup$ My underlying question is: can every hyperarithmetic question be decided by induction up to some recursive ordinal? $\endgroup$– Paul BudnikJul 20, 2011 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 TowsnerJul 20, 2011 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 well-founded, then you answer whether the number belongs to the set. $\endgroup$– Daniel MehkeriJul 21, 2011 at 0:39
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
4
Every $\Pi^1_1$ set is many-one reducible to Kleene's $\mathcal{O}$. In particular, the universal $\Pi^1_1$ set is many-one 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$ Jul 19, 2011 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$ Jul 19, 2011 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$ Jul 19, 2011 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$ Jul 19, 2011 at 17:56