Teorema de Gödel

El Teorema de Incompletitud de Gödel.

Situémonos en los comienzos de los años treinta. En el ambiente lógico matemático se trabaja febrilmente buscando llevar a feliz término un programa que se arrastra desde finales del siglo XIX, cuyas ideas se pueden rastrear en los escritos de lógicos medievales como Raimundo Lulio, en Leibniz, en todos quienes alguna vez soñaron con mecanizar el razonamiento, y cuyo principal impulsor es el famoso matemático David Hilbert. Este programa consiste en la formalización total del razonamiento matemático y su culminación sería la demostración de la consistencia de las matemáticas, es decir, la prueba formal de que las matemáticas no son un sistema contradictorio. O para usar la metáfora de Borges, el proyecto consiste en construir un catálogo fiel de las matemáticas y demostrar que no es contradictorio.

La insistencia en estos temas relativamente esotéricos tenía fuertes motivaciones prácticas. Por un lado los fundamentos del análisis matemático, especialmente el tratamiento del sospechoso concepto de número infinitesimal, hizo imperiosa la necesidad de contar con algún sistema formal que haga más evidente las posibles fallas en que se incurre al razonar. Por otro lado, a fines del siglo XIX se había descubierto varias paradojas en ciertos sistemas formales. Así, los fundamentos mismos de la ciencia “más segura”, la ciencia “exacta” por antonomasia, se veían temblorosos. Esa vergüenza no le convenía a nadie. El ilimitado optimismo, tantas veces ciego, de la comunidad científica, rápidamente encontró el remedio: demostrar formalmente que las matemáticas son consistentes. Uno ya pudiera husmear aquí cierta circularidad del intento: ¿no se está usando el mismo lente para examinar la calidad del lente?

Pero los triunfos parciales que se conseguían envalentonaban hasta a los más escépticos: el monumental tratado Principia Mathematica de Whitehead y Russell por un lado, y la emergente teoría de conjuntos por otro, despacharon casi de una plumada el primer problema a que aludíamos: ambos son sistemas formales en los cuales se puede expresar toda la matemática conocida. Solo quedaba entonces demostrar que esos sistemas eran consistentes. Las esperanzas crecían, pues se obtenían algunos resultados bastante interesantes en esa dirección. Entre los más importantes habría que señalar la demostración de la consistencia de la teoría de números, con un postulado de inducción algo más débil que el usual, que logró Ackermann en 1924-5 y Von Neumann en 1927, ambos discípulos de Hilbert.

Al llegar el año 1930 la tarea central era la demostración de la consistencia del análisis clásico, que puede ser visto como una extensión de la aritmética si le agregamos conjuntos de números y algunos axiomas que los gobiernen. Para los optimistas de siempre, el cumplimiento del programa formalista de Hilbert era cuestión de tiempo y paciencia. De hecho, el joven Kurt Gödel se propuso a mediados de 1930, asumiendo (grosso modo) la consistencia de la aritmética, intentar demostrar la consistencia del análisis clásico. Mientras  más trabajaba en el problema, más consciente se iba haciendo que el proyecto era imposible. Y así, por esas ironías del destino, quien estuvo más cerca de llevar a cabo el programa de Hilbert fue precisamente quien le dio el tiro de gracia. Así nacía el, sin duda, más famoso teorema de la lógica matemática.

El trabajo de Gödel titulado Uber formal unentscheidbare S¨atze der Prin- ¨ cipia Mathematica und verwandter Systeme (Sobre sentencias formalmente indecidibles de Principia Mathematica y Sistemas afines), de modestas 25 páginas, fue escrito el año 1930 y publicado en 1931 en la revista Monatshefte für Mathematik und Physik. Allí Gödel se propone como objetivo principal demostrar lo que hoy se conoce como el “teorema de incompletitud de Gödel”. Dejemos que él mismo nos explique, con las palabras introductorias de su artículo, en qué consiste:

Como es sabido, el progreso de la matemática hacia una exactitud cada vez mayor ha llevado a la formalización de amplias partes de ella, de tal modo que las deducciones pueden llevarse a cabo según unas pocas reglas mecánicas. Los sistemas formales más amplios construídos hasta ahora son el sistema de Principia Mathematica (PM) y la teoría de conjuntos de Zermelo-Fraenkel (desarrollada aún más por J. von Neumann).

Estos dos sistemas son tan amplios que todos los métodos usados hoy día en la matemática pueden ser formalizados en ellos, es decir, pueden ser reducidos a unos pocos axiomas y reglas de inferencia. Resulta por tanto natural la conjetura de que estos axiomas y reglas basten para decidir todas las cuestiones matemáticas que puedan ser formuladas en dichos sistemas. En lo que sigue se muestra que esto no es así, sino que por el contrario, en ambos sistemas hay problemas relativamente simples de la teoría de los números naturales que no pueden ser decididos con sus axiomas (y reglas).

Y a continuación esboza la idea de la demostración, que es lo que expondremos aquí con ligeras modificaciones para mejor entendimiento. Gödel trabaja en el sistema formal de los PM; nosotros trabajaremos en un sistema formal que llamaremos N, que el lector, para ganar intuición, puede pensarlo como una axiomatización de la aritmética de los números naturales. Supondremos entonces, que tenemos un sistema de axiomas y reglas de deducción que permiten deducir afirmaciones en N. La demostración consiste en encontrar una oración F del sistema N con la propiedad de que ella ni su negación, ¬F, son deducibles en N. Bosquejemos los pasos uno por uno.

1. El lenguaje de un sistema formal consta de ciertos signos primitivos (“veinticinco símbolos suficientes. . .”). Podemos mencionar variables, constantes lógicas como ¬, ∧, ∀, paréntesis y constantes no lógicas, que en nuestro caso basta con considerar + (adición) y 1 (uno).

2. Las fórmulas de un sistema formal son ciertas sucesiones finitas de esos signos, por ejemplo ∀x¬(x = 1 + 1) es una fórmula. También hay otras sucesiones de símbolos que no tienen significado alguno como por ejemplo ∨¬11+. No es difícil indicar un método por el cual reconocer unas y otras.

 Hay ciertas fórmulas especiales, las oraciones, de las cuales tiene sentido preguntar si son deducibles o no usando los axiomas y reglas de deducción que el sistema tenga.

3. Es posible codificar todas las fórmulas por medio de números naturales de tal forma que a cada fórmula F le corresponda un número natural diferente, el código de F, que denotaremos por [F].

4. Las fórmulas con una variable libre (informalmente, fórmulas a las que les falta un dato para ser oraciones, como “x es un número par”; si reemplazamos x por un número concreto, tenemos una oración, por ejemplo “5 es un número par”) jugarán un papel importante. Ordenemos en una lista todas estas fórmulas:

F1(x), F2(x), F3(x),. . .

Es importante observar que las fórmulas en el lenguaje de N con una variable libre codifican conjuntos de números. La idea es sencilla: la fórmula F(x) representará el conjunto de todos los números n para los cuales F(n) es deducible en el sistema N.

5. Entonces viene la parte más importante (y técnica) de la demostración, y que cubre casi todo el trabajo de las 25 páginas. Se demuestra que también todos los conceptos meta-matemáticos que ocuparemos, como “fórmula”, “ser deducible en N”, “sustitución de variable”, etc., se pueden codificar en el sistema formal N.

6. En particular, se demuestra que existe una fórmula, que llamaremos Dem(x), en el lenguaje de N, que codifica el conjunto de todas las oraciones que son deducibles en N. Es decir, Dem(x) tiene la propiedad de que si F es una oración en N, entonces la oración Dem([F]) es deducible en N si y sólo si F es deducible en N.

Vale la pena detenerse un momento a meditar sobre los atisbos de autoreferencia que comienzan a aparecer aquí: fórmulas “hablando” de fórmulas.

7. Definimos a continuación un conjunto de números, que denotaremos con la letra K, por la siguiente fórmula (donde el signo ¬ denota negación):

n ∈ K ⇐⇒ ¬Dem([Fn(n)])

Observemos que, usando la definición de Dem dada en (6), podemos concluir que n ∈ K si y sólo si la oración Fn(n) no es deducible en N.

8. Puesto que todos los conceptos que aparecen en la definición en (7) son formalizables en N, también lo es el conjunto K. Por lo tanto hay una fórmula de la lista en (4) que codifica el conjunto K, supongamos que es la q-ésima de la lista. Es decir tenemos entonces que n ∈ K si y sólo si Fq(n) es deducible en N.

