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

  • $\begingroup$ 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)}$. $\endgroup$ – Wojowu May 10 at 10:49
  • $\begingroup$ 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? $\endgroup$ – holmes May 10 at 11:48
  • $\begingroup$ @Wojowu I forgot to add this to my previous comment which I can not edit any longer $\endgroup$ – holmes May 10 at 12:10
  • $\begingroup$ I posted a related question math.stackexchange.com/questions/3668199/… $\endgroup$ – holmes May 10 at 15:58
  • $\begingroup$ @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). $\endgroup$ – Noah Schweber May 10 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.