Breve introducción a los teoremas de Gödel

 

En 1930 tenía lugar en Könisberg, la ciudad natal de Immanuel Kant, la segunda Conferencia Sobre la Epistemología de las Ciencias Exactas. Entre los conferencistas se encontraban figuras destacadas del ámbito de la lógica, la ciencia y la filosofía, tales como Rudolf Carnap, Arend Heyting, Werner Heisenberg, Hans Reichenbach, y John von Neumann.

Pero posiblemente la charla más destacada del evento, por su impacto y originalidad, la dio un casi desconocido joven austríaco de 24 años, Kurt Gödel. En ella demostró la completitud de la lógica de primer orden.

Voy a explicar estos conceptos con detalle más adelante, pero por ahora basta con decir que este resultado, por sí solo, ya hubiese bastado para que el nombre de Gödel quede inmortalizado en la historia de la lógica y las matemáticas.

Pero el joven Gödel no se detuvo ahí. En la misma charla mencionó, de forma casual y casi “de pasada”, que este resultado no se aplicaría al tipo de lógica necesario para representar la aritmética elemental. Se dice que, al terminar la charla, von Neumann encaró inmediatamente a Gödel para que le elaborara más sobre este punto, y mantuvieron correspondencia después de eso (von Plato, 2021).

Se trata del famoso teorema de incompletitud de Gödel que, junto con su corolario, el usualmente llamado “segundo teorema de Gödel”, constituyen uno de los descubrimientos más fascinantes del pensamiento humano.

Intentaré explicar estos resultados de una forma que no presupone conocimientos especializados pero evitando, al mismo tiempo, sacrificar los detalles importantes.

A pesar de eso, debo advertir que el escrito demanda cierto grado de esfuerzo de parte del lector, pues el tópico tiene una dificultad inherente que no se puede deshacer sin pérdida de información.

Sin embargo, aquellos que deseen solo tener un primer acercamiento preliminar de nivel más general también podrán sacar provecho del artículo. A estos lectores recomiendo leer todo el contenido que va desde la siguiente sección hasta el apartado “Demostración detallada”, y luego saltar directamente hasta la sección “Observaciones finales”.

El sueño de Leibniz, o la characteristica universalis

Imaginemos que existe un lenguaje capaz de expresar de forma precisa, es decir, sin ambigüedades, todas las ideas concebibles por el ser humano. Además, existen unas cuantas ideas fundamentales que todos aceptarían como obviamente verdaderas. Por último, digamos que existe un cálculo que nos permite construir de forma mecánica, a partir de estas ideas fundamentales, todas las verdades acerca de cualquier tema.

Dejando de lado detalles, esta suerte de cálculo del pensamiento era más o menos lo que tenía en mente Leibniz en su escrito El arte del descubrimiento en 1685 (Wiener, 1982), cuando escribe lo siguiente:

Leibniz bautizó a este lenguaje imaginario como characteristica universalis.

Los lógicos modernos, desde el siglo XIX, empezaron a construir lenguajes artificiales similares a la characteristica universalis de Leibniz, los llamados lenguajes formales.

Para aclarar la relación entre la lógica, una ciencia formal, y los lenguajes formales, recordemos que la lógica estudia las leyes del razonamiento válido. Básicamente, los lenguajes formales son útiles para el estudio de la lógica porque cada uno modela, de forma precisa, una noción específica de validez.

Por ejemplo, la lógica proposicional es un sistema formal que define la relación de validez para el caso en el que razonamos con oraciones, sin tener en cuenta la conexión lógica que hay entre el sujeto y el predicado que componen dichas oraciones. Cuando sí tenemos en cuenta dicha relación, utilizamos otro lenguaje formal más potente, la lógica de primer orden. Cuando razonamos con palabras como “necesario” y “contingente”, podemos usar lógica modal.

En síntesis, los lenguajes formales nos ayudan a entender, de forma precisa, qué significa que un razonamiento lógico sea válido o inválido, y por eso son útiles para la lógica como disciplina. El lector interesado puede profundizar más sobre el tema aquí.

Algunas definiciones

Agreguemos un poco de terminología técnica. Llamaremos axiomas a las oraciones que representan las mencionadas ideas fundamentales. Las reglas del cálculo son reglas de inferencia. Los símbolos básicos del lenguaje son su vocabulario. Finalmente, las oraciones del lenguaje generadas a partir de la aplicación de las reglas de inferencia a los axiomas son los teoremas.

Además, diremos que una prueba o demostración es una serie finita de oraciones del lenguaje en la que cada oración de la serie es o bien un axioma o un teorema. Una demostración de la oración A en el lenguaje es simplemente una serie finita de oraciones como la anteriormente descrita, en donde la última oración de la serie es A.

Si es cierto que, para toda oración A del lenguaje, o bien A o su negación (o sea, no-A) tiene una demostración en el lenguaje, decimos que el lenguaje es decidible.

Si toda oración verdadera del lenguaje es también demostrable en él (o sea, podemos construir una prueba de ella), entonces el lenguaje es completo.

Si toda oración demostrable en el lenguaje es también verdadera, decimos que el lenguaje es sólido (sound en inglés).

Los fundamentos de las matemáticas y la escuela logicista

Digamos ahora que existe un lenguaje formal cuyo vocabulario se compone de conceptos lógicos simples e intuitivos, y tiene un pequeño número de axiomas lógicos y reglas de inferencia. Cuando hablo de conceptos lógicos, me refiero a conceptos como el de negación, disyunción, conjunción, predicado, etc. Cuando hablo de axiomas “lógicos”, me refiero a afirmaciones compuestas exclusivamente de conceptos lógicos y cuya verdad es analítica, es decir, que no depende de hechos contingentes. Por ejemplo, el principio de no contradicción podría considerarse como un principio lógico, pero la ley de los gases nobles no. Al menos esto era lo que tenían en mente ciertos lógicos de la época, aunque hoy la situación sea algo más compleja.

El lenguaje que acabamos de describir es un modelo del razonamiento en el sentido de que todas las formas de razonamiento que intuitivamente consideraríamos como correctas son también correctas en él. Se podría decir que representa una lógica específica que caería dentro de lo que comúnmente se conoce como lógica clásica.

Por último, proponemos la siguiente hipótesis:

Es fácil ver que esta afirmación presupone que el lenguaje es completo, en el sentido técnico que he definido más arriba: para toda afirmación matemática sería posible, en este lenguaje, demostrarla o refutarla a partir de sus axiomas y reglas de inferencia, que es exactamente la definición de completitud.

Russell y Whitehead, en su obra Principia Mathematica, siguiendo los pasos de Gottlob Frege,  intentaron llevar a cabo este monumental proyecto mostrando, a lo largo de tres largos volúmenes, cómo grandes porciones de las matemáticas podían ser derivadas a partir de un sistema formal similar al propuesto más arriba.

La meta final era epistemológica. Intentaban responder a la pregunta: ¿Cómo podemos tener certeza acerca de las matemáticas? Si la totalidad de las matemáticas pudiese reducirse a unos cuantos conceptos y axiomas lógicos simples sobre los cuáles tenemos absoluta entonces, por añadidura, también tendríamos certeza de que las matemáticas son verdaderas. A este programa de investigación se le conoce dentro de la filosofía de las matemáticas como logicismo, y puede representarse más generalmente como la idea de que las matemáticas son reducibles a la lógica.

Los resultados de Gödel

Esencialmente, Gödel demostró que el proyecto logicista (al menos bajo la forma anteriormente descrita) no es lograble: para todo lenguaje formal lo suficientemente expresivo como para representar los conceptos de la aritmética básica, existen oraciones que son verdaderas pero indecidibles, siempre y cuando el lenguaje sea consistente.

Esto implica que ciertas oraciones del lenguaje son verdaderas, pero no demostrables dentro del lenguaje. Obviamente, un sistema formal como este no sería completo. Esto es lo que se quiere significar cuando se dice que Gödel mostró que el lenguaje de la aritmética es incompleto, y de ahí viene el mote de “teorema de incompletitud” para referirse a este resultado.

Como corolario, el segundo teorema afirma que tal sistema no es capaz de demostrar su propia consistencia (en otras palabras, la oración que afirma “este sistema es consistente” no es demostrable dentro del sistema).

Demostración de los teoremas: primer acercamiento

En esta sección, voy a explicar de manera informal (sin fórmulas) y muy simplificada la estrategia de Gödel para demostrar sus teoremas, de forma que el lector se haga una idea intuitiva de la misma. Espero que esto facilite la comprensión de la demostración más detallada que daré en la siguiente sección.

