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$ 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 well-founded, then you answer whether the number belongs to the set. $\endgroup$ – Daniel Mehkeri Jul 21 '11 at 0:39

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.