Set Theory HT25, Ordinals

A transitive set $\alpha$ whose elements are well-ordered by $\in$.

The class of all ordinals.

Suppose $\beta \in \alpha \in \mathbf{ON}$.

Then $\beta \subseteq \alpha$ by transitivity of $\alpha$, so the restriction $(\beta, \in)$ is a well-order. But $\beta$ is also transitive, since if $x \in y \in \beta$, then $y \in \alpha$ and $x \in \alpha$ by transitivity of $\alpha$, so then $x \in \beta$ by the transitivity property of the order $\in$ on $\alpha$.

Hence $\beta$ is an ordinal.

If $\beta \in \alpha$, then $\beta = \alpha _ {<\beta}$, so that the elements of $\alpha$ are the proper initial segments of $\alpha$.

Proof: $\alpha _ {<\beta} = \lbrace \gamma \in \alpha : \gamma \in \beta\rbrace = \beta$, since $\gamma \in \beta \implies \gamma \in \alpha$ by the transitivity of $\alpha$.

The class relation $\in$ on $\mathbf{ON}$ is a class-well order.

The first uncountable ordinal, i.e. the set of all countable ordinals.

• $\omega _ \alpha$ is $\aleph _ \alpha$ considered as an ordinal.
• $\omega _ 1$ is thus $\aleph _ 1$ considered as an ordinal, and so is the first uncountable ordinal (note also that this is not necessarily $2^{\aleph _ 0}$ considered as an ordinal, since $\aleph _ 1 = 2^{\aleph _ 0}$ requires the continuum hypothesis).

Let $\gamma := \alpha \cap \beta$. Then $\gamma$ is an initial segment of $\beta$, by transitivity of $\alpha$ and $\beta$.

If $\gamma$ is a proper initial segment of both, then $\gamma \in \alpha \cap \beta$, since the elements of an ordinal are its proper initial segments, but this contradicts irreflexivity.

So either $\gamma = \alpha$, so $\alpha \subsetneq \beta$, or $\gamma = \beta$, so $\beta \subsetneq \alpha$.

@exam~

Suppose:

• $\phi(x)$ is a formula with parameters
• $\phi(\beta)$ holds for every $\beta \in \mathbf{ON}$ for which $\phi(\gamma)$ holds for all $\gamma \in \beta$

Then:

• $\phi(\alpha)$ holds for all $\alpha \in \mathbf{ON}$

---

Combined with the fact that every ordinal is either the zero ordinal, a successor ordinal, or a limit ordinal, this means that to show $\phi(\alpha)$ holds for all $\alpha$ it suffices to show:

• $\phi(0)$ holds
• Given that $\phi(\alpha)$ holds, $\phi(\alpha^+)$ holds.
• Given that $\phi(\beta)$ holds for all $\beta \in \alpha$, then $\phi(\alpha)$ holds.

Suppose this is not true, and let

\[\alpha := \min\lbrace \beta \in \mathbf{ON} : \lnot \phi(\beta)\rbrace\]

Then $\phi(\gamma)$ holds for all $\gamma \in \alpha$ by the minimality of $\alpha$, so $\phi(\alpha)$ holds, a contradiction.

Since the $\mathbf{ON}$ is well-ordered by $\in$, any subset of $\mathbf{ON}$ also inherits this well-order and since by assumption $X$ is transitive, this set must be an ordinal.

Suppose $\mathbf{ON}$ is a set. Then $\mathbf{ON}$ is transitive, since any element of an ordinal is an ordinal. Hence $\mathbf{ON}$ is a transitive set of ordinals, and hence also an ordinal. Then $\mathbf{ON} \in \mathbf{ON}$, which contradicts the irreflexivity of $\mathbf{ON}$ (and the axiom of foundation).

Isomorphic ordinals are equal.

We show the contrapositive.

Suppose $\alpha$ and $\beta$ are two isomorphic ordinals. If they are not equal, then one is a proper initial segment. Hence one is a proper initial segment. But then as a well-order is not isomorphic to any of its proper initial segments, they are not isomorphic.

• If $\alpha$ is an ordinal, then so is its successor $\alpha^+ = \alpha \cup \lbrace \alpha\rbrace$.
• If $\Gamma$ is a set of ordinals, then $\bigcup \Gamma$ is an ordinal.

