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<S(\alpha).  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<x, 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<x; 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!

Advertisements

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 Living

[…] 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 Living




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: