Cómo usar formalmente la recursividad transfinita para construir una secuencia para una prueba del lema de Zorn

Podemos evitar apelar a los números de Hartogs si en su lugar hacemos una prueba indirecta. Como beneficio adicional, la recursividad transfinita se vuelve un poco más limpia:

Suponga que (a)$(P,\preceq)$es un conjunto parcialmente ordenado que satisface las premisas del lema de Zorn, (b)$P$no tiene elemento máximo, y (c)$C$es una función de elección en$P$. Entonces buscamos una contradicción.

Sin pérdida de generalidad extender$C$tal que$C(\varnothing)=42$, sin importar si o no$42\in P$.

Aplicar Transfinite Recursion I a la función de clase

$$G(X) = C(\{y\in P\mid \forall z\in \operatorname{Rng}(X)\cap P: z\prec y\})$$ Esto da una función de clase $F$tal que para cada ordinal $\alpha$, $$F(\alpha) = C(\{y\in P \mid \forall \beta<\alpha : F(\beta)\in P \to F(\beta)\prec y\})$$

Lema. Para todos$\alpha$sostiene que$F(\alpha)\in P$y$\forall \beta : F(\beta)\prec F(\alpha)$.

Prueba. Por inducción transfinita sobre$\alpha$. La hipótesis de inducción nos dice que$\{F(\beta)\mid \beta<\alpha\}$es una cadena en$P$(tenga en cuenta que es un conjunto en cualquier caso gracias a Reemplazo). Las premisas de Zorn nos dicen que esta cadena tiene un límite superior; debido a que no hay un elemento máximo, incluso tiene un límite superior estricto . En otras palabras,

$$\{y\in P \mid \forall \beta<\alpha : F(\beta)\in P \to F(\beta)\prec y\},$$ el conjunto de todos los límites superiores estrictos, no está vacío, por lo que $F(\alpha)$es en $P$y es mayor que todos los $F(\beta)$s.

El lema nos dice que$F$es una función de preservación del orden de ON a$P$. Desde$F$conserva el orden, es en particular inyectiva . Por lo tanto la fórmula

$$H(x)=\alpha \iff F(\alpha)=x \lor (\alpha=117 \land \forall\beta:F(\beta)\ne x)$$ es funcional, y aplicando Reemplazo en $P$y $H$nos dice que ON es un conjunto. La paradoja de Burali-Forti proporciona ahora nuestra deseada contradicción.

---

Tenga en cuenta que en realidad nunca necesitábamos$C(\varnothing)=42$ excepto para asegurarse de que$G$era una función de clase , por lo que podíamos usar el teorema de recursión en ella.

La estructura de prueba aquí es típica: la definición por recursión transfinita es seguida inmediatamente por una inducción transfinita que extrae hechos útiles de la fórmula de recursión. Este enfoque de dos pasos a menudo es necesario para usar la maquinaria recursiva general porque necesitamos definir$G$de una forma defensiva tal que podamos probar que tiene sentido y es funcional sin depender de que su argumento sea producido por recursividad. Este andamiaje defensivo, es decir, la intersección$\operatorname{Rng}(X)$con$P$entonces$z\prec y$tiene sentido y asegurarse de que$C(\{x\in P\mid \cdots\})$siempre significa algo, incluso si la condición termina filtrando todo, luego el lema lo limpia una vez que la magia recursiva ha hecho su trabajo y conocemos la entrada para$G$proviene de una recursividad bien comportada.

---

Como nota adicional, se podría argumentar que esto no es "moralmente" una prueba indirecta. La forma en que prefiero pensar en esto es que me gustaría asumir solo (a) y (c), y luego en medio de la prueba del lema decir

... esta cadena tiene un límite superior. Si ese límite superior es un elemento máximo, entonces hemos terminado ; de lo contrario, hay algo más grande, que por lo tanto es un límite superior estricto ...

Sin embargo, afirmar que "hemos terminado" con todo el lema de Zorn cuando estábamos en medio de un paso de inducción interna no se hace realmente en compañía educada. Formular toda la prueba como una prueba indirecta nos permitirá seguir esta intuición de todos modos, de una manera simple pero formalmente aceptable.

