Gödel y Turing (Parte 16 y última)

(A la parte 15)

Las consecuencias del primer teorema de Gödel

Uno de los temas de controversia durante la crisis de los fundamentos giraba en torno a qué razonamientos matemáticos podían considerarse aceptables. Los intuicionistas, en particular, sostenían que las reglas usuales de la lógica sólo son válidas si se aplican a conjuntos finitos y que cuando tratamos con el infinito (que ellos sólo aceptaban en sentido potencial) las reglas de razonamiento debían ser diferentes. En particular los intuicinistas rechazaban para el infinito las demostraciones por el absurdo.

El Programa de Hilbert propuso un criterio objetivo para determinar cuáles razonamientos eran válidos y cuáles no. Para cada teoría matemática debía establecerse un algoritmo que fuera capaz de distinguir entre los razonamiento correctos y los incorrectos. En realidad, ya una idea similar había tenido Leibniz dos siglos antes. Leibniz había imaginado alguna vez la posibilidad de un lenguaje formal para la lógica, lenguaje que estaría constituido de tal modo que razonar equivaliera a calcular, de tal suerte que cuando dos filósofos tuvieran alguna disputa, en lugar de discutir, simplemente calcularían.

Hilbert esperaba que estos razonamientos algorítmicos (o finitistas) fueran suficientemente potentes como para demostrar toda verdad matemática (o al menos todas las verdades de la Teoría Elemental de Números). El Primer Teorema de Gódel dio por tierra con esta esperanza.

Pero la pregunta quedó en pie y sigue en pie desde entonces, aunque ya casi nadie la plantea explícitamente ¿qué es un razonamiento matemático válido? Dijimos clases atrás que toda verdad relativa a la Teoría de Números puede demostrarse a partir de los Axiomas de Peano pero ¿qué significa en este caso la palabra “demostrar”? La respuesta que suele darse a este interrogante es vaga e intuitiva, “todo el mundo sabe” qué es un razonamiento válido. De hecho, el primer Teorema de Gödel prueba que no existe, que nunca podrá existir, un criterio objetivo y finitista para determinar si una demostración es correcta o no.

Ése es el legado de Gödel, no la incertidumbre sobre la consistencia de la Matemática (consistencia de la que nadie duda aunque no pueda darse una demostración finitista de ello), sino la imposibilidad de determinar de modo claro y conciso cuáles razonamientos matemáticos son válidos y cuáles no. La decisión última a este respecto termina siendo en general una cuestión de mayorías, las demostraciones correctas son aquellas que la mayoría de los especialista consideran como tales. Las controversias en torno a la demostración de la conjetura de Kepler son tal vez una consecuencia de este legado.

¿Es posible que en el futuro un nuevo Gödel o un nuevo Hilbert den finalmente con un criterio (no finitista por fuerza) que permita distinguir de modo claro e indubitable cuáles son los razonamientos que pueden considerarse válidos y cuáles no? ¿Podrá suceder entonces que algunas demostraciones hoy consideradas correctas dejen de ser válidas en el futuro? Esto ha sucedido ya en el pasado, en 1806, por ejemplo, Ampère demostró (y la demostración fue publicada en una revista de la época, es decir la demostración era válida en ese tiempo) que toda función continua es derivable, excepto eventualmente en algunos puntos aislados y esto fue tomado como cierto hasta que en 1872 Weierstrass mostró ante la Academia de Ciencias de Berlín un ejemplo de una función continua que no es derivable en ningún punto (Bolzano había encontrado antes otro ejemplo, pero no lo publicó) ¿Podrá suceder esto nuevamente en el futuro? Algunos responderán que no, otros dirán que sí, otros, finalmente, diremos quién sabe.

FIN

(A la parte 15)

Gödel y Turing (Parte 15 y penúltima)

(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)

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)

Gödel y Turing (Parte 13)

(A la parte 12 - A la parte 14)

El Programa de Hilbert

Según veíamos en la parte anterior, a principios del siglo XX se descubrió que la Teoría de Conjuntos de Cantor era inconsistente. Esto significó una crisis, pues en ese momento la Teoría de Conjuntos se había transformado en la columna vertebral del Cálculo. De hecho, la Teoría de Conjuntos iba en camino de transformarse en el fundamento mismo de toda la Matemática, pues Georg Cantor, Richard Dedekind y Gottlob Frege (1), trabajando independientemente, habían logrado definir a partir de la noción de conjunto el concepto mismo de número.

