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.