Large Countable Ordinals (Part 2)

Last time I took you on a road trip to infinity. We zipped past a bunch of countable ordinals

\omega , \; \omega^\omega,\; \omega^{\omega^\omega}, \;\omega^{\omega^{\omega^\omega}}, \dots

and stopped for gas at the first one after all these. It’s called \epsilon_0. Heuristically, you can imagine it like this:

\epsilon_0 = \omega^{\omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}}

More rigorously, it’s the smallest ordinal x obeying the equation

x = \omega^x

Beyond εo

But I’m sure you have a question. What comes after \epsilon_0?

Well, duh! It’s

\epsilon_0 + 1

Then comes

\epsilon_0 + 2

and then eventually we get to

\epsilon_0 + \omega

and then

\epsilon_0 + \omega^2 ,\dots, \epsilon_0 + \omega^3,\dots \epsilon_0 + \omega^4,\dots

and after a long time

\epsilon_0 + \epsilon_0 = \epsilon_0 2

and then eventually

\epsilon_0^2

and then eventually….

Oh, I see! You wanted to know the first really interesting ordinal after \epsilon_0.

Well, this is a matter of taste, but you might be interested in \epsilon_1. This is the first ordinal after \epsilon_0 that satisfies this equation:

x = \omega^x

How do we actually reach this ordinal? Well, just as \epsilon_0 was the limit of this sequence:

\omega , \; \omega^\omega,\; \omega^{\omega^\omega}, \;\omega^{\omega^{\omega^\omega}}, \dots

\epsilon_1 is the limit of this:

\epsilon_0 + 1, \; \omega^{\epsilon_0 + 1}, \; \omega^{\omega^{\epsilon_0 + 1}}, \; \omega^{\omega^{\omega^{\epsilon_0 + 1}}},\dots

You may wonder what I mean by the ‘limit’ of an increasing sequence of ordinals. I just mean the smallest ordinal greater than or equal to every ordinal in that sequence. Such a thing is guaranteed to exist, since if we treat ordinals as well-ordered sets, we can just take the union of all the sets in that sequence.

Here’s a picture of \epsilon_1, taken from David Madore’s interactive webpage:

In what sense is \epsilon_1 the first "really interesting" ordinal after \epsilon_0?

For one thing, it’s first that can’t be built out of 1, \omega and \epsilon_0 using finitely many additions, multiplications and exponentiations. In other words, if we use Cantor normal form to describe ordinals (as explained last time), and allow expressions involving \epsilon_0 as well as 1 and \omega, we get a notation for all ordinals up to \epsilon_1.

What’s the next really interesting ordinal after \epsilon_1? As you might expect, it’s called \epsilon_2. This is the next solution of

x = \omega^{x}

and it’s defined to be the limit of this sequence:

\epsilon_1 + 1, \; \omega^{\epsilon_1 + 1}, \;\omega^{\omega^{\epsilon_1 + 1}}, \; \omega^{\omega^{\omega^{\epsilon_1 + 1}}},\dots

Maybe now you get the pattern. In general, \epsilon_{\alpha} is the
\alphath solution of x = \omega^{x}. We can define this, if we’re smart, for any ordinal \alpha.

So, we can keep driving on through fields of ever larger ordinals:

\epsilon_2,\dots, \epsilon_{3},\dots, \epsilon_{4}, \dots

and eventually

\epsilon_{\omega}

which is the first ordinal bigger than \epsilon_0, \epsilon_1, \epsilon_2, \dots

Let’s stop and take a look!

Nice! Okay, back in the car…

\epsilon_{\omega+1},\dots, \epsilon_{\omega+2},\dots, \epsilon_{\omega+1},\dots

and then

\epsilon_{\omega^2},\dots , \epsilon_{\omega^3},\dots, \epsilon_{\omega^4},\dots

and then

\epsilon_{\omega^{\omega}},\dots, \epsilon_{\omega^{\omega^{\omega}}},\dots

As you can see, this gets boring after a while: it’s suspiciously similar to the beginning of our trip through the ordinals. The same ordinals are now showing up as subscripts in this epsilon notation. But we’re moving much faster now, since I’m skipping over much bigger gaps, not bothering to mention all sorts of ordinals like

\epsilon_{\omega^{\omega}} + \epsilon_{\omega 248} + \omega^{\omega^{\omega + 17}} + 1

Anyway… while we’re zipping along, I might as well finish telling you the story I started last time. My friend David Sternlieb and I were driving across South Dakota on Route 80. We kept seeing signs for the South Dakota Tractor Museum. When we finally got there, we were driving pretty darn fast, out of boredom—about 85 miles an hour. And guess what happened then!

Oh — wait a minute—this one is sort of interesting:

\displaystyle{ \epsilon_{\epsilon_0} }

Then come some more like that:

