Arma grupos

Question

¿Alguien sabe de una forma de mostrar que un $\Sigma^0_n$-conjunto completo no $\Pi^0_n$ sin tener que apelar a $\Sigma^0_n$-universal establece?

Por ejemplo un argumento de diagonalización más directo para mostrar que $\overline{\text{Tot}}$ no $\Pi^0_2$.

Nota: soy consciente de que el hecho de que $\overline{\text{Tot}}$ no $\Pi^0_2$ se deduce fácilmente el hecho de que $\text{Tot}$ $\Pi^0_2$-completa y el teorema de recursión.

Answer 1

Deje $P$ ser el complemento de Tot. Si $P$$\Pi^0_2$, entonces, puesto que ya es $\Sigma^0_2$, sería $\Delta^0_2$ y, por lo tanto, $P$ y Tot sería computable de $0'$. Por simplicidad, identificar los conjuntos con sus funciones características.

Por lo tanto, por el límite lema, no sería una manera uniforme computable de la secuencia de funciones de $(f_i)$ tal que $\text{Tot} = \lim_{i\to\infty} f_i$. Considere la posibilidad de un programa de $e$ que hace lo siguiente: en la entrada de $2^e3^n$, devuelve el mínimo de $i > n$ tal que $f_i(e) = 0$. En todas las otras entradas, $e$ inmediatamente devuelve 0. Ahora $e$ total si y sólo si hay arbitrariamente grande,$i$$f_i(e) = 0$. Pero, debido a $(f_i)$ converge a Tot, hay arbitrariamente grande, $i$ $f_i(e) = 0$ si y sólo si $\lim_{i\to\infty} f_i(e) = 0$, si y sólo si $e$ no está en Tot. Por lo $e$ calcula el total de la función si y sólo si no es en Tot, lo cual es una contradicción, mostrando Tot (y su complemento) no $\Delta^0_2$.

Es que el tipo de diagonalización que usted está buscando?