Ordinals

“What’s the biggest number?” I might ask a clever schoolchild. They ponder for a moment, then might shout their answer, loud and wild. “Infinity,” escapes their mouth, an answer quite unbeatable. Since, after all, with finite numbers, that one is unmeetable. And yet, I smirk; infinity’s the answer I’d been hoping for. But now, I have a planned response; they’ve opened up the perfect door. “Ah yes, but have you thought about infinity plus one?” I ask. “That’s the same!” they then exclaim “Now in my genius you must bask!” Dear reader, in a sense they’re right. “Infinity plus one” is still infinity. But read on, for if you continue then we will explore a sense in which these values are, perhaps, not quite the same. Just trust me – I assure you I am better at math exposition than finishing poems satisfyingly.

To this hypothetical child’s credit, “infinity+1” does seem like it should just be infinity. After all, if you have infinitely many things, and then you add one to it, it’s still infinitely many things. ∞+1=∞. Moreover, even though we’re about to explore how infinity+1 is distinct from infinity, it’s not necessarily “bigger” as such. It’s more accurate to say it “comes after” infinity. Let’s dive in.

First, let’s talk about putting things in order. For finitely many objects, this is pretty easy. There’s a first thing, a second thing, maybe a third and fourth thing, and on and on until the last thing. In fact, if you have n objects for any fixed value of n, in a sense, there’s only one way to put them in order. Obviously (A,B,C) is different from (B,C,A), but they have the same “shape,” so to speak. There’s a first number, a second one, and a third one. Changing which letters go into which spots doesn’t change the “way” they’re ordered, so to speak. For infinite sets though it gets a lot wackier.

The natural numbers ℕ (for those unfamiliar, those are nonnegative integers) are easy enough. You start with 0 (not 1; fight me), then have 1, 2, 3, and so on forever. For this reason, herein I’m going to frequently refer to the 0^th element of a list rather than the 1^st to denote the initial one. This is totally reasonable, and it’s probably the most natural way to make an infinite list.

But then consider the integers ℤ, positive and negative whole numbers. You in some sense have a 0^th number, a 1^st, a 2^nd, and so on (respectively 0, 1, 2) as normal. But then there’s also a -1^st, a -2^nd, -3^rd, going in the reverse direction. It’s an infamous result that the naturals and integers are equinumerous – that is, they have the “same number” of elements. Some infinities are bigger than other infinities, but these two infinities are the same size. Yet, these two orderings are fundamentally different. One has a true 0^th element, with nothing coming before it, and the other doesn’t.

The rational numbers ℚ, that is to say the fractions, are even weirder. There, between any two distinct numbers, there are infinitely many more numbers between them. This is obviously very different to the relatively discrete case of both orderings of whole numbers, but the infinity of the rational numbers is still the same as the infinity of the others.

Hopefully by now I’ve convinced you that putting infinitely many things in order can get kind of weird. But here I am to tell you that it gets even weirder.

We’re going to limit our scope to well-ordered sets, which are a particularly nice kind of ordered set. Specifically, an ordered set is considered well-ordered if every (nonempty) subset of elements has a minimum element. ℕ is well-ordered for example – say you have a set of natural numbers. If it contains 0, then that’s the minimum element. If it doesn’t contain 0 but does contain 1, then 1 is the minimum. If it doesn’t contain 0 or 1 but does contain 2, then that’s the minimum. You can keep going on and on like this, if your set is nonempty, then it contains some element of ℕ, and the first one you find when going up like this is the minimum.

By contrast, ℤ and ℚ are not well-ordered. There is no smallest integer since you can always subtract 1, so ℤ has no minimum. ℚ is even less well-ordered; the set of all positive rational numbers has a lower bound (namely 0) but there is no minimum number. Anything you think is the minimum, you can simply divide by 2.

Any finite ordered set is well-ordered by a relatively simple argument. Recall from earlier that a finite order always has a 0^th, 1^st, 2^nd, and however many other elements, now consider a subset of this finite ordered set. Just like with ℕ, if it contains the 0^th then that’s the minimum. If not the 0^th but the 1^st, then that’s the minimum, and so on and so forth.

As a last bit of bookkeeping, I should define exactly what we’re talking about: ordinals. Basically, an ordinal is a way to well-order a set of objects, up to relabeling them. Remember earlier when I said [A, B, C] was basically the same as [B, C, A]. The order of the specific letters changed, but the shape of their order is the same. These two ordered sets therefore have the same ordinal, which is 3.

Every finite number corresponds to exactly one ordinal. To distinguish them, I’ll leave numbers as usual and put ordinals in bold font. Like: the ordinal that corresponds to ordering 3 elements is 3. As such we have 0, the unique way to put nothing in order. 1, the unique way to put 1 thing in order, 2 is the unique way to order two things, 3 for 3 things, and so on. I’ll also denote ordered sets in [square brackets] as I have been previously.

Given an ordinal, we can get the “next” one just by putting an element on the end. Go from 0 to 1 by adding an element – from [] to [A]. Then we go to 2 by adding another; [A, B], then to 3 with [A, B, C]. When representing ordinals like this, we often use the ordinal itself as the next element. So 0 is represented by [] since there’s nothing to order. But then when jumping to 1, the element we add is 0 itself; 1 is represented by [0]. Then 2 is represented by [0, 1], 3 by [0, 1, 2], 4 by [0, 1, 2, 3], and so on. In general, an ordinal is represented simply by the set of all previous ordinals. This isn’t strictly what they are a priori, but it’s a very useful way to represent them. Taking this to the extreme, we end up with [0, 1, 2, 3, 4, …]; which looks like ℕ. There’s no end to this set, so there’s no way to add itself to the end, right?

