Counting to Epsilon Naught

Shall we count higher in the ordinals? Let us strive for the ordinal epsilon naught, the first exponential fixed point—we shall completely grasp all the ordinals we encounter to that pinnacle.

In an earlier essay we had learned How to Count in the ordinals—we counted together to the ordinal ω². Anyone can do it, even a child. One begins, of course, by counting through all the finite numbers

\(\qquad 0\quad 1\quad 2\quad 3\quad 4\quad 5\quad ··· \)

The first infinite number is ω, but one can always add 1 more.

\(\qquad 0\quad 1\quad 2\quad 3\quad 4\quad 5\quad ···\quadω\quadω + 1\quadω + 2\quadω + 3\quad···\)

The next simple limit is ω + ω, which is the same as ω · 2, and so one continues. Each new limit ordinal begins a new block of ordinals of length ω, a new era of infinity.

We proceed to the next limit ordinal ω · 3, starting yet another era of infinity, then ω · 4 after that, and indeed ω · n + k for every finite n and k:

In this way we have counted to ω². The ordinals encountered along the way take the form ω · n + k for finite n and k.

Counting to ω² is rather like counting to 100. When we count to 100 you might notice that within each decade—the teens, the twenties, the thirties, and so on—it is just like counting to 10 again. In counting to 100, which is 10², we thus count to 10 altogether 10 times. Similarly, when we count to ω², we count to ω altogether ω many times. We start with the finite numbers, the original copy of ω, and then proceed from ω to ω · 2, from ω · 2 to ω · 3, and so on. In counting up to ω², we thus encounter ω many eras, each of size ω, in effect counting to ω altogether ω many times. And just as the numbers up to 100 have two digits in base ten, with the form 10 · n + k, similarly the ordinals up to ω² have the form ω · n + k, which is two digits in base ω.

The ordinal ω² is the first compound limit ordinal—a limit ordinal that is a limit of limit ordinals since ω² is the limit of ω · n as n increases in ω. In other words, ω² is a limit ordinal, but there is no largest limit ordinal below it. A simple limit ordinal, in contrast, is a limit ordinal that is not a compound limit—all simple limits take the form α + ω for some ordinal α.

Counting to ω^ω and beyond

But I should truly like us to count much further. We essentially repeat the process of counting to ω² when counting from ω² to ω² · 2, then again when counting further to ω² · 3, and similarly through every successive ω² · n. With ω many repetitions, we thus count to ω² · ω, which is the ordinal ω³. By repeating that process ω many times, we reach ω⁴, and so on. Thus we are on our way to the local peak ω^ω, which is the supremum of ωⁿ for all finite numbers n.

Continuing further, if we count like this to ω^ω altogether ω many times, first to ω^ω · 2, then to ω^ω · 3, and so on, then we shall reach ω^ω · ω, which is the same as ω^ω+1. In light of the difficulty of reaching ω^ω in the first place, however, and having had to do that work ω many times to reach ω^ω+1, we might notice that it was a troublesome burden for us to increase the exponent merely by 1. And we shall have infinitely more such trouble again to reach ω^ω+2, and then still infinitely more trouble to reach ω^ω+3, and so on. Each increase of the exponent by 1 requires an additional infinite duplication of all the preceding difficult work to that juncture. And yet we shall not stop counting. With perseverance we shall reach ω^ω·2 and beyond—every tiny increase in the exponent is an achievement to be celebrated.

With stoical fortitude, we thus find our way to ω^ω·3 and then to ω^ω·4, on the way to

\(ω^{ω^2}.\)

Eventually, exceeding that we shall arrive at

\(ω^{ω^3}\)

and then

\(ω^{ω^4}\)

and so on. We likely find ourselves exhausted at each new height of achievement. Nevertheless, we continue onward to

\(ω^{ω^ω}\!.\)

With enduring heroic dedication, we press on ever upward, successively scaling the towering further summits:

\( ω\qquadω^ω\qquadω^{ω^ω}\qquad ω^{ω^{ω^ω}}\qquad ω^{ω^{ω^{ω^ω}}}\qquad··· \)

Each new step up with these finite-stack tetrations is a vast increase over the previous instance—remember how difficult it was to increase the exponent just by 1, but here we see huge steps up with vast exponential towers of increase. Nevertheless, with silent resolve and quiet determination we shall climb through these iterated exponential powers. The supremum of these finite-stack tetrations is a vast pinnacle, the ordinal known as ε₀.

Welcome to this series of essays on the ordinals and ordinal arithmetic—you can find them in the ordinal-arithmetic tag. In this essay, we consider the ordinals up to the ordinal ε₀, which we shall prove, amazingly, is a fixed point of ordinal exponentiation, and we shall introduce a computable ordinal denotation system for the ordinals up this point. Afterwards, we shall give an application of this ordinal technology with Goodstein’s theorem and the Hydra game. You are welcome to join and follow along!

Let us get started more seriously.