This note is meant to collect a few basic facts about ordinals. I found that I didn’t really know how they work and this was embarrassing. I also couldn’t find any source that covered both the basics and some interesting applications, so I tried to assemble them here. Some results proved below are

- The Borel -algebra has the cardinality of the continuum
- (Sierpinski) There is a set in the plane such that every line intersects it in exactly two points
- (Cantor-Bendixson) Any closed subset of is a union of a perfect set and a countable set.

In what follows, many set-theoretical subtleties are ignored. In particular, von Neumann’s construction of ordinals is not presented.

** — 1. Well-Ordered Sets — **

Definition 1A linear order on a set is a binary relation satisfying

- (totality) For any , exactly one of the following holds: or or
- (transitivity) If and then

Definition 2A linear order on a set is awell-orderingif any subset has a minimal element.

Example 1With the natural orderings, is not well-ordered whereas is.

Consider from now on a well-ordered set .

Definition 3An initial segment is a subset such that , if and , then . For a given element , the associated initial segment is the set

Proposition 4Any initial segment is the initial segment associated to some element .

*Proof:* Take . This set has a smallest element , and then .

Proposition 5Suppose are two well-ordered sets. If are two order-preserving bijections, then .

*Proof:* Take the smallest such that and assume . There must be an such that , so necessarily . But this implies , which yields , leading to a contradiction.

Proposition 6A well-ordered set is not isomorphic to any proper initial segment of itself.

*Proof:* Apply the same proof as above to the identity map and the purported isomorphism.

Remark 1The condition on the segment is crucial, as there are many order-preserving maps .

The following result clarifies the relation between well-ordered sets (much like between cardinals).

Theorem 7Suppose and are two well-ordered sets. Then either one is isomorphic to a proper initial segment of the other, or they are order-isomorphic.

*Proof:* For , define the binary relation if as well-ordered sets. Think of as the graph of a hypothetical function or the other way around. For any , there is at most one such that (and similarly for elements of ), so the hypothetical is well-defined. Moreover it is well-defined on some initial segments of and . If either initial segment is proper, we get the desired embedding. If both are proper, they would be of the form and , which would imply , contradicting the assumption on the initial segments.

** — 2. Ordinals — **

Definition 8An ordinal is an equivalence class of well-ordered sets.

Remark 2As stated, this definition is plagued by some set-theoretical difficulties. Ordinals thus form more of a class than a set. However, von Neumann provided a procedure for choosing canonical set-theoretical representatives for each ordinal. This representative is not only canonical in the usual mathematical sense (unique up to unique isomorphism) – it is canonical in that the actual underlying set is some uniquely described set.

Ordinals will be denote by lower-case Greek letters, e.g. .

Remark 3Theorem 7 allows us to introduce an ordering on the ordinals themselves, making them into a well-ordered class.

Theorem 9Let be a collection of ordinals. There exists a smallest element .

*Proof:* Take some . For any such that , take such that . This collection of elements of has a unique minimal element, corresponding to some .

** — 3. Operations on Ordinals — **

Definition 10Given an ordinal , define its successor , with the same order structure, but with greater than anything else. Given a collection of ordinals, letbe the smallest ordinal that’s bigger than all the ‘s.

Remark 4For any ordinal , take the collection of ordinals . If it has a largest element, is a successor ordinal. Otherwise, it’s called a limit ordinal.

Example 2Denote by the first infinite ordinal, namely with the usual order structure. We also have the finite ordinals, denoted .

Definition 11Given two ordinals , define the following operations

- is the ordinal whose underlying set is , and in addition to the initial relations, all elements of are less than any element of .
- is the ordinal given by lexicographic order on . One can think of it as copies of .

Example 3Some examples to illustrate the concepts are

Remark 5Given a collection of ordinals indexed itself by an ordinal , one can form their sums and productsand

This requires transfinite induction/recursion, discussed below.

** — 4. Countable Ordinals — **

