Inducción transfinita

Concepto matemático

Representación de los números ordinales hasta . Cada vuelta de la espiral representa una potencia de . La inducción transfinita requiere demostrar un caso base (usado para 0), un caso sucesor (usado para aquellos ordinales que tienen un predecesor) y un caso límite (usado para ordinales que no tienen un predecesor). ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \omega }$

La inducción transfinita es una extensión de la inducción matemática a conjuntos bien ordenados , por ejemplo a conjuntos de números ordinales o cardinales . Su corrección es un teorema de ZFC . ^[1]

Inducción por casos

Sea una propiedad definida para todos los ordinales . Supongamos que siempre que sea verdadera para todos , entonces también es verdadera. ^[2] Entonces la inducción transfinita nos dice que es verdadera para todos los ordinales. ${\displaystyle P(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle P(\beta )}$ ${\displaystyle \beta <\alpha }$ ${\displaystyle P(\alpha )}$ ${\displaystyle P}$

Generalmente la prueba se divide en tres casos:

• Caso cero: Demuestre que es cierto. ${\displaystyle P(0)}$
• Caso sucesor: Demuestre que para cualquier ordinal sucesor , se sigue de (y, si es necesario, para todos los ). ${\displaystyle \alpha +1}$ ${\displaystyle P(\alpha +1)}$ ${\displaystyle P(\alpha )}$ ${\displaystyle P(\beta )}$ ${\displaystyle \beta <\alpha }$
• Caso límite: Demuestre que para cualquier ordinal límite , se sigue de para todo . ${\displaystyle \lambda }$ ${\displaystyle P(\lambda )}$ ${\displaystyle P(\beta )}$ ${\displaystyle \beta <\lambda }$

Los tres casos son idénticos, salvo por el tipo de ordinal considerado. No es necesario considerarlos formalmente por separado, pero en la práctica las demostraciones suelen ser tan diferentes que requieren presentaciones separadas. El cero a veces se considera un ordinal límite y, a veces, puede tratarse en las demostraciones en el mismo caso que los ordinales límite.

Recursión transfinita

La recursión transfinita es similar a la inducción transfinita; sin embargo, en lugar de demostrar que algo es válido para todos los números ordinales, construimos una secuencia de objetos, uno para cada ordinal.

Por ejemplo, se puede crear una base para un espacio vectorial (posiblemente de dimensión infinita) comenzando con el conjunto vacío y, para cada ordinal α > 0, eligiendo un vector que no esté en el espacio de los vectores . Este proceso se detiene cuando no se puede elegir ningún vector. ${\displaystyle \{v_{\beta }\mid \beta <\alpha \}}$

De manera más formal, podemos enunciar el Teorema de Recursión Transfinita de la siguiente manera:

Teorema de recursión transfinita (versión 1) . Dada una función de clase ^[3] G : V → V (donde V es la clase de todos los conjuntos), existe una secuencia transfinita única F : Ord → V (donde Ord es la clase de todos los ordinales) tal que

${\displaystyle F(\alpha )=G(F\upharpoonright \alpha )}$para todos los ordinales α , donde denota la restricción del dominio de  F a los ordinales < α . ${\displaystyle \upharpoonright }$

Como en el caso de la inducción, podemos tratar diferentes tipos de ordinales por separado: otra formulación de recursión transfinita es la siguiente:

Teorema de recursión transfinita (versión 2) . Dado un conjunto g ₁ y funciones de clase G ₂ , G ₃ , existe una función única F : Ord → V tal que

• F (0) = g ₁ ,
• F ( α + 1) = G ₂ ( F ( α )), para todo α ∈ Ord,
• ${\displaystyle F(\lambda )=G_{3}(F\upharpoonright \lambda )}$, para todo límite λ ≠ 0.

Nótese que requerimos que los dominios de G ₂ , G ₃ sean lo suficientemente amplios para que las propiedades anteriores tengan sentido. La unicidad de la secuencia que satisface estas propiedades se puede demostrar mediante inducción transfinita.

De manera más general, se pueden definir objetos por recursión transfinita en cualquier relación bien fundada R ( R ni siquiera necesita ser un conjunto; puede ser una clase propia , siempre que sea una relación tipo conjunto ; es decir, para cualquier x , la colección de todos los y tales que yRx es un conjunto).

Relación con el axioma de elección

Las demostraciones o construcciones que utilizan inducción y recursión a menudo utilizan el axioma de elección para producir una relación bien ordenada que puede ser tratada por inducción transfinita. Sin embargo, si la relación en cuestión ya está bien ordenada, a menudo se puede utilizar la inducción transfinita sin invocar el axioma de elección. ^[4] Por ejemplo, muchos resultados sobre los conjuntos de Borel se demuestran por inducción transfinita sobre el rango ordinal del conjunto; estos rangos ya están bien ordenados, por lo que no se necesita el axioma de elección para ordenarlos bien.

La siguiente construcción del conjunto de Vitali muestra una forma en que el axioma de elección puede usarse en una prueba por inducción transfinita:

Primero, ordena bien los números reales (aquí es donde entra el axioma de elección a través del teorema de buen ordenamiento ), dando una secuencia , donde β es un ordinal con la cardinalidad del continuo . Sea v ₀ igual a r ₀ . Luego sea v ₁ igual a r _{α 1} , donde α ₁ es el menor tal que r _{α 1}  −  v ₀ no es un número racional . Continúa; en cada paso usa el menor real de la secuencia r que no tenga una diferencia racional con ningún elemento construido hasta ahora en la secuencia v . Continúa hasta que se agoten todos los reales en la secuencia r . La secuencia v final enumerará el conjunto de Vitali. ${\displaystyle \langle r_{\alpha }\mid \alpha <\beta \rangle }$

El argumento anterior utiliza el axioma de elección de manera esencial desde el principio, para ordenar correctamente los números reales. Después de ese paso, el axioma de elección no se vuelve a utilizar.

Otros usos del axioma de elección son más sutiles. Por ejemplo, una construcción por recursión transfinita con frecuencia no especificará un valor único para A _{α +1} , dada la secuencia hasta α , sino que especificará solo una condición que A _{α +1} debe satisfacer, y argumentará que hay al menos un conjunto que satisface esta condición. Si no es posible definir un ejemplo único de tal conjunto en cada etapa, entonces puede ser necesario invocar (alguna forma de) el axioma de elección para seleccionar uno de ellos en cada paso. Para inducciones y recursiones de longitud contable , el axioma más débil de elección dependiente es suficiente. Debido a que hay modelos de la teoría de conjuntos de Zermelo-Fraenkel de interés para los teóricos de conjuntos que satisfacen el axioma de elección dependiente pero no el axioma de elección completo, el conocimiento de que una prueba particular solo requiere elección dependiente puede ser útil.

Véase también

• Inducción matemática
• ∈-inducción
• Número transfinito
• Inducción bien fundada
• Lema de Zorn

Notas

1. J. Schlöder, Aritmética ordinal. Consultado el 24 de marzo de 2022.
2. No es necesario aquí suponer por separado que es cierto. Como no hay nada menor que 0, es vacuamente cierto que para todo , es cierto. ${\displaystyle P(0)}$ ${\displaystyle \beta }$ ${\displaystyle \beta <0}$ ${\displaystyle P(\beta )}$
3. Una función de clase es una regla (específicamente, una fórmula lógica) que asigna cada elemento de la clase de la izquierda a un elemento de la clase de la derecha. No es una función porque su dominio y codominio no son conjuntos.
4. De hecho, el dominio de la relación ni siquiera necesita ser un conjunto. Puede ser una clase propia, siempre que la relación R sea semejante a un conjunto: para cualquier x , la colección de todos los y tales que y  R  x debe ser un conjunto.

Referencias

• Suppes, Patrick (1972), "Sección 7.1", Teoría de conjuntos axiomáticos, Dover Publications , ISBN 0-486-61630-4

Enlaces externos

• Emerson, Jonathan; Lezama, Mark y Weisstein, Eric W. "Inducción transfinita". MathWorld .