Introduction to the transfinite ordinals

In this thread, I was asked this question by @tim wood:

Quoting tim wood

Attempt at a coherent question here. Maybe best to leave it simple. What is an infinite ordinal?

Rather than hijack the other thread, I'm top-posting this here in the Math section where it may serve as a general resource to interested readers.

It's not particularly short, but I do believe it's simple, in the sense that you can read a little here and there and perhaps get the gist.

Comments, questions, and criticisms gladly appreciated. In particular, please let me know if anything is unclear or needs more explanation.

Contents
* Ordinal numbers
* Well-orders
* Order-types
* Some more ordinals
* Uncountable ordinals
* The Alephs
* The von Neumann ordinals
* The class of all ordinals
* Ordinal arithmetic
* Odds and ends about countable ordinals


* Ordinal Numbers

Most people have heard of Cantor's great discovery of the cardinal numbers, the Alephs, a way of assigning a measure of quantity to infinite sets. Far fewer have heard of ordinals, which were Cantor's other great discovery; and which are, in the modern formulation, logically prior to cardinals. Ordinals describe order, analogously to how cardinals describe quantity.

Ordinals find applications in mathematical logic, proof theory, set theory, and theoretical computer science, as well as being fascinating objects of study in their own right.

This article is a general introduction to the basics of the transfinite ordinal numbers.


* Well-orders

An ordinal number is the order-type of a well-ordered set. What does that mean?

The core concept of ordinals is the idea of a well order. A well-order is an order relation on a set such that every nonempty subset has a smallest element.

For example the usual [math]<[/math] order on the natural numbers is a well-order. The set of primes, the set of even numbers, the set of squares, each have a smallest member. Every possble nonempty set of the naturals has a smallest member, so the naturals are well-ordered by [math]<[/math].

On the other hand the usual order [math]<[/math] on the integers is not a well-order, because the negative numbers have no smallest element.


* Order-types

What we mean by an order-type is the "shape," or structure, of a well-ordered set.

Consider for example the natural numbers in their usual order, 0, 1, 2, 3, 4, ...

and the natural numbers with the positions of 1 and 2 switched, like this:

0, 2, 1, 3, 4, 5, ...

It's clear that this is a different order than the usual order; but that it's structurally the same. That is, there is an order-preserving bijection between the two ordered sets:

0  1  2  3  4  5 ...

^  ^  ^  ^  ^  ^ ...

|  |  |  |  |  | ...

v  v  v  v  v  v ...

0  2  1  3  4  5 ...

In other words we can find a bijection between the two sets that preserves their respective orders. Such an order-preserving bijection is called an order-isomorphism.

The "shape," or structure, of each of these well-ordered sets can be depicted as:

[math]\square \ \square \ \square \ \square \ \square \ \square \ \dots[/math]

On the other hand, consider the following interesting reordering of the natural numbers:

1, 2, 3, 4, 5, ..., 0

Here we have simply placed 0 at the end. We could, if we wanted to, formalize this by defining a new "funny order" relation [math]\prec[/math] defined like this:

* If [math]n < m[/math] and [math]n \neq 0[/math], then [math]n \prec 0[/math].

* [math]n \prec 0[/math] for all [math]n \neq 0[/math].

In other words [math]\prec[/math] is just like [math]<[/math] except that everyhing is "funny less than" 0.

You should convince yourself that "funny less than" is a well-order.

I should mention that each of the finite numbers 0, 1, 2, 3, ... is itself an ordinal representing a single order type. No matter how you rearrange finite set it's always got the same order type.

There's a notation for an ordered set. We denote the natural numbers in their usual order as [math](\mathbb N, <)[/math]. That is, it's an ordered pair where the first item is the set, and the second is the particular order relationship on the set.

Likewise [math](\mathbb N, \prec)[/math] represents the funny order on the naturals, the one with 0 at the end.

There's a special notation for the ordered set [math](\mathbb N, <)[/math], and that is [math]\omega[/math]. That is, [math]\omega[/math] stands for the natural numbers in their usual order.

We can see right away that there is no order-isomorphism between these two ordered sets, because [math](\mathbb N, \prec)[/math] has a largest element, while [math](\mathbb N, <)[/math] doesn't.

The shape, or structure, of [math](\mathbb N, \prec)[/math] looks like this:

[math]\square \ \square \ \square \ \dots \ \square[/math]

If the usual order 0, 1, 2, 3, ... is called [math]\omega[/math], then our funny order [math](\mathbb N, \prec)[/math] is called [math]\omega + 1[/math]; that is, the successor of [math]\omega[/math]