Wrong. There’s no element at the end, but we can still add it “to the end” and get [0, 1, 2, 3, 4, …, ℕ]. That last element doesn’t come immediately after anything, but it’s still at the end, after every finite number. Just as “infinity” is bigger than every finite number, we’ve decided that ℕ is at the “end” of all the natural numbers. When we’re considering it as an ordinal though, we usually use the symbol ω, a lowercase omega, the last letter of the Greek alphabet. We have ω = [0, 1, 2, 3, 4, …], and then our new ordinal is represented by [0, 1, 2, 3, 4, …, ω]. What should we call it? Well, it comes after ω, so a natural choice I think is ω+1.

Can we keep going though? Of course we can. Now that we’ve found ω+1, we can construct [0, 1, 2, 3, 4, …, ω, ω+1] which can only reasonably be called ω+2, and then ω+3, ω+4, and so on forever. Indeed, what’s stopping us from doing [0, 1, 2, 3, 4, …, ω, ω+1, ω+2, ω+3, ω+4, …] what would we call that? Well that’s ω+ω, or ω×2.

Before we move on, let’s take a minute to think about what ω×2 could look like in practice. Imagine setting the volume on a TV. You have the kind of TV that only exists in a math problem, and the volume can be set to any natural number, no matter how high, but to keep it from blowing out everyone’s ears when it’s set to 16 trillion, the manufacturer has set the natural volume of the TV so quiet that no matter how it’s set, you can barely hear it. In order to hear the audio then, you want to set the volume as high as possible. Setting it to 100 is better than setting it to 10, but setting it to 1,000 would be better still, since it’s of course slightly louder. But even more important than that, you need to set the volume to an even number. Having the volume at 7 is just deeply unsatisfying – 6 or 8 would be much better, I’m sure you’d agree.

With these constraints in mind, the worst volume setting is obviously 1. 2 is better than 1, and indeed better than 3 since it’s even. But 3 is better than 1 since it’s greater. 4 is the best so far, then 5 is worse than 4 or 2 since it’s odd, but still better than 3. 0 even would be better than 1 or 3, since if you can’t hear it anyway you might as well have it set to an even number. If you list everything out, you’ll find the order goes [1, 3, 5, 7, 9, …, 0, 2, 4, 6, 8, …]. The odd numbers are ordered like ω, as are the even numbers, but all the evens come after all the odds. So the preferences of volume settings is ordered like ω×2.

But then we can keep going. ω×3 is the shape of 3 copies of ω one after the other – say you want to set the volume to a multiple of 10, but failing that an odd multiple of 5 will do, and after that you don’t care but you still want to set it as high as possible. You get something like [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, … 5, 15, 25, 35, 45, … 10, 20, 30, 40, …] which you can see has the shape of 3 copies of ω. Then ω×4, ω×5, and so on and so forth.

But we can keep going. Say we order all the ω×n+m for natural numbers n and m, and stick that in an ordered set. We’d get something like [1, 2, 3, … ω, ω+1, ω+2, … ω×2, ω×2+1, … ω×3, … ω×4, …]. What’s that? Well, it comes after everything like ω×n, for all finite n, and what’s the thing that comes after all the finite ordinals? Why, it’s ω, so I suppose this is ω×ω, or ω². You can think of this as taking ω, which recall is represented by [0, 1, 2, 3, …], and replacing every finite ordinal with a copy of ω. If you then replace every element in a representation of ω² with a copy of ω, you get ω³. Continuing on, you can get higher and higher powers of ω, and if you put all of those in order, you end up with ω^ω.

It’s possible, but a little too finicky for this article, to define exponentiation for ordinals even further than this. In so doing, you can define things like

And, as before, you can collect all finite towers of ω into a set, put them in order, and slap a name on it. Conventionally, this is called ε₀, ε is the Greek letter epsilon. The subscript 0 is an indication that there are bigger ε’s out there, but they’re even harder to define and I’m not going to go into them.

The details of ordinals are hard, and also not super important, which is why I glossed over the construction after ω^ω. There are too many ordinals to describe. Indeed, too many to even fit in a set. If you imagine any set of ordinals, you can always define one that comes after them, just like how we described ω+1 or ω² or any of the others. So any “set of all ordinals” would need to contain itself, which is impossible.

And to illustrate just how little of the world of ordinals we’ve seen, consider this. Remember earlier, when I said that ℕ, ℤ, and ℚ were all the “same size” of infinity. This is the smallest possible infinite size, and is commonly known as “countable” infinity. Most infinities are uncountable, which is just to say “bigger than countable,” and likewise most ordinals are uncountable. But every ordinal that’s come up in this article, be it ω, or ω×2, or ω², or even ω^ω or ε₀ are all countable. There are countable ordinals that are bigger than we can even describe explicitly well before we even get to the uncountable ones.

Infinity is truly bigger than we can even imagine, and once we start messing around with the shapes it can take, it gets bigger still. And yet we can still do math to it, to tackle beasts beyond our comprehension with a few little Greek symbols and some clever reasoning. Isn’t that neat?

I want us now to think again about the poem at the start. Return attention to that child; infinity does grasp their heart. When I proposed infinity plus one, they surely took offense. They could not see within their mind a method for that to make sense. But now, dear reader, be assured that you can see the truth within this subtle concept, even though it will lead others’ heads to spin. For having read this article, you’re better set to wonder, nay, explore the infinite world of math. No time is better than today.