Is there a “solution” to the ordinal game?

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?

Answer 1

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.

Answer 2

"Is there any sense in which even though any given notation system can't reach $ω_{CK}$, there is a hierarchy of notation systems so that when you take the "union", you do get there?"

In a certain precise sense, the answer to this is in negative (in a somewhat trivial sense). But it is a standard fact nevertheless.

For example, suppose we have a computable function whose output we interpret as the index of programs coding well-orders of $\mathbb{N}$. So, for example, suppose some number $x\in \mathbb{N}$ represents the index of a program (from $\mathbb{N}^2$ to $\{0,1\}$) describing a well-order (of $\mathbb{N}$) with order-type $\alpha \in \omega_{CK}$. Then say we write $[x]=\alpha$ to denote this fact. If $x$ doesn't describe a well-order then suppose we write $[x]=\omega_{CK}$. (I just arbitrarily dug-up this $[x]$ terminology, it isn't standard or anything)

Now we have a more precise version of the above statement. We say that for every computable function $f:\mathbb{N} \rightarrow \mathbb{N}$ if the following condition is true:

for all $x\in \mathbb{N}$, we have $[f(x)]<\omega_{CK}$

Then we must have:

$\mathrm{sup}\,\{\,[f(x)]\,:\,x \in \mathbb{N}\}<\omega_{CK}$

The proof of this is quite easy of course.

---

A certain version of this should also hold for $\mathcal{O}$ I believe (I am not really familiar with it in a good enough manner though). In the sense that for every computable function $f:\mathbb{N} \rightarrow \mathbb{N}$ if the following condition is satisfied:

for all $x\in \mathbb{N}$, we have $f(x) \in \mathcal{O}$ and $|f(x+1)|_{\mathcal{O}}>|f(x)|_{\mathcal{O}}$

Then we must have: $\mathrm{sup}\,\{\,|f(x)|_{\mathcal{O}}\,:\,x \in \mathbb{N}\}<\omega_{CK}$

This really directly follows from the very definition of $\mathcal{O}$, alongside the result(s) (I really need to study these at some point) which describe the fact that the set of ordinals described by $\mathcal{O}$ are precisely the ones below $\omega_{CK}$.

I don't know whether the condition $|f(x+1)|_{\mathcal{O}}>|f(x)|_{\mathcal{O}}$ can be dropped or not (I suppose I am quite dumb for not knowing this).

---

There is a slightly alternative way to look at your question. Every normal function $f:\omega_1 \rightarrow \omega_1$ has $\omega_1$ many fixed points. In standard set theory, surely true under choice (not commenting about the case I am not fully sure about). In particular we can suppose that we have a (total) function $F:\omega_1 \rightarrow \omega_1$ enumerating fixed points of $f$.

Now, as usual, I believe we can just switch over to an explicit version of $F$ in the sense that: $(1)$ Define $F(0)$ $(2)$ Define $F(x+1)$ in terms of $F(x)$ $(3)$ Define $F(x)$ for some limit value $x$. For example, following this outline, the following formulas, I believe, should be a precise description of $F$:

$(1)$ $F(0)=\mathrm{sup}\{\,f^n(0):n \in \mathbb{N}^+\}$

$(2)$ $F(x+1)=\mathrm{sup}\{\,f^n(F(x)+1):n \in \mathbb{N}^+\}$

$(3)$ When $x$ is a limit we have: $F(x)=\mathrm{sup}\{\,F(\alpha): \alpha<x\}$

There is one interesting point in all of this. If there is a fixed computable description (needs to be made a bit more precise) of well-order of $f(x+1)$ in terms of well-order of $f(x)$, and $\alpha<\omega_{CK}$, $f(0)<\omega_{CK}$, then we can show explicitly that $F(\alpha)<\omega_{CK}$.

This is quite relevant from the point of view of this question. On the very least, this already assures that whenever a given normal function $f$ is of certain form (I think the conditions on $f$ can be relaxed further) this guarantees that $F(0)<\omega_{CK}$ ---- $F(0)$ being first fixed-point of $f$.