INCOMPLETITUD DE GÖDELL

Es larga la historia de la consideración científica y filosófica de los imposibles físicos. La cosmovisión aristotélica prohibía que pudieran formarse u observarse infinitos físicos o vacíos físicos locales. Durante la Edad Media hubo físicos que idearon ingeniosos experimentos mentales para intentar imaginar cómo «engañar» a la naturaleza y permitir la aparición de un vacío instantáneo, y explicar después de qué manera se evitaba que ocurriera esa posibilidad mediante procesos naturales o, si eso fallaba, invocando a un Censor Cósmico que impidiera su aparición, aunque fuera de manera momentánea.

En la actualidad los especialistas en física de la gravitación que estudian los agujeros negros y la cosmología tratan de demostrar que la teoría de la relatividad general de Einstein no permite la aparición de infinitos físicos, salvo al principio y al final del universo, a no ser que se encuentren ocultos tras el horizonte de los agujeros negros, donde no pueden influir en el universo exterior.

La química vivió su propio debate alquímico sobre la posibilidad o imposibilidad de fabricar oro a partir de metales menos nobles, y dentro de la ingeniería perduró el gusto por buscar máquinas de movimiento perpetuo hasta que la interpretación sistemática de las consecuencias de las leyes de la termodinámica a lo largo del siglo XIX lo erradicó por completo. Ejemplos sutiles, como el del demonio de Maxwell, permanecieron sin solución hasta quedar exorcizados por la moderna termodinámica computacional en 1961.

Los matemáticos también se toparon de forma ocasional con la cuestión de la imposibilidad dentro del contexto de varios problemas fundamentales de aritmética, geometría y álgebra. Supuestamente, alrededor del 550 a. C. los pitagóricos se toparon por primera vez con la «irracionalidad» (que en su origen significaba tan solo «no fracción» o «no razón», en el sentido de no ratio, pero no implicaba «fuera de la razón», como cabría pensar hoy en día) de números como √2, que no podía expresarse como una fracción de dos enteros. Cuenta la leyenda que los pitagóricos consideraron tan escandalosa esta revelación que ahogaron a su descubridor, Hípaso de Metaponto, por los problemas que les causó. Esto da una ligera idea sobre el tipo de operaciones y cuestiones que no tienen respuesta a partir de una serie particular de reglas.

Durante el primer cuarto del siglo XIX, el joven matemático noruego Henrik Abel demostró que no hay manera de resolver de forma explícita una ecuación algebraica general de quinto grado (Ax5 + Bx4 + Cx3 + Dx2 + Ex + F = 0, con A, B…, F constantes arbitrarias) aplicando a sus coeficientes operaciones aritméticas ordinarias, como la suma, la resta, la multiplicación, la división y la extracción de raíces del grado adecuado (hasta la quinta en este caso)[6]. El premio equivalente al Nobel de matemáticas lleva hoy el nombre de este físico. A diferencia de las ecuaciones de segundo, tercer o cuarto grado, las de quinto grado no se pueden resolver con una fórmula exacta[7]. Tan solo unos años después, en 1837, se demostró con rigor de varias maneras que un ángulo de 60º no se puede dividir en tres partes iguales trazando tan solo rectas o arcos de circunferencia con escuadra y compás. Estos casos revelaron por primera vez a quienes los estudiaron del modo correcto algunos indicios de las limitaciones de determinados sistemas axiomáticos.

En 1899 David Hilbert, el matemático más brillante del momento, emprendió un plan sistemático para apoyar las matemáticas sobre un plano axiomático formal[8], un programa que expuso en su totalidad en el ensayo titulado «Sobre el infinito» de 1925[9]. Hilbert creía que sería posible determinar los axiomas en los que se fundamenta cada parte de las matemáticas (y, por tanto, todas ellas en su conjunto), demostrar la coherencia interna de esos axiomas y después evidenciar que el sistema resultante de enunciados y deducciones surgido de esos axiomas es completo y, al mismo tiempo, decidible. Más en concreto, un sistema es «coherente» cuando no se puede demostrar que un enunciado E y su negación, –E, son teoremas verdaderos (por ejemplo, demostrando que un número es al mismo tiempo par e impar).

Y es «completo» si para cada enunciado E que se pueda construir en el marco de su lenguaje se puede demostrar que es cierto, o bien el propio enunciado E, o bien su negación.

