Gödel y la Metamatemática

Kurt Gödel y la Metamatemática

Un todavía desconocido Kurt Gödel dejó asombrada a la comunidad matemática cuando, con apenas veintitrés años, ofreció una demostración de la completitud del Cálculo Lógico de Primer Orden. Gödel presentó este resultado en su tesis doctoral de 1929 y lo publicó al año siguiente. Como habíamos indicado en el artículo previo, la completitud era una de las cuestiones fundamentales que permanecían abiertas en la Lógica Matemática.

La conferencia pronunciada por Hilbert en el Congreso Internacional de Matemáticos celebrado en Bolonia en 1928 contribuyó a despertar el interés de Gödel por los problemas relacionados con la completitud, la consistencia y la decidibilidad de los sistemas formales. Este temprano interés le permitiría ofrecer el importante resultado que acabamos de mencionar.

Pero aún le quedaba mucho que ofrecer. Apenas dos años después, en 1930, Gödel anunció los resultados que le darían fama imperecedera. Su demostración completa aparecería publicada en 1931 bajo el título Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme —«Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines»—.

Los Teoremas de Incompletitud serán el tema del próximo artículo. Antes de abordar su demostración necesitamos introducir dos herramientas desarrolladas por Gödel: las funciones recursivas y la aritmetización de la sintaxis mediante los llamados números de Gödel.

El Programa Formalista

Como vimos a lo largo de esta serie, a finales de los años veinte ya estaban plenamente planteados los objetivos del llamado Programa Formalista, con Hilbert a la cabeza como su principal defensor. Este programa perseguía formalizar las teorías matemáticas, esto es, transformar la Aritmética, la Geometría y el Análisis en sistemas de símbolos regidos por axiomas y reglas de inferencia explícitas.

Dentro de un sistema formal, las demostraciones debían poder comprobarse atendiendo únicamente a la forma de los símbolos, sin depender de una interpretación intuitiva de su significado. A partir de unos axiomas iniciales, las reglas permitirían obtener en un número finito de pasos nuevas fórmulas que expresasen los teoremas propios de cada campo matemático.

Este carácter mecánico de la deducción formal puede compararse con el funcionamiento de un programa informático: para comprobar si cada paso de una demostración es correcto no es necesario comprender el contenido de las fórmulas, sino verificar que se han aplicado las reglas permitidas.

El finitismo, sin embargo, no consistía simplemente en que las demostraciones formales poseyeran una longitud finita. Era la exigencia de que las demostraciones metamatemáticas de consistencia recurrieran exclusivamente a procedimientos elementales aplicados a signos y configuraciones finitas. La posibilidad de realizar este proyecto permanecía todavía abierta.

Metamatemática

Hilbert no consideraba que toda aproximación intuitiva estuviese excluida de la Matemática. La comprensión intuitiva debía operar, sobre todo, en el nivel metamatemático. Los axiomas, las fórmulas y las demostraciones de una teoría formal podían ser estudiados desde fuera como sucesiones finitas de signos.

El matemático adopta entonces el papel de metamatemático: un observador externo que estudia el sistema formal y sus propiedades como un objeto matemático. Puede comprobar, por ejemplo, si una cadena de fórmulas constituye una demostración legítima, si los axiomas son independientes o si una contradicción puede derivarse dentro del sistema.

Dos de las propiedades principales son la consistencia y la completitud. Un sistema es consistente si no permite demostrar simultáneamente una fórmula y su negación. Un sistema es sintácticamente completo si, para toda sentencia \(A\) formulable en él, puede demostrarse \(A\) o puede demostrarse \(\neg A\).

No debe confundirse esta completitud con el Teorema de Completitud de la Lógica de Primer Orden demostrado anteriormente por Gödel. Este último afirma que toda fórmula válida en todas las interpretaciones es demostrable en el cálculo lógico. Los Teoremas de Incompletitud se refieren, en cambio, a teorías formales concretas suficientemente potentes para expresar la Aritmética.