9. Consideremos entonces la fórmula Fq(q)

Si suponemos que Fq(q) es deducible en N, entonces por (7), q no pertenece a  K.

Pero esto significa, por (8), que Fq(q) no es deducible en N.

Si por el contrario, suponemos que Fq(q) no es deducible en N, entonces, por (7), q ∈ K. Pero entonces, por (8), Fq(q) es deducible en N.

Es decir, es imposible que Fq(q) sea deducible en N (pues suponerlo lleva a una contradicción). También es imposible que ¬Fq(q) sea deducible en N, pues si suponemos que ¬Fq(q) es deducible, entonces como N es consistente, Fq(q) no es deducible, pero eso significa que Fq(q) es deducible, contradicción.

Es decir, demostramos:

Teorema 1 (Gödel, 1931) La oración Fq(q) es indecidible en N, es decir en N no se puede deducir Fq(q) ni su negación.

Gödel acota en este punto:

La analogía de esta argumentación con la antinomia de Richard salta a la vista; también está íntimamente relacionada con la paradoja del “mentiroso”, pues la oración indecidible Fq(q) dice que q pertenece a K, es decir según (7), que Fq(q) no es deducible. Así pues, tenemos ante nosotros una oración que afirma su propia indeducibilidad. Evidentemente el método de prueba que acabamos de exponer es aplicable a cualquier sistema formal que, en primer lugar, interpretado naturalmente, disponga de medios de expresión suficientes para definir los conceptos que aparecen en la argumentación anterior especialmente el concepto de “fórmula deducible” y en el cual, en segundo lugar, cada fórmula deducible sea verdadera en la interpretación natural.

Con este resultado Gödel echa por tierra el famoso “axioma de la solubilidad de todo problema matemático” que postulaba Hilbert (y en su corazoncito cada matemático). Pero las sorpresas no acaban aquí. De hecho, el resultado más importante desde el punto de vista de los fundamentos de los sistemas formales es la “sorprendente consecuencia” del resultado anterior, que Gödel agrega inmediatamente al final de su trabajo (con el ofrecimiento nunca cumplido de demostrarlo rigurosamente más adelante) y expresada en su teorema XI, que dice esencialmente que no es posible demostrar la consistencia de un sistema formal en su propio marco.

Teorema 2 (Gödel, 1931) Sea A un sistema consistente de axiomas que sea mínimamente expresivo. Entonces la consistencia de A no es demostrable en A.

Veamos como probar esto para el sistema N. Se demuestra que la oración “N es consistente” se puede codificar con una oración de N, llamémosla Cons. Consideremos entonces la fórmula Cons ⇒ Fq(q), que interpretada en N dice “si N es consistente, entonces Fq(q) es deducible en N”. No es difícil demostrar que esta fórmula es deducible en N. Supongamos entonces que N pueda demostrar su propia consistencia, es decir que Cons se puede deducir en N. Entonces por modus ponens, Fq(q) sería deducible en N, lo que sabemos, por el Teorema anterior, que es falso. Por lo tanto N no puede demostrar su propia consistencia.

Después de todo esto Gödel comenta:

La prueba entera del teorema XI [nuestro Teorema 2] puede trasladarse a la teoría axiomática de conjuntos M y a la matemática clásica axiomática A, y también aquí obtenemos el mismo resultado:  No hay prueba alguna de la consistencia de M (de A) que pueda ser formalizada en M (en A), suponiendo que M (A) sea consistente.

No es difícil imaginar el impacto que estos resultados provocaron en la época. Al extremo que el mismo Gödel intenta suavizarlos comentando al final de su trabajo: “Hagamos notar explícitamente que el teorema XI (y los resultados correspondientes sobre M y A) no se oponen al punto de vista formalista de Hilbert”, y en un par de líneas propone algunas ampliaciones del concepto de formalismo que habría que considerar para rescatar el programa formalista después de este serio revés. Nunca es triste la verdad, lo que no tiene el remedio: el golpe en el terreno de los fundamentos de las matemáticas fue brutal y remeció hasta sus cimientos las formas de entender los formalismos. Los ecos los seguimos escuchando hoy día.