1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ $\epsilon_1$ is indeed the name of that ordinal. $\endgroup$ – Akiva Weinberger Aug 1 '17 at 18:31
  • $\begingroup$ Likewise, $\zeta_0$ is the limit of $\epsilon_x$. $\endgroup$ – Simply Beautiful Art Aug 1 '17 at 18:34
  • 1
    $\begingroup$ I don't really see why you have contempt for correctness with respect to the order of multiplication ($\omega 2$ vs. $2 \omega$). There is value in respecting conventions / trying to do things properly, even if you're "not a mathematician". $\endgroup$ – Mr. Chip Aug 1 '17 at 18:35
  • 2
    $\begingroup$ Any naming system is fooled by the question, "What's the set of all ordinals I can name with this naming system? …And what's the first ordinal larger than all of those?" (Note that any naming system will only be able to name countable many things.) $\endgroup$ – Akiva Weinberger Aug 1 '17 at 18:48
  • 1
    $\begingroup$ Since you have the computability tag, it may interest you that $\omega_1^{\mathrm{CK}}$ is the first uncomputable ordinal (the Church-Kleene ordinal) and there are other very large uncomputable but also countable ordinals. You have the admissible ordinals, then the recursively inaccessible, then the hyper recursively inaccessible... $\endgroup$ – Simply Beautiful Art Aug 2 '17 at 0:12
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ My very Achillean response is: Then can't I make $\Gamma_0, \Gamma_1, \Gamma_\omega, \Gamma_{\phi_1(0)}, \Gamma_{\phi_{\phi_1(0)}(0)}, \dots, \Gamma_{\Gamma_0}, \Gamma_{\Gamma_{\Gamma_0}}, \dots, \Delta_0, \dots$? But I guess ultimately we run into trouble when we've exhausted the entire system of "subscripts of any kind of thing whatever" and need to jump outside that system, eh? $\endgroup$ – Quuxplusone Aug 1 '17 at 20:50
  • 1
    $\begingroup$ @Quuxplusone Yeah, you can always build a better system. What you can't do is build a complete system, one that can name everything. $\endgroup$ – Akiva Weinberger Aug 1 '17 at 20:51
  • $\begingroup$ I suppose that's a fair answer. I wish there were an intuitive-to-me proof of that statement, though, in the way that we can intuitively prove the uncountability of the reals or the undecidability of the Halting Problem. I think your argument above that "any naming system will only be able to name countably many things" might be half of an intuitive proof... except that I intuitively consider "decimal notation" to be a naming system for the reals, of which there are uncountably many... so that argument seems to have a hole in it already! $\endgroup$ – Quuxplusone Aug 1 '17 at 20:58
  • 1
    $\begingroup$ @Quuxplusone Decimals don't count because you need infinitely many symbols for each "name". I've been assuming we want finitely many symbols for each ordinal name. $\endgroup$ – Akiva Weinberger Aug 1 '17 at 20:59
  • 1
    $\begingroup$ Note that every ordinal we've mentioned so far is countable… and we can form the set of all countable ordinals. This set is uncountable. (It's kind of like how the set of all finite numbers is infinite.) The first uncountable ordinal is labeled $\omega_1$. However, the set of all ordinals doesn't exist (because, if it did, we could take its supremum and get a new ordinal). $\endgroup$ – Akiva Weinberger Aug 1 '17 at 21:07
2
$\begingroup$

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.

$\endgroup$

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.