More on Ordinals: Ordinal Arithmetic (part 1)

I'll continue my explanation of the ordinal numbers, starting with a nifty trick. Yesterday, I said that the collection of all ordinals is *not* a set, but rather a proper class. There's another really neat way to show that.

Remember that we defined the ordinal 0 as the empty set, ∅, and every other ordinal a+1=a∪{a}. One obvious implication of this is that every ordinal b≤a is a member of a+1: in fact, a+1 is exactly the set of all ordinals ≤ a. So it's not just the case that every b≤a∈a+1, but every b≤a *is a subset* of a.

Imagine that it was possible to have a set S which is the set of all ordinals. Every ordinal number 0 is a subset of that set. So in its well-ordering, it's the sequence of all ordinals from 0 onwards: {0, 1, 2, ...}, with no end.

Here's the trick. An infinite set of all of the ordinals *is no different* than any other infinite set of ordinals. How is the set of all ordinals different from ω? They're both infinite sets of ordinals. The only difference is that the set of all ordinals has a different cardinality than ω: it's got the cardinality of the set of all ordinals. But since it's got the same structure, it *must* be an ordinal itself, which means it's a member of the set of all ordinals. But if it's a member of the set of all ordinals, then there must be an ordinal *larger* than it - because by definition, every ordinal has a successor. And that larger ordinal isn't a member of the set of all ordinals, or *it* would be the set of all ordinals. So we're in a recursive trap: the set of all ordinals can't be defined consistently, and so it's *not* a set.

I love that argument.

Ok, moving on... Ordinal arithmetic.

In ordinal arithmetic, we define addition, multiplication, and exponentiation. Subtraction and division are not well-defined for ordinals. For the purpose of clarity, from here on, I'll use greek letters for ordinals, and roman letters for sets.

Addition is simple. It's based on the idea of ordinals as the basis of an order of a set, where an order is a mapping from a collection of ordinal numbers to the members of the set. We call the ordinal α containing all of the ordinals mapped to members of a set A the *order-type* of A.

An ordinal expresses the idea of position in a well ordering - which leads us to the intuition behind the meaning of ordinal addition. Given two disjoint sets A (with order-type α) and B (with order-type β), their union A∪B also has a well-ordering, which has order type α+β. This makes sense, because α is the number of positions of elements in the well-ordering of A, and β is the number of positions of members of B; so the number of positions in the well ordering of A∪B should be α+β.

We can give a simple recursive definition of how it works:

* α+0=α
* α+(β+1)=(α+β)+1
* If β is a limit ordinal, then α+β is the limit ordinal of α+γ for all γ<β.

There is, of course, a catch. Ordinal arithmetic is *not* commutative: (2+ω)=ω - the result is the limit ordinal &omega. &omega+2=ω+1+1 - the successor ordinal of the successor ordinal of ω. In fact, it's even worse than just non-commutative; ordinal arithmetic is non-continuous in its left argument, but continous in its right. It's a thoroughly non-symmetric form of addition.

Multiplication works similarly - but instead of being the order type of a union of sets, it's the order type of a cartesian product of sets. Recursively:

* α×0=0
* α×1=α
* α×(β+1)=(α×β)+α.
* If β is a limit ordinal, then α×β is the limit ordinal of α×γ for all γ<β.

Like addition, ordinal multiplication is rather ugly. It's non-commutative, and non-continuous in its left argument. It's distributive in its left argument, but not its right. Seriously icky.

Tomorrow, we'll get to ordinal exponentiation, and the really cool thing that it produces: the Cantor normal form of ordinal numbers.