Every ordinal $\beta \in \mathbf{ON}$ is precisely one of the following three types:

• Zero ordinal: $\beta = 0$
• Successor ordinal: $\beta = \alpha^+$ for some $\alpha \in \mathbf{ON}$
• Limit ordinal: $\beta = \bigcup \beta$ and $\beta \ne 0$

Zero ordinal exists and is not a successor or limit ordinal: $\beta = 0$ is not a successor ordinal or a limit ordinal.

Successor ordinals are not zero ordinals or limit ordinals: If $\beta = \alpha^+$ is a successor ordinal, it is not the zero ordinal or a limit ordinal, since $\alpha \in \alpha^+$ but $\alpha \notin \bigcup \alpha^+$ and so $\beta \ne \bigcup \beta$.

If an ordinal is not a successor or the zero ordinal, it is a limit ordinal: We aim to show that $\beta = \bigcup \beta$.

To see $\beta \subseteq \bigcup \beta$, suppose that $\alpha \in \beta$. Then by assumption, $\beta \neq \alpha^+$, and hence $\alpha^+ \in \beta$ since the class order on $\mathbf{ON}$ is total (and $\beta \notin \alpha^+$, since then either $\beta = \alpha$ or $\beta \in \alpha$, both impossible). Hence $\alpha \in \bigcup \beta$, and since $\alpha \in \beta$ was arbitrary $\beta \subseteq \bigcup \beta$.

To see $\bigcup \beta \subseteq \beta$, note that this follows immediately from the transitivity of $\beta$ (ordinals are defined as transitive sets well-ordered by $\in$).

A non-zero ordinal which is not a successor of any ordinal.

---

The definition is not $\alpha = \bigcup \eta$ where $\eta$ is a set of ordinals.

$\mathbb N$ considered as an ordinal.

\[\omega = \bigcup \omega\]

and every $n \in \omega$ is either $0$ or a successor (if it were not the first limit ordinal, it would contain a limit ordinal).

Let $\alpha$ be an ordinal and suppose $\beta \in \alpha$. We aim to show $\beta$ is well-ordered by $\in$ and $\beta$ is transitive.

$\beta$ is well-ordered by $\in$: Suppose $\gamma, \delta \in \beta$. Then by transitivity of $\alpha$, we have $\gamma, \delta \in \alpha$. Hence the elements are well-ordered by the well-order from $\alpha$.

$\beta$ is transitive: Now suppose $\delta \in \gamma \in \beta \in \alpha$. Then by transitivity of $\alpha$, we have $\gamma, \delta \in \alpha$. Since $\alpha$ is well-ordered by $\in$, we must have that $\delta \in \gamma \in \beta$ implies $\delta \in \beta$ (otherwise $\in$ wouldn’t be a well-order).

@exam~

Suppose $\beta \setminus \alpha$ is a singleton. Then, as $\beta$ and $\alpha^+$ are both ordinals, either $\alpha^+ \subseteq \beta$ or $\beta \subseteq \alpha^+$.

In the first case, as $\alpha^+ = \alpha \cup \lbrace \alpha\rbrace$, we have $(\alpha \cup \lbrace \alpha\rbrace ) \subseteq \beta$. Therefore $\beta \setminus \alpha = \lbrace \alpha \rbrace$ and hence $\beta = \alpha^+$.

In the second case, either $\beta = \alpha^+$ or $\beta \in \alpha^+$. In the latter case, $\beta \subseteq \alpha$ so that $\beta \setminus \alpha = \lbrace x\rbrace$ is impossible.

@exam~

Suppose:

• $X$ is a set

Then:

• There exists $\alpha \in \mathbf{ON}$ with $ \vert \alpha \vert \not\le \vert X \vert $.

(i.e. no injection from $\alpha$ to $X$).

@important~

Let $Z$ be the set of all well-orders on subsets $Y$ of $X$, which is a set by comprehension over $\mathcal P(X \times X)$. For each $z \in Z$, the well-order is isomorphic to a unique ordinal $\alpha _ z$. By replacement,

\[A = \lbrace \alpha^+_z : z \in Z\rbrace\]

