Ordinals

# Ordinal Numbers

Suppose there are sets $$X$$, $$Y$$, and orders on them, namely $$(X, <)$$ and $$(Y, <)$$. Say they have the same order-type if there exists a bijection $$f : X \rightarrow Y$$ such that $$x < y$$ if and only if $$f(x) < f(y)$$. $$f$$ is called an order-isomorphism.

Recall $$X$$ is well-ordered if every non-empty subset of $$X$$ has a least element.

Construct $$\emptyset$$, $$\{\emptyset\}$$, $$\{\emptyset, \{\emptyset\}\}$$, $$\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$$, etc. Ordering on them is defined as set containment.

An ordinal is a set that is

1. transitive/complete (every member is a subset), and
2. strictly well-ordered by membership.

## Observations

1. If $$\alpha$$ is an ordinal then $$S(\alpha) = \alpha \cup \{\alpha\}$$ is an ordinal, called the successor ordinal.
2. If $$\alpha$$ is an ordinal and $$\beta \in \alpha$$ then $$\beta$$ is an ordinal.
3. If $$A$$ is a set of ordinals then $$\sup A = \bigcup A$$ is an ordinal.

## Theorems

Theorem. Any well-ordered set is order-isomorphic to some ordinal $$\alpha$$.

$$\omega$$, called the limit ordinal is the first infinite ordinal. It is not the successor of any ordinal (i.e. $$\omega \neq S(\alpha)$$ for any ordinal $$\alpha$$). $$\epsilon_0$$ is the first ordinal such that $$\epsilon_0 = \omega^{\epsilon_0}$$. $$\omega_1$$ is the first uncountable ordinal.

$0, 1, 2, 3, \dots, \omega, \omega + 1, \omega + 2, \dots, \\ \underbrace{\omega + \omega}_{\omega \cdot 2}, \omega \cdot 2 + 1, \dots, \omega \cdot 3, \dots, \\ \underbrace{\omega\omega}_{\omega^2}, \omega^2 + 1, \dots, \omega^3, \dots, \\ \omega^\omega, \omega^\omega + 1, \dots, \omega^{\omega^\omega}, \dots, \\ \epsilon_0, \epsilon_0 + 1, \dots, \epsilon_1, \dots, \\ \omega_1, \omega_1 + 1$

# Transfinite Induction

Recall strong induction: Let $$S_n = \{i \in \mathbb{N} : i < n\}$$, called a section. $$A \subset \mathcal{N}$$ is inductive if for all $$n \in \mathcal{N}$$, $$S_n \subset A$$ implies $$n \in A$$.

Recall the principle of strong induction: If $$A \subset \mathbb{N}$$ is inductive then $$A = \mathcal{N}$$.

Proof (by contradiction). If $$A \neq \mathbb{N}$$ then $$\mathbb{N} \setminus A$$ has a smallest element $$n$$. But then $$S_n \subset A$$ which implies $$n \in A$$, a contradiction. QED.

Theorem. Every set can be well-ordered.

The proof depends on the axiom of choice.

Well-order the index set of statements $$J$$. Let $$S_\alpha = \{\gamma \in J : \gamma < \alpha\}$$, called a section. A set $$A \subset J$$ is inductive if for all $$\alpha \in J$$, $$S_\alpha \subset A$$ implies $$\alpha \in A$$.

The principle of transfinite induction: Suppose $$J$$ is well-ordered. A set $$A \subset J$$ is inductive implies $$A = J$$.

## Applications

Theorem. There exists a set $$K$$ in $$\mathbb{R}^2$$ that intersect every line in the plane twice.

Proof (depends on the axiom of choice). Let $$L$$ be the set of all lines in $$\mathbb{R}^2$$ (so $$|L| = |\mathbb{R}|$$). Well-order $$L$$ with the type $$J$$ of the first ordinal with the same cardinality as $$\mathbb{R}$$ (all elements of $$J$$ have cardinality less than that of $$\mathbb{R}$$). Write $$L = \{L_\alpha\}_{\alpha \in J}$$. Let \begin{align} A = \{\alpha \in J : \exists \text{ set } K_\alpha \text{ such that } & (1) |K_\alpha| < |\mathbb{R}| \text{ and}\\ & (2) \text{ no three points are colinear} \text{ and} \\ & (3) |K_\alpha \cap L_\beta| = 2 \text{ if } \alpha \leq \beta \text{ and} \\ & (4) K_\beta \subset K_\alpha \text{ if } \beta < \alpha\} \end{align} We need to show that $$A$$ is inductive, so $$A = J$$.

Base case: Clearly, $$1 \in A$$ (let $$K_1$$ be the set of two points on $$L_1$$).

Inductive step: If $$S_\alpha \subset A$$, let $$K = \bigcup\limits_{\beta < \alpha} K_\beta$$. $$K$$ has the same cardinality as $$\mathbb{R}$$ (by (1)) and has no three point colinear (by (2) and (3)). The set of all lines through $$K_\alpha$$ have cardinality less than that of $$\mathbb{R}$$ so it can’t hit all of $$L_\alpha$$. Pick 1 or 2 points to form $$K_\alpha = K \cup \{\text{1 or 2 extra points}\}$$. So $$\alpha \in A$$. QED.