Ordinals - Descriptive Set Theory

It will be important for us to extend the usual counting process beyond the natural numbers. To give an example, let us return for a moment to perfect subsets of the reals. To show that every uncountable closed subset of $\mathbb{R}$ contains a perfect subset, we considered the condensation points of the set. There is another, more constructive way, to arrive at a perfect subset. When Cantor studied convergence of Fourier series, he introduced the derivative of a set:

A' = \{ x \in A \colon x \text{ is a limit point of } A\}

(1)

We can iterate the derivative and consider $A^\prime, A^{\prime\prime}, A^{\prime\prime\prime}, \dots$ . This yields a descending sequence of sets

A^\prime \supseteq A^{\prime\prime} \supseteq A^{\prime\prime\prime} \supseteq \dots \supseteq A^{(n)} \supseteq \dots

(2)

As the sequence is nested, we can take a “limit”:

A^{\infty} = \bigcap_n A^{(n)}

(3)

But the process does not necessarily stop here. $A^\infty$ may have isolated points again, so that $A^\infty \supsetneq (A^\infty)^\prime$ .

Let us introduce ${\omega}$ as a new number to be used in place of $\infty$ above. We can continue the counting process:

1,2,3, \dots, \omega, \omega+1, \omega+2, \dots, \omega + \omega, \omega + \omega +1, \dots, \omega + \omega + \omega, \dots, \omega\cdot \omega, \dots

(4)

We can then define, for example, $A^{\omega+1} := (A^{\omega})'$ . As intuitively clear from above, the new transfinite numbers come with a natural ordering, so we can put, for example, $A^{\omega+\omega} := \bigcap_{\alpha < \omega+\omega} A^{\alpha}$ .

To obtain a perfect subset, one can show that the above process of taking derivatives, eventually reaches a fixed point: some stage $\alpha$ for which $(A^{\alpha})' = A^\alpha$ . If $A$ is uncountable, $A^\alpha$ will be a perfect subset, since one can show that at each derivative step we remove an at most countable set and it will take at most countably many steps to reach the fixed point. But what does “countably many steps” exactly mean if we have to count past $\omega$ ? The formal notions of ordinal and cardinal numbers will answer this question.

The fundamental concept on which the ordinal numbers are based if that of a well-order.

Orders and well-orders¶

With any reflexive partial order $\leq$ we can associate an irreflexive or strict partial order by letting

a < b \quad :\iff \quad a \leq b \; \wedge \; a \neq b.

(5)

Likewise, we can obtain a reflexive order from a strict one by defining

a \leq b \quad :\iff \quad a < b \; \vee \; a = b.

(6)

We will use $\leq$ or similar symbols to indicate the order is reflexive, while $<$ , $\prec$ , etc. are reserved for strict orders.

We can enumerate the natural numbers one after another, but for the other standard ordered number domains this is not possible: We cannot find a place to begin counting (as in the case of $\mathbb{Z}$ ) or there is no “next bigger” element (as in the case of $\mathbb{Q}$ or $\mathbb{R}$ ).

To enumerate these domains in the form $\{a_0, a_1,\ldots, a_n, a_{n+1}, \ldots \}$ we have to reorder them in a way that

we can start with a smallest element,

and once we have arrived at an element $a$ ,

we know with which element we continue the enumeration (i.e. there is an immediate successor to $a$ ),
we can continue the enumeration even if we have already enumerated infinitely many elements before $a$ (but elements of the domain still remain).

These requirements can be combined into a single property: every non-empty subset (i.e. the elements not enumerated yet) has a least element (to be enumerated next).

Orders themselves can be compared using embeddings.

Of course every order is isomorphic to itself (automorphic) via the identity. But many orders allow automorphisms other than the identity (e.g. $\mathbb{Z}$ or $\mathbb{R}$ with $z \mapsto z+1$ ). As we will see, well-orders are very rigid in this regard.

We start with a simple observation.

Proof

If the set $\{x \in A \colon f(x) < x\}$ is non-empty, it has a minimal element $z$ . But since $f$ is increasing, this would imply $f(f(z)) < f(z)$ , contradicting the minimality of $z$ .

We immediately obtain

An initial segment of an order $(A,<)$ is given by all elements that are smaller than a given element $b$ . We denote this initial segment by $A\mid_b$ .

Proof

Suppose $f: A \to A\mid_b$ is an isomorphism. Then $\operatorname{ran}(f) = A\mid_b$ and $f(x) < b$ for all $x \in A$ . In particular, $f(b) < b$ , contradicting Proposition 1.

Ordinal numbers¶

