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 .
Sea una propiedad definida para todos los ordinales . Supongamos que siempre que sea cierto para todos , entonces también lo es. [1] Entonces, la inducción transfinita nos dice que es cierto para todos los ordinales.
Por lo general, la prueba se divide en tres casos:
Los tres casos son idénticos excepto por el tipo de ordinal considerado. No es necesario considerarlos formalmente por separado, pero en la práctica las pruebas suelen ser tan diferentes que requieren presentaciones por separado. A veces, el cero se considera un ordinal límite y, a continuación, a veces se puede tratar en las pruebas en el mismo caso que los ordinales límite.
La recursión transfinita es similar a la inducción transfinita; sin embargo, en lugar de probar que algo es válido 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 de dimensión infinita) eligiendo un vector y para cada α ordinal eligiendo un vector que no esté en el intervalo de los vectores . Este proceso se detiene cuando no se puede elegir ningún vector.
Más formalmente, podemos enunciar el teorema de la recursividad transfinita de la siguiente manera:
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:
Tenga en cuenta que requerimos que los dominios de G 2 , G 3 sean lo suficientemente amplios para que las propiedades anteriores sean significativas. La unicidad de la secuencia que satisface estas propiedades puede demostrarse mediante inducción transfinita.
De manera más general, se pueden definir objetos mediante recursividad transfinita en cualquier relación R bien fundada . ( R ni siquiera necesita ser un conjunto; puede ser una clase adecuada , siempre que sea una relación similar a un conjunto ; es decir, para cualquier x , la colección de todo y tal que yRx es un conjunto).
Las pruebas o construcciones que utilizan la inducción y la recursividad a menudo utilizan el axioma de elección para producir una relación bien ordenada que pueda tratarse mediante 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. [3] Por ejemplo, muchos resultados sobre conjuntos de Borel se prueban mediante inducción transfinita en el rango ordinal del conjunto; estos rangos ya están bien ordenados, por lo que el axioma de elección no es necesario para ordenarlos bien.
La siguiente construcción del conjunto Vitali muestra una forma en que el axioma de elección puede usarse en una prueba por inducción transfinita:
El argumento anterior utiliza el axioma de elección de una 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 con frecuencia no especificará un valor único para A α +1 , dada la secuencia hasta α , pero especificará solo una condición que A α +1 debe satisfacer, y argumentará que hay al menos una conjunto que satisfaga 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 dependientees suficiente. Debido a que existen modelos de la teoría de conjuntos de interés de Zermelo-Fraenkel para teóricos de conjuntos que satisfacen el axioma de elección dependiente pero no el axioma completo de elección, el conocimiento de que una prueba particular solo requiere elección dependiente puede ser útil.