¿Por qué no se pueden hacer construcciones recursivas contables usando elección contable?

Question

¿Por qué las construcciones recursivas contables no pueden hacerse usando elección contable? Por ejemplo, reemplace $Z$ por $\omega$ en el siguiente teorema

¿Por qué no se puede probar usando elección contable? (La prueba para la versión dada es la siguiente:

Tal como señaló Brian en los comentarios, modificar el argumento dado no funcionará. Pero ¿qué pasa con una prueba diferente? ¿Está claro que eso no es posible?

Gracias por tu ayuda.

Answer 1

La respuesta breve es que las construcciones recursivas1 te dan una secuencia al extender una secuencia específica; mientras que la elección contable no puede garantizar la coherencia en la elección de secuencias.

Vamos a ver una situación típica donde podemos reducir las construcciones recursivas a la elección contable:

Teorema. Cada conjunto infinito $X$ contiene un subconjunto infinito contable.

Prueba I. Considera la función $G^*$ cuyo dominio son pares $\langle f,n\rangle$ donde $f$ es una función de $n=\{0,\ldots,n-1\}$ en $X$ y $G^*(f,n)=\{x\in X\mid x\notin\operatorname{rng}(f)\}$. Por el principio de construcciones recursivas, hay un $F\colon\omega\to X$ tal que $F(n)\in G^*(F|n,n)$.2 Ahora no es difícil mostrar que $F$ es inyectiva por inducción en $\omega$. $\square$

Prueba II. Para cada $n$ considera el siguiente conjunto $$A_n = \{\langle Y,f\rangle \mid Y\subseteq X\text{ con exactamente }n\text{ elementos}, f\colon Y\to\omega \text{ inyectiva}\}$$ Entonces, por la suposición de que $X$ es infinito, para cada $n$, $A_n\neq\varnothing$. Por elección contable, podemos elegir exactamente un elemento de cada $A_n$, $\langle Y_n,f_n\rangle$. Ahora afirmamos que $Y=\bigcup Y_n\subseteq X$ es un conjunto infinito contable. Es claro que $Y$ es infinito, ya que tomamos uniones de conjuntos finitos cada vez más grandes. Para ver que $Y$ es contable, fija $y_0\in Y$ y define $F\colon\omega\times\omega\to Y$ de la siguiente manera: $$F(n,m)=\begin{cases}f^{-1}_n(m) & m Es claro que $F$ es una sobreyección, y por lo tanto $Y$ es contable. $\square$

Entonces, ¿qué sucede aquí? Podríamos hacerlo relativamente fácilmente por recursión, simplemente elegir un elemento más en cada paso (aunque esto no se presente como tal). Pero podríamos ser inteligentes y elegir directamente conjuntos finitos con sus enumeraciones, luego la unión de conjuntos enumerados es bien ordenable y en este caso contable.

Pero, ¿qué podría haber sucedido cuando solo elegimos el conjunto finito? ¿Por qué no escribimos una biyección con $\omega$ directamente, y decidimos optar por una sobreyección en su lugar? Porque las elecciones de los $Y_n$ no necesariamente coincidían entre sí, por lo que $Y_1$ pudo haber sido o no un subconjunto de $Y_2$ y $f_5$ pudo o no haber coincidido con $f_{42}$ en los elementos comunes de sus dominios.

Entonces, lo que podría haber sido un caso simple de elegir $f=\bigcup f_n$ como una inyección en $\omega$ resulta posiblemente que no sea una función en absoluto. Y por lo tanto, necesitábamos "corregir" esto de una forma u otra.

Y esta es exactamente la dificultad en el caso general. Mientras que la elección contable nos permite elegir infinitos elementos a la vez, no necesita obedecer ninguna ley de coherencia entre las elecciones. Y todo el punto de las construcciones y definiciones recursivas es que las elecciones de hecho son coherentes.

Formalmente hablando, sabemos que no podemos demostrar el principio de construcciones recursivas desde la elección contable porque hay un modelo en el que la elección contable se cumple, y el principio generalizado de construcciones recursivas falla.

La idea detrás de la construcción3 es añadir un árbol "muy amplio" de altura $\omega$ sin elementos máximos, y solo "recordar" subconjuntos que tienen altura acotada, y cosas que podemos construir a partir de esos. Es una demostración técnica mostrar que la elección contable todavía se cumple, pero es fácil mostrar4 que no hay ramas en ese árbol. Y también es bastante fácil mostrar que si las construcciones recursivas pueden llevarse a cabo, entonces cada árbol de este tipo debería tener una rama.

Entonces, ¿qué sucede en un árbol así? Bueno, podemos repetir algo similar a la elección de ramas arbitrariamente largas, pero allí no podemos combinarlas en una rama porque las elecciones deben ser coherentes, no hay forma de evitar eso en absoluto.

---

Notas al pie.

1. Solo consideraré el caso donde $Z=\omega$, ya que ese es el caso en cuestión.

2. La versión que estás usando tiene un error tipográfico, y debería ser $F(z)\in G^*(F|I_W(z),z)$ en la conclusión del principio. Y eso también tiene sentido, ya que $G^*$ toma dos variables.

3. De hecho, escribí una versión ligeramente más detallada en MathOverflow que muestra cómo probar un teorema aún más general sobre el fracaso de las construcciones recursivas generalizadas (no necesariamente contables), mientras se preserva la elección arbitrariamente alta de familias bien ordenadas.

4. De la definición real, de todos modos, no esta explicación ambigua.