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.

Tags

More like this

With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite ordinals using exponentiation. Exponentiation is defined in terms of repeated multiplication, but it allows us to represent numbers that we can't express in terms of any…
I've talked about the idea of the size of a set; and I've talked about the well-ordering theorem, that there's a well-ordering (or total ordering) definable for any set, including infinite ones. That leaves a fairly obvious gap: we know how big a set, even an infinite one is; we know that the…
This is a short post, in which I attempt to cover up for the fact that I forgot to include some important stuff in my last post. As I said in the last post, the cardinal numbers are an extension of the natural numbers, which are used for measuring the size of sets. The extended part is the…
Even though this post seems to be shifting back to axiomatic set theory, don't go thinking that we're done with type theory yet. Type theory will make its triumphant return before too long. But before that, I want to take a bit of time to go through some basic constructions using set theory. We'…

Minor point with the second paragraph -- what happened to the limit ordinals?

By Chad Groft (not verified) on 13 Jun 2007 #permalink

What do you mean by "non-continuous in its left argument" here?

What do you mean by "non-continuous in its left argument" here?

For 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.

By Ãrjan Johansen (not verified) on 16 Jun 2007 #permalink

I realized that may be ambiguous, there should be a semicolon after ...

By Ãrjan Johansen (not verified) on 16 Jun 2007 #permalink

Actually, 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.

By Michael Welford (not verified) on 19 Jun 2007 #permalink