Dado un φ independiente de la PA, lo cual es cierto en el modelo estándar, siempre (PA+ φ) ω-incompatible? Qué significa que cada una de estas φ puede ser usado para demostrar que una máquina de Turing se detiene en un determinado C cuando realmente nunca detener?
Respuesta
¿Demasiados anuncios?
La definición habitual de $\omega$ consistencia:
Una teoría de la $T$$\omega$ -inconsistente si no hay una fórmula $\psi$ tal que $T$ demuestra $(\exists x)\psi(x)$, e $T$ también es $\lnot \psi(n)$ por separado para cada número natural $n$.
$T$ $\omega$- consistente si no es $\omega$-incoherente.
La propiedad de que "para cada frase $\psi$, si la teoría de la prueba $\psi$ $\psi$ es verdadera en el modelo estándar" que se llama "aritmética solidez" de la teoría de la $T$. La declaración de la "si $T$ demuestra que una máquina de Turing se detiene, a continuación, hace detener" es un caso especial de la solidez conocido como "1-consistencia", que se define formalmente el uso de una cierta clasificación de las fórmulas. Una fórmula en el lenguaje de la aritmética se llama $\Sigma^0_1$ si es de la forma $(\exists x)\psi(x)$ donde $\psi(x)$ sólo ha delimitado cuantificadores. Resulta que para cualquier máquina de Turing $m$, la declaración "$m$ se detiene en la entrada de $x$" puede ser expresado como $\Sigma^0_1$ fórmula $\psi(x)$, y viceversa. 1-la consistencia se define como la solidez de $\Sigma^0_1$ fórmulas.
Desafortunadamente, sólo hay una débil relación entre la aritmética solidez, 1-consistencia y $\omega$-consistencia:
- (1) Cada suficientemente fuerte $\omega$-consistente de la teoría es 1-consistente, es decir, $\Sigma^0_1$ sonido. "Suficientemente fuerte" aquí incluye el supuesto de que la teoría resulta cada cierto $\Sigma^0_1$ frase - PA tiene esta propiedad.
Los siguientes ejemplos muestran que no podemos fortalecer a la declaración de mucho:
(2) Hay teorías que se $\omega$-de acuerdo, pero no aritméticamente sonido: demostrar frases que son falsas en el modelo estándar de la aritmética. Algunas de estas teorías son incluso de la forma $PA + \lnot\phi$ por una condena $\phi$ que es verdad en el modelo estándar e independiente de la PA.
(3) Hay $1$-consistente teorías (es decir, $\Sigma^0_1$ sonido) que se $\omega$-incoherente. Algunas de estas teorías son incluso de la forma $PA + \lnot\phi$ por una condena $\phi$ que es verdad en el modelo estándar e independiente de la PA.
Ejemplo (2), muestra que no es el caso que $PA + \lnot \phi$ se $\omega$-inconsistentes, que responde a la primera parte de la pregunta.
Ejemplo (3) muestra que es posible para $PA + \lnot \phi$ $\Sigma^0_1$ sonido, en cuyo caso no demuestra que una máquina de Turing se detiene a menos que la máquina no se detenga. Que responde a la segunda parte de la pregunta.
