Last time we saw why it’s devilishly hard to give names to large countable ordinals.
An obvious strategy is to make up a function from ordinals to ordinals that grows really fast, so that is a lot bigger than the ordinal indexing it. This is indeed a good idea. But something funny tends to happen! Eventually catches up with In other words, you eventually hit a solution of
This is called a fixed point of At this point, there’s no way to use as a name for unless you already have a name for So, your scheme fizzles out!
For example, we started by looking at powers of the smallest infinite ordinal. But eventually we ran into ordinals that obey
There’s an obvious work-around: we make up a new name for ordinals that obey
We call them epsilon numbers. In our usual nerdy way we start counting at zero, so we call the smallest solution of this equation and the next one and so on.
But eventually we run into ordinals that are fixed points of the function meaning that
There’s an obvious work-around: we make up a new name for ordinals that obey
But by now you can guess that this problem will keep happening, so we’d better get systematic about making up new names! We should let
and let be the th fixed point of
Oswald Veblen, a mathematician at Princeton, came up with this idea around 1908, based on some thoughts of G. H. Hardy:
• Oswald Veblen, Continuous increasing functions of finite and transfinite ordinals, Trans. Amer. Math. Soc. 9 (1908), 280–292.
He figured out how to define even when the index is infinite.
Last time we saw how to name a lot of countable ordinals using this idea: in fact, all ordinals less than the ‘Feferman–Schütte ordinal’. This time I want go further, still using Veblen’s work.
First, however, I feel an urge to explain things a bit more precisely.
Veblen’s fixed point theorem
There are three kinds of ordinals. The first is a successor ordinal, which is one more than some other ordinal. So, we say is a successor ordinal if
for some The second is 0, which is not a successor ordinal. And the third is a limit ordinal, which is neither 0 nor a successor ordinal. The smallest example is
Every limit ordinal is the ‘limit’ of ordinals less than it. What does that mean, exactly? Remember, each ordinal is a set: the set of all smaller ordinals. We can define the limit of a set of ordinals to be the union of that set. Alternatively, it’s the smallest ordinal that’s greater than or equal to every ordinal in that set.
Now for Veblen’s key idea:
Veblen’s Fixed Point Theorem. Suppose a function from ordinals to ordinals is:
• strictly increasing: if then
• continuous: if is a limit ordinal, is the limit of the ordinals where
Then must have a fixed point.
Why? For starters, we always have this fact:
After all, if this weren’t true, there’d be a smallest with the property that since every nonempty set of ordinals has a smallest element. But since is strictly increasing,
so would be an even smaller ordinal with this property. Contradiction!
Using this fact repeatedly, we get
Let be the limit of the ordinals
Then by continuity, is the limit of the sequence
So equals Voilà! A fixed point!
This construction gives the smallest fixed point of . There are infinitely many more, since we can start not with but with and repeat the same argument, etc. Indeed if we try to list these fixed points, we find there is one for each ordinal.
So, we can make up a new function that lists these fixed points. Just to be cute, people call this the derivative of so that is the th fixed point of Beware: while the derivative of a polynomial grows more slowly than the original polynomial, the derivative of a continuous increasing function from ordinals to ordinals generally grows more quickly than It doesn’t really act like a derivative; people just call it that.
Veblen proved another nice theorem:
Theorem. If is a continuous and strictly increasing function from ordinals to ordinals, so is
So, we can take the derivative repeatedly! This is the key to the Veblen hierarchy.
If you want to read more about this, it helps to know that a function from ordinals to ordinals that’s continuous and strictly increasing is called normal. ‘Normal’ is an adjective that mathematicians use when they haven’t had enough coffee in the morning and aren’t feeling creative—it means a thousand different things. In this case, a better term would be ‘differentiable’.
Armed with that buzzword, you can try this:
• Wikipedia, Fixed-point lemma for normal functions.
Okay, enough theory. On to larger ordinals!
The Feferman–Schütte barrier
First let’s summarize how far we got last time, and why we got stuck. We inductively defined the th ordinal of the th kind by:
meaning that is the th fixed point of
This handles the cases where is zero or a successor ordinal. When is a limit ordinal we let be the th ordinal that’s a fixed point of all the functions for
Last time I explained how these functions give a nice notation for ordinals less than the Feferman–Schütte ordinal, which is also called This ordinal is the smallest solution of
So it’s a fixed point, but of a new kind, because now the appears as a subscript of the function.
We can get our hands on the Feferman–Schütte ordinal by taking the limit of the ordinals
(If you’re wondering why we use the number 0 here, instead of some other ordinal, I believe the answer is: it doesn’t really matter, we would get the same result if we used any ordinal less than the Feferman–Schütte ordinal.)
The ‘Feferman–Schütte barrier’ is the combination of these two facts:
• On the one hand, every ordinal less than can be written as a finite sum of guys where and are even smaller than Using this fact repeatedly, we can get a finite expression for any ordinal less than the Feferman–Schütte ordinal in terms of the function, addition, and the ordinal 0.
• On the other hand, if and are less than then is less than So we can’t use the function to name the Feferman–Schütte ordinal in terms of smaller ordinals.
But now let’s break the Feferman–Schütte barrier and reach some bigger countable ordinas!
The Γ function
The function is strictly increasing and continuous as a function of So, using Veblen’s theorems, we can define to be the th solution of
We can then define a bunch of enormous countable ordinals:
and still bigger ones:
and even bigger ones:
and even bigger ones:
But since is just we can reach much bigger countable ordinals with the help of the function:
and we can do vastly better using the function itself:
The limit of all these is the smallest solution of
As usual, this ordinal is still countable, but there’s no way to express it in terms of the function and smaller ordinals. So we are stuck again.
In short: we got past the Feferman–Schütte barrier by introducing a name for the th solution of We called it This made us happy for about two minutes…
…. but then we ran into another barrier of the same kind.
So what we really need is a more general notation: one that gets us over not just this particular bump in the road, but all bumps of this kind! We don’t want to keep randomly choosing goofy new letters like We need something systematic.
The multi-variable Veblen hierarchy
We were actually doing pretty well with the function. It was nice and systematic. It just wasn’t powerful enough. But if you’re trying to keep track of how far you’re driving on a really long trip, you want an odometer with more digits. So, let’s try that.
In other words, let’s generalize the function to allow more subscripts. Let’s rename and call it . The fact that we’re using two subscripts says that we’re going beyond the old functions with just one subscript. The subscripts 1 and 0 should remind you of what happens when you drive more than 9 miles: if your odometer has two digits, it’ll say you’re on mile 10.
Now we proceed as before: we make up new functions, each of which enumerates the fixed points of the previous one:
and so on. In general, we let
and when is a limit ordinal, we let
Are you confused?
How could you possibly be confused???
Okay, maybe an example will help. In the last section, our notation fizzled out when we took the limit of these ordinals:
The limit of these is the smallest solution of But now we’re writing so this limit is the smallest fixed point of So, it’s
We can now ride happily into the sunset, defining for all ordinals Of course, this will never give us a notation for ordinals with
But we don’t let that stop us! This is where the new extra subscript really comes in handy. We now define to be the th solution of
Then we drive on as before. We let
and when is a limit ordinal, we say
I hope you get the idea. Keep doing this!
We can inductively define for all and Of course, these functions will never give a notation for solutions of
To describe these, we need a function with one more subscript! So let be the th solution of
We can then proceed on and on and on, adding extra subscripts as needed.
This is called the multi-variable Veblen hierarchy.
To help you understand the multi-variable Veblen hierarchy, I’ll use it to describe lots of ordinals. Some are old friends. Starting with finite ones, we have:
and so on, so we don’t need separate names for natural numbers… but I’ll use them just to save space.
and so on, so we don’t need separate names for and its powers, but I’ll use them just to save space.
where I should remind you that is a name for the th solution of
• is the limit of
• is called the Ackermann ordinal.
Apparently Wilhelm Ackermann, the logician who invented a very fast-growing function called Ackermann’s function, had a system for naming ordinals that fizzled out at this ordinal.
The small Veblen ordinal
There are obviously lots more ordinals that can be described using the multi-variable Veblen hierarchy, but I don’t have anything interesting to say about them. And you’re probably more interested in this question: what’s next?
The limit of these ordinals
is called the small Veblen ordinal. Yet again, it’s a countable ordinal. It’s the smallest ordinal that cannot be named in terms of smaller ordinals using the multi-variable Veblen hierarchy…. at least, not the version I described. And here’s a nice fact:
Theorem. Every ordinal less than the small Veblen ordinal can be written as a finite expression in terms of the multi-variable function, addition, and 0.
is equal to
On the one hand, this notation is quite tiresome to read. On the other hand, it’s amazing that it gets us so far!
Furthermore, if you stare at expressions like the above one for a while, and think about them abstractly, they should start looking like trees. So you should find it easy to believe that ordinals less than the small Veblen ordinal correspond to trees, perhaps labelled in some way.
Indeed, this paper describes a correspondence of this sort:
• Herman Ruge Jervell, Finite trees as ordinals, in New Computational Paradigms, Lecture Notes in Computer Science 3526, Springer, Berlin, 2005, pp. 211–220.
However, I don’t think his idea is quite same as what you’d come up with by staring at expressions like
Beyond the small Veblen ordinal
We’re not quite done yet. The modifier ‘small’ in the term ‘small Veblen ordinal’ should make you suspect that there’s more in Veblen’s paper. And indeed there is!
Veblen actually extended his multi-variable function to the case where there are infinitely many variables. He requires that all but finitely many of these variables equal zero, to keep things under control. Using this, one can set up a notation for even bigger countable ordinals! This notation works for all ordinals less than the large Veblen ordinal.
We don’t need to stop here. The large Veblen ordinal is just the first of a new series of even larger countable ordinals!
These can again be defined as fixed points. Yes: it’s déjà vu all over again. But around here, people usually switch to a new method for naming these fixed points, called ‘ordinal collapsing functions’. One interesting thing about this notation is that it makes use of uncountable ordinal. The first uncountable ordinal is called and it dwarfs all those we’ve seen here.
We can use the ordinal collapsing function to name many of our favorite countable ordinals, and more:
• is the smallest solution of
• is the Feferman–Schütte ordinal.
• is the Ackermann ordinal.
• is the small Veblen ordinal.
• is the large Veblen ordinal.
• is called the Bachmann–Howard ordinal. This is the limit of the ordinals
I won’t explain this now. Maybe later! But not tonight. As Bilbo Baggins said:
The Road goes ever on and on
Out from the door where it began.
Now far ahead the Road has gone,
Let others follow it who can!
Let them a journey new begin,
But I at last with weary feet
Will turn towards the lighted inn,
My evening-rest and sleep to meet.
But perhaps you’re impatient and want to begin a new journey now!
The people who study notations for very large countable ordinals tend to work on proof theory, because these ordinals have nice applications to that branch of logic. For example, Peano arithmetic is powerful enough to work with ordinals up to but not including , so we call the proof-theoretic ordinal of Peano arithmetic. Stronger axiom systems have bigger proof-theoretic ordinals.
Unfortunately this makes it a bit hard to learn about large countable ordinals without learning, or at least bumping into, a lot of proof theory. And this subject, while interesting in principle, is quite tough. So it’s hard to find a readable introduction to large countable ordinals.
The bibliography of the Wikipedia article on large countable ordinals gives this half-hearted recommendation:
Wolfram Pohlers, Proof theory, Springer 1989 ISBN 0-387-51842-8 (for Veblen hierarchy and some impredicative ordinals). This is probably the most readable book on large countable ordinals (which is not saying much).
Unfortunately, Pohlers does not seem to give a detailed account of ordinal collapsing functions. If you want to read something fun that goes further than my posts so far, try this:
• Hilbert Levitz, Transfinite ordinals and their notations: for the uninitiated.
(Anyone whose first name is Hilbert must be born to do logic!)
This is both systematic and clear:
• Wikipedia, Ordinal collapsing functions.
And if you want to explore countable ordinals using a computer program, try this:
• Paul Budnik, Ordinal calculator and research tool.
Among other things, this calculator can add, multiply and exponentiate ordinals described using the multi-variable Veblen hierarchy—even the version with infinitely many variables!