This page uses the theorems of ordinal induction
and recursion together with several previously-given basic
results on ordinals to develop ordinal arithmetic. There are some proofs here and many exercises.
In all cases, a proposition, exercise or theorem may assume the results previously given.
Propositions given without proofs are exercises. Sometimes only a hint is
given as a proof

and completing the proof is also intended
as an exercise. There are a couple of mildly tricky points
to be found in the details of setting up ordinal arithmetic
and I have not attempted to skate over these rapidly. However,
with these details apart, the theory of ordinal arithmetic
is a very beautiful and straightforward one, enjoyable and worth learning.

Throughout, $\alpha ,\beta ,\gamma ,\delta $ range over ordinals and $\lambda ,\mu $ range over limit ordinals.

We start by recalling a few earlier definitions and results.

Definition.

An ordinal is (possibly empty) set $\alpha $ such that:

- $\forall x\in \alpha \u200a\forall y\in \alpha \u200a\forall z\in \alpha \u200a(x\in y\wedge y\in x\to x\in z)$
- $\forall x\in \alpha \u200a\forall y\in \alpha \u200a(x\in y\vee x=y\vee y\in x)$

Definition.

$\alpha <\beta $ iff $\alpha \in \beta $.

Definition.

$\alpha +1$ is the set $\alpha \cup \left\{\alpha \right\}$.

Proposition.

For all ordinals $\alpha $, each element of $\alpha $ is an ordinal.

Proposition.

For all $\alpha $, $\alpha +1$ is an ordinal and $\alpha <\alpha +1$.

Proposition.

For any set $X$ of ordinals, $\bigcup X$ is an ordinal.

Definition.

A limit ordinal is an ordinal $\lambda $ such that $\lambda $ is nonempty and $\alpha \in \lambda $ implies $\alpha +1\in \lambda $.

Proposition.

Every ordinal is exactly one of: zero; a limit ordinal; or $\alpha +1$ for some $\alpha $.

Proposition.

$\alpha \u2a7d\beta $ (i.e. $\alpha <\beta $ or $\alpha =\beta $) iff $\alpha \subseteq \beta $.

**Proof.**

Hint: ordinals are transitive sets.

Proposition.

For any two ordinals $\alpha ,\beta $ either $\alpha \u2a7d\beta $ or $\beta \u2a7d\alpha $.

Proposition.

If $\alpha \in \beta $ and $\alpha +1\notin \beta $ then $\alpha =\beta $.

Proposition.

If $\alpha \in \beta $ then $\alpha +1\in \beta +1$.

Proposition.

$\alpha <\beta $ iff $\alpha +1\u2a7d\beta $.

Proposition.

If $\varphi \left(\alpha \right)$ holds for some ordinal $\alpha $, where $\varphi $ is a first-order statement possibly involving other set parameters, then there is a least ordinal $\beta $ such that $\varphi \left(\beta \right)$.

**Proof.**

Hint: look at the least $\beta \in \alpha +1$ such that $\varphi \left(\beta \right)$ and use results on $\u2a7d$ above.

Proposition.

The class On of all ordinals is not a set.

**Proof.**

Hint: if it were, it would be an ordinal and hence a member of itself.

Definition.

Addition of ordinals is defined by

- $\alpha +0=\alpha $
- $\alpha +(\beta +1)=(\alpha +\beta )+1$
- $\alpha +\lambda ={\bigcup}_{\gamma \in \lambda}(\alpha +\gamma )$

Note the notation ${\bigcup}_{\gamma \in \lambda}{E}_{\gamma}$ which is the same as $\bigcup \{{E}_{\gamma}:\gamma \in \lambda \}$. For ordinals $\gamma ,\lambda $ and well-behaved functions ${E}_{\gamma}$ this is often written ${lim}_{\gamma \to \lambda}{E}_{\gamma}$.

Proposition.

For all ordinals we have $\alpha \u2a7d\alpha +\beta $.

**Proof.**

Induction on $\beta $.

Proposition.

For all ordinals $\alpha ,\beta $ with $\beta \ne 0$ we have $\alpha <\alpha +\beta $.

**Proof.**

Induction on $\beta $.

Proposition.

If $\alpha <\beta $ then $\gamma +\alpha <\gamma +\beta $.

Exercise.

It is not true that if $\alpha <\beta $ then $\alpha +\gamma <\beta +\gamma $ for all $\gamma $.

Proposition.

For all $\alpha ,\lambda $, if $\lambda $ is a limit ordinal then so is $\alpha +\lambda $.

**Proof.**

If $\gamma <\alpha +\lambda $ then $\gamma \in \alpha +\beta $ for some $\beta <\lambda $ so $\gamma +1<(\alpha +\beta )+1=\alpha +(\beta +1)\in \alpha +\lambda $.

Proposition.

If $\gamma <\alpha +\beta $ then $\gamma <\alpha $ or $\gamma =\alpha +\delta $ for some $\delta <\beta $.

**Proof.**

Let $\delta \prime \u2a7d\beta $ be least such that $\gamma <\alpha +\delta \prime $. Then $\delta \prime $ is not a limit since it it were then $\gamma \in \alpha +\delta \prime ={\bigcup}_{\epsilon <\delta \prime}(\alpha +\epsilon )$ so $\gamma <\alpha +\epsilon $ for some $\epsilon <\delta \prime $. If $\delta \prime =0$ then $\gamma <\alpha $, and if $\delta \prime =\delta +1$ then $\gamma =\alpha +\delta $.

