I have been very interested in the countable ordinals for awhile now, but one thing has eluded me despite my research into the subject. What is a well-ordering of the natural numbers corresponding to $\epsilon_1$?

By $\epsilon_{1}$ I mean the second solution to the equation $\omega^a = a$. I have a basic understanding of the ordinals up to $\epsilon_0$, and I have a (unproven) basic method for constructing a well-ordering of the natural numbers corresponding to those ordinals. The ordinal $\epsilon_0$ is massively hard to comprehend but I have constructed an ordering on finite trees that has order type $\epsilon_0$, and after a long search found a way to convert finite trees to natural numbers. However, I have yet to find anything that gives a well-ordering of the natural numbers or trees or pumpkins or any countable set with order type $\epsilon_1$. Even a hint of an idea of the possibility of constructing an ordering on the natural numbers corresponding to $\epsilon_1$ would be helpful. Also, if someone knows a process for going even farther, that would also be appreciated.

  • $\begingroup$ If I recall correctly, and I might not, $\varepsilon_0$ is the least non-PR ordinal, and while $\varepsilon_1$ is still recursive, it is no longer primitive recursive. This means that describing it is going to be much harder, because we can't really imagine a whole lot outside the realm of primitive recursive (although we have explicit examples). $\endgroup$ – Asaf Karagila Dec 22 '13 at 16:05
  • $\begingroup$ I do not know what you mean by a "PR ordinal", but the proof theoretic ordinal of Primitive Recursive Arithmetic is w^w. That makes even epsilon null outside the realm of primitive recursive, yet I find the well-ordering of trees completely imaginable. This doesn't mean that the rest of your comment is invalid though. $\endgroup$ – weux082690 Oct 22 '14 at 14:41
  • $\begingroup$ I mean by "PR ordinal" an ordinal that is the order type of a relation on $\Bbb N$ which is primitive recursive. $\endgroup$ – Asaf Karagila Oct 22 '14 at 14:43
  • 1
    $\begingroup$ @AsafKaragila I don't think this characterization of $\epsilon_0$ is right. The ordering of type $\epsilon_1$ that I describe in my answer looks primitive recursive. In fact, I think all the recursive ordinals occur as order-types of primitive recursive wellorderings. More generally, you can vary the complexity of the well-orderings all the way from primitive recursive up to hyperarithmetical without changing the resulting order-types. $\endgroup$ – Andreas Blass Jul 2 '15 at 16:55

The ordinals below $\epsilon_1$ are those that can be written in Cantor normal form when a symbol for $\epsilon_0$ is allowed. More precisely, they are the values of the terms that can be built from the following symbols: $0$, $\omega$, $\epsilon_0$, $+$, and $\uparrow$ (where the last of these means ordinal exponentiation). So you can code each such ordinal by using the Gödel number (in some standard numbering scheme) of a term denoting that ordinal. (An ordinal may be denoted by several terms; take the smallest of the resulting Gödel numbers.) The standard ordering of the ordinal numbers corresponds to an ordering of these terms (and thus of their Gödel numbers) that is rather messy but not difficult to compute, using standard facts about ordinal arithmetic and Cantor normal forms.


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.