MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
Great. I put the reference in the article. – Emil Jeřábek Aug 23 '11 at 10:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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