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 A0,
- 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 G1, G2, y G3, existe una única secuencia transfinita F con dom(F) = Ord (la clase propia de todos los ordinales) tal que:
- F(0) = G1(∅)
- F(α + 1) = G2(F(α)), para todo α ∈ Ord, y
- F(α) = G3(F|α), para todo ordinal límite α ≠ 0.
Se requiere que los dominios de G1, G2, y G3, 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 v0 = r0. Defínase entonces v1 = rα1, donde α1 = mín{ α |rα − v0| 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.
Véase también
Enlaces externos
- Weisstein, Eric W. «Transfinite Induction». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.