Set Theory/Ordinals

Axioms used. Unless stated otherwise, we work in ZF. We do not use Choice or Regularity on this page. Replacement is used for Transfinite Recursion and the Rank/Height theorem for well-founded relations.

The definition of ordinal numbers offers little insight into their nature. In situations like this pure mathematicians create representations of the objects they wish to study. Such representations are built from familiar mathematical constructions and are equivalent to the obstruce objects. By manipulating the familiar objects in the representation, the pure mathematician may thus investigate the structure of the mysterious abstract entities.

The most common representation of the ordinal numbers, due to Von Neumann, is as follows. The ordinal 0 is defined to be the empty set ${\displaystyle \emptyset }$; the ordinal 1 is defined to be the set ${\displaystyle \{0\}}$, which is of course equal to ${\displaystyle \{\emptyset \}}$. Similarly, the ordinal 2 is the set ${\displaystyle \{0,1\}}$; the ordinal 3 is the set ${\displaystyle \{0,1,2\}}$; the ordinal 4 is the set ${\displaystyle \{0,1,2,3\}}$. Any finite ordinal ${\displaystyle n}$ is defined to be the set ${\displaystyle \{0,1,2,\ldots ,n-1\}}$ (or, in a rigorous notation, the successor of an ordinal α is defined as the set ${\displaystyle s(\alpha )=\alpha \cup \{\alpha \}\,}$).

In fact this definition extends naturally to transfinite ordinals. The ordinal ${\displaystyle \omega }$ is the set consisting of every finite ordinal ${\displaystyle \{0,1,2,3,\ldots \}}$. Again, ${\displaystyle \omega +1}$ is the set ${\displaystyle \{0,1,2,3,\ldots ,\omega \}}$; ${\displaystyle \omega +2}$ is the set ${\displaystyle \{0,1,2,3,\ldots ,\omega ,\omega +1\}}$; and so on.

The ordinal ${\displaystyle \omega +\omega }$ (or ${\displaystyle \omega *2}$) is the set consisting of all finite ordinals and ordinals of the form ${\displaystyle \omega +n}$, where ${\displaystyle n}$ is a finite ordinal. Thus ${\displaystyle \omega +\omega =\{0,1,2,\ldots ;\omega ,\omega +1,\omega +2,\ldots \}}$.

The ordinal ${\displaystyle \omega _{1}}$ is the first uncountable ordinal, and is the set of all countable ordinals.

Definition (transitive set). A set ${\displaystyle T}$ is transitive if ${\displaystyle x\in T}$ implies ${\displaystyle x\subseteq T}$ (equivalently: ${\displaystyle y\in x\in T\Rightarrow y\in T}$.)

Definition (ordinal). A set ${\displaystyle \alpha }$ is an ordinal if it is transitive and well-ordered by ${\displaystyle \in }$.

Unpacking “well-ordered”. If ${\displaystyle \alpha }$ is an ordinal, then ${\displaystyle \in }$ on ${\displaystyle \alpha }$ is a strict linear order:

• Irreflexive (nonreflexive): for all ${\displaystyle \beta \in \alpha }$, ${\displaystyle \beta \notin \beta }$.
• Transitive: if ${\displaystyle \beta \in \gamma \in \delta }$ (all in ${\displaystyle \alpha }$), then ${\displaystyle \beta \in \delta }$.
• Total on ${\displaystyle \alpha }$: for ${\displaystyle \beta \neq \gamma }$ in ${\displaystyle \alpha }$, either ${\displaystyle \beta \in \gamma }$ or ${\displaystyle \gamma \in \beta }$.

And every nonempty subset of ${\displaystyle \alpha }$ has a least element under ${\displaystyle \in }$.

Lemma (subset of a well-order). If ${\displaystyle (W,<)}$ is well-ordered and ${\displaystyle Y\subseteq W}$, then ${\displaystyle (Y,<)}$ is well-ordered (by restriction).

Elements of ordinals are ordinals. If ${\displaystyle \alpha }$ is an ordinal and ${\displaystyle \beta \in \alpha }$, then ${\displaystyle \beta }$ is transitive and well-ordered by ${\displaystyle \in }$: since ${\displaystyle \alpha }$ is transitive, ${\displaystyle \beta \subseteq \alpha }$, so the restriction of ${\displaystyle \in }$ well-orders ${\displaystyle \beta }$; if ${\displaystyle x\in y\in \beta }$, then ${\displaystyle x,y,\beta \in \alpha }$ and the strict-order transitivity of ${\displaystyle \in }$ on ${\displaystyle \alpha }$ gives ${\displaystyle x\in \beta }$.

