Ordinals (the basics)

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 {\sigma}-algebra has the cardinality of the continuum
  • (Sierpinski) There is a set {A} in the plane such that every line intersects it in exactly two points
  • (Cantor-Bendixson) Any closed subset of {{\mathbb R}} 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 {\prec} on a set {X} is a binary relation satisfying

  • (totality) For any {x,y\in X}, exactly one of the following holds: {x\prec y} or {x=y} or {y\prec x}
  • (transitivity) If {x\prec y} and {y\prec z} then {x\prec z}

Definition 2 A linear order on a set {X} is a well-ordering if any subset {S\subset X} has a minimal element.

Example 1 With the natural orderings, {{\mathbb Z}} is not well-ordered whereas {{\mathbb N}} is.

Consider from now on a well-ordered set {X}.

Definition 3 An initial segment {I\subset X} is a subset such that {\forall x,y\in X}, if {x\prec y} and {y\in I}, then {x\in I}. For a given element {x\in X}, the associated initial segment {I_x} is the set

\displaystyle  I_x:=\{y\in X\mid y\prec x\}

Proposition 4 Any initial segment {I\subset X} is the initial segment associated to some element {x\in X}.

Proof: Take {S:=X\setminus I}. This set has a smallest element {x}, and then {I=I_x}. \Box

Proposition 5 Suppose {X,Y} are two well-ordered sets. If {f,g:X\rightarrow Y} are two order-preserving bijections, then {f=g}.

Proof: Take the smallest {x} such that {f(x)\neq g(x)} and assume {f(x)\prec g(x)}. There must be an {x'} such that {g(x')=f(x)}, so necessarily {x'\prec x}. But this implies {g(x')=f(x')}, which yields {f(x')=f(x)}, leading to a contradiction. \Box

Proposition 6 A well-ordered set {X} 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. \Box

Remark 1 The condition on the segment is crucial, as there are many order-preserving maps {\phi:{\mathbb N}\rightarrow {\mathbb N}}.

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

Theorem 7 Suppose {X} and {Y} 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 {x\in X, y\in Y}, define the binary relation {xRy} if {I_x\cong I_y} as well-ordered sets. Think of {R} as the graph of a hypothetical function {F:X\rightarrow Y} or the other way around. For any {x}, there is at most one {y} such that {xRy} (and similarly for elements of {Y}), so the hypothetical {F} is well-defined. Moreover it is well-defined on some initial segments of {X} and {Y}. If either initial segment is proper, we get the desired embedding. If both are proper, they would be of the form {I_{x_0}} and {I_{y_0}}, which would imply {x_0 R y_0}, contradicting the assumption on the initial segments. \Box

— 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. {\alpha,\beta,\gamma}.

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

Theorem 9 Let {S} be a collection of ordinals. There exists a smallest element {\alpha\in S}.

Proof: Take some {\beta\in S}. For any {\gamma \in S} such that {\gamma \prec \beta}, take {x_\gamma\in \beta} such that {\gamma\cong I_{x_\gamma}}. This collection of elements of {\beta} has a unique minimal element, corresponding to some {\alpha \in S}. \Box

— 3. Operations on Ordinals —

Definition 10 Given an ordinal {\alpha}, define its successor {\alpha'=\alpha\cup \{*\}}, with the same order structure, but with {*} greater than anything else. Given a collection {\{\alpha_i\}_{i\in I}} of ordinals, let

\displaystyle \vee_{i\in I} \alpha_i

be the smallest ordinal that’s bigger than all the {\alpha_i}‘s.

Remark 4 For any ordinal {\alpha}, take the collection of ordinals {\{\beta\mid \beta<\alpha\}}. If it has a largest element, {\alpha} is a successor ordinal. Otherwise, it’s called a limit ordinal.

Example 2 Denote by {\omega} the first infinite ordinal, namely {{\mathbb N}} with the usual order structure. We also have the finite ordinals, denoted {1,2,3,\ldots}.

Definition 11 Given two ordinals {\alpha,\beta}, define the following operations

  • {\alpha+\beta} is the ordinal whose underlying set is {\alpha \coprod \beta}, and in addition to the initial relations, all elements of {\alpha} are less than any element of {\beta}.
  • {\alpha\cdot\beta} is the ordinal given by lexicographic order on {\beta\times\alpha}. One can think of it as {\beta} copies of {\alpha}.

Example 3 Some examples to illustrate the concepts are

\displaystyle 1+\omega = \omega

\displaystyle \omega+1 = \omega'

\displaystyle 2\cdot \omega = \omega

\displaystyle \omega\cdot 2 = \omega+\omega

Remark 5 Given a collection of ordinals {\alpha_i} indexed itself by an ordinal {\beta}, one can form their sums and products

\displaystyle  \sum_{i\in \beta} \alpha_i

and

\displaystyle  \prod_{i\in\beta} \alpha_i

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 {3}-manifolds has ordinal type {\omega^\omega}). 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 {\alpha_1,\alpha_2,\ldots} is a countable collection of countable ordinals, there exists a countable ordinal {\beta} such that {\alpha_i\prec \beta} for any {i}.

