(A la parte 14 - A la parte 16)
La demostración del Primer Teorema de Gödel
Supongamos que hemos dado una axiomatización finitista y consistente de la Teoría de Números, tenemos que demostrar que no puede ser completa, es decir, que existe una afirmación verdadera que no se puede demostrar a partir de los axiomas.
Recordemos que en la parte anterior hablábamos de conjuntos aritméticos. Un conjunto (que siempre supondremos formado por números enteros positivos) es aritmético si la propiedad que lo define puede expresarse en el lenguaje de primer orden de la Teoría de Números, es decir puede expresarse formalmente usando la suma, el producto y los conectivos y cuantificadores lógicos, respetando las restricciones que mencionábamos en la parte anterior.
Por ejemplo, el conjunto de los números pares es aritmético, pues la propiedad “x es par” puede expresarse en el lenguaje de primer orden de la Teoría de Números, ya que “x es par” equivale a “existe algún y tal que x = y + y”. La propiedad “x es primo” también es aritmética, ya que equivale a que “no existen números y, z tales que x = (y + 1)(z + 1)”.
Las expresiones “x es par” o “x es primo” son lo que Bertrand Russell llamaría funciones proposicionales, es decir, afirmaciones genéricas en las que aparece una variable x y en la que cada vez que x es reemplazada por un número concreto se obtiene una afirmación (o un enunciado) que, según el valor elegido, será verdadera o falsa. Si la función proposicional define un conjunto entonces es verdadera exactamente para todos los números que forman parte de ese conjunto.
Indicaremos a las funciones proposicionales como P(x) o Q(x). Así si P(x) es “x es primo” entonces P(2) es verdadera, pues 2 es primo, mientras que P(4) es falsa, pues 4 no es primo.
Supongamos que P(x) es una función proposicional que define un cierto conjunto A. Es bastante claro que la negación de P(x) definirá el complemento de A. Y dado que la negación es una operación lógica perfectamente legítima en un lenguaje de primer orden (y que puede ser usada sin restricciones especiales) entonces podemos deducir que si A es un conjunto aritmético entonces su complemento también lo es. Por ejemplo, así como “existe algún y tal que x = y + y” define al conjunto de los números pares, entonces “no existe algún y tal que x = y + y” define al de los impares.
Por otra parte, decíamos en la parte anterior que todo conjunto recursivamente numerable es aritmético, aunque la demostración de este hecho excede estas notas.
Comencemos ahora la demostración del Teorema de Gödel, en la que usaremos todos los conceptos estudiados en las partes previas.
Sea A un conjunto recursivamente numerable que no es recursivo y sea B su complemento. El conjunto A es, entonces, aritmético y por lo tanto B también es aritmético. Por otra parte, como A es recursivamente numerable pero no es recursivo, entonces B no es ni siquiera recursivamente numerable.
Por lo tanto B es aritmético, pero no es recursivamente numerable.
Ahora bien, como B es aritmético, la propiedad que lo define puede expresarse mediante alguna función proposicional P(x) expresable en el lenguaje de la Teoría de Números. Para cada n, P(n) es una afirmación de la Teoría de Números que es verdadera si n está en B y es falsa en caso contrario.
Por lo tanto B = {n : P(n) es verdadera}.
Recordemos que hemos supuesto que está dada una axiomatización finitista y consistente de la Teoría de Números. A los efectos de lo que sigue, la palabra “demostrable” significará “demostrable a partir de esos axiomas”.
Sea C entonces el conjunto C = {n : P(n) es demostrable}.
Está claro que C está contenido en B, ya que si P(n) es demostrable entonces debe ser verdadera (la consistencia de los axiomas garantiza que no se puede demostrar una falsedad). Veamos que C es recursivamente numerable.
Que la axiomatización sea finitista significa que existe un algoritmo que, dada una sucesión de enunciados, decide si esa sucesión constituye una demostración, o no. Ordenemos lexicográficamente todas las sucesiones posibles de enunciados y programemos nuestra Computadora Permanente de tal modo que las vaya recorriendo una por una y decidiendo si son o no demostraciones. Cuando la sucesión sea una demostración, la computadora debe fijarse si la conclusión de la misma es un enunciado de la forma P(n), para algún n. Si así fuera, debe imprimir el número n, en caso contrario pasa a la siguiente sucesión sin imprimir nada. Es claro que la Computadora Permanente irá así imprimiendo uno por uno los elementos de C. Por lo tanto C es, tal como dijimos, recursivamente numerable.
Recapitulando: C es recursivamente numerable, pero B no lo es, por lo tanto C y B no son el mismo conjunto. Pero C está contenido en B. Luego existe algún m que está en B, pero no está en C. Viendo las definiciones de estos conjuntos, concluimos que existe algún m tal que P(m) es una afirmación verdadera, pero que no es demostrable a partir de los axiomas. De este modo hemos probado el Primer Teorema de Gödel. Q.E.D.
La demostración del Segundo Teorema (la imposibilidad de demostrar de modo finitista la consistencia de la Teoría de Números) excede estas notas.
En la parte 16, y última, hablaremos un poco sobre las consecuencias del Primer Teorema de Gödel.
(A la parte 14 - A la parte 16)
No hay comentarios.:
Publicar un comentario