Inducción transfinita

La inducción transfinita es una extensión de la inducción matemática a (grandes) conjuntos bien ordenados, tales como conjuntos de ordinales o cardinales.

Definición formal

Supóngase que si para todo β < α vale P(β), entonces P(α) vale también. Entonces, por inducción transfinita, P vale para todos los ordinales.

Esto es, si P(α) vale siempre que P(β) valga para todo β < α, entonces P(α) vale para todo α. En términos prácticos, esto significa que para probar una propiedad P para todos los ordinales α, se puede asumir que ya está demostrada para todos los β < α.

Normalmente, una tal prueba se divide en tres casos:

• Caso cero: Demostrar que vale P(0).

• Caso sucesor: Demostrar que para todo ordinal sucesor β+1, P(β+1) se sigue de P(β) (y, de ser necesario, de P(α) para todo α < β).

• Caso límite: Demostrar que para todo ordinal límite λ, P(λ) se sigue de [P(α) para todo α < λ].

Los últimos dos casos son idénticos, excepto por el tipo de ordinal considerado. Formalmente no necesitan ser probados por separado, pero usualmente las demostraciones difieren tanto que requieren ser presentadas por separado.

Recursión transfinita

La recursión transfinita es un método de construcción o definición estrechamente relacionado con el concepto de inducción transfinita. Por ejemplo, se puede definir una secuencia de conjuntos A_α para todo ordinal α, especificando tres cosas:

• Qué es A₀,
• Cómo determinar A_α+1 de A_α (o, posiblemente, de toda la secuencia hasta A_α), y
• Para un ordinal límite λ, cómo determinar A_λ de la secuencia A_α con α < λ.

Más formalmente, se puede enunciar el teorema de recursión transfinita como sigue: dadas tres funciones G₁, G₂, y G₃, existe una única secuencia transfinita F con dom(F) = Ord (la clase propia de todos los ordinales) tal que:

• F(0) = G₁(∅)
• F(α + 1) = G₂(F(α)), para todo α ∈ Ord, y
• F(α) = G₃(F|_α), para todo ordinal límite α ≠ 0.

Se requiere que los dominios de G₁, G₂, y G₃, sean lo bastante amplios como para que las propiedades anteriores tengan sentido. La unicidad de la secuencia que satisface dichas propiedades se puede demostrar usando inducción transfinita.

Más generalmente, se pueden definir objetos por recursión transfinita en una relación bien fundada R (no se necesita siquiera que R sea un conjunto; puede ser una clase propia, si se asume que para todo x, la colección {y|y R x} es un conjunto).

Relación con el axioma de elección

Usualmente se cree que la inducción o la recursión transfinita requieren el axioma de elección. Esto es incorrecto; la inducción transfinita se puede aplicar a cualquier conjunto bien ordenado. Sin embargo, muchas veces las pruebas o construcciones que usan inducción transfinita usan también el axioma de elección para dar un buen orden a un conjunto.

Por ejemplo, considérese la siguiente construcción del conjunto de Vitali: Primero, bienordénense los reales en una secuencia {r_{α | α<c}}, donde c es la cardinalidad del continuo. Defínase v₀ = r₀. Defínase entonces v₁ = r_α1, donde α1 = mín{ α |r_α − v₀| y no es racional}, y continúese de esta manera, siempre eligiendo el mínimo de la secuencia r que no tenga una diferencia racional con ninguno de los elementos hasta ahora tomados en la secuencia v, hasta que se agote la secuencia r. La secuencia final v contendrá los elementos del conjunto de Vitali.

El argumento anterior usa el axioma de elección de forma descarada justo al inicio, al darle un buen orden a los reales. Otros usos son más sutiles; por ejemplo, una construcción por recursión transfinita podría no especificar un valor único para A_α+1, dada la secuencia hasta α, sino especificar sólo una condición que debe ser cumplida por A_α+1, y demostrar luego que sí es posible satisfacerla. Si no es posible definir un ejemplo único de un tal conjunto a cada paso, puede ser necesario invocar el axioma para elegir uno.