Kurt Gödel II: el teorema de completitud de la lógica de primer orden
La obra y las aportaciones de Kurt Gödel destacan por el hecho de haber supuesto hitos sin precedentes en los campos de la lógica y la matemática, además de ser ricos en consecuencias filosóficas. No obstante, como veremos en posteriores artículos, Gödel también escribió obras estrictamente filosóficas. En cualquier caso, comenzaremos aquí con una de sus primeras aportaciones, el teorema de completitud de la lógica de primer orden, la cual transformó la lógica moderna hasta límites insospechados.
Kurt Gödel con su amigo Albert Einstein
Lógica, matemática y filosofía a principios del siglo XX: el proyecto logicista
Con toda seguridad, uno de los capítulos más apasionantes, frenéticos y ricos en consecuencias para la matemática, la lógica y la filosofía contemporáneas se produjo entre finales del siglo XIX y el primer tercio del siglo XX. Entre sus protagonistas destacan nombres de matemáticos y filósofos como los de Gottlob Frege, Georg Cantor, Richard Dedekin, Bertrand Russell, Alfred N. Whitehead, Gerhard Gentzen, David Hilbert, Alonzo Church, Alan Turing y Kurt Gödel.
Como sabemos por anteriores artículos, desde el siglo XVII se venía amasando la idea de crear un sistema formal a partir del cual fueran deducibles todas las verdades de la matemática. Leibniz fue su principal promotor en aquella época (aunque la idea fue avanzada por el mallorquín Raimundo Lulio en el siglo XIII). No obstante, fue Frege, en el último cuarto del siglo XIX, quien dio el primer gran paso al respecto, creando el primer sistema lógico totalmente formalizado, su conceptografía o lenguaje de fórmulas para la transmisión del contenido conceptual, que mostraba con rigor lógico las relaciones inferenciales entre las proposiciones.
La idea era ofrecer una justificación lógica de la inferencia matemática, la cual sería una base sólida para esta ciencia y, en la medida en que el resto de ciencias buscan su justificación en la matemática, también suponía unos fundamentos lógicos para estas. Frege, tras su lenguaje de fórmulas, dio el siguiente paso de su programa: utilizar este pare expresar lógicamente las inferencias de la aritmética. Pero fracasó. Bertrand Russell encontró en la obra de Frege la paradoja que bautizó con su nombre: la Paradoja de Russell.
El hallazgo de Russell fue el equivalente a lanzar una bomba nuclear contra el edificio de la ciencia, especialmente de la matemática, la base de todas las ciencias. Como sabemos, la famosa paradoja se encontraba en el ambicioso principio de abstracción, el cual fundamentaba la teoría de conjuntos, base de la matemática moderna y desarrollada por Frege, Cantor y Dedekind. El descubrimiento de Russell en la obra de Frege destruyó la teoría clásica de conjuntos, teoría lo suficientemente atrevida y ambiciosa como para «demostrar» matemáticamente que el universo era un conjunto, lo cual hoy sabemos que es falso.
Pero los matemáticos rápidamente se pusieron a trabajar para reconstruir los destrozos que el descubrimiento de Russell había ocasionado. El propio Russell, junto a su colega Alfred N. Whitehead, estaba trabajando de forma independiente en el mismo proyecto de Frege. Así que tras su descubrimiento formuló la teoría de los tipos, lo que le permitió una ilusoria, como veremos en el siguiente post, solución a la Paradoja de Russell. Principia Mathematica se publicó entre 1910 y 1913, a volumen por año. En esta obra, Russell y Whitehead pensaron que habían reducido casi toda la matemática a un sistema lógico formado por una serie de axiomas y un par de conectivas. Pensaban que habían probado la tesis logicista.
El programa formalista de Hilbert
En 1900 David Hilbert presenta una lista de 23 problemas no resueltos que, desde su punto de vista, representaban el mayor reto para la matemática del siglo XX. Esta serie de problemas fue conocida como «Programa de Hilbert» y fue presentada en el Segundo Congreso Internacional de Matemáticas que se celebró ese año en París. Entre estos problemas había dos de especial importancia para las cuestiones que estamos tratando: por un lado, la formalización de la inferencia matemática. Esto se estaba consiguiendo gracias, por una parte, a Principia Mathematica de Russell y Whitehead, y, por otra, a la nueva teoría de conjuntos, desarrollada por Ernst Zermelo y Adolf Fraenkel, conocida como teoría de conjuntos Zermelo-Fraenkel.
El segundo de los problemas planteados por Hilbert fue la demostración de que la matemática era consistente. Es evidente que este se volvió bastante más acuciante cuando Russell descubrió la paradoja que lleva su nombre en la obra de Frege.
De estos dos problemas será de los que se ocupará Kurt Gödel. Por un lado, respecto de los sistemas lógicos del estilo al desarrollado en Principia por Russell y Whitehead, demosatrará que son completos; por otro, por lo que respecta a la consistencia de la matemática, demostrará que esta es inconsistente. A continuación veremos lo primero, dejando el tema de la incompletitud de la matemática para el próximo artículo dedicado a Gödel.
El teorema de completitud de la lógica de primer orden
Según el teorema de completitud de Gödel, «para toda fórmula A de la lógica cuantificacional de primer orden, si A es lógicamente verdadera, entonces A es deducible». Se llama teorema de completitud, porque todas las verdades lógicas expresables mediante el sistema son demostrables dentro del mismo sistema. Es un sistema completo. Gödel, además de formular un teorema tan elegante, demostró que era verdadero. Pero antes de ver su demostración, explicaremos el contenido mismo del teorema.
Veamos, vamos a hacer memoria y a acordarnos de algunos de los post dedicados al curso de lógica. Allí decíamos que lo que a los lógicos les interesa es la forma de los argumentos válidos, esto es, de aquellos cuya conclusión se sigue lógicamente de sus premisas: en realidad, está contenida en ellas. Y observábamos allí que esta relación de validez entre conclusión y premisas tenía, en realidad, un carácter sintáctico. Esto es, dada la forma de un argumento válido, este será válido para cualquier interpretación de sus símbolos no lógicos.
Recordemos además los post dedicados al cálculo deductivo. En este se exhibían los pasos que nos llevan desde un conjunto de premisas a una conclusión. Son series finitas de pasos, en los que se ve cómo aplicando determinadas reglas de introducción y eliminación de conectivas (los signos constantes en los argumentos, el vocabulario lógico) podemos derivar fórmulas bien formadas a partir de otras fórmulas previas. Bien, pues para una fórmula dada, que esta es demostrable quiere decir que es posible elaborar una deducción más o menos de este tipo. Dicho esto, pasemos a la demostración del teorema elaborada por Gödel, por lo demás bastante ingeniosa.
Formalmente, el teorema de Gödel es así: ╞ A → ├ A. El símbolo «╞» delante de una fórmula, significa que esta es una verdad lógica; el signo «├» delante de una fórmula, significa que esta es deducible y si está entre dos fórmulas, por ejemplo A ├ B, se lee «B se deduce de A». Pues bien, para demostrar su teorema Gödel supone
(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