Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the largest known ordinal number $\alpha$ such that a uniform notation scheme has been developed for all ordinals up to $\alpha$ (there should be no "gaps" in what ordinals are representable), with an algorithm allowing to effectively compare any two ordinals written in that notation?

(I understand that every such scheme can in principle be extended by adding ad hoc symbol for $\alpha$ itself, but I am interested in notations that have been actually described.)

share|improve this question
2  
What is a uniform notation scheme? –  Qiaochu Yuan Nov 17 '11 at 23:08
    
I mean a finite set of rules which identify some symbolic expressions with all ordinals up to a certain point - similar to Cantor normal form for ordinals < \epsilon_0. –  Vladimir Reshetnikov Nov 17 '11 at 23:43
    
If I could answer this question and give you such an ordinal $\alpha$, wouldn't I have just written down a symbolic expression that describes $\alpha$? –  Qiaochu Yuan Nov 17 '11 at 23:47
    
I understand that in principle every notation can be extended in this way. My question is more about what notations have been actually described, with an algorithm allowing comparison of ordinals written in that notation. –  Vladimir Reshetnikov Nov 18 '11 at 0:01
    
@nikov: It seems that the only reasonable answer is "letters" let $\alpha,\beta$ be two ordinals. Either $\alpha\in\beta$, $\alpha=\beta$ or $\beta\in\alpha$. This is a nice algorithm. Also note that if you replace $\omega$ by something larger in the CNF then you just get to a "larger" epsilon-like number. –  Asaf Karagila Nov 18 '11 at 0:05

2 Answers 2

Ordinal arithmetics say that given an ordinal $\alpha>0$, and $\beta$ we can write $\beta$ uniquely as a polynomial in $\alpha$, that is: $$\beta=\sum_{i=1}^n \alpha^{\tau_i}\cdot\sigma_i$$ Where $\sigma_i<\alpha$, and $\tau_i<\tau_j$ for $j<i$ (we must have this since ordinal arithmetics are hardly commutative). When $\alpha=\omega$ this is called Cantor normal form. If you wish to consider this as the "proper" way to write up ordinals, which makes sense because then the coefficients $\sigma_i$ are finite numbers, you may want to consider $\epsilon_0$, which is a countable ordinal.

$\epsilon_0$ is the least ordinal $\alpha$ for which $\alpha=\omega^\alpha$. It can be defined as the limit of $\alpha_n$ where $\alpha_0=\omega$ and $\alpha_{n+1}=\omega^{\alpha_n}$.

Below this ordinal, you can write every ordinal in a Cantor normal form in a very nice way. Above $\epsilon_0$ you can still write every ordinal in a Cantor normal form, but you have "circular" forms because $\epsilon_0 = \omega^{\epsilon_0}$, and so it is its Cantor normal form.

Of course $\epsilon_0$ is not the only number with this property, there are uncountably many countable $\epsilon$-ordinals. In fact, one can even consider $\omega_1$ as $\epsilon_{\omega_1}$ since $\omega^{\omega_1}=\omega_1$. However it is often usual to talk about countable $\epsilon$-ordinals.

As for how big is this? Well, not very big. While this order type is nearly incomprehensible it is still only countable, thus very very small in terms of cardinality. This ordinal arises naturally in complexity proofs.

share|improve this answer
    
I think the original poster is looking for ordinals well beyond $\epsilon_{0}$, even well beyond $\Gamma_{0}$, and probably well beyond the Bachmann-Howard ordinal. I suggest he look at the many papers by Michael Rathjen, although I have to admit that the use of ordinal collapsing functions for large cardinals is well beyond anything I have personally tried to understand. –  Dave L. Renfro Nov 18 '11 at 16:14
    
@Dave: Possibly. His post was unclear at time of posting. Only after my answer did he answered the comments and mentioned $\epsilon_0$ in his comment. I am leaving it here because it may help the OP, and it does sort of answer the question - which is not phrased clearly and well enough, as it seems. –  Asaf Karagila Nov 18 '11 at 16:20
    
That helps with my confusion, since I figured you would be well aware that $\epsilon_{0}$ is just out of the starting gate for ordinal notations (even Veblen went way, way beyond this in his well-known 1908 paper). I had forgotten how the original statements of questions at this site can often change in the first hour or two of their appearance. –  Dave L. Renfro Nov 18 '11 at 16:42

It will depend on what you mean by a "notation scheme". In general, for any computable well-ordering $\prec$ of $\mathbb{N}$ you can view each number $n$ as a notation for a particular ordinal $|n|_\prec = \{ |m|_\prec : m \prec n\}$. For any computable well-ordering $\prec$ the set of such ordinals is countable and downward closed, and is thus itself a countable ordinal. In general any order type of a computable well-ordering of $\mathbb{N}$ is called a computable ordinal.

The supremum of the computable ordinals is known as $\omega_1^{CK}$ after Church and Kleene. This is a countable limit ordinal, and there is no computable well-ordering of $\mathbb{N}$ with this order type, but for any $\alpha < \omega_1^{CK}$ there is such a computable well-ordering of $\mathbb{N}$ of order type $\alpha$.

So I would say that the answer to your question, in generality, is $\omega_1^{CK}$ if by "system of ordinal notations" you simply mean "computable well ordering of $\mathbb{N}$". Depending on how the question is read, the answer might instead be "every ordinal up to $\omega_1^{CK}$ but not $\omega_1^{CK}$ itself".

share|improve this answer
    
"you can view each number n as a notation for a particular ordinal" - Is there an effective way to compare ordinals written in this notation? –  Vladimir Reshetnikov Nov 18 '11 at 0:22
    
Yes because the well ordering is computable. –  Carl Mummert Nov 18 '11 at 0:31
    
But how can you effectively determine that (1) a given computable function is a well-ordering function (2) two given computable functions represent the same ordinal? –  Vladimir Reshetnikov Nov 18 '11 at 0:36
    
You can effectively compare ordinals encoded using the same computable well-ordering. You cannot effectively compare two ordinals represented by codes of computable well-orderings, that would be tantamount to making $\omega_1^{CK}$ a computable ordinal, and it would also contradict Rice's theorem. –  Emil Jeřábek Apr 5 '12 at 10:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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