He visto en Wikipedia la existencia de una secuencia infinita de grados de Turing $\bf{a_0}, \bf{a_1}, \dots$ tal que $\bf{a}_{i+1}' \leq_T \bf{a}_i$ donde $\bf{a}_{i+1}'$ es el salto de Turing de $\bf{a}_i$ .
Sin embargo, no he podido encontrar referencias para este resultado. ¿Es una consecuencia trivial de uno de los conocidos teoremas de inversión de saltos?
Seguramente hay una prueba utilizando sólo la teoría de la recursión clásica, pero la prueba que conozco utiliza la aritmética de segundo orden.
Tome un $\omega$ -modelo $M$ de $\mathsf{ATR}_0$ en la que existe un orden lineal contable $L$ tal que $M$ satisface " $L$ está bien fundado", pero tal que $L$ no está realmente bien fundado. Entonces, $M$ cree que hay un conjunto $H$ que se obtiene iterando el salto de Turing a lo largo de $L$ empezando por $\emptyset$ porque esto es demostrable en $\mathsf{ATR}_0$ .
Porque $M$ es un $\omega$ -es absoluta para declaraciones de la forma " $A' = B$ " cuando $A,B \in M$ . Así, si tomamos una secuencia descendente infinita $(a_i : i \in \omega)$ en $L$ y que $(A_i : i \in \omega)$ sea la correspondiente secuencia de conjuntos en $H$ entonces $A_{i+1}' \leq_T A_i$ para todos $i \in \omega$ .
Este método puede ampliarse fácilmente para obtener resultados más contundentes; por ejemplo, podríamos hacer $A_{i+1}^{(\omega)} \leq_T A_i$ .
El uso de $\mathsf{ATR}_0$ no es realmente necesario aquí. El punto clave es que hay un ordenamiento lineal $L$ de $\omega$ que no es una ordenación de pozos, para la que existe un conjunto $H^L$ que satisface la definición aritmética de ser la iteración del salto de Turing a lo largo de $L$ empezando por el conjunto vacío. Este tipo de conjunto $H^L$ se conoce más generalmente como "pseudojerarquía".
La existencia de un $L$ se deduce inmediatamente del hecho estándar de que el conjunto de ordenamientos de pozos de $\omega$ no es $\Sigma^1_1$ definible. La afirmación " $L$ es un orden lineal y $H(L)$ existe" es un $\Sigma^1_1$ fórmula con el parámetro $L$ que se satisface en todo ordenamiento de pozos de $\omega$ por lo que también debe ser satisfecha por algún otro conjunto $L$ ; esto $L$ satisfará la declaración de "punto clave" del párrafo anterior.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
