The Unabashed Expanse of Ordinal numbers

Let me take you on a magical journey to explore one of the most fundamental and elegant, yet underappreciated, concept in mathematics – the ordinal numbers.

This cannot be done without a few words on what they are and and why we need them, but my focus will be on trying to instill a sense of awe at just how many of them there are – something that I have always found beautiful.

A language primer

The concepts of ordinal numbers – and their close cousins, the cardinal numbers – were not invented by mathematicians. They were originally a language construct, which we are all familiar with in our spoken language of choice, be it English, Hebrew or whatever.

A cardinal numeral is a way to express how many things there are. “One”, “two”, “three”, “four”, “fourty-two”, “seventy-eight hundred and twenty-five” are all cardinal numerals.

An ordinal numeral describes the position of something in a list of ordered items. “First”, “second”, “third” and “fourth” are ordinal numerals.

Back to math

In mathematics, cardinal numbers are basically the same as their natural language counterpart – they describe the size of a set, how many elements there are. 0, 1, 2, 3, etc. – known as “natural numbers” or “non-negative integers” – are cardinal numbers. Where this gets interesting – and where they truly diverge from the linguistic concept – is with infinite sets. Their size is measured with infinite cardinal numbers, which have names such as $\aleph_0$ or $\beth_1$ .

Ordinal numbers are silghtly more complicated. They represent the different fundamental ways in which the elements of a set can be ordered, known also as “order types”. I’ll show you what I mean, but I should warn you that they are not terribly interesting in the realm of finite sets. For every given finite size for a set, there is exactly one fundamental way to order it – so each finite cardinal number corresonds to exactly one finite ordinal number. Because finite cardinal and ordinal numbers are basically the same, it may not be clear why we even introduced ordinal numbers as a new concept. This should become clearer when we explore infinite numbers.

So let’s take a set with, say, 4 elements – $\{A,B,C,D\}$ . There are many ways to order it (24, to be exact, if you remember your combinatorics) – for example, $A<C<B<D$ , or $C<D<B<A$ , or $D<A<B<C$ . But all these orderings are fundamentally the same. They all follow the pattern – “One item, then another, then another, then another”. Different orderings have different items in each position, but they all follow the same basic structure. This structure is represented by the ordinal number 4 (so called because it is the only way to order sets of size 4).

Similarly, sets of size 2 can be ordered in one fundamental way – “One item, then another”. This way is denoted by the ordinal number 2. Likewise for 42 or 7825 – every cardinal number is essentially also an ordinal number.

To infinity and beyond!

Let’s shift gears and talk about infinite sets, such as the collection of all natural numbers, $\mathbb{N}=\{0,1,2,3,4,\ldots\}$ . The cardinality of this set is $\aleph_0$ , which is the smallest infinite cardinal number.

There are infinitely many ways to order this set – we’ll start with the usual ordering of numbers, $0<1<2<3<4<5<\cdots$ . The order type for this ordering can be described as “one item, then another, then another, and so on until infinity”. This order type is represented by the ordinal number called $\omega$ – we use a different notation than the cardinal number $\aleph_0$ because, as we’ll soon see, there are many order types which correspond to a set of size $\aleph_0$ .

Before we explore these other order types, let’s have a look at some different orderings with the same order type.

For example, we can shuffle things around a bit, and have $3<2<1<0<4<5<6<\cdots$ , where after 4 the numbers are ordered as usual. This is the same order type, because it can still be described as “one item, then another, then another, and so on until infinity”.

We can shuffle it even more and have something like $1<0<3<2<5<4<7<6<9<8<\cdots$ , where the pattern continues. Here, there is no point at which the usual ordering resumes – but still, the overall structure is the same as the usual ordering. So this particular ordering also belongs to the order type $\omega$ .

Now let’s do something more extreme. Let’s have an ordering where 0 is declared to be greater than any other number. So we have $1<2<3<4<5<\cdots<0$ . First we have an infinite sequence of numbers, and then, on the mountaintop above all others, we have 0.

