Pruebas de coherencia para dos sistemas formales

Question

¿Existen dos sistemas formales, $F_1$ y $F_2$ tal que $F_1$ prueba $F_2$ es coherente y $F_2$ prueba $F_1$ ¿es coherente? ¿Evitarían estas pruebas el Segundo Teorema de Incompletitud de Gödel? Por "consistente", quiero decir que el sistema formal no prueba $X$ y NO $X$ .

Answer 1

La respuesta a su pregunta es no.

¡Estas cosas pueden ser sutiles! Permítanme primero dar una prueba informal, y luego ampliarlo en una respuesta real; sin la prueba informal, me preocupa que mi argumento riguroso parecerá lógica espagueti (pruebas que utilizan frases como "... demuestra que ... demuestra que ..." son realmente difíciles de leer sin saber ya la idea principal).

Prueba informal : Si $F_2$ es incoherente, entonces $F_1$ lo sabe - una prueba de una contradicción en $F_2$ puede verificarse mediante $F_1$ . Desde $F_1$ demuestra que $F_2$ es coherente lo que significa que si $F_2$ es incoherente, entonces también lo es $F_1$ (ya que $F_1$ demostraría tanto " $F_2$ es coherente" por suposición, y " $F_2$ es incoherente" por la frase anterior).

Además, el párrafo anterior es bastante básico - en particular, $F_2$ ¡puede probarlo! Así que $F_2$ prueba "Si $F_2$ es incoherente, entonces $F_1$ es incoherente"; o, en contrapositivo, "Si $F_1$ es coherente, entonces $F_2$ es coherente".

Pero $F_2$ demuestra " $F_1$ es coherente". Combinando las dos frases anteriores, $F_2$ demuestra " $F_2$ es consistente". Así que el Segundo Teorema de Incompletitud de Goedel va CHOMP.

---

Muy bien, ahora vamos a intentar hacerlo riguroso.

Empecemos por señalar algunos supuestos que faltan, empezando por fuerza . Los teoremas de Goedel se aplican a suficientemente fuerte sistemas - hay sistemas débiles que demostrar su propia coherencia porque no demuestran propiedades básicas sobre la demostrabilidad. El uso de un sistema de este tipo como $F_1$ y $F_2$ da una respuesta positiva a su pregunta, pero por una razón muy tonta. Así que queremos restringir la atención a los sistemas que son lo suficientemente fuertes como para que la pregunta sea interesante; por ejemplo, los sistemas que amplían $PA$ (aunque esto es una exageración masiva).

También debemos limitar la atención a las teorías que no sean demasiado complicadas: hay son teorías definibles aritméticamente que demuestran su propia consistencia ¡!

Por último, volviendo a la fuerza, estamos pensando en dos teorías que "se miran". No basta con que las teorías en cuestión sean fuertes; tienen que conozca que son fuertes. En concreto, vamos a necesitar un supuesto adicional, $(\dagger)$ que $PA$ prueba que las teorías se extienden cada una $PA$ . Llamaremos a esta teoría extensión visible de $PA$ . (Hay teorías extrañas que se extienden $PA$ pero $PA$ -sin duda. Por cierto, para un fenómeno realmente extraño en torno a $(\dagger)$ Ver este deliciosamente llamado artículo de Visser .)

EDIT: Resulta que $(\dagger)$ no es necesario. Sin embargo, como la prueba de esto no es trivial, voy a dejar esta respuesta como está, y simplemente remitir al lector al resultado mejorado .

Si restringimos la atención a tales teorías, entonces la respuesta a su pregunta es no .

El punto clave es el siguiente:

$(*)\quad$ Si $T$ es una teoría que amplía $PA$ entonces $T$ prueba cada verdad $\Sigma_1$ sentencia. Además, si $S$ es una extensión axiomatizable recursivamente de $PA$ satisfaciendo $(\dagger)$ entonces $S$ demuestra la frase anterior.

No voy a demostrar este hecho aquí, pero se pueden encontrar pruebas en varios lugares. Actualmente estoy buscando una buena referencia .

Obsérvese que la segunda frase de la afirmación anterior presupone que el primero _es expresable en aritmética. Esto puede parecer dudoso, ya que en general la verdad no es definible . Sin embargo, los predicados de verdad definibles para_ clases restringidas de oraciones existen; en particular, el conjunto de oraciones verdaderas $\Sigma_1$ sentencias es definible en aritmética, por un $\Sigma_2$ fórmula.

Además, vale la pena señalar que -en cuanto al Segundo Teorema de Incompletitud de Goedel en sí- PA es exagerado. Basta con sistemas mucho más débiles.

También observamos:

Si $W$ es una teoría axiomatizable recursivamente y $\varphi$ es una frase, entonces la frase " $W$ prueba $\varphi$ " es $\Sigma_1$ .

De hecho, las afirmaciones de demostrabilidad son el seulement tipo de $\Sigma_1$ hecho que nos interesará aquí.

---

Ahora estamos listos para en realidad responder a su pregunta:

No hay teorías $F_1, F_2$ que son extensiones visibles consistentes y recursivamente axiomatizables de $PA$ que demuestran mutuamente su coherencia.

Prueba . Iré línea por línea. Destacaré dos supuestos:

• (1) $F_1$ demuestra que $F_2$ es coherente.

• (2) $F_2$ demuestra que $F_1$ es coherente.

y dos hechos sobre la demostrabilidad:

• (A) $F_i$ demuestra cada verdad $\Sigma_1$ sentencia, por $i\in\{1, 2\}$ .

• (B) $F_i$ demuestra que $F_j$ demuestra cada verdad $\Sigma_1$ sentencia, por $i, j\in \{1, 2\}$ .

Es decir, (A) y (B) corresponden a la primera y segunda frases de $(*)$ respectivamente.

¡Así que vamos!

• Por (2) y (A), $F_1$ demuestra " $F_2$ prueba $F_1$ es coherente".

• Por (B), $F_1$ prueba "Si $F_1$ es incoherente, entonces $F_2$ prueba $F_1$ es incoherente".

• Por las dos líneas anteriores, $F_1$ prueba "Si $F_1$ es incoherente, entonces $F_2$ demuestra " $F_1$ es coherente" y $F_2$ demuestra " $F_1$ es incoherente".

• Eso es, $F_1$ prueba "Si $F_1$ es incoherente, entonces $F_2$ es incoherente".

• Pero por (1) y el contrapositivo de la línea anterior, $F_1$ demuestra " $F_1$ es coherente".

• . . . Así que $F_1$ es inconsistente por el Segundo Teorema de Incompletitud de Goedel.