En este 2006, que está a punto de acabar, como siempre ocurre en estos casos, con grandes fuegos artificiales y ensordecedoras tracas festivas, se cumplen cien años, no más, del nacimiento allá en Chequia del checo Kurt Gödel. Y sería, en mi humilde opinión, una notable falta de urbanidad por nuestra parte no dedicarle aquí a este señor algún otro post, aparte de los que ya le hemos dedicado no hace mucho NuezMoscada y yo mismo.

Gödel. Qué apellido notable, tronc@s. O sea, God = Dios, como casi todo el mundo sabe. Pero es que también El = Dios en hebreo. En una palabra: ¡Rediós! Kurt Rediós.

De niño es fama que al feo mocoso este le llamaban Herr Warum, o sea, “Señor Por Qué”. Lo cual, modestia aparte, me recuerda mi propio caso, pues yo, cuando era niño, también asaeteaba incansablemente a mi querido abuelito Avelino con mis inacabables porqués. “¿Por qué brilla la luna, abuelito?”, “¿Por qué es tan húmeda el agua, abuelito?”, “¿Por qué quema el fuego, abuelito?” A lo que el querido abuelito Avelino me respondía siempre con mucha paciencia, y cerrando filosóficamente los ojillos, con un imperturbable trino: “Ti…, ti…, ti.” (No conseguí salir de dudas en aquella época, esa es la verdad.)

Sería ridículo intentar negar o disimular que también estos detalles y estas pequeñas coincidencias biográficas contribuyen lo suyo a que la personalidad de este señor Rediós me resulte particularmente fascinante.

No voy a entrar ahora en el relato minucioso de cómo transcurrió la infancia, la adolescencia y la primera juventud de Gödel. Esas pijoterías, que suelen ser bastante enojosas, aburridas e incluso soporíferas (o al menos así lo creo yo), pueden encontrarse sin mayor dificultad en la Wikipedia o en el Goodel, digo en el Gúgol. Yo abordaré la cosa --como decimos, secundando a Horatius Flaccus, los versados en culta latiniparla-- in medias res. Es decir, en mitad de la vaca, es decir, de la res, o sea: en medio del asunto.

Hete aquí, pues, que el primer problema lógico importante que decidió abordar don Kurt en 1930 fue el enunciado por el bueno de David Hilbert dos años antes en el Congreso Internacional de Bolonia: el teorema de completud para la lógica de predicados.

Lo cual requiere una aclaración.

Tal como lo planteaba de antiguo Hilbert, el decisivo problema de la completud para la lógica consistía en establecer qué expresiones lógicas son, como diría Leibniz, verdaderas en todos los mundos posibles. En lo que respecta a la lógica proposicional, la cuestión fue resuelta positivamente en 1921 por el matemático Emil Leon Post. Y nueve años después, como digo, fue nuestro amigo Kurt Gödel quien se encargaría de probar la equivalente completud de la lógica predicativa.

(Aquí sería quizá preciso explicar la diferencia existente entre proposiciones o enunciados, por un lado, y predicados, por otro, a fin de que se entendiese bien en qué consisten las correspondientes lógicas. Pero, bueno, de momento lo dejo todo aquí, que se me enfría y se me pone perdida de moscas la sopa.)

Gödel, 2

Antes de proseguir exponiendo audazmente los trascendentales descubrimientos de este chico checo, Kurt Gödel, será conveniente hacer dos cosas:

A) Aclarar el significado de cuatro conceptos básicos de los lenguajes “bien hechos”, a saber: “cálculo formal”, “consistencia”, “completud” y “decidibilidad”, y

B) Hacer una breve alusión contextualizadora a los Principia de Russell/Whitehead.

A ello, pues.

Un cálculo formal es un sistema que consta de: 1. Un conjunto de símbolos elementales, 2. Un conjunto de reglas de formación para utilizar esos símbolos en formaciones compuestas, y 3. Un conjunto de reglas de transformación que indica cómo pasar de una a otra combinación de símbolos.

Se dice que un cálculo es consistente cuando resulta imposible demostrar en él una contradicción, o sea, un enunciado E y la negación de E.

