#well ordering

So what's a well-ordering? Well, first, we need some elements to put into an order. So let A be set. We can define an ordering < on A, which is simply a relation on A with the following properties:

irreflexivity: x < x is never the case for any x ∈ A. In other words, there are no elements of the form < x, x > ∈ <.

transitivity: if x < y and y < z, then x < z.

trichotomy: for any pair x, y, at most one of the three x < y, y < x, x = y holds. It's not necessary for any of them to hold, either. In this case, we get a partial ordering. If it's the case that exactly one holds for all pairs x, y, then we have a linear ordering (correct me if I'm wrong, but I believe it could also be called a total ordering).

So for < to be a well-ordering, it has to be a linear ordering with the added property that any subset B ⊆ A has a least element. An element b ∈ B is a least element if b < b' for every b' ∈ B where b' ≠ b. Okay, so now that we've got our structures, let's measure their lengths!

To construct the ordinal numbers, we need this weird thing called transfinite recursion. I had to read this section of the text at least ten times before I actually understood it. I think it read it around four times the first night I was going through the material, and then let it marinate for a while before reading it several times again a few weeks later. I kind of got it, but I don't think it was until yesterday, when I was going back through my book to really solidify and catch up, did I truly get the concept. Well, better late than never right? So I'm going to try and be as slow and clear as possible. The general idea is pretty simple, but it get really wonky with the notation.

Let's first think about induction. To construct something inductively, you take what you had previously, then do something to it. So if you were trying to construct something for n+, you take whatever value you had for n, and then manipulate it according to some pre-specified rule. So what about "strong induction", which I covered in my discrete math posts (toc)? That's basically what transfinite recursion is. Instead of constructing the next value by simply using the previous value, you need to take into account all the previous values. That's the intuition. So now, here's the formalism.

Let's start with an easy definition. Start with a linearly-ordered set, A. Let a be an element of A. Then the segment of a, seg(a), is the set of all elements less than a, i.e. {x ∈ A | x < a}.

Suppose you have some rule, a function G, that assigns the next value based on all previous values. Let's say that G picks out an element from B, based on its previous values on A. How do we actually formalise G? Well, the codomain of G is easy: it's B. What about the domain? It's not actually A, because G is taking all previous values of itself as input. In fact, G is defined on the set {f | f a function from some segment in A to B}. For example, G(t) takes as input some function defined on seg(t); in particular, the previous values of G on seg(t). It takes this input, then spits out the next value in B. So in fact G goes from this weird set of functions on segments to B.

So the idea is we want to define some function on A that follows this rule G. It's pretty easy to see how it would work intuitively. First, we need A to be well-ordered. Then, A has a least element a0, so we calculate G of a0. That's the value of F at a0. Now, A - {a0} has a least element, a1. a1 is like the "next smallest" element in A. We calculate F(a1) as G of F so far. And on and on. Notationally, we say that F(t) = G(F ↑ segt), i.e. we find the value of t by applying G to the function F defined on the segment of t (all the values of F before t).

The transfinite recursion theorem says that this "on and on" is rigourous. In other words, there indeed exists a function F that can be defined this way, given G. In fact, F is unique. So for every rule G, there is a unique function that is defined by G recursively.

In fact, G doesn't actually need to be a function at all. It can go from a class to a class, not necessarily restricted to going from sets to sets. (Remember, there are "classes" or groups of elements that are too big to be sets, such as the class of all sets. What I'm saying here is that G doesn't need to be a function, so it doesn't need to go from a set to a set.) So the more general way of reformulating transfinite recursion is as follows: instead of a function G, we can simply take a formula γ(f, y) which specifies some relationship between f and y. As long as there is exactly one y for each f such that γ(f, y) holds, we can build a function using transfinite recursion constructed using γ.

The particular γ that we use to build the ordinal numbers is y = ranf. Of course, given a specific function f, the range is completely determined and unique, so there is exactly one y to go with each f such that y = ranf. So our rule checks out and we are good to go to use it.

Finally, all the legwork is out of the way. Time for a test drive! Let's use transfinite recursion to build a function F constructed by this rule on a well ordered set! We'll start easy, with a four-element well-ordered set. Say we use A = {w, x, y, z} where it's ordered alphabetically, so w < x < y < z.

first we evaluate F at the least element, w. F(w) = G(F ↑ segw) = ran(F ↑ ∅) = ran(∅) = ∅. Here, the segment of w is the empty set, so F has no preceding values. So the range of F is empty.

x, is next, so F(x) = G(F ↑ segx) = ran(F ↑ w) = F[w] = {∅}.

now, y. F(y) = G(F ↑ segy) = ran(F ↑ {w, x}) = F[{w, x}] = {∅, {∅}}

last of all, z F(z) = G(F ↑ segy) = ran(F ↑ z) = ran(F ↑ {w, x, y}) = F[{w, x, y}] = {∅, {∅}, {∅ {∅}}}

