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

127 Views Asked by At

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$?