¿Aplicaciones simples de forzar en la teoría de la recursión?

Hay muchos ejemplos. Rápidamente se vuelven bastante complicados, por ejemplo, creo que el teorema de base baja podría no ser pedagógicamente apropiado, pero de hecho hay ejemplos.

En particular, la prueba más fácil (en mi opinión) de que existen grados de Turing incomparables es un argumento convincente. Específicamente, se muestra que para cualquier par de cadenas binarias finitas$\sigma,\tau$y cualquier$e\in\mathbb{N}$, hay extensiones$\sigma'\supseteq\sigma$y$\tau'\supseteq\tau$tal que no hay secuencias binarias infinitas$f\supseteq\sigma', g\supseteq\tau'$con$\Phi_e^f=g$. Esto nos permite construir inductivamente un par de secuencias binarias infinitas que son incomparables con Turing, diagonalizando frente a posibles reducciones (la frase "extensiones finitas" se usa a menudo aquí). El teorema de Friedberg-Muchnik mejora esto al hacer que los grados ce pasen del forzamiento "puro" al establecimiento más complicado de argumentos de prioridad; ver esta vieja pregunta .

Ahora, mencionó el tema de "genérico" versus "genérico para una colección específica de conjuntos densos " (por ejemplo, los re). Existe una rica jerarquía de "niveles de genericidad" en la teoría de la computabilidad, y este también es el caso de las nociones de forzamiento que no son de Cohen (desafortunadamente, la palabra "genérico" en la teoría de la computabilidad generalmente significa Cohen-genérico). En particular, al examinar el argumento anterior, vemos lo siguiente:

• Los conjuntos densos que queremos encontrar son aquellos de la forma "Ninguna extensión infinita de la cadena izquierda (resp. derecha) calcula cualquier extensión infinita de la cadena derecha (resp. izquierda) a través de$\Phi_e$."

• A primera vista, cada uno de estos es bastante complicado, a saber,$\Pi^1_1$. Todavía hay muchos conjuntos contables tan densos, por lo que podemos encontrarlos trivialmente a todos.

• ... ¡Pero también podríamos querer ver qué tan simple podemos ir! Hay dos formas en que un cálculo puede "fallar": puede cometer un error o puede no dar ninguna respuesta. Esto nos permite redefinir los conjuntos densos que nos interesan: "O ya hay algunos$n$tal que$\Phi_e^{left}(n)$se detiene,$right(n)$se define, y$\Phi_e^{left}(n)\not=right(n)$, O hay algunos$n$tal que ninguna extensión de la cadena izquierda hace$\Phi_e^?(n)$alto." (Y de manera similar, intercambiando "izquierda" y "derecha").

• Esta definición se comprueba fácilmente para ser$\Sigma^0_2$. Entonces tenemos:

Si$x, y\in 2^{\omega}$son mutuamente$\Sigma^0_2$-Cohen genérico - es decir, si el conjunto$\{(\sigma,\tau)\in 2^{<\omega}\times 2^{<\omega}: \sigma\prec x, \tau\prec y\}$es un filtro que se encuentra cada$\Sigma^0_2$subconjunto denso de$2^{<\omega}\times 2^{<\omega}$- entonces$x$y$y$son Turing incomparables.

Aquí hay otro ejemplo. No estoy seguro de que esto se ajuste a la factura: la prueba es bastante complicada si uno no se ha sentido cómodo con forzar la teoría de la computabilidad, pero el forzamiento en sí es simple, la pregunta es fácil de formular (aunque la respuesta es un poco complicada ), y toda la situación es bastante interesante.

Digamos que queremos construir una función de rápido crecimiento$\omega\rightarrow\omega$. Hay un forzamiento natural que salta a la mente (hay muchas variaciones de esta idea) :

• Las condiciones son pares.$(p, f)$con$p$un mapa de algún subconjunto finito de$\omega$a$\omega$, y$f:\omega\rightarrow\omega$es total con$p\subseteq f$.

• El orden viene dado por$(p, f)\le (q, g)$(recordar, "$\le$" significa "es más fuerte que") si:

  • $p\supseteq q$,

  • $f(n)\ge g(n)$para todos$n$, y

  • para cada$m$en$dom(p)\setminus dom(q)$, tenemos$p(m)\ge g(m)$.

Básicamente, lo que está pasando aquí es lo siguiente. Estamos tratando de construir una función.$\omega\rightarrow\omega$. en una condición$(p, f)$, el$p$-part es la cantidad de la función que hemos construido hasta ahora, y la$f$parte es una "promesa" de que a partir de ahora la función que estamos construyendo crecerá al menos tan rápido como$f$.

Esto se llama forzamiento de Hechler . No es el único forzamiento que agrega una función de rápido crecimiento, por supuesto, pero en mi opinión es el más natural (y tiene algunas buenas propiedades de universalidad de teoría de conjuntos, por ejemplo, Truss demostró que si$V[d]$es una extensión forzada del modelo básico$V$dónde$d:\omega\rightarrow\omega$domina todas las funciones en$V$, y$c\in\omega^\omega$es Cohen genérico sobre$V[d]$, entonces$d+c$es Hechler genérico sobre$V$) .

Ahora, una clase importante de preguntas en la teoría de la computabilidad son de la forma:

Supongamos que puedo calcular un real con cierta propiedad. ¿Cuáles son los reales específicos que se me garantiza poder calcular?

Por ejemplo, no es difícil (pensando en el argumento anterior) mostrar que dos reales genéricos de Cohen suficientemente mutuamente no calculan nada en común además de los conjuntos computables (forman un "par mínimo"), por lo que no hay reales específicos que "ser suficientemente Cohen genérico" me permite calcular.

Una pregunta particularmente natural de esta forma, expresada en contraposición, es:

Suponer$x$es computable a partir de cualquier función de crecimiento suficientemente rápido, es decir, hay algún$f:\omega\rightarrow\omega$tal que cualquier$g$dominante$f$calcula$x$. ¿Qué sabemos acerca de$x$?

Resulta que el conjunto de tales reales tiene una caracterización muy ágil:

teorema _ un verdadero$x$es computable a partir de cualquier función de crecimiento suficientemente rápido si es hiperaritmética .

Los conjuntos hiperaritméticos son esencialmente aquellos que se pueden calcular tomando saltos de Turing repetidos , posiblemente infinitos saltos, pero solo "computablemente muchos". (También hay muchas otras caracterizaciones). Definir esto con precisión es complicado, pero no es demasiado difícil de$(i)$demostrar que "la$\omega$el salto de$0$"tiene una definición obvia y$(ii)$argumentar que las cosas se vuelven realmente raras si tratamos de tomar el$\alpha$el salto de$0$para un ordinal contable realmente muy complicado$\alpha$(es decir, cualquiera que no tenga una copia computable).

La prueba del teorema anterior, debido a Solovay si no recuerdo mal, es bastante buena. Demostrar que todo real hiperaritmético es computable a partir de una función de crecimiento suficientemente rápido es una prueba por inducción transfinita, usando una noción generalizada de las funciones Busy Beaver. Lo contrario es la dirección interesante, e implica un análisis inteligente de$\Vdash_{Hechler}$. Si está interesado, la tesis de Peter Gerdes es un buen lugar para comenzar a leer si no recuerdo mal.