* Some more ordinals.

We can play this game indefinitely. How about

2, 3, 4, ..., 0, 1. That's a different order-type, named [math]\omega + 2[/math]. And

3, 4, 5, ..., 0, 1, 2 is [math]\omega + 3[/math].

We can keep doing this over and over; and we can take the limit of this process to get [math]\omega + \omega[/math]. How would we represent that with a funny ordering of the naturals? This is the even-odd order:

0, 2, 4, 6, ..., 1, 3, 5, 7, ... in which all the evens come before all the odds. It's just two copies of [math]\omega[/math], one after the other. The ordinal [math]\omega + \omega[/math] is also notated [math]\omega 2[/math], because ordinal multiplication is notated backwards. [math]\omega 2[/math] is 2 copies of [math]\omega[/math]. Apparently Cantor (who thought all this up) went back and forth on which way to notate ordinal multiplication, and in the end picked this one.

How could we represent three copies, [math]\omega 3[/math]? Instead of evens and odds, we can go by remainders mod 3:

0, 3, 6, 9, ..., 1, 4, 7, 10, ..., 2, 5, 8, 11, ...

We can do the same trick with remainders mod 4, 5, and so on, to represent [math]\omega 4, \omega 5, \dots[/math]. Eventually the upward limit of that process is [math]\omega [/math] copies of [math]\omega[/math], or [math]\omega * \omega = \omega^2[/math].

But now the modulo remainder trick doesn't work; and it's clear that there are going to be a lot more ordinals than there are obvious ways to reorder the naturals to represent them. We need new ideas.

But before going on, let's stop a moment to meet some more ordinals and make an amazing observation about them.

The successor of [math]\omega^2[/math] is [math]\omega^2 + 1[/math], then [math]\omega^2 + 2[/math], and so forth, then [math]\omega^2 + \omega[/math], and we keep on going. In fact ordinals look sort of like polynomials in [math]\omega[/math]. This notation is known as Cantor normal form.

Let's look at some more of these. After we run through [math]\omega^3, \omega^4, \dots[/math], the upper limit of that process is [math]\omega^\omega[/math]. If we keep on going, we come to [math]\omega^{\omega^\omega}[/math], [math]\omega^{\omega^{\omega^\omega}}[/math], and so forth; and eventually to the coolest number that I know, an [math]\omega[/math]-sized exponental tower of [math]\omega[/math]'s. This number is called [math]\epsilon_0 = \omega^{\omega^{{\omega^?}}}[/math]. Then there's a hierarchy [math]\epsilon_1[/math], [math]\epsilon_2[/math], and on and on. These are the epsilon numbers.

Now here is the punch line.

Every one of these ordinal numbers that I've shown so far is a countable set. It represents some well-ordering of [math]\mathbb N[/math].

After all, rearranging the elements of a set does not alter its cardinality. So it's obvious that [math]\omega, \omega + 1, \dots, \omega 2, \dots[/math] all have the same cardinality, and the epsilons you can take on faith. In fact the Wiki article on the epsilon numbers states that every epsilon number whose index is countable is itself countable.

I should note in case the exponentiation caused confusion, that ordinal exponentiation is not the same as cardinal exponentiation. [math]\aleph_0^{\aleph_0}[/math] is indeed uncountable, because it's cardinal exponentiation; but [math]\omega^\omega[/math] is countable by the definition of ordinal exponentiation.


* Uncountable ordinals.

Can there possibly be an uncountable ordinal? In fact there is. We sketch the construction as follows.

We've already noted that the [math]\sup[/math], or union, or least upper bound of a set of ordinals is an ordinal.

Now onsider the set of all possible countable ordinals; that is, the set of all well-orderings of [math]\mathbb N[/math]. We have to prove that this is a set, but that can be done.

Its union, or [math]\sup[/math], is an ordinal, but it can't be a countable one because then it would be a member of itself; and no ordinal is a member of itself. We call this ordinal [math]\omega_1[/math], the first uncountable ordinal. Its existence can be proven without the axiom of choice.

Trying to imagine an uncountable ordinal is mind boggling, but they exist even in ZF. In other words we know that the axiom of choice says that all sets can be well-ordered. But even without choice, some uncountable sets can be well-ordered. Just not all of them.


* The Alephs.

Ok time to catch our breath. The ordinals are dizzying to contemplate. Let's take a digression to define the Aleph numbers. These are Cantor's famous cardinalities. What are they, exactly? In the early days of set theory, a cardinal number was the equivalence class of all sets bijectively equivalent to each other. So [math]\aleph_0[/math] was the class of all sets bijectively equivalent to the natural numbers, and so forth.

