Kleene's $O$ is an ordinal notation system that uses certain natural numbers to represent transfinite ordinals. It is a recursive notation system (although it's not decidable whether a number represents an ordinal whether two numbers represent the same ordinal), so naturally we can only represent recursive ordinals, i.e. order types of recursive well-orderings. The smallest ordinal we cannot represent in Kleene's $O$ is the Church-Kleene ordinal $\omega_1^{\mathrm{CK}}$, the smallest non-recursive ordinal, so it is the order type of the recursive ordinals, i.e. the order type of the ordinals that can be represented in Kleene's $O$. (This leads to the result that the set of natural numbers in Kleene's $O$ is not recursive, or even recursively enumerable.) Since $\omega_1^{\mathrm{CK}}$ is non-recursive, it follows that you can't have a recursive well-ordering in Kleene's $O$ that has order-type $\omega_1^{\mathrm{CK}}$.

Yet this Wikipedia article mentions a remarkable fact:

"Within the scheme of notations of Kleene some represent ordinals and some do not. One can define a recursive total ordering that is a subset of the Kleene notations and has an initial segment which is well-ordered with order-type $\omega_1^{\mathrm{CK}}$. Every recursively enumerable (or even hyperarithmetic) nonempty subset of this total ordering has a least element. So it resembles a well-ordering in some respects. For example, one can define the arithmetic operations on it. Yet it is not possible to effectively determine exactly where the initial well-ordered part ends and the part lacking a least element begins."

First of all, does anyone know the details of how this recursive subset is defined? I'm more interested in the last part: "it is not possible to effectively determine exactly where the initial well-ordered part ends and the part lacking a least element begins." I assume that if you partitioned a recursive totally ordered set $X$ into two parts $A$ and $B$, such that every element of $A$ is less than every element of $B$, then both $A$ and $B$ are recursive totally ordered sets. Am I wrong about that? If I'm right, then is the article saying that a partition of the recursive subset into the well-ordered part and the non-well-ordered part CAN be done recursively, but we can't tell recursively which partition is the one we want?

Any help would be greatly appreciated.

Thank You in Advance.


1 Answer 1


This is a bit too long to fully describe here. I can give you references.

Sacks's Higer Recursion Theory is a good source for learning about the ordinal notations and Kleene's $\mathcal{O}$.

I believe wikipedia above is describing the $\Pi_1^1$ set of unique notations in Kleene $\mathcal{O}$. This is constructed using the Harrison Ordering, which is a recursive linear ordering which is not a well-ordering but has no hyperarithmetic decreasing sequence. It also has an initial sequence of order type $\omega_1^\text{CK}$. In fact the order type of the Harrison Ordering is $\omega_1^{CK}(1 + \eta) + \gamma$ where $\eta$ is the order type of $\mathbb{Q}$ and $\gamma$ is some computable ordinal.

The relevant section to learn about the set of unique notations and the Harrison Ordering is page 55-58 in Sacks's Book. I believe the book is available online.

  • $\begingroup$ Indeed it is: Projet Euclid link. $\endgroup$
    – user642796
    Oct 8, 2013 at 2:31
  • $\begingroup$ @William Thanks for this. Does Sacks discuss my question about whether the well-ordered initial segment of the Harrison Ordering is a recursive set? Also, is anything known about what specific ordinal this mysterious $\gamma$ is? $\endgroup$ Oct 8, 2013 at 2:43
  • 1
    $\begingroup$ @KeshavSrinivasan The Harrison Linear ordering is recursive in the sense that it is isomorphic to a computable linear ordering of $\omega$. This does not mean that the Harrison Linear Ordering sitting inside of $\mathcal{O}$ is a computable subset of $\mathcal{O}$. Also the Harrison Ordering is constructed by using a arbitrary recursive linear ordering with no hyperarithmetic descreasing sequence. So the $\gamma$ will probably depend on which one you choose. $\endgroup$
    – William
    Oct 8, 2013 at 2:58
  • $\begingroup$ @William So is the Harrison Ordering NOT a computable subset of $O$? $\endgroup$ Oct 8, 2013 at 3:02
  • $\begingroup$ Wikipedia and Sacks does not say that the Harrison Ordering is computable as it sits inside of $\mathcal{O}$. However, the well-ordering ititial segment is definitely not recursive. If it was, then the initial is isomorphic to an computable ordinal. But we know the initial segment is $\omega_1^{CK}$ which is not computable. Although I suspect the Harrison Order is not recursive inside $\mathcal{O}$, even if it was, the initial segment is a limit ordinal so I do not see any way this would imply the initial segment is computable. $\endgroup$
    – William
    Oct 8, 2013 at 3:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .