Teorema de recursión transfinita

En matemáticas, el teorema de recursión transfinita dice que una función puede definirse usando una recursión sobre un conjunto bien ordenado; por ejemplo, $\mathbb {N}$ pero también sobre conjuntos generalmente bien ordenados.

Dado que cada conjunto bien ordenado es isomorfo a un ordinal, el teorema también se suele expresar en términos de ordinales.

Declaraciones

La recursión transfinita es un ejemplo de inducción transfinita , y esta última funciona sobre un conjunto bien ordenado (de hecho, la factibilidad de dicha inducción es equivalente a la condición de estar bien ordenado). En particular, el teorema puede enunciarse para conjuntos bien ordenados. Si $A$ es un conjunto parcialmente ordenado, escribimos $A^{a}=\{b\in A\mid b<a\}.$

Teorema de recursión transfinita ^{[ 1 ]} — Sea un conjunto $X$ , un conjunto bien ordenado $A$ y una función

G:\{A^{a}\to X\mid a\in A\}\to X

se da. Entonces existe una función única

f:A\to X

de tal manera que

f(a)=G(f|_{A^{a}})

para cada $a$ en $A$ donde la barra vertical significa restricción.

El teorema de recursión transfinita también se enuncia comúnmente para ordinales. Una versión simple es: sea un conjunto $X$ y una función de clase $G$ con valores en $X$ definido en la clase de todas las funciones que se den. Entonces, para cada ordinal $\alpha$ , existe una función única

f:\alpha \to X

de tal manera que, para cada ordinal $\beta <\alpha$ ; eso es, $\beta \in \alpha$ o $\beta \subsetneq \alpha$ ,

f(\beta )=G(f|_{\beta })

.

Dado que un ordinal es un conjunto bien ordenado, la versión anterior se deduce de la versión bien ordenada (como $\beta =\alpha ^{\beta }$ ). Aunque es común preguntar $G$ para ser definido para todas las funciones, esta es solo una forma conveniente de enunciar el teorema. En la práctica, normalmente solo se define $G(f)$ para funciones $f:\alpha \to X$ , $\alpha$ todos los ordinales, y luego se extiende $G$ para todas las demás funciones arbitrarias.

Prueba

Cuando $A=\mathbb {N}$ La demostración aparece en el libro Álgebra básica I de N. Jacobson ^{[ 2 ]} , y es exactamente la misma demostración válida para un conjunto arbitrario bien ordenado. La demostración en sí está tomada de Halmos ^{[ 1 ] .}

Decimos un subconjunto $E\subset A\times X$ está cerrado (con respecto a $G$ ) si para cada función $f:A^{a}\to X,\,a\in A$ cuyo gráfico está contenido en $E$ , tenemos $(a,G(f))$ está en $E$ . Por ejemplo, $A\times X$ Está cerrado.

Dejar $F$ sea la intersección de todos los subconjuntos cerrados de $A\times X$ (con respecto a $G$ ), que de nuevo está cerrado. Lo demostraremos $F$ es la gráfica de una función $A\to X$ ; es decir, la fibra $p^{-1}(a)$ para la proyección $p:F\subset A\times X\to A$ tiene exactamente un elemento para cada $a$ en $A$ Para ello, utilizaremos la inducción fuerte sobre $A$ . Es decir, suponiendo $\#p^{-1}(b)=1$ por cada $b<a$ , mostramos $\#p^{-1}(a)=1$ .

Por hipótesis inductiva, tenemos la función $f:A^{a}\to X,\,b\mapsto {\text{elemento único en }}p^{-1}(b)$ . Nótese que su gráfica se encuentra en $F$ . Desde $F$ está cerrado, $(a,G(f))$ está en $F$ . De este modo, $\#p^{-1}(a)\geq 1$ Para demostrar que es la igualdad, supongamos lo contrario. Eso significa que existe algún par $(a,y)\neq (a,G(f))$ en $F$ Reclamamos el conjunto

E:=F-\{(a,y)\}

está cerrado. Por lo tanto, dejemos $g:A^{b}\to X$ sea una función cuya gráfica se encuentra en $E$ . Si $b=a$ , entonces tenemos $f=g$ por hipótesis inductiva; de hecho, puesto que sus gráficos se encuentran en $F$ ,

\{f(c),g(c)\}\subset p^{-1}(c)

para cada $c<a$ . De este modo, $(b,G(g))\in E$ desde $y\neq G(f)=G(g)$ y $F$ está cerrado. Si $b\neq a$ , luego otra vez $(b,G(g))$ está en $E$ como $F$ está cerrado. Esto prueba la afirmación y luego $E\subsetneq F$ es una contradicción con la pequeñez de $F$ . Finalmente, la unicidad se demuestra mediante una inducción similar pero más sencilla. $\square$