There is a problem with this definition, which is that the Alephs are not sets. For the same reason that there's no set of all sets, there's also no set of all sets bijectively equivalent to the naturals or any other cardinality. [I'm using cardinality a little circularly there, but you know what I mean].

John von Neumann, who we'll talk about more in a bit, is responsible for the following modern definition, called the von Neumann cardinality assignment. Although tonight as I was writing this is the first time I ever heard it called that, and learned that von Neumann is responsible for the idea. He showed how to define the cardinality of any well-ordered set as a particular ordinal, so that cardinals are sets and can be manipulated using the rules of set theory. That turns out to be more convenient than the older definition.

We need the fact that any nonempty collection of ordinals must have a smallest ordinal. In other words the class of ordinals is itself well-ordered.

(However the class of ordinals is not a set, that's the Burali-Forti paradox).

Now given any well-ordered set, we define its Aleph number as the least ordinal that's cardinally equivalent to that set. How do we know that there is one? Since the set is well-ordered by hypothesis, it's cardinally equivalent to at least one ordinal. In other words the class of ordinals cardinally equivalent to our set is nonempty; therefore there's a smallest one. That's the one that we define as the set's Aleph.

And since the Alephs are then a collection of ordinals, there's a smallest one, which is [math]\aleph_0[/math], and a next one, [math]\aleph_1[/math], and so forth.

That's why there's no [math]\aleph_{\frac{1}{2}}[/math] for example. Nobody ever asks why the Alephs are indexed by whole numbers, but now it's clear why. Each Aleph is itself an ordinal, and any collection of ordinals is well-ordered. The collection of all the Alephs is not a set, by the way. Again, same reason as that there's no set of all sets.

In fact the Alephs are indexed not just by natural numbers, but by ordinals. So for each ordinal [math]\alpha[/math], there's an [math]\aleph_\alpha[/math]. There's an [math]\aleph_\omega[/math], and an [math]\aleph_{\omega_1}[/math], and so forth. Those are some big sets!

Let's work out the first few Alephs.

What is the least of all the ordinals with the same cardinality as [math]\mathbb N[/math]? We've seen that it's [math]\omega[/math]. So we define [math]\aleph_0 \stackrel{\text{def}}{\equiv} \omega[/math].

What's next? We define [math]\aleph_1 \stackrel{\text{def}}{\equiv} \omega_1[/math]. So now we can visualize [math]\aleph_1[/math]. It's the cardinality of the set of all countable ordinals.

And then [math]\aleph_2 \stackrel{\text{def}}{\equiv} \omega_2[/math] is the cardinality of the set of all ordinals of cardinality [math]\aleph_1[/math].

And since each of the finite numbers 1, 2, 3, ... is itself an ordinal, we see that [math]\aleph_0[/math] is just the cardinality of the set of all finite ordinals.

And now we can concretely visualize all the Alephs. For suitable values of "concretely," anyway. Each Aleph is the cardinality of the set of ordinals one level down. You want to know what is [math]\aleph_{47}[/math]? It's the cardinality of the set of all well-orders of a set of cardinality [math]\aleph_{46}[/math].

Let me say this again to emphasize how simple it is.

How many different well-orderings are their of finite sets? There are [math]\aleph_0[/math] of them, one for each of 0, 1, 2, ... How many well-orderings are there of a set of cardinality [math]\aleph_0[/math]? There are [math]\aleph_1[/math] of them. How many well-orderings of a set of cardinality [math]\aleph_1[/math]? There are [math]\aleph_2[/math] of them. And so on all the way up.

One final wrinkle. I said this definition works for any set that is well-orderable. Given a well-ordered set, we find the class of all ordinals cardinally equivalent to it, and define that set's Aleph as the least such ordinal.

In the presence of the Axiom of Choice, every set can be well-ordered and this definition works for every possible set. But in the absence of choice, there are infinite sets that are not well-ordered, so we can't use this definition. In that case there's a trick, called Scott's trick, that can assign a cardinality to every set, even the non-well-ordered ones. That's a little outside the scope of this exposition but I'm mentioning it for completeness.


* The von Neumann ordinals.

We've seen that we ran out of clever ways to visualize well-orders of the natural numbers long before we ran out of countable ordinals. Here's another nice way to visualize the ordinals. In fact this method provides a specific, canonical set to represent each ordinal.

John von Neumann was a mathematician and pure and applied scientist. He invented mathematical game theory, worked on the hydrogen bomb, made fundamental contributions to functional analysis and quantum mechanics, worked on operator algebras and fluid mechanics and more. In his time he was regarded as the smartest man in the world. And as if all that wasn't enough for one short life -- he died tragically at 53 of cancer, possibly due to radiation exposure contracted at Los Alamos National Laboratory -- he gave us our modern definition of ordinal numbers.

First, a transitive set is a set each of whose elements is also a subset.

If [math]X[/math] is any set, we define its successor [math]X'[/math] as [math]X \cup \{X\}[/math]; that is, [math]X[/math] unioned with the set containing [math]X[/math]

We can then build up all the ordinals as transitive sets, starting from the empty set.

[math]\emptyset[/math] is vacuously a transitive set, which we call [math]0[/math].

If [math]n'[/math] is the successor of [math]n[/math], then:

[math]0' = \emptyset \cup \{\emptyset\} = \{\emptyset\}\stackrel{\text{def}}{\equiv} 1[/math].

[math]1' = 1 \cup \{1\} = \{{\emptyset, \{ \emptyset \} }\} \stackrel{\text{def}}{\equiv} 2[/math],

[math]2' = 2 \cup \{2\} = \{{\emptyset, \{ \emptyset \} }, \{\emptyset, \{\emptyset\}\}\} \stackrel{\text{def}}{\equiv} 3[/math]

and so on.

Now if [math]X[/math] is a set of ordinals, we define [math]\sup(X) = \bigcup X[/math], the union of all the ordinals in [math]X[/math]. We also call that the least upper bound of that set of ordinals.

If [math]X[/math] has a largest element, such as for example [math]X = \{1,2,3,4,5\}[/math], then [math]\sup(X) = 5[/math], the largest element. In other words, the union of a set of ordinals having a largest element is just that largest element.

But if the set of ordinals has no largest element, then its union is a brand new ordinal. So [math]\sup \{0, 1, 2, 3, ...\} = \omega[/math]. Such an ordinal is called a limit ordinal. That is, a limit ordinal is an ordinal that's not the successor of any ordinal.

Once we reach [math]\omega[/math], we keep taking successors till we reach [math]\omega 2[/math] and all the rest of them. The idea is to keep taking successors then limits, successors then limits, without end.

This gives another way to think of the ordinals.

The natural numbers are produced by starting with 0, and then repeatedly applying the successor operation.

The ordinals are just like that, but in addition to the successor operation, we also have the sup operation. We keep taking successors, and every once in a while we accumulate a countably infinite collection of successors into their sup and keep on going.

One of the virtues of the von Neumann ordinals is that every ordinal is the set of all smaller ordinals.

And von Neumann's idea allows us to give the standard, official definition of an ordinal number that you'll find in set theory textbooks:

An ordinal is a transitive set well-ordered by [math]\in[/math].


* The class of all ordinals.

As I mentioned, the collection of all the ordinals is not a set. The class of ordinals is called On or sometimes Ord. It's On that Cantor originally identified with God. Cantor called the class of ordinals [math]\Omega[/math], the Absolute infinite. He already knew that the class of all ordinals is not a set. He said:

[quote=Georg Cantor]
The system ? of all [ordinal] numbers is an inconsistent, absolutely infinite multiplicity.
[/quote]

In modern set theory, On is of great theoretical importance.


* Ordinal arithmetic

We can add, multiply, and exponentiate ordinals. The Wiki writeup of ordinal arithmetic is pretty good and I can't add anything to it. One thing to know is that ordinal addition and multiplication are not in general commutative. They are both associative, and multiplication left-distributes but does not right-distribute over addition.



* Odds and ends about countable ordinals.

The countable ordinals are very wild and strange. [math]\epsilon_0[/math] is one mind-boggling countable ordinal we saw.

A surprising fact is that every countable ordinal can be order-embedded into the rationals. That is, for every countable ordinal, there is a set of rationals in their usual order that's order-isomorphic to that ordinal.

We've seen that there are uncountably many well-orders of [math]\mathbb N[/math]. But there are only countably many Turing machines, or Python or C++ programs if you prefer. So there must exist noncomputable well-orderings of the natural numbers; and if there are any, since they're ordinals, there's a smallest one. The smallest noncomputable countable ordinal is called the Church-Kleene ordinal. From that point on, none of the order types of the natural numbers are computable.

Here's the Feferman–Schütte ordinal, whose Wiki definition is far from clear to me and about which I know nothing.

Wikipedia has an article on large countable ordinals that shows just how complicated things can get.

I'm in too deep, time to stop.