What comes after $1$, $\omega$, $\epsilon_0$, ...?

Question

Note that I am not a mathematician. I'm working from sources like Gödel, Escher, Bach and Transfinite Ordinals and Their Notations For The Uninitiated. Therefore, I'm looking for the most basic, non-specialist, pop-science answer you can give me. (Your answer will undoubtedly include "It depends," but I hope it will not consist solely of those two words.)

One of the intriguing claims in Gödel, Escher, Bach is "there is no recursive rule for naming ordinals" — that is, as you count higher, you'll end up needing new names not just on a regular basis but on an irregular basis, such that you can't even make up a rule for naming the new numbers anymore. I understand how the ordinal numbers begin:

$$ 1, 2, 3, \dots, \omega \\ \omega + 1, \omega + 2, \dots, 2\omega \\ $$ (Please excuse my writing $2\omega$ instead of $\omega2$. This should set your expectations correctly for the kind of answer I'd like!) Then we just keep finding sequences and taking suprema: $$ 2\omega, 3\omega, 4\omega, \dots, \omega^2 \\ \omega^2, \omega^3, \omega^4, \dots, \omega^\omega \\ \omega^\omega, \omega^{\omega+1}, \dots, \omega^{2\omega}, \dots, \omega^{\omega^{\omega}} \\ \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \dots, \epsilon_0 $$ At this point ($\epsilon_0$) we encounter the need to introduce a new name for a supremum, for only the second time ever. (The first time was when we introduced $\omega$.) At this point my book-learning runs out, but I intuit that we continue: $$ \epsilon_0 + 1, \epsilon_0 + 2, \dots, \epsilon_0 + \omega \\ \epsilon_0 + 2\omega, \epsilon_0 + \omega^2, \epsilon_0 + \omega^\omega, \dots, 2\epsilon_0 \\ 2\epsilon_0, 3\epsilon_0, \dots, \omega\epsilon_0 \\ \omega\epsilon_0, \omega^2\epsilon_0, \omega^\omega\epsilon_0, \omega^{\omega^\omega}\epsilon_0, \dots, \epsilon_0^2 \\ \epsilon_0^2, \epsilon_0^3, \dots, \epsilon_0^\omega \\ \epsilon_0^\omega, \epsilon_0^{2\omega}, \epsilon_0^{\omega^2}, \epsilon_0^{\omega^\omega}, \dots, \epsilon_0^{\epsilon_0} \\ \epsilon_0, \epsilon_0^{\epsilon_0}, \epsilon_0^{\epsilon_0^{\epsilon_0}}, \dots, ?? $$

And now I need a name for the supremum of this sequence. Intuitively I'd like to call it something like $\epsilon_1$; but I bet it has a "real" name. (I also wouldn't be at all surprised if there were some ordinal equivalent of the Continuum Hypothesis, such that technically $\epsilon_1$ might or might not be the name of this number, but where for pop-science purposes we can treat it as such, as long as we preface our remarks with an incantation like "Assuming ZFC...")

Intuitively then I'd eventually need the name $\epsilon_2$ for the supremum of

$$ \epsilon_1, \epsilon_1^{\epsilon_1}, \epsilon_1^{\epsilon_1^{\epsilon_1}}, \dots $$

and then $\epsilon_3, \epsilon_4, \dots$ before finally needing the name $\epsilon_\omega$ for the supremum of that sequence...

Now, everything from $\epsilon_1$ onward was just my blind conjecture; but assuming I'm roughly on the right track, I do see shades of the Tortoise and Achilles here. But — so far, I haven't had any trouble making up names for all these ordinal numbers. The real trouble starts when I get to

$$ \epsilon_1, \epsilon_2, \epsilon_3, \dots, \epsilon_\omega \\ \epsilon_\omega, \epsilon_{\omega^\omega}, \dots, \epsilon_{\epsilon_0} \\ \epsilon_{\epsilon_0}, \epsilon_{\epsilon_1}, \epsilon_{\epsilon_2}, \dots, \epsilon_{\epsilon_\omega} \\ \epsilon_{\epsilon_\omega}, \epsilon_{\epsilon_{\omega^\omega}}, \epsilon_{\epsilon_{\omega^{\omega^\omega}}}, \dots, \epsilon_{\epsilon_{\epsilon_0}} \\ \epsilon_0, \epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, \dots, ?? $$