The description we had earlier no longer applies. This ordering can be described as “one item, then another, then another, and so on until infinity, and then another item”. There is an element “at the end”, greater than all others, which is fundamentally different from the orderings we’ve seen before. This is a new order type – which we call $\omega+1$ .

What happens if we take an infinite sequence of numbers, and then tack two more items at the end? For example, $2<3<4<5<6<\cdots<0<1$ . This is yet another order type, $\omega+2$ .

You might be getting now where this is going – we also have $\omega+3$ , $\omega+4$ , $\omega+5$ and so on. For any natural number $n$ , we can have an infinite sequence of items, and then $n$ more items – the ordinal number which describes such an ordering is $\omega+n$ .

Revisiting addition

We’ve used the symbol + in the description of ordinal numbers like $\omega+2$ , but we haven’t quite explained what it means.

It’s not too hard, though. Given ordinal numbers $\alpha$ and $\beta$ , we define $\alpha+\beta$ as the order type we get if we take items ordered according to $\alpha$ , and follow them up with items ordered according to $\beta$ .

With finite numbers, this is exactly the addition we learned in first grade. For example, if 2 describes “one item, then another” and 3 describes “one item, then another, then another”, then 2+3 describes “one item, then another; then another, then another, then another”, which is 5.

So, given that $\omega$ represents “an infinite sequence of items”, it should now be clear why we call “an infinite sequence of items, then 2 more” $\omega+2$ .

Be warned though – unlike addition of finite numbers, addition of ordinal numbers in general is not commutative! The law we all know and love, $\alpha+\beta=\beta+\alpha$ , does not apply for infinite ordinal numbers.

To understand this, let’s consider – what is $1+\omega$ ? Per above, it is the order type “one item; then another, then another, the another, and so on, to infinity”. But that is exactly the same as “One item, then another, then another, and so on, to infinity”! An item followed by an infinite sequence, is itself an infinite sequence. So $1+\omega = \omega$ , while $\omega+1$ is a different thing altogether.

In fact, for any finite ordinal (aka natural number) $n$ , we have $n+\omega = \omega$ , while $\omega+n$ gives us a new ordinal number for each $n$ .

Even more ordinals

To recap the ordinals we’ve seen so far, we have $0,1,2,3,4,5,\ldots,\omega\ , \omega+1,\ \omega+2,\ \omega +3,\ \omega +4,\ \omega +5\ldots$ .

What comes after all of these? Why, it’s $\omega+\omega$ , of course. This is what we get when we have an infinite sequence, followed by another infinite sequence. For example, we can decide that all odd numbers are greater than all even numbers, leading to the ordering $0<2<4<6<8<\cdots<1<3<5<7<9<\cdots$ . This is the ordinal number $\omega+\omega$ , which for brevity we will also call $\omega\cdot2$ (more about multiplication later).

If we tack on another item after these two successive infinite sequences, we get $\omega\cdot2+1$ . Two items? $\omega\cdot2+2$ . If two infinite sequences are followed by 3 items, we have $\omega\cdot2+3$ . And then we have $\omega\cdot2+4,\ \omega\cdot2+5$ , and so on.

And if we have two infinite sequences, and then yet another infinite sequence? That’s $\omega\cdot2+\omega$ , which we call $\omega\cdot3$ – three infinite sequences in succession.

And then we have $\omega\cdot3+1,\ \omega\cdot3+2,\ \omega\cdot3+3,\ \omega\cdot3+4, \ldots,\ \omega\cdot4,\ \omega\cdot4+1,\ \omega\cdot4+2,\ \omega\cdot4+3, \ldots,\ \omega\cdot5,\ \omega\cdot5+1,\ \omega\cdot5+2, \ldots,\ \omega\cdot6, \ldots,\ \omega\cdot7,\ldots$

Go forth and multiply

Once again, we’ve alluded to multiplication of ordinals without really explaining what it is.

The best way to explain $\alpha\cdot\beta$ is – take the description of $\beta$ , but replace each item with an entire copy of $\alpha$ .

So if $\omega$ is “an infinite sequence”, and 2 is “one item, then another”, then $\omega\cdot2$ is “an infinite sequence, then another”, which matches our usage above.