Proposition.

For all $\alpha ,\beta ,\gamma $ we have $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$.

**Proof.**

Fix $\alpha ,\beta $ and argue by induction on $\gamma $.

- $(\alpha +\beta )+0=(\alpha +\beta )=(\alpha +(\beta +0\left)\right)$
- $(\alpha +\beta )+(\gamma +1)=\left(\right(\alpha +\beta )+\gamma )+1=(\alpha +(\beta +\gamma \left)\right)+1=\alpha +(\beta +(\gamma +1\left)\right)$
- $(\alpha +\beta )+\lambda ={\bigcup}_{\gamma <\lambda}\left(\right(\alpha +\beta )+\gamma )={\bigcup}_{\gamma <\lambda}(\alpha +(\beta +\gamma \left)\right)=\alpha +{\bigcup}_{\gamma <\lambda}(\beta +\gamma )=\alpha +(\beta +\lambda )$

Exercise.

Verify the step ${\bigcup}_{\gamma <\lambda}(\alpha +(\beta +\gamma \left)\right)=\alpha +{\bigcup}_{\gamma <\lambda}(\beta +\gamma )$ in the last proof.

Exercise.

Show that $0+\alpha =\alpha $ for all ordinals $\alpha $,

Exercise.

Show that it is not true in general that $\alpha +\beta =\beta +\alpha $.

Exercise.

Show that if $\alpha <\beta $ then there is $\gamma $ such that $\alpha +\gamma =\beta $. Is there alos $\delta $ such that $\delta +\alpha =\beta $?

Exercise.

Using recursion on ordinals, define a modified subtraction operation $\alpha -\beta $ such that $\alpha -\beta =0$ is $\alpha <\beta $ and $\alpha =\beta +(\alpha -\beta )$ otherwise. Prove your assertions.

Definition.

Multiplication of ordinals is defined by

- $\alpha \xb70=\alpha $
- $\alpha \xb7(\beta +1)=(\alpha \xb7\beta )+\alpha $
- $\alpha \xb7\lambda ={\bigcup}_{\gamma \in \lambda}(\alpha \xb7\gamma )$

We omit the multiplication symbol where it is clear to do so and have the convention that multiplication is more binding than addition, as for usual arithmetic.

Proposition.

If $0<\gamma $ and $\alpha <\beta $ then $\gamma \alpha <\gamma \beta $.

**Proof.**

Induction on $\beta $.

Proposition.

If $0<\gamma $ and $\lambda $ is a limit then $\gamma \lambda $ is also a limit.

Proposition.

For ordinals $\alpha ,\beta ,\gamma $ we have $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma $.

**Proof.**

Induction on $\gamma $.

Proposition.

For ordinals $\alpha ,\beta ,\gamma $ we have $\alpha \left(\beta \gamma \right)=\left(\alpha \beta \right)\gamma $.

**Proof.**

Induction on $\gamma $.

Exercise.

It is not true in general that $\alpha \beta =\beta \alpha $.

Exercise.

It is not true in general that $(\alpha +\beta )\gamma =\alpha \gamma +\beta \gamma $.

Proposition.

For all $\alpha ,\beta $ with $\alpha \ne 0$ there are unique $\gamma ,\delta $ such that $\beta =\alpha \gamma +\delta $ and $\delta <\alpha $.

**Proof.**

Choose $\gamma \prime \u2a7d\beta $ least such that $\beta <\alpha \gamma \prime $. Then $\gamma \prime $ is not zero nor a limit (why not?) so $\gamma \prime =\gamma +1$ and $\alpha \gamma \u2a7d\beta <\alpha \gamma +\alpha $. Now use a previous result to find $\delta $.

Exercise.

Give examples of $\alpha ,\beta $ with $\alpha \ne 0$ such that for no $\gamma ,\delta $ is $\beta =\gamma \alpha +\delta $.

Definition.

Exponentiation of ordinals is defined by

- ${\alpha}^{0}=1$
- ${\alpha}^{\beta +1}={\alpha}^{\beta}\xb7\alpha $
- ${\alpha}^{\lambda}={\bigcup}_{\gamma \in \lambda}{\alpha}^{\gamma}$

Exercise.

Prove that $\left({\alpha}^{\beta}\right)\left({\alpha}^{\gamma}\right)={\alpha}^{\beta +\gamma}$ for all ordinals.

Exercise.

Prove that $({\alpha}^{\beta}{)}^{\gamma}={\alpha}^{\beta \xb7\gamma}$ for all ordinals.

A normal function $f:\text{On}\to \text{On}$ is a class function such that $f(\alpha +1)>f\left(\alpha \right)$ for all $\alpha $ and $f\left(\lambda \right)={\bigcup}_{\gamma \in \lambda}f\left(\gamma \right)$ at limits.

Exercise.

Prove that for all normal functions $f$ and all $\alpha $ there is $\beta >\alpha $ such that $f\left(\beta \right)=\beta $.

Exercise.

Prove that for all normal functions $f$ there is a normal function $g$ such that the image of $g$ is precisely the set of fixed points of $f$.