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

(A la parte 4 - A la parte 6)

La codificación de Gödel

Vamos a comenzar la demostración del Primer Teorema de Incompletitud de Gödel. Imaginemos que van a darnos un sistema de axiomas para la Aritmética que es recursivo y consistente, y que además permite demostrar todos los enunciados finitistas verdaderos. Tendremos que demostrar que existe un enunciado P tal que tanto él como su negación no son demostrables a partir de esos axiomas. [Por razones didácticas no vamos a suponer que trabajamos con un sistema de axiomas general, sino que nos han dado un sistema específico y que vamos a reproducir en él la demostración de Gödel.]

Hablo en futuro y digo "van a darnos un sistema de axiomas" porque el primer paso de la demostración de Gödel (y esto es importante destacarlo) no depende del sistema de axiomas que vayan a darnos.

Este primer paso consiste en asignarle a cada enunciado y a cada sucesión finita de enunciados un número natural, al que llamaremos el código de ese enunciado o de esa sucesión finita de enunciados. Hay muchas formas de definir esta asignación, pero, no importa el modo que elijamos para hacerlo, se deben cumplir siempre las siguientes condiciones:

1. A cada objeto (ya sea un enunciado, ya sea una sucesión de enunciados) le debe corresponder un número natural diferente.

2. Debe existir un algoritmo que, dado un enunciado o una sucesión de enunciados, nos permita calcular qué número le corresponde.

3. Debe existir un algoritmo que, dado un número natural, nos permita determinar si este número es. o no es, el código de un enunciado o de una sucesión, y que, en caso de que sí lo sea, determine exactamente a qué objeto corresponde. (1)

Cuando hablamos de "algoritmo" estamos hablando de un procedimiento sintáctico, por lo tanto los códigos se asignan a los enunciados o a las sucesiones de enunciados siempre que estos objetos estén escritos en el lenguaje formal.

Como decía antes, hay muchas maneras de asignar los códigos. Raymond Smullyan, en su libro Gödel's Incompleteness Theorems, trabaja con un lenguaje de 13 símbolos (incluyendo un símbolo especial para separar los enunciados que forman parte de una sucesión) y, traduciendo cada símbolo a un "dígito", convierte a cada enunciado (o sucesión de enunciados) en un número natural escrito en base 13. En Gödel para Todos se procede de manera similar, pero usando secuencias de dígitos binarios. El propio Gödel en su demostración original usa productos de potencias de primos (2). Aquí evitaremos dar detalles de cómo se hace la asignación, asumiremos simplemente que la asignación ha sido definida.

En algunas charlas (y tal vez también en alguna entrada de este mismo blog) he dicho que, por ejemplo, al enunciado "2 es par" se le asigna un número natural. Sin embargo, esta forma de hablar, que tiene la virtud de la simplicidad, encierra el germen de un error: el de confundir los conceptos sintácticos con los conceptos semánticos.

Como dije antes, la asignación de códigos es un procedimiento puramente sintáctico. ¿Cómo traducimos "2 es par" al lenguaje formal? En realidad hay muchas formas diferentes de hacerlo, por ejemplo (en lo que sigue usamos la "E" para inidcar "existe"):

Ex((1 + 1) = (1 + 1).x)

Ex((1 + 1).x = (1 + 1))

Ey((1 + 1) = (1 + 1).y)

Ex((1 + 1).y = (1 + 1))

...y muchos más.

Sintácticamente los cuatro enunciados escritos más arriba son diferentes y, por lo tanto, a cada uno de ellos le corresponde un código diferente. No existe un código para "2 es par", existen diferentes códigos para cada una de las infinitas formas en que puede ser traducido al lenguaje formal. Por lo tanto, no debemos pensar a los códigos como asignados a frases escritas en castellano, sino a objetos sintácticos llamados "enunciados" o "sucesiones de enunciados".

La observación anterior puede parecer trivial, pero no lo es. Los conceptos semánticos nos resultan más familiares que los sintácticos y por eso tendemos a pensar, a hablar, a explicar e, inclusive, a escribir libros de Lógica convirtiendo lo sintáctico en semántico (para que sea más "digerible"), pero esta conversión puede llevarnos a confusión.

Veamos otro ejemplo en el que se ve claramente la diferencia entre conceptos semánticos y sintácticos (entre conceptos matemáticos y metamatemáticos). Supongamos que tomamos como axiomas los enunciados A1,.., An (que, me apresuro a aclarar, no cumplen las hipótesis del Teorema de Gödel) y que nos dicen que el enunciado "1 + 1 = 1" es demostrable a partir de esos axiomas. ¿Debemos concluir que A1,...,An es un sistema inconsistente? La respuesta es que no. Los axiomas podrían formar un sistema consistente. (Recordemos que consistente significa que P y no-P nunca son al mismo tiempo demostrables.)

¿Cómo es posible que "1 + 1 = 1" sea demostrable, pero que el sistema sea consistente? Si uno se hace esa pregunta es que está confundiendo "demostrable" con "verdadero" (sintaxis con semántica).

¿Qué quiere decir que A1,.., An permitan demostrar el enunciado "1 + 1 = 1"? Respuesta: significa que existe una sucesión finita de enunciados cuyo enunciado final es "1 + 1 = 1" y en la que cada uno de ellos es, o bien uno de los A1,.., An, o bien se deduce de enunciados anteriores por aplicación del modus ponens. Notemos que esta respuesta está basada en conceptos sintácticos y que en ella no tiene cabida el concepto de "verdad" (o de "falsedad"). Notemos además que esa demostración de "1 + 1 = 1", como toda sucesión finita de enunciados, tiene asignada (a manera de código) un número natural.

Si los axiomas cumplieran la hipótesis de que todo enunciado finitista verdadero es demostrable, entonces sí formarían un sistema inconsistente. En efecto, "-(1 + 1 = 1)" (el signo "-" indica negación) es un enunciado finitista verdadero y, si se cumpliera la hipótesis, entonces ese enunciado sería demostrable. Como también "1 + 1 = 1" es demostrable entonces el sistema sería inconsistente.

Sin embargo, es posible que A1,.., An (que, dijimos, no cumple las hipótesis de Gödel) no admita una demostración para el enunciado "-(1 + 1 = 1)" y que, por lo tanto, sea un sistema consistente.

Continuará...

Notas:

(1) Dos aclaraciones de lenguaje: A los efectos de esta serie de entradas, los números naturales son 1, 2, 3, 4, 5, 6, etc. y por algoritmo entendemos un procedimiento mecánico que se completa en una cantidad finita de pasos.

(2) Gödel le asigna a cada símbolo del lenguaje un número impar. Si un enunciado E está formado por lo símbolos s1, s2, s3,... entonces le corresponde el número 2^c(s1).3^c(s2).5^c(s3).7^c(s4).... conde c() es el código de cada símbolo. A la sucesión de enunciados E1, E2, E3,... le corresponde el código 2^c(E1).3^c(E2)....

(A la parte 4 - A la parte 6)