# Turing degrees of subsets of Kleene $\mathcal{O}$ which are ordinal notations of subsets of the set of recursive ordinals

An ordinal $$\alpha$$ is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type $$\alpha$$. The smallest ordinal that is not recursive is called Church–Kleene ordinal, $$\omega _{1}^{CK}$$. Kleene $$\mathcal{O}$$ (a subset of natural numbers) is an ordinal notation for the set of recursive ordinal $$\omega _{1}^{CK}$$. Kleene $$\mathcal{O}$$ is not recursive, not arithmetical and it has Turing degree $$\mathcal{O}$$ which is an hyperdegree.

Suppose $$\alpha$$ is a recursive ordinal, let define $$K(\alpha)$$ as the subset of Kleene $$\mathcal{O}$$ which is an ordinal notation restricted to any ordinal $$\beta <\alpha$$.

What is the smallest $$\alpha$$ for which $$K(\alpha)$$ is not recursive? Assuming such ordinal exist, what is the smallest $$\alpha(n)$$ for which the Turing degree of $$K(\alpha(n))$$ is $$0^n$$, and what about $$0^\omega$$. Is there an ordinal $$\gamma$$ for which the Turing degree of $$K(\gamma)$$ is $$0^\gamma$$?

I guess $$K(\alpha)$$ is recursive for all predicative ordinals, what about $$K(\Gamma_0)$$, $$K(\phi(1,0,0,0))$$, $$K(\psi (\Omega ^{{\Omega ^{\Omega }}}))$$, $$K(\psi_0 (\varepsilon_{\Omega+1}))$$, $$K(\Psi_0(\Omega_\omega))$$, $$K(\psi_0 (\varepsilon_{\Omega_\omega+1}))$$?

Finally always assuming that there is a recursive ordinal $$\alpha$$ for which $$K(\alpha)$$ is not recursive and $$K(\alpha)$$ has Turing degree $$0^n$$, is a there a different ordinal notation for $$\alpha$$ , let call it $$\hat K(\alpha)$$ which is not a subset of Kleene $$\mathcal{O}$$ and whose Turing degree is $$0^m$$, with $$0^m$$<$$0^n$$?

• I'm not sure I understand your definition of $K(\alpha)$. If you mean $K(\alpha)$ is the set of notations representing ordinals smaller than $\alpha$, then already $K(\omega+1)$ is non-recursive, and in fact has Turing degree $0''$. Indeed, determining if some notation denotes $\omega$ is equivalent to asking if some machine gives prescribed output for all natural number inputs, which is easily seen to be equivalent to the problem "does a given TM halt for all inputs", which is a prime example of a $0''$ problem. Similarly, $\omega n+1$ is the least for which $K(\alpha)$ has degree $0^{(2n)}$. – Wojowu May 10 at 10:49
• I know very little about ordinal notation, I hope to clarify an important point with your comment. You say $K(\omega+1)$ is not recursive. Why is this notation (which I think is recursive) of all ordinals up to $\omega$ (included) is not admissible : I map $n \in \mathbb{N}$ in $2*n$, and $\omega$ in $1$ and I state that in this notation any even number is less then any odd number. Isn't an ordinal notation just about providing codes which respect the order of the ordinal numbers? – holmes May 10 at 11:48
• @Wojowu I forgot to add this to my previous comment which I can not edit any longer – holmes May 10 at 12:10
• I posted a related question math.stackexchange.com/questions/3668199/… – holmes May 10 at 15:58
• @holmes You've just described one specific notation for $\omega+1$, but there are lots of others. If your $K(\alpha)$ is the set of all notations for ordinals $<\alpha$, then $K(\alpha)$ is not computable as soon as $\alpha\ge\omega$; on the other hand, if you want to focus on one specific set of notations then in general $K(\alpha)$ isn't well-defined (and some possible choices for $K(\alpha)$ will be computable while others won't be). – Noah Schweber May 10 at 20:45