Page 171 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En 1910, Russell publicó el primero de los tres volúmenes de la obra Principia Mathematica, un in-
tento de tratar el problema surgido de su propia paradoja. Cuando Hilbert se retiró en 1930, estaba
seguro de que las matemáticas estaban bien encaminadas hacia su recuperación. Al parecer, su
sueño de una lógica coherente y lo bastante sólida como para responder a cualquier pregunta se
hallaba en vías de tornarse en realidad.

gödel y sus dos teoremas de la incompletitud

Pero ocurrió que en 1931 un matemático desconocido de veinticinco años hizo público un artículo
que destruiría para siempre las esperanzas de Hilbert. Kurt Gödel iba a forzar a los matemáticos a
aceptar que las matemáticas nunca llegarían a alcanzar una lógica perfecta, y sus trabajos llevaban
implícita la idea de que problemas como el último teorema de Fermat pudieran ser imposibles de
resolver.

Gödel había demostrado que el intento de crear un sistema matemático completo y coherente era
un imposible. Sus ideas se pueden recoger en dos proposiciones:

• Primer teorema de indecidibilidad: Si el conjunto de axiomas de una teoría es
coherente, existen teoremas que no se pueden ni probar ni refutar.

• Segundo teorema de indecibilidad: No existe ningún proceso constructivo ca-
paz de demostrar que una teoría axiomática es coherente.

El primer enunciado de Gödel dice básicamente que, con independencia de la serie de axiomas
que se vaya a utilizar, habrá cuestiones que las matemáticas no puedan resolver; la completitud no
podrá alcanzarse jamás.
Peor aún, el segundo enunciado dice que los matemáticos jamás podrán estar seguros de que los
axiomas elegidos no los conducirán a ninguna contradicción; la coherencia no podrá demostrarse
jamás.

Gödel probó que el programa de Hilbert era una tarea imposible. A pesar de que el segundo enun-
ciado de Gödel decía que era imposible demostrar que los axiomas fueran coherentes, eso no im-
plicaba que fueran incoherentes. Muchos años después, el gran teórico de números André Weil dijo:

Dios existe porque las matemáticas son coherentes y el diablo existe porque no
podemos demostrarlo.

165