Esta crisis de los fundamentos generó inicialmente dos reacciones, dos intentos casi diametralmente opuestos de recuperar la solidez de las bases de la Matemática. Una de estas reacciones fue el Programa Logicista, propuesto por Bertrand Russell hacia 1905 y cuya obra fundamental es Principia Mathematica. La otra propuesta fue el Intuicionismo o Cosntructivismo, contemporáneo del Logicismo y cuyo principal ideólogo fue L.E.J. Brouwer.

El Logicismo proponía fundamentar la Matemática en la Lógica y la Teoría de Conjuntos, aunque, para evitar las paradojas, Russell proponía hacer previamente una reestructuración en el lenguaje. Russell sostenía que todas las paradojas, no sólo las de la Teoría de Conjuntos sino en general todas las paradojas lógicas conocidas, provienen de un uso indebido de la autorreferencia, de la existencia de círculos viciosos en los que, metafóricamente, se crean serpientes que se comen a sí mismas desde su propia cola. Así por ejemplo, la “paradoja de Russell”, que vimos en la parte anterior, proviene de considerar conjuntos que son elementos de sí mismos.

Para evitar estas autorreferencias indebidas, Russell propuso establecer en el lenguaje una jerarquía estricta e inviolable, a la que llamó Teoría de los Tipos. En el nivel inferior de esta jerarquía estarían los individuos (por ejemplo, las letras). En el nivel inmediato superior estarían las oraciones de tipo-1, que son las oraciones que se refieren a los individuos. Por ejemplo “La letra a es una consonante” es una oración de tipo-1.

En el nivel inmediato superior están las oraciones de tipo-2, que se refieren a las oraciones de tipo-1. Así por ejemplo, “Es falso que la letra a es una consonante” es de tipo-2.

Luego están las oraciones de tipo-3, que son las que hablan de las oraciones de tipo-2, y así sucesivamente. De este modo toda oración, para ser válida, debería ocupar un lugar en esta jerarquía, en algún tipo-n. Cualquier oración que no se ajustara a esta restricción sería considerada un sin-sentido.

“Esta frase es falsa”, que se refiere a sí misma, es un ejemplo de sin-sentido, es decir, es una concatenación de palabras que parece decir algo, pero que en realidad carece de significado. Las propiedades que definen a los conjuntos, por supuesto, deberán también adaptarse a esta jerarquía de tipos. De tal modo que “El conjunto de todos los conjuntos” es un sin-sentido que, por ende, no define ningún ente matemático.

Esta jerarquía, en efecto, evita todas las paradojas (al menos todas las paradojas conocidas hasta la actualidad). El problema es que cuando tratamos de fundamentar toda la Matemática ateniéndonos a estas restricciones de lenguaje, la situación se vuelve insostenible. Por ejemplo, supongamos que quisiéramos establecer a modo de axioma que “Toda afirmación es verdadera o falsa”. Pues bien, no podríamos hacerlo. En efecto, “Toda afirmación es verdadera o falsa” habla de todas las afirmaciones, en particular habla de sí misma, y por lo tanto es autorreferente y un sin-sentido.

Ante este problema, Bertrand Ruseell introduce el llamado Axioma de Reductibilidad, que dice que toda oración de tipo-n es equivalente a alguna oración de tipo-1. De este modo podemos decir con toda corrección que “Toda afirmación de tipo-1 es verdadera o falsa” y como cualquier otra afirmación es equivalente a una de tipo-1 estaremos diciendo en definitiva que toda afirmación es verdadera o falsa.

Pero si bien se mira el Axioma de Reductibilidad tira por la borda toda la filosofía de la jerarquía del lenguaje. Hemos creado entonces una rígida jerarquía del lenguaje, para decir inmediatamente después que toda la jerarquía se reduce al tipo-1.

El mismo Russell se vio obligado a admitir que este axioma no era para nada evidente y que se vio obligado a introducirlo meramente porque le resultaba indispensable para completar ciertas definiciones o demostraciones que no habría sabido hacer de otro modo. Pero la introducción de un axioma controvertido con la única justificación de que resulta práctico no es una buena idea si es que estamos construyendo una fundamentación indubitable para la Matemática. Por eso mismo las controversias en torno al Axioma de Reductibilidad acabaron por herir de muerte la idea de Russell y, finalmente, hacia 1920 el Logicismo había perdido toda acabado por perder toda influencia.

La segunda propuesta, contemporánea del Logicismo, fue el Intuicionismo o Constructivismo, cuyo principal impulsor fue L.E.J. Brouwer. Los intuicionistas sostenían que las inconsistencias de la Teoría de Conjuntos se debían simplemente al uso del infinito actual, concepto que los intuicionistas consideraban inconsistente en sí mismo. Más allá de este rechazo al uso del infinito actual, el concepto central de la filosofía intuicionista es el concepto de algoritmo.

