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 1 A 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 2 A linear order on a set is a well-ordering if any subset has a minimal element.
Example 1 With the natural orderings, is not well-ordered whereas is.
Consider from now on a well-ordered set .
Definition 3 An initial segment is a subset such that , if and , then . For a given element , the associated initial segment is the set
Proposition 4 Any initial segment is the initial segment associated to some element .
Proof: Take . This set has a smallest element , and then .
Proposition 5 Suppose 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 6 A 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 1 The 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).
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 8 An ordinal is an equivalence class of well-ordered sets.
Remark 2 As 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 3 Theorem 7 allows us to introduce an ordering on the ordinals themselves, making them into a well-ordered class.
Theorem 9 Let 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 10 Given an ordinal , define its successor , with the same order structure, but with greater than anything else. Given a collection of ordinals, let
be the smallest ordinal that’s bigger than all the ‘s.
Remark 4 For 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 2 Denote by the first infinite ordinal, namely with the usual order structure. We also have the finite ordinals, denoted .
Definition 11 Given 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 3 Some examples to illustrate the concepts are
Remark 5 Given a collection of ordinals indexed itself by an ordinal , one can form their sums and products
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 12 An ordinal is called countable if its underlying set is countable.
Proposition 13 If is a countable collection of countable ordinals, there exists a countable ordinal such that for any .
Proof: One can take .
Theorem 14 There 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 15 Any 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 .
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 16 The 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.