\epsilon_{\epsilon_1},\dots, \epsilon_{\epsilon_2},\dots \epsilon_{\epsilon_3},\dots

until we reach this:

\epsilon_{\epsilon_{\omega}}

and then

\epsilon_{\epsilon_{\omega^{\omega}}},\dots, \epsilon_{\epsilon_{\omega^{\omega^{\omega}}}},\dots

As we keep speeding up, we see:

\epsilon_{\epsilon_{\epsilon_0}},\dots \epsilon_{\epsilon_{\epsilon_{\epsilon_0}}},\dots \epsilon_{\epsilon_{\epsilon_{\epsilon_{\epsilon_0}}}},\dots

So, anyway: by the time we got that tractor museum, we were driving really fast. And, all we saw as we whizzed by was a bunch of rusty tractors out in a field! It was over in a split second! It was a real anticlimax — just like this anecdote, in fact.

But that’s just the way it is when you’re driving through these ordinals! Every ordinal, no matter how large, looks pretty pathetic and small compared to the ones ahead — so you keep speeding up, looking for something ‘really new and different’. But when you find one, it turns out to be part of a larger pattern, and soon that gets boring too.

For example, when we reach the limit of this sequence:

\epsilon_0, \epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, \epsilon_{\epsilon_{\epsilon_{\epsilon_0}}}, \epsilon_{\epsilon_{\epsilon_{\epsilon_{\epsilon_0}}}},\dots

our notation fizzles out again, since this is the first solution of

x = \epsilon_{x}

We could make up a new name for this ordinal, like \zeta_0. I don’t think this name is very common, though I’ve seen it. We could call it the Tractor Museum of Countable Ordinals.

Now we can play the whole game again, defining the zeta number \zeta_{\alpha} to be the \alphath solution of

x = \epsilon_x

sort of like how we defined the epsilons. This kind of equation, where something equals some function of itself, is called a fixed point equation.

But since we’ll have to play this game infinitely often, we might as well be more systematic about it!

The Veblen hierarchy

As you can see, we keep running into new, qualitatively different types of ordinals. First we ran into the powers of omega. Then we ran into the epsilons, and then the zetas. It’s gonna keep happening! For each type of ordinal, our notation fizzles out when we reach the first ‘fixed point’— when the xth ordinal of this type is actually equal to x.

So, instead of making up infinitely many Greek letters for different types of ordinals let’s index them… by ordinals! For each ordinal \gamma we’ll have a type of ordinal. We’ll let \phi_\gamma(\alpha) be the \alphath ordinal of type \gamma.

We can use the fixed point equation to define \phi_{\gamma+1} in terms of \phi_{\gamma}. In other words, we start off by defining

\phi_0(\alpha) = \omega^{\alpha}

and then define

\phi_{\gamma+1}(\alpha)

to be the \alphath solution of

x = \phi_{\gamma}(x)

where we start counting at \alpha = 0, so the first solution is called the ‘zeroth’.

We can even make sense of \phi_\gamma(\alpha) when \gamma itself is infinite! Suppose \gamma is a limit of smaller ordinals. Then we define \phi_\gamma(x) to be the limit of \phi_\beta(x) as \beta approaches \gamma. I’ll make this more precise next time.

We get infinitely many different types of ordinals, called the Veblen hierarchy. So, concretely, the Veblen hierarchy starts with the powers of \omega:

\phi_0(\alpha) = \omega^\alpha

and then it goes on to the ‘epsilons’:

\phi_1(\alpha) = \epsilon_\alpha

and then it goes on to what I called the ‘zetas’:

\phi_2(\alpha) = \zeta_\alpha

But that’s just the start!

The Feferman–Schütte ordinal

Boosting the subscript \gamma in \phi_\gamma(\alpha) increases the result much more than boosting \alpha, so let’s focus on that and just let \alpha = 0. The Veblen hierarchy contains ordinals like this:

\phi_{\omega}(0), \; \phi_{\omega+1}(0), \; \phi_{\omega+2}(0), \dots

and then ordinals like this:

\phi_{\omega^2}(0), \; \phi_{\omega^3}(0), \; \phi_{\omega^4}(0), \dots

and then ordinals like this:

\phi_{\omega^\omega}(0), \; \phi_{\omega^{\omega^\omega}}(0), \; \phi_{\omega^{\omega^{\omega^{\omega}}}}(0), \dots

and then this:

\phi_{\epsilon_0}(0), \phi_{\epsilon_{\epsilon_0}}(0), \phi_{\epsilon_{\epsilon_{\epsilon_0}}}(0), \dots

where of course I’m skipping huge infinite stretches of ‘boring’ ones. But note that

\phi_{\omega}(0) = \phi_{\phi_0(0)}(0)

and

\phi_{\epsilon_0}(0) = \phi_{\phi_1(0)}(0)

and

\phi_{\zeta_0}(0) = \phi_{\phi_2(0)}(0)