is a set, and its union is an ordinal $\alpha$. Now suppose that $ \vert \alpha \vert \le \vert X \vert $, so that there is an injection $f : \alpha \to X$. Then $f$ induces a well-order $z$ on its range, but since $\text{ran}(f) \subseteq X$, it follows $z \in Z$. Then $\alpha = \alpha _ z$. But then $\alpha \in \alpha _ z^+ \in A \in \alpha$, a contradiction.

---

Non-constructive proof: Suppose for a contradiction that $ \vert \alpha \vert \le \vert X \vert $ for all $\alpha \in \mathbf{ON}$.

Then for every $\alpha \in \mathbf{ON}$, there exists an injection $f : \alpha \to X$ and hence $f(x) < f(y) \iff x \in y$ defines a well-order on $f[X] \subseteq X$, which is isomorphic to $\alpha$.

Considering the well-order $(Y, <)$ as an ordered pair $\langle Y, <\rangle$, let $W \subseteq \mathcal P(X) \times \mathcal P(X \times X)$ be the set of all well-orders $(Y, <)$ with $Y \subseteq X$ such that $(Y, <)$ is isomorphic to some ordinal, and let $\mathbf F : W \to \mathbf{ON}$ be the class function such that $F((Y, <))$ is the ordinal isomorphic to $(Y, <)$ (which is unique by a previous result).

Then $\mathbf F[W] = \mathbf{ON}$ by the previous paragraph. But this would imply that $\mathbf{ON}$ is a set by replacement, however $\mathbf{ON}$ is actually a proper class, a contradiction.

@important~

Every well-ordered set $(X, <)$ is isomorphic to a unique ordinal by a unique isomorphism.

By Hartog’s theorem, there exists some $\alpha \in \mathbf{ON}$ with $ \vert \alpha \vert \not\le \vert X \vert $. Then $\alpha$ is not isomorphic to an initial segment of $X$, and hence by the result that says

If:

• $(X, <)$ is a well-order
• $(Y, <’)$ is a well-order

Then either:

• $(X, <)$ is isomorphic to an initial segment of $(Y, <’)$, or
• $(Y, <’)$ is isomorphic to an initial segment of $(X, <)$.

it follows that $X$ is isomorphic to an initial segment of $\alpha$, and this initial segment is an ordinal.

Uniqueness follows from the result which says isomorphic ordinals are equal, and the fact the isomorphism is unique follows from the result which says that isomorphisms between well-orders are unique.

@important~

• Zero: $\alpha + 0 = \alpha$
• Successor: $\alpha + \beta^+ = (\alpha + \beta)^+$
• Limit: $\alpha + \eta = \bigcup \lbrace \alpha + \beta : \beta \in \eta\rbrace$

• Zero: $\alpha \cdot 0 = 0$
• Successor: $\alpha \cdot \beta^+ = \alpha \cdot \beta + \alpha$ (keep in mind order matters here)
• Limit: $\alpha \cdot \eta = \bigcup \lbrace \alpha \cdot \beta : \beta \in \eta\rbrace$

• Zero: $\alpha^0 = 1$
• Successor: $(\alpha^\beta) \cdot \alpha$ (keep in mind order matters here)
• Limit: $\alpha^\eta = \bigcup \lbrace \alpha^\beta : \beta \in \eta\rbrace$

\[\beta = \alpha + \delta\]

for some $\delta \le \beta$.

(This can be interpreted as a sort of ordinal subtraction).

1, i.e.

\[\alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma\]

$(A \times B, < _ {\times})$ where $< _ {\times}$ is defined by

