Definición precisa de $\Sigma_0^0$ en la jerarquía aritmética

Question

He encontrado varias definiciones diferentes para $$\Sigma_0^0 = \Pi_0^0 = \Delta_0^0$$ de la jerarquía aritmética. A continuación hay dos definiciones que me parecen diferentes, pero no estoy seguro:

1. Todas las fórmulas aritméticas de primer orden que no tienen cuantificadores no limitados.

2. En la segunda versión, se permite además utilizar funciones recursivas primitivas (o, en otra versión, toda función que pueda definirse recursivamente; esta definición incluye también funciones como la función de Ackermann, pero sólo funciones probadamente totales).

Las funciones recursivas primitivas se pueden formalizar en aritmética de Peano de primer orden utilizando la fórmula de Gödel $\beta$ pero esto parece requerir el uso de cuantificadores no limitados también.

¿Por qué? Supongamos que queremos escribir formalmente una fórmula $\varphi(n)$ de la siguiente forma:

$\forall k<n: \varphi_0(a_k)$

donde $\varphi_0$ es alguna fórmula de primer orden y $a_k$ es la primitiva definida recursivamente por:

$a_0 = C$

$a_{n+1} = F(a_n,n)$

con $C$ una constante y $F$ alguna función ya definida (podría ser simplemente la multiplicación, por el bien del argumento).

Usamos la $\beta$ como aquí:

https://en.wikipedia.org/wiki/G%C3%B6del%27s_%CE%B2_function

Entonces deberíamos escribir $\varphi(n)$ de la siguiente manera:

$\exists b: \exists c<b: \forall k<n: \varphi_0(\beta(b,c,k))\land (\beta(b,c,0) = C)\land \forall i<n:(\beta(b,c,i+1) = F(\beta(b,c,i),i))$

Esencialmente, el cuantificador en $b$ no puede ser acotado (sin utilizar otras funciones recursivas primitivas, y así ad infinitum).

Así que $\varphi(n)$ está en Σ ₁ 0 pero no en Σ ₀ 0 según la primera definición dada anteriormente, mientras que está en Σ ₀ 0 según la segunda definición.

De forma más general, parece que por definición 1 sólo se incluyen las fórmulas decidibles en tiempo polinómico de sus variables (correspondientes a problemas en EXPTIME, ya que es exponencial en el número de bits); la definición 2, en cambio, incluye todas las fórmulas decidibles en tiempo que sea cualquier función recursiva primitiva de sus variables.

Tenga en cuenta que esto no afectará al resto de la jerarquía aritmética, ya que siempre podemos acotar $b$ por una variable dada en un cuantificador "externo" no limitado.

Para terminar, mi pregunta es: ¿son realmente diferentes estas dos definiciones?

Answer 1

Estás hablando de al menos tres posibles definiciones de $\Delta^0_0$ juegos, no sólo dos:

• $\mathcal A=$ los conjuntos definibles con cuantificación acotada, $0$ , $1$ , $+$ y $\times$ .
• $\mathcal B=$ los conjuntos definibles con cuantificación acotada y funciones recursivas primitivas. Son exactamente los conjuntos de la forma $\{x\in\mathbb N\mid f(n)=0\}$ para alguna función recursiva primitiva $f$ ya que siempre podemos codificar la cuantificación acotada utilizando la recursión primitiva.
• $\mathcal C=$ los conjuntos definibles con cuantificación acotada y demostrables (en algún sistema axiomático apropiado) funciones recursivas totales.
• $\mathcal D=$ los conjuntos definibles con funciones recursivas realmente totales -- es decir cada Máquina de Turing que pasa a la detención en cada entrada es un juego justo, no importa si podemos probarlo o no. Estos son exactamente los decidible conjuntos.

Está claro que tenemos $\mathcal A\subseteq \mathcal B\subseteq \mathcal C\subseteq\mathcal D$ pero, como ha supuesto, todas estas inclusiones son estrictas.

Su argumento sobre la decidibilidad en tiempo polinómico funciona para dinstinguir $\mathcal A$ de $\mathcal B$ -- el teorema de la jerarquía temporal producirá un conjunto que está en $\mathcal B$ pero no en $\mathcal A$ .

Para ver que $\mathcal B\ne \mathcal C$ podemos construir un conjunto en $\mathcal C\setminus\mathcal B$ por diagonalización, ya que las funciones recursivas primitivas son efectivamente enumerables.

Para ver que $\mathcal C\ne\mathcal D$ , tenga en cuenta que el probadamente Las máquinas de Turing totales son efectivamente enumerables, así que podemos hacer el mismo truco de diagonalización una vez más. Sin embargo, para esta prueba tenemos que suponer que el sistema de pruebas que utilizamos para definir $\mathcal C$ es sonido con respecto a los verdaderos números naturales.

La razón por la que se permite que esta confusión persista es que no importa cuál de $\mathcal A$ , $\mathcal B$ , $\mathcal C$ o $\mathcal D$ se elige como $\Delta^0_0 = \Pi^0_0 = \Sigma^0_0$ obtenemos lo mismo $\Sigma^0_1$ en todos los casos, es decir, ¡exactamente los conjuntos recursivamente enumerables! De manera similar, $\Pi^0_1$ es siempre exactamente el conjunto co-r.e., y todo el resto de la jerarquía aritmética es la misma en los tres casos.

(Y así, en cada caso obtenemos $\Delta^0_1=\mathcal D$ . Curiosamente, los dos argumentos diferentes para $\mathcal A\ne \Delta^0_1$ Ofrecí en mi respuesta anterior se dividen muy bien en los argumentos para la inclusión estricta dados anteriormente).