La parte de la prueba después del lema es solo un argumento de que eventualmente debemos alcanzar una de las condiciones de "hemos terminado", porque continuar para siempre tendría consecuencias absurdas.

Dejar$C$ser una función de elección en$P.$Podemos usar su segunda variación de recursión transfinita para definir una secuencia ordinal$F:\mathbf{Ord}\to P$como sigue:

1. $F(0)= C(P)$
2. Si$F(\alpha)$es máximo en$P$dejar$F(\alpha+1) = F(\alpha).$De lo contrario el conjunto$A=\{x\in P : x > F(\alpha)\}$no está vacío y toma$F(\alpha+1) = C(A).$
3. Para un ordinal límite$\lambda,$podemos ver por inducción que$F''(\lambda)$es una cadena La suposición de que toda cadena tiene una cota superior en$P$significa el conjunto $$B=\{x\in P:\mbox{x is an upper bound for $F''(\lambda)$}\}$$ no está vacío. Dejar$F(\lambda) = C(B).$

para hacer el$G$funciones totales, simplemente defínalas arbitrariamente para cualquier caso que no estén bien definidas por lo anterior (por ejemplo, en cosas que no son elementos / subconjuntos de$P$o si los conjuntos$A$o$B$están vacíos). La inducción muestra que estos casos nunca surgen.

Aquí es donde entra Hartog. Sabemos que hay un ordinal$\alpha^*$que no se inyecta$P.$Así para algunos$\beta<\gamma < \alpha^*,$tenemos$F(\beta)=F(\gamma).$Si$F(\beta)$no eran máximos, entonces$F(\beta+1)> F(\beta)$por el hecho de que$F$esta incrementando,$F(\gamma)>F(\beta),$contradiciendo el hecho de que$F(\gamma)=F(\beta).$De este modo$F(\beta)$es máximo en$P$.

Sí, este tema me desconcertó durante mucho tiempo como estudiante. Más de lo que me gustaría admitir, de hecho.

Primero, abordemos el problema del teorema de Hartogs. Necesitas aplicarlo en cualquiera de los dos casos. La idea es que construyas algo recursivamente, y este algo es necesariamente una función inyectiva. Quiere saber que el proceso se estabiliza en algún punto, y el teorema de Hartogs dice que tiene que detenerse en algún ordinal, de lo contrario habríamos tenido una inyección de la clase adecuada de todos los ordinales en nuestro conjunto.

Ahora. ¿Como hacer esto? Trabajemos al revés.

El objetivo es construir una cadena bien ordenada que tenga un límite superior que sea un elemento máximo. Entonces$G_i$, o$G$debe proporcionarle una cadena un poco más larga si se les da una cadena en el orden parcial. Si no lo hacen, no nos importa.

¿Por qué no nos importa? Porque vamos a demostrar por inducción que nuestra aplicación recursiva de la función siempre da como resultado una cadena. Así que cualquier otra cosa es irrelevante.

Ahora, usamos la función de elección.

1. Para$x$un subconjunto del orden parcial,$C(x)$es una función que elige un límite superior para$x$, que se encuentra fuera de$x$. Si no existe tal límite superior, entonces$x$no está en el dominio de$C$. Aquí aplicamos el axioma de elección.

2. Cuando$x$es una incrustación que preserva el orden de un ordinal$\alpha$en el orden parcial con una imagen acotada, defina$G(x)$es$C(x)$. Es decir, un límite superior que podemos agregar a$x$.

3. Cuando$x$es cualquier otra cosa,$G(x)=\varnothing$.

Ahora aplique el teorema de la recursividad transfinita. Obtenemos una función que gira un límite superior tras otro, y tendremos que probar, por inducción, que esto siempre es una cadena y, a menos que se estabilicen, son diferentes. Entonces, según el teorema de Hartogs, hay un punto en el que debemos habernos estabilizado, y esto nos da el resultado deseado.