La autorreferencia en la demostración de Gödel (Parte 3)

(A la parte 2 - A la parte 4)

Demostraciones

- Profesor, ¿cuándo llegamos a la autorreferencia?

- Paciencia, ya falta poco.

En el capítulo anterior dijimos que el Programa de Hilbert proponía dar axiomas para la Aritmética y que estos axiomas (así como las reglas de inferencia, que son las que nos dicen qué conclusiones podemos obtener a partir de ciertas hipótesis) debían ser elegidos de modo tal que la corrección de cualquier demostración basada en ellos pudiera ser verificada (desde el nivel de la Metamatemática) mecánicamente en una cantidad finita de pasos (es decir, debía ser posible programar una computadora para que verificara si una demostración es válida o no).

En concreto, las demostraciones que contemplaba el Programa de Hilbert como válidas debían ser traducibles a una sucesión finita de enunciados tales que cada uno de estos, o bien era un axioma, o bien podía deducirse de enunciados previamente ubicados en la sucesión por aplicación de ciertas reglas de inferencia específicas. (1)

Esta idea impone tres características a la formalización de la Aritmética. La primera es que sus enunciados deben poder traducirse a un lenguaje con símbolos bien definidos (requisito necesario para que haya un algoritmo que trabaje sobre esos enunciados -a nivel metamatemático-).

A los efectos de esta serie de entradas, el lenguaje que usaremos constará de los símbolos "+" y ".", la constante 1, a los que agregaremos paréntesis y símbolos para las operaciones lógicas. El lenguaje tendrá también variables, x, y, z,... que sólo podrán representar números naturales (nunca expresarán funciones, conjuntos u otros objetos (2)).

Observemos que la Metamatemática trabaja solamente a nivel sintáctico, por lo que la expresión:

(1 + 1).(1 + 1) = 1 + 1 + 1 + 1

será, a nivel metamatemático, diferente de la expresión:

1 + 1 + 1 + 1 = (1 + 1).(1 + 1)

porque, aunque ambas tienen los mismos símbolos, estos están escritos en diferente orden.

Asumamos que, para su tratamiento metamatemático, todos los enunciados han sido traducidos a este lenguaje formal. Asumamos también que tenemos una secuencia de enunciados y que queremos escribir un programa que verifique si esa secuencia es, o no, una demostración válida. El programa "tomará" entonces un enunciado de la secuencia y deberá verificar si se trata, o no, de un axioma.

La segunda característica es, entonces, que exista un algoritmo que verifique en una cantidad finita de pasos si un enunciado es, o no, un axioma.

Continuando con el proceso que debería seguir ese programa, si un enunciado no es un axioma, el programa debe se capaz de verificar si el enunciado puede deducirse de enunciados anteriores en la sucesión. La tercera característica es, entonces, que la relación "Q se deduce de las hipótesis H1, H2, H3,..." debe ser verificable algorítmicamente.

En realidad, podemos reducirnos a tomar una única regla de inferencia: la llamada Regla del Modus Ponens, que dice que de P y de P ---> Q se deduce Q. (La regla debe ser entendida a nivel sintáctico, sin apelación a posible significados.)

Diremos que una propiedad es recursiva si es verificable algorítmicamente. Podemos decir entonces que el sistema de axiomas y sus reglas de inferencia deben ser ambos recursivos.

Continuará...

Notas:

(1) Éste es el proceso de verificación metamatemática de las demostraciopnes que proponía el Programa de Hilbert. Desde luego, no es el proceso por el que los matemáticos encuentran esas demostraciones.

(2) Toda teoría tiene dos tipos de axiomas: sus axiomas específicos y también los axiomas lógicos, que son generales y comunes a todas las teorías. Estos últimos son enunciados que valen cualquiera sea el universo del discurso considerado (como por ejemplo, "Para todo x, x = x"). Si respetamos las restricciones para el uso de variables entonces es posible dar un sistema de axiomas que respeta las condiciones de Hilbert y que permite deducir todas esas afirmaciones universalmente válidas (esto fue probado por Gödel en 1929). Si admitiéramos variables que representaran funciones, conjuntos, etc. entonces el Programa de Hilbert sería irrealizable al nivel mismo de esta lógica subyacente.

(A la parte 2 - A la parte 4)

La autorreferencia en la demostración de Gödel (Parte 2)

(A la parte 1 - A la parte 3)

La dialéctica Sintaxis /Semántica

Los teoremas de Gödel, publicados en 1931, forman parte de una larga polémica sobre los Fundamentos de la Matemática que había comenzado en 1872 con el descubrimiento, por parte de Cantor, de los transfinitos, y que se había potenciado a partir de 1902 con el descubrimiento de la Paradoja de Russell.

El campo de batalla de la polémica era nada menos que el infinito. La escuela constructivista, encabezada por L.E.J. Brouwer, sostenía que la introducción del infinito actual en Matemáticas era absurda e injustificada y que la teoría de los transfinitos de Cantor era solamente un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir mecánicamente en una cantidad finita de pasos. Por ejemplo, para ellos no podía hablarse de la totalidad de los números naturales, sino de una cantidad siempre finita y creciente de números que son calculados uno por uno. Los enunciados que hablan de totalidades infinitas, para los constructivistas carecían de significado.

Hacia 1920 interviene en la polémica David Hilbert quien, en una serie de papers publicados a lo largo de unos diez años, propone el que hoy es conocido como el Programa de Hilbert y que, en esencia, llevaba la exigencia de finitud y de constructividad de los objetos matemáticos a los razonamientos matemáticos.

Con más precisión, Hilbert proponía la creación de una nueva ciencia a la que él llamaba Metamatemática. Esta ciencia tendría como objetivo el verificar la validez de los razonamientos matemáticos. Para evitar polémicas (y para asegurarse de que no surgieran paradojas) esta ciencia sería puramente finitista: la Metamatemática trataría a los enunciados y a los razonamientos matemáticos como si fueran simples secuencias de símbolos sin significado a los que manipularía mecánicamente en una cantidad finita de pasos.

Se ha dicho en algunos textos de divulgación que el Programa de Hilbert proponía reducir la Matemática a un juego de símbolos carente de significado, se ha dicho también que para Hilbert el concepto de "verdad matemática" no existía. Nada más falso. Hilbert, comprendamos, era ante todo un investigador matemático (el mejor de su tiempo) por lo que es imposible, inimaginable, que pudiera pensar así. Esas características las atribuía Hilbert, no a la Matemática, sino a la Metamatemática.

La Matemática trabaja a un nivel semántico, lleno de significados. El matemático, en el día a día, siempre trabaja, crea, conjetura, demuestra y sufre, como si lo que tuviera entre manos fueran objetos reales.

La Metamatemática, según la idea de Hilbert, que trabaja a nivel sintáctico, provee los métodos para verificar si los razonamientos, que el matemático ha obtenido como fruto final de su trabajo creador, son correctos. Para hacer esta verificación los razonamientos serían cargados en una computadora que verificaría si el razonamiento es válido, o no. Hilbert, desde luego, no hablaba de computadoras, pero lo que he dicho en la oración anterior refleja la idea esencial de Hilbert: la validez del razonamiento es verificada mediante manipulaciones mecánicas de símbolos realizadas en una cantidad finita de pasos (la verificación del razonamiento, no su obtención).

En concreto, el Programa de Hilbert proponía dar un conjunto de axiomas para la Aritmética (1) que cumpliera estas cuatro condiciones:

1. El sistema debía ser consistente (es decir, no debía existir un enunciado P tal que P y su negación fueran simultáneamente demostrables).

2. La validez de cualquier demostración debía ser verificable por manipulaciones mecánicas (sintácticas) en una cantidad finita de pasos.

3. Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable.

4. La consistencia de los axiomas debía ser verificable mecánicamente en una cantidad fnita de pasos.

Nótese que estas condiciones no son matemáticas sino metamatemáticas. Si estas cuatro condiciones pudieran cumplirse entonces la noción de "demostrabilidad" (sintáctica) y de "verdad" (semántica) podrían considerarse equivalentes. Pero los teoremas de Gödel demostraron precisamente que esas cuatro condiciones no se pueden cumplirse a la vez. Si se cumplen 1 y 2 entonces 3 es falsa y 4, si el sistema es razonablemente potente, es irrealizable.

En el próximo capítulo precisaremos qué quiere decir "razonablemente potente" y comenzaremos a analizar la demostración de Gödel.

Continuará...

(1) Nota: La Aritmética es la teoría que habla de la suma y el producto de los números naturales. Hilbert consideraba que era ésta la teoría fundamental de la Matemática (y no la Teoría de Conjuntos).

