7.3 Ordinals and Well Ordering

Ordinals are set theoretic objects used to measure order type. Natural numbers measure the size of finite sets, while ordinals measure the structure of well ordered sets. The main idea is that a well ordered set is not only a collection of elements, but a collection arranged so that every nonempty subset has a first element.

Well Ordered Sets

A linear order tells us how to compare any two elements. A well order is a stronger kind of linear order. It requires that every nonempty subset have a least element.

Definition 7.42 (Well Order)

Let $A$ be a set, and let $\leq$ be a linear order on $A$ . The ordered pair:

(A,\leq)

is a well ordered set if every nonempty subset $B \subseteq A$ has a least element.

That is, whenever:

B \subseteq A

and:

B \ne \varnothing

there exists an element $b_0 \in B$ such that:

b_0 \leq b

for every $b \in B$ .

The element $b_0$ is called the least element of $B$ .

Example 7.43

The natural numbers:

\mathbb{N}

with the usual order:

\leq

are well ordered.

Indeed, every nonempty subset of $\mathbb{N}$ has a least element. For example, the subset:

\{5,7,10,100,\dots\}

has least element:

5

This property is one of the basic distinguishing features of the natural numbers.

Example 7.44

The integers:

\mathbb{Z}

with the usual order:

\leq

are not well ordered.

The subset:

\{\dots,-3,-2,-1\}

is nonempty, but it has no least element. For every negative integer in the set, there is a smaller negative integer also in the set.

Thus a linear order need not be a well order.

Example 7.45

The real numbers:

\mathbb{R}

with the usual order are not well ordered.

The subset:

(0,1)

is nonempty, but it has no least element. If $x \in (0,1)$ , then:

\frac{x}{2} \in (0,1)

and:

\frac{x}{2} < x

Therefore no element of $(0,1)$ can be least.

Initial Segments

Initial segments are the parts of an ordered set that lie before a given element. They are important because ordinals are designed so that each ordinal is exactly the set of all smaller ordinals.

Definition 7.46 (Initial Segment)

Let $(A,\leq)$ be a linearly ordered set, and let $a \in A$ . The initial segment determined by $a$ is:

A_{<a}=\{x\in A:x<a\}

Thus $A_{<a}$ consists of all elements of $A$ that occur strictly before $a$ .

Example 7.47

In the natural numbers:

\mathbb{N}=\{0,1,2,3,\dots\}

the initial segment before $4$ is:

\mathbb{N}_{<4}=\{0,1,2,3\}

This example explains why finite ordinals are usually represented by:

0=\varnothing

1=\{0\}

2=\{0,1\}

3=\{0,1,2\}

Each number is identified with the set of all smaller numbers.

Order Isomorphism

Two ordered sets have the same order type if their elements can be matched in a way that preserves and reflects the order.

Definition 7.48 (Order Isomorphism)

Let $(A,\leq_A)$ and $(B,\leq_B)$ be linearly ordered sets. An order isomorphism from $A$ to $B$ is a bijection:

f:A\to B

such that for all $x,y\in A$ :

x\leq_A y \quad \text{if and only if} \quad f(x)\leq_B f(y)

If such a function exists, then $A$ and $B$ are said to have the same order type.

Example 7.49

The ordered sets:

\{0,1,2\}

and:

\{5,8,10\}

with their usual orders have the same order type.

The function:

f(0)=5,\quad f(1)=8,\quad f(2)=10

is a bijection and preserves order.

Thus these two ordered sets are different as sets, but the same as ordered structures.

Lemma 7.50 (Order Isomorphisms Preserve Least Elements)

Let:

f:(A,\leq_A)\to(B,\leq_B)

be an order isomorphism. If $a_0$ is the least element of $A$ , then $f(a_0)$ is the least element of $B$ .

Proof

Let $b\in B$ . Since $f$ is surjective, there exists $a\in A$ such that:

f(a)=b

Since $a_0$ is the least element of $A$ , we have:

a_0\leq_A a

Because $f$ preserves order:

f(a_0)\leq_B f(a)

Since $f(a)=b$ , this gives:

f(a_0)\leq_B b

As $b$ was arbitrary, $f(a_0)$ is the least element of $B$ .

Lemma 7.51 (Order Isomorphism Preserves Well Ordering)

If $(A,\leq_A)$ is well ordered and:

f:(A,\leq_A)\to(B,\leq_B)

is an order isomorphism, then $(B,\leq_B)$ is well ordered.

Proof

Let $C\subseteq B$ be nonempty. We must show that $C$ has a least element.

Consider the preimage:

f^{-1}[C]=\{a\in A:f(a)\in C\}

Since $C$ is nonempty and $f$ is surjective, the set $f^{-1}[C]$ is nonempty. Since $A$ is well ordered, there exists:

