Paths in Kleene's O and deciding $\Pi^0_1$ sentences

2011-08-22T16:29:35Z

This question comes from the Wikipedia article on Kleene's O and a previous Math Overflow question. The claim in Wikipedia that I have a question about is the second sentence in the following quote. "There exist $\aleph_0$ paths through $\mathcal{O}$ which are $\Pi^1_1$. Given a progression of recursively enumerable theories based on iterating Uniform Reflection, each such path is incomplete with respect to the set of true $\Pi^0_1$ sentences." I do not understand the informal proof in the second sentence I would appreciate a more complete explanation and/or a reference.

Answer by François G. Dorais for Paths in Kleene's O and deciding $\Pi^0_1$ sentences

2011-08-22T17:30:35Z

The basic reference for this is Feferman and Spector, Incompleteness Along Paths in Progressions of Theories [JSL 27 (1962), 383-390]. Theorem 2.5 states:

If $Z$ is a path through $O$ and $Z \in \Pi$ then $Tr_1 \nsubseteq \bigcup_{d \in Z} S_d$.

Here, $\Pi$ basically means $\Pi^1_1$ in modern notation, $Tr_1$ is the set of true $\Pi^0_1$ sentences, and $\{S_d : d \in I\}$ is any progression of theories such that:

$O \subseteq I \subseteq \omega$;
If $d \in O$, then $S_d$ is consistent;
If $c, d \in O$ and $c \leq_O d$, then $S_c \subseteq S_d$; and
the relation $Thm[\psi,d]$ which holds if and only if $d \in I$ and $\psi \in S_d$ is recursively enumerable.

Then, Theorem 3.7 states:

There exists a path $Z$ through $O$ with $Z \in \Pi$. In fact, for any $d \in O^\ast - O$, $Z = O \cap C'(d)$ is such a path.

Here, $O^\ast$ is an extension of $O$ with some nonstandard notations, and $C'(d)$ is the set of predecessor of such a notation. (Basically, $O^\ast$ has the same definition as $O$, but one quantifies only over the hyperarithmetic subsets of $\omega$ instead of all subsets of $\omega$. Thus, elements of $O^\ast$ describe pseudowellorderings: linear orders that have no hyperarithmetic descending sequences. By a well-known result of Kleene, it follows that $O^\ast$ is $\Sigma^1_1$ and therefore $O^\ast - O$ is nonempty.)

Paths in Kleene's O and deciding $\Pi^0_1$ sentences - MathOverflow

Paths in Kleene's O and deciding $\Pi^0_1$ sentences

Answer by François G. Dorais for Paths in Kleene's O and deciding $\Pi^0_1$ sentences