After making another question about ordinal notation I want to clear some confusion I have about the topic. Let consider ordinals less than $\omega^2$ (or in $\omega^2$) , any of such ordinals can be written as $\omega *n +m$ with $n,m \in \mathbb{N}$.

I can map $\omega*n +m$ to the natural number $(p_n)^{m+1}$ (the $n$-th prime number power $m+1$), to create an ordinal notation over a set $S$ = {$ (p_n)^{m+1} \mid p_n \text{ $n$-th prime number}, \forall n,m \in \mathbb{N} $}$\subseteq \mathbb{N}$. Besides I can consider the lexicographic order relation over $(n, m+1)$ to induce an order in $S$ which is equivalent to the order of the ordinals in $\omega^2$.

$S$ is recursive, the map from $\omega^2$ to $S$ is recursive, the order relation is recursive, so I assume this ordinal notation is recursive, or is there something that I am missing here?

If I don't, additionally by using the hyperoperation or the Veblen function, I think you can build a recursive notation for all predicative ordinals (all the ordinals less than $\Gamma_0$), is this right?


This is correct - and to address your broader question, the computable ordinals (= those which are isomorphic to some computable well-ordering of $\mathbb{N}$) extend well past the ordinal $\Gamma_0$. Indeed, all proof-theoretic ordinals are computable, that's basically part of the definition. More broadly, all the usual proof-theoretic operations on ordinals send computable ordinals to computable ordinals.

The least noncomputable ordinal is denoted "$\omega_1^{CK}$" (the Church-Kleene analogue of $\omega_1$). This summary by Madore describes the a number of interesting ordinals, ranging from the computable to well past $\omega_1^{CK}$, and I suspect will be of interest to you. It's worth noting that the noncomputable countable ordinals are rather technical objects, and you're unlikely to run into them outside of computability theory (to put it mildly!); even within computability theory, they don't show up in most areas.

A couple technical comments:

  • Note that "computable ordinal" is an extremely robust notion: the computable ordinals, the polynomial-time computable ordinals, and the hyperarithmetic ordinals coincide. Spector proved the hyperarithmetic part, and the polynomial-time part is I believe folklore. Spector's result helps establish that $\omega_1^{CK}$ really is gigantic.

  • By $\Sigma^1_1$-bounding, if $T$ is a "reasonable" theory then there is some computable ordinal $\alpha$ such that there is no formula $\varphi$ which $T$ proves defines a well-ordering of $\mathbb{N}$ and such that in reality $\varphi$ defines a well-ordering of $\mathbb{N}$ of ordertype $\alpha$. This gives us one way to define the proof-theoretic ordinal of a theory precisely: basically, the smallest ordinal with no presentation which $T$ proves is well-founded.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.