Cantor defined ordinal numbers (or ordinals) as isomorphism classes of well-orders. Later, von Neumann suggested a system of representatives particularly suitable for set theoretic considerations. The idea is to define the order $<$ through the $\in$ -relation on a set. For example,

\{ \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}

(10)

represents a 3-element well-order.

We will impose some conditions on the sets we allow as ordinals. Given a set $A$ , we use $\in_A$ to denote the $\in$ -relation on $A$ :

\in_A = \{ (x,y) \colon x,y \in A \; \wedge \; x \in y \}

(11)

In other words, transitive sets cannot “hide” elements in subsets.

It is customary to use lower case Greek letters $\alpha, \beta, \gamma, \dots$ to denote ordinals.

If we exclude certain pathological sets from the beginning, we can further simplify this definition.

Sets which contain themselves ( $A \in A$ ) are not well-founded $-$ $\{A\}$ would be a subset without a $\in$ -minimal element. Similarly, well-founded sets cannot have cycles like $a \in b \in c \in a$ .

If we write out the formulas in full, we see the characterization given in Proposition 2 is much simpler than the original one. Most notably, in Proposition 2 we only use only bounded quantifiers (of the form $\forall y \in a$ ), whereas in the original form we have to quantify over arbitrary subsets of $a$ . This is an important difference whose impact will become clear later on.

Proof

Let ${\alpha}$ be an ordinal, and assume $b \in \alpha$ . Any subset of a linear order is again a linear order under the induced order relation. It remains to show that $(b, \in_b)$ is transitive (as a set). Let $x \in c \in b$ . We claim $x \in b$ . Since ${\alpha}$ is transitive, $b \subseteq \alpha$ and hence $c \in \alpha$ . By transitivity of ${\alpha}$ again, $x \in \alpha$ . Thus $x,b \in \alpha$ , and since $\in_\alpha$ linearly orders ${\alpha}$ , we must have

x \in b \; \vee \; x = b \; \vee \; b \in x.

(13)

If $x = b$ , we get $b \in c \in b$ , contradicting well-foundedness. Similar for $b \in x$ . Therefore, $x \in b$ .

The well-ordering of ordinals¶

Proposition 3 suggests we can order ordinals by letting

\alpha < \beta \; :\iff \; \alpha \in \beta.

(14)

By Proposition 3, an ordinal then contains precisely the ordinals smaller than it:

\alpha = \{ \beta : \beta < \alpha \}.

(15)

$\in$ defines a partial order on all ordinals: As all sets are well-founded, irreflexivity holds, and since ordinals are transitive sets, $<$ is a transitive relation.

Proof

The $\Rightarrow$ direction follows directly from the transitivity of ordinals. For $\Leftarrow$ , we show something more general, namely that any transitive proper subset of an ordinal is itself an ordinal and is an element of the superset ordinal:

\Op{trans}(a) \; \wedge \; a \subset \beta \quad \Rightarrow \quad \Op{Ord}(a) \; \wedge \; a \in \beta.

(18)

If $a \subset \beta$ , $a$ is linearly ordered by $\in$ (as a subset of ${}\beta$ ). Further, if $a$ is transitive, $a$ is an ordinal.

It remains to show $a \in \beta$ . Since $a$ is a proper subset of ${}\beta$ , by well-foundedness there exists a $\in$ -minimal element of $\gamma \in \beta \setminus a$ . We claim $a = \gamma$ . By $\in$ -minimality of ${}\gamma$ , every element of ${}\gamma$ cannot be in $\beta\setminus a$ and therefore has to be in $a$ . Hence $\gamma \subseteq a$ . On the other hand, if $x \in a$ , then, by assumption $x \in \beta$ , and since $\in$ linearly orders ${}\beta$ ,

x \in \gamma \; \vee \; x = \gamma \; \vee \; \gamma \in x.

(19)

The latter two are impossible due to $\gamma \notin a$ . Hence $x \in \gamma$ and therefore $a \subseteq \gamma$ , yielding $a =\gamma$ .

Proof

We first show $<$ is a linear order. Irreflexivity follows from well-foundedness of $\in$ . Transitivity of $<$ follow from the transitivity of ordinals as sets. To show

\alpha < \beta \; \vee \; \alpha = \beta \; \vee \; \beta < \alpha,

(20)

observe that the intersection of two ordinals is an ordinal, the minimum of the two ordinals. Let $\gamma = \alpha \cap \beta$ . Then $\gamma \subseteq \alpha$ , so by Proposition 4, $\gamma \in \alpha$ or $\gamma = \alpha$ and similarly $\gamma \in \beta$ or $\gamma = \beta$ . But in the case $\gamma \in \alpha, \gamma \in \beta$ we would have $\gamma \in \alpha \cap \beta = \gamma$ , contradicting well-foundedness.

