# Induction and recursion on ordinals

## 1. Introduction

We have seen that ordinals are either zero, a successor, or a limit, and are based on $∈$ which is well-founded and has induction and recursion principles. Therefore there are induction and recursion principles on ordinals, which are essentially just special cases of $∈$-induction and recursion. This web page states these principles: the proofs are the same as for $∈$-induction and recursion. Examples will be given later.

As elsewhere, $α , β , γ , δ , …$ etc. and $λ , μ , …$ range over ordinals with $λ , μ , …$ being reserved for limit ordinals.

## 2. Induction on ordinals

Theorem.

Suppose $ϕ ( x )$ is a first order formula and

• $ϕ ( 0 )$
• $∀ α ( ϕ ( α ) → ϕ ( α + 1 ) )$
• $∀ λ ( ( ∀ α ∈ λ ϕ ( α ) ) → ϕ ( λ ) )$

Then for all ordinals $α$ we have $ϕ ( α )$.

Remark: in the above, and everywhere in these notes, $λ$ is thought of as a limit ordinal. However the third case includes the first for $λ = 0$ and the second for $λ = α + 1$ so strictly speaking the first two cases are redundant.

## 3. Recursion on ordinals

Theorem.

Suppose $G ( x , y ) , H ( x , y )$ are class functions defined on ordinals alpha and $G$ is defined by

• $F ( 0 ) = F 0$
• $∀ α F ( α + 1 ) = G ( α , F ( α ) )$
• $∀ λ F ( λ ) = H ( λ , F ( α ) α ∈ λ )$

Then there is a class function $F$ defined as above, uniform in any parameters in $G , H$.

## 4. Ordinals and well-founded sets

There are similar induction and recursion theorems on any well-founded relation. A well-order is a particular kind of well-founded relation closely related to ordinals.

Note: some of the following will be moved to somewhere more appropriate in the future.

Definition.

A binary relation, $R$, is well-founded if $∀ z ( z ≠ ∅ → ∃ y ∈ z ∀ x ( x ∈ z → ¬ R ( x , y ) ) )$. A set $r ⊆ x × x$ is well-founded if the relation $( u , v ) ∈ r$ is well-founded. The relation $R$ is local if $∀ y ∃ z ∀ x ( x ∈ z ↔ R ( x , y ) )$.

A set $x$ is called a well-founded set if the set membership relation is well-founded on the transitive closure of $x$.

Definition.

A well-order $<$ on a set $X$ is a linear order such that for all nonempty $Y ⊆ X$ there is a $<$-least element of $Y$.

Theorem.

If $( X , < )$ is a well-ordered set there is a unique ordinal $α$ such that $( X , < )$ is order-isomorphic to $( α , ∈ )$.

Proof.

Consider the class of set-functions $F = f : Y → β Y ⊆ e X ∧ f : ( Y , < ) ( β , ∈ )$. where $⊆ e$ denoted Initial part of and $β$ ranges over ordinals. $F$ is a class i.e. defined by a first order formula. (We shall show eventually it is a set.) It is nonempty because it contains the empty cunction $∅ → 0$.

Given $f : Y → β$ in $F$, if the domain $Y$ of $f$ is not the whole of $X$ we can take $y ∈ X ∖ Y$ to be $∈$-least and define $f ′ ( y ) = β$ and $f ′ ( x ) = f ( x )$ for $x ∈ Y$ hence extend $f$. Furthermore we can prove that for any $f , g ∈ F$ either $dom f ⊆ dom g$ or $dom g ⊆ dom f$ (since both are initial parts of $X$) and that $f , g$ agree on their common doman. (Else take $x ∈ X$ to be least such that $f , g$ disagree at $x$.) It follows that the union of a set of fucntions in $F$ is a function in $F$.

Now for each $x ∈ X$ let $F x$ be the unique element of $F$ with domain $y ∈ X y < x$ proving (by considering the least such $x$ such that $F x$ doesn't exis) that such $F x$ always exists. Then $F x x ∈ X$ is a set by replacement and $f = ⋃ F x x ∈ X$ is a set function mapping $X$ to some ordinal, as may be checked.