Hyperarithmetic statements decidable by induction up to a recursive ordinal

2011-07-29T15:34:39Z

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

Answer by Daniel Mehkeri for Hyperarithmetic statements decidable by induction up to a recursive ordinal

2011-08-08T00:16:48Z

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.

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.

Suppose $A$ is a $\Pi^1_1$ set. As mentioned in the answer to the first question, 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}$

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

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.

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

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

I believe the answer to the question as stated is no, and even if we make just the alteration (1) above:

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

However Wikipedia implies 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}$.

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 all notations for greater recursive ordinals to also be able to decide the question, and this includes unnatural notations.

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!

The question of natural ordinal notations is the second of three conceptual questions that bug Solomon Feferman.

Maybe one could ask if there is some branch $\mathcal{B}$ such that, for all hyperarithmetic sets, the three conditions hold.

Hyperarithmetic statements decidable by induction up to a recursive ordinal - MathOverflow

Hyperarithmetic statements decidable by induction up to a recursive ordinal

Answer by Daniel Mehkeri for Hyperarithmetic statements decidable by induction up to a recursive ordinal