Por último, el sistema es «decidible» si se puede demostrar que es verdadero o falso cualquier enunciado E construible con ese lenguaje. Por tanto, si un sistema es decidible también tiene que ser completo. La visión formalista que tenía Hilbert de las matemáticas consistía en una densa red de deducciones que se desplegaba con impecables conexiones lógicas a partir de los axiomas fundamentales. De hecho, las matemáticas se definieron como el conjunto de todas esas deducciones. Hilbert se propuso completar esa formalización de las matemáticas con ayuda de otros colegas, y creyó que en última instancia sería posible ampliar su alcance para incluir ciencias que se fundamentan en las matemáticas aplicadas como, por ejemplo, la física[10]. Él partió de la geometría euclídea y logró apoyarla sobre una base axiomática rigurosa. Después, su plan imaginó el reforzamiento del sistema con la incorporación de axiomas adicionales que evidenciaran a cada paso el mantenimiento de la coherencia y la decidibilidad, hasta que el sistema acabara siendo lo bastante extenso como para abarcar toda la aritmética. El criterio esencial para acreditar estos sistemas era siempre el mismo: demostrar la coherencia.

Hilbert puso en marcha su plan con gran confianza y convencido de que solo era cuestión de tiempo que todas las matemáticas quedaran atrapadas dentro de su red formalista. Esta confianza se refleja en el epitafio de su tumba, que es una cita del discurso que pronunció ante la Sociedad Alemana de Naturalistas y Físicos el 8 de septiembre de 1930 con motivo de una conferencia sobre epistemología de las ciencias exactas:

Wir müssen wissen Wir werden wissen,

es decir, «Debemos saber. Sabremos». Este convencimiento incondicional se manifestó en otras declaraciones no matemáticas de Hilbert. Hablando sobre el proceso judicial de Galileo y su incapacidad para defender sus convicciones científicas, Hilbert subrayó que el científico pisano «no era estúpido […]. Solo un estúpido podría creer que la verdad científica necesita recurrir al martirio; este tal vez sea necesario para la religión, pero los resultados científicos se acaban demostrando a su debido tiempo[11]». Pero, mira por dónde, el joven Kurt Gödel puso el mundo patas arriba algo más tarde, apenas un día después del convencido discurso de Hilbert, durante una mesa redonda al margen de la conferencia de Königsberg. Gödel había completado uno de los primeros pasos del plan de Hilbert como parte de su tesis doctoral, en la que demostró la coherencia y completitud del primer orden lógico (aunque más tarde Alonzo Church y Alan Turing revelarían que no es decidible). En 1929 el matemático polaco Mojźesz Presburger demostró que la aritmética de Peano es coherente, decidible y completa si no se incluye la multiplicación. En su caso se habla de la aritmética de Presburger. En 1930 el noruego Thoralf Skolem demostró lo mismo sobre la aritmética de Peano, aunque dejando fuera la adición. Pero los siguientes pasos que acometió Gödel fueron los que le valieron la fama de ser el lógico más grande que ha existido desde Aristóteles. Lejos de expandir el plan de Hilbert para alcanzar su objetivo principal (una demostración de la completitud de la aritmética), Gödel demostró lo contrario: que cualquier sistema coherente lo bastante rico como para contener toda la aritmética tiene que ser incompleto e indecidible. o pilló a casi todo el mundo por sorpresa y, de hecho, acabó de un solo golpe con el plan de Hilbert (y también con el de Whitehead y Russell).

Gödel provocó reacciones optimistas y pesimistas. Las optimistas, como la de Freeman Dyson, consideran sus resultados como la garantía de la naturaleza interminable de la investigación humana. Contemplan la indagación científica como una parte tan esencial del espíritu humano que, si se completara, produciría un efecto desmotivador desastroso en nosotros. En cambio, las interpretaciones pesimistas, como la de John Lucas[12], consideran el resultado de Gödel como la confirmación de la imposibilidad de la mente humana para conocer todos los secretos de la naturaleza (tal vez incluso la mayoría de ellos).

Tabla. Resumen de los resultados obtenidos en relación con la coherencia, la completitud y la decidibilidad de los sistemas lógicos fundamentales.

Teoría ¿Es coherente? ¿Es completa? ¿Es decidible? Breve explicación

Lógica proposicional

Sí No Sí Es el conjunto de todas las fórmulas válidas, es decir, siempre verdaderas: se trata exactamente de aquellas fórmulas que pueden demostrarse mediante un cálculo deductivo adecuado. La adecuado. La decidibilidad está vinculada al problema P = NP.

Lógica de primer orden

Sí No No Es el conjunto de todos los enunciados válidos: los mismos que se demuestran mediante un cálculo deductivo adecuado. Su indecidibilidad la demostraron sobre todo Church y Turing.

Teoría elemental de los números reales con +, ×

Sí Sí Sí Se trata de los enunciados verdaderos de primer orden de los números reales: elemental significa justamente «formalizado en el primer orden». Fue Tarski quien demostró sus propiedades diversas.

Geometría euclídea elemental

