Teorema de completitud e incompletitud Gödel

Teorema de Gödel.

Gödel quiso certificar que las matemáticas no podían ser demostradas solo por axiomas formales debido que, es un trabajo imposible porque la axiomática es incompleta, y la matemática no es limitada. Por tal razón Gödel, se basó completamente en el intuicionismo, tomando en cuenta las definiciones y demostraciones.

Es importante aclarar que el teorema no pone en cuestión a la matemática sino a los sistemas axiomáticos.

Teorema de completitud de Gödel

Como su nombre lo indica, es un teorema de completitud porque, todas las verdades lógicas expresables mediante el sistema son demostrables dentro del mismo sistema. Es denominado como un sistema completo.

Ejemplificando el teorema de completitud se deduce:

Si A es lógicamente verdadera, entonces A es deducible, es decir, "Si ╞ A, entonces ├ A".

Esto nos indica que, el sistema formal de la lógica cuantificacional será completo si todas las fórmulas que representan verdades lógicas son formalmente deducibles en el sistema.

La prueba del teorema de completitud, demuestra lo siguiente:

(1) ╞ A

Si (1) es verdadera, entonces ¬A, «no A», es insatisfacible, esto es, falsa para cualquier interpretación.

(2) ¬ ╞ ¬A

Y si ¬A es insatisfacible, es inconsistente, esto es, se puede deducir de ella una fórmula y su contraria:

(3) ¬A ├ B ^ ¬A ├ ¬B

Puesto que ¬A es inconsistente, ¬¬A («no, no A»), su negación, es consistente:

(4) (¬A ├ B ^ ¬A ├ ¬B) → ├ ¬¬ A

Por Modus Ponens entre (3) y (4), se obtiene

(5) ├ ¬¬A

Y aplicando la doble negación sobre (5), se obtiene:

(6) ├ A

Y puesto que a partir de ╞ A hemos llegado a ├ A, queda demostrado el teorema de Gödel

(7) ╞ A → ├ A

Teorema de incompletitud de Gödel

Se divide en dos célebres teoremas.

Primer teorema de incompletitud de Gödel.

Indica que, cualquier teoría aritmética recursiva que sea consistente es incompleta ¿Por qué?, la respuesta es que un sistema axiomático que se derive de la aritmética, es necesariamente incompleto, en consecuencia existen fórmulas matemáticas verdaderas, que se derivan de la aritmética que no podría deducirse por los axiomas matemáticos usuales.

Demostración del primer teorema de incompletitud de Gödel.

Imaginemos que se ha dado un sistema de axiomas para la aritmética que es consistente y que solo admitimos demostraciones verificables algorítmicamente.

Demostremos que, existe un enunciado, denominado G, el cual ni él ni su negación es demostrable, a partir de esos axiomas.

El primer paso de la demostración consiste en asignar a cada enunciado aritmético un número natural, al que llamaremos el número de Gödel de ese enunciado.

Por ejemplo, al enunciado “2 es par” podría corresponderle el número 19, mientras que al enunciado “9 es primo” podría corresponderle el número 44.

Debemos hacer aquí dos aclaraciones importantes.

La primera es que la asignación de números de Gödel alcanza a todos los enunciados, tanto a los verdaderos como a los falsos.
La segunda aclaración es que; los ejemplos dados hipotéticos y sirven solamente para facilitar la comprensión de la idea. Para asignar realmente los números de Gödel a los enunciados estos deben estar previamente escritos en un lenguaje formal específico y la asignación en sí se hace mediante fórmulas claramente definidas.

Segundo teorema de incompletitud de Gödel.

Afirma que, en toda teoría aritmética recursiva consistente T, la fórmula Consistente T no es un teorema. ¿Por qué?, la respuesta es que no puede probarse un sistema axiomático que se derive de la aritmética sea consistente, dentro de la lógica del propio sistema. Es decir, no se puede garantizar que un sistema se deriva de la aritmética sea consistente sin involucrar elementos externos del mismo.

Para demostrar el segundo teorema de incompletitud de Gödel.

Debemos tomar en cuenta que para su demostración se requiere traducir el primer teorema a una fórmula el cual afirma que si T es consistente, entonces G no es demostrable.

La fórmula que afirma la consistencia de T es consistente T, mientras que la fórmula que afirma la indemostrabilidad de G es la propia G. La fórmula que traduce el primer teorema es consistente T → G, donde “→“ significa implicación.

Gödel demostró que esta fórmula es un teorema, y que por lo tanto consistente T no es un teorema: si lo fuera, de las reglas básicas de T como teoría formal se deduciría que G es demostrable, en contradicción con el enunciado del primer teorema de incompletitud.