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:

$\forall x \in α \forall y \in α \forall z \in α (x \in y \land y \in x \to x \in z)$
$\forall x \in α \forall y \in α (x \in y \lor x = y \lor y \in x)$

Definition.

$α < β$ iff $α \in β$ .

Definition.

$α + 1$ is the set $α \cup \{α\}$ .

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 $α \in λ$ implies $α + 1 \in λ$ .

Proposition.

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

Proposition.

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

Proof.

Hint: ordinals are transitive sets.

Proposition.

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

Proposition.

If $α \in β$ and $α + 1 \notin β$ then $α = β$ .

Proposition.

If $α \in β$ then $α + 1 \in β + 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 $β \in α + 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.

3. Addition of ordinals

Definition.

Addition of ordinals is defined by

$α + 0 = α$
$α + (β + 1) = (α + β) + 1$
$α + λ = ⋃_{γ \in λ} (α + γ)$

Note the notation $⋃_{γ \in λ} E_{γ}$ which is the same as $⋃ \{E_{γ}: γ \in λ\}$ . For ordinals $γ, λ$ and well-behaved functions $E_{γ}$ this is often written ${lim}_{γ \to λ} E_{γ}$ .

Proposition.

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

Proof.

Induction on $β$ .

Proposition.

For all ordinals $α, β$ with $β \neq 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 $γ \in α + β$ for some $β < λ$ so $γ + 1 < (α + β) + 1 = α + (β + 1) \in α + λ$ .

Proposition.

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

Proof.

Let $δ' ⩽ β$ be least such that $γ < α + δ'$ . Then $δ'$ is not a limit since it it were then $γ \in α + δ' = ⋃_{ε < δ'} (α + ε)$ 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

$α \cdot 0 = α$
$α \cdot (β + 1) = (α \cdot β) + α$
$α \cdot λ = ⋃_{γ \in λ} (α \cdot γ)$

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 $α \neq 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 $α \neq 0$ such that for no $γ, δ$ is $β = γ α + δ$ .

5. Exponentiation of ordinals

Definition.

Exponentiation of ordinals is defined by

$α^{0} = 1$
$α^{β + 1} = α^{β} \cdot α$
$α^{λ} = ⋃_{γ \in λ} α^{γ}$

Exercise.

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

Exercise.

Prove that $(α^{β})^{γ} = α^{β \cdot γ}$ for all ordinals.

6. Normal functions and fixed points

A normal function $f : On \to On$ is a class function such that $f (α + 1) > f (α)$ for all $α$ and $f (λ) = ⋃_{γ \in λ} 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$ .