Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|cite|improve this question

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}$.

share|cite|improve this answer

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.