Welcome to MathOverflow

Question

4

1

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?

edited Jul 19 2011 at 16:39

François G. Dorais♦
23.1k●2●52●116

asked Jul 18 2011 at 22:40

Paul Budnik
159●5

	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. – François G. Dorais♦ Jul 19 2011 at 17:29
	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. – Ali Enayat Jul 19 2011 at 17:34
	My underlying question is: can every hyperarithmetic question be decided by induction up to some recursive ordinal? – Paul Budnik Jul 20 2011 at 15:58
	@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$. – Henry Towsner Jul 20 2011 at 22:05
	... 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. – Daniel Mehkeri Jul 21 2011 at 0:39

show 2 more comments

François G. Dorais · Accepted Answer · 2011-07-19 17:00:45Z UTC

1

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

answered Jul 19 2011 at 17:00

François G. Dorais♦
23.1k●2●52●116

1

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. – Ali Enayat Jul 19 2011 at 17:17

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. – François G. Dorais♦ Jul 19 2011 at 17:28

1

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. – Ali Enayat Jul 19 2011 at 17:49

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. – Paul Budnik Jul 19 2011 at 17:56

Hyperarithemtic statements decidable by induction up to a recursive ordinal

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.