# Ordinal arithmetic

## 1. Introduction

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, $α , β , γ , δ$ range over ordinals and $λ , μ$ range over limit ordinals.

## 2. The successor function and the order relation

We start by recalling a few earlier definitions and results.

Definition.

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

• $∀ x ∈ α ∀ y ∈ α ∀ z ∈ α ( x ∈ y ∧ y ∈ x → x ∈ z )$
• $∀ x ∈ α ∀ y ∈ α ( x ∈ y ∨ x = y ∨ y ∈ x )$

Definition.

$α < β$ iff $α ∈ β$.

Definition.

$α + 1$ is the set $α ∪ α$.

Proposition.

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

Proposition.

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

Proposition.

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

Definition.

A limit ordinal is an ordinal $λ$ such that $λ$ is nonempty and $α ∈ λ$ implies $α + 1 ∈ λ$.

Proposition.

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

Proposition.

$α ⩽ β$ (i.e. $α < β$ or $α = β$) iff $α ⊆ β$.

Proof.

Hint: ordinals are transitive sets.

Proposition.

For any two ordinals $α , β$ either $α ⩽ β$ or $β ⩽ α$.

Proposition.

If $α ∈ β$ and $α + 1 ∉ β$ then $α = β$.

Proposition.

If $α ∈ β$ then $α + 1 ∈ β + 1$.

Proposition.

$α < β$ iff $α + 1 ⩽ β$.

Proposition.

If $ϕ ( α )$ holds for some ordinal $α$, where $ϕ$ is a first-order statement possibly involving other set parameters, then there is a least ordinal $β$ such that $ϕ ( β )$.

Proof.

Hint: look at the least $β ∈ α + 1$ such that $ϕ ( β )$ and use results on $⩽$ 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

• $α + 0 = α$
• $α + ( β + 1 ) = ( α + β ) + 1$
• $α + λ = ⋃ γ ∈ λ ( α + γ )$

Note the notation $⋃ γ ∈ λ E γ$ which is the same as $⋃ E γ γ ∈ λ$. For ordinals $γ , λ$ and well-behaved functions $E γ$ this is often written $lim γ → λ E γ$.

Proposition.

For all ordinals we have $α ⩽ α + β$.

Proof.

Induction on $β$.

Proposition.

For all ordinals $α , β$ with $β ≠ 0$ we have $α < α + β$.

Proof.

Induction on $β$.

Proposition.

If $α < β$ then $γ + α < γ + β$.

Exercise.

It is not true that if $α < β$ then $α + γ < β + γ$ for all $γ$.

Proposition.

For all $α , λ$, if $λ$ is a limit ordinal then so is $α + λ$.

Proof.

If $γ < α + λ$ then $γ ∈ α + β$ for some $β < λ$ so $γ + 1 < ( α + β ) + 1 = α + ( β + 1 ) ∈ α + λ$.

Proposition.

If $γ < α + β$ then $γ < α$ or $γ = α + δ$ for some $δ < β$.

Proof.

Let $δ ′ ⩽ β$ be least such that $γ < α + δ ′$. Then $δ ′$ is not a limit since it it were then $γ ∈ α + δ ′ = ⋃ ε < δ ′ ( α + ε )$ so $γ < α + ε$ for some $ε < δ ′$. If $δ ′ = 0$ then $γ < α$, and if $δ ′ = δ + 1$ then $γ = α + δ$.

Proposition.

For all $α , β , γ$ we have $( α + β ) + γ = α + ( β + γ )$.

Proof.

Fix $α , β$ and argue by induction on $γ$.

• $( α + β ) + 0 = ( α + β ) = ( α + ( β + 0 ) )$
• $( α + β ) + ( γ + 1 ) = ( ( α + β ) + γ ) + 1 = ( α + ( β + γ ) ) + 1 = α + ( β + ( γ + 1 ) )$
• $( α + β ) + λ = ⋃ γ < λ ( ( α + β ) + γ ) = ⋃ γ < λ ( α + ( β + γ ) ) = α + ⋃ γ < λ ( β + γ ) = α + ( β + λ )$

Exercise.

Verify the step $⋃ γ < λ ( α + ( β + γ ) ) = α + ⋃ γ < λ ( β + γ )$ in the last proof.

Exercise.

Show that $0 + α = α$ for all ordinals $α$,

Exercise.

Show that it is not true in general that $α + β = β + α$.

Exercise.

Show that if $α < β$ then there is $γ$ such that $α + γ = β$. Is there alos $δ$ such that $δ + α = β$?

Exercise.

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

## 4. Multiplication of ordinals

Definition.

Multiplication of ordinals is defined by

• $α · 0 = α$
• $α · ( β + 1 ) = ( α · β ) + α$
• $α · λ = ⋃ γ ∈ λ ( α · γ )$

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 < γ$ and $α < β$ then $γ α < γ β$.

Proof.

Induction on $β$.

Proposition.

If $0 < γ$ and $λ$ is a limit then $γ λ$ is also a limit.

Proposition.

For ordinals $α , β , γ$ we have $α ( β + γ ) = α β + α γ$.

Proof.

Induction on $γ$.

Proposition.

For ordinals $α , β , γ$ we have $α ( β γ ) = ( α β ) γ$.

Proof.

Induction on $γ$.

Exercise.

It is not true in general that $α β = β α$.

Exercise.

It is not true in general that $( α + β ) γ = α γ + β γ$.

Proposition.

For all $α , β$ with $α ≠ 0$ there are unique $γ , δ$ such that $β = α γ + δ$ and $δ < α$.

Proof.

Choose $γ ′ ⩽ β$ least such that $β < α γ ′$. Then $γ ′$ is not zero nor a limit (why not?) so $γ ′ = γ + 1$ and $α γ ⩽ β < α γ + α$. Now use a previous result to find $δ$.

Exercise.

Give examples of $α , β$ with $α ≠ 0$ such that for no $γ , δ$ is $β = γ α + δ$.

## 5. Exponentiation of ordinals

Definition.

Exponentiation of ordinals is defined by

• $α 0 = 1$
• $α β + 1 = α β · α$
• $α λ = ⋃ γ ∈ λ α γ$

Exercise.

Prove that $( α β ) ( α γ ) = α β + γ$ for all ordinals.

Exercise.

Prove that $( α β ) γ = α β · γ$ for all ordinals.

## 6. Normal functions and fixed points

A normal function $f : On → On$ is a class function such that $f ( α + 1 ) > f ( α )$ for all $α$ and $f ( λ ) = ⋃ γ ∈ λ f ( γ )$ at limits.

Exercise.

Prove that for all normal functions $f$ and all $α$ there is $β > α$ such that $f ( β ) = β$.

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