Ordinals

1. The idea of an ordinal

Certain constructions in set theory go beyond the finite. For example in the construction of the cumulative hierarchy we defined $V_{0} = \emptyset$ and $V_{i + 1} = P (V_{i})$ . But we also said we would collect together previous levels ever so often at limit stages. The idea of ordinal is a generalisation of counting number that includes infinite values or limits, in which we can make these constructions precise.

The formal definition is precise but not very instructive.

Definition.

An ordinal is (possibly empty) set $α$ which is transitive and on which the membership relation $\in$ defines a linear order:

$\forall x \in α \forall y \in α \forall z \in α (x \in y \land y \in x \to x \in z)$
$\forall x \in α \forall y \in α (x \in y \lor x = y \lor y \in x)$

(We don't need the irreflexivity axiom $\forall x \in α x \notin x$ as this holds for all sets $x$ .)

The relation $\in$ restricted to an ordinal $α$ is often written $<$ . It is a well-order, meaning that it is a linear order such that for every nonempty subset $x \subseteq α$ the set $x$ has a $<$ -least element. (This is an easy application of foundation together with transitivity. By foundation, there is $β \in x$ with $β \cap x = \emptyset$ and if also $γ < β$ then $γ \in α$ by transitivity of $α$ and hence $γ \notin x$ . Thus $β$ is the $<$ -least element of $x$ .)

A better view of ordinals, but one that at this stage one that has to be regarded as rather informal, is that they represent the well-orders in some canonical way. Indeed an ordinal is well-ordered as we have just seen, no two distinct ordinals are isomorphic as linear orderd, and also (as it turns out) any well-order is order-isomorphic to some ordinal.

2. Examples and preliminary results

Proposition.

$\emptyset$ is an ordinal.

Proof.

Easy

We denote $\emptyset$ by $0$ .

Proposition.

If $α$ is an ordinal then so is $s (α) = α \cup \{α\}$ .

Proof.

If $x \in y \in α \cup \{α\}$ then either $y = α$ so $x \in α \subseteq α \cup \{α\}$ or $y \in α$ so $x \in α \subseteq α \cup \{α\}$ by transitivity of $α$ . Hence $s (α)$ is transitive.

If $x, y, z \in α \cup \{α\}$ and $x \in y \in z$ then by checking all the cases ( $z = α$ or not) we find $x \in z$ as required for transitivity of $\in$ or else $x, y, z \in α$ from which $x \in z$ follows as $α$ is an ordinal.

If $x, y \in α \cup \{α\}$ then by checking all the cases ( $x, y = α$ or not) we find $x \in y$ or $x = y$ or $y \in x$ as required for transitivity of $\in$ , or else $x, y \in α$ from which one of the three possibilities follows as $α$ is an ordinal.

We write $1, 2, 3, \dots$ for $s (0), s (1), s (2), \dots$ . We write $α + 1$ for $s (α)$ . We also use the relation $<$ for $\in$ when looking at elements of an ordinal.

Proposition.

If $α, β$ are ordinals then $α \cap β$ is an ordinal.

Proof.

Easy.

Proposition.

If $x \in α$ where $α$ is an ordinal then $x$ is an ordinal.

Proof.

Transitivity of $x$ follows from $\in$ being transitive on $α$ and $α$ being transitive. The other properties are easy.

Proposition.

If $α, β$ are ordinals then either $α \subseteq β$ or $β \subseteq α$ .

Proof.

Assume first that $α \cap β$ is a proper subset of $α$ . Then there is a least $γ$ in $α ∖ α \cap β$ . If $δ \in γ \in α$ then $δ \in α$ and $δ < γ$ so $δ \in α \cap β$ by minimality of $γ$ . So $γ \subseteq α \cap β$ . Conversely if $δ \in α \cap β$ then with $γ, δ$ both being elements of $α$ we must have $δ \in γ$ , $δ = γ$ , or $γ \in δ$ . The second of these gives $γ = δ \in α \cap β$ contradicting the choice of $γ$ , and the third gives $γ \in δ \in α \cap β$ hence $γ \in α \cap β$ , likewise. Therefore $δ \in γ$ and thus $α \cap β \subseteq γ$ and these are equal. In particular from $γ \in α$ we have $α \cap β \in α$ .

Similarly if $α \cap β$ is a proper subset of $β$ we deduce that $α \cap β \in β$ . Thus we cannot have $α \cap β$ is both proper subset of $α$ and of $β$ else $α \cap β \in α \cap β$ contradicting foundation.

Proposition.

If $α, β$ are ordinals then either $α = β$ or $α \in β$ or $β \in α$ .

Proof.

Suppose $α \subseteq β$ but that these are not the same. The by the proof of the preceding result the least $γ \in β ∖ α$ is $α$ itself, so $α \in β$ .

Proposition.

If $α$ is a nonzero ordinal then $0 \in α$ .

Proof.

By the previous proposition, either $α \in 0$ or $0 \in α$ , and of course the first of these is absurd.

Proposition.

If $x$ is a set of ordinals then $⋃ x$ is an ordinal.

Proof.

Exercise.

Proposition.

If $α$ is an ordinal and $x \in α$ then $x + 1 \in α$ or $x + 1 = α$ .

Proof.

If $x \in α$ then $x$ is an ordinal and $x + 1 = α$ or $x + 1 \in α$ or $α \in x + 1$ . We just have to show the last cannot happen. But if $α \in x \cup \{x\}$ then $α = x \in α$ or $α \in x \in α$ , both of which contradict foundation.

Proposition.

Any ordinal $α$ is exactly one of: zero, 0; a successor ordinal, $β + 1$ for some ordinal $β$ ; a limit ordinal, a non-zero ordinal $λ$ such that for each $x \in λ$ we have $x + 1 \in λ$ .

Proof.

If $α$ is neither zero nor a successor ordinal it must be a limit, by the previous proposition. It is easy to check that the three alternatives are mutually exclusive.