Paths in Kleene's O and deciding $\Pi^0_1$ sentences - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T13:40:37Z http://mathoverflow.net/feeds/question/73416 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73416/paths-in-kleenes-o-and-deciding-pi0-1-sentences Paths in Kleene's O and deciding $\Pi^0_1$ sentences Paul Budnik 2011-08-22T16:29:35Z 2011-08-22T17:39:29Z <p>This question comes from the <a href="http://en.wikipedia.org/wiki/Kleene%27s_O#Properties_of_Paths_in" rel="nofollow"> Wikipedia article on Kleene's O</a> and a <a href="http://mathoverflow.net/questions/71584/hyperarithmetic-statements-decidable-by-induction-up-to-a-recursive-ordinal" rel="nofollow">previous Math Overflow question</a>. 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.</p> http://mathoverflow.net/questions/73416/paths-in-kleenes-o-and-deciding-pi0-1-sentences/73421#73421 Answer by François G. Dorais for Paths in Kleene's O and deciding $\Pi^0_1$ sentences François G. Dorais 2011-08-22T17:30:35Z 2011-08-22T17:39:29Z <p>The basic reference for this is Feferman and Spector, <em>Incompleteness Along Paths in Progressions of Theories</em> [JSL 27 (1962), 383-390]. Theorem 2.5 states:</p> <blockquote> <p>If $Z$ is a path through $O$ and $Z \in \Pi$ then $Tr_1 \nsubseteq \bigcup_{d \in Z} S_d$.</p> </blockquote> <p>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:</p> <ol> <li>$O \subseteq I \subseteq \omega$;</li> <li>If $d \in O$, then $S_d$ is consistent;</li> <li>If $c, d \in O$ and $c \leq_O d$, then $S_c \subseteq S_d$; and</li> <li>the relation $Thm[\psi,d]$ which holds if and only if $d \in I$ and $\psi \in S_d$ is recursively enumerable.</li> </ol> <p>Then, Theorem 3.7 states:</p> <blockquote> <p>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.</p> </blockquote> <p>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 <em>pseudowellorderings</em>: 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.)</p>