\[(a, b) < _ {\times} (a', b') \iff (b <_B b' \lor (b = b' \land a <_A a'))\]

$((A \times \lbrace 0\rbrace ) \cup (B \times \lbrace 1\rbrace ), < _ +)$ where for all $a, a’ \in A$ and $b, b’ \in B$,

• $(a, 0) < _ + (a’, 0) \iff a < _ A a’$
• $(b, 1) < _ + (b’, 1) \iff b < _ B b’$
• $(a, 0) < _ + (b, 1)$ always.

For all $\alpha, \beta \in \mathbf{ON}$,

1. $(\alpha + \beta, \in) \cong (\alpha, \in) + (\beta, \in)$
2. $(\alpha \cdot \beta, \in) \cong (\alpha, \in) \times (\beta, \in)$

---

This is useful because it lets you translate questions about sums and products of ordinals into questions about sums and products of orders. For example, if you’re asked to show

\[\alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma\]

You can instead show that for three orders $(A, < _ A)$, $(B, < _ B)$ and $(C, < _ C)$

\[(A, <_A) \times \Big((B, <_B) + (C, <_C)\Big) \cong \Big((A, <_A) \times (B, <_B)\Big) + \Big((A, <_A) \times (C, <_C)\Big)\]

and use the fact that order-isomorphic ordinals are equal. This is often easier than arguing directly about ordinals from their definitions, since sum and product orders have more structure that you can exploit.

(1): We perform transfinite induction on $\beta$ for each fixed $\alpha \in \mathbf{ON}$.

Case $\beta = 0$: The result is immediate.

Case $\beta = \gamma^+$: Note that $(\alpha + \beta) = (\alpha + \gamma)^+$, which inductively is isomorphic to the extension of $(\alpha, \in) + (\gamma, \in)$ by a new greatest element, which is isomorphic to $(\alpha, \in) + (\gamma^+, \in)$.

Case $\beta$ is limit ordinal:

Note that $\alpha + \beta = \bigcup _ {\gamma \in \beta} (\alpha + \gamma)$, and inductively $(\alpha + \gamma, \in) \cong (\alpha, \in) + (\gamma, \in)$ for each $\gamma \in \beta$.

Let $\sigma _ \gamma : (\alpha, \in) + (\gamma, \in) \to (\alpha + \gamma, \in)$ be the unique (by previous result) isomorphisms for each $\gamma$. Then they form a chain: if $\delta \in \gamma$, then $\sigma _ \gamma$ restricts to an isomorphism of $(\alpha, \in) + (\delta, \in)$ with an initial segment of $\alpha + \gamma$, which is also an ordinal and so must be $\alpha + \delta)$ (by uniqueness). Hence $\sigma _ \gamma$ extends $\sigma _ \delta$.

So their union $\sigma := \bigcup _ {\gamma \in \beta} \sigma _ \gamma$ (which is a set by replacement) is an isomorphism of

\[\bigcup_{\gamma \in \beta} ((\alpha, \in) + (\gamma, \in)) = (\alpha, \in) + (\beta, \in)\]

with

\[\bigcup_{\gamma \in \beta} (\alpha + \gamma) = \alpha + \beta\]

(2): By the same argument, except that for the successor stage, we argue as follows:

\[\begin{aligned} (\alpha \cdot \gamma^+, \in) &= (\alpha \cdot \gamma + \alpha, \in) \\\\ &\cong (\alpha, \in) \times (\gamma, \in) + (\alpha, \in) \\\\ &\cong (\alpha, \in) \times (\beta, \in) \end{aligned}\]

where the penultimate isomorphism uses the inductive hypothesis and (1), and the final isomorphism is by the definitions of the sum and product orders.

Suppose:

• $B \subseteq \alpha \in \mathbf{ON}$ is a subset of an ordinal $\alpha$

Then:

• The induced order $(B, \in)$ is isomorphic to some $\beta \le \alpha$.

Let $\beta$ be the ordinal isomorphic to $(B, \in)$. If $\beta \not\le \alpha$, then $\alpha < \beta$, so $\alpha$ is isomorphic to a proper initial segment of $B$, say $B _ {<b}$. But then $\alpha$ embeds into the proper initial segment $\alpha _ {< b}$, which contradicts the result which says

If:

• $(X, <)$ is a well-order
• $\phi : (X, <) \to (X, <)$ is an embedding

Then:

• $\phi(x) \ge x$

Note that $(\beta \setminus \alpha, \in) \cong (\delta, \in)$ for some $\delta \le \beta$ by the result that says a subset of an ordinal is isomorphic to some initial segment of that ordinal.

But then

\[(\beta, \in) \cong (\alpha, \in) + (\beta \setminus \alpha, \in) \cong (\alpha, \in) + (\delta, \in)\]

---

If you are not required to show $\delta \le \beta$, you can just appeal to the fact $\beta \setminus \alpha$ is well-ordered by the well-order it inherits from $\beta$, and so is isomorphic to some ordinal.

We have the result that

\[(\alpha \cdot \beta, \in) \cong (\alpha, \in) \times (\beta, \in)\]

and thus

\[\begin{aligned} ((\alpha \cdot \beta) \cdot \gamma, \in) &\cong ((\alpha , \in) \times (\beta, \in)) \times (\gamma, \in) \\\\ &\cong (\alpha, \in) \times ((\beta, \in) \times (\gamma, \in)) \\\\ &\cong (\alpha \cdot (\beta \cdot \gamma), \in) \end{aligned}\]

where “$\times$” denotes the product order operation. Since the product order operation is associative and order-isomorphic ordinals.

---

Formally,

\[(A, <_A) \times ((B, <_B) \times (C, <_C)) = (A \times (B \times C), <_{\times_1})\]

where $< _ {\times _ 1}$ denotes taking the product orders in this order:

\[(a, b, c) <_{\times_1} (a', b', c')\] \[\Longleftrightarrow (c < c') \vee (c = c' \wedge (a, b) <_{\times} (a', b'))\] \[\Longleftrightarrow (c < c') \vee (c = c' \wedge (b < b' \vee (b = b' \wedge a < a')))\] \[\Longleftrightarrow (b, c) < (b', c') \vee ((b, c) = (b', c') \wedge a < a')\] \[\Longleftrightarrow (a, b, c) <_{\times_2} (a', b', c')\]