(A la parte 1 - A la parte 3)

La autorreferencia en la demostración de Gödel (Parte 1)

(A la parte 2)

¿Qué decimos cuando decimos "Esta oración no es demostrable"?

En estos últimos años, por diversos motivos y en diferentes ámbitos, me ha tocado discutir extensamente la demostración de los teoremas de Gödel. En esas ocasiones he notado que hay ciertas dudas que aparecen recurrentemente en el público y que, tal vez, sean compartidas por algunos de los lectores de este blog.

La intención de esta serie de entradas es tratar de despejar esas dudas. No intentaré desarrollar en detalle las demostraciones de los teoremas de Gödel, sino que haré un bosquejo general poniendo énfasis especial en dos puntos:

1. El llamado Primer Teorema de Incompletitud de Gödel dice que, dado un sistema axiomático para la Aritmética que cumpla ciertas condiciones (que recordaremos más adelante), siempre es posible encontrar una afirmación aritmética que no puede ser demostrada ni refutada a partir de esos axiomas.

Suele decirse (yo mismo lo he dicho en más de una ocasión) que la demostración de este teorema consiste en construir una afirmación aritmética que dice: "Esta oración no es demostrable".

Pero ¿es realmente así? ¿Habla realmente la afirmación de su propia no-demostrabilidad? La respuesta es que la afirmación no habla de sí misma. Más exactamente, veremos que la afirmación puede llegar a considerarse autorreferente solamente si se aceptan ciertas convenciones arbitrarias que son externas al sistema de axiomas.

El segundo punto que trataremos es éste:

2. Tomemos, a modo de ejemplo, los axiomas de Peano (que son axiomas de la Aritmética). Aceptemos que esos axiomas forman un sistema consistente (como, de hecho, suele aceptarse). Del llamado Segundo Teorema de Incompletitud de Gödel se deduce que la afirmación "Los axiomas de Peano son consistentes" no puede demostrarse ni refutarse a partir de esos axiomas.

Ahora bien, si una afirmación P no puede demostrarse ni refutarse a partir de un sistema de axiomas (llamémoslo A) entonces tanto la afirmación P como su negación pueden ser agregadas al sistema A y en ambos casos se obtendrá un sistema consistente. (El ejemplo histórico clásico es tomar A como los primeros cuatro postulados de Euclides y como P, el postulado de las paralelas.)

En particular, esto quiere decir que la afirmación "Los axiomas de Peano no son consistentes" puede agregarse a los axiomas de Peano de modo que el sistema resultante ¡sea consistente!. Ahora... ¿no es raro? ¿Cómo puede ser consistente con los axiomas de Peano la afirmación que niega (falsamente) que esos axiomas sean consistentes? Como veremos, la paradoja es sólo aparente y resulta de una mala interprertación de lo que realmente dice el enunciado aritmético "Los axiomas de Peano no son consistentes".

La tarea está planteada. Sólo falta arremangarse y llevarla a cabo.

Continuará...

(A la parte 2)

500 x 1

Cambio 500 respuestas excelentes por una buena pregunta.

Diálogo (2º parte)

(Viene del diálogo anterior.)

F: ¿Y dónde queda entonces su analogía con la cuadratura del círculo?

G: Cuando planteé en esta entrada la analogía entre el movimiento del alfil y la cuadratura del círculo, imaginaba un único alfil en un tablero de ajedrez, sin otras piezas presentes. Bajo ésas condiciones, si el alfil es movido según las reglas del ajedrez, nunca podrá pasar de una casilla blanca a una negra.

F: ¿Y eso demuestra que la cuadratura del círculo es imposible?

G: No, definitivamente no lo demuestra. Es sólo una imagen que sirve para ejemplificar la idea de imposibilidad absoluta en Matemática. Es tan imposible lograr la cuadratura del círculo como lo es lograr que el alfil pase de una casilla blanca a una negra (bajo las condiciones que antes describí).

F: Pero sí es posible lograr que el alfil pase de una casilla blanca a una negra en una partida de verdad. ¿No invalida esto su analogía?

G: Al contrario. La cuadratura del círculo pide, dado un círculo, construir un cuadrado que tenga exactamente la misma área, usando solamente una regla no graduada y un compás. Bajo esas condiciones la construcción es absolutamente imposible. Pero sí es posible hacer la construcción si admitimos otros recursos; de la misma forma que el alfil sí puede cambiar de color si agregamos otras complejidades a la situación.