Meanwhile, $2\cdot\omega$ is “two items, then two more items, then two more, and so on to infinity”. But this is just an infinite sequence in disguise, so $2\cdot\omega=\omega$ . Multiplication, too, is not commutative.

Don’t be square

Now that we are familiar with multiplication, we should have no problem with $\omega \cdot \omega$ , an ordinal number greater than any ordinal number of the form $\omega\cdot m+n$ (with $m$ and $n$ finite). This is “an infinite sequence, then another infinite sequence, then another infinite sequence, and so on, to infinity”.

We will also call $\omega \cdot \omega$ simply $\omega^2$ . Taking powers of ordinal numbers would probably be too complicated to explain in general, so let’s just have faith that this makes sense.

If we add just one more item at the end of this infinite sequence of infinite sequences, we get $\omega^2+1$ . And of course this is followed by $\omega^2+2$ , and then $\omega^2+3$ , and so on, all the way to $\omega^2+\omega$ . Further ahead we have ordinal numbers such as $\omega^2+\omega\cdot3+2$ and $\omega^2+\omega\cdot5+98$ . After all numbers of the form $\omega^2+\omega\cdot m+n$ are exhausted, we get to $\omega^2+\omega^2=\omega^2\cdot2$ .

And this just keeps going. Up ahead are numbers like $\omega^2\cdot2+60\omega+10$ , $\omega^2\cdot4+3$ and $\omega^2\cdot20+\omega\cdot8+916382$ . Eventully we reach $\omega^2\cdot\omega=\omega^3$ .

Ordinal polynomials

But it doesn’t end there, not by a long shot. Since we also have $\omega^3\cdot5+\omega^2\cdot10+20$ and $\omega^3\cdot13+\omega^2\cdot7+\omega\cdot19+2$ . We also have $\omega^4$ .

In fact, any polynomial in $\omega$ , with natural number coefficients, is a new ordinal number. This includes $\omega^6\cdot7+\omega^3\cdot8$ and $\omega^{20}\cdot4 + \omega^7\cdot5+\omega^2\cdot30$ .

But there is an ordinal number greater than all of these. The smallest ordinal greater than any of the polynomials is called $\omega^{\omega}$ .

And of course, we can add to that any of the polynomial ordinals, and get a new ordinal. Or add it to itself to get $\omega^{\omega}\cdot2$ . Or multiply it by $\omega$ to get $\omega^{\omega}\cdot\omega = \omega^{\omega+1}$ .

In fact, we can take $\omega$ to the power of any of the ordinals we’ve seen before. We have $\omega^{\omega\cdot2}$ and $\omega^{\omega^2\cdot3+\omega\cdot2+5}$ . And we can combine them in various ways, such as $\omega^{\omega^3}\cdot4 + \omega^{\omega^2\cdot5+\omega\cdot2}\cdot9+\omega^6\cdot8$ .

We even have $\omega^{\omega^{\omega}}$ . And $\omega^{\omega^{\omega^{\omega}}}$ . We can have a power tower as long as we want, leading to bigger and bigger ordinals.

And thus, we have covered the entirety of the ordinal numbers.

Hahaha nope.

Beyond arithmetic

All the ordinal numbers we’ve discussed so far can be obtained by starting with the natural numbers and the smallest infinite ordinal $\omega$ , and combining them with the arithmetic operations addition, multiplication and power.

But the thing with ordinal numbers is that there is always a bigger one. Even if we take all the ordinal numbers that can be constructed with arithmetic operations, there is an ordinal which is the smallest one greater than all of them. This ordinal is called $\epsilon_0$ .

And it keeps going – the next ordinal is $\epsilon_0+1$ , then $\epsilon_0+2$ . Eventually we get to $\epsilon_0+\omega$ , and $\epsilon_0+\omega^2$ , and $\epsilon_0+\omega^\omega$ . Eventually we have $\epsilon_0+\epsilon_0 = \epsilon_0\cdot2$ . And $\epsilon_0\cdot\omega$ . And $\epsilon_0\cdot\epsilon_0=\epsilon_0^2$ . And $\epsilon_0^{\omega}$ . And $\epsilon_0^{\epsilon_0}$ .

