# Terminal Paths in Kleene's O

I'm stuck on a problem in Sack's Higher Recursion Theory (#2.4)- any hints are welcome. He defines Kleene's O in the usual way, and the corresponding order $<_O$. A path through O is a linearly ordered subset Z s.t. $w<_Ov\in Z\rightarrow w\in Z$. A path can be continued if there is a $w\in O$ s.t. $\forall z\in Z z<_O w$. The problem is find a path that can't be continued of order type $<\omega_1^{ck}$. I believe I can show that there is such a path using a counting argument, but I can't find one explicitly.

Thank you.

-

I will use $\Phi_e(n)$ for $\{e\}(n)$ used by Sack's in his book.

If $\delta$ is a constructive limit ordinal, then $\delta$ has infinitely many notations. This follows from the so called "Padding Lemma" which asserts that every computable function has infinitely many indices, i.e. for any $e$, there exists infinitely many $f$ such that $\Phi_e = \Phi_f$.

Convince yourself that $\omega \cdot n$ and $\omega \cdot \omega$ are constructive ordinals.

We will construct a sequence of notations $(a_i)_{i \in \omega}$ such that $a_i <_O a_{i + 1}$ and $|a_i| = \omega \cdot (i + 1)$. (The "+1" is just because $\omega$ starts with $0$.)

First if $3 \cdot 5^{0} \in O$ and $|3 \cdot 5^e| \geq \omega$, then since $\omega$ is a limit constructive ordinal it has infinitely many indices so in particular it has an notation $a_0$ such that $a_0$ is not $<_O$ comparable with $3\cdot 5^0$. (You may want to use Theorem 2.2 (iii) to justify this.) If $3 \cdot 5^0 \notin O$ or $|3 \cdot 5^0| < \omega$, then we don't care and just let $a_0$ be any notation of $\omega$.

Now suppose that $a_n$ has been defined with the desired properties. $|a_n| = \omega(n + 1)$. Suppose that $3 \cdot 5^{n + 1} \in O$ and $|3 \cdot 5^{n + 1}| \geq \omega(n + 2)$ and $a_i$ such that for all $i \leq n$, $3 \cdot 5^\omega \geq_O a_i$. Now choose notation $a_{n + 1}' = 3 \cdot 5^{f}$ (some $f \in \omega$) for $\omega(n + 2)$ such that $a_{n + 1}' = 3 \cdot 5^f$ is not $<_O$ comparable with $3 \cdot 5^{n + 1}$. By modifying the computable function $\Phi_f$ in finitely many places, one can get a $\Phi_{g}$ such that $\Phi_g(i) = a_i$ for all $i \leq n$, $\Phi_g$ agrees with $\Phi_f$ for all but finitely many values, $|3 \cdot 5^{g}| = \omega(n + 2)$, and $3 \cdot 5^{g}$ is $<_O$ incomparable with $3 \cdot 5^{n + 1}$. Define $a_{n + 1} = 3 \cdot 5^{g}$. (Note that $\Phi_f$ needed to be modified finitely to the $\Phi_g$ in order to ensure that $a_{n + 1}$ is comparable with the previous $a_i$'s.) If the above condition on $n + 1$ is not satisfied, just let $a_{n + 1}$ be any notation for $\omega(n + 2)$.

In this way, we have produced the desired sequence $(a_n)_{n \in \omega}$. Let $Z$ be the $\{u \in O : (\exists n)(u <_O a_n)\}$. It is clear that $Z$ is a path. (Use Theorem 2.2 iii if necessary.) By construction it is clear that $Z$ has order type $\omega \cdot \omega$ which is constructive and hence $\omega \cdot \omega < \omega_1^\text{CK}$.

It remain to show that $Z$ can not be continued. Clearly $Z$ does not have a largest element. Thus if $Z$ can be continued, there must exists an $e$ such that $\Phi_e(n) <_O \Phi_e(n + 1)$ and $z <_O 3 \cdot 5^{e}$ for all $z \in Z$. However this is impossible because $a_{e}$ is $<_0$ incomparable with $3 \cdot 5^e$ by construction. So $Z$ is your desired path that can not be continued.

Note that the main idea is to diagonalize against all computable function satisfy Sacks 2.1 (2), but you have to add in a little argument to make sure the order type does not reach $\omega_1^\text{CK}$ and that the sequence $a_i < a_{i + 1}$.

-