Notes - 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} = \{\gamma \in \alpha : \gamma \in \beta\} = \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.

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}$

Suppose this is not true, and let

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

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 a well-ordered class, any transitive subset of $\mathbf{ON}$ is also also well-ordered and hence 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}$.

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 \{\alpha\}$.
• 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$

$\beta = 0$ is not a successor ordinal or a limit ordinal.

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$.

It remains to show that if $\beta$ is not a successor ordinal, then it’s either a limit ordinal or zero. Hence 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$).

$\mathbb N$ considered as an ordinal.

\[\omega = \bigcup \omega\]

and every $n \in \omega$ is either $0$ or a successor.

Suppose:

• $X$ is a set

Then:

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

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.

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.

\[\alpha + \eta = \bigcup \\{\alpha + \beta : \beta \in \eta\\}\]

\[\alpha + \eta = \bigcup \\{\alpha \cdot \beta : \beta \in \eta\\}\]

\[\alpha^\eta = \bigcup \\{\alpha^\beta : \beta \in \eta\\}\]

$\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^+$.

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

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

\[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 \{0, 1\}$, which is uncountable.

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

\[(a, b) <_X (a', b') \iff (b <_B b' \lor (b = b' \land a <_A a'))\]

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

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

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)$

(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 is inductively 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$