Hay una declaración independiente de la PA y no aumenta la consistencia de la fuerza?

Question

Se conocen muchos independencia resultado de la PA, por ejemplo, el teorema de Goodstein, París-Harrington y teorema de la reflexión principio. Pero estos ejemplos implican la consistencia de PA.

Supongo que no todos independiente de la declaración de PA implica la consistencia de PA. He intentado encontrar ejemplos de este tipo, pero aún no puedo probar la existencia de tal proposición. Agradecería su ayuda.

Answer 1

El Rosser sentencia de $\rho$ es un ejemplo.

El Rosser sentencia de $\rho$ para una teoría T (contiene algunos débiles aritmética) es la afirmación de que para cada prueba de $\rho$$T$, hay un corto a prueba de $\neg\rho$, es decir, una prueba con un pequeño código de Gödel. (Se puede utilizar el punto fijo lema para manejar la aparente auto-referencia).

Si $T$ es consistente, entonces $\rho$ es independiente de $T$, por el siguiente argumento bien conocido. Si $T\vdash\rho$, $T$ no demuestran $\neg\rho$, pero, a la luz de lo $\rho$ expresa. Por lo $T\not\vdash\rho$. Del mismo modo, si $T\vdash\neg\rho$, $T$ tendría que demostrar que existe un menor prueba de $\rho$, lo que no puede porque es coherente.

Por lo tanto, hemos demostrado $\text{Con}(T)\to\text{Con}(T+\rho)\wedge\text{Con}(T+\neg\rho)$, en una muy débil de la teoría. Por lo tanto, $T+\rho$ $T+\neg\rho$ son equiconsistent con $T$. Por lo $\rho$ es una frase que es indepdnent de $T$, sin aumentar la coherencia de la fuerza.

En particular, el Rosser sentencia de $\rho$ es estrictamente más débil de lo $\text{Con}(T)$.

Answer 2

Puede atacar a este tipo de pregunta por el pensamiento acerca de la Lindenbaum-Tarski álgebra para PA. Esto puede ser visto como un orden parcial $\preceq$ en el conjunto de todas las sentencias en el lenguaje de la aritmética, en donde tenemos $\phi \preceq \psi$ si y sólo si $PA + \psi \vdash \phi$. (Es posible utilizar el orden opuesto, pero yo prefiero tener más fuertes condenas de ser superior en el orden de los más débiles oraciones).

Un hecho acerca de este orden es que, cuando hacemos uso de la PA o otros lo suficientemente fuerte teorías, el orden es densa: si $\phi \prec \psi$, entonces hay una frase que $\theta$$\phi \prec \theta \prec \psi$. Una forma de construir $\theta$ es comenzar con una frase $\chi$ que es independiente de la $\text{PA} + \phi + \lnot \psi$ y, a continuación, deje $\theta = \psi \lor (\phi \land \chi)$.

Así que, para responder a la pregunta, si dejamos $\phi$ ser una sentencia demostrable en PA, y dejamos $\psi$ ser Con(PA), luego tenemos a $\phi \prec \psi$, y así por la densidad de una frase de $\theta$ estrictamente entre ellos. Esta frase $\theta$ no es demostrable en PA, debido a que es estrictamente por encima de $\phi$, pero esto no implica Con(PA), debido a que es estrictamente por debajo Con(PA).

Es mucho más difícil encontrar "natural" ejemplos de oraciones independientes de PA que implica, pero no implican, Con(PA). La construcción en general muestra que hay al menos algunas frases con que los bienes, sin embargo. El ejemplo construido como es arriba es esencialmente $$\text{Con}(\text{PA}) \lor \text{Con}(\text{PA} + \lnot\text{Con}(\text{PA}))$$ donde $\text{Con}(\cdot)$ es el Gödel/Rosser coherencia de la frase.

Answer 3

He aquí una prueba de que existe una sentencia (aunque como Carl observa, este no da un ejemplo de una frase). Vamos a suponer $PA$ es consistente a través de todo.

Supongamos hacia una contradicción que por cada $\varphi$ que es independiente de la $PA$, $\varphi$ o $\neg\varphi$ demuestra $Con(PA)$. Tenga en cuenta que desde $PA$ es consistente, esto significa que para cualquier $\varphi$ que es independiente de la $PA$, exactamente uno de $\varphi$ $\neg\varphi$ implica $Con(PA)$ (si ambos $\varphi$ $\neg\varphi$ implícitas $Con(PA)$,$PA\vdash Con(PA)$, lo $PA$ es inconsistente).

Pero esto nos permite construir una computable consistente finalización de $PA$, como sigue. Enumerar las sentencias de la aritmética como $\{\psi_i: i\in\mathbb{N}\}$, y definir una secuencia de sentencias $\varphi_i$ $(i\in\mathbb{N})$ de la siguiente manera:

• Supongamos que hemos definido a $\varphi_j$ todos los $j<i$. Deje $\theta_i=\bigwedge_{j<i}\varphi_j$ ser el conjunto de todas las $\varphi$s hasta el momento. Por inducción, vamos a tener cuatro casos, exactamente uno de los cuales tiene: $PA+\theta_i$ demuestra $\psi_i$ o $PA+\theta_i$ demuestra $\neg\psi_i$ o $PA+\theta_i+\psi_i$ demuestra $Con(PA)$ o $PA+\theta_i+\neg\psi_i$ demuestra $Con(PA)$.

• Mediante la búsqueda a través de todas las posibles pruebas de $PA+\theta_i$, podemos determinar de forma efectiva que de estos cuatro casos se mantiene. Ahora nos definen $\varphi_i$ como sigue. Si el caso de $1$ o $4$ mantiene, $\varphi_i=\psi_i$; si el caso $2$ o $3$ mantiene, $\varphi_i=\neg\psi_i$.

Ahora no es difícil comprobar que $PA\cup\{\varphi_i: i\in\mathbb{N}\}$ es una computable consistente finalización de $PA$ - contradice el teorema de Gödel.