I love the infinite.
It may not exist in the physical world, but we can set up rules to think about it in consistent ways, and then it’s a helpful concept. The reason is that infinity is often easier to think about than very large finite numbers.
Finding rules to work with the infinite is one of the great triumphs of mathematics. Cantor’s realization that there are different sizes of infinity is truly wondrous—and by now, it’s part of the everyday bread and butter of mathematics.
Trying to create a notation for these different infinities is very challenging. It’s not a fair challenge, because there are more infinities than expressions we can write down in any given alphabet! But if we seek a notation for countable ordinals, the challenge becomes more fair.
It’s still incredibly frustrating. No matter what notation we use it fizzles out too soon… making us wish we’d invented a more general notation. But this process of ‘fizzling out’ is fascinating to me. There’s something profound about it. So, I would like to tell you about this.
Today I’ll start with a warmup. Cantor invented a notation for ordinals that works great for ordinals less than a certain ordinal called ε0. Next time I’ll go further, and bring in the ‘single-variable Veblen hierarchy’! This lets us describe all ordinals below a big guy called the ‘Feferman–Schütte ordinal’.
In the post after that I’ll bring in the ‘multi-variable Veblen hierarchy’, which gets us all the ordinals below the ‘small Veblen ordinal’. We’ll even touch on the ‘large Veblen ordinal’, which requires a version of the Veblen hierarchy with infinitely many variables. But all this is really just the beginning of a longer story. That’s how infinity works: the story never ends!
To describe countable ordinals beyond the large Veblen ordinal, most people switch to an entirely different set of ideas, called ‘ordinal collapsing functions’. I may tell you about those someday. Not soon, but someday. My interest in the infinite doesn’t seem to be waning. It’s a decadent hobby, but hey: some middle-aged men buy fancy red sports cars and drive them really fast. Studying notions of infinity is cooler, and it’s environmentally friendly.
I can even imagine writing a book about the infinite. Maybe these posts will become part of that book. But one step at a time…
Cardinals versus ordinals
Cantor invented two different kinds of infinities: cardinals and ordinals. Cardinals say how big sets are. Two sets can be put into 1-1 correspondence iff they have the same number of elements—where this kind of ‘number’ is a cardinal. You may have heard about cardinals like aleph-nought (the number of integers), 2 to power aleph-nought (the number of real numbers), and so on. You may have even heard rumors of much bigger cardinals, like ‘inaccessible cardinals’ or ‘super-huge cardinals’. All this is tremendously fun, and I recommend starting here:
• Frank R. Drake, Set Theory, an Introduction to Large Cardinals, North-Holland, 1974.
There are other books that go much further, but as a beginner, I found this to be the most fun.
But I don’t want to talk about cardinals! I want to talk about ordinals.
• Transitivity: if x ≤ y and y ≤ z then x ≤ z
• Reflexivity: x ≤ x
• Antisymmetry: if x ≤ y and y ≤ x then x = y
and one more rule: every nonempty subset has a smallest element!
For example, the empty set
is well-ordered in a trivial sort of way, and the corresponding ordinal is called
Similarly, any set with just one element, like this:
is well-ordered in a trivial sort of way, and the corresponding ordinal is called
Similarly, any set with two elements, like this:
becomes well-ordered as soon as we decree which element is bigger; the obvious choice is to say 0 < 1. The corresponding ordinal is called
Similarly, any set with three elements, like this:
becomes well-ordered as soon as we linearly order it; the obvious choice here is to say 0 < 1 < 2. The corresponding ordinal is called
Perhaps you're getting the pattern — you've probably seen these particular ordinals before, maybe sometime in grade school. They're called finite ordinals, or "natural numbers".
But there's a cute trick they probably didn't teach you then: we can define each ordinal to be the set of all ordinals less than it:
(since no ordinal is less than 0)
(since only 0 is less than 1)
(since 0 and 1 are less than 2)
(since 0, 1 and 2 are less than 3)
and so on. It’s nice because now each ordinal is a well-ordered set of the size that ordinal stands for. And, we can define one ordinal to be “less than or equal” to another precisely when its a subset of the other.
What comes after all the finite ordinals? Well, the set of all finite ordinals is itself well-ordered:
So, there’s an ordinal corresponding to this — and it’s the first infinite ordinal. It’s usually called pronounced ‘omega’. Using the cute trick I mentioned, we can actually define
What comes after this? Well, it turns out there’s a well-ordered set
containing the finite ordinals together with with the obvious notion of “less than”: is bigger than the rest. Corresponding to this set there’s an ordinal called
As usual, we can simply define
At this point you could be confused if you know about cardinals, so let me throw in a word of reassurance. The sets and have the same cardinality: they are both countable. In other words, you can find a 1-1 and onto function between these sets. But and are different as ordinals, since you can’t find a 1-1 and onto function between them that preserves the ordering. This is easy to see, since has a biggest element while does not.
Indeed, all the ordinals in this series of posts will be countable! So for the infinite ones, you can imagine that all I’m doing is taking your favorite countable set and well-ordering it in ever more sneaky ways.
Okay, so we got to What comes next? Well, not surprisingly, it’s
and so on. You get the idea.
I haven’t really defined ordinal addition in general. I’m trying to keep things fun, not like a textbook. But you can read about it here:
• Wikipedia, Ordinal arithmetic: addition.
The main surprise is that ordinal addition is not commutative. We’ve seen that since
is an infinite list of things… and then one more thing that comes after all those!. But because one thing followed by a list of infinitely many more is just a list of infinitely many things.
With ordinals, it’s not just about quantity: the order matters!
ω+ω and beyond
Okay, so we’ve seen these ordinals:
Well, the ordinal after all these is called People often call it “omega times 2” or for short. So,
It would be fun to have a book with pages, each page half as thick as the previous page. You can tell a nice long story with an -sized book. I think you can imagine this. And if you put one such book next to another, that’s a nice picture of
It’s worth noting that is not the same as We have
where we add of these terms. But
This is not a proof, because I haven’t given you the official definition of how to multiply ordinals. You can find it here:
• Wikipedia, Ordinal arithmetic: multiplication.
Using this you can prove that what I’m saying is true. Nonetheless, I hope you see why what I’m saying might make sense. Like ordinal addition, ordinal multiplication is not commutative! If you don’t like this, you should study cardinals instead.
What next? Well, then comes
and so on. But you probably have the hang of this already, so we can skip right ahead to
In fact, you’re probably ready to skip right ahead to and and so on.
In fact, I bet now you’re ready to skip all the way to “omega times omega”, or for short:
Suppose you had an encyclopedia with volumes, each one being a book with pages. If each book is twice as thin as one before, you’ll have pages — and it can still fit in one bookshelf! Here’s the idea:
What comes next? Well, we have
and so on, and after all these come
and so on — and eventually
and then a bunch more, and then
and then a bunch more, and then
and then a bunch more, and more, and eventually
You can probably imagine a bookcase containing encyclopedias, each with volumes, each with pages, for a total of pages. That’s
I’ve been skipping more and more steps to keep you from getting bored. I know you have plenty to do and can’t spend an infinite amount of time reading this, even if the subject is infinity.
So if you don’t mind me just mentioning some of the high points, there are guys like and and so on, and after all these comes
Let’s try to we imagine this! First, imagine a book with pages. Then imagine an encyclopedia of books like this, with volumes. Then imagine a bookcase containing encyclopedias like this. Then imagine a room containing bookcases like this. Then imagine a floor with library with rooms like this. Then imagine a library with floors like this. Then imagine a city with libraries like this. And so on, ad infinitum.
You have to be a bit careful here, or you’ll be imagining an uncountable number of pages. To name a particular page in this universe, you have to say something like this:
the 23rd page of the 107th book of the 20th encyclopedia in the 7th bookcase in 0th room on the 1000th floor of the 973rd library in the 6th city on the 0th continent on the 0th planet in the 0th solar system in the…
But it’s crucial that after some finite point you keep saying “the 0th”. Without that restriction, there would be uncountably many pages! This is just one of the rules for how ordinal exponentiation works. For the details, read:
• Wikipedia, Ordinal arithmetic: exponentiation.
As they say,
But for infinite exponents, the definition may not be obvious.
Here’s a picture of taken from David Madore’s wonderful interactive webpage:
On his page, if you click on any of the labels for an initial portion of an ordinal, like or here, the picture will expand to show that portion!
And here’s another picture, where each turn of the clock’s hand takes you to a higher power of :
Ordinals up to ε0
Okay, so we’ve reached Now what?
Well, then comes and so on, but I’m sure that’s boring by now. And then come ordinals like
leading up to
Then eventually come ordinals like
and so on, leading up to
This actually reminds me of something that happened driving across South Dakota one summer with a friend of mine. We were in college, so we had the summer off, so we drive across the country. We drove across South Dakota all the way from the eastern border to the west on Interstate 90.
This state is huge — about 600 kilometers across, and most of it is really flat, so the drive was really boring. We kept seeing signs for a bunch of tourist attractions on the western edge of the state, like the Badlands and Mt. Rushmore — a mountain that they carved to look like faces of presidents, just to give people some reason to keep driving.
Anyway, I’ll tell you the rest of the story later — I see some more ordinals coming up:
We’re really whizzing along now just to keep from getting bored — just like my friend and I did in South Dakota. You might fondly imagine that we had fun trading stories and jokes, like they do in road movies. But we were driving all the way from Princeton to my friend Chip’s cabin in California. By the time we got to South Dakota, we were all out of stories and jokes.
Hey, look! It’s
That was cool. Then comes
and so on.
Anyway, back to my story. For the first half of our half of our trip across the state, we kept seeing signs for something called the South Dakota Tractor Museum.
Oh, wait, here’s an interesting ordinal:
Let’s stop and take look:
That was cool. Okay, let’s keep driving. Here comes
After a while we reach
This is pretty boring; we’re already going infinitely fast, but we’re still just picking up speed, and it’ll take a while before we reach something interesting.
Anyway, we started getting really curious about this South Dakota Tractor Museum — it sounded sort of funny. It took 250 kilometers of driving before we passed it. We wouldn’t normally care about a tractor museum, but there was really nothing else to think about while we were driving. The only thing to see were fields of grain, and these signs, which kept building up the suspense, saying things like
ONLY 100 MILES TO THE SOUTH DAKOTA TRACTOR MUSEUM!
We’re zipping along really fast now:
What comes after all these?
At this point we need to stop for gas. Our notation for ordinals just ran out!
The ordinals don’t stop; it’s just our notation that fizzled out. The set of all ordinals listed up to now — including all the ones we zipped past — is a well-ordered set called
or “epsilon-nought”. This has the amazing property that
And it’s the smallest ordinal with this property! It looks like this:
It’s an amazing fact that every countable ordinal is isomorphic, as an well-ordered set, to some subset of the real line. David Madore took advantage of this to make his pictures.
Cantor normal form
I’ll tell you the rest of my road story later. For now let me conclude with a bit of math.
There’s a nice notation for all ordinals less than called ‘Cantor normal form’. We’ve been seeing lots of examples. Here is a typical ordinal in Cantor normal form:
The idea is that you write it out using just + and exponentials and 1 and
Here is the theorem that justifies Cantor normal form:
Theorem. Every ordinal can be uniquely written as
where is a natural number, are positive integers, and are ordinals.
It’s like writing ordinals in base
Note that every ordinal can be written this way! So why did I say that Cantor normal form is nice notation for ordinals less than ? Here’s the problem: the Cantor normal form of is
So, when we hit the exponents can be as big as the ordinal we’re trying to describe! So, while the Cantor normal form still exists for ordinals it doesn’t give a good notation for them unless we already have some notation for ordinals this big!
This is what I mean by a notation ‘fizzling out’. We’ll keep seeing this problem in the posts to come.
But for an ordinal less than something nice happens. In this case, when we write
all the exponents are less than So we can go ahead and write them in Cantor normal form, and so on… and because ordinals are well-ordered, this process ends after finitely many steps.
So, Cantor normal form gives a nice way to write any ordinal less than using finitely many symbols! If we abbreviate as and write multiplication by positive integers in terms of addition, we get expressions like this:
They look like trees. Even better, you can write a computer program that does ordinal arithmetic for ordinals of this form: you can add, multiply, and exponentiate them, and tell when one is less than another.
So, there’s really no reason to be scared of Remember, each ordinal is just the set of all smaller ordinals. So you can think of as the set of tree-shaped expressions like the one above, with a particular rule for saying when one is less than another. It’s a perfectly reasonable entity. For some real excitement, we’ll need to move on to larger ordinals. We’ll do that next time.
For more, see:
• Wikipedia, Cantor normal form.