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.

Blake Stacey, OMYou’re missing a couple closing semicolons on your HTML entities — I see two instances of “&omega”.

Anonymoushttp://bramcohen.livejournal.com/39662.html

Chad GroftMinor point with the second paragraph — what happened to the limit ordinals?

M“Perelman in a Subway”

http://englishrussia.com/?p=998#more-998

Well. Look at that. There he is.

…What a bum.

DougWhat do you mean by “non-continuous in its left argument” here?

Ørjan JohansenFor increasing sequences (or in general topology, nets) of ordinals, the limit is the smallest upper bound. (I guess there is a definition if they are not increasing as well, to make this a proper topology.)

Observe that ω is the limit of the finite ordinals 1,2,3,… and n+ω = ω for all finite n, but ω+ω is different from ω, so you cannot take limits on the left side, so it is non-continuous in the topological sense.

Ørjan JohansenI realized that may be ambiguous, there should be a semicolon after …

Michael WelfordActually, there are versions of subtraction and division for ordinals.

Given ordinals alpha and beta, with beta greater than alpha, there exists a unique ordinal delta with alpha + delta = beta. It’s true that there is no ordinal omega – 1, if we interpret that to mean an ordinal with successor omega. But there is an ordinal that when added to 1 gives omega, namely omega itself.

There is also a kind of division with remainder and even a version of Euclids algorithm to find a greatest common divisor.