Successor and limit ordinals. ${\displaystyle S(\alpha )=\alpha \cup {\alpha }}$ is an ordinal; ordinals of the form ${\displaystyle S(\beta )}$ are successors. An ordinal that is neither ${\displaystyle 0}$ nor a successor is a (nonzero) limit ordinal.

Infima and suprema of ordinals. For a nonempty class ${\displaystyle C}$ of ordinals, ${\displaystyle \inf C=\bigcap C}$ is an ordinal and the greatest lower bound of ${\displaystyle C}$. For a (set) ${\displaystyle X}$ of ordinals, ${\displaystyle \sup X=\bigcup X}$ is an ordinal and the least upper bound of ${\displaystyle X}$.

We construct the natural numbers as finite ordinals and obtain ${\displaystyle \omega }$ (the least infinite, least nonzero limit ordinal) from the Axiom of Infinity.

Axiom (Infinity). There exists a set ${\displaystyle I}$ such that ${\displaystyle \varnothing \in I}$ and for every ${\displaystyle x\in I}$, its successor ${\displaystyle S(x)=x\cup {x}}$ also lies in ${\displaystyle I}$. Such a set is called inductive.

Lemma 1. If ${\displaystyle X}$ is inductive, then ${\displaystyle X\cap \mathrm {Ord} }$ is inductive.

Proof. ${\displaystyle \varnothing }$ is an ordinal and lies in ${\displaystyle X}$; if ${\displaystyle \alpha \in X\cap \mathrm {Ord} }$, then ${\displaystyle S(\alpha )\in X}$ and is an ordinal, so ${\displaystyle S(\alpha )\in X\cap \mathrm {Ord} }$. ■

Construction. Fix an inductive set ${\displaystyle I}$. Let ${\displaystyle {\mathcal {I}}=\{X\subseteq I:\ X{\text{ is inductive}}\}}$ and define ${\displaystyle \omega =\bigcap {\mathcal {I}}.}$

Lemma 2. ${\displaystyle \omega }$ is inductive and is the least inductive subset of ${\displaystyle I}$.

Proof. Intersection of inductive subsets of ${\displaystyle I}$ is inductive; minimality is by definition of intersection. ■

Lemma 3. ${\displaystyle \omega \subseteq \mathrm {Ord} }$.

Proof. By Lemma 1, ${\displaystyle I\cap \mathrm {Ord} }$ is inductive and contained in ${\displaystyle I}$, hence ${\displaystyle \omega \subseteq I\cap \mathrm {Ord} }$. ■

First few ordinals. Define ${\displaystyle 0=\varnothing }$ and ${\displaystyle n+1=S(n)}$. The finite ordinals are exactly the elements of ${\displaystyle \omega }$. Then ${\displaystyle \omega ,\omega +1,\omega +2,\dots }$ are formed by repeated successor from ${\displaystyle \omega }$; ${\displaystyle \omega +\omega }$ is the order-type of two ${\displaystyle \omega }$-blocks in sequence, etc.

Transfinite sequences. A function with domain an ordinal ${\displaystyle \theta }$ is a sequence ${\displaystyle \langle a_{\xi }:\xi <\theta \rangle }$. For ordinal-valued sequences, limits at limits are taken by suprema: ${\displaystyle \displaystyle \lim _{\xi \to \alpha }\gamma _{\xi }=\sup\{\gamma _{\xi }:\xi <\alpha \}}$. A sequence ${\displaystyle \langle \gamma _{\alpha }:\alpha \in \mathrm {Ord} \rangle }$ is normal if increasing and continuous (value at limits equals the supremum of earlier values).

Set-length version. If ${\displaystyle X}$ is a set, ${\displaystyle \theta }$ an ordinal, and ${\displaystyle G}$ maps sequences in ${\displaystyle X}$ of length ${\displaystyle <\theta }$ into ${\displaystyle X}$, there is a unique sequence ${\displaystyle \langle a_{\alpha }:\alpha <\theta \rangle }$ in ${\displaystyle X}$ with ${\displaystyle a_{\alpha }=G(\langle a_{\xi }:\xi <\alpha \rangle )}$.

We define operations by recursion on the second argument.

Addition.