In short, we can plug the phi function into itself—and we get the biggest effect if we plug it into the subscript!

So, if we’re in a rush to reach some really big countable ordinals, we can try these:

\phi_0(0), \; \phi_{\phi_0(0)}(0) , \; \phi_{\phi_{\phi_0(0)}(0)}(0), \dots

But the limit of these is an ordinal x that has

x = \phi_x(0)

This is called the Feferman–Schütte ordinal and denoted \Gamma_0.

In fact, the Feferman–Schütte ordinal is the smallest solution of

x = \phi_x(0)

Since this equation is self-referential, we can’t describe Feferman–Schütte ordinal using the Veblen hierarchy—at least, not without using the Feferman–Schütte ordinal!

Indeed, some mathematicians have made a big deal about this ordinal, claiming it’s

the smallest ordinal that cannot be described without self-reference.

This takes some explaining, and it’s somewhat controversial. After all, there’s a sense in which every fixed point equation is self-referential. But there’s a certain precise sense in which the Feferman–Schütte ordinal is different from previous ones.

Anyway, you have admit that this is a very cute description of the Fefferman–Schuette ordinal: “the smallest ordinal that cannot be described without self-reference.” Does it use self-reference? It had better—otherwise we have a contradiction!

It’s a little scary, like this picture:

More importantly for us, the Veblen hierarchy fizzles out when we hit the Feferman–Schuette ordinal. Let me say what I mean by that.

Veblen normal form

The Veblen hierarchy gives a notation for ordinals called the Veblen normal form. You can think of this as a high-powered version of Cantor normal form, which we discussed last time.

Veblen normal form relies on this result:

Theorem. Any ordinal \beta can be written uniquely as

\beta = \phi_{\gamma_1}(\alpha_1) + \dots + \phi_{\gamma_{k}}(\alpha_k)

where k is a natural number, each term is less than or equal to the previous one, and \alpha_i < \phi_{\gamma_i}(\alpha_i) for all i.

Note that we can also use this theorem to write out the ordinals \beta_i and \gamma_i, and so on, recursively. So, it gives us a notation for ordinals.

However, this notation is only useful when all the ordinals \alpha_i, \gamma_i are less than the ordinal \beta that we’re trying to describe. Otherwise we need to already have a notation for \beta to express \alpha in Veblen normal form!

So, the power of this notation eventually fizzles out. And the place where it does is Feferman–Schütte ordinal. Every ordinal less than this can be expressed in terms of 0, addition, and the function \phi, using just finitely many symbols!

The moral

As I hope you see, the power of the human mind to see a pattern and formalize it gives the quest for large countable ordinals a strange quality. As soon as we see a systematic way to generate a sequence of larger and larger ordinals, we know this sequence has a limit that’s larger then all of those! And this opens the door to even larger ones….

So, this whole journey feels a bit like trying to outrace our car’s own shadow as we drive away from the sunset: the faster we drive, the faster it shoots ahead of us. We’ll never win.

On the other hand, we’ll only lose if we get tired.

So it’s interesting to hear what happens next. We don’t have to give up. The usual symbol for the Feferman–Schütte ordinal should be a clue. It’s called \Gamma_0. And that’s because it’s just the start of a new series of even bigger countable ordinals!

I’m dying to tell you about those. But this is enough for today.

This entry was posted on Monday, July 4th, 2016 at 1:00 am and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