where $< _ {\times _ 2}$ denotes taking the product order in the other order. Hence

\[(A \times (B \times C), <_{\times_1}) = ((A \times B) \times C, <_{\times_2})\]

and hence ordinal multiplication is also associative.

\[\begin{aligned} &\quad(\alpha \cdot (\beta + \gamma), \in) \\\\ &\cong (\alpha, \in) \times ((\beta, \in) + (\gamma, \in)) &&(1) \\\\ &\cong (\alpha, \in) \times (\beta, \in) + (\alpha, \in) \times (\gamma, \in) &&(2) \\\\ \end{aligned}\]

Since in $(1)$ the order is characterised by:

• $(a, 0, c) < (a’, 0, c’) \iff (a, c) < _ \times (a’, c’)$,
• $(b, 1, c) < (b’, 1, c’) \iff (b, c) < _ \times (b’, c’)$,
• $(a, 0, c) < (b, 1, c’)$ always.

which is isomorphic to the order in $(2)$. Hence $\alpha \cdot (\beta + \gamma)$ is equal to $\alpha \cdot \beta + \alpha \cdot \gamma$.

If $\beta < \gamma$, then $(\beta, \in)$ is a proper initial segment of $(\gamma, \in)$. Then it follows that if $\alpha \ne 0$ then $(\alpha, \in) \times (\beta, \in)$ is a proper initial segment of $(\alpha, \in) \times (\gamma, \in)$ where if $\alpha = 0$ then there will be equality instead. Hence if $\alpha \ne 0$, $\alpha \cdot \beta < \alpha \cdot \gamma$.

Note that $(\alpha \cdot \beta, \in)$ is isomorphic to a suborder of $(\gamma \cdot \beta, \in)$ by considering the restriction of the product order on $(\alpha \cdot \beta, \in)$ to give one on $(\gamma \cdot \beta, \in)$. Hence $\alpha \cdot \beta$ is isomorphic to some $\delta \le \gamma \cdot \beta$, so $\alpha \cdot \beta \le \gamma \cdot \beta$.

• For every limit ordinal $\gamma$, $f(\gamma) = \sup \lbrace f(\beta) \mid \beta \in \gamma \rbrace$

• For all ordinals $\alpha < \beta$, $f(\alpha) < f(\beta)$.

• Normal: $f(\alpha) := 1 + \alpha$
• Not normal: $f(\alpha) := \alpha + 1$ (consider $f(\omega)$).

