El principio de inducción y el teorema de recursión son las herramientas principales para demostrar teoremas acerca de los números naturales y para la construcción de funciones presentadas con dominio N. Usamos ambos ampliamente en los capítulos anteriores. En esta sección, se muestra cómo generalizar estos resultados a los números ordinales.

4.1

EL PRINCIPIO DE INDUCCIÓN TRANSFINITA

Sea P (x) sea una propiedad (posiblemente con parámetros). Supongamos que, para todos los números ordinales α :

4.2 Si P (β ) es valido para todo β≺α , entonces P (α ).

Entonces P (α ) es valido para todo ordinal α .

PRUEBA

Suponga que algún número ordinal γ no tiene la propiedad P, y sea S el conjunto de

todos los números ordinales β≤γ que no tiene la propiedad P. El conjunto S tiene un

elemento mínimo α . Debido a que cada β≺α tiene la propiedad P, se sigue por (4,2) que contiene P (α ), contradicción

A veces es conveniente usar el principio de inducción transfinita en una forma que se asemeja más de cerca a la formulación usual del principio de inducción para N. Lo hacemos mediante el tratamiento sucesor y ordinales límite por separado.

4.3

SEGUNDA VERSIÓN DEL PRINCIPIO DE INDUCCIÓN TRANSFINITA

Sea P (x) sea una propiedad. Asuma que

a. P (0) se tiene

b. P (α ) implica P (α+1 ) para todo ordinal α .

c. Para todo limite ordinal α≠0 , si P (β ) se tiene para todo β≺α , entonces P (α ) se tiene. Entonces P (α ) se tiene para todo ordinal α .

PRUEBA

Es suficiente mostrar que los supuestos (a), (b) y (c) implican 4.2. Asi sea α un ordinal

tal que P (β ) para todo β≺α . Si α=0 , entonces P (α ) se tiene por (a). Si α es un

sucesor es decir si no es β≺α talque α=β+1 , nosotros conocemos que P (β ) se

tiene por lo que P (α ) se tiene por (b). Si α≠0 es limite, tenemos P (α ) por (c).

4.4

TEOREMA

Sea Ω un número ordinal, sea un conjunto A, y S=¿α≺Ω Aα

el conjunto de todas

las secuencias transfinita de elementos de A de una longitud de menores que Ω . Sea

g :S→A una función. Entonces existe una única función f :Ω→A tal que

f (α )=g ( fΓα ) Para todo α≺Ω

El lector podría tratar de demostrar este teorema en una forma enteramente análoga a la prueba del teorema de recursión en el capítulo 3. No entraré en detalles ya que este teorema se deduce del teorema de recursión transfinita posterior más general.

Si ν es un ordinal y f es una secuencia transfinita de longitud ν , se utiliza la notación

f=⟨aα lα≺ν ⟩

El teorema 4,4 establece que si g es un función en el conjunto de todas las secuencias

transfinita de elementos de A de una longitud de menores que Ω con valores en A,

entonces hay una secuencia transfinita ⟨aα lα≺ν ⟩

tal que para todo α≺Ω ,

aα=g ( ⟨aξ lξ≺α ⟩)

4.5

EL TEOREMA DE RECURSIÓN TRANSFINITA

Sea G una operación: entonces la propiedad P se indicada en 4.6 define una operación

de F tal que F (α )=G(Fl α) para todo ordinal α .

PRUEBA

Llamemos t un cálculo de longitud α basado en G si t es una función, domt=α+1y

para todo β≤α , t ( β )=G( tl β )

Sea P(x,y) una propiedad

4.6

X es un numero ordinal y y=t(x) para algún calculo t de longitud x basado en G, o x no

es un numero ordinal y y=φ

Nosotros probaremos primero que P define una operación.

Nosotros tenemos que probar que para cada x este un único y tal que P(x,y). Esto es obvio si x no es un ordinal. Para demostrar para ordinales es suficiente probarlo por inducción transfinita: para cada ordinal α hay un único cálculo de longitud α .

Hacemos la hipótesis de inducción para todo β≺α hay un único calculo de longitud

β y demostremos la existencia y unicidad de un cálculo de la longitud α .

Existencia

De acuerdo con el esquema del axioma de sustitución aplicada a la propiedad "y es un cálculo de la longitud x" y el conjunto α , hay un conjunto

T={tl t esuncalculode longitud β para a lg unβ≺α }

Por otra parte la hipótesis de inducción implica que para cada β≺α existe un único

t∈T tal que la longitud de t es β .

T es un sistema de funciones; sea t−=¿T , finalmente sea

τ=t−

∪{(α ,G( t )− )}

nosotros probamos que τ es un único calculo de longitud α .

4.7

τ es una función y dom τ =α+1

PRUEBA

Nosotros vemos inmediatamente que dom t−=¿ t∈T domt=∪β∈α ( β+1)=α en

consecuencia dom τ=dom t−∪ {α }=α+1

Luego puesto que α∉dom t−

es suficiente probar que t−

es una función. Esto se deduce del hecho de que T es un sistema compatible de funciones.

En efecto sea ta , t2∈T arbitrarios y sea domt 1=β1 , domt 2=β2 asumamos que

β1≤β2 , entonces β1⊆ β2y es suficiente probar que t1(γ )=t2 (γ ) para todo γ≺β1 lo

hacemos por inducción transfinita. Asumamos que γ≺β1 y t1(δ )=t2 (δ ) para todo

δ≺γ . Entonces t1Γγ=t2 Γγ y nosotros tenemos que

t1(γ )=G( t1 Γγ )=G (t2 Γγ )=t2( γ ) concluimos que t1(γ )=t2 (γ )para todo γ≺β1 . Esto completa la prueba

4.8

τ (β )=G(τΓβ )para todo β≤α

PRUEBA

Es claro que si β=α como τ (α )=G( t−)=G(τΓα ). Si β≺α , t∈T tal que β∈domt ,

nosotros tenemos que τ (β )=t ( β )=G( τΓβ ) porque t es un calculo y t⊆ τ .

El resultado 4.7 y 4.8 juntos prueban que τ es un cálculo de longitud α .