a_0\in f^{-1}[C]

such that:

a_0\leq_A a

for every $a\in f^{-1}[C]$ .

We claim that:

f(a_0)

is the least element of $C$ .

Let $c\in C$ . Since $f$ is surjective, there exists $a\in A$ such that:

f(a)=c

Because $c\in C$ , we have $a\in f^{-1}[C]$ . Hence:

a_0\leq_A a

Since $f$ preserves order:

f(a_0)\leq_B f(a)

Thus:

f(a_0)\leq_B c

Therefore $f(a_0)$ is the least element of $C$ , so $B$ is well ordered.

Transitive Sets

Ordinals are usually defined as transitive sets that are well ordered by membership. We first define transitivity.

Definition 7.52 (Transitive Set)

A set $A$ is transitive if every element of an element of $A$ is itself an element of $A$ .

Formally:

A \text{ is transitive} \quad \text{if and only if} \quad \forall x\in A,\ \forall y\in x,\ y\in A

Equivalently:

x\in A \to x\subseteq A

for every $x$ .

Example 7.53

The set:

3=\{0,1,2\}

is transitive, where:

0=\varnothing

1=\{0\}

2=\{0,1\}

Indeed, every element of $3$ is one of:

0,\quad 1,\quad 2

and each of these is a subset of:

3

For example:

2=\{0,1\}\subseteq 3

Example 7.54

The set:

A=\{\{0\}\}

is not transitive.

We have:

\{0\}\in A

and:

0\in \{0\}

but:

0\notin A

Thus $A$ fails the condition for transitivity.

Ordinals

An ordinal is a canonical representative of a well ordered structure. In the standard set theoretic definition, an ordinal is a transitive set that is well ordered by the membership relation.

Definition 7.55 (Ordinal)

A set $\alpha$ is an ordinal if:

$\alpha$ is transitive.
The relation $\in$ well orders $\alpha$ .

Thus, for an ordinal $\alpha$ , its elements are themselves arranged by membership, and every element of $\alpha$ is also a subset of $\alpha$ .

When $\alpha$ and $\beta$ are ordinals, we write:

\beta < \alpha

to mean:

\beta \in \alpha

We write:

\beta \leq \alpha

to mean:

\beta \in \alpha \quad \text{or} \quad \beta=\alpha

Example 7.56

The empty set:

0=\varnothing

is an ordinal.

It is transitive because it has no elements. The membership relation well orders it because every nonempty subset of $\varnothing$ has a least element vacuously, since there are no nonempty subsets.

The next ordinals are:

1=\{0\}=\{\varnothing\}

2=\{0,1\}=\{\varnothing,\{\varnothing\}\}

3=\{0,1,2\}

In general, each finite ordinal is the set of all smaller finite ordinals.

Lemma 7.57 (Elements of Ordinals Are Ordinals)

If $\alpha$ is an ordinal and:

\beta\in\alpha

then $\beta$ is an ordinal.

Proof

Since $\alpha$ is transitive and $\beta\in\alpha$ , we have:

\beta\subseteq\alpha

First we show that $\beta$ is transitive. Let $x\in\beta$ and let $y\in x$ . Since $\beta\in\alpha$ and $\alpha$ is transitive, every element of $\beta$ is an element of $\alpha$ , so:

x\in\alpha

Since $x\in\beta$ and $\beta$ is an element of the well ordered set $\alpha$ , the order on $\alpha$ is given by membership. The fact that $y\in x\in\beta$ places $y$ before $x$ and $x$ before $\beta$ , and transitivity of the membership order inside $\alpha$ gives:

y\in\beta

Thus $\beta$ is transitive.

Next, $\in$ well orders $\beta$ because $\beta$ is a subset of $\alpha$ , and every nonempty subset of $\beta$ is also a nonempty subset of $\alpha$ . Since $\in$ well orders $\alpha$ , every nonempty subset of $\beta$ has a least element. Therefore $\beta$ is an ordinal.

Lemma 7.58 (Ordinals Are Transitive Classes of Smaller Ordinals)

If $\alpha$ is an ordinal, then:

\alpha=\{\beta:\beta \text{ is an ordinal and } \beta<\alpha\}

Proof

By definition:

\beta<\alpha

means:

\beta\in\alpha

Thus every element of $\alpha$ is automatically smaller than $\alpha$ . By Lemma 7.57, every such element is an ordinal.

Conversely, if $\beta<\alpha$ , then by definition:

\beta\in\alpha

Therefore the elements of $\alpha$ are exactly the ordinals smaller than $\alpha$ .

Successor Ordinals

The successor operation extends the operation $n\mapsto n+1$ from natural numbers to all ordinals.

Definition 7.59 (Successor Ordinal)

If $\alpha$ is an ordinal, its successor is:

\alpha+1=\alpha\cup\{\alpha\}

This is also often denoted:

S(\alpha)

The successor $\alpha+1$ contains all elements of $\alpha$ together with $\alpha$ itself.

Example 7.60

Starting from:

0=\varnothing

we get:

1=0+1=0\cup\{0\}=\{0\}

Then:

2=1+1=1\cup\{1\}=\{0,1\}

Then:

3=2+1=2\cup\{2\}=\{0,1,2\}

Thus the finite ordinals are built by repeated successor.

Lemma 7.61 (Successor of an Ordinal Is an Ordinal)

If $\alpha$ is an ordinal, then:

\alpha+1

is an ordinal.

Proof

We must show that $\alpha+1$ is transitive and that membership well orders it.

First, let:

x\in \alpha+1

Then either:

x\in\alpha

or:

x=\alpha

If $x\in\alpha$ , then since $\alpha$ is transitive, we have:

x\subseteq\alpha

and therefore:

x\subseteq \alpha+1

If $x=\alpha$ , then:

x=\alpha\subseteq \alpha+1

Thus every element of $\alpha+1$ is a subset of $\alpha+1$ , so $\alpha+1$ is transitive.

Now we show that membership well orders $\alpha+1$ . Let:

B\subseteq \alpha+1

be nonempty.

If:

B\cap\alpha \ne \varnothing

then $B\cap\alpha$ has a least element because $\alpha$ is well ordered by membership. This least element is also the least element of $B$ , unless $B$ also contains $\alpha$ , but every element of $\alpha$ is before $\alpha$ , so the same least element works for $B$ .

If:

B\cap\alpha=\varnothing

then since $B$ is nonempty and $B\subseteq \alpha+1$ , we must have:

B=\{\alpha\}

and its least element is $\alpha$ .

Hence every nonempty subset of $\alpha+1$ has a least element, so $\alpha+1$ is an ordinal.

Limit Ordinals

Not every ordinal is a successor. Some ordinals collect all earlier stages without being obtained by adding one new last element to a previous ordinal.

Definition 7.62 (Limit Ordinal)

An ordinal $\lambda$ is a limit ordinal if:

\lambda\ne 0

and there is no ordinal $\alpha$ such that:

\lambda=\alpha+1

Thus a nonzero limit ordinal has no immediate predecessor.

Example 7.63

The set of all finite ordinals:

\omega=\{0,1,2,3,\dots\}

is an ordinal.

It is the first infinite ordinal. It is a limit ordinal because it is not $0$ and it is not the successor of any finite ordinal.

Every finite ordinal appears in $\omega$ , but there is no largest finite ordinal. Hence $\omega$ is not obtained by adding one final element after all finite ordinals.

Lemma 7.64 (Union of Ordinals)

If $A$ is a set of ordinals, then:

\bigcup A

is transitive.

If, in addition, $A$ is nonempty and its elements are linearly ordered by membership, then:

\bigcup A

is an ordinal.

Proof

First we prove transitivity. Let:

x\in \bigcup A

Then there exists an ordinal $\alpha\in A$ such that:

x\in\alpha

Since $\alpha$ is transitive:

x\subseteq\alpha

Since:

\alpha\subseteq \bigcup A

we get:

x\subseteq \bigcup A

Thus $\bigcup A$ is transitive.

Now assume that $A$ is nonempty and linearly ordered by membership. Let:

B\subseteq \bigcup A

be nonempty. Choose:

b\in B

Since $b\in \bigcup A$ , there exists $\alpha\in A$ such that:

b\in\alpha

Then:

B\cap\alpha

is a nonempty subset of $\alpha$ . Since $\alpha$ is an ordinal, it is well ordered by membership, so $B\cap\alpha$ has a least element, say:

b_0

We claim that $b_0$ is least in $B$ . Let $c\in B$ . Since $c\in \bigcup A$ , there exists $\gamma\in A$ such that:

c\in\gamma

Since $A$ is linearly ordered by membership, either:

\gamma\in\alpha

or:

\gamma=\alpha

or:

\alpha\in\gamma

In the first two cases, $c\in\gamma$ implies $c\in\alpha$ because $\alpha$ is transitive or equal to $\gamma$ , so $c\in B\cap\alpha$ , and therefore:

b_0\leq c

In the third case, $\alpha\in\gamma$ . Since $b_0\in\alpha$ , we have:

b_0\in\alpha\in\gamma

and the ordering inside $\gamma$ places $b_0$ before every element of $\gamma$ that is not before $b_0$ . In particular the well ordering by membership gives that $b_0$ is no later than $c$ .

Thus every nonempty subset of $\bigcup A$ has a least element, and so $\bigcup A$ is an ordinal.

Ordinal Comparison

Ordinals are comparable. This is one of the main reasons they are useful as canonical order types.