• For all ordinals $\alpha$, $f(\alpha) \ge \alpha$ (consider minimal counterexample, and then use the fact it’s monotonic, or use transfinite induction)
• If $S$ is a nonempty set of ordinals, then $f(\sup S) = \sup f(S)$ (use transfinite induction)
• $f$ has arbitrarily large fixed points
  • Proof: For any ordinal $\alpha$, consider union of $\alpha, f(\alpha), f(f(\alpha)), \ldots$, which is allowed by transfinite recursion.
  • In fact the fixed point found this way is the least fixed point $\ge \alpha$. To see this, you can prove that if $\beta \ge \alpha$, then $\beta \ge f(\alpha), f(f(\alpha)), \ldots$ so that $\beta \ge \bigcup \lbrace \alpha, f(\alpha), \ldots \rbrace$, so if $\beta = f(\beta)$, then this fixed point must be greater than or equal to the fixed point found this way.

$\omega$ is a limit ordinal, so

\[1 + \omega = \bigcup_{n \in \omega} (1 + n) = \omega\]

whereas $\omega + 1$ is just $\omega^+$ and $\omega \ne \omega^+$.

@example~

\[\omega + \omega^2 = \omega \cdot 1 + \omega \cdot \omega = \omega \cdot (1 + \omega) = \omega\cdot\omega = \omega^2\]

\[\alpha \cdot 1 = \alpha \cdot 0 + \alpha = 0 + \alpha = \alpha\]

where the last equality holds by transfinite induction on $\alpha$.

@example~

\[2^\omega = \bigcup_{n \in \omega} (2 \cdot n) = \omega\]

whereas $\omega^2 = \omega \cdot \omega$. Since $\omega$ is countable, it follows $2^\omega$ is countable. This is a conflict in notation, since $2^\mathbb N$ is also used to denote the set of all functions from $\mathbb N \to \lbrace 0, 1\rbrace$, which is uncountable.

1. $\alpha = \omega + (2 \cdot \omega + 3) = \omega + (\omega + 3) = \omega \cdot 2 + 3$
2. $\beta = \omega + 2 + \omega + 2 = \omega + \omega + 2 = \omega \cdot 2 + 2$

So $\alpha > \beta$.

@example~

1. $\alpha \cdot \beta = \alpha + \alpha + \cdots$, $\beta$ times

E.g. consider $2 \cdot \omega = \omega$.

If $x \cup \lbrace x\rbrace = y \cup \lbrace y\rbrace$, then either $x = y$ or $x \subseteq y$. If $x = y$, we are done. Otherwise, symmetrically $y \subseteq x$ and therefore $x = y$ also.

(There is also a slightly more complicated argument using the axiom of foundation).

@exam~ @example~

Claim: $\alpha \le \omega \cdot \alpha$ for all ordinals $\alpha$.

This follows straightforwardly by transfinite induction on $\alpha$.

---

Suppose $\alpha$ is a limit ordinal: Then $\alpha^+ \le \omega \cdot \alpha^+$. Hence all ordinals with $\omega \cdot \beta \le \alpha$ have $\beta \le \alpha$, and so the collection of them is a subset of $\alpha^+$.

This set has a largest element $\beta$, since if $\omega \cdot \gamma \le \alpha$ for all $\gamma \in \lambda$ a limit ordinal, then $\omega \cdot \lambda \le \alpha$.

Then $\omega \cdot \beta \le \alpha < \omega \cdot \beta^+ = \omega \cdot \beta + \omega$, so $\alpha = \omega \cdot \beta + n$ for some $n$, but then as $\alpha$ is a limit ordinal, $n = 0$.

Suppose $\alpha = \omega \cdot \beta$, where $\beta > 0$: This follows straightforwardly from transfinite induction on $\beta$.

@exam~ @example~

Since $\omega \cdot \omega = \bigcup _ {n \in \omega} (\omega \cdot \ell)$, it follows that $\alpha \in \omega \cdot \ell$ for some minimal $\ell$.

If $\ell = 0$, then $\alpha = 0$ and so $n = 0, m = 0$.

If $\ell > 0$, then $\ell = n^+$ for some $n$. Then we have $\omega \cdot n < \alpha \le \omega \cdot n^+ = \omega \cdot n + \omega$. So we can find $n, m$ as required.

@exam~ @example~