Is there a “solution” to the ordinal game

logicordinal-analysisordinalssoft-question

Even though I have almost no background in logic, I find the idea of ordinal notation quite interesting. It seems that the idea is to come up with notation to define larger and larger numbers, until your notation is exhausted, in which case you make up a new symbol to be the smallest number you can't define (the supremum). Then you keep repeating this process. So you go $1,2,…$ which gets exhausted so you just declare $\omega$. Then you get the tower $\omega^\omega, \omega^{\omega^\omega},…$ which gets exhausted and you declare $\epsilon_0$. Then from what I understand, you go through the Veblen hierarchy getting new numbers with the Veblen functions $\phi_\beta$ until it gets exhausted and you get the Feferman–Schütte ordinal $\Gamma_0$. And you keep going with the small Veblen ordinal, large Veblen ordinal, Bachmann-Howard ordinal, etc. I think going on like this, you never get beyond the Church–Kleene ordinal.

I think my question is basically whether there is a systematic way of naming all the ordinals up to the Church–Kleene ordinal. It seems the way this is going, we're eventually going to run out of people to name the ordinals after. Or is the point that no matter how powerful of a system you think you have, you can always define the least ordinal that can't be named by that system, in which case you can keep continuing? So there is no way to jump to "the end" of this process?

Best Answer

The answer (unsurprisingly) depends on what you mean by "systematic way." Although $\omega_1^{CK}$ has no computable description, and so no "computable notation system" will reach up all the way to $\omega_1^{CK}$ (this can be made precise and proved), there are other ways to describe ordinals. For example, any $\alpha<\omega_1^{CK}$ has a natural number $n_\alpha$ assigned to it, namely the least Kleene notation corresponding to it. This is a perfectly well-defined description of $\alpha$; does that count?

In fact, the map $n:\omega_1^{CK}\rightarrow\omega:\alpha\mapsto n_\alpha$ turns out to be "as simple as possible" in a precise sense, and via this simplicity plays an important role in metarecursion theory (= $\omega_1^{CK}$-recursion theory). So it's not flippant to point out that it is "not too complicatedly definable" - that's actually something that matters!

On the other hand, $\omega_1^{CK}$ isn't the real barrier: the problem is that given any reasonable descriptive framework, there will be countable ordinals not describable in that way, simply because there are uncountably many countable ordinals and only countably many descriptions. "The least ordinal not described by system $S$" is going to be a perfectly reasonable definition of an ordinal, whenever $S$ is a perfectly reasonable descriptive framework, but clearly can't be part of $S$ itself.

On the other other hand, the word "reasonable" is doing some serious work there. There is a precise sense in which it is possible that every countable ordinal (indeed, everything whatsoever) is first-order definable in the universe. The reason this doesn't immediately lead to an explosion is that "(unrestricted) definability (within the whole universe) isn't definable", and an analysis of this bizarre situation can be found here.

Related Question