Gödel y Turing (Parte 14)

(A la parte 13 - A la parte 15)

Las hipótesis de los Teoremas de Gödel

El Programa de Hilbert proponía axiomatizar de un modo finitista la Teoría de Números y luego probar, también de modo finitista, que la axiomatización elegida es consistente y completa. Antes de seguir adelante, aclaremos el significado de todas las palabras que acabamos de usar, para ello respondamos algunas preguntas.

1 - ¿Qué es la Teoría de Números?

En el contexto en que estamos, podemos decir que la Teoría de Números es el estudio de las propiedades de los números naturales que son expresables en términos de la suma y el producto. Esta teoría habla de números primos, números compuestos, números perfectos, propiedades de la divisibilidad, etc. La Conjetura de Goldbach, el Último Teorema de Fermat y la Conjetura de los Primos Gemelos son expresables en el contexto de la Teoría de Números.

2 - ¿Qué significa axiomatizar una teoría?

En el siglo III a.C., en su libro Elementos, Euclides axiomatizó la Geometría, o al menos una buena parte de los conocimientos geométricos de su tiempo. Para ello eligió cinco enunciados, que estableció como postulados o axiomas, y en base a los cuales resultaba posible deducir a modo de teoremas todos los demás enunciados verdaderos de la teoría.

En realidad, Euclides estableció otros axiomas además de los famosos cinco postulados, a estos otros axiomas los que llamó nociones comunes. Se trataba de reglas generales del pensamiento, reglas válidas en cualquier contexto y no solamente en la Geometría. Una de ellas, por ejemplo, enuncia que dos cosas iguales a una tercera son iguales entre sí.

Del mismo modo, cuando Hilbert habla de una axiomatización de la Teoría de Números n sólo pide elegir algunos de los enunciados de la teoría como axiomas, sino que también pide incluir también nociones comunes, que modernamente son llamadas enunciados universalmente válidos, enunciados válidos en cualquier contexto. Pero además de los axiomas debían indicarse “reglas de inferencia”. Es decir, las reglas que indican qué conclusiones es lícito extraer de determinadas premisas. Es posible, de hecho, utilizar una única regla de inferencia, la llamada regla del Modus Ponens, que dice que tomando como premisas la afirmación “Si P entonces Q” y la afirmación P entonces es válido deducir Q.

3 - ¿Qué significa que una axiomatización sea finitista?

Una vez que se ha establecida una axiomatización para una teoría podemos definir qué es una demostración.

Definición: Una demostración es una sucesión de afirmaciones tal que cada una de ellas es, o bien un axioma, o bien se deduce de afirmaciones anteriores por aplicación de las reglas de inferencia.

Esta definición responde a la idea intuitiva de lo que es una demostración, una concatenación de enunciados en los que cada uno de ellos es, o bien un axioma, o bien una consecuencia de hechos enunciados anteriormente en la demostración.

Decimos entonces que una axiomatización es finitista si existe un algoritmo que, dada una sucesión finita de enunciados, nos permite decidir si esa sucesión es una demostración o no. En otras palabras, pensando en el universo de las sucesiones finitas de enunciados, una axiomatización es finitista si el conjunto de todas las demostraciones es recursivo.

4 - ¿Es a priori concebible que una axiomatización sea finitista?

Si una axiomatización fuese finitista existiría entonces una Máquina de Turing tal que si escribimos en su cinta una sucesión de enunciados de la teoría así axiomatizada, la máquina nos dará como salida un # si la sucesión constituye una demostración y un ## en caso contrario. En otras palabras, esta máquina permitiría disipar cualquier conflicto que pudiera surgir en torno a la validez de un razonamiento referido a la teoría. Pero ¿no le estamos pediendo demasiado a una simple máquina de Turing?

Para comenzar, ¿cómo escribimos en la cinta la sucesión de enunciados? Para ello debemos establecer un lenguaje formal preciso que servirá para escribir todos los enunciados de la teoría. Deberá indicarse claramente qué símbolos se pueden usar y con qué reglas sintácticas se construirán los enunciados. Habrá símbolos para variables, para constantes, para operaciones, habrá también conectivos lógicos, paréntesis, etc. Será conveniente agregar un símbolo especial que marque la separación entre los distintos enunciados de una sucesión.

Una vez establecidos los símbolos, estos serán codificados de tal modo que una máquina de Turing pueda aceptarlos. El primer símbolo será codificado como #, el segundo como ##, etc.

Dada un enunciado sea parte de una sucesión, la máquina deberá ser capaz de determinar si se trata de un axioma o si el enunciado se deduce de enunciados anteriores por aplicación de las reglas de inferencia.

Supongamos que, como de hecho es posible hacer, tomamos al Modus Ponens como única regla de inferencia. Es claro que dada una sucesión de enunciados (codificados como antes dijimos), es posible determinar algorítmicamente si uno de ellos se deduce de los anteriores por aplicación de esta regla. Un enunciado Q (pensado meramente como una sucesión de símbolos de una cinta de una máquina de Turing), que forma parte de una sucesión, se obtiene por aplicación de la regla del Modus Ponens si antes, en la misma sucesión, aparecen un enunciado P y el enunciado “P -> Q”. Es claro que la verificación de esta condición puede hacerse algorítmicamente.

Por lo tanto, para que una axiomatización sea finitista sólo es necesario que exista un algoritmo que reconozca si un enunciado dado es o no un axioma. En particular, el conjunto de los axiomas que elijamos para la teoría debe ser recursivo. Esta condición se cumplirá casi inevitablemente ya que, como dijimos alguna vez, casi cualquier conjunto que imaginemos será, de hecho, recursivo.

