Filed under: Math, Set Theory | Tags: Math, order theory, set theory, topology, weird

When we talked about cardinality, we defined “standardized” finite cardinal numbers as the set , which we modeled as and so on. We’ve since noted certain special properties of this model:

- the set exists by the ZFC axioms
- because of this, it is “pure” — everything is a set of sets, there are no ur-elements
- the “successor function” is well-defined, injective, and its image is everything but
- because of this, if a statement is true for and its truth for implies its truth for , it is true for all elements of — this is the “inductive property”
- iff , and these synonymous relations are total orders on .

In the discussion of the Axiom of Choice, we defined a “well-order” as a total order in which every subset has a least element, and proved that every set can be well-ordered if we assume the AC. In fact, the subset/element ordering on is already a well-order: given , the set is a least element, and you should prove that this is always an element of (induction might help).

Cardinalities tell us everything about sets up to bijection. But when sets also have orders on them, this isn’t enough. If we care about the orders on and , the only functions we should be caring about are those that are **order-preserving**: that is, that when . Likewise, rather than all bijections, we care about the **order isomorphisms**: bijections that are order-preserving and have order-preserving inverses. We’re “pairing off” the sets again, but in the same order. None of the bijections with in the post on countability did this, and it’s pretty clear why: any order isomorphism has to preserve the type of ordering, and is well-ordered while and aren’t.

The order isomorphism classes (or **order types**) of general posets or tosets are many and difficult to talk about. But the order types of well-ordered sets are easier to study. Below the fold, let’s take them on.

We define an **ordinal** as a transitive set well-ordered by inclusion, where by **transitive** we mean that every element of the ordinal is also a subset of the ordinal. Plainly, the natural numbers as defined above satisfy this condition. But the set does as well! This is our first infinite ordinal, and in these circumstances we write it as . To get beyond this, we’ll appeal to a couple of propositions:

**Proposition**. *If is an ordinal, then is as well.*

**Proof**. The elements of are and its elements, and must be greater than each of its elements since it includes them all. is well-ordered: every subset is either a subset of (and has the expected least element), or is union a subset (and has the least element you get if you subtract ), or is (and its least element is ). Similarly, all elements of are , and by definition.

Thus, from , we get . To go further, we need our second proposition.

**Proposition**. *The union of ordinals is an ordinal.*

**Proof**. Let $\latex \beta=\bigcup_{i\in I}\alpha_i$, for some indexing set. Then for all . Any element of is an element of some , thus a subset of it, and so of .

So, for example, the union of the set is a new ordinal; we call it . Because of transitivity, it’s not necessary to include the whole set, just for ever-increasing values of . Similarly, we can define , and then take their union to get . Continue further, and you get . For want of a better name, the limit of *this* sequence is called .

An ordinal of the form is called a **successor ordinal**; an ordinal not of this form is called a **limit ordinal**. So is the first limit ordinal, is the next one, and so on. Ordinals *don’t* form a set, because this set, being a union of ordinals, would be an ordinal itself, and thus an element of itself! But the *class* of ordinals is well-ordered by inclusion, as expected, and when you restrict to an individual ordinal, the well-ordering is preserved. So each ordinal is really the set of ordinals less than it.

This observation leads to an important tool, an analogue of induction on natural numbers. It’s called **transfinite induction**. Again, suppose we have a property, and suppose that the property holds for the ordinal if it holds for all ordinals . Then it holds for all ordinals. Note the zero case is given because any property holds vacuously for the nonexistent subsets of . In practice, it’s easier to do one of these proofs in two steps: successors, and limits. Here’s an example.

**Lemma**. *No two ordinals are order isomorphic.*

**Proof**. The property in question is “ is not order isomorphic to any ordinal smaller than “; we write this as . Clearly holds, because there are no ordinals smaller than .

Suppose but not ; instead, say is order isomorphic to . Since has a greatest element, does too, so is a successor ordinal, say . But then the order isomorphism restricts to an order isomorphism , which is a contradiction. So implies .

Now let be a limit ordinal, and we know for all . Then if we have an order isomorphism , it restricts to an order isomorphism on each , say to . The union of all is clearly , but since we know , then , so their union, , is equal to . By transfinite induction, the proof is done.

**Theorem** (fundamental theorem of ordinals). *Every well-ordered set is order isomorphic to a unique ordinal.*

**Proof**. Uniqueness comes from the lemma. Given a well-ordered set and , define the **section** of , , to be the set of elements less than . Let be such that for all , is order isomorphic to an ordinal. Such a exists — the least element of is an example. Look at the union of ordinals order isomorphic to for ; this is also an ordinal, and it is clearly order isomorphic to . By transfinite recursion, every element has order isomorphic to an ordinal. Let , with for all . This is also well-ordered, and so is order isomorphic to a unique ordinal.

So our claim that ordinals enumerated order types of well-ordered sets was correct! Before we leave set theory forever, let’s look at a few cool things you can do with ordinals.

First, we can define cardinals as ordinals. Assuming the Axiom of Choice and hence the Well-Ordering Theorem, any set can be well-ordered, and so has an order isomorphism to an ordinal. If we ignore the order part, this is just a bijection. We can look at all the ordinals bijects with in this way; since the ordinals are well-ordered, this set has a least element, and we call this the **cardinal number** corresponding to . Thus, is just , the smallest countable ordinal. The smallest uncountable ordinal is usually written ; whether this bijects with depends on whether you accept the continuum hypothesis. Note that is the set of countable ordinals (or union of them, your choice).

Besides , there are some other large ordinals. We might talk about ordinal arithmetic later, but for now look at this. We defined as the limit of . Another way of looking at this is by saying that is the smallest ordinal with . But other ordinals could satisfy this: the next such is the limit of . We can call these successive solutions , where $\iota$ is indexed by the ordinals! But even this isn’t good enough. All of these epsilons are defined by what are called “computable” functions, which basically means something a human or computer can define. We can take the union of all computable ordinals to find the first non-computable one: the **Church-Kleene ordinal**, . Oh, by the way, this is still countable. And it gets worse…

Last, since these guys basically are order, let’s look at their order topologies. We saw that has the discrete topology, and is discrete except at its last element, , which is a limit point. In general (investigate this yourself), the limit points of an ordinal with the order topology are precisely its limit ordinals! Oh, and uncountable ordinals are also interesting, because they show that sequences aren’t good enough to understand limit points. For instance, is a limit point of , and its greatest element; but any sequence of ordinals less than it is countable, and thus converges to some countable ordinal below it. So in this space is a limit point but not a limit of any sequence! We’ll come back to these examples often.

I think I’m done with set theory for a while now. We’ll get onto some classical topology tomorrow. Thanks for reading!

**2 Comments so far**

Leave a comment

[…] Theorem is a super-simple number theory statement that you can prove easily using ordinals and ZFC, but that you can’t prove in […]

Pingback by A Couple Nuances « Gracious LivingDecember 6, 2010 @ 03:02[…] retain the order and you win the exciting new property of it being closed under limits. This is ordinal arithmetic. Building it will let us understand the structure of the ordinals more rigorously than […]

Pingback by Ordinal Arithmetic « Gracious LivingDecember 7, 2010 @ 21:03