Skip to main content
2 of 2
two clarifications
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

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

François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233