Hmmm... those values of F look a lot like the natural numbers. In fact, they are. The first is 0, then 1, then 2, then 3. And notice that ranF is well-ordered by inclusion, ∈, the exact same way our original set was ordered by its own well-ordering. How curious.

In fact, this "coincidence" is not a coincidence at all. We call <ranF, ∈> the ∈-image ("epsilon image") of the original well-ordered structure <A, < >, precisely because the ∈-image of any well-ordered structure will be isomorphic to the original structure.

Isomorphisms again? Yes. I've defined isomorphisms over and over on this blog, and the general concept never changes. An isomorphism is a map between two structures that is a bijection of the underlying sets which preserves the structure. Here, we have a set together with a relation (to define an isomorphism, the relation need not be an ordering at all). For the map f: <A, R> → <B, S> to be an isomorphism, it must:

be a bijection of the sets A and B

preserve the relation. In other words, given a and a' in A, we have aRa' iff f(a)Sf(a'). Notice f(a) and f(a') are elements in B, so we use the relation S on B.

Therefore, when we say the ∈-image of any well-ordered set A is isomorphic to the well-ordered set, we mean that it is in bijection with A, and that it is well-ordered precisely in the same way A is ordered. The ordering used on ranF is that of inclusion, ∈. So given a, a' in A, then a < a' iff F(a) ∈ F(a'). Basically, ranF is a collection of elements equinumerous to the original set that also has the same ordering structure.

In fact, this process is how we define the ordinal numbers. Any ∈-image is an ordinal number. As long as a set is the ∈-image of another set, then it is an ordinal number. Notice the ∈-images of any finite well-ordered structure is simply a natural number. Therefore, every natural number is an ordinal number.

You can think of ordinal numbers as a way of "standardising" well-ordered sets. In other words, two well-ordered structures will have the same ordinal number (∈-image) iff they are isomorphic...just like two sets will have the same cardinal number if they are equinumerous.

So the cardinal numbers "standardise" sets based on size (because equinumerous sets look identical from a distance; their elements are simply renamed from one set to another), and ordinal numbers "standardise" well-ordered sets. Because isomorphic structures look fairly similar from far away, structure-wise, their elements are also just relabelled from structure to structure.

To recap (since this concept is new and weird):

we construct the ordinal number of a set A by applying to A the function F constructed by transfinite recursion where y = ranf, then taking ranF ordered by inclusion.

the ordinal number is well-ordered by inclusion.

the ordinal number together with inclusion is isomorphic to the original well-ordered structure.

two well-ordered structures have the same ordinal number iff they are isomorphic.

the finite ordinals are exactly the natural numbers.

How about the ordinal number of our simplest infinite set, ω? Well, like we calculated above, F(n) = n. So ranF = ω itself, and ω is therefore also an ordinal number.

You may be wondering how the ordinals and cardinal numbers are different. The short answer is that there are more ordinal numbers than cardinal numbers. Let me demonstrate with a (hopefully) simple example. Let's consider the well-ordered structure where the underlying set is the natural numbers, and the ordering is defined 1 < 2 < 3 < ... < 0, i.e. just take 0, and make it bigger than everything else. Let's call this structure < A, < >. The cardinality of this set is just ℵ0, because we haven't messed with which elements are in the set; we've simply reordered the set. But what's the ordinal number? Let's calculate the ∈-image.

Well, the structure 1 < 2 < 3 < ... is isomorphic to the natural numbers under the usual ordering. Then, the ∈-image of this "substructure" of <A , < > is therefore just ω. So now, what about F(0)? F(0) = ran(F ↑ seg0) which is simply the ∈-image of the substructure we previously calulated. So F(0) = {ω}. Then, ranF = ω ∪ {ω} = ω+. (Note: F maps A one to one onto its ∈-image, so ω^+ is equinumerous to ω. Therefore, some ordinal numbers will have the same cardinality, even though they are different ordinal numbers. This fact will become important later.)

The idea is that this structure we've constructed, <A, < >, is fundamentally different from the original natural numbers. The big difference is that <A, < > has a maximum element, 0, which is certainly not true for the natural numbers. So although A and the natural numbers are the same set, and have the same cardinality, the way it's ordered (or the "length" of the ordering, if you will) is different. The ordinal numbers capture this added nuance of the well-ordering that the cardinal numbers do not.

In this way, we can actually think about "infinity + 1", just like proofsareart mentioned briefly here. So now I've motivated and constructed the ordinal numbers, next time I might review some results about the them. While most math students have some degree of familiarity with cardinal numbers, ordinal numbers are generally a bit new and more uncomfortable to think about, precisely because they allow this sort of weird business of "infinity + 1"...so we get to deal with all the additional ramifications that come with it. Excited??