Theorem 7.65 (Trichotomy of Ordinals)

For any ordinals $\alpha$ and $\beta$ , exactly one of the following holds:

\alpha\in\beta

\alpha=\beta

\beta\in\alpha

Equivalently, exactly one of:

\alpha<\beta,\quad \alpha=\beta,\quad \beta<\alpha

holds.

Proof

The proof uses the fact that ordinals are transitive and well ordered by membership.

Consider:

\alpha\cap\beta

If:

\alpha=\beta

there is nothing to prove. Suppose:

\alpha\ne\beta

Then by extensionality, either there is an element of $\alpha$ not in $\beta$ , or there is an element of $\beta$ not in $\alpha$ .

Assume first that:

\alpha\setminus\beta\ne\varnothing

Since $\alpha$ is well ordered by membership, the set $\alpha\setminus\beta$ has a least element, say $\gamma$ . One shows that:

\gamma=\beta

Indeed, all elements of $\gamma$ must lie in $\beta$ , by minimality of $\gamma$ , and all elements of $\beta$ lie in $\gamma$ , otherwise the first disagreement would occur earlier. Hence $\gamma=\beta$ . Since $\gamma\in\alpha$ , we get:

\beta\in\alpha

Similarly, if:

\beta\setminus\alpha\ne\varnothing

then the least element of $\beta\setminus\alpha$ is $\alpha$ , and hence:

\alpha\in\beta

The three alternatives are mutually exclusive because membership on an ordinal is irreflexive and transitive.

Corollary 7.66 (Ordinals Are Linearly Ordered by Membership)

The class of ordinals is linearly ordered by:

<

where:

\alpha<\beta \quad \text{means} \quad \alpha\in\beta

Proof

By Theorem 7.65, any two ordinals are comparable. Since the alternatives are mutually exclusive, this comparison gives a linear order.

Transfinite Induction

Ordinals support induction beyond the natural numbers. This is called transfinite induction.

Theorem 7.67 (Transfinite Induction)

Let $P(\alpha)$ be a property of ordinals. Suppose that for every ordinal $\alpha$ , the following implication holds:

\bigl(\forall \beta<\alpha,\ P(\beta)\bigr)\to P(\alpha)

Then:

P(\alpha)

holds for every ordinal $\alpha$ .

Proof

Suppose, for contradiction, that $P(\alpha)$ fails for some ordinal $\alpha$ . Let:

C=\{\alpha:P(\alpha) \text{ fails}\}

be the class of counterexamples. Choose a counterexample $\alpha_0$ that is least among all counterexamples. This is justified by the well ordering of ordinals below any given counterexample.

Then for every:

\beta<\alpha_0

the property $P(\beta)$ holds, because $\alpha_0$ was chosen least among counterexamples. Therefore:

\forall \beta<\alpha_0,\ P(\beta)

By the hypothesis of the theorem, this implies:

P(\alpha_0)

This contradicts the choice of $\alpha_0$ as a counterexample. Therefore no counterexample exists, and $P(\alpha)$ holds for every ordinal $\alpha$ .

Transfinite Recursion

Ordinals also support recursive definitions in which the value at stage $\alpha$ is allowed to depend on all earlier stages.

Principle 7.68 (Transfinite Recursion)

Suppose that a rule $F$ assigns an object from each function whose domain is an ordinal. Then there exists a unique function $G$ defined on the ordinals such that:

G(\alpha)=F(G\upharpoonright \alpha)

for every ordinal $\alpha$ .

Here:

G\upharpoonright \alpha

denotes the restriction of $G$ to all ordinals smaller than $\alpha$ .

This principle says that to define an object at stage $\alpha$ , it is enough to know the objects already defined at all earlier stages.

Example 7.69

The sequence of finite ordinals can be defined recursively by:

0=\varnothing

and:

n+1=n\cup\{n\}

The same pattern extends beyond finite stages. At a limit stage such as $\omega$ , the object is obtained by collecting all earlier stages:

\omega=\bigcup_{n\in\mathbb{N}} n

This illustrates the general shape of transfinite constructions: successor stages add a new step, while limit stages collect what came before.

Well Ordering Theorem

The well ordering theorem states that every set can be well ordered. This result is equivalent to the axiom of choice, so it is not proved from the basic axioms alone without additional assumptions.

Theorem 7.70 (Well Ordering Theorem)

Every set admits a well ordering.

That is, for every set $A$ , there exists a relation $\leq$ on $A$ such that:

(A,\leq)

is a well ordered set.

Consequence 7.71

Every set has the same cardinality as some ordinal.

Indeed, if $A$ can be well ordered, then its well ordered structure has an order type, and that order type is represented by a unique ordinal. This is one reason ordinals are central in set theory: they provide canonical representatives for well ordered structures.