Teorema de incompletez de Gödel



Al ampliar ligeramente el lenguaje de la lógica de primer orden con el fin de incluir el esquema de inducción matemática en la aritmética, Gödel pudo demostrar, en su teorema de incompletez, que existen oraciones aritméticas que no es posible demostrar. La demostración del teorema de Gödel rebasa el alcance de este libro, para lo cual se necesitaría de por lo menos treinta páginas; sin embargo, podemos dar aquí una primicia de él. Empezaremos por la teoría lógica de los números. En esta teoría existe una sola constante, 0, y una sola función, S (la función sucesor). En el modelo propuesto, S(0) denota 1, S(S(0)) denota 2, etc.

El lenguaje, por lo tanto, tiene tiene nombres para todos los números naturales. El vocabulario incluye también los signos de las funciones +, X y Expt (potenciación), así como el conjunto habitual de conectores y cuantificadores lógicos. El primer paso consiste en notar que el conjunto de oraciones que podemos escribir en este lenguaje puede enumerarse.

(Imagine que define un orden alfabético de los signos y luego procede a ordenar alfabéticamente cada conjunto de oraciones de extensión 1, 2, etc.) Podemos luego enumerar cada oración a mediante un número natural #a (el número de Gödel).

Lo anterior es determinante: en la teoría de los números hay un nombre para cada una de las oraciones. De la misma manera, podemos enumerar cada demostración posible P mediante un número de Gödel G(P), puesto que la demostración no es sino una secuencia finita de oraciones.

Supongamos ahora que tenemos un conjunto A de oraciones que son aseveraciones verdaderas acerca de los números naturales. Si recordamos que A se puede nombrar utilizando cualquier conjunto de números enteros, podemos suponer que en nuestro lenguaje escribimos una oración a(j, A) del siguiente tipo:

Para todo i   i no es el número de Gödel de una demostración de la oración cuyo número de Gödel sea j, en donde la demostración utiliza sólo las premisas de A.

Sea ahora s la oración (#s, A), es decir, una oración que afirma su propia indemostrabilidad a partir de A. (La permanebte existencia de esta oración es verdad, aunque no totalmente obvio).

Procedemos ahora a razonar de la siguiente manera. Supóngase que s se puede demostrar a partir de A; entonces s es falso (porque s afirma que no se puede demostrar): Pero entonces tendríamos una oración falsa que es probable a partir de A, por lo que A no puede estar formada sólo de oraciones verdaderas: sería una violación a nuestra premisa. Por lo tanto s no se puede demostrar a partir de A. Pero esto es justo lo que afirma s; por lo tanto s es una oración verdadera.

Es decir, hemos demostrado (ahorrándonos 29 y media páginas) que para cualquier conjunto de oraciones verdaderas de la teoría de los números, y para cualquier conjunto particular de axiomas básicos, existen otras oraciones verdaderas que no es posible demostrar a partir de estos axiomas. Lo anterior establece, entre otras cosas que nunca será posible demostrar todos los teoremas de las matemáticas dentro de cualquier sistema de axiomas.

Es evidente que el anterior fue un descubrimiento de gran importancia para las matemáticas. Susu repercusiones en IA han sido objeto de amplio debate, empezando por las especulaciones realizadas por Gödel mismo.

STUART RUSSELL, PETER NORVIG, "Inteligencia artificial. Un enfoque moderno"
Prentice Hall Hispanoamericana, S.A, méxico, 1996