Sí Sí Sí Elemental sigue significando «formalizado en el primer orden». Se hace referencia a la axiomatización de Tarski, quien demostró las diversas propiedades deduciéndolas a partir de las de los números reales.

Algunas geometrías no euclídeas elementales

Sí Sí Sí Se hace referencia, por ejemplo, a las geometrías hiperbólicas y elípticas tratadas por Schwabhäuser con técnicas análogas a las del punto anterior.

Aritmética elemental de Presburger

Sí Sí Sí Es la teoría de primer orden de los números naturales que solo incluye la adición, es decir, el conjunto de enunciados verdaderos en este universo.

Aritmética elemental de Skolem

Sí Sí Sí En este caso solo se contempla la multiplicación.

Aritmética elemental de Peano (PA)

Sí? No No Aparecen tanto la adición como la multiplicación.

La coherencia la demostró Gentzen dentro de un contexto lógico apropiado. Los otros dos resultados negativos guardan relación con los teoremas de incompletitud de Gödel. Estos mismos teoremas descartan que la coherencia se pueda demostrar tan solo sobre la base de la PA. Sin embargo, otros, como Stanley Jaki[13], contemplan esta barrera de incompletitud con optimismo, ya que demostraría que la mente humana no puede ser superada por una máquina calculadora. Otros usos, más bien informales, de los resultados de Gödel se revelan divertidos. Por ejemplo, si una religión es un sistema de pensamiento que contiene afirmaciones no demostrables que deben aceptarse por la fe, entonces las matemáticas no solo son una religión, sino que también es la única capaz de demostrar que es una religión.

Es interesante observar que ninguna de las demostraciones de «imposibilidad» previas, como la de Abel, dio lugar a estas consideraciones generales sobre la capacidad cognitiva última y definitiva de la especie humana. En el caso de Abel, por ejemplo, se descarta una fórmula general para resolver ecuaciones de grado fijo superior a 4, pero se consigue a partir de los coeficientes de la ecuación mediante operaciones elementales (es decir, suma, etc.) y por extracción de raíces. Pero si se permiten herramientas más poderosas, se puede encontrar una fórmula. El discurso de Gödel, sin embargo, es más radical. Gödel fue un hombre, cuando menos, singular. Tal como escribió el poeta John Dryden en 1861, «los grandes genios son sin duda aliados íntimos de la locura. Y finas son las particiones que separan sus fronteras».

Cuando se pregunta a algunos de los contemporáneos de Gödel del Instituto de Estudios Avanzados de Princeton si habían llegado a conocerlo, siempre han respondido: «nadie conocía a Gödel». Un físico famoso dijo que, cuando llegó a ese instituto siendo muy joven, estaba, como es natural, ansioso por hablar con Gödel sobre sus teoremas de incompletitud y otras cuestiones relacionadas con la mecánica cuántica. Lo llamó a través de la línea telefónica interna y lo sorprendió gratamente que lo pusieran directamente con él, sin la mediación de ninguna secretaria o asistente que lo parapetara. Gödel le ofreció un encuentro en su oficina. El joven físico se quedó entusiasmado con la idea, pero al llegar la hora convenida no encontró a nadie. Pensó que Gödel se habría retrasado por algún compromiso importante. Al día siguiente asistió al té de bienvenida que ofrecía el instituto a los recién llegados y vio a Gödel sentado solo en un rincón. Se acercó a él, se presentó y le explicó que había ido a su oficina a la hora acordada, pero que se figuraba que habría tenido que irse por algún asunto más importante. «Al contrario», respondió Gödel, «he aprendido que solo concertando una cita puedo estar seguro de que no me encontraré con nadie».

Es útil concretar las afirmaciones precisas que subyacen a la deducción de incompletitud de Gödel. El teorema de Gödel establece que si un sistema formal es

1. especificado de manera recursiva,

2. lo bastante grande para incluir la aritmética, 3. coherente, entonces se deduce, precisamente, que es incompleto.

La condición 1 significa que debe haber una relación clara y accesible de axiomas como, por ejemplo, en la aritmética de primer orden de Peano.

La condición 2 significa que el sistema formal consigue definir los números naturales junto con sus operaciones de suma y multiplicación (¡ambas!) y demostrar ciertos hechos elementales sobre ellos. Esto se da, de nuevo, con la aritmética de Peano de primer orden.

La estructura de la aritmética tiene un papel central en la demostración del teorema de Gödel. Gödel utilizó ciertas propiedades especiales de los números, como sus factorizaciones y, tal como reveló Gauss, el hecho de que cualquier número se pueda factorizar de una manera única como el producto de divisores primos (por ejemplo, 130 = 2 × 5 × 13), para establecer una correspondencia crucial entre enunciados matemáticos y enunciados sobre matemáticas. Estos últimos se denominan en ocasiones enunciados metamatemáticos.

