Diferencia entre revisiones de «Teorema de completitud de Gödel»
Página reemplazada por «En 1930 Gödel '''demostró la completitu de la lógica cuantificacional de primer orden.''' Literalmente el Teorema d;La prueba del teorema de completitud se reduce a c...». |
m Revertidos los cambios de 190.232.8.157 a la última edición de Bigsus-bot |
||
| Línea 1: | Línea 1: | ||
En 1930 Gödel '''demostró la |
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: |
|||
# A es lógicamente verdadera: | A= A. |
|||
# Si A es lógicamente verdadera, entonces ¬A es insatisfacible. |
|||
# Si ¬A es insatisfacible, entonces ¬A es inconsistente. |
|||
# Si ¬A es inconsistente, entonces da lugar a contradicción: ¬A |- B y ¬A |- ¬B. |
|||
# 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 satisfacible; |
|||
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 premiss, 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== |
|||
* {{cite paper |
|||
|last=Gödel |first=K |authorlink=Kurt Gödel |
|||
|year=1929 |
|||
|title=Über die Vollständigkeit des Logikkalküls |
|||
|version=Doctoral dissertation |publisher=University Of Vienna. |
|||
}} Primera demostración del teorema de completitud. |
|||
* {{cita publicación |
|||
|apellido=Gödel |nombre=K |enlaceautor=Kurt Gödel |
|||
|título=Die Vollständigkeit der Axiome des logischen Funktionenkalküls |
|||
|idioma=German |
|||
|publicación=Monatshefte für Mathematik |
|||
|volumen=37 |páginas=349–360 |año=1930 |
|||
|doi=10.1007/BF01696781 |
|||
|id={{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. |
|||
[[Categoría:Teoremas]] |
|||
[[en:Original proof of Gödel's completeness theorem]] |
|||
Revisión del 00:59 1 abr 2010
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
- A es lógicamente verdadera: | A= A.
- Si A es lógicamente verdadera, entonces ¬A es insatisfacible.
- Si ¬A es insatisfacible, entonces ¬A es inconsistente.
- Si ¬A es inconsistente, entonces da lugar a contradicción: ¬A |- B y ¬A |- ¬B.
- 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 satisfacible;
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 premiss, 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
- Gödel, K (1929). Über die Vollständigkeit des Logikkalküls. Doctoral dissertation. University Of Vienna. Primera demostración del teorema de completitud.
- Gödel, K (1930). «Die Vollständigkeit der Axiome des logischen Funktionenkalküls». Monatshefte für Mathematik (en german) 37: 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.