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

Ordinals say how big ‘well-ordered’ sets are. A set is well-ordered if it comes with a relation ≤ obeying the usual rules:

• **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:

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.

### Infinite ordinals

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

What comes after this? Well, it turns out there’s a well-ordered set

containing the finite ordinals together with

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 *preserves the ordering*. This is easy to see, since

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

Then comes

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

is an infinite list of things… *and then one more thing that comes after all those!*. But

With ordinals, it’s not just about quantity: the order matters!

### ω+ω and beyond

Okay, so we’ve seen these ordinals:

What next?

Well, the ordinal after all these is called

It would be fun to have a book with

It’s worth noting that

while

where we add

so

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

In fact, I bet now you’re ready to skip all the way to "omega times omega", or

Suppose you had an encyclopedia with

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

### ω^{ω}

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

Let’s try to we imagine this! First, imagine a book with *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

On his page, if you click on any of the labels for an initial portion of an ordinal, like

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

Well, then comes

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

and then

and then

and eventually

and eventually

and then

and eventually

After a while we reach

and then

and then

and then

and then

and then

and eventually

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

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

where

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

So, when we hit *exists* for ordinals *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

all the exponents *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

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

For more, see:

• Wikipedia, Cantor normal form.