¿Cuál es la diferencia entre los teoremas de completitud e incompletitud de Gödel?

Question

¿Cuál es la diferencia entre los teoremas de completitud e incompletitud de Gödel?

Answer 1

En primer lugar, obsérvese que, a pesar de sus nombres, una no es la negación de la otra.

El teorema de exhaustividad se aplica a cualquier teoría de primer orden: Si $T$ es una teoría de este tipo, y $\phi$ es una frase (en la misma lengua) y cualquier modelo de $T$ es un modelo de $\phi$ entonces existe una (de primer orden) prueba de $\phi$ utilizando las declaraciones de $T$ como axiomas. A veces se dice esto como "cualquier cosa verdadera es demostrable".

El teorema de incompletitud es más técnico. Dice que si $T$ es una teoría de primer orden que es:

1. Recursivamente enumerable (es decir, existe un programa informático que puede enumerar los axiomas de $T$ ),
2. Coherente, y
3. Capaz de interpretar cierta cantidad de aritmética Peano (típicamente, se requiere el fragmento conocido como Q de Robinson),

entonces $T$ no está completa, es decir, hay al menos una frase $\phi$ en la misma lengua que $T$ tal que existe un modelo de $T$ y $\phi$ y también existe un modelo de $T$ y $\lnot\phi$ . Equivalentemente (por el teorema de completitud), $T$ no puede probar $\phi$ y también $T$ no puede demostrar $\lnot\phi$ .

Se suele decir lo siguiente: Si una teoría es razonable y al menos modestamente sólida, entonces no es completa.

El segundo teorema de incompletitud es más llamativo. Si realmente exigimos que $T$ interpreta la Aritmética de Peano, entonces de hecho $T$ no puede demostrar su propia coherencia. Entonces: No hay forma de probar la consistencia de una teoría matemática razonablemente fuerte, a menos que estemos dispuestos a asumir un escenario aún más fuerte para llevar a cabo la prueba. O bien: Si una teoría razonablemente fuerte puede demostrar su propia consistencia, entonces es de hecho inconsistente. (Nótese que cualquier teoría inconsistente demuestra cualquier cosa, en particular, si su lenguaje nos permite formular esta afirmación, entonces puede demostrar que es consistente).

El requisito de que $T$ es recursivamente enumerable es razonable, creo yo. Formalmente, una teoría no es más que un conjunto de sentencias, pero nos interesan sobre todo las teorías que podemos escribir o, al menos, para las que podemos reconocer si algo es un axioma o no.

El requisito de interpretabilidad suele presentarse de forma más restrictiva, por ejemplo, pidiendo que $T$ es una teoría sobre los números y contiene la Aritmética de Peano. Pero la versión que he mencionado se aplica en más situaciones; por ejemplo, a la teoría de conjuntos, que no es propiamente una teoría sobre números, pero puede interpretar fácilmente la teoría de números. El requisito de interpretar la Aritmética de Peano es doble. En primer lugar, buscamos teorías que nos permitan (mediante codificación) llevar a cabo al menos cierta cantidad de práctica matemática común, y la teoría de números es señalada como la forma habitual de hacerlo. Y lo que es más importante, queremos que sea posible cierto grado de "codificación" dentro de la teoría, de modo que podamos hablar de sentencias y pruebas. La teoría de números nos permite hacerlo fácilmente, y así podemos hablar de "la teoría es consistente", una afirmación sobre pruebas, aunque nuestra teoría sea realmente sobre números y no sobre fórmulas de primer orden.

Answer 2

Añadiré algunos comentarios ...

Es útil enunciar el Teorema de Completitud de Gödel de esta forma :

si un wff $A$ de una teoría de primer orden $T$ está lógicamente implicada por los axiomas de $T$ entonces es demostrable en $T$ donde " $T$ implica lógicamente $A$ "significa que $A$ es cierto en todos los modelos de $T$ .

El problema es que la mayoría de las teorías matemáticas de primer orden tienen más de un modelo; en particular, esto ocurre para $\mathsf {PA}$ y sistemas afines (a los que se aplica el (Primer) Teorema de Incompletitud de Gödel).

Cuando "vemos" (con perspicacia) que la fórmula indemostrable del Teorema de Incompletitud de Gödel es verdadera, nos referimos a nuestra "lectura natural" de la misma en la interpretación pretendida de $\mathsf {PA}$ (la estructura formada por el número natural con la suma y la multiplicación).

Por lo tanto, existe alguna "interpretación no intencionada" que también es un modelo de $\mathsf {PA}$ en los que no se cumple la fórmula anterior. Esto a su vez implica que la fórmula indemostrable no está lógicamente implicada por los axiomas de $\mathsf {PA}$ .