Un cálculo es, además, completo cuando es posible demostrar en él como teoremas los enunciados formalmente verdaderos construibles con sus símbolos. O, dicho de otro modo: cuando, aplicado a los principios o axiomas de la teoría correspondiente, dicho cálculo produce como teoremas todas las verdades de esa teoría.

Un cálculo es, por último, decidible cuando siempre es posible establecer, mediante un número finito de pasos normados, si una determinada fórmula es o no es un teorema de dicho cálculo.

Diré por otro lado que el logicismo de Frege y Russell (del que he hablado ya en algún que otro post) significó el afán por encontrar y establecer unos fundamentos firmes, claros y seguros para la matemática. La idea básica de estos autores era que la aritmética es idéntica con alguna parte de la lógica. En consecuencia, las paradojas que aparecían en la fundamentación de la aritmética por la teoría de conjuntos tenían que ser, en última instancia, de naturaleza lógica. Se imponía, por tanto, la necesidad de una revisión de los fundamentos de la propia lógica. A tal fin estaba orientada la clásica y monumental obra en tres gruesos volúmenes que Russell y Whitehead publicaron en los años 1910-1913 con el newtoniano título de Principia Mathematica.

Pues bien: en 1931, firmado por un jovenzuelo de veinticinco años llamado Kurt Gödel, apareció en una publicación alemana un breve trabajo titulado Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, o sea, “Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas conexos”…

Gödel, 3

Así que, una vez demostrada, como vimos, la completud de la lógica (primero de la proposicional por Post, luego de la predicativa por Gödel), ¿qué cosa más natural cabía esperar de nuestro autor sino que fijase su poderosa atención en la matemática, e intentara extender a esta disciplina “lógica” aquellos felices resultados? Para lo cual, como ya he dicho y es fácil entender, en 1931 eligió los imponentes Principia de Russell y Whitehead.

Y cuál no sería su sorpresa cuando descubrió que había fórmulas verdaderas de la aritmética que no formaban parte de los teoremas de tal obra magna. Pero su sorpresa fue aún mayor al comprobar que ese problema era irremediable. Pues, ciertamente, era posible añadir a los Principia nuevos axiomas destinados a completar la obra, ¡pero ningún añadido habría podido nunca completarla del todo! De ahí el título del artículo de Gödel: “Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas conexos”, ya que en realidad el problema de incompletud afectaba, no sólo a los Principia de Russell y Whitehead, sino ¡a cualquier sistema matemático pasado, presente o futuro!

La idea básica de la demostración de Gödel era una variante de la clásica paradoja del mentiroso en la versión de Eubúlides: “Esta frase no es verdadera.” Si llamamos F a esa oración entrecomillada, ocurre que: si F es verdadera, entonces F no es verdadera; si F es falsa, entonces F no es falsa. ¡No hay manera de saber, o decidir, si F es verdadera o falsa! Nos hallamos inmersos en una situación angustiosa de indecibilidad.

En vez de verdad o falsedad, Gödel hablaba de demostrabilidad. Su sentencia era: “Esta fórmula no es demostrable.” En el caso de la paradoja de Eubúlides, y dado que la verdad es una sola (o lo sería en el caso de que existiera), la oración F es paradójica, sí, pero no ambigua. En el caso gödeliano de la demostración, sin embargo, hay muchas posibilidades: tantas como sistemas de axiomas y reglas. La oración de Gödel es, así pues, ambigua, y debe ser reformulada estableciendo su pertenencia a un sistema particular, por ejemplo el de los Principia. Con lo cual el enunciado quedaría así: “Esta fórmula no es demostrable en el sistema dado.”

Pues bien, así como Eubúlides se preguntaba si su frase era verdadera o falsa, y había descubierto que ninguna de esas alternativas era posible, Gödel se preguntó también si su fórmula era demostrable o refutable, ¡y descubrió análogamente que ninguna de ambas opciones era posible! ¡No había manera de decidir al respecto!

Pero proseguiremos otro día, que estas temáticas resultan un poco indigestas en grandes dosis.

Gödel, 4