Gödel llegó a su resultado asignando a cada afirmación lógica un número de código, es decir, un número natural que la representa. Para ello se basa en el teorema de la descomposición en factores primos. Primero, asigna un número de código a los distintos símbolos implicados: por ejemplo, 3 al símbolo cero (0), o 19 al símbolo de la relación de igualdad (=). En este punto, una fórmula viene codificada por el número que se obtiene tomando los diversos factores primos 2, 3, 5, 7… y elevándolos a los números que se han asignado a los símbolos de la fórmula, en el orden en que aparecen. Así, «0 = 0» está numerado como 23 × 319 × 53. De esta manera, las afirmaciones sobre los números se convierten en números de por sí, y permiten expresar como enunciados sobre los números naturales las afirmaciones que se refieren, sin embargo, a razonamientos sobre los números naturales. En un sistema dado E se puede formular, por tanto, como una proposición sobre los números, una afirmación que habla de sí misma y dice: «No soy demostrable mediante E». Lo que conlleva la consecuencia de que esa afirmación es demostrable si y solo si no lo es (otro recordatorio de la paradoja del mentiroso). ¡Un movimiento de jiujitsu matemático!

De modo que la aritmética de primer orden de Peano no es completa ni decidible.

Una vez más resulta instructivo ver que es posible no reunir esas condiciones. Si se elige una teoría coherente en cuanto a referencias a (y relaciones entre) tan solo los 10 primeros números naturales, es decir, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, y se suman y multiplican dentro de un sistema de módulo 10 (es decir, cada vez que se pasa de 9 se vuelve a empezar desde el 0, por ejemplo, 5 + 6, que es 11, se convierte de nuevo en 1), entonces esta «miniaritmética» es completa. Su universo es, de hecho, finito y escapa a la condición 2 del teorema de Gödel.

Un resultado mucho más sorprendente lo ofrece la teoría de primer orden de los números reales con sus respectivas operaciones de adición y multiplicación, que es un mundo aparentemente mucho más complicado que el de los números naturales. Sin embargo, esta teoría es completa y decidible, tal como constata un teorema de Alfred Tarski, demostrado en medio de la última guerra mundial. Dado que la geometría euclídea se expresa mediante los números reales y sus operaciones, se puede deducir que también es completa. Cabría objetar que no hay nada mágico y, por lo tanto, impredecible en la naturaleza euclídea, plana, de la geometría clásica. Pues bien, hasta las geometrías no euclídeas de las superficies curvas resultan ser completas. Pero el asunto no se zanja con un teorema abstracto de completitud y decidibilidad, como el que acabamos de enunciar para los números y la geometría reales. Cualquier procedimiento para diferenciar lo verdadero de lo falso, es decir, un algoritmo de decisión para la teoría de números reales de primer orden, puede requerir en la práctica un largo y tortuoso camino de verificación. En efecto, un teorema de 1974 de Fischer y Rabin sostiene que cualquier algoritmo para reconocer enunciados verdaderos para los números reales con adición y multiplicación (e incluso para números reales solo con adición) tarda en responder, en el peor de los casos, tiempos al menos exponenciales respecto de la longitud del enunciado que se ha de analizar y, por lo tanto y en definitiva, amenaza con esperas prohibitivas.

Peor aún es la aritmética aparentemente inofensiva de Presburger, la única que es completa y decidible incluyendo solo la adición. Sin embargo, cualquier algoritmo que decida sus enunciados requiere, en el peor de los casos, un tiempo doblemente exponencial respecto de la longitud del enunciado en cuestión. Por lo tanto, anuncia esperas muchísimo más prolongadas incluso que en el caso de los números reales. Así lo demostraron Fischer y Rabin. Como ya se ha dicho, muchas teorías físicas se basan en números reales o en números complejos, y existe una riqueza sorprendente de fenómenos que se pueden formalizar en el ámbito abstracto de estos conjuntos numéricos con sus operaciones. Todo esto infunde la esperanza de que estas teorías físicas puedan evitarse la vergüenza de la indecidibilidad. Tarski, con la ayuda de sus colaboradores, entre los que se encontraba su alumna Wanda Szmielew, señaló que muchos sistemas matemáticos utilizados en física, como la teoría de retículos, la geometría proyectiva y la teoría de los grupos abelianos (así llamada en honor a Abel), son decidibles. Otros, sin embargo, como la teoría de grupos no abelianos, no lo son].

Así termina un capítulo extraordinario de la historia del desarrollo de las matemáticas, que tiene ramificaciones en física, ciencias de la computación y el poder de la mente humana en relación con sistemas axiomáticos como los ordenadores.