Uh-oh! Now I really need a new name! I could call this number $\zeta_0$ (again, I bet it has a real name, if I'm not off in the weeds yet), and then keep going: $\zeta_0, \zeta_0 + 1, \zeta_0 + \omega, \zeta_0 + \epsilon_0, 2\zeta_0, \dots$

What I still don't intuitively "get" is why GEB says "there is no recursive rule for naming ordinals". I mean, my method of making up names seems to be working so far! But I admit I've only gone 3 steps ($\omega, \epsilon, \zeta$) and there's an infinite number of steps left to go. And then there'll be an $\omega$'th step after that, right?

But still, I don't intuitively "get" where this recursion breaks down, if it does.

So this is kind of a two-parter: Number one, if I've made any major errors of fact in the above, please correct me (especially about "official" names for $\epsilon_1$ and $\zeta_0$). Number two, please explain GEB's claim that "there is no recursive rule for naming ordinals."

In case it helps, I am fairly familiar with Cantor's diagonal argument and the proof of the undecidability of the Halting Problem.

Answer 1

I think you're essentially going after the Veblen function. If I understand it correctly, $\varphi_1(\alpha)$ and $\varphi_2(\alpha)$ are your $\epsilon_\alpha$ and $\zeta_\alpha$. Whatever third symbol you come up with will be $\varphi_3$; whatever $\omega$-eth symbol you come up with will be $\varphi_\omega$.

Eventually you'll have a $\zeta_0$-eth symbol. The Veblen function would write that as $\varphi_{\varphi_2(0)}$. And so on.

But what do we call the limit of $\varphi_0(0)$, $\varphi_{\varphi_0(0)}(0)$, $\varphi_{\varphi_{\varphi_0(0)}(0)}(0)$, etc.? This is the ordinal you get with a subscript going infinitely deep. It would be the first ordinal that can't be written with just the $\varphi$ function. Your scheme will never get you past that barrier. This limit is called the Feferman–Schütte ordinal, written $\Gamma_0$.

Answer 2

Everything looks correct so far. Likewise, all the naming is done correctly. However, there are more succinct ways to write all this. Simply use a two argument Veblen function:

$$\varphi_0(x)=\omega^x$$

$$\varphi_\alpha(0)=\sup\{\varphi_\beta^n(0):n<\omega,\beta<\alpha\}$$

$$\varphi_\alpha(x)=\sup\{\varphi_\beta^n(\varphi_\alpha(y)+1):n<\omega,y<x,\beta<\alpha\}$$

where $f^n$ is function iteration. For $n\in\{1,2,3,\dots\}$, we have

$$f^n(x)\in\{f(x),f(f(x)),f(f(f(x))),\dots\}$$

This gives

$$\varepsilon_x=\varphi_1(x)$$

$$\zeta_x=\varphi_2(x)$$

$$\eta_x=\varphi_3(x)$$

$$\vdots$$

Now, I believe what GEB means by "there is no recursive rule for naming ordinals" can be explained through an example:

Let $\Gamma_0$ be the Feferman–Schütte ordinal. It can be given by

$$f(x)=\varphi_x(0)$$

$$\Gamma_0=\sup\{f^n(1),n<\omega\}$$

The problem here is that it will require a different kind of recursion to reach this ordinal. To make it clear, consider the following function:

$$C(0)=\{0,1\}$$

$$C(n+1)=C(n)\cup\{\underbrace{\gamma+\delta,\gamma\delta,\varphi_\gamma(\delta)}:\gamma,\delta\in C(n)\}$$

Basically, starting at $0$ and $1$, then repeatedly apply your recursion. Your recursion methods are described by the operations presented above the braces.

The problem with this is that you will never reach $\sup\{\gamma:\gamma\in C(\alpha)_n,n<\omega\}$, because to do so would require you to apply an operation outside of the operations you are given.

Of course, put whatever you want above the braces and you will find that since the surpremum of every set exists, there is no single recursive rule for naming all ordinals (mainly the supremum of all the $C$'s.