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.
