¿Se contradice el teorema de incompletitud de Gödel?

Question

Tengo problemas para entender el teorema de incompletitud de Gödel. Supongo que tengo un malentendido de alguna frase o tengo que mirar más de cerca el significado de algún detalle.

El segundo teorema de incompletitud de Gödel afirma que en un sistema libre de contradicciones, esta ausencia de contradicciones no es demostrable ni refutable.

Si encontráramos una contradicción, entonces habríamos refutado la ausencia de contradicciones. El teorema de Gödel afirma que esto es imposible. Así que nunca encontraremos una contradicción. ¿No significa eso que no existe ninguna contradicción? (Si existiera una, podríamos encontrarla.) Así que esto parece ser una prueba de que no existe ninguna contradicción. Así, demostramos la ausencia de contradicciones, lo que contradice el segundo teorema de incompletitud.

Es una contradicción que no puedo resolver.

Answer 1

Soy un poco novato en esto, pero creo que esto puede ayudar.

(Nota: aquí estoy usando la Aritmética de Peano (PA) pero puedes sustituirla por cualquier teoría con la que estés hablando del Segundo Teorema de Incompletitud (G2)).

Definiciones

1. Un teorema de PA se define como una sentencia en el lenguaje de PA (es decir, una cadena de símbolos de PA que satisface ciertas condiciones) que puede concluirse a partir de los axiomas de PA mediante aplicaciones finitas de las reglas de inferencia de PA (las de la lógica de primer orden).
   • Si S es un teorema de PA, decimos que PA demuestra S (simbólicamente, PA $\vdash$ S). En caso contrario, decimos que PA no prueba S (simbólicamente, PA $\nvdash$ S). Con esta notación, podemos enunciar G2 como PA $\nvdash$ ConPA].
2. "PA es consistente" significa que no hay ningún par de teoremas de PA que sean la negación del otro, e "inconsistente" significa no consistente.

Aclarar las nociones clave

Hay un enunciado (llamémoslo ConPA) en el lenguaje de la AP (es decir, ConPA es una cadena de símbolos que puede escribirse realmente -aunque lleva páginas-), que es verdadero en el modelo estándar de la AP si la AP es consistente (y por tanto su negación es verdadera si la AP es inconsistente). Fundamentalmente, por la frase anterior, no quiero decir que PA pueda demostrar ConPA si PA es consistente, y no quiero decir que ConPA es verdadera si PA puede demostrar ConPA. Quiero decir que ConPA es verdadera si PA es consistente. (Cuando la gente habla de si PA puede demostrar su propia consistencia, todo lo que están hablando es si PA demuestra ConPA). G2 es esto: "si PA es consistente, PA no demuestra ConPA, es decir, PA $\nvdash$ ConPA". Nótese que G2 no es un teorema de PA. Tal y como lo he presentado aquí, G2 es sólo un hecho general sobre el mundo, y no es una sentencia (y mucho menos un teorema) de ninguna teoría formal (aunque, según recuerdo, puede ser una especie de paráfrasis y demostrarse en algunas teorías formales de la misma manera que, en PA, ConPA parafrasea "PA es consistente" aunque PA no demuestra ConPA). Es una consecuencia directa de la solidez de PA (el hecho de que los axiomas de PA son verdaderos y las reglas de la lógica de primer orden preservan la verdad) que si PA es consistente entonces PA $\nvdash \neg$ ConPA: esto no es una consecuencia de G2 por lo que veo.

Responder realmente a la pregunta

Si entiendo correctamente la pregunta, expresa la preocupación de que se siga de G2 que PA (o cualquier teoría formal) es consistente ya que si no lo fuera habría una contradicción en ella y eso significaría que PA demostraría su propia inconsistencia, que es justo lo que G2 dice que no puede hacer: una contradicción putativa en sí misma.

Varios problemas con eso: G2 no dice que PA no pueda demostrar su propia inconsistencia; dice que si PA es consistente, no puede demostrar su propia consistencia - una teoría inconsistente demuestra todo en su lenguaje. Aunque de la solidez de la AP (que es un hecho) se deduce que si la AP es consistente entonces la AP no demuestra su propia inconsistencia (y quizás esto se considera a veces parte de G2), esto no demuestra que la AP no demuestra su propia inconsistencia porque no sabemos con seguridad que la AP es consistente. Ahora bien, podría preocupar que bajo el supuesto de que PA es consistente, el hecho (la conclusión de G2) de que no puede probar su consistencia (es decir, probar ConPA) significaría que PA no es consistente y esto contradiría a G2. Pero esta implicación (si no demuestra una sentencia S, entonces S es falsa) sólo se mantendría si PA fuera completa y no lo es, como muestra el primer teorema de incompletitud.

Answer 2

Sé que es tarde, pero tu comentario sobre "dentro" y "fuera" es el quid. Básicamente la "prueba" es siempre relativo al sistema de pruebas.

Definir un sistema formal como útil si tiene un programa verificador de pruebas. Godel demostró efectivamente que existe un programa que, dado el verificador de pruebas para cualquier sistema formal útil $S$ , siempre se emitirá una frase $Con(S)$ sobre PA, tal que ( $\mathbb{N} \vDash Con(S)$ ) si S es consistente. Obsérvese que esto sólo puede afirmarse y probarse en un metasistema que sea lo suficientemente fuerte como para razonar eficazmente sobre los programas y el comportamiento de parada, lo que incluye "saber $\mathbb{N}$ como una "estructura" que satisface la AP. El teorema de Godel-Rosser es que si $S$ es un sistema formal útil y consistente que interpreta la aritmética, entonces $S$ no demuestra la interpretación de $Con(S)$ . Ver este puesto sobre el caso concreto en el que $S$ es una extensión de la AP, y tenga cuidado de no cometer el mismo error que Robert Israel.

Para más detalles y un poco sobre la lógica de la demostrabilidad, véase este puesto . El teorema de incompletitud es, en realidad, mucho más general de lo que exponen la mayoría de los libros de texto, porque se aplica a cualquier sistema formal útil, tal como lo he definido más arriba, incluyendo las lógicas no clásicas, las lógicas aún no descubiertas, ... Para el caso general debemos definir qué significa "interpreta la aritmética", lo que hago en este puesto antes de demostrar el teorema general de incompletitud utilizando una prueba diferente a la de Rosser. Y para una calibración más precisa de lo que es "suficientemente fuerte" para el metasistema, véase este puesto .

Answer 3

Lo hace no afirmar que la ausencia de contradicciones no es refutable. Sin embargo, "el segundo teorema de incompletitud de Gödel afirma que en un sistema libre de contradicciones, esta ausencia de contradicciones no es demostrable" es exacto.

Puede darse el caso de que ZFC, por ejemplo, sea consistente y también que "ZFC es inconsistente" sea un teorema de ZFC.

Answer 4

Así que nunca encontraremos una contradicción. ¿No significa eso que ninguna contradicción existe? (Si existiera una, podríamos encontrarla.) Así que esto parece ser una prueba de que no existe ninguna contradicción.

El problema aquí es la palabra "nunca". Para llegar a algo después de "nunca" para hacer cualquier conclusión tendrías que pasar un tiempo infinito. De lo contrario, no estarías seguro de si algo nunca sucede o simplemente no ha sucedido hasta ahora.