Proof: One can take {\beta:=\alpha_1+\alpha_2+\cdots}. \Box

Theorem 14 There exists an uncountable ordinal, denoted {\omega_1}, such that {\forall x\in \omega_1}, the initial segment {I_{x}} is countable.

Proof: Take some uncountable ordinal {\alpha} and consider in it the collection of all {y} such that {I_y} is uncountable. Either this set is empty, in which case {\omega_1:=I_y}, or it has a smallest element {x}, in which case {\omega_1:=I_x}. Alternatively, one can define {\omega_1} to be the limit of all countable ordinals. \Box

The following results will be useful when dealing with the Borel {\sigma}-algebra.

Proposition 15 Any countable set {A\subset \omega_1} has an upper bound in {\omega_1}.

Proof: Consider {\cup_{a\in A} I_a}. This is a countable union of countable sets, so itself countable. Thus it cannot be all of {\omega_1}. \Box

— 5. Applications —

Principle of transfinite induction

Suppose {X} is a set in bijection with some ordinal {\theta}. Denote by {x_\alpha} elements of {x} corresponding to some {\alpha\in \theta} (viewed itself as a ordinal, via the initial segment construction).

Suppose {P(x)} is some proposition with the property that whenever {P(x_\beta)} is true for all {\beta \prec \alpha}, then {P(x_\alpha)} is true as well.

If we know that {P} holds for the smallest element of {X}, the principle of transfinite induction implies that {P(x)} is true for all {x\in X}.

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 {f(x)} for the elements of an ordinal. Suppose further that we know how to do it for the smallest element, and from the knowledge of {f(\beta)} for all {\beta\prec\alpha} we know how to define {f(\alpha)}. Then {f(x)} can be defined for all elements of the ordinal.

Theorem 16 The Borel {\sigma}-algebra of {[0,1]} 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 {1}. The sets of complexity {\alpha} are those that can be written as countable unions and intersections of sets {A_i} of complexity {\beta_i}, with {\beta_i<\alpha} for all {i}.
Denote by {X_\alpha} the sets of complexity {\alpha}. We shall see that {\cup_{\alpha\in\omega_1} X_\alpha} equals the Borel {\sigma}-algebra. This implies the claim, since we are taking a union of sets of cardinality continuum over {\omega_1}, which itself has cardinality at most continuum.
To check the claim about the Borel {\sigma}-algebra, take a countable collection of sets {A_j\in X_{\alpha_j}}. Any intersections or unions of these will lie inside an ordinal that is itself countable, thus still in {\omega_1}. \Box

Theorem 17 (Sierpinski) There exists a subset {X\subset {\mathbb R}^2} such that every line intersects it in exactly two points. (this assumes the continuum hypothesis)

Proof: Put the set of lines in {{\mathbb R}^2} in bijection with {\omega_1}, denote such lines by {L_\delta}. Let {P(\beta)} be the claim that there exists {X_\gamma\subset {\mathbb R}^2} for all {\gamma\preceq\beta} with the following properties:

  • Any line in {{\mathbb R}^2} contains at most {2} points from {X_\beta}
  • The set {X_\beta} has cardinality less than the continuum
  • The sets are nested: {X_\gamma\subseteq X_\beta} when {\gamma\preceq \beta}
  • For any {\delta\preceq \beta}, we have {|L_\delta\cap X_\beta|=2}, where {L_\delta} is the corresponding line

We can clearly start this construction with any two points, and suppose we know the claim for all {\beta\prec \alpha}. Define {Y_\alpha:=\cup_{\beta\prec \alpha}X_\beta}. This is our candidate set {X_\alpha}, except perhaps fixing the last requirement. We have

  • Each line still has at most two points from {Y_\alpha}
  • The cardinality is still less than the continuum, because we took a countable union
  • The sets are still nested
  • If {|L_\alpha\cap Y_\alpha|<2}, note that each {L_\delta} with {\delta\prec\alpha} intersects {L_\alpha} 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 {Y_\alpha} to satisfy the last requirement without affecting the previous ones.

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

Theorem 18 (Cantor-Bendixson) Let {F} be a closed subset of {{\mathbb R}} (any separable metric space will work). Then {F} is a union of a perfect set {P} and a countable set {C}.
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 {F_1=F}. For successor ordinals, define

\displaystyle  F_{\alpha'}:=\{\textrm{limit points of }F_\alpha\}

If {\alpha} is a limit ordinal, define

\displaystyle  F_{\alpha} := \bigcap_{\beta\prec\alpha}F_\beta

From the definition, {F_{\alpha'}\setminus F_\alpha} is discrete, thus countable. Let {\mu} be the least ordinal such that {F_\mu} has stabilized.
Claim We have {\mu\prec\omega_1}.
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 {\mu\prec \omega_1}, since the set {F_\mu} is perfect, and what’s left is a countable union of countable sets. \Box

Advertisements

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