Inducción transfinita

Representación de los números ordinal hasta ⋅ ⋅ ⋅ ⋅ {displaystyle omega ^{omega }. Cada giro de la espiral representa un poder de ⋅ ⋅ {displaystyle omega }. Inducción transfinita requiere probar un Caso básico (utilizado para 0), a Caso sucesor (utilizado para las ordinalidades que tienen un predecesor) y un Caso límite (utilizado para ordinals que no tienen un predecesor).

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 números cardinales. Su corrección es un teorema de ZFC.

Inducción por casos

Vamos P()α α ){displaystyle P(alpha)} ser una propiedad definida para todos los ordinals α α {displaystyle alpha }. Supongamos que cada vez que P()β β ){displaystyle P(beta)} es verdad para todos <math alttext="{displaystyle beta β β .α α {displaystyle beta = 'alpha }<img alt="beta , entonces P()α α ){displaystyle P(alpha)} es también cierto. Entonces la inducción transfinita nos dice que P{displaystyle P} es verdad para todos los ordinals.

Por lo general, la prueba se divide en tres casos:

• Cero caso: Probar eso P()0){displaystyle P(0)} es verdad.
• Caso de éxito: Probar eso para cualquier ordinal sucesor α α +1{displaystyle alpha +1}, P()α α +1){displaystyle P(alpha +1)} A continuación P()α α ){displaystyle P(alpha)} (y, si es necesario, P()β β ){displaystyle P(beta)} para todos <math alttext="{displaystyle beta β β .α α {displaystyle beta = 'alpha }<img alt="beta ).
• Caso límite: Probar eso para cualquier ordinal límite λ λ {displaystyle lambda }, P()λ λ ){displaystyle P(lambda)} A continuación P()β β ){displaystyle P(beta)} para todos <math alttext="{displaystyle beta β β .λ λ {displaystyle beta }lambda }<img alt="{displaystyle beta .

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

Recursión transfinita

Recursividad transfinita es similar a la inducción transfinita; sin embargo, en lugar de probar que algo vale para todos los números ordinales, construimos una secuencia de objetos, uno para cada ordinal.

Como ejemplo, se puede crear una base para un espacio vectorial (posiblemente infinita-dimensional) comenzando por el conjunto vacío y para cada ordinal α 0 elegir un vector que no está en el lapso de los vectores <math alttext="{displaystyle {v_{beta }mid beta {}vβ β ▪ ▪ β β .α α }{displaystyle {v_{beta }mid beta - No.<img alt="{displaystyle {v_{beta }mid beta . Este proceso se detiene cuando ningún vector puede ser elegido.

Más formalmente, 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 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

F()α α )=G()F↾ ↾ α α ){displaystyle F(alpha)=G(Fupharpoonright alpha)} para todos los ordinal α, donde ↾ ↾ {displaystyle upharpoonright } denota la restricción F 's dominio a ordinalsα.

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

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

• F(0) g₁,
• F()α + 1) G₂()F()α), para todos α Ord,
• F()λ λ )=G3()F↾ ↾ λ λ ){displaystyle F(lambda)=G_{3}(Fupharpoonright lambda)}, para todo límite λ ل 0.

Tenga en cuenta que requerimos que los dominios de G₂, G₃ sean lo suficientemente amplios para que el propiedades anteriores significativas. La unicidad de la secuencia que satisface estas propiedades se puede demostrar mediante inducción transfinita.

Más generalmente, uno puede definir objetos por recursividad transfinita en cualquier relación bien fundamentada R. (R ni siquiera necesita ser un conjunto; puede ser una clase adecuada, siempre que sea una relación de tipo conjunto; es decir, para cualquier x, la colección de todos los y tal que yRx es un conjunto.)

Relación con el axioma de elección

Las pruebas o construcciones que usan inducción y recursividad a menudo usan 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 usar la inducción transfinita sin invocar el axioma de elección. Por ejemplo, muchos resultados sobre conjuntos de Borel se prueban por inducción transfinita en 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 se puede usar en una prueba por inducción transfinita:

Primero, bien ordena los números reales (esto es donde el axioma de elección entra a través del teorema bien ordenado), dando una secuencia <math alttext="{displaystyle langle r_{alpha }|alpha .. rα α Silencioα α .β β .. {displaystyle langle r_{alpha }sobrevivientealpha < beta rangle }<img alt="langle r_{alpha }|alpha , donde β es un ordinal con la cardenalidad del continuum. Vamos v₀ iguales r₀. Entonces, v₁ iguales r_α1, donde α₁ es menos tal que r_α1−v₀ no es un número racional. Continúe; en cada paso use lo menos real del r secuencia que no tiene una diferencia racional con ningún elemento hasta ahora construido en la v secuencia. Continuar hasta todos los reales en el r la secuencia está agotada. La final v secuencia enumerará el conjunto Vitali.

El argumento anterior utiliza el axioma de elección de manera esencial desde el principio, para ordenar bien los 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 recursividad transfinita frecuentemente no especificará un valor único para A_α+1, dado la secuencia hasta α, pero 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 en cada paso. Para inducciones y recursiones de longitud numerable, 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.