jueves, 10 de marzo de 2011

La autorreferencia en la demostración de Gödel (Parte 9 y última)

(A la parte 8)

Todo enunciado aritmético verdadero es demostrable

La intención principal de esta serie de entradas fue despejar algunas "preguntas frecuentes" relativas a los teoremas de Gödel. Por ejemplo: ¿Cómo es posible que un sistema axiomático sea consistente con la afirmación que dice que ese sistema no es consistente? ¿Puede ser demostrable un enunciado falso? Etc.

Como vimos, en los teoremas de Gödel hay tres niveles de análisis del lenguaje. Por un lado está el nivel sintáctico, en el que los símbolos del lenguaje se manipulan sin tomar en cuenta su posible significado (en este nivel se enuncian y demuestran los teoremas de Gödel).

Tenemos después el nivel semántico, en el que los enunciados se entienden como referidos a un cierto universo del discurso. Este universo puede ser el de los números naturales u otro universo más amplio. Este es el nivel en el que los matemáticos se mueven en su trabajo diario y es, en general, el nivel en el que nos sentimos más cómodos.

En el tercer nivel (que en el capítulo anterior di en llamar supra-aritmético), gracias a una codificación arbitrariamente definida, algunos enunciados pueden entenderse como referidos a propiedades metamatemáticas de sí mismos o de otros enunciados. Es sólo en este tercer nivel de análisis donde aparece la autorreferencia o la referencia a la consistencia de un sistema de axiomas.

La mayoría de las confusiones relativas a los teoremas de Gödel nacen de mezclar indebidamente conceptos pertenecientes a niveles diferentes. En efecto es un error mezclarlos porque, por ejemplo, tal como vimos en el capítulo anterior, hay enunciados que son equivalentes en un nivel, pero no equivalentes en otro nivel diferente.

Como dije en un capítulo anterior, la autorreferencia no es esencial para la demostración de los teoremas de Gödel. La interpretación de un enunciado como diciendo "Yo no soy demostrable" solamente ayuda a hacer más aceptable, o más creíble, la prueba de Gödel, pero no forma parte esencial de ella. ¿Por qué se hace tanto hincapié en la autorreferencia, entonces? Porque los matemáticos, créase o no, no son frías máquinas de calcular, sino seres humanos, y las demostraciones (especialmente aquellas que el matemático A hace para que el matemático B se convenza de que lo que está diciendo es cierto) no sólo deben ser correctas, sino también convincentes.

No quiero terminar esta serie de entradas sin antes referirme a otro error frecuente en relación al Primer Teorema de Gödel. Este error aparece, por ejemplo, en la novela El Tío Petros y la Conjetura de Goldbach. El Tío Petros, el protagonista de la novela, es un matemático bastante talentoso que, a una edad relativamente temprana, se obsesiona con la idea de demostrar la Conjetura de Goldbach.

Unos años después de iniciar su empresa, Petros se entera de la noticia de la demostración de Gödel y se plantea la duda de si la Conjetura de Goldbach no será una afirmación indecidible. Petros cree tener el talento suficiente como para encontrar una demostración de la Conjetura, si es que esta demostración existe. Pero ante la posibilidad de que tal vez la Conjetura sea verdadera, pero indemostrable, decide abandonar el intento de probarla y, de hecho, abandona toda investigación matemática.

Ahora bien, en los capítulos anteriores hemos hablado siempre de "demostrable con respecto a cierto sistema de axiomas" o "indecidible con respecto a tal sistema de axiomas". Pero ¿existen afirmaciones indecidible en sentido absoluto? ¿Hay verdades indemostrables? ¿Por qué digo "sistema de axiomas" y no "conjunto de axiomas?

Respondo primero a la segunda pregunta. Cuando hablamos de demostraciones, consistencia, etc. no sólo debemos tener en cuenta a los axiomas de la teoría en cuestión, sino que también debemos tener en cuenta la lógica subyacente y las reglas de inferencia. Hablo de "sistema de axiomas" como equivalente a "conjunto de axiomas + lógica subyacente + reglas de inferencia".

