Demostración original del teorema de completitud de Gödel

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En 1930 Gödel demostró la completitud de la lógica cuantificacional de primer orden. Literalmente el teorema de completitud de Gödel establece: "Para toda fórmula A de la lógica cuantificacional de primer orden, si A es lógicamente verdadera, entonces A es deducible". Dicho formalmente: "Si ╞ A, entonces ├ A". Esto quiere decir 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 se reduce a consignar las siguientes premisas
  1. A es lógicamente verdadera: A ╞ A.
  2. Si A es lógicamente verdadera, entonces ¬A es insatisfacible.
  3. Si ¬A es insatisfacible, entonces ¬A es inconsistente.
  4. Si ¬A es inconsistente, entonces da lugar a contradicción: ¬A ├ B y ¬A ├ ¬B.
  5. Si ¬A ├ B y ¬A ├ ¬B, entonces ├ A.
La justificación de estas premisas es la siguiente

1) Es la hipótesis del teorema de completitud;

2) Se sigue de la definición del concepto de fórmula lógicamente verdadera: su negación ha de ser insatisfacible;

3) Es la contraposición del teorema de Henkin;

4) Es un mero análisis de la definición de inconsistencia, y finalmente

5) Se basa en el teorema de deducción, que permite pasar de ¬A ├ B y ¬A ├ ¬B a ├ ¬A ^ B y ├ ¬A ^ ¬B, respectivamente, y en Modus Ponens, que permite, con ayuda de estas dos últimas fórmulas, eliminar los antecedentes en la ley de reducción al absurdo (├ (¬A ^ B) ® ((¬A ^ ¬B) ^ ¬¬A); de ├ ¬¬A se pasa a ├ a mediante una aplicación de MP a la ley de doble negación ├ ¬¬A ^ A.

Aceptadas estas premisas, se les aplica reiteradamente la regla MP, empezando por 2) y 1), siguiendo con 3) y el consecuente de 2), y así sucesivamente, hasta liberar el consecuente de 5): ├ A, que es justamente la tesis del teorema de Gödel, el cual queda, por tanto, demostrado.

Referencias[editar]

  • Über die Vollständigkeit des Logikkalküls. Doctoral dissertation. University Of Vienna.. 1929.  Primera demostración del teorema de completitud.
  • Gödel, K (1930). «Die Vollständigkeit der Axiome des logischen Funktionenkalküls» (en German). Monatshefte für Mathematik 37:  pp. 349–360. doi:10.1007/BF01696781. JFM 56.0046.04.  El mismo material que en la disertación, pero con demostraciones más breves, explicaciones más suscintas, y omitiendo la extensa introducción.