Basically, a whole new playground is opened to us, where we can combine $\omega$ and $\epsilon_0$ with arithmetic operations however we please, to find more and more ordinals.

But there are ordinal numbers greater than any we can express with arithmetic operaions on $\epsilon_0$ . The smallest such is called $\epsilon_1$ .

After introducing it, we can once again combine $\epsilon_1,\epsilon_0,\omega$ with arithmetic operations to create new numbers.

Greater than any of the numbers we can make this way, we have $\epsilon_2$ .

And we also have $\epsilon_3$ , and $\epsilon_4$ , and so on.

There is also a number greater than anything we can create with arithmetic combinations of $\omega, \epsilon_0, \epsilon_1, \epsilon_2, \epsilon_3,\ldots$ and any $\epsilon_n$ . This number is called $\epsilon_{\omega}$ .

We can use it in arithmetic operations too – and once we’re done, we’ll move up to $\epsilon_{\omega+1}$ . And then to $\epsilon_{\omega+2}$ .

In fact – every ordinal number can be used as a subscript to $\epsilon$ . So eventually we will have to use $\epsilon_{\omega\cdot2}$ , and $\epsilon_{\omega^2}$ , and $\epsilon_{\omega^{\omega}}$ , and even $\epsilon_{\epsilon_0}$ .

Which opens a whole new can of worms, since we also have $\epsilon_{\epsilon_{\epsilon_0}}$ and $\epsilon_{\epsilon_{\epsilon_{\epsilon_0}}}$ .

If you’ve been paying attention, you might correctly suspect that there is an ordinal greater than anything we can achieve by nesting subscripts of $\epsilon$ . But this leads us to more complicated things like the Veblen hierarchy and the Feferman–Schütte ordinal, so we should probably stop here.

But here’s the kicker – all of these ordinals are countable. That is, they describe ways to order a set of size $\aleph_0$ , such as the familiar $\mathbb{N}=\{0,1,2,3,4,\ldots\}$ . If we started out by saying that every finite cardinal number corresponds to exactly one ordinal number, then the cardinal number $\aleph_0$ corresponds to all of the ordinal numbers we’ve discussed so far.

Beyond all of these, we have bigger cardinal numbers such as $\aleph_1$ , each with their own plethora of ordinal numbers.

Final thoughts

I hope you’ve had as much fun as I did appreciating the elegance of the construction of the ordinal numbers and their internal logic. But they are not only beautiful – they also have a variety of serious and recreational uses.

My favorite is their ability to describe positions for chess played on an infinite board. If you’re familiar with chess puzzles where the goal is to “mate in 3”, you might appreciate that on an infinite board, you can have a “mate in $\omega+7$ “, or any other ordinal number.

They are also applied for solving games such as “the hydra game”, and a variety of foundational mathematics such as the Von Neumann Hierarchy, surreal numbers and derived sets.

If this was the first post you’ve read on ordinal numbers, I hope it interested you enough to seek a second resource to read. Then you’ll read your third, and your fourth, and so on. Afterwards, you’ll read about ordinal numbers for the $\omega$ th time, and then the $(\omega+1)$ th…

	Bitcoiners : Underst… on How I learned to stop worrying…
	"There is no po… on How I learned to stop worrying…
	UAHF: A contingency… on How I learned to stop worrying…
	Coinosphere on Between two extremes, but not…
	Liviu on How I learned to stop worrying…

Fiery Spinning Sword

A weblog of Bitcoin, math, and common sense. But mostly just Bitcoin.

The Unabashed Expanse of Ordinal numbers

A language primer

Back to math

To infinity and beyond!

Revisiting addition

Even more ordinals

Go forth and multiply

Don’t be square

Ordinal polynomials

Beyond arithmetic

Final thoughts

Leave a Reply Cancel reply

A language primer

Back to math

To infinity and beyond!

Revisiting addition

Even more ordinals

Go forth and multiply

Don’t be square

Ordinal polynomials

Beyond arithmetic

Final thoughts

Share this:

Like this:

Related

Leave a Reply Cancel reply