From the Cardinals to the Ordinals

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 elements of a set can be put in order, even if it's infinite: how do we talk about *where* an element occurs in a well-ordering of an infinite set?

For doing this, there's a construction similar to the cardinal numbers called the *ordinal numbers*. Just like the cardinals provide a way of talking about the *size* of infinitely large things, ordinals provide a way of talking about *position* within infinitely large things.

Just like the cardinals, with the ordinals, we can start with the natural numbers: 0, 1, 2, 3, representing the first, second, third, and fourth position in a well-ordered set. In fact, we'll do more than that, and define them in terms of sets, using the same scheme we used before: 0=∅, 1={∅}, 2={∅,{∅}}, ..., n+1=n∪{n}. So each number is *the set of numbers that preceeded it*.

What happens when we get to a set with cardinality ℵ₀? To talk about the position of elements inside of that, we need something for representing the first position of an element *after* all of the finite ordinal positions. We use the symbol ω for the first transfinite ordinal. While we won't get to ordinal arithmetic until a bit later, with ordinals, ω+1>ω: we're not talking about size: we're talking about position, and even when we get to the transfinite realm, there can be something *next to* an object in position ω, and since it's in a distinct position, it needs a distinct transfinite ordinal.

When we talk about ordinals, there are three kinds of ordinal numbers. There's zero, which is the position of the initial element of a well-ordered set. There are successor ordinals, which are ordinals which we can define as as the next ordinal after (aka the successor to) some other ordinal; and there are limit ordinals, which are ordinals that are neither 0 nor successor ordinals. ω is a limit ordinal: it's the limit of the finite ordinals: as the first non-finite ordinal, every finite ordinal comes before it, but there is no way of specifying just what ordinal it's the successor to. (There is no subtraction operation in ordinal arithmetic, so ω-1 is undefined.)

Limit ordinals are important, because they're what gives us the ability to make the connection to positions infinite sets. A successor ordinal can tell us any position within a finite set, but it's no good once we get to infinite sets. And as we saw with the cardinals, there's no limit to how large sets can get - there's an infinite number of transfinite cardinals, with corresponding sets.

So how do we use transfinite ordinals to talk about position in sets? In general, it's part of a proof using transfinite induction. So while we can't necessarily specifically identify element ω of a set with transfinite cardinality, we can talk about the ωth element. The way that we do that is by isomorphism: every well-ordered set is isomorphic to the set-form of an ordinal. A set with N elements is isomorphic to the ordinal N+1. Then we can talk about the ωth element of an infinite set by talking in terms of the well-ordering and the isomorphism.

This does, however, lead us to a problem. You see, by this process, you can use ordinals for indexing anything with a well-ordering: not just sets. While there's no *requirement* that classes in general must have well-orderings, there are classes - even proper classes - which have well-orderings. Which means that the ordinals must be a proper class themselves: because proper classes are larger that the largest sets: so to be able to define a well-ordering on a proper class, there must be too many ordinals for the ordinals to be a set.

One last tidbit for today. Ordinals and cardinals are clearly deeply connected. What's the direct connection? The cardinal ℵ₀ is the cardinality of the set representation of ω. (It's also the cardinality of ω+1, ω+1, etc.)