¿Cuántas variables se qué se necesita para ser completa para $\Sigma^0_n$?

Question

La aritmética de la jerarquía es una estructura en frases en primer orden la lógica. Tiene una relación particular con la computabilidad, debido a Post del Teorema.

En la mayoría de los debates de la media aritmética de la jerarquía, se supone que usted tiene acceso a cada fórmula $\phi$ en el primer orden de la lógica. Pero, ¿qué si no? Específicamente, lo que si definimos $\Sigma_{n,m}^0$ a ser el habitual conjunto de $\Sigma_n^0$ excepto usted sólo tiene fórmulas con un total de $m$ variables ($n\leq m$).

¿Cuál es la teoría de la computabilidad poder de este conjunto? Hay un número de variables que es suficiente para obtener el poder total de $\Sigma_n^0$? Lo que si establecemos $m=n$?

Answer 1

Por Matiyasevich del Teorema, el universal, $\Sigma_n$ fórmula es equivalente a una de la forma

$\exists y_1 \forall y_2 \cdots Q y_n Q^* y_{n+1} \phi( x, \bar y)$,

donde $Q$ e $Q^*$ son los adecuados cuantificador y delimitada cuantificador, respectivamente, y $\phi$ es libre de cuantificadores. Esto significa que usted sólo necesita $n+1$ variables para conseguir el poder total de $\Sigma_n$---con la salvedad, como @James ha criado, que su lenguaje debe ser la misma que la utilizada por Matiyasevich.

La eliminación de una variable reduce su potencia de cálculo para que de $\Sigma_{n-1}$. Por ejemplo, si $\phi$ es cuantificador libre, el conjunto $\{x :\exists y \phi(x,y)\}$ es decidable por primera utilizando el cálculo para encontrar los límites superior e inferior sobre la posible $y$, y luego el control de cada uno de los valores a mano.