Hyperarithmetic statements decidable by induction up to a recursive ordinal - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:08:07Z http://mathoverflow.net/feeds/question/71584 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71584/hyperarithmetic-statements-decidable-by-induction-up-to-a-recursive-ordinal Hyperarithmetic statements decidable by induction up to a recursive ordinal Paul Budnik 2011-07-29T15:34:39Z 2011-08-08T00:16:48Z <p>The first version of this question received a helpful answer but was too vague to fully convey what I intended. I hope this version remedies that problem. For any hyperarithmetic set of integers $S$, does there exist a single recursive process that can determine if $s\in S$ for all integers provided it also has access to a notation from Kleene's $\mathcal{O}$ for a sufficiently large (which can vary with $s$) recursive ordinal? More precisely, given any hyperarithmetic set of integers $S$, is there a recursive function $f(s,n)$ where $s$ is an integer and $n$ is an ordinal notation in Kleene's $\mathcal{O}$ and the following holds? (Note if $n\in\mathcal{O}$ then $n_o$ is the ordinal represented by $n$.)\ $$(\forall s\in\omega)(\forall n\in\mathcal{O}) \hspace{.045in}f(s,n)= \mbox{ 0 (false), 1 (true) or 2 (unknown)}$$ $$(\forall s\in\omega)(\forall n\in\mathcal{O}) \hspace{.045in}((s\in S\equiv f(s,n)) \vee f(s,n)=2)$$ $$(\forall s\in\omega)(\exists n\in\mathcal{O})\hspace{.045in}((s\in S\equiv f(s,n))\wedge (\forall m\in\mathcal{O})\hspace{.045in} (n_o\leq m_o \rightarrow (s\in S\equiv f(s,m))))$$</p> http://mathoverflow.net/questions/71584/hyperarithmetic-statements-decidable-by-induction-up-to-a-recursive-ordinal/72322#72322 Answer by Daniel Mehkeri for Hyperarithmetic statements decidable by induction up to a recursive ordinal Daniel Mehkeri 2011-08-08T00:16:48Z 2011-08-08T00:16:48Z <p>Well this has gone unanswered for a while, so I'll give a pseudo-answer. First I'll answer yes to a slightly different question, then I'll guess that the answer to the question as stated is no, then I'll make some random comments.</p> <hr> <p>My proposed alterations are: (1) instead of a three-valued computable function, have a two-valued partial computable function ("unknown" becomes a non-terminating computation); (2) replace $n_{\mathcal{O}} \le m_{\mathcal{O}}$ with $n \;\le_\mathcal{O}\; m$. The relation $\le_\mathcal{O}$ is computably enumerable - or rather, there is a two-valued partial computable relation that agrees with $\le_\mathcal{O}$ over the elements of $\mathcal{O}$, and that is sufficient here.</p> <p>Suppose $A$ is a $\Pi^1_1$ set. As mentioned in the <a href="http://mathoverflow.net/questions/70683/hyperarithemtic-statements-decidable-by-induction-up-to-a-recursive-ordinal/70754#70754" rel="nofollow">answer to the first question</a>, any membership question can be reduced to a single query to $\mathcal{O}$; there is a computable $g$ such that $(\forall s \in \mathbb{N}) s \in A \leftrightarrow g(s) \in \mathcal{O}$</p> <p>Suppose $A$ is $\Delta^1_1$. Then not only is it $\Pi^1_1$, but so is $\mathbb{N} \setminus A$. So there is also a computable $h$ such that $(\forall s \in \mathbb{N}) s \not\in A \leftrightarrow h(s) \in \mathcal{O}$</p> <p>So define $f$ as: $f(s,n) = true$ if $g(s) \;\le_\mathcal{O}\; n$, $f(s,n) = false$ if $h(s) \;\le_\mathcal{O}\; n$, undefined otherwise. This is a partial computable function.</p> <p>This meets the second condition because if $f(s,n)=true$ and $n \in \mathcal{O}$ then $g(s) \in \mathcal{O}$ so $s \in A$, and similarly for $f(s,n)=false$. As to the third, if $s \in A$ then $g(s) \in \mathcal{O}$ and $f(s,n)=true$ for all $n \in \mathcal{O}$ such that $n \;\ge_\mathcal{O}\; g(s)$, and similarly if $s \not\in A$. </p> <p>You didn't say anything about how $A$ is given, like asking for a single $f(A,s,n)$ that takes as input a particular type of code for $A$. So I just directly identified hyperarithmetic sets with $\Delta^1_1$. </p> <hr> <p>I believe the answer to the question as stated is no, and even if we make just the alteration (1) above:</p> <p>$\mathcal{O}$ gives an infinite number of different notations to each infinite recursive ordinal. Let's say we had a "branch" $\mathcal{B} \subset \mathcal{O}$, by which I mean that $\mathcal{B}$ contains exactly one notation for each recursive ordinal and is totally ordered by $\le_\mathcal{O}$. Now your if your three conditions held, they would still hold with $\mathcal{B}$ replacing $\mathcal{O}$: universal quantifiers just restrict to the subset, and as for the one existential quantifier in the third condition, it follows from the assumed property of $\mathcal{B}$ that some member of $\mathcal{B}$ would satisfy that condition, if $\mathcal{O}$ did.</p> <p>However <a href="http://en.wikipedia.org/wiki/Kleene%27s_O#Properties_of_Paths_in" rel="nofollow">Wikipedia implies</a> there does exist such a subset $\mathcal{B}$ which does not even decide all $\Pi^0_1$ sentences. If so, then your three conditions can't hold for that $\mathcal{B}$, so they can't hold for $\mathcal{O}$.</p> <hr> <p>Now for some random comments. There are some very unnatural notations in $\mathcal{O}$. In my positive answer, we're allowed to cook up unnatural notations $g(s)$ and $h(s)$ which basically just encode the sentences $s \in A$ and $s \not\in A$. In my negative answer, we require <em>all</em> notations for greater recursive ordinals to also be able to decide the question, and this includes unnatural notations. </p> <p>For an example of an unnatural notation: given some formal system $T$, for every $n$ it is decidable whether there is a contradiction in $T$ of size $\le n$. We can basically choose a notation so that $\alpha_n$ is the n'th finite ordinal if there isn't, and something ill-founded if there is. From the assumption that transfinite induction up to $\alpha$ is valid, we can prove $T$ consistent. Conversely from the assumption that $T$ is consistent, we can prove $\alpha$ is well-founded, and that actually its order type is $\omega$. So I could say, any consistent formal system is provably consistent by transfinite induction up to $\omega$ .. but that's a very misleading way to put it!</p> <p>The question of natural ordinal notations is the second of <a href="http://math.stanford.edu/~feferman/papers/conceptualprobs.pdf" rel="nofollow">three conceptual questions that bug Solomon Feferman</a>. </p> <p>Maybe one could ask if there is some branch $\mathcal{B}$ such that, for all hyperarithmetic sets, the three conditions hold.</p>