1. ${\displaystyle \alpha +0=\alpha }$.
2. ${\displaystyle \alpha +(\beta +1)=(\alpha +\beta )+1}$.
3. For nonzero limit ${\displaystyle \beta }$, ${\displaystyle \alpha +\beta =\displaystyle \sup _{\xi <\beta }(\alpha +\xi )}$.

Multiplication.

1. ${\displaystyle \alpha \cdot 0=0}$.
2. ${\displaystyle \alpha \cdot (\beta +1)=(\alpha \cdot \beta )+\alpha }$.
3. For nonzero limit ${\displaystyle \beta }$, ${\displaystyle \alpha \cdot \beta =\displaystyle \sup _{\xi <\beta }(\alpha \cdot \xi )}$.

Exponentiation.

1. ${\displaystyle \alpha ^{0}=1}$.
2. ${\displaystyle \alpha ^{\beta +1}=\alpha ^{\beta }\cdot \alpha }$.
3. For nonzero limit ${\displaystyle \beta }$, ${\displaystyle \alpha ^{\beta }=\displaystyle \sup _{\xi <\beta }\alpha ^{\xi }}$.

These are normal (increasing and continuous) in the second variable.

Non-commutativity. ${\displaystyle 1+\omega =\omega \neq \omega +1}$; ${\displaystyle 2\cdot \omega =\omega \neq \omega \cdot 2=\omega +\omega }$.

Geometric picture. ${\displaystyle \alpha +\beta }$ is the order-type of a disjoint sum “all of ${\displaystyle \alpha }$ before all of ${\displaystyle \beta }$”; ${\displaystyle \alpha \cdot \beta }$ is the lexicographic product “${\displaystyle \beta }$ many levels, each a copy of ${\displaystyle \alpha }$” (ordered first by level).

Remark. The least fixed point of ${\displaystyle \alpha \mapsto \omega ^{\alpha }}$ is ${\displaystyle \varepsilon _{0}}$.

A binary relation ${\displaystyle E}$ on a set ${\displaystyle P}$ is well-founded if every nonempty ${\displaystyle X\subseteq P}$ has an ${\displaystyle E}$-minimal element. Any well-order is well-founded, but ${\displaystyle E}$ need not be linear.

Rank and height. If ${\displaystyle E}$ is well-founded on ${\displaystyle P}$, there is a unique function ${\displaystyle \rho :P\to \mathrm {Ord} }$ such that ${\displaystyle \displaystyle \rho (x)=\sup\{\rho (y)+1:\ yEx\}}$. The range ${\displaystyle \rho [P]}$ is an initial segment of the ordinals; its supremum is the height of ${\displaystyle E}$.

Well-founded recursion. If ${\displaystyle E}$ is well-founded on ${\displaystyle P}$ and ${\displaystyle G}$ is any operation, there exists a unique ${\displaystyle F:P\to V}$ with ${\displaystyle \displaystyle F(x)=G{\bigl (}x,\ F\upharpoonright \{y\in P:\ yEx\}{\bigr )}.}$

• Prove there is no strictly decreasing sequence ${\displaystyle \langle a_{n}:n\in \mathbb {N} \rangle }$ in a well-ordered set.
• Show there are arbitrarily large limit ordinals.
• For a normal sequence ${\displaystyle \langle \gamma _{\alpha }:\alpha \in \mathrm {Ord} \rangle }$, show it has arbitrarily large fixed points.
• Prove distributivity and power rules: ${\displaystyle \alpha \cdot (\beta +\gamma )=\alpha \cdot \beta +\alpha \cdot \gamma }$, ${\displaystyle \alpha ^{\beta +\gamma }=\alpha ^{\beta }\cdot \alpha ^{\gamma }}$, ${\displaystyle (\alpha ^{\beta })^{\gamma }=\alpha ^{\beta \cdot \gamma }}$.
• Find examples witnessing failure of cancellation for ${\displaystyle +}$ or ${\displaystyle \cdot }$ on the left/right.
• Define ${\displaystyle \varepsilon _{0}}$ by ${\displaystyle \alpha _{0}=\omega }$, ${\displaystyle \alpha _{n+1}=\omega ^{\alpha _{n}}}$, and ${\displaystyle \varepsilon _{0}=\lim _{n\to \omega }\alpha _{n}}$; show ${\displaystyle \omega ^{\varepsilon _{0}}=\varepsilon _{0}}$.
• Prove the well-founded recursion theorem stated above.