Finally, if $A$ is a non-empty set of ordinals, the well-ordering condition on $<$ spells out as

\exists \alpha \in A \; \forall \beta \in A \; \; \beta \notin \alpha.

(21)

But this holds since we assume all sets are well-founded.

Basic properties of ordinals¶

Using the results obtained so far, we can now deduce some basic facts about the structure of ordinals:

$0 = \emptyset$ is the smallest ordinal.
Every ordinal ${\alpha}$ has an immediate successor under the ordering $<$ :
$\alpha' = \alpha+1 = \alpha \cup \{\alpha\}.$
(22)
Clearly $\alpha < \alpha+1$ . If $\alpha < \beta$ , then by Proposition 4, $\alpha \subset \beta$ and $\alpha \in \beta$ . Hence $\alpha+1 \subseteq \beta$ and therefore $\alpha+1 \leq \beta$ .
The finite ordinals are exactly the natural numbers (“set theoretic version”):

0 = \emptyset, \quad 1 = 0 + 1 = \emptyset \cup \{\emptyset\} = \{\emptyset\}, \quad 2 = 1+1 = \{\emptyset, \{\emptyset\} \}, \dots

(23)

The set of all natural numbers is transitive and well-ordered by $\in$ and thus itself an ordinal, the first infinite ordinal ${\omega}$ :
$\omega = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \dots \}$
(24)
${\omega}$ is also the first instance of a limit ordinal: A successor ordinal is any ordinal of the form $\alpha+1$ . Any ordinal ${\lambda}$ that is not a successor is called a limit ordinal. Being limit is equivalent to the following property:
$\lambda \neq 0 \: \wedge \: \forall \alpha < \lambda \; (\alpha+1 < \lambda).$
(25)
This shows immediately that ${\omega}$ is limit.
More generally, if $A$ is a set of ordinals, $\sup A = \bigcup_{\alpha \in A} \alpha$ is an ordinal and is the least upper bound for $A$ .
The first limit ordinal ${\omega}$ is followed by a number of successor ordinals as well as their limits as limit ordinals:

\begin{gather*} \omega, \omega+1, \omega+2, \ldots \omega+\omega, \omega+\omega+1, \omega + \omega+2, \ldots \omega+\omega+ \omega, \qquad \quad \\ \omega + \omega+ \omega+1, \omega + \omega+ \omega+2, \ldots \omega \cdot \omega, \omega \cdot \omega +1,\ldots, \omega^{\omega} \ldots \omega^{\omega^{\omega}} \ldots \end{gather*}

(26)

All of the ordinals listed here are still countable (as sets). The supremum of the set of all countable ordinals is denoted by $\omega_1$ , the first uncountable ordinal. After $\omega_1$ , we have again successors, limits, and so on.

Metamathematical issues¶

Is there a set $\Ord$ of all ordinals? If so, it would be well-ordered by $\in$ and also transitive (since, by Proposition 3, every element of an ordinal is an ordinal) and therefore an ordinal. Hence we would have $\Ord \in \Ord$ . But no ordinal can be an element of itself. This holds even if we do not assume every set is well-founded, since ordinals are by definition strictly ordered by $\in$ .

This is known as the Anomaly of Burali-Forti. It tells us that somehow the collection of all ordinals is too big to form a set. It also warns us that if we handle the intuitive concept of a set too carelessly, it might lead to contradictions and inconsistencies.

Later on we will develop an axiomatic approach to sets which aims to exclude antinomies like this. In this framework, we will be able to formally show that $\Ord$ is not a set. It forms what we will call a proper class.

Representing well-orders as ordinals¶

We introduced ordinals with the goal to have a specific representation for any well-order.

The ordinal ${\alpha}$ is called the order type of $(A,<)$ . We will delay the proof of this theorem for a while, until we learn how to extend induction and recursion into the transfinite. This will, in particular, give us the following generalization of the usual induction principle for the natural numbers.

Of course, informally one would prove this as follows: If $P$ does not hold for some ordinal, since the ordinals are well-ordered, there has to be a least ordinal ${}\alpha$ for which $P$ does not hold. But then each of the three cases (0, successor, or limit ordinal) would lead to a contradiction based on the assumption.

However, we have seen that there is no set of all ordinals, so we have to tread a little carefully here. We will take this up again once we have developed an axiomatic foundation for sets.

Descriptive Set Theory

Perfect Subsets of the Real Line

Ordinals and cardinals

The Axiom of Choice