Para los intuicionistas los números naturales están dados a priori, por una intuición inherente al pensamiento humano. Cualquier otro objeto matemático sólo existe si es posible mostrar un algoritmo que lo construya a partir de los números naturales. Así por ejemplo, la raíz cuadrada de 2 no existe como número “actual” o “acabado”, pero sí existen (porque se pueden calcular algorítmicamente) números racionales que se acercan tanto como uno quiera a un número positivo que elevado al cuadrado sea igual a 2.

Otro ejemplo del papel de la noción de algoritmo desempeña en el pensamiento intuicionista es éste: para los intuicionistas una propiedad, digamos una propiedad referida a los números naturales, sólo puede considerarse bien definida si existe un algoritmo que, dado un número, nos permita verificar si el número cumple o no la propiedad en cuestión. Usando la terminología que desarrollamos en las partes anteriores, para los intuicionistas las únicas funciones que existen son las funciones recursivas y los únicos conjuntos que existen son los conjuntos recursivos.

El llamado Programa Intuicionista se proponía reconstruir toda la Matemática respetando esta filosofía. Desde luego, esta reconstrucción dejaría fuera de la Matemática a la teoría de Cantor, así como gran parte del Análisis.

Hacia 1920, con la caída del Logicismo, el Intuicionismo comenzaba a transformarse en la filosofía dominante de la Matemática y esto ponía, por decirlo dramáticamente, en riesgo de muerte a la teoría de Cantor.

David Hilbert, uno de los más grandes matemáticos de fines del siglo XIX y principios del XX, había sido desde siempre un gran defensor de las ideas de Cantor y, ante el avance del intuicionismo, decide proponer una filosofía alternativa: el Formalismo.

La idea de Hilbert, que además de ser un gran matemático era un muy hábil político, fue crear un concepto que sedujera a los intuicionistas, es decir que fuera completamente compatible con su forma de ver la Matemática, pero que a la vez permitiera conservar la intacta teoría de Cantor. La idea de Hilbert consistió esencialmente en respetar la exigencia algorítmica que impregnaba el pensamiento intuicionista, pero llevándola a los razonamientos matemáticos en lugar de aplicarla a los objetos matemáticos en sí.

La idea central del Formalismo es la siguiente: toda teoría matemática debe ser axiomática (es decir, debe estar basada en axiomas de los cuales se deducen todos los teoremas), pero la axiomatización debe ser realizada de tal modo que exista un algoritmo que, dada una sucesión de enunciados, nos indique si esa sucesión constituye o no una demostración. Es decir, la exigencia de recursividad ya no se refiere a las propiedades de los objetos matemáticos, sino a las propiedad (referida a sucesiones de afirmaciones) de “ser una demostración”. Una teoría axiomática para la cual exista un algoritmo así es llamada una teoría finitista. Podemos hablar del infinito actual, dice Hilbert, siempre y cuando al hablar de él hagamos razonamientos finitistas.

En concreto, la propuesta de Hilbert era axiomatizar de modo finitista la Teoría de Números y luego demostrar, también de modo finitista, que esa axiomatización es completa y consistente. Donde completa significa que toda verdad pueda deducirse de los axiomas y consistente significa que ninguna falsedad puede ser demostrada. Una vez así axiomatizada la Teoría de Números se tendría un fundamento sólido para el resto de la Matemática (digamos, dadme un punto de apoyo bien fundamentado y fundamentaré a partir de él toda la Matemática).

Tras una década de luchas y polémicas, en septiembre de 1930 los intuicionistas aceptaron finalmente el Programa de Hilbert. Si el programa podía completarse, los intuicionistas aceptarían incluso el infinito actual. Pero fue justo en septiembre de 1930 (2) cuando Gödel expuso públicamente por primera vez sus teoremas de incompletitud.

El primer teorema dice que es imposible dar una axiomatización finitista de la Teoría de Números que sea a la vez completa y consistente. El segundo teorema dice que es imposible demostrar de modo finitista la consistencia de la Teoría de Números. En otras palabras, justo en el mismo momento en que parecía que el programa de Hilbert había triunfado, los teoremas de Gödel demostraron que el ese programa era irrealizable.

En la próxima parte comenzaremos a estudiar la demostración del primer teorema de Gödel.

Notas:

(1) Hay que aclarar que el concepto que tenían Frege y Dedekind de la noción de conjunto difería en algunos puntos esenciales de la noción que tenía Cantor.

(2) Kurt Gódel expuso por primera vez su teorema en septiembre de 1930, en un congreso sobre fundamentos de la Matemática. El artículo que contiene los teoremas se publicó algunos meses después, en 1931.

(A la parte 12 - A la parte 14)