Dado, pues, un sistema de axiomas y reglas, la fórmula G de Gödel afirma: “Esta fórmula no es demostrable”. Al igual que ocurre con la oración F de Eubúlides, se trata también ahora de una formula autorreferente, pero ésta no predica de sí misma la cualidad semántica de la verdad o la falsedad (como en el caso de Eubúlides) sino la cualidad sintáctica de la demostrabilidad o la indemostrabilidad. Si el sistema de referencia demuestra solo verdades, en el caso de que G fuera demostrable sería verdadera y, por tanto, no demostrable. Ahora bien, si no fuera demostrable, sería necesariamente verdadera, lo que significaría que en el sistema dado hay verdades indemostrables, exactamente igual que sucede en las distintas teologías.

Pero es que, además, la fórmula G no solo es indemostrable en el sistema: es también irrefutable, dado que ni siquiera su negación es demostrable. Si fuese falsa, habría que negar su significado y decir que es demostrable, lo cual estaría en contradicción con la hipótesis de consistencia, según la cual las proposiciones falsas no son demostrables en un sistema consistente. Nos encontramos, por tanto, con que existen fórmulas que no son demostrables ni refutables, es decir, con ejemplos de afirmaciones destinadas a permanecer eternamente indecidibles. Queda así demostrada la incompletud del correspondiente sistema de axiomas y reglas.

El razonamiento de este llamado teorema de Gödel estaba, como es lógico, basado en una rigurosa formalización en la que aparecían expresiones que decían de sí mismas que no eran demostrables en el sistema dado. (Lo que por cierto, y de paso, suponía una refutación de la tesis de Ludwig Witgenstein, en su Tractatus, según la cual un lenguaje no puede hablar de su propia forma lógica, o sea, de su estructura sintáctica.) Puesto a reducir la sintaxis del sistema a la aritmética, Gödel procedió de una manera análoga a lo que había intentado Leibniz. Para soslayar los problemas con los que se había topado y no había sabido resolver el matemático alemán, Gödel tuvo en cuenta el teorema fundamental de la aritmética, según el cual la descomposición en factores primos de cualquier número es única.

Pero de este asunto, la llamada “gödelización”, hablaré en el próximo post.

Gödel, 5

La gödelización de un lenguaje L es una función G: L --->N que asigna números naturales, llamados de Gödel, a conjuntos o hileras de signos.

Sea, por ejemplo, el alfabeto parcial, tomado de los célebres Principia, {p, q, ~, v, ¬}, a cuyos elementos se les asignan respectivamente los números sucesivos 1, 2, 3, 4, 5.

Dada entonces, por ejemplo, la fórmula p v q (donde 'v' es la disyuntiva 'o'), se marcan esos símbolos con números primos correlativos a partir del 2. Tendríamos, por tanto, en este caso: 2 para p, 3 para v, 5 para q. A cada uno de esos números se le aplica un exponente, que es el que corresponde al número de Gödel de la lista citada antes: p es 1, v es 4, q es 2. Por lo tanto, el número de Gödel de nuestra fórmula p v q sería 2*(3^4)*(5^2) = 2*81*25 = 4050.

Obsérvese que, procediendo a la inversa, si nos encontrásemos con el número 4050, su descomposición única en factores primos nos produciría 2*(3^4)*(5^2), que se lee unívocamente “p v q”.

Otro ejemplo: si nos topásemos casualmente con el número de Gödel 24, dado que 24 = (2^3)*3, sabríamos con seguridad y de manera inequívoca que se trata de la fórmula “~ p”.

En el caso de una demostración, que no es más que una sucesión de fórmulas, lo que se hace es hallar el número de Gödel de cada una de las fórmulas, y numerar luego éstas del mismo modo que hacíamos con los símbolos elementales. Para una supuesta demostración con solo dos fórmulas, verbi gratia:

L1 p
L2 p v q,

el correspondiente número de Gödel sería, por tanto, 2*(3^4050). (Al ver una expresión así, sabremos sin duda de inmediato que se trata de una demostración y no de una fórmula, ya que ese número tan gordo, 4050, no se corresponde ni puede corresponderse con ningún símbolo elemental, sino con una fórmula.)

Aclarado, supongo, este asuntillo técnico, en el próximo post volveré a utilizar, Dios mediante, solo prosa molieresca, que quizá resulte algo más digerible.

Gödel, y 6