Ejemplos

Ejemplo: una construcción de base

Dejar $V$ Sea un espacio vectorial. Existe una forma "muy obvia" de construir una base de $V$ de la siguiente manera. Si $V\neq 0$ , elige un vector distinto de cero $v_{1}$ y luego elige otro vector distinto de cero $v_{2}$ no en el lapso de $v_{1}$ , si los hay, y así sucesivamente. La recursión transfinita puede hacer riguroso este argumento, como mostramos ahora (alternativamente, se puede usar el lema de Zorn; véase el lema de Zorn § Todo espacio vectorial tiene una base .)

Dejemos lo anterior $V$ se nos da un buen ordenamiento por el teorema del buen ordenamiento . Supongamos que se nos da una secuencia de vectores $x_{\gamma }$ indexado por un ordinal $\beta$ . Es decir, se nos da una función $f:\beta \to V$ de tal manera que $f(\gamma )=x_{\gamma }$ para cada $\gamma \en \beta$ (o $\gamma <\beta$ ). Entonces deja

G(f)=

el elemento más pequeño del complemento

V-\operatorname {span} (\operatorname {im} (f))

si $V\neq \operatorname {span} (\operatorname {im} (f))$ y $G(f)=0$ de lo contrario. Nota, dado que $f$ es arbitrario, la imagen de $f$ no es necesariamente linealmente independiente; todo lo que tenemos es que $G(f)$ es linealmente independiente de los vectores no nulos en $\operatorname {im} (f)$ .

El teorema de recursión transfinita dice entonces: dado un ordinal $\alpha$ , existe un único $f:\alpha \to V$ que satisface la condición de recursión; es decir, $f(\beta )=G(f|_{\beta })$ es linealmente independiente de $\operatorname {im} (f|_{\beta })$ para $\beta <\alpha$ . En particular, los vectores no nulos en la imagen de $f$ son linealmente independientes. Finalmente, si tomamos $\alpha =\kappa$ ser algún ordinal grande; por ejemplo, tomar $\kappa$ tener una cardinalidad estrictamente mayor que la de $V$ , entonces, por razón de cardinalidad,

B:=\operatorname {im} (f:\kappa \to V)-\{0\}

es una base de $V$ . (Nótese que, a diferencia de una construcción mediante el lema de Zorn, esta base está determinada de forma única por la elección de un buen ordenamiento en $V$ .)

Ejemplo: una demostración del lema de Zorn

La recursión transfinita se utiliza en una demostración típica del lema de Zorn , asumiendo el axioma de elección. Aquí hay un argumento (que es bastante similar a la construcción de una base anterior). ^{[ 3 ]}

Dejar $X$ Sea un conjunto parcialmente ordenado en el que cada cadena, incluida la cadena vacía, tiene una cota superior. Para demostrarlo, $X$ tiene un elemento maximal, supongamos, por el contrario, que no tiene ninguno. Entonces cada cadena $C$ tiene un límite superior estricto; es decir, un elemento $x$ en $X$ de tal manera que $x>y$ para cada $y$ en $C$ , puesto que tiene un límite superior que está acotado por algún elemento estrictamente mayor. Sea $c:{\mathfrak {P}}(X)-\{\emptyset \}\to X$ ser una función de elección; es decir, $c(S)\in S$ y luego para cada cadena $C$ en $X$ , dejar

b(C)=c(\{{\text{strict upper bounds of }}C\}).

Ahora construimos recursivamente una secuencia sobre ordinales. Para cada función $f:\beta \to X$ , dejar $G(f)=b(\operatorname {im} (f))$ si $\operatorname {im} (f)$ es una cadena y de otra manera $G(f)=$ algún elemento arbitrario en $X$ ; p.ej, $b(\emptyset )$ . Por el teorema de recursión transfinita, encontramos una función $f:\alpha \to X$ de tal manera que $f(\beta )=G(f|_{\beta })$ para $\beta <\alpha$ ; en particular, es inyectivo. Pero esto es una contradicción ya que hay un ordinal cuya cardinalidad es estrictamente mayor que la de $X$ (véase el número de Hartogs ). Si no se está seguro de la existencia de un ordinal grande, también existe un argumento que evita por completo los ordinales (siguiendo utilizando la recursión transfinita). Véase, por ejemplo, el principio maximal de Hausdorff § Demostración a partir del teorema del buen ordenamiento . $\square$

Recursión con el axioma de reemplazo

Para algunos usos de la recursión transfinita, es posible que necesitemos construir una función con valores en una clase; en ese caso, necesitamos usar el axioma de reemplazo para asegurarnos de que aún obtenemos la función. $f$ aunque el codominio sea una clase.

Aquí hay un ejemplo de tal necesidad. ^{[ 4 ]}^{[ 5 ]} Supongamos que queremos mostrar

