3
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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:

  1. $O \subseteq I \subseteq \omega$;
  2. If $d \in O$, then $S_d$ is consistent;
  3. If $c, d \in O$ and $c \leq_O d$, then $S_c \subseteq S_d$; and
  4. 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.)

$\endgroup$
1
  • $\begingroup$ Great. I put the reference in the article. $\endgroup$ Aug 23, 2011 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.