¿Qué sucede con las nociones comunes (o enunciados universalmente válidos)? En 1929, en la que fue su tesis doctoral, Kurt Gödel demostró que es posible axiomatizar las nociones comunes. Es decir, existe un conjunto recursivo de enunciados universalmente válidos tal que cualquier otro enunciado de ese tipo puede deducirse de ellos por aplicaciones sucesivas del Modus Ponens. Sin embargo, para que esto sea posible, el lenguaje formal en el que se escriben los enunciados debe respetar dos restricciones, que son las siguientes:

a) Los cuantificadores, es decir los símbolos “para todo” y “existe”, sólo pueden aplicarse a variables que representen individuos de la teoría. Así por ejemplo, si se trata de la Teoría de Números, los cuantificadores sólo pueden aplicarse a variables que representen números. En particular, los cuantificadores no pueden referirse a enunciados ni a conjuntos de individuos.

b) Las operaciones, tanto lógicas como aritméticas o de cualquier otro tipo, sólo pueden aparecer aplicadas una cantidad finita y determinada de veces. Por ejemplo, es lícito decir y = x + x + ... + x + x (2.400 veces la x), pero no es lícito y = x + x + ... + x + x (n veces la x), donde n es número no determinado.

Los lenguajes que se ajustan a estas restricciones se llaman lenguajes de primer orden. Las teorías axiomáticas cuyos lenguajes son de primer orden se denominan, por supuesto, teorías de primer orden. Puesto que en estas teorías las nociones comunes son axiomatizables, entonces en toda teoría de primer orden es posible dar una axiomatización finitista ¿pero será una axiomatización completa? Dejemos esta cuestión para la próxima respuesta.

Puesto que sólo las teorías de primer orden pueden llegar a ser finitistas y dado que los Teoremas de Gödel se refieren a teorías finitistas, los Teoremas de Gödel sólo se aplican a teorías de primer orden. La axiomatización de Peano, que vimos algunas partes atrás, no es de primer orden y por ende, no es finitista. No es de primer orden porque incluye un axioma que no respeta las restricciones anteriores:

Ax.8: Si A es un conjunto tal que 1 es elemento de A y tal que para todo x vale que si x es elemento de A entonces Sig(x) también lo es, entonces A = N.

5 - ¿Qué significa que una axiomatización sea completa?

Una axiomatización para una teoría es completa si todo enunciado verdadero de la teoría es demostrable a partir de los axiomas. Uno podría preguntarse qué significa que un enunciado sea verdadero, para evitar esta cuestión suele decirse simplemente que una axiomatización es completa si para todo enunciado P, o bien P, o bien su negación es demostrable a partir de los axiomas.

6 - ¿Qué significa que una axiomatización sea consistente?

Una axiomatización es consistente si no es posible deducir de los axiomas ninguna falsedad. Otra forma de decirlo, es que no existe ningún enunciado P tal que tanto P como su negación sean ambos demostrables.

7 - ¿Qué dice el Primer Teorema de Gödel?

Consideremos la Teoría de Números, más exactamente la parte de la Teoría de Números que es expresable mediante un lenguaje de primer orden, a la que llamaremos Teoría Elemental de Números.

El Primer Teorema de Gödel dice que es imposible dar una axiomatización finitista de la Teoría Elemental de Números que sea al mismo tiempo consistente y completa.

El Segundo Teorema de Gödel dice que es imposible dar una demostración finitista de la consistencia de la Teoría Elemental de Números. (1)

Puesto que el Programa de Hilbert proponía dar una axiomatización finitista de la Teoría Elemental de Números y luego demostrar su consistencia y completitud de modo finitista, los Teoremas de Gödel demostraron, en definitiva, que el Programa de Hilbert era irrealizable.

8 - ¿Qué significa que una teoría contenga a la Teoría de Números?

Tomemos una teoría que hable de los números naturales. Un conjunto de números es definible en esa teoría si la propiedad que define al conjunto es expresable en el lenguje de la teoría. Por ejemplo, el conjunto de los números pares es definible en la Teoría Elemental de Números, ya que la propiedad “x es par” equivale a decir “existe algún y tal que x = y + y”, y esta última propiedad está expresada en el lenguaje de la Teoría Elemental de Números.

Decimos que un conjunto es aritmético si es definible en la Teoría Elemental de Números. Tal como dijimos alguna vez para los conjuntos recursivos, es casi seguro que cualquier conjunto numérico que los lectores puedan imaginar será aritmético. Existen, sin embargo, conjuntos que no lo son, aunque no daremos aquí ningún ejemplo.

Será de vital importancia para nosotros la siguiente propiedad:

Teorema: Todo conjunto recursivamente numerable es aritmético. (Aunque no vale la recíproca.)

Respondamos ahora la pregunta planteada: una teoría contiene a la Teoría Elemental de Números si permite definir todos los conjuntos aritméticos. A los efectos de los Teoremas de Gödel es suficiente en realidad que permita definir todos los conjuntos recursivamente numerables. El Primer Teorema de Gödel puede enunciarse diciendo que es imposible dar una axiomatización finitista, consistente y completa de cualquier teoría de primer orden que contenga a la Teoría Elemental de Números.

En la próxima parte veremos finalmente la demostración del Primer Teorema de Gödel.

Notas:

(1) Para dar una demostración finitista de la consistencia de la teoría de números habría que formular una teoría que se refiera a los enunciados de la Teoría de Números en la que sea posible expresar la consistencia de esta teoría. Habría que axiomatizar de modo finitista esta teoría y luego demostrar la consistencia de la Teoría de Números.

(A la parte 13 - A la parte 15)