Kurt Gödel y la Metamatemática
David Baños Abril
Este artículo está dedicado al que es sin duda uno de los descubrimientos matemáticos más portentosos de todos los tiempos y la culminación a los intentos de una formalización de la Matemática desde los tiempos de Frege, lo cual ha sido el tema de esta serie. Los Teoremas de Incompletitud; sus implicaciones en la forma en que entendemos la Matemática y nuestra propia cognición resuenan todavía en la actualidad y han elevado a Gödel como una de las grandes mentes del siglo.
Kurt Gödel y los Teoremas de Incompletitud
Un todavía desconocido Kurt Gödel había dejado a la comunidad matemática asombrada cuando, a sus 23 años, pudo ofrecer una demostración de la completitud del Cálculo Lógico de Primer Orden, que, como habíamos indicado en el artículo previo, era una de las cuestiones irresueltas de la Lógica Matemática. Gödel conoció los dilemas entorno a la completitud y consistencia de los sistemas formales de la mano del propio Hilbert en una conferencia en Bolonia en 1928. Este temprano interés de Gödel le permitiría ofrecer el importante resultado que indicábamos antes.
Pero aún le quedaba mucho que ofrecer. Y es que, apenas dos años después, en 1930 Gödel publicaría los Teoremas de Incompletitud que le daría fama imperecedera y que son el tema de este artículo.
Nos fundamentaremos principalmente en el artículo mismo publicado por Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sobre proposiciones formalmente indecibles de los Principia Mathematica y sistemas afines).
El Programa Formalista
Metamatemática
Hilbert no consideraba que una aproximación intuitiva estuviese excluida a priori de la Matemática. Simplemente esta debía restringirse fuera de los sistemas formales que hemos comentado. Es decir, nuestra comprensión profunda de las entidades matemáticas (como es el número o la línea) es necesaria para asentar tales sistemas formales, por ejemplo, disponiendo sus cimientos, en forma de axiomas, y sus posibilidades expresivas haciendo uso de reglas de inferencia que nos permitan deducir los teoremas a partir de tales axiomas. Pero el objetivo es lograr un sistema totalmente autónomo. El papel del matemático quedaría relegado al de metamatemático, un observar externo que se limita a estudiar estos sistemas y sus propiedades como totalidades.
Dichas propiedades son principalmente dos: la consistencia -podemos probar que el sistema no demuestra dos sentencias que sean contradictorias- y la completitud -podemos demostrar que toda sentencia verdadera puede demostrarse en el sistema-.
Los Teoremas de Incompletitud de Gödel demostraría que este programa formalista es un sueño imposible.
Funciones Recursivas de Gödel
Antes de meternos de lleno en la demostración de los Teoremas de Incompletitud vamos a introducir una noción que el propio Gödel desarrolló en su artículo: la recursión. Esta noción era conocida previamente, pero el matemático austríaco le ofreció un fundamento formal.
Decimos que una función numérica f (cualquiera que mapee números naturales con números naturales) está recursivamente definida si:
para todo natural k y toda secuencia de números naturales x_{1}… x_{n}.
Una explicación intuitiva de esta definición nos dice que la resolución de una función f depende de un conjunto de n problemas anidados.
Podemos verlo con un ejemplo con el caso más sencillo: cuando n=1. Pongamos que es necesario resolver la función f(x) cuando x=4. Gödel nos dice que esta función estará recursivamente definida si, primero, podemos establecer un caso inicial:
y segundo, si podemos resolver la función para cualquier número natural retrocediendo al caso inicial mediante una función q anidada. En el caso de x=4 sería f(4) = q(3,q(2,q(1,q(0,h)))), dado que:
La recursión como vemos, es un esquema de definición.
Funciones recursivas primitivas
Gödel introduce a partir de esta noción la de recursión primitiva. Una función es recursiva primitiva si las funciones que la definen (h y q del esquema previo), así como aquellas que definan a estas también, o bien son también funciones recursivas (o bien constantes o instancias de otra función), formando así una cadena finita de funciones que se definen sucesivamente. Con mayor perspectiva, podemos decir que las funciones recursivas primitivas son aquellas que son siempre resolubles. Podemos decidir y calcular su valor de forma efectiva para cualquier combinación de argumentos en un número finito de pasos, pues siempre dispondremos de un caso inicial sobre el que volver. En los lenguajes de programación modernos son equivalentes a los bucles for.
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 ser expresadas en forma de funciones recursivas primitivas y, gracias ello, resolverse en un número finito de pasos simplemente reduciendo el problema a un caso inicial que, dado que se recorre el dominio de los números naturales, será cuando la variable valga 0.
Veamos por ejemplo la función suma a definida de forma recursiva a partir de la función sucesora s.
Y a partir de esta la multiplicación M :
A lo largo de este artículo, toda variable que sea una letra minúscula o bien es una función numérica o representa un número natural 0, 1, 2, 3…
Relaciones recursivas
Gödel también define las llamadas relaciones recursivas, las cuales, aunque no directamente relacionadas, tienen un peso fundamental en la demostración de los Teoremas de Incompletitud. Las relaciones recursivas son similares a lo que usualmente hemos llamado propiedades. Eso sí, estas se definen exclusivamente para números naturales y dependen de funciones recursivas. R es una propiedad de n números naturales si existe una función recursiva f que resuelva con el valor 0:
A diferencia de lo usual en otros artículos de esta serie, aquí 0 funciona como el valor de verdad verdadero por ser el caso inicial.
Veamos un ejemplo de la disyunción lógica definida de forma recursiva:
D(x,y) = 1 si x≠0 y y≠0
o la conjunción:
C(x,y) = 1 si x≠0 o y≠0
Por definición, toda propiedad recursiva R(x_{1}, x_{2}… x_{n}) es decidible para cualquier combinación de valores x_{1}, x_{2}… x_{n}.
Minimización
Una de las consecuencias de la decibilidad inherente a las propiedades recursivas es que, dado que podemos chequear uno a uno si dicha propiedad se cumple o no para una variable x hasta llegar a x = 0, es posible determinar en un número finito de pasos el mínimo número para el que la propiedad recursiva se cumple (tal número sería 0 si no se cumpliese en ningún caso).
Esto hace posible definiciones que involucren aserciones de existencia, es decir, expresiones del tipo «existe un número x menor que j y que cumple una propiedad S«. Un ejemplo es la definición de número primo:
todas la funciones que integran esta definición son recursivas y lo es por tanto la propia definición de número primo: nos aseguramos que podemos decidir si x es un número primo en un número finito de pasos.
Gödelización
Vamos ahora con otro de los pilares de la demostración de los Teoremas de Incompletitud de Gödel que, por el momento, no tiene nada que ver con funciones recursivas. A lo largo de esta serie hemos visto que un recurso común para la resolución de problemas metamatemáticos es la aritmetización, esto es, construir un sistema numérico que refleje ciertas propiedades del sistema formal en cuestión. El caso más simple es el de la Tabla de Verdad: transformando las variables proposicionales en valores de verdad 0s y 1s y resolviendo los conectores como operadores aritméticos podemos decidir el valor de verdad de la sentencia al completo.
Pues bien, Gödel lleva un paso más allá este ejercicio y diseña un sistema a partir del cual cada símbolo de una fórmula está asociado con un número natural. No solo símbolos sino también toda fórmula está vinculada a un único número natural. Tal ejercicio es conocido como gödelización.
Factores primos
Vamos explicar ahora el mecanismo de gödelización o asignación a cada fórmula de un número natural (conocido como Número de Gödel). Todo este proceso gira entorno al llamado Teorema Fundamental de la Aritmética, demostrado por Gauss hace ya más de 200 años. El teorema en cuestión afirma que todo número natural mayor que 1 o bien es un número primo (solo divisible por 1 o por sí mismo) o bien es un único producto de números primos. Así, por ejemplo, el producto de primos 2^{3}×13^{3} es la factorización de 17576. No existe ninguna otra factorización para ese número. De la misma manera, un número como 2023 tiene una única descomposición en factores primos: 7× 17× 17 = 7^{1}× 17^{2}.
Número de Gödel
Comencemos asignando a los símbolos su correspondiente número primo. Son los símbolos del sistema formal que propone Gödel y que nace de la combinación entre los Principia Mathematica de Russell y Whitehead y los Axiomas de Peano para los números naturales:
Es necesario asignar también un número a las variables: a cada variable de orden n se le asigna el número p^{n} siendo p un primo a partir de 17. Logramos así asociar cada fórmula con una secuencia de números naturales. Por ejemplo, a la fórmula
le corresponde la secuencia:
El Número de Gödel se obtiene transformando toda cadena de símbolos τ_{1},τ_{2},τ_{3}…τ_{n} en una serie tal que 2_{1}^{t_{1}}×3_{2}^{t_{2}}×5_{3}^{t_{3}}…p_{k}^{t_{n}}, siendo p_{k} un número primo en orden de menor a mayor, y t_{n} el número asociado a cada símbolo τ_{n}.
Así, el Número de Gödel de la fórmula previa sería:
un número inmenso pero un número totalmente unívoco que es lo que nos interesa.
Cada demostración de una fórmula es posible también construir su correspondiente Número de Gödel. Dado que toda demostración no es más que una cadena de fórmulas, podemos aplicar el mismo esquema anterior y construir su Número de Gödel como 2_{1}^{r_{1}}×3_{2}^{r_{2}}×5_{3}^{r_{3}}…p_{k}^{r_{n}} siendo r_{n} el Número de Gödel de cada fórmula. Por la propiedad de los números primos comentada con anterioridad, conociendo el Número de Gödel de una demostración es perfectamente posible factorizarlo y descubrir las fórmulas que lo comprenden.
Esquema de los Teoremas de Incompletitud de Gödel
Aquí hemos expuesto la numeración tal y como aparece en el artículo original del propio Gödel en los que anuncia los Teoremas de Incompletitud. Pero existen otro tipo de procedimientos debidos a otros autores que, por ejemplo, incluyen un número mayor de símbolos. La lógica bajo todos ellos es parecida.
Hasta ahora hemos presentado dos esquemas completamente distintos y sin aparente relación: las funciones recursivas primitivas y la gödelización. Vamos a presentar esquemáticamente cual será el recorrido del próximo artículo en el que expondremos los teoremas.
Primero las funciones recursivas primitivas nos permitirán trabajar con relaciones puramente aritméticas entre números. Pero buscaremos que estas relaciones realmente puedan ser interpretadas como relaciones lógicas. Así, por ejemplo, afirmaciones metamatemáticas acerca del sistema como «A es demostrable por X» serán posibles gracias a su representación como relaciones aritméticas entre el Número de Gödel de A y el Número de Gödel de X. Trabajando con funciones recursivas primitivas lograremos construir un teorema del sistema que, siendo cierto, no puede ser demostrado en el, probando así su incompletitud.
Lecturas Recomendadas
– Gödel, K. (2006) Obras completas. Edición de Jesús Mosterín.
