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.

3. Addition of ordinals

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 .