F: ¿Cómo?

G: Por ejemplo, dado el círculo, coloque un hilo alrededor de su borde de modo que ambos, borde e hilo, coincidan perfectamente. Estire luego el hilo de modo que quede como un segmento. Trace el segmento determinado por el hilo. Si el diámetro del círculo mide uno, el segmento medirá pi y a partir de él es muy fácil trazar el cuadrado pedido.

F: Entonces ¿es posible o es imposible lograr la cuadratura del círculo?

G: Es imposible si nos limitamos a usar los recursos que exige el problema clásico (regla no graduada y compás). Pero es posible si admitimos el uso de otros elementos. Por eso, sus extraños ejemplos de partidas en las que el alfil cambia de color, lejos de refutar la analogía, la hacen más completa.

F: Pero usted dice que la analogía no demuestra que la cuadratura es imposible.

G: No, claro que no. La demostración se basa en tres hechos:

1. Partiendo de un segmento unidad sólo se pueden construir (usando regla no graduada y compás) segmentos cuya longitud sea un número algebraico. [No se pueden obtener todos los números algebraicos, pero eso no es importante ahora.]

2. La cuadratura de círculo es posible si y sólo si se puede construir un segmento de longitud pi.

3. Pi no es algebraico.

La combinación de los tres hechos da como resultado ineludible... bueno, lo que ya sabemos: la cuadratura del círculo es imposible.

F: ¿Las demostraciones de esos tres hechos son fáciles de entender?

G: La demostración del hecho (1) no es difícil, sólo requiere saber un poco de geometría elemental. la demostración del hecho (2) es un poco más difícil. La del hecho (3) es bastante más complicada.

F: ¿Y si hubiera un error en la demostración del hecho (3)? (Digo ésa porque es la más difícil.)

G: La demostración ha sido revisada, una y otra vez, por generaciones de matemáticos quienes han ratificado unánimemente su validez.

F: ¿Y si, a pesar de todo, hubiera un error? ¿Un error que se le hubiera pasado por alto a todos los miles de matemáticos que revisaron la demostración?

G: ¿Usted estuvo alguna vez en París?

F: Dígamelo usted, ya que fue usted quien me creó.

G: Bueno. Usted nunca estuvo en París, como yo tampoco.

F: Ya veo, va a preguntarme cómo sé que la Torre Eiffel realmente existe.

G: Exacto. ¿Cómo lo sabe? ¿Cómo sabe que no hay una conspiración universal para hacernos creer (a quienes nunca estuvimos en París) que existe algo llamado "Torre Eiffel"? ¿Cómo sabe si en realidad en ese lugar de París no hay nada? ¿Cómo sabe si lo que sucede es que cada supuesto visitante de la torre es reclutado para formar parte de esa conspiración y propagar la mentira? ¿Cómo sabe si todas las supuestas fotos de la torre son trucadas? Etcétera, etcétera...

F: No puedo saberlo con certeza.

G: Exacto. En realidad ni siquiera podría saberlo aunque estuviera de pie frente a la torre misma, porque sus sentidos podrían estar siendo engañados. Pero la suposición infinitamente más razonable es que la Torre Eiffel sí existe y que todas las fotografías que la muestran (bueno, digamos que casi todas) representan un objeto real.

F: Supongo que tiene razón.

G: De la misma manera, exactamente de la misma manera, la suposición infinitamente más razonable es que realmente la cuadratura del círculo es imposible, porque generaciones de matemáticos así lo han comprobado. Lo más razonable, lo único razonable, es abandonar todo intento de resolver el problema (usando los método clásicos).

F: Entonces ¿por qué hay gente que lo sigue intentado?

G: No tengo idea.

F: ¿Me permite una última pregunta?

G: Por supuesto.

F: Siguiendo sus palabras...¿De la misma manera, de exactamente la misma manera, la suposición más razonable para mí es aceptar que estoy conversando con usted?

G: Sí, claro.

F: Y sin embargo, yo no existo. Como dije antes, usted me creó. ¿Dónde nos deja eso?

G: Yo le preguntaría qué clase de afirmación es "yo no existo". ¿Quién es el "yo" que afirma que no existe?

¿Fin?

Una película ¿sobre Gödel?

Gödel from Igor Kramer on Vimeo.

Para seguirla, hay que saber un poquito de inglés.