The ordinals whose underlying set is countable are the ones that are likely to be most useful in real life (e.g. the set of volumes of finite-volume hyperbolic -manifolds has ordinal type ). Another place to encounter ordinals is when studying Borel sets (to be discussed in the section on applications).

Definition 12An ordinal is called countable if its underlying set is countable.

Proposition 13If is a countable collection of countable ordinals, there exists a countable ordinal such that for any .

*Proof:* One can take .

Theorem 14There exists an uncountable ordinal, denoted , such that , the initial segment is countable.

*Proof:* Take some uncountable ordinal and consider in it the collection of all such that is uncountable. Either this set is empty, in which case , or it has a smallest element , in which case . Alternatively, one can define to be the limit of all countable ordinals.

The following results will be useful when dealing with the Borel -algebra.

Proposition 15Any countable set has an upper bound in .

*Proof:* Consider . This is a countable union of countable sets, so itself countable. Thus it cannot be all of .

** — 5. Applications — **

**Principle of transfinite induction**

Suppose is a set in bijection with some ordinal . Denote by elements of corresponding to some (viewed itself as a ordinal, via the initial segment construction).

Suppose is some proposition with the property that whenever is true for all , then is true as well.

If we know that holds for the smallest element of , the principle of transfinite induction implies that is true for all .

**Transfinite recursion**

This will be stated less precisely, because the actual statement involves detailing the notion of `property` or `function`. However, suppose we want to define some such property or function for the elements of an ordinal. Suppose further that we know how to do it for the smallest element, and from the knowledge of for all we know how to define . Then can be defined for all elements of the ordinal.

Theorem 16The Borel -algebra of has the cardinality of (at most) the continuum. (At most, because it depends on the continuum hypothesis.)

*Proof:* Using transfinite recursion, we can define the *level* or *complexity* of a Borel set, valued in ordinals. Namely, define the open and closed intervals with rational endpoints to be of complexity . The sets of complexity are those that can be written as countable unions and intersections of sets of complexity , with for all .

Denote by the sets of complexity . We shall see that equals the Borel -algebra. This implies the claim, since we are taking a union of sets of cardinality continuum over , which itself has cardinality at most continuum.

To check the claim about the Borel -algebra, take a countable collection of sets . Any intersections or unions of these will lie inside an ordinal that is itself countable, thus still in .

Theorem 17 (Sierpinski)There exists a subset such that every line intersects it in exactly two points. (this assumes the continuum hypothesis)

*Proof:* Put the set of lines in in bijection with , denote such lines by . Let be the claim that there exists for all with the following properties:

- Any line in contains at most points from
- The set has cardinality less than the continuum
- The sets are nested: when
- For any , we have , where is the corresponding line

We can clearly start this construction with any two points, and suppose we know the claim for all . Define . This is our candidate set , except perhaps fixing the last requirement. We have

- Each line still has at most two points from
- The cardinality is still less than the continuum, because we took a countable union
- The sets are still nested
- If , note that each with intersects is at most a point, and there are countably many such points. Thus there are plenty of points to choose from, and we can add one or two to to satisfy the last requirement without affecting the previous ones.

By transfinite induction, this construction applies to the collection of all lines.

Theorem 18 (Cantor-Bendixson)Let be a closed subset of (any separable metric space will work). Then is a union of a perfect set and a countable set .

Recall that a set is perfect if it has no isolated points.

*Proof:* For the proof, define a decreasing sequence of sets, indexed by ordinals. Set . For successor ordinals, define

If is a limit ordinal, define

From the definition, is discrete, thus countable. Let be the least ordinal such that has stabilized.

**Claim** We have .

This follows because there is no uncountable intersection of closed sets that is strictly decreasing. This is because there can be no uncountable union of opens that keeps increasing. The last statement follows since there is a countable basis of opens for the topology.

The result follows from the claim , since the set is perfect, and what’s left is a countable union of countable sets.