4
$\begingroup$

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?

$\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$ Jul 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 Enayat
    Jul 19, 2011 at 17:34
  • $\begingroup$ My underlying question is: can every hyperarithmetic question be decided by induction up to some recursive ordinal? $\endgroup$ Jul 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$ Jul 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$ Jul 21, 2011 at 0:39

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
4
  • 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, 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$
    – Ali Enayat
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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