Cada conjunto bien ordenado es isomorfo de forma única a un ordinal único.

El problema es que, a priori , no sabemos qué ordinal usar. Por lo tanto, en cada etapa de la inducción transfinita, construimos un nuevo ordinal. Precisamente, dado un conjunto bien ordenado $X$ y un elemento $a$ en $X$ , supongamos que hemos construido

g_{b}:X^{b}{\overset {\sim }{\to }}\alpha _{b}

dónde $X^{b}=\{c\mid c<b\}$ . Extenderemos estos isomorfismos a un isomorfismo $X^{a}\simeq \alpha$ para algún ordinal $\alpha$ . Si $a=s(b)$ es un sucesor; es decir, el elemento más pequeño entre los límites superiores estrictos de $b$ , entonces dejamos $f|_{X^{b}}=g_{b}$ y $f(a)=\alpha _{b}$ . Entonces

f:X^{a}{\overset {\sim }{\to }}s(\alpha _{b}):=\alpha _{b}\cup \{\alpha _{b}\},

donde la unión de la derecha existe por el axioma de unión . Si $a=\sup(X^{a})$ , entonces, pensando $g_{b}$ como conjuntos de pares ordenados, sea

f=\bigcup _{b<a}g_{b}.

La unión de la derecha es un conjunto determinado por el axioma de reemplazo y el axioma de unión; de hecho, el primero garantiza la colección. $\{g_{b}\mid b<a\}$ es un conjunto. Sea $\alpha$ ser la imagen de $f$ , que es claramente un ordinal, y $f:X^{a}{\overset {\sim }{\to }}\alpha$ . Finalmente, comprobamos la unicidad. Por inducción transfinita, vemos que los isomorfismos entre ordinales son las identidades. Entonces dado $f:X{\overset {\sim }{\to }}\alpha ,g:X{\overset {\sim }{\to }}\beta$ , tenemos $g\circ f^{-1}:\alpha {\overset {\sim }{\to }}\beta$ es la identidad y por lo tanto $f=g$ . $\square$

El mismo argumento puede utilizarse para demostrar el teorema de recursión transfinita cuando el objetivo $X$ es una clase. La demostración se realiza mediante inducción fuerte sobre ordinales (la misma demostración funciona para conjuntos bien ordenados, pero usamos ordinales por simplicidad). Por lo tanto, supongamos que el teorema es verdadero para todo $\beta <\alpha$ . Por hipótesis inductiva, para cada $\beta <\alpha$ Tenemos una función única $g_{\beta }:\beta \to X$ que satisface la condición de recursión. Sea $h_{\beta }:\beta \to X$ ser dado por $\gamma \mapsto G(g_{\beta }|_{\gamma })$ . En el caso límite; es decir, $\alpha$ es un ordinal límite, que identifica funciones con sus gráficas, considere la unión

\bigcup _{\beta <\alpha }h_{\beta }.

La formación de una unión se justifica por el axioma de unión, pero para que la unión anterior sea un conjunto, necesitamos la colección.

\{h_{\beta }\mid \beta <\alpha \}

ser un conjunto; en otras palabras, la imagen del mapa $\beta \mapsto h_{\beta }$ ser un conjunto y eso está garantizado por el axioma de reemplazo. Finalmente, esta unión es la gráfica de una función $f:\alpha \to X$ que satisface la condición de recursión requerida. El caso sucesor se maneja de manera similar. $\square$

Referencias

1 2 Halmos 1960 , § 18.
↑ Jacobson, Nathan (22 de junio de 2009). Álgebra básica I: Segunda edición . § 0.4.: Courier Corporation. ISBN 978-0-486-47189-1.{{cite book}}: CS1 mantenimiento: ubicación ( enlace )
↑ Ken Brown (septiembre de 2010). "Matemáticas 6310 : Lema de Zorn" (PDF) . Pi.math.cornell.edu . Universidad de Cornell . Consultado el 20 de junio de 2026 .
↑ "Teorema 1 en 245B, Notas 7: Conjuntos bien ordenados, ordinales y lema de Zorn (opcional)" . Terrytao.wordpress.com . Consultado el 20 de junio de 2026 .
↑ Halmos 1960 , § 20., Teorema de conteo.

Halmos, Paul (1960). Teoría ingenua de conjuntos . Princeton, Nueva Jersey: D. Van Nostrand Company.
"Capítulo IV Recursión Transfinita". Teoría Axiomática de Conjuntos . Estudios en Lógica y Fundamentos de las Matemáticas. Vol. 21. 1958. pp. 100–113 . doi : 10.1016/S0049-237X(08)71575-1 .
Paul Taylor, Fundamentos prácticos de las matemáticas, Fundamentos prácticos de las matemáticas