Los resultados de Gödel impondrían una profunda limitación al Programa de Hilbert: determinados sistemas formales consistentes no pueden demostrar todas las sentencias aritméticas que pueden formularse en su lenguaje y tampoco pueden, bajo ciertas condiciones, demostrar su propia consistencia.

Funciones recursivas de Gödel

Antes de introducirnos en la demostración de los Teoremas de Incompletitud debemos presentar la noción de recursión. Esta noción era conocida con anterioridad, pero Gödel la incorporó a su artículo de 1931 como una herramienta para describir rigurosamente determinadas operaciones aritméticas efectivas.

La clase que Gödel denominó entonces «funciones recursivas» se aproxima a lo que actualmente denominamos funciones recursivas primitivas, aunque ambas definiciones no coinciden exactamente en todos sus detalles. En esta exposición utilizaremos la presentación moderna de la recursión primitiva.

Decimos que una función numérica \(f\), cuyos argumentos y valores son números naturales, está definida mediante recursión primitiva a partir de las funciones \(h\) y \(q\) si:

$$f(0,x_{2},\ldots,x_{n})=h(x_{2},\ldots,x_{n})$$

$$f(k+1,x_{2},\ldots,x_{n})=q\left(k,f(k,x_{2},\ldots,x_{n}),x_{2},\ldots,x_{n}\right)$$

para todo número natural \(k\) y todos los valores \(x_{2},\ldots,x_{n}\).

La primera ecuación establece el caso inicial. La segunda muestra cómo calcular el valor correspondiente a \(k+1\) a partir del valor ya obtenido para \(k\). La función no se define mediante una referencia circular indeterminada: cada cálculo retrocede, tras un número finito de pasos, hasta el caso inicial.

Podemos verlo en el caso más sencillo, cuando \(f\) posee un único argumento. Supongamos:

$$f(0)=h$$

$$f(k+1)=q(k,f(k))$$

Para calcular \(f(4)\), aplicamos sucesivamente la segunda regla hasta llegar al caso inicial:

$$f(1)=q(0,h)$$

$$f(2)=q(1,q(0,h))$$

$$f(3)=q(2,q(1,q(0,h)))$$

$$f(4)=q(3,q(2,q(1,q(0,h))))$$

La recursión es, como vemos, un esquema de definición.

Funciones recursivas primitivas

Una función es recursiva primitiva si puede construirse a partir de unas funciones iniciales elementales mediante un número finito de aplicaciones de las operaciones de composición y recursión primitiva.

Las funciones iniciales son:

• la función constante cero;
• la función sucesor \(s(x)=x+1\);
• las funciones de proyección, que seleccionan uno de los argumentos recibidos.

Las funciones recursivas primitivas son funciones totales: ofrecen un valor para cualquier combinación admisible de argumentos. Podemos calcular su valor de manera efectiva en un número finito de pasos.

En los lenguajes de programación modernos pueden compararse, de manera aproximada, con procedimientos formados mediante composiciones y bucles cuyo número de iteraciones queda determinado de antemano por los datos de entrada. Esta comparación es únicamente intuitiva, pero permite comprender por qué el cálculo siempre termina.

Aritmética recursiva de Gödel

Gödel subraya que las operaciones fundamentales de la Aritmética, como la suma o la multiplicación, pueden expresarse mediante funciones recursivas primitivas. Gracias a ello, sus valores pueden calcularse en un número finito de pasos reduciendo el problema al caso inicial en el que una de las variables vale \(0\).

Veamos, por ejemplo, la función suma \(a\), definida recursivamente a partir de la función sucesor \(s\):

$$a(0,y)=y$$

$$a(x+1,y)=s(a(x,y))$$

La primera ecuación afirma que sumar \(0\) a \(y\) devuelve \(y\). La segunda indica que sumar el sucesor de \(x\) equivale a aplicar el sucesor al resultado de sumar \(x\).

A partir de la suma podemos definir la multiplicación \(m\):

$$m(0,y)=0$$

$$m(x+1,y)=a(m(x,y),y)$$

Multiplicar \(x+1\) por \(y\) consiste en sumar \(y\) al resultado de multiplicar \(x\) por \(y\).

A lo largo de este artículo utilizaremos letras minúsculas como \(x\), \(y\), \(z\) y \(k\) para representar números naturales. Las letras \(f\), \(g\), \(h\), \(a\) o \(m\) designarán funciones numéricas cuando aparezcan aplicadas a argumentos.

Relaciones recursivas

Gödel utiliza también las llamadas relaciones recursivas, que poseen un peso fundamental en la demostración de los Teoremas de Incompletitud. Estas relaciones son propiedades o relaciones definidas sobre números naturales cuya verdad puede decidirse mediante un cálculo efectivo.

Una relación \(R\) de \(n\) argumentos es recursiva primitiva si existe una función recursiva primitiva \(r\) que actúa como su función característica. Siguiendo la convención utilizada por Gödel, podemos representar la verdad mediante \(0\):

$$R(x_{1},x_{2},\ldots,x_{n})\leftrightarrow r(x_{1},x_{2},\ldots,x_{n})=0$$

Cuando la relación no se cumple, la función devuelve un valor distinto de \(0\). Esta elección es una convención y no implica que el número \(0\) sea verdadero en un sentido lógico general.

Veamos un ejemplo de disyunción lógica codificada mediante una función numérica \(D\). Si \(0\) representa verdadero y \(1\) representa falso, definimos:

$$D(0,x)=D(x,0)=0$$

y:

$$D(x,y)=1\quad\text{si }x\neq0\text{ e }y\neq0$$

La disyunción es verdadera cuando al menos uno de sus argumentos representa una proposición verdadera.

La conjunción puede representarse mediante una función \(C\):

$$C(0,0)=0$$

y:

$$C(x,y)=1\quad\text{si }x\neq0\text{ o }y\neq0$$

Por definición, toda relación recursiva primitiva \(R(x_{1},x_{2},\ldots,x_{n})\) es decidible para cualquier combinación concreta de valores: existe un procedimiento que determina en un número finito de pasos si se cumple o no.

Minimización acotada

Una consecuencia de la decidibilidad de las relaciones recursivas primitivas es que podemos buscar el menor número que satisface una propiedad siempre que la búsqueda se encuentre limitada por una cota finita.

Dada una relación \(R(z)\) y un número \(j\), podemos comprobar sucesivamente:

$$R(0),R(1),R(2),\ldots,R(j)$$

La operación de minimización acotada devuelve el menor \(z\leq j\) para el que se cumple \(R(z)\). Si ningún número menor o igual que \(j\) satisface la propiedad, podemos asignar convencionalmente como resultado \(j+1\).

La cota es esencial. Una búsqueda sin límite podría continuar indefinidamente cuando no existiera ningún número que satisficiera la relación. La minimización no acotada no conserva, en general, el carácter recursivo primitivo ni garantiza que el cálculo termine.

La minimización acotada permite expresar aserciones como «existe un número \(z\) menor que \(j\) que cumple la propiedad \(S\)». Un ejemplo es la definición de número primo:

$$\operatorname{Primo}(x)\leftrightarrow x>1\land\neg\exists z\left[1<z<x\land z\mid x\right]$$

La expresión \(z\mid x\) significa que \(z\) divide a \(x\). Como solo es necesario comprobar los posibles divisores menores que \(x\), podemos decidir en un número finito de pasos si un número concreto es primo. La relación \(\operatorname{Primo}(x)\) es, por tanto, recursiva primitiva.

Gödelización

Vamos ahora con otro de los pilares de la demostración de los Teoremas de Incompletitud: la aritmetización de la sintaxis. A lo largo de esta serie hemos visto que un recurso común para resolver problemas metamatemáticos consiste en construir una representación numérica de los objetos de un sistema formal.

Una Tabla de Verdad ofrece una analogía elemental: transformamos los valores de verdad en \(0\) y \(1\) y representamos los conectores mediante operaciones definidas sobre esos números. Gödel lleva mucho más lejos esta idea y diseña un procedimiento mediante el cual cada símbolo, cada fórmula y cada demostración de un sistema formal queda asociado a un número natural.

Este procedimiento recibe el nombre de gödelización o numeración de Gödel. Su importancia no reside simplemente en sustituir fórmulas por números, sino en que las propiedades sintácticas de las fórmulas pueden traducirse en propiedades aritméticas de sus números correspondientes.

Factores primos

Vamos a explicar el mecanismo de gödelización o asignación a cada expresión de un número natural, conocido como Número de Gödel. Todo el proceso se apoya en el Teorema Fundamental de la Aritmética.

Este teorema afirma que todo número natural mayor que \(1\) es un número primo o puede expresarse como un producto de números primos de manera única, salvo por el orden de sus factores.

Así, por ejemplo:

$$17576=2^{3}\times13^{3}$$

No existe ninguna otra descomposición de \(17576\) en factores primos. De la misma manera:

$$2023=7\times17\times17=7^{1}\times17^{2}$$

La unicidad de la factorización permite codificar una secuencia finita de números dentro de un único número natural y recuperar posteriormente cada uno de sus componentes.

Número de Gödel

Comencemos asignando a cada símbolo básico un número natural diferente. En el sistema presentado por Gödel, basado en una versión de la teoría de tipos de los Principia Mathematica enriquecida con recursos aritméticos, algunos de los signos reciben los siguientes números:

$$0\Rightarrow1$$

$$s\Rightarrow3$$

$$\neg\Rightarrow5$$

$$\lor\Rightarrow7$$

$$\forall\Rightarrow9$$

$$(\Rightarrow11$$

$$)\Rightarrow13$$

Estos códigos no son necesariamente números primos. Son simplemente números diferentes asignados a los símbolos elementales.

Es necesario asignar también números a las variables. Gödel reserva para ellas potencias de números primos mayores que \(13\). A una variable de tipo \(n\) se le asigna un número de la forma:

$$p^{n}$$

donde \(p\) es un número primo mayor que \(13\). Así, una variable individual \(x\) podría recibir el número \(17\), mientras que una variable predicativa \(X\), perteneciente al tipo siguiente, podría recibir el número:

$$19^{2}=361$$

Logramos así asociar cada fórmula con una secuencia finita de números naturales. Por ejemplo, a la fórmula:

$$\forall x\left(X(x)\right)$$

le corresponde la secuencia:

$$9-17-11-361-11-17-13-13$$

Una vez obtenida la secuencia de códigos \(t_{1},t_{2},\ldots,t_{n}\), construimos su Número de Gödel mediante:

$$2^{t_{1}}\times3^{t_{2}}\times5^{t_{3}}\times\cdots\times p_{n}^{t_{n}}$$

donde \(p_{n}\) es el \(n\)-ésimo número primo. La posición de cada símbolo queda representada por la base prima correspondiente, mientras que su código aparece como exponente.

El Número de Gödel de la fórmula anterior sería:

$$2^{9}\times3^{17}\times5^{11}\times7^{361}\times11^{11}\times13^{17}\times17^{13}\times19^{13}$$

Se trata de un número inmenso, pero perfectamente determinado y exclusivo de esa secuencia de símbolos. Gracias a la unicidad de la factorización prima, dos secuencias diferentes no reciben el mismo número.

También podemos construir el Número de Gödel correspondiente a una demostración completa. Dado que toda demostración es una secuencia finita de fórmulas, si \(r_{1},r_{2},\ldots,r_{n}\) son los números de Gödel de sus fórmulas, podemos codificarla mediante:

$$2^{r_{1}}\times3^{r_{2}}\times5^{r_{3}}\times\cdots\times p_{n}^{r_{n}}$$

Conociendo el Número de Gödel de una demostración es posible, al menos en principio, factorizarlo, recuperar los números de cada una de sus fórmulas y reconstruir la secuencia completa.

Aritmetización de la Metamatemática

Hasta ahora hemos presentado dos recursos aparentemente independientes: las funciones recursivas primitivas y la gödelización. La demostración de los Teoremas de Incompletitud surge precisamente de su combinación.

La gödelización transforma los símbolos, las fórmulas y las demostraciones en números naturales. Las relaciones recursivas primitivas permiten definir propiedades decidibles de esos números. De esta manera, ciertas afirmaciones metamatemáticas acerca de un sistema formal pueden traducirse en afirmaciones puramente aritméticas.

Por ejemplo, podemos definir una relación:

$$\operatorname{Prf}_{P}(x,y)$$

que se interpreta como «\(x\) es el Número de Gödel de una demostración válida en el sistema \(P\) cuya última fórmula posee el Número de Gödel \(y\)».

La relación \(\operatorname{Prf}_{P}(x,y)\) es recursiva primitiva cuando los axiomas y las reglas del sistema pueden reconocerse efectivamente. Dado un número concreto \(x\), podemos descomponerlo, comprobar si codifica una secuencia de fórmulas y verificar, paso por paso, si cada fórmula es un axioma o se obtiene legítimamente a partir de las anteriores.

La afirmación de que la fórmula con Número de Gödel \(y\) es demostrable se expresa entonces mediante:

$$\operatorname{Prov}_{P}(y)\equiv\exists x\,\operatorname{Prf}_{P}(x,y)$$

Debemos distinguir ambas nociones. Comprobar si un número concreto \(x\) codifica una prueba concreta de \(y\) es una operación decidible. Determinar si existe algún número \(x\) que codifique una prueba de \(y\) exige buscar entre una cantidad ilimitada de posibles demostraciones y no es, en general, un problema decidible.

Gödel demuestra además que las relaciones recursivas primitivas relevantes pueden ser representadas mediante fórmulas del propio sistema aritmético. El sistema puede, por tanto, formular en su lenguaje propiedades que desde fuera interpretamos como afirmaciones acerca de sus propias expresiones y demostraciones.

Esquema de los Teoremas de Incompletitud de Gödel

Hemos expuesto una versión simplificada de la numeración utilizada por Gödel en el artículo donde presenta los Teoremas de Incompletitud. Existen muchos otros procedimientos posibles para codificar los símbolos y las fórmulas. Algunos utilizan un repertorio diferente de signos o sistemas de codificación más sencillos. La elección concreta no resulta esencial siempre que la codificación sea efectiva y unívoca.

Hasta ahora hemos presentado dos esquemas distintos: las funciones recursivas primitivas y la gödelización. En el próximo artículo veremos cómo Gödel los relaciona.

Las funciones recursivas primitivas nos permiten trabajar con relaciones aritméticas decidibles entre números naturales. La gödelización permite interpretar algunos de esos números como símbolos, fórmulas o demostraciones. Así, una relación aritmética como \(\operatorname{Prf}_{P}(x,y)\) puede interpretarse metamatemáticamente como «\(x\) es una demostración de la fórmula \(y\)».

El paso decisivo consistirá en construir, mediante un procedimiento de sustitución y autorreferencia, una sentencia que exprese dentro del propio sistema que ella misma no es demostrable. Bajo las condiciones de consistencia apropiadas, el sistema no podrá demostrar esa sentencia ni, en la formulación original de Gödel, su negación.

De esta manera, la aritmética deja de hablar únicamente de números y comienza a reflejar propiedades de sus propias fórmulas y demostraciones. Esta capacidad de representar la metamatemática dentro de la Aritmética será la clave de los Teoremas de Incompletitud.

Lecturas recomendadas

– Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.

– Gödel, K. (2006). Obras completas. Edición de Jesús Mosterín.