La lógica subyacente está formada los enunciados del lenguaje que son "universalmente válidos". Es decir, enunciados que son verdaderos cualquiera sea la interpretación que se dé a los símbolos del lenguaje. Nótese que esta definición es semántica. Un ejemplo es "P o no-P", donde P es un enunciado cualquiera. Se habla de "lógica subyacente" porque estos enunciados pueden formar parte (y, de hecho, forman parte) de cualquier razonamiento.

Si el lenguaje respeta las restricciones que comentamos en un capítulo anterior, entonces es posible dar un sistema recursivo de axiomas que permita deducir todos los enunciados universalmente válidos expresables en ese lenguaje. Este hecho, que fue probado por Gödel en 1929 (sus teoremas de incompletitud son de 1931), nos habilita a dar una definición sintáctica de la noción de "enunciado universalmente válido": son todos aquellos que se deducen, modus ponens mediante, del sistema de axiomas que Gödel dio en 1929 (o de cualquier otro equivalente a él).

Los lenguajes que respetan las restricciones antes indicadas se llaman lenguajes de primer orden. Se dice, entonces, que la lógica de primer orden es formalizable o que es recursivamente axiomatizable. Como la lógica de primer orden es recursivamente axiomatizable entonces existen chances de que una teoría expresada en un lenguaje así pueda cumplir las condiciones del Programa de HIlbert (la Aritmética no las cumple, eso probó Gödel, pero otras teorías sí pueden cumplirlas).

Aumentemos ahora la potencia del lenguaje mediante el artilugio de agregarle variables que se refieran a enunciados o a fórmulas (una fórmula es una expresión en la que hay "variables libres", que pueden ser reemplazadas por números cualesquiera, como por ejemplo "x es par").

Tenemos ahora un lenguaje de segundo orden, o de orden superior. En este tipo de lenguaje podemos decir, por ejemplo (en un lenguaje de primer orden no se puede expresar el enunciado que sigue):

"a = b si y sólo si para toda fórmula P(x), P(a) es equivalente a P(b)"

En los lenguajes de segundo orden tenemos también el concepto de "enunciados universalmente válidos" (y que constituyen la "lógica subyacente" de las teorías expresadas en esos lenguajes). Sin embargo, se puede probar que es imposible dar un conjunto recursivo de axiomas que permita demostrar todos los enunciados universalmente válidos de segundo orden.

En la lógica de segundo orden, entonces, no hay una definición sintáctica para la lógica subyacente y, por ende, el Programa de Hilbert es de plano irrealizable en teorías expresadas en lenguajes de este tipo.
Toda demostración expresada en un lenguaje de segundo orden es no-finitista, en el sentido de que la lógica subyacente no es definible sintácticamente (y no porque tenga una cantidad infinita de pasos). La regla de inferencia que se usa en las lógicas de segundo orden, y que tampoco es finitista, es la siguiente: "Q se deduce de P si para toda interpretación de los símbolos para la cual P es verdadera resulta que Q también es verdadera".

Ahora bien, si al lenguaje que dimos antes para la Aritmética le agregamos variables para los enunciados y fórmulas (y lo transformamos en un lenguaje de segundo orden) entonces es posible dar un conjunto finito de axiomas (concretamente, los Axiomas de Peano) tal que todo enunciado aritmético verdadero es demostrable a partir de ellos.

Insisto, todo enunciado aritmético verdadero es demostrable a partir de los Axiomas de Peano, si admitimos una lógica de segundo orden. (La teoría tiene indecidibles, pero no son enunciados aritméticos). En particular, si la Conjetura de Goldbach es verdadera entonces es demostrable.
Aunque es imposible prever qué tan difícil será encontrar una demostración de ella, ni tampoco será posible dar un algoritmo que verifique su corrección. De modo que el Tío Petros hizo muy mal en abandobar su búsqueda.

Termina aquí esta serie de entradas. Espero haber resuelto algunas dudas, pero, principalmente, espero haber sembrado dudas nuevas, mejores y más resistentes.

Fin