46 Responses to Large Countable Ordinals (Part 2)

  1. Marek14 says:
    4 July, 2016 at 4:32 am

    A question that comes in mind is: can we actually find any example of an ordered set corresponding to such ordinals, OTHER than the ordinal itself? For example, a set of all natural numbers, followed by set of all pairs in lexicographic order, then all triplets, quadruplets, etc… is still just \omega^\omega. To get to epsilon, we could imagine similar lexicographic ordering of finite sequences of finite sequences, and of finite sequences of finite sequences of finite sequences, up to arbitrarily many levels of nesting, But beyond that…

    Reply
    • John Baez says:
      4 July, 2016 at 4:59 am

      There’s an order-preserving isomorphism between the set ordinals up to \epsilon_0 and the set of finite rooted trees, with a certain nice ordering on them. This is the basis of the hydra game, which you can play online here if you can convince your browser it’s safe to run this Java applet. (I promise: it’s safe.)

      It’s also possible to explicitly describe a subset of the real line which, with the usual ordering, is isomorphic to the set of ordinals up to \epsilon_0. That’s how David Madore drew the picture here:

      Click on the picture, and then click on the names of ordinals, to explore this further.

      However, I don’t know if you’ll consider these structures to be different from “the ordinal itself”. Whenever two mathematical structures are isomorphic, it’s a bit subjective to decide whether they are “the same” or “different”.

      I should add that the main use, so far, of countable ordinals above \epsilon_0 is to measure the strength of axiom systems. You can see an explanation and lots of examples here:

      • Wikipedia, Ordinal analysis.

      Proof theorists keep needing larger countable ordinals to measure the strength of stronger axiom systems! For example, it seems nobody has yet found a good notation for countable ordinals large enough to measure the strength of Zermelo—Fraenkel set theory:

      • Scott Aaronson, Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?, MathOverflow, 26 April 2014.

      Henry Towsner’s short answer is:

      Finding an explicit description of the ordinal for ZFC is an active problem in proof theory, but progress has been very slow..

      Reply
      • Marek14 says:
        4 July, 2016 at 5:19 am

        Well, for the subset of real line, the question is whether each ordinal can be actually assigned a specific real number. A picture by itself isn’t much.

        If you have an interval, then you can put omega in it by filling it with an infinite sequence — for <0,1), the sequence of 0, 1/2, 3/4, 7/8, etc. would be sufficient.

        To get omega^2, you’d iterate this, putting another omega-worth to intervals <0,1/2), <1/2,3/4), <3/4,7/8), etc. For omega^omega, you’d fit omega into <0,1/2), omega^2 into <1/2, 3/4), omega^3 into <3/4,7/8), etc. But can the above definition of epsilon give an explicit assignment of a real (well, rational, probably) number for every ordinal below epsilon?

        Reply
        • Royce Peng says:
          4 July, 2016 at 7:33 am

          I actually wrote an answer to this question on Math Stack Exchange: see

          http://math.stackexchange.com/questions/165151/question-of-an-isomorphism-of-epsilon-0-and-a-subset-of-the-rationals/200616#200616.

          It turns out, though, that any countable ordinal can be embedded into the rationals! Given a countable ordinal \alpha, we can define a bijection f:\mathbb{N} \mapsto \alpha. Start by setting g(f(0)) = \frac{1}{2}. Set g(f(1)) to either 1/4 or 3/4, depending on whether or not f(0) is bigger than f(1). Say it is bigger. Then set g(f(2)) to be either 1/4 if it f(2) is less than f(0), 5/8 if f(2) is between f(0) and f(1), and 7/8 if f(2) is bigger than f(1). And just continue in that fashion: each time, set g(f(n)) in the middle of the interval where f(n) is supposed to be (considering 0 and 1 to be -infinity and infinity). At the end you will have the ordinal \alpha represented as a set of dyadic rationals betwen 0 and 1.

          What about uncountable ordinals? Unfortunately, those cannot be embedded in the real numbers; after each ordinal, there is a next one, which must be some positive distance to the right. So if we could embed an uncountable ordinal in the real numbers, to each ordinal in the set we could associate a rational number in the interval between that ordinal and the next. But there are only countably many rational numbers, a contradiction.

      • John Baez says:
        4 July, 2016 at 7:06 am

        Marek14 wrote:

        But can the above definition of epsilon give an explicit assignment of a real (well, rational, probably) number for every ordinal below epsilon?

        Yes, there are various explicit ways to do this. To see one way, click on this:

        and then type “CTRL-u” to see the Javascript program that drew the picture. But personally, since I don’t read Javascript very well, I’d find it more fun to make up my own way!

        Reply
    • John Baez says:
      4 July, 2016 at 7:27 am

      Oh, and here’s another way to get a well-ordered set that’s isomorphic to a fairly large ordinal.

      Consider all functions

      f \colon [1,\infty) \to [1,\infty)

      built up from the functions 1 and x by addition, multiplication and exponentiation. So, functions like this:

      \displaystyle{ x^{x^{x + x} + x} x + x + x + 1 }

      Say f < g if f(x) < g(x) for all sufficiently large x. In 1973 Ehrenfeucht proved this ordering was a well-ordering. So, this set of functions, with this ordering, corresponds to some ordinal.

      Which ordinal? Skolem proved that \epsilon_0 is a lower bound. In 1978, Levitz proved that \kappa_0 is an upper bound.

      Skolem guessed that the right answer is \epsilon_0. This certainly seems like the obvious guess, given how these functions:

      x^{x^x} x + x + x + 1

      look a lot like the ordinals below \epsilon_0:

      \omega^{\omega^\omega} \omega + \omega + \omega + 1

      Reply
    • Royce Peng says:
      4 July, 2016 at 8:39 am

      Another very nice well-ordered set are the “Fusible numbers”. See here: http://www.mathpuzzle.com/fusible.pdf for a very nice presentation of the fusible numbers, although a couple of things in the slides are incorrect.

      Basically, the idea is that you have an infinite set of fuses that each take 1 hour to burn, and the fusible numbers are those numbers of hours that you can time by burning the fuses in various ways. So you can time 1/2 hour by light a single fuse at one end. You can time 3/4 of an by lighting fuse 1 at both ends and fuse 2 at one end at time 0, and lighting the other end of fuse 2 when fuse 1 burns out.

      Mathematically the fusible numbers are defined as the smallest set which contains 0 and is closed under the operation a,b \mapsto \frac{a+b+1}{2} provided that |a-b| < 1. This correpsonds to lighting one end of a fuse at time a and the other at time b, so it will burn out at time \frac{a+b+1}{2}.

      A relatively simple argument proves that the fusible numbers are well-ordered, so again we can ask what ordinal the fusible numbers correspond to. We can identify a subset of the fusible numbers with order type \varepsilon_0, so that is a lower bound for the order type of the entire set. It is conjectured that the order type is exactly \varepsilon_0, but we don’t know for sure; so the situation is much like the situation for the problem of Skolem.

      Another interesting fact about fusible numbers: If we define a(x) as the next fusible number after x, and m(x) = a(x) - x, then m(x) will be a power of 1/2 (when x is a fusible number). So if we let f(x) = -\log_2 (m(x)) and focus on when x is a natural number, f(x) will be a very fast-growing function of x. If a conjecture by Junyan Xu for the fusible numbers is true, then the fusible numbers will have order type \varepsilon_0 and it appears that f will grow at the rate close to F_{\varepsilon_0}(x), where F is the fast-growing hierarchy. This is a very fast-growing function; F_\omega (x) already grows a rate equal to the Ackermann function!

      If Xu’s conjecture is false, then the order type of the fusible numbers could be larger, and the function f could grow even faster.

      Reply
  2. John Baez says:
    4 July, 2016 at 5:03 am

    Here are some puzzles in ordinal arithmetic. If you’re a super-expert, maybe you should let other people try them:

    Puzzle 1. What is \omega^{\epsilon_0}?

    Puzzle 2. What is {\epsilon_0}^\omega?

    Puzzle 3. What is \omega^{\epsilon_1}?

    Puzzle 4. What is {\epsilon_1}^\omega?

    Puzzle 5. What is {\epsilon_0}^{\epsilon_0}?

    Puzzle 6. What is {\epsilon_0}^{\epsilon_1}?

    Puzzle 7. What is {\epsilon_1}^{\epsilon_0}?

    Puzzle 8. What is {\epsilon_1}^{\epsilon_1}?

    Reply
    • Marek14 says:
      4 July, 2016 at 5:29 am

      Well, let’s see…

      1 and 3 are trivial. Epsilons are fixed points of \omega^x, so \omega^{\epsilon_0} = \epsilon_0 and \omega^{\epsilon_1} = \epsilon_1.

      2 and 4: {\epsilon_0}^\omega is {\omega^{\epsilon_0}}^\omega, or \omega^{{\epsilon_0}+1}, similarly {\epsilon_1}^\omega is \omega^{{\epsilon_1}+1}.

      5 and 8: Similarly, we get that {\epsilon_0}^{\epsilon_0} is {\omega^{\epsilon_0}}^{\epsilon_0}, or \omega^{{\epsilon_0}.2} and {\epsilon_1}^{\epsilon_1} is {\omega^{\epsilon_1}}^{\epsilon_1}, or \omega^{{\epsilon_1}.2}.

      6: {\epsilon_0}^{\epsilon_1} is is {\omega^{\epsilon_0}}^{\epsilon_1}, or \omega^{{\epsilon_0}+{\epsilon_1}} – but {\epsilon_0}+{\epsilon_1} is simply {\epsilon_1}, so it’s \omega^{{\epsilon_1}}, or simply {\epsilon_1}.

      7: Through analogical construction, we get \omega^{{\epsilon_1}+{\epsilon_0}}. We can’t simplify {\epsilon_1}+{\epsilon_0} any further, so we probably can’t get a more succinct representation.

      Reply
      • Royce Peng says:
        4 July, 2016 at 6:10 am

        2, 4, 5, 7, and 8 aren’t quite right, unless you switch at some point from talking about the ordinal to talking about the exponent.

        Reply
        • Marek14 says:
          4 July, 2016 at 7:41 am

          Yeah, that was incorrect. {\epsilon_0}^\omega = (\omega^{\epsilon_0})^\omega = \omega^{{\epsilon_0}.\omega}. If \epsilon_0 is an exponential tower of \omega \omega‘s, then this is a tower of \omega+1 \omega‘s. So, for 4, we get

          \omega^{{\epsilon_1} \cdot \omega}

          for 5 we get

          \displaystyle{ \omega^{{\epsilon_0}^2} }

          for 8

          \omega^{{\epsilon_1}^2}

          and for 7

          \omega^{{\epsilon_1} \cdot {\epsilon_0}}.

          I made a mistake in 6 as well, but the final result should still stay since {\epsilon_0}\cdot{\epsilon_1} should still equal \epsilon_1.

        • Royce Peng says:
          4 July, 2016 at 7:53 am

          Correct, but those are not in (iterated) Cantor Normal Form; you have to keep going until you everything is either addition or exponentiation with base \omega.

        • Marek14 says:
          4 July, 2016 at 7:57 am

          Not sure how to do that — after all, they all involve epsilons; aren’t Cantor Normal forms of epsilons already infinite? I could iterate it like that, but I’m not sure how to write the result; never used LaTeX before today, though it’s similar to equation tools in some text editors I used when translating books in the past.

        • Royce Peng says:
          4 July, 2016 at 8:05 am

          Indeed, the epsilon numbers cannot be reduced, so you just leave them as they are. However, numbers like \varepsilon_0 \cdot \omega are not epsilon numbers, so they should be reduced (in this case to \omega^{\varepsilon_0 + 1}).

        • John Baez says:
          4 July, 2016 at 8:09 am

          I described Cantor normal form last time:

          Theorem. Every ordinal \alpha can be uniquely written as

          \alpha = \omega^{\beta_1} c_1 + \omega^{\beta_2}c_2 + \cdots + \omega^{\beta_k}c_k

          where k is a natural number, c_1, c_2, \ldots, c_k are positive integers, and \beta_1 > \beta_2 > \cdots > \beta_k \geq 0 are ordinals.

          This works for every ordinal, but if you apply it to \epsilon_0 you get

          \epsilon_0 = \omega^{\epsilon_0}

          which isn’t very helpful. So, we can agree to leave \epsilon_0, \epsilon_1, \dots alone instead of applying this theorem to them. However, the theorem says we can always take expressions like

          {\epsilon_0}^\omega

          or

          \epsilon_0 \,\omega

          and rewrite them using the theorem.

          Of course the proof of the theorem is more informative than the mere statement of the theorem, since it says how to rewrite these expressions!

        • Marek14 says:
          4 July, 2016 at 8:18 am

          OK, so if we use normal form with epsilons, we have:

          Puzzle 1. \epsilon_0

          Puzzle 2. \omega^{\omega^{{\epsilon_0}+1}}

          Puzzle 3. \epsilon_1

          Puzzle 4. \omega^{\omega^{{\epsilon_1}+1}}

          Puzzle 5. \omega^{\omega^{{\epsilon_0}\cdot 2}}

          Puzzle 6. \epsilon_1

          Puzzle 7. \omega^{\omega^{{\epsilon_1}+{\epsilon_0}}}

          Puzzle 8. \omega^{\omega^{{\epsilon_1} \cdot 2}}

        • Royce Peng says:
          4 July, 2016 at 8:22 am

          Correct!

    • Rob Superty says:
      4 July, 2016 at 8:34 am

      Hi – I’d like to give it a shot.

      So firstly, when counting up with ordinals, I find it handy to avoid forms like \varepsilon_0^2 and instead to think of everything in powers of \omega unless at a fixed point of \omega (i.e., a pure epsilon number).

      So that means when getting up through the ordinals \varepsilon_0.2 , \varepsilon_0.3 , …, I would stop at \varepsilon_0.\omega and instead express that as \omega^{\varepsilon_0+1} , because it is the next power of \omega after the first fixed point, \varepsilon_0=\omega^{\varepsilon_0} . Just feels a bit tidier to me.

      So that being said, I’d express those 8 expressions as powers of \omega unless they are epsilon numbers. My answers are as follows:

      1) \omega^{\varepsilon_0} = \varepsilon_0
      2) \varepsilon_0^\omega = (\omega^{\varepsilon_0})^\omega = \omega^{\omega^{\varepsilon_0+1}}
      3) \omega^{\varepsilon_1} = \varepsilon_1
      4) \varepsilon_1^\omega = (\omega^{\varepsilon_1})^\omega = \omega^{\omega^{\varepsilon_1+1}}
      5) \varepsilon_0^{\varepsilon_0} = (\omega^{\varepsilon_0})^{\varepsilon_0}=\omega^{(\omega^{\varepsilon_0})}{^{(\omega^{\varepsilon_0})}}=\omega^{\omega^{\varepsilon_0.2}}
      6) \varepsilon_0^{\varepsilon_1}=\varepsilon_1
      7) \varepsilon_1^{\varepsilon_0} = (\omega^{\varepsilon_1})^{\varepsilon_0}=\omega^{(\omega^{\varepsilon_1})}{^{(\omega^{\varepsilon_0})}}=\omega^{\omega^{\varepsilon_1+\varepsilon_0}}
      8) \varepsilon_1^{\varepsilon_1} = (\omega^{\varepsilon_1})^{\varepsilon_1}=\omega^{(\omega^{\varepsilon_1})}{^{(\omega^{\varepsilon_1})}}=\omega^{\omega^{\varepsilon_1.2}}

      Hope that all renders properly!

      Reply
  3. Marek14 says:
    4 July, 2016 at 8:24 am

    Now, you have written that {\epsilon_1} is the limit of the sequence

    \epsilon_0 + 1, \; \omega^{\epsilon_0 + 1}, \; \omega^{\omega^{\epsilon_0 + 1}}, \; \omega^{\omega^{\omega^{\epsilon_0 + 1}}},\dots

    So, what is, say, limit of this similar sequence:

    \epsilon_0 + 2, \; \omega^{\epsilon_0 + 2}, \; \omega^{\omega^{\epsilon_0 + 2}}, \; \omega^{\omega^{\omega^{\epsilon_0 + 2}}},\dots?

    Should it be greater than \epsilon_1, but probably smaller than \epsilon_2?

    Second question: all the limit ordinals constructed so far are supremas of some infinite sequences, i.e. sequences with \omega members. Are there countable ordinals that require longer sequences? Or can all ordinals below \omega_1 (the first uncountable ordinal, which of course cannot be expressed in countable terms) be expressed using sequences with \omega members?

    Reply
    • Rob Superty says:
      4 July, 2016 at 8:51 am

      Hi Marek – my instinct would be that the sequence you reference would still only indicate \varepsilon_1 , but I’ll leave it to the experts to explain/confirm. Interestingly, \varepsilon_1 can also be represented by an infinite tower of \varepsilon_0 . One thing I find fascinating is the surreal number system, which gives meaning to forms like \varepsilon_{-1} and \varepsilon_{1/2} . But that’s a huge topic in itself! I’d recommend Gonshor’s Introduction to the Theory of Surreal Numbers if you’d like to learn more.

      Reply
      • Marek14 says:
        4 July, 2016 at 9:10 am

        Oh, I’m familiar with those. Some people admired actors or singers in their teens; my idol was Conway, ever since I found a copy of Winning Ways in a local university library.

        Reply
    • John Baez says:
      4 July, 2016 at 8:52 am

      Marek14 wrote:

      So, what is, say, the limit of this similar sequence:

      \epsilon_0 + 2, \; \omega^{\epsilon_0 + 2}, \; \omega^{\omega^{\epsilon_0 + 2}}, \; \omega^{\omega^{\omega^{\epsilon_0 + 2}}},\dots?

      Should it be greater than \epsilon_1, but probably smaller than \epsilon_2?

      This is a good puzzle. I’ll just give a small hint.

      Let’s call the limit of this sequence x. It’s pretty easy to see that

      x = \omega^x

      So, by definition, x is an epsilon number. If it’s the \alphath epsilon number, we call it \epsilon_\alpha.

      So, it can’t be greater than \epsilon_1 and smaller than \epsilon_2. There are no epsilon numbers between these two!

      On the other hand, x is certainly greater than or equal to \epsilon_1, which is the limit of

      \epsilon_0 + 1, \; \omega^{\epsilon_0 + 1}, \; \omega^{\omega^{\epsilon_0 + 1}}, \; \omega^{\omega^{\omega^{\epsilon_0 + 1}}},\dots

      After all, each term in the sequence you gave is greater than or equal to the corresponding term in this sequence.

      So, x is either \epsilon_1, \epsilon_2, or \epsilon_\alpha for some \alpha > 2.

      At this point I will shut up and let others continue.

      Reply
    • Royce Peng says:
      4 July, 2016 at 8:53 am

      If we call the first sequence a_i and the second sequence b_i, notice that

      a_1 < b_1 < a_2 < b_2 < a_3 < b_3 \ldots.

      So it should be clear that any ordinal larger than all of the a_i will also be larger than all of the b_i and vice versa, so of course the smallest such ordinal will be the same for both.

      Remember that an ordinal \alpha is countably infinite if and only if there is a bijection f from the natural numbers to \alpha. So if \alpha is limit, we can form a sequence of length \omega by starting with f(0), then selecting the first f(n) that is greater than it, then the next greater ordinal, and so on. This is obviously a sequence of length \omega, and it will have limit \alpha, since for any ordinal \beta < \alpha, we will at some point pass \beta in the sequence, at which point we will either select \beta, or pass it by because we have already exceeded it.

      Reply
  4. bjonas says:
    4 July, 2016 at 4:52 pm

    Your description of the Veblen normal form is a bit confused, it mixes alpha and beta.

    Reply
    • John Baez says:
      5 July, 2016 at 2:51 am

      Thanks, I’ll check that out and fix if it needed.

      Reply
    • John Baez says:
      5 July, 2016 at 2:58 am

      I don’t see a mistake here:

      Theorem. Any ordinal \beta can be written uniquely as

      \beta = \phi_{\gamma_1}(\alpha_1) + \dots + \phi_{\gamma_{k}}(\alpha_{k})

      where k is a natural number, each term is less than or equal to the previous one, and \alpha_{i} < \phi_{\gamma_{i}}(\alpha_i) for all i.

      Reply
      • Anonymous says:
        6 July, 2016 at 2:43 am

        The paragraphs after that refer to \beta_i as \alpha_i (and to \alpha as \beta )

        Reply
        • John Baez says:
          6 July, 2016 at 5:22 am

          Got it! Thanks. Fixed.

          By the way, Wikipedia says that in Veblen normal form we have

          \alpha_i < \phi_{\gamma_i}(\alpha_i)

          but I’m afraid we might only have

          \alpha_i \le \phi_{\gamma_i}(\alpha_i)

          when \beta reaches or exceeds the small Veblen ordinal, which is a fixed point of all the functions \phi_\gamma.

          What’s the Veblen normal form of the small Veblen ordinal? I feel I only understand Veblen normal form for ordinals below this.

        • Royce Peng says:
          6 July, 2016 at 7:07 am

          We can always have \alpha_i < \varphi_{\gamma_i}(\alpha_i), by choosing \gamma_i to be as large as possible. (We can choose a maximal \gamma_i since the set of possible values is closed; but if \alpha_i = \varphi_{\gamma_i}(\alpha_i) then we can increase \gamma_i by one.)

          The Veblen normal form for any strongly critical ordinal $\latex \alpha$ such as the Small Veblen Ordinal is \varphi_\alpha(0).

        • John Baez says:
          6 July, 2016 at 8:53 am

          Thanks! Now I feel dumb, because I should have been able to figure that out. But that’s very helpful and reassuring.

  5. Refurio Anachro says:
    4 July, 2016 at 9:03 pm

    Wow. You really made this one roll, John. I have to admit, I thought about collecting stuff for a book as well, but reading this post I might end up preferring to suggest yours. Fancy! And no, that wouldn’t stop me.

    Reply
  6. Royce Peng says:
    5 July, 2016 at 5:48 am

    Near the end you say that every ordinal less than the Feferman-Schutte ordinal can be expressed in terms of 1, +, and the \varphi function. The 1 should be replaced by 0 I think.

    Also, I think ordinal neophytes will be at a loss on how to get things like \varepsilon_\omega and \varphi_\omega(\alpha); perhaps you could add some detail there?

    Reply
    • John Baez says:
      5 July, 2016 at 8:29 am

      Royce wrote:

      The 1 should be replaced by 0 I think.

      You’re right!

      perhaps you could add some detail there?

      Hmm, I don’t want to turn this road trip into a textbook… and the advantage of blog articles is that people can ask questions… but I’ll mention that \epsilon_\omega is the first ordinal bigger than \epsilon_0, \epsilon_1, \epsilon_2, \dots

      Next time I’ll talk about some of this stuff a bit more formally.

      Reply
      • Marek14 says:
        5 July, 2016 at 9:57 am

        Well, maybe it would be easier to say that \epsilon_\omega = \epsilon_0 + \epsilon_1 + \epsilon_2 + \dots?

        Reply
        • Royce Peng says:
          5 July, 2016 at 10:05 am

          That might be more concise, but perhaps more confusing to the uninitiated. (I think it’s less clear that the ordinal defined by that expression is closed under omega exponentiation, for example.)

        • John Baez says:
          5 July, 2016 at 12:30 pm

          If I said

          \epsilon_\omega = \epsilon_0 + \epsilon_1 + \epsilon_2 + \cdots

          someone might point out that I haven’t defined an infinite sum of ordinals, or even pointed to a definition.

          Of course the definition of this infinite sum is that it’s the limit of

          \epsilon_0, \; \epsilon_0 + \epsilon_1, \; \epsilon_0 + \epsilon_1 + \epsilon_2, \dots

          but that seems more complicated than saying \epsilon_\omega is the limit of

          \epsilon_0, \; \epsilon_1, \; \epsilon_2, \dots

  7. Large Countable Ordinals (Part 3) | Azimuth says:
    7 July, 2016 at 1:00 am

    Last time we saw how to name a lot of countable ordinals using an idea developed by Veblen. In fact, all ordinals less than the ‘Feferman–Schütte ordinal’. This time I’ll explain Veblen’s idea more precisely and go even further, still using Veblen’s work.

    Reply
  8. Non-standard Models of Arithmetic 8 | Diagonal Argument says:
    17 May, 2019 at 8:53 pm

    Getting back to the Paris-Harrington theorem: the original proof used non-standard models of PA. (Kanamori and McAloon soon simplified it; the treatment in the recent book by Katz and Reimann is particularly easy to follow.) That’s the one I want to look at here.

    But since you had such fun with ordinals here (and here and here), I better add that Ketonen and Solovay later gave a proof based on the ε0 stuff and the hierarchy of fast-growing functions. (The variation due to Loebl and Nešetřil is nice and short.) We should talk about this sometime! I wish I understood all the connections better. (Stillwell’s Roads to Infinity offers a nice entry point, though he does like to gloss over details.)

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

This site uses Akismet to reduce spam. Learn how your comment data is processed.