A grandes rasgos, la prueba del teorema de incompletitud de Gödel es muy sencilla. Básicamente, Gödel muestra que es posible construir, en un lenguaje formal con ciertas características, una oración G. Esta oración afirma, acerca de sí misma, que no es demostrable. Podemos expresar esto de la siguiente forma:

Entonces, si G fuese demostrable, sería verdadera. Es decir, sería verdad que G no es demostrable. Pero si G es demostrable y no demostrable al mismo tiempo, esto es una contradicción lógica. Entonces, G no puede ser demostrable.

Por otra parte, supongamos que G es refutable, es decir, su negación no-G es demostrable. Se sigue que no-G sería verdadera. Pero entonces sería verdad que G es demostrable. Nuevamente, tendríamos que G es demostrable y no es demostrable al mismo tiempo, lo cual es una contradicción lógica. Entonces, G no puede ser refutable.

Por lo tanto, la oración G es indecidible en el lenguaje formal en cuestión, o sea, no es demostrable ni refutable. Sin embargo, esto significa que lo que afirma G, “G no es demostrable”, es verdadero. Por lo tanto, tenemos una oración que no es decidible pero es verdadera. Como vimos anteriormente, esto implica que el sistema formal es incompleto.

Como corolario, tenemos el segundo teorema. Para comprender su demostración, es necesario introducir una regla de inferencia, el modus ponens. Según la misma, son válidos todos los razonamientos que tengan la siguiente forma:

P y Q son oraciones de nuestro lenguaje formal. Esta es una forma de razonamiento que utilizamos en nuestra vida cotidiana sin darnos cuenta y que, en principio, todos aceptaríamos sin controversia. Por ejemplo, el siguiente razonamiento tiene la forma de un modus ponens, y por lo tanto es válido: 

Volvamos ahora al segundo teorema. Como hemos visto en la prueba del primer teorema de incompletitud, el hecho de que un sistema formal con ciertas características sea consistente (o sea, que no tenga contradicciones lógicas) implica que G no es demostrable en el mismo pues, como mencionamos, la demostrabilidad de G lleva a una contradicción.

Ahora bien, afirmar “G no es demostrable” es lo mismo que afirmar G: recordemos que G es una oración que “afirma”, acerca de sí misma, que no es demostrable. Por lo tanto, tenemos que: si el sistema formal es consistente, entonces G.

Volvamos ahora al modus ponens, y reemplacemos P por la oración “El sistema formal es consistente”, y Q por la oración G.

También pongamos el siguiente supuesto: se puede demostrar que el sistema formal es consistente. Entonces, el modus ponens quedaría así:

Esto, por si el lector no se hubiera dado cuenta, es una demostración lógica de G. Por lo tanto:

Esto obviamente contradice al primer teorema que, recordemos, decía que G no es demostrable ni refutable, es indecidible. Por lo tanto, la consistencia del sistema formal no es demostrable dentro del sistema formal mismo, y con esto concluye la prueba del segundo teorema.

Demostración detallada

La prueba original de Gödel, presentada en su artículo Sobre proposiciones formalmente indecidibles de Principia Mathematica (1931) es compleja e introduce varias técnicas en ese entonces novedosas y revolucionarias.

Entonces, empezaré por describir estas técnicas, así como algunos conceptos previos que serán de utilidad.

Sistema formal P

En su artículo, Gödel define un sistema formal P. Según Gödel, “P es esencialmente el sistema que se obtiene al superponer en los axiomas de Peano la lógica de PM”.

“PM” se refiere al sistema formal elaborado por Russell y Whitehead en su ya mencionada obra Principia Mathematica.

Los axiomas de Peano son un conjunto de axiomas propuestos por el matemático italiano Giuseppe Peano en el siglo XIX con la pretensión de derivar, a partir de ellos, todos los teoremas de la aritmética con números naturales. Al conjunto compuesto por los axiomas de Peano y todos sus teoremas se le llama a veces aritmética de Peano. Entonces, el sistema P es aquella parte del sistema de PM que trata acerca de los números naturales.

En lo que sigue, voy a describir una versión del sistema P usando una notación más moderna.

El vocabulario de P se compone de:

