What's a number? 3 - in an orderly manner

Why is infinity plus 1 bigger than 1 plus infinity? What about infinity times 2 and 2 times infinity? It all depends, on course, on what you mean by plus, times, and infinity.

Back to the beginning

In a previous blog post I discussed the natural numbers (by which I mean the non-negative integers, though some people exclude \(0\)). To recap briefly, we can describe by these means of how they behave, using the Peano axioms, and also give a concrete realization of them, namely the von Neumann numbers.
These von Neumann numbers are given by starting with the empty set \(\emptyset\), which is \(0\), then definining a successor function by saying that the successor of any number \(n\) is the set \(s(n)=n ; \{n\}\), and then collecting together everything you can make that way. Then \(1=s(0)=\{0\}, 2=s(1)=\{0,1\}\) and so on.
With this notion of a number, we can define the usual addition and multiplication; we also have an order, so \(m \leq n\) if there is some \(p\) such that \(n=m+p\).
I already looked at how to build on these by extending them in various ways to include negative numbers, rational numbers, and finally complete them with the irrational numbers to form \(\mathbb{R}\), the set of real numbers.
This time I want to go back to these natural numbers, and build on them in a different way: this time by taking the ordering on them, and seeing how we can enlarge our set of numbers in an interesting way using this idea.
But first, there's going to be a bit of a digression, in which we'll see some general ideas involving ordering.

(Well) ordered sets

We say that a set, \(S\) is ordered if there's a relationship \(\leq\) on it which has the properties

1. If \(a,b,c \in S\) then \(a \leq b\) and \(b \leq c\) implies \(a \leq c\)
2. If \(a,b \in S\) and \(a \leq b\) and \(b \leq a\) then \(a=b\)
3. If \(a,b\in S\) then \(a \leq b\) or \(b \leq a\) (or both)

So clearly \(\mathbb{N}\), the set of natural numbers, is ordered, with \(\leq\) being the usual less than or equal to.
The same is true for \(\mathbb{Q}\) and \(\mathbb{R}\), the sets of rational and real numbers.
It's natural (and sensible) to say that two sets \(A,B\) are the same size if they can be matched up so that each element of one set is matched to a different one of the other: such a matching is a bijective function \(f:A \to B\).
But with ordered sets we have another ingredient: we say that two ordered sets \(A\) and \(B\) are similar, written \(A \sim B\), if there is a bijective function \(f:A \to B\) which preserves the ordering, so for any \(a_1,a_2 \in A\), \(f(a_1) \leq f(a_2)\) is equivalent to \(a_1 \leq a_2\).
It's not hard to show that there's bijection between the natural numbers and the non-negative rationals. It's a bit harder to see that the two sets aren't similar, but if you notice that if you choose any positive rational number, there are infinitely many smaller ones, but there are only finitely many natural numbers smaller than any given natural number, then you can see it's pretty hopeless to try to find a similarity.
In fact, the natural numbers have another important property. In particular, they have the property that any set of natural numbers contains a smallest element. An ordered set with this property is called a well-ordered set
Neither the set of rational numbers nor the set of real numbers is well-ordered (with the usual ordering): the set of all rational or reals greater than \(0\) has no least element. So this is a bit special.
Well-ordered sets are pretty special: they behave a lot like numbers.
But we have to do a little bit or work here.
First, if \(A\) is a well-ordered set, and \(a \in A\), then \(i(a)\) is the set of all elements of \(A\) less than \((a)\), and is called the initial segment of \(a\). (It's common to use \(s(a)\) for the initial segment of \(a\), but I'm already using that for the successor.)
For example, in \(\mathbb{N}\), the intial segment of \(3\) is \(\{0,1,2\}\).
This is actually a bit of a mind-expander. In the von Neumann numbers, \(3\) is, by definition, \(\{0,1,2\}\), so \(i(3)=3\), and in general, for any \(n \in \mathbb{N}\), we have \(i(n)=n\). You might want to take a break and walk around the block, or do some pressups, or something, until that settles in. I know it took me a while to get used to the idea.
We think of two similar well-ordered sets as being ''really the same''; they are representations of the same ordinal number. (This is what we mean by ordinal number, but I may sometimes forget myself and talk about a particular ordered set as an ordinal number, rather than as a representation of on.)
For example, the sets of integers \(3=\{0,1,2\}\), \(\{1,2,3\}\) and \(\{2,4,7\}\) are all similar, and we can say that each represents the ordinal \(\pmb{3}\).
Now comes the miracle.
If \(A\) and \(B\) are well-ordered sets, then exactly one of the following is true:

1. \(A\) is similar to an initial segment of \(B\)
2. \(B\) is similar to an initial segment of \(A\)
3. \(A\) is similar to \(B\).

It then turns out that this notion is similar to all of or to an initial segment of can be thought of as \(\le\), and ordinal numbers are themselves well-ordered. (Though you have to be a little bit careful about this for rather technical reasons.)
Just as with the usual numbers, we say \(A \lt B\) if \(A \leq B\), and \(A \neq B\), which is saying that \(A\) is an initial segment of \(B\).
And now we can start to do something with this machinery. We'll think a bit about how these ordinals extend the von Neumann numbers.

The first infinite number, \(\omega\)

So first of all, every von Neumann number is a well-ordered set, so represents an ordinal. But (and this is the point) there are more. In particular, the set of all natural numbers is also well-ordered, and so represents an ordinal. We call this ordinal \(\omega\).
What can we say about \(\omega\)?
The first thing is, every von Neumann number is less than it, because every von Neumann number is an initial segment.
Second, it's the smallest ordinal which is bigger than all the von Neumann numbers. For suppose that \(\alpha\) is also an ordinal which is bigger than all the von Neumann numbers, and \(\alpha \leq \omega\). Then \(\alpha\) must be an initial segment of \(\omega\); but the initial segments of \(\omega\) are just the von Neumann numbers themselves and \(\omega\). If \(\alpha\) is a von Neumann number, then it is not bigger than all the von Neumann numbers. The only alternative is that \(\alpha=\omega\).
So we can see that \(\omega\) is the smallest infinite ordinal.
There are lots of different representations of \(\omega\): here are a few: \[ \begin{split} &\{1,2,3,\ldots\}\\ &\{1,2,3,4,\ldots\}\\ &\{1,3,5,7,\ldots\}\\ &\{0,2,4,6,\ldots\} \end{split} \] Each of these is similar to \(\mathbb{N}\), and so is a representative of \(\omega\).
Although \(\omega\) is not itself an von Neumann number, it is very like one. In fact, ordinals are sufficiently like von Neumann numbers that we can do a lot of the same stuff as we can with the natural numbers, and in particular we can do arithmetic.
Before going on to look at addition and multiplication in general, let's just think about the successor, i.e what we get when we add \(1\) to a number.
With the finite (von Neumann) numbers, we define \[ n+1 = s(n) = \{0,1,2,\ldots, n\} \] and there's nothing to stop is doing the same with \(\omega\): \[ s(\omega) = \omega+1 = \{0,1,2,3,\ldots,\omega\} \] and we have to note that in this ordered set, \(\omega\) has infinitely many predecessors, but no immediate predecessor.
And of course, we can do this as often as we like: \[ \omega+2 = \{0,1,2,3,\ldots,\omega, \omega+1\} \] We can even build up the entire collection \[ \{0,1,2,\ldots,\omega,\omega+1,\omega+2,\ldots\} \] which it seems sensible to think of as \(\omega+\omega\), which is the result of doubling \(\omega\).
This all suggests that we might be able to add and multiply ordinals, if we paid enough attention to how to generalise the procedure for for numbers. And we can (or I probably wouldn't have raised the issue). But we have to be careful: there are a few surprised in store.

Arithmetic with ordinals

Let's start off with

Addition

It would be nice to use the same definition as with the von Neumann numbers, but that (as it stands) relies on each number other than \(0\) have a predecessor, and we don't have that any more.
We have to generalise the idea somehow. There is more than one way to do this, and I'm just going to look at the one that I find easiest to understand.
So, if \(\alpha\) and \(\beta\) are ordinals, maybe finite, maybe note, then here's one way we can define their sum.
We take well-ordered sets \(A\) and \(B\) corresponding to \(\alpha\) and \(\beta\), and define their ordered union to be the ordered set \(A ; B\) which contains all the elements of \(A\) followed by all the elements of \(B\). This ordered set is (represents) \(\alpha+\beta\).
It's important to note here than when I write these out, it's the ordering given by the listing of the elements that matters, so \[ 3+4=\{0,1,2\} ; \{0,1,2,3\} = \{0,1,2,0,1,2,3\} \sim \{0,1,2,3,4,5,6\} = 7 \]
It's not hard to convince yourself that this gives the right answer when \(\alpha\) and \(\beta\) are ordinary finite numbers, so this does generalise the usual addition. There's the slight technicality that we should check that this ordered union produces a well-ordered set: but it does.
You can also see straight from the definition that if \(\alpha,\beta\) and \(\gamma\) are ordinals, then \[ (\alpha+\beta)+\gamma = \alpha+(\beta+\gamma) \] so addition is associative.
Now comes the first surprise: addition of ordinals is not in general commutative. We can see this in the simplest possible case, comparing \(1+\omega\) with \(\omega+1\).
In the first case, since \(1=\{0\}\), we have \[ 1+\omega = \{0,0,1,\ldots\} \sim \{0,1,\dots\} = \omega \] Where the first \(0\) in there comes from \(1\), and precedes the second one, which comes from \(\omega\) (and I'm being a little sloppy by thinking of a particular well-ordered set as the actual ordinal, rather than a representative for it).
On the other hand, \[ \omega+1 = \{0,1,2,\ldots,0\} \sim \{0,1,2,\ldots,\omega\} \] which is definitely not similar to \(\omega\). In fact, since \(\omega\) is an initial segment of this, we know that \(\omega \lt \omega+1\).
And from this definition, we see straight from the definition that \[ \omega+\omega = \{\omega,\omega\}=\{0,1,2,\ldots,0,1,2,\ldots\} \] in agreement with the guess up above.
So, we have a definition for the sum of two ordinals which agrees with what we know for finite ordinals, and still works for infinite ones. But, as often happens when we generalise a good notion, some of the properties are lost - in this case, commutativity.
So, what about multiplication? This can also be done.

Multiplication

As before, we have ordinals \(\alpha\) and \(\beta\), with corresponding well-ordered sets \(A\) and \(B\). This time, instead of an ordered union, we define an ordered Cartesian product.
We have \[ A \times B = \{(a,b) : a \in A, b \in B\} \] and we say that \((a_1,b_1) \lt (a_2,b_2)\) if

1. \(b_1 \lt b_2\), or
2. \(b_1=b_2\) and \(a_1 \lt a_2\)

This gives us a copy of \(A\) for each element of \(B\), and the copies are ordered by the ordering of the elements of \(B\).
As you might hope, multiplying by \(1\) leaves ordinals unchanged: if \(\alpha\) is any ordinal, then \[ 1 \times \alpha = \alpha \times 1 = \alpha. \]
As with addition, the multiplication of ordinals is associative, though it's a little harder to see than with addition.
But, also as with addition, commutativity is lost. And as before, it is the simplest example imaginable (well, imaginable to me) which shows us this.
First, we have \[ \begin{split} 2 \times \omega &= \{0,1\} \times \{0,1,2\ldots\} \\ &= \{(0,0),(1,0),(0,1),(1,1), \ldots\}\\ & \sim \{0,1,2,\ldots\}\\ &=\omega \end{split} \] But then \[ \begin{split} \omega \times 2 &= \{0,1,2,\ldots\} \times \{0,1\}\\ &= \{(0,0),(0,1),\ldots, (1,0),(1,1),\ldots\}\\ &\sim \{\omega,\omega\}\\ &=\omega+\omega \end{split} \] So again, we have lost commutativity.
The other property we might hope for is distributivity. Is this preserved? Well, yes and no.
If \(\alpha,\beta\) and \(\gamma\) are ordinals, then (pretty much straight from the definition) \[ \alpha \times (\beta+\gamma) = \alpha \times \beta + \alpha \times \gamma. \]
But on the other hand, \[ \omega = 2 \times \omega = (1+1) \times \omega = 1 \times \omega + 1 \times \omega \neq \omega \] so in general \[ (\alpha+\beta) \times \gamma \neq \alpha \times \gamma + \alpha \times \beta \] So the ordinals have an arithmetic that extends the arithmetic of finite numbers, but we do have to be a bit more careful.

Is there more?

There's more.
For example, you can define a notion of exponentiation, and you can build immense towers of ordinal numbers, each larger than everything that comes before it. There is an inductive principle, called the principle of transfinite induction, which gives a powerful tool for proving theorems involving ordinal numbers.
The behaviour of these objects is rich and fascination. For example, one of my favourite results is that if \(\alpha\) is any ordinal, then any sequence of (strictly) decreasing ordinals starting at \(\alpha\) must reach \(0\) after finitely many terms.
But this has already been more than long enough.
A fairly technical presentation is given by the wiki page. If that's not to your taste, then Rudy Rucker (@rudytheelder) has a novel, White Light, exploring aspects of infinity.