¿Cuál es el grado de verdad de Turing?

Question

Primero que todo, por la Verdad quiero decir que el conjunto de $T$ de la Gôdel números de la verdadera fórmulas de primer orden de la aritmética.

De primer orden de la aritmética no es decidable y $T$ no es decidable, además el undefinability teorema dice que $T$ no puede ser expresado en primer orden de la lógica, por lo $T$ no pertenece a la aritmética y de la jerarquía de su grado de Turing es, al menos, $\omega$.

¿Cuál es entonces la de Turing grado de $T$?

Hay un buen libro de texto que alguien puede sugerir que este tipo de temas se explican a fondo?

Answer 1

$T$ no pertenece a la aritmética y de la jerarquía de su grado de Turing es, al menos, $\omega$.

Un par de comentarios rápidos:

• Asumo "$\omega$" debe ser "$0^{(\omega)}$" - en cuyo caso eso es correcto - desde $\omega$ no es un grado de Turing.

• De manera más sustantiva, existe un grave problema en su razonamiento. Es verdad que el $T$ no puede ser aritmética. Sin embargo, esto no es suficiente para concluir que $T\ge_T0^{(\omega)}$: hay Turing grados incomparable con $0^{(\omega)}$ (y, por tanto, no aritmética o $\ge_T0^{(\omega)}$), e incluso de Turing grados por encima de todos los de la aritmética establece que son incomparables con $0^{(\omega)}$ (este segundo hecho es una instancia de la más general pareja exacta teorema).

Para mostrar que $T\ge_T0^{(\omega)}$, necesita argumentar que dado $\langle a,b\rangle\in\mathbb{N}^2$ usted puede encontrar - computably - una frase $\varphi$ , lo cual es cierto iff $b\in 0^{(a)}$. Usted puede hacer que a través de Kleene de la $T$-predicado. Por el contrario, para mostrar $0^{(\omega)}\ge_TT$ acaba de mostrar de que manera uniforme la $\Sigma_n$-teoría de la $\mathbb{N}$ tiene grado de Turing $0^{(n)}$. Soare el libro es una buena fuente de este material.