# Gracious Living

Ordinals
November 6, 2010, 08:17
Filed under: Math, Set Theory | Tags: , , , ,

When we talked about cardinality, we defined “standardized” finite cardinal numbers as the set $\mathbb{N}$, which we modeled as $0=\emptyset, 1=\{0\},2=\{0,1\},$ 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” $S(n)=n\cup\{n\}$ is well-defined, injective, and its image is everything but $0$
• because of this, if a statement is true for $0$ and its truth for $n$ implies its truth for $S(n)$, it is true for all elements of $\mathbb{N}$ — this is the “inductive property”
• $n\subset m$ iff $n\in m$, and these synonymous relations are total orders on $\mathbb{N}$.

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 $\mathbb{N}$ is already a well-order: given $M\subset\mathbb{N}$, the set $\bigcap M$ is a least element, and you should prove that this is always an element of $M$ (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 $X$ and $Y$, the only functions we should be caring about are those that are order-preserving: that is, that $f(a)\le_Y f(b)$ when $a\le_X b$.  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 $\mathbb{N}$ in the post on countability did this, and it’s pretty clear why: any order isomorphism has to preserve the type of ordering, and $\mathbb{N}$ is well-ordered while $\mathbb{Z}$ and $\mathbb{Q}$ 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 $\mathbb{N}$ does as well!  This is our first infinite ordinal, and in these circumstances we write it as $\omega$.  To get beyond this, we’ll appeal to a couple of propositions:

Proposition.  If $\alpha$ is an ordinal, then $S(\alpha)=\alpha\cup\{\alpha\}$ is as well.

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

Thus, from $\omega$, we get $\omega+1,\omega+2,\dotsc$.  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 $I$ some indexing set.  Then $\beta>\alpha_i$ for all $i$.  Any element of $\beta$ is an element of some $\alpha_i$, thus a subset of it, and so of $\beta$.  $\square$

So, for example, the union of the set $\{0,1,2,\dotsc,\omega,\omega+1,\omega+2,\dotsc\}$ is a new ordinal; we call it $2\omega$.  Because of transitivity, it’s not necessary to include the whole set, just $\omega+i$ for ever-increasing values of $i$.  Similarly, we can define $3\omega,4\omega,\dotsc$, and then take their union to get $\omega^2$.  Continue further, and you get $\omega^\omega,\omega^{\omega^\omega},\dotsc$.  For want of a better name, the limit of this sequence is called $\epsilon_0$.

An ordinal of the form $S(\alpha)$ is called a successor ordinal; an ordinal not of this form is called a limit ordinal.  So $\omega$ is the first limit ordinal, $2\omega$ 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 $\alpha$ if it holds for all ordinals $\beta<\alpha$.  Then it holds for all ordinals.  Note the zero case is given because any property holds vacuously for the nonexistent subsets of $\emptyset$.  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 “$\alpha$ is not order isomorphic to any ordinal smaller than $\alpha$“; we write this as $P(\alpha)$.  Clearly $P(0)$ holds, because there are no ordinals smaller than $0$.

Suppose $P(\alpha)$ but not $P(S(\alpha))$; instead, say $S(\alpha)$ is order isomorphic to $\beta.  Since $S(\alpha)$ has a greatest element, $\beta$ does too, so $\beta$ is a successor ordinal, say $\beta=S(\gamma)$.  But then the order isomorphism $S(\alpha)\rightarrow S(\gamma)$ restricts to an order isomorphism $\alpha\rightarrow\gamma$, which is a contradiction.  So $P(\alpha)$ implies $P(S(\alpha))$.

Now let $\lambda$ be a limit ordinal, and we know $P(\kappa)$ for all $\kappa<\lambda$.  Then if we have an order isomorphism $\lambda\rightarrow\mu$, it restricts to an order isomorphism on each $\kappa$, say to $\nu_\kappa<\mu$.  The union of all $\nu_\kappa$ is clearly $\mu$, but since we know $P(\kappa)$, then $\nu_\kappa=\kappa$, so their union, $\mu$, is equal to $\lambda$.  By transfinite induction, the proof is done.  $\square$

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 $X$ and $x\in X$, define the section of $x$, $s_x$, to be the set of elements less than $x$.  Let $x$ be such that for all $y, $s_y$ is order isomorphic to an ordinal.  Such a $x$ exists — the least element of $X$ is an example.  Look at the union of ordinals order isomorphic to $s_y$ for $y; this is also an ordinal, and it is clearly order isomorphic to $s_x$.  By transfinite recursion, every element $x\in X$ has $s_x$ order isomorphic to an ordinal.  Let $M=X\cup\{m\}$, with $m>x$ for all $x\in X$.  This is also well-ordered, and so $s_m=X$ is order isomorphic to a unique ordinal.  $\square$

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 $A$ 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 $A$ 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 $A$.  Thus, $\aleph_0$ is just $\omega$, the smallest countable ordinal.  The smallest uncountable ordinal is usually written $\omega_1$; whether this bijects with $\mathbb{R}$ depends on whether you accept the continuum hypothesis.  Note that $\omega_1$ is the set of countable ordinals (or union of them, your choice).

Besides $\omega_1$, there are some other large ordinals.  We might talk about ordinal arithmetic later, but for now look at this.  We defined $\epsilon_0$ as the limit of $\omega,\omega^\omega,\omega^{\omega^\omega},\dotsc$.  Another way of looking at this is by saying that $\epsilon_0$ is the smallest ordinal $\alpha$ with $\omega^\alpha=\alpha$.  But other ordinals could satisfy this: the next such is the limit of $\epsilon_0+1,\omega^{\epsilon_0+1},\omega^{\omega^{\epsilon_0+1}},\dotsc$.  We can call these successive solutions $\epsilon_\iota$, 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, $\omega_1^{CK}$.  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 $\omega$ has the discrete topology, and $\omega+1$ is discrete except at its last element, $\omega$, 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, $\omega_1$ is a limit point of $\omega_1+1$, and its greatest element; but any sequence of ordinals less than it is countable, and thus converges to some countable ordinal below it.  So $\omega_1$ 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!