Inducción transfinita

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

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

La inducción transfinita es una extensión de la inducción matemática a los números ordinales . Su corrección es un teorema de ZF y se basa en el hecho de que los números ordinales están bien ordenados , por lo que una afirmación que no sea universalmente verdadera para todos los ordinales debe tener un contraejemplo mínimo . De hecho, este principio también es cierto para conjuntos bien ordenados arbitrarios, pero dado que cualquier conjunto bien ordenado puede indexarse mediante ordinales de manera que se preserve el orden, basta con establecer el principio para los ordinales. ^{[ 1 ]}

Descripción general

El principio de inducción transfinita es el siguiente:

Dejar

P(\alpha )

ser una propiedad definida para todos los ordinales

\alpha

Supongamos que siempre que

P(\beta )

Es cierto para todos .

\beta <\alpha

, entonces

P(\alpha )

También es cierto. ^{[ 2 ]} Entonces

P

Esto es cierto para todos los números ordinales.

Este principio se puede demostrar fácilmente considerando la forma contrapositiva :

Si

P

Si no es cierto para todos los ordinales, entonces existe un ordinal .

\alpha

de tal manera que

P(\beta )

Es cierto para todos .

\beta <\alpha

⁠ , pero ⁠

P(\alpha )

es falso.

Tal ⁠ $\alpha$ ⁠ es solo un contraejemplo mínimo , cuya existencia está garantizada por el hecho de que la clase de números ordinales está bien ordenada .

Inducción mediante casos

Una demostración por inducción transfinita a menudo se divide en tres casos:

Caso cero: Demuestre que $P(0)$ Es cierto.
Caso sucesor: Demuestre que para cualquier ordinal sucesor $\alpha +1$ , $P(\alpha +1)$ sigue de $P(\alpha )$ (y, si es necesario, $P(\beta )$ a pesar de $\beta <\alpha$ ).
Caso límite: Demuestre que para cualquier ordinal límite $\lambda$ , si $P(\beta )$ se aplica a todos $\beta <\lambda$ , entonces $P(\lambda )$ .

Los tres casos son idénticos, salvo por el tipo de ordinal considerado. Formalmente, no es necesario tratarlos por separado, pero en la práctica las demostraciones suelen ser tan diferentes que requieren presentaciones distintas. El cero a veces se considera un ordinal límite y, en consecuencia, puede tratarse en las demostraciones del mismo modo 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 se cumple 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) comenzando con el conjunto vacío y, para cada ordinal α > 0, eligiendo un vector que no esté en el espacio generado por los vectores. $\{v_{\beta }\mid \beta <\alpha \}$ Este proceso se detiene cuando no se puede elegir ningún vector.

De forma 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 única sucesión transfinita F : Ord → V (donde Ord es la clase de todos los ordinales) tal que

F(\alpha )=G(F\upharpoonright \alpha )

para todos los ordinales α , donde

\upharpoonright

denota la restricción del dominio de F a los ordinales < α .

Al igual que en el caso de la inducción, podemos tratar los diferentes tipos de ordinales por separado: otra formulación de la 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 única función F : Ord → V tal que

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

Cabe señalar que requerimos que los dominios de _G₂ y G₃ _seanlo suficientemente amplios para que las propiedades anteriores tengan sentido. La unicidad de la secuencia que satisface estas propiedades puede demostrarse mediante inducción transfinita.

De forma más general, se pueden definir objetos mediante recursión transfinita sobre cualquier relación bien fundamentada R. ( R ni siquiera tiene por qué ser un conjunto; puede ser una clase propia , siempre que sea una relación de 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 suelen emplear el axioma de elección para generar una relación bien ordenada que puede tratarse mediante 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 recurrir al axioma de elección. ^{[ 4 ]} Por ejemplo, muchos resultados sobre conjuntos de Borel se demuestran mediante 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.

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

Primero, ordenamos bien los números reales (aquí es donde entra en juego el axioma de elección a través del teorema del buen orden ), lo que da como resultado una secuencia

\langle r_{\alpha }\mid \alpha <\beta \rangle

donde β es un ordinal con la cardinalidad del continuo . Sea v ₀ igual a r _0. Entonces sea v ₁ igual a r _{α ₁} , donde α ₁ es el menor tal que r _{α ₁} − v ₀ no es un número racional . Continúe; en cada paso use 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úe hasta que se agoten todos los reales en la secuencia r . La secuencia v final enumerará el conjunto de Vitali.

El argumento anterior utiliza el axioma de elección de manera esencial desde el principio, para ordenar adecuadamente 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 mediante recursión transfinita frecuentemente 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 existe al menos un conjunto que satisface esta condición. Si no es posible definir un ejemplo único de dicho 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. Dado que existen 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 demostración particular solo requiere elección dependiente puede ser útil.

Véase también

Notas

↑ J. Schlöder, Aritmética ordinal . Consultado el 24 de marzo de 2022.
↑ No es necesario asumir aquí por separado que $P(0)$ es cierto. Como no hay $\beta$ menor que 0, es trivialmente cierto que para todo $\beta <0$ , $P(\beta )$ Es cierto.
↑ Una función de clase es una regla (específicamente, una fórmula lógica) que asigna cada elemento de la clase izquierda a un elemento de la clase derecha. No es una función porque su dominio y codominio no son conjuntos.
↑ 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 de tipo conjunto: para cualquier x , la colección de todos los y tales que y R x debe ser un conjunto.