1. Conectivas lógicas: “~” (no),  “∨” (o), “∀” (para todo), “0” (cero), “f” (el sucesor de), “(“, “)” (paréntesis)
2. Símbolos de orden n, en donde n es un número natural mayor a cero.
   1. A los símbolos de orden 1, los llamaremos “variables de individuo”, y los representaremos con las letras x, y, z,…
   2. A los símbolos de orden n > 1 los llamaremos “predicados”, y los representaremos con las letras F_n,G_n,…

Entonces, un símbolo de orden 2, es un predicado que se aplica a variables de individuo. Un símbolo de orden 3 es un predicado que se aplica a un predicado de orden 2. Y así sucesivamente, en órden jerárquico. Para simplificar, si un predicado aparece sin su subíndice, se asume que es de orden 2, es decir, que se aplica a variables de individuo.

Se ve que cualquier número natural puede ser representado mediante la sucesiva aplicación del operador de sucesión f, siempre y cuando todo número tenga un sucesor, cosa que está garantizada por los axiomas de Peano. Por ejemplo, el número dos se podría representar como f(f(0)) (o sea, “el sucesor del sucesor de 0”).

Para abreviar, simbolizamos con las letras a, b, c, d, etc., a un número natural cualquiera resultante de aplicar n veces el operador f a 0. Gödel llama a estos símbolos signos-número.

A las fórmulas gramaticalmente correctas de P las llamamos fórmulas bien formadas. Algunos ejemplos:

• ~F(a) (se lee: “el número a no tiene la propiedad F”)
• ~∃x(F(x)) (se lee: “no existe un número que tenga la propiedad F”)
• ∀x(F(x) → (G(x) ∨ H(x))) (se lee: “Todos los números que tienen la propiedad F también tienen la propiedad G o la propiedad H”)

Los axiomas de P consisten en:

• Los axiomas de Peano
• Cualquier fórmula generada a partir de unos schemata. Los schemata son como “recetas” para generar axiomas. En concreto, son expresiones en la que las fórmulas de P aparecen como variables. Entonces, son axiomas de P todas las fórmulas resultantes de reemplazar dichas variables por fórmulas de P.

Para propósitos de este artículo, no viene al caso ahondar en más detalles, pues simplemente quiero dar al lector una idea muy general del tipo de lenguaje del que estamos hablando. Sin embargo, refiero al lector curioso a la primera parte de la sección 2 del artículo original.

Aritmetización

Una parte importante de la estrategia de Gödel para probar sus teoremas se basa, como ya hemos señalado en la sección anterior, en construir una oración que “dice” acerca de sí misma que no es demostrable en P. En otras palabras, es una oración que se refiere a sí misma.

Esta autorreferencia se logra mediante el método de aritmetización:

Gödel encuentra un algoritmo o método efectivo por el cual podemos tomar cualquier fórmula arbitraria A de P y convertirla en un número natural, que a veces se conoce como el número de Gödel de la fórmula.

Para una fórmula cualquiera A del lenguaje P, simbolizamos su número de Gödel como |A|.
Como vimos, todas las oraciones de P se pueden interpretar como oraciones que hablan acerca de números naturales. Entonces, se tiene que: si hemos codificado las fórmulas de P como números naturales, P tiene la capacidad de “hablar” acerca de sus propias fórmulas. Basta con que P haga una afirmación acerca del número de Gödel correspondiente a una de sus fórmulas.

Por ejemplo:

F(|A|), que se lee “La fórmula de P cuyo número de Gödel es |A| posee la propiedad F”.

Es fácil ver que F(|A|) es una oración del lenguaje P que afirma un hecho acerca de otra oración A del lenguaje P: que A posee la propiedad F.

Gödel logró esto de la siguiente forma:

Primero, definimos que a cada símbolo del vocabulario base de P le corresponde un número natural primo:

0	1
f	3
~	5
∨	7
∀	9
(	11
)	13

 

A los símbolos de orden n (variables y predicados) les corresponden números p_kⁿ, en donde p_k es el k-ésimo número primo mayor a 13.

El procedimiento para obtener el número de Gödel de una fórmula es como sigue:

1. Establecemos una correspondencia de uno a uno entre la serie de signos del vocabulario básico de P que componen la fórmula, y una serie de números naturales, según las reglas anteriormente descritas. En el caso de la fórmula ∀xF(x), por ejemplo, esto da como resultado la serie:

[9,17,169,11,17,13]

1. Calculamos la multiplicación 2^n₁ * 3^n₂,…p_k^n_k, en donde el exponente n_k es el k-ésimo número de la serie obtenida en el primer paso, y la base p_k es el k-ésimo número primo. En nuestro caso:

2⁹ * 3¹⁷  * 5¹⁶⁹ * 7¹¹ * 11¹⁷ * 13¹³ = |∀xF(x)|

Este número es extremadamente grande, pero lo importante es que es único, es decir, no hay otra fórmula cuyo número de Gödel sea el mismo.

El proceso opuesto de encontrar la fórmula correspondiente a un número de Gödel dado es muy simple de ejecutar, pues solo debemos descomponerlo en sus factores primos. De hecho, según el teorema fundamental de la aritmética, todo número natural es primo o equivalente a un producto de números primos. En este sentido, los números primos son como los “átomos” de los números naturales.

La idea de relacionar a los “átomos” del lenguaje P (su vocabulario base) con los “átomos” de los números naturales (los números primos) es muy ingeniosa, y es esencial para entender por qué la numeración de Gödel funciona.

Por último, debemos decir que la aritmetización también afecta a las propiedades y las relaciones entre fórmulas en P:

• A cada propiedad F en P satisfecha por una fórmula A le corresponde una propiedad aritmética satisfecha por el número |A|
• A cada relación R en P entre n fórmulas A₁, A₂, …A_n, le corresponde una relación aritmética entre los números de Gödel |A₁|, |A₂|,…|A_n|

Por ejemplo, la función matemática Neg(n) toma el número de Gödel n de una fórmula y devuelve el número de Gödel correspondiente a la negación de la misma. De esta forma, la operación lógica de negación tiene su equivalente en la función aritmética Neg.

Resumen: lo clave de esta sección es entender que cada fórmula de P puede representarse con un número natural único, su número de Gödel, y cada propiedad y relación entre fórmulas de P puede representarse con una función aritmética entre números de Gödel. Esto permite construir, en P, oraciones acerca de sus fórmulas (autorreferencia).

Funciones recursivas y representabilidad

Después de explicar el método de aritmetización, Gödel introduce el concepto de función recursiva.

 Dicho de manera informal e intuitiva, una función recursiva es una función matemática cuyo valor se puede determinar por la sucesiva aplicación de la misma función para argumentos más pequeños.

La función fact(n), que calcula el factorial de un número n, es un típico ejemplo de función recursiva. La misma se define como aquella función tal que, cuando n = 0, entonces: 

fact(0) = 1

Y cuando n > 0:

fact(n) = n * fact(n-1)

Entonces, podemos calcular mecánicamente el valor de la función fact para cualquier número natural en un número finito de pasos. Por ejemplo, para el caso de fact(3):

De hecho, las funciones recursivas modelan matemáticamente el concepto de computación, que a su vez se entiende, intuitivamente, como la acción y efecto de llegar a la solución de un problema mediante un método mecánico.

Ahora supongamos que tenemos una relación recursiva R. Gödel, en la Proposición V de su artículo, afirma que:

• Si es cierto que esta relación tiene lugar entre los números x₁,x₂,…x_n, entonces esta relación se puede expresar en P por una fórmula A que es demostrable en P.
• De lo contrario, esta relación se puede expresar en P por la negación de A, que es demostrable en P.

A esta propiedad se la llama, en textos modernos, representabilidad fuerte (Raatikainen, 2022).

La relación de prueba es recursiva y, por ende, fuertemente representable (Raatikainen, 2022). Podemos denotarla como Pr(n,|A|), que se lee “n es el número de Gödel de una prueba/demostración de la fórmula representada por el número de Gödel |A|”.

Para llevar a cabo la demostración del teorema de incompletitud, Gödel realmente solo necesita de un requisito más liviano, la representabilidad débil (Raatikainen, 2022):

• R tiene lugar entre los números x₁,x₂,…x_n si, y solo si, R se puede expresar en P por una fórmula A que es demostrable en P

En particular, tomemos la relación P⊢A (se lee “la fórmula A es demostrable en P”). Entonces, por representabilidad débil, existe una relación de demostrabilidad, que vamos a denotar por Dem_p(|A|), que es demostrable en P si, y solo si, P⊢A (y viceversa, es refutable en P si, y solo si, P⊢no-A). En símbolos:

P⊢A ↔ P⊢Dem_p(|A|) 

Se lee: “La fórmula A es demostrable en P si, y solo si, la fórmula Dem_p(|A|) es demostrable en P”

Entonces, al afirmar Dem_p(|A|), estamos diciendo que la fórmula correspondiente al número de Gödel |A| es demostrable en P. O sea, que existe una prueba de A.

Resumen:

• Gödel introduce el concepto de funciones recursivas porque estas tienen la propiedad de la representabilidad.
• Esto, a su vez, le permite representar la idea de “demostrabilidad en P” dentro del lenguaje P mismo.
• En otras palabras el lenguaje P tiene la capacidad de “decir”, acerca de cualquiera de sus fórmulas, que es demostrable en P.
• Esto, como veremos, juega un papel muy importante en su prueba.

Omega-consistencia

Aunque en muchos textos de divulgación se afirma que una de las condiciones para que el teorema de incompletitud de Gödel se aplique a un sistema formal determinado es que este debe ser consistente, en realidad esta es una imprecisión, al menos si estamos hablando del artículo original de 1931.

Gödel no pudo demostrar su teorema para el caso de la consistencia simple. En su lugar, utilizó otro concepto más fuerte, el de omega-consistencia. Fue John Barkley Rosser quien, en 1936, logró elaborar una versión del teorema de incompletitud asumiendo solo consistencia simple.

Veamos la diferencia.

Consistencia simple: tomemos una fórmula cualquiera de nuestro sistema formal P. El sistema es consistente si no es posible demostrar, dentro del sistema, tanto la fórmula como su negación.

Omega-consistencia: nuestro sistema formal P es omega-consistente si no ocurre, al mismo tiempo, que:

• Para cualquier número natural, es posible demostrar que el número en cuestión no tiene la propiedad F
• Existe un número natural que tiene la propiedad F

La omega-consistencia implica consistencia simple pero no viceversa, lo cual significa que un sistema podría ser consistente sin ser omega-consistente.

Primer teorema

Gödel, logra construir una oración G tal que se cumple lo siguiente:

P⊢G↔~Dem_p(|G|)

Se lee: “G es demostrable en P si, y solo si, la oración cuyo número de Gödel es |G| no es demostrable en P”

Intuitivamente podríamos decir que G es una oración que “afirma” acerca de sí misma, que no es demostrable en P, pues la oración cuyo número de Gödel es |G| no es otra que G misma. Esto es posible porque, como vimos, la técnica de aritmetización permite que el lenguaje P pueda realizar afirmaciones acerca de sus propias fórmulas, una forma de autorreferencia.

El filósofo Rudolf Carnap generalizó este resultado y mostró que, en toda teoría que cumpla ciertas condiciones, es posible construir una oración que afirma, acerca de sí misma, que tiene una propiedad F. A este resultado se le conoce a veces como el lema de diagonalización (Picollo, 2018).

Gödel muestra que G es indecidible en P, de la siguiente forma:

Demostración del primer teorema – primera sección

Supongamos que G es demostrable en P.

Gödel muestra que, si G es demostrable, también lo es su negación, lo cual es una contradicción. Por lo tanto, G no puede demostrarse.

Para entender esto, recordemos que el predicado Dem_p es débilmente representable en P. Entonces, tenemos que:

P⊢G ↔ P⊢Dem_p(|G|)

En otras palabras, si G es demostrable en P, entonces también lo es Dem_p(|G|).

Sin embargo, más arriba dijimos que P⊢G↔~Dem_p(|G|). Por lo tanto, si Dem_p(|G|) es demostrable, de ahí se sigue que ~G.

Esto es fácil de mostrar, pero requiere cierto conocimiento previo.

La oración G ↔ ~Dem_p(|G|), en lógica, es equivalente a:

(G → ~Dem_p(|G|)) y (~Dem_p(|G|) → G).

Obs.: el símbolo “y” (conjunción) no forma parte de P, pero puede ser definido a partir de los demás símbolos del lenguaje.

De ahí, se puede deducir G → ~Dem_p(|G|), por una regla de inferencia, la simplificación de la conjunción. Entonces, por aplicación directa del modus ponens (que ya conocemos):

Si ~Dem_p(|G|), entonces G

Dem_p(|G|)

Por lo tanto, ~G

En resumidas cuentas, si G es demostrable, también lo es su negación ~G, lo que significa que P es inconsistente. Por lo tanto, G no es demostrable en P.

Demostración del primer teorema – segunda sección

Supongamos que G es refutable en P, o sea, que ~G (la negación de G) es demostrable en P

En esta parte de la prueba juega un papel clave el concepto de omega-consistencia:

• Postulemos que ~G es demostrable en P
• Entonces, obviamente G no es demostrable en P, pues esto sería una contradicción. Esto significa que no existe un número natural n que sea el número de Gödel correspondiente a una prueba de G. Como la relación de prueba Pr es fuertemente representable en P, entonces podemos demostrar que ~Pr(n,|G|), para cualquier número natural n, es decir, podemos demostrar que no existe una prueba de G.
• Ahora bien, ya sabemos que G↔~Dem_p(|G|). Por lo tanto, si ~G es demostrable (como postulamos al comienzo), entonces tendríamos Dem_p(|G|).
• Dem_p(|G|) se puede definir como ∃xPr(x,|G|), que se lee “Existe un número x tal que x es el número de Gödel de una prueba de G”.Entonces, si G es demostrable en P:

• ~Pr(n,|G|): “para cualquier número natural n, n no es una prueba de G”

• ∃xPr(x,|G|): “existe una prueba de G”

• Esto no significa que P sea inconsistente, pues este resultado no es una contradicción lógica (no estamos demostrando una oración y su negación). Sin embargo, sí implica que P es omega-inconsistente. Como expliqué en la sección anterior, un sistema formal P es omega-inconsistente si se cumplen las siguientes condiciones:
  • Para cualquier número natural, es posible demostrar que el número en cuestión no tiene la propiedad F. En nuestro caso, F es la propiedad de ser una prueba de G, y ya hemos mostrado que esta condición claramente se cumple.
  • Existe un número natural que tiene la propiedad F. Como vimos más arriba, esta condición también se cumple.

• Por lo tanto, si no-G es demostrable en P, P es omega-inconsistente.

Resumiendo, en el lenguaje P es posible construir una oración G tal que se cumple lo siguiente (Raatikainen, 2022):

• Si P es consistente, entonces P no es demostrable
• Si P es omega-consistente, P no es refutable

Dicho de otra forma, G es indecidible en P, y con esto concluye la prueba del primer teorema.

Gödel mostró que este resultado no se aplica solo al lenguaje P. En realidad, es posible construir una fórmula indecidible como G en cualquier lenguaje L que satisfaga estas dos condiciones:

• Podemos definir funciones recursivas en L, pues así aparece la propiedad de representabilidad, que es necesaria para la sección (a) de la prueba. En realidad, lo más preciso sería decir que el lenguaje debe ser recursivamente axiomatizable, pero en esencia esta forma de expresarse es lo suficientemente correcta, sobre todo para los propósitos de este artículo.
• L es omega-consistente, que es necesaria para la sección (b) de la prueba.

Entonces, para finalizar esta sección, podríamos expresar el teorema de incompletitud de Gödel de la siguiente forma:

En todo sistema formal omega-consistente capaz de expresar funciones recursivas, es posible construir una fórmula indecidible G dentro del sistema

Además, la oración indecidible G es verdadera. Recordemos que G es una oración que “dice” de sí misma que no es demostrable. Entonces, si fuese falsa, sería demostrable, lo cual contradice el teorema de Gödel. Como escribe el propio Gödel:

A partir de la observación de que [R(q); q] afirma su propia indemostrabilidad, se sigue inmediatamente que [R(q); q] es correcta, pues [R(q); q] es ciertamente indemostrable (por ser indecidible)

Por lo tanto, todo lenguaje formal al que se aplique el teorema de Gödel es incompleto, pues tendría oraciones verdaderas pero no demostrables. En particular, se sigue que la aritmética es incompleta. Siendo aún más específicos, el teorema de Gödel se aplica a toda teoría aritmética más expresiva que la llamada aritmética de Robinson, que vendría a ser idéntica a la aritmética de Peano pero excluyendo el axioma de inducción matemática (Raatikainen, 2022).

Segundo teorema

El segundo teorema se sigue como corolario del primero, y es la proposición XI en el artículo original. En lo que sigue, expongo una demostración intuitiva, aunque informal y bastante simplificada, del mismo:

• Tomemos una fórmula inconsistente y representémosla como ⊥ (generalmente se toma 1=0)
• Entonces, P es consistente si, y sólo si, la contradicción ⊥ no es demostrable en P
• Ahora bien, como vimos más arriba cuando estábamos demostrando el primer teorema, si G fuese demostrable en P, esto nos lleva a una contradicción. O sea, P sería inconsistente.
• Entonces, podemos estar seguros de esto: si P es consistente, G no es demostrable en P. En símbolos:

Cons(P) → ~Dem(|G|)

• Sin embargo, dijimos que G es una oración que afirma, acerca de sí misma, que no es demostrable. Entonces, si G no es demostrable, G es verdadera.
• Por lo tanto, si P es consistente, entonces G. En símbolos:

Cons(P) → G

Este hecho es demostrable en P, es decir, es un teorema de P.

• De esto se sigue que, si la consistencia de P fuese demostrable en P, G también lo sería. Esto se puede demostrar usando, una vez más, un simple modus ponens:

Cons(P) → G (como establecimos más arriba)

Cons(P) (asumimos que la consistencia de P es demostrable)

Por lo tanto, G

• Esto claramente contradice el primer teorema que, recordemos, afirma precisamente que G no es demostrable. Por lo tanto, si el primer teorema es cierto, Cons(P) no puede ser demostrable (pues esto lleva a una contradicción). Ergo, la consistencia de P no es demostrable en P, y esto concluye la prueba del segundo teorema.

Podemos formular el segundo teorema de la siguiente forma:

En todo sistema formal omega-consistente capaz de expresar funciones recursivas, no es posible demostrar la consistencia del sistema

Observaciones finales

Como ya señalé, el teorema de incompletitud demolió la ambición del logicismo en filosofía de las matemáticas, al menos en su forma original. Recordemos que la tesis logicista era que las matemáticas son reducibles a la lógica. Todos los conceptos de las matemáticas serían definibles en términos de conceptos de la lógica, y todos los axiomas de las matemáticas serían demostrables a partir de los axiomas de la lógica.

Sin embargo, Gödel muestra que existen verdades matemáticas que no pueden ser reducidas a un sistema de lógica formal en este sentido.

En el proceso, creó técnicas y conceptos que tuvieron impacto en otras áreas del pensamiento. En particular, el concepto de función recursiva, al representar el concepto de un problema que se puede resolver mecánicamente en un número finito de pasos, está directamente relacionado al concepto de computabilidad y la teoría de la computación. Como escribe Khomskii (2008):

“…la teoría de la computabilidad…todavía no había sido inventada. De hecho, fueron los teoremas de Gödel los que en gran parte estimularon la creación de esta teoría…”

Por otra parte, la aritmetización y la representabilidad son importantes en filosofía para el estudio de la autorreferencia y las paradojas (Picollo, 2018). En filosofía de la mente, Roger Penrose (2016) y otros han argumentado que la mente humana no es representable por un algoritmo basándose en el teorema de incompletitud, aunque no sin controversia.

Sin embargo, más allá de la utilidad que puedan tener los teoremas, en mi opinión, estos poseen un valor intelectual intrínseco. Gödel descubrió una verdad fascinante y totalmente inesperada acerca del alcance y los límites de la razón. Por lo tanto, me gustaría concluir el artículo con una cita de Kant (1987) que me parece que refleja el sentimiento que me genera (y quizá también al lector) recorrer el sendero intelectual trazado por Gödel en sus teoremas:

Referencias

• • Godel, K. (2012). On formally undecidable propositions of principia Mathematica and related systems. Dover Publications.
  • Kant, I. (1987). Critique of Judgment (W. S. Pluhar, Trad.). Hackett Publishing.
  • Khomskii, Yurii (2008). Gödel’s Incompleteness Theorem. https://www.math.uni-hamburg.de/home/khomskii/recursion/Goedel.pdf
  • Penrose, R. (2016). The emperor’s new mind: Concerning computers, minds, and the laws of physics. Oxford University Press.
  • Picollo, L. (2018). Reference in arithmetic. Review of Symbolic Logic, 11(3), 573–603.
  • Raatikainen, Panu. Gödel’s Incompleteness Theorems. The Stanford Encyclopedia of Philosophy (Spring 2022 Edition), Edward N. Zalta (ed.).
  • von Plato, J. (2021). Von Neumann explains his game theory to gödel, September 1940. The Mathematical Intelligencer, 43(1), 42–44.
  • Wiener. (1982). Leibniz select: Hudson river ed. Simon & Schuster.

¿Qué te pareció este artículo?

(1 votos, promedio: 5,00 de 5)