Teoremas de incompletitud de Gödel, explicados con ejemplos

Teoremas de incompletitud de Gödel, explicados con ejemplos
Índice
  1. Las tres hipótesis
  2. Enunciados
    1. Primer teorema de incompletitud
    2. Segundo teorema de incompletitud
  3. Idea de la demostración
    1. Paso 1: convertir fórmulas en números
    2. Paso 2: hablar de demostraciones con aritmética
    3. Paso 3: la sentencia que habla de sí misma
    4. Paso 4: el segundo teorema
  4. Ejemplos de enunciados indecidibles «naturales»
  5. Lo que los teoremas NO dicen
  6. Por qué fue importante: el programa de Hilbert
  7. Relación con otros resultados
  8. Historia
  9. Preguntas frecuentes
    1. ¿Qué dice el teorema de incompletitud de Gödel?
    2. ¿En qué año los publicó Gödel?
    3. ¿Significa que las matemáticas son contradictorias?
    4. ¿Hay teorías completas?
    5. ¿Qué es un número de Gödel?
  10. Fuentes

Actualizado el

Los teoremas de incompletitud de Gödel dicen que ningún sistema de axiomas que sea consistente, que se pueda describir mediante un procedimiento mecánico y que contenga la aritmética básica puede demostrar todas las verdades aritméticas. Siempre quedan enunciados que el sistema no puede probar ni refutar. Además, un sistema así no puede demostrar su propia consistencia. Kurt Gödel los publicó en 1931 y cambiaron lo que se esperaba de los fundamentos de las matemáticas.

Las tres hipótesis

Los teoremas no hablan de cualquier sistema, sino de teorías formales T que cumplen:

  1. Consistencia: T no demuestra a la vez un enunciado y su negación.
  2. Axiomatización efectiva: hay un algoritmo que decide si una fórmula es axioma de T. Dicho de otra forma, sus teoremas se pueden enumerar con un programa.
  3. Suficiente aritmética: T puede expresar y demostrar hechos básicos sobre los números naturales con suma y multiplicación. La aritmética de Peano los cumple de sobra; la teoría de conjuntos ZFC, también.

Una teoría es completa si para todo enunciado φ de su lenguaje demuestra φ o demuestra su negación.

Enunciados

Primer teorema de incompletitud

Si T cumple las tres hipótesis, existe un enunciado GT del lenguaje de la aritmética tal que T no demuestra GT ni demuestra su negación. Es decir, T es incompleta.

La prueba original de Gödel pedía una condición algo más fuerte que la consistencia (la ω-consistencia). J. Barkley Rosser la eliminó en 1936 con una variante del enunciado, y por eso a veces se habla del teorema de Gödel-Rosser.

Segundo teorema de incompletitud

Si T cumple las tres hipótesis, T no puede demostrar el enunciado Cons(T), que expresa dentro de la aritmética que «T es consistente».

Primer teoremaSegundo teorema
Qué afirmaHay enunciados indecidibles en TT no prueba su propia consistencia
Ejemplo de enunciadoLa sentencia de Gödel GTCons(T)
Número en el artículo de 1931Teorema VITeorema XI

Idea de la demostración

Paso 1: convertir fórmulas en números

Gödel asigna a cada símbolo un número y a cada fórmula un único número natural, su número de Gödel. Una forma de hacerlo es con potencias de primos. Supongamos que codificamos 0 → 1, = → 2 y S (sucesor) → 3. La fórmula «S0 = S0» (es decir, 1 = 1) es la sucesión de códigos 3, 1, 2, 3, 1, y su número es

23 · 31 · 52 · 73 · 111 = 2.263.800

Por la descomposición única en factores primos, a partir de 2.263.800 se recupera la fórmula sin ambigüedad. Lo mismo se hace con las demostraciones, que son sucesiones de fórmulas.

Paso 2: hablar de demostraciones con aritmética

Con esta codificación, «x es el número de una demostración en T de la fórmula de número y» se convierte en una relación aritmética entre x e y, que la propia T puede expresar. Así, la aritmética puede «hablar» de lo que T demuestra.

Paso 3: la sentencia que habla de sí misma

Mediante un argumento diagonal (el lema de diagonalización), se construye un enunciado G que afirma, en esencia, «el enunciado con número de Gödel g no es demostrable en T», siendo g el propio número de G. Entonces:

  • Si T demostrara G, demostraría algo que dice que G no es demostrable; con la consistencia se llega a contradicción.
  • Si T demostrara la negación de G, con la condición de ω-consistencia (o con el truco de Rosser) también se llega a contradicción.

Así que G es indecidible en T. Es parecido a la paradoja del mentiroso, pero cambiando «falso» por «no demostrable», que es lo que evita la contradicción.

Paso 4: el segundo teorema

El razonamiento del primer teorema se puede formalizar dentro de T y da: Cons(T) → G. Si T demostrara Cons(T), demostraría G, lo que es imposible. Por tanto T no demuestra Cons(T).

Ejemplos de enunciados indecidibles «naturales»

La sentencia de Gödel es artificial. Más tarde se encontraron enunciados de aspecto corriente que la aritmética de Peano no puede demostrar, aunque son verdaderos:

  • Teorema de Goodstein: trata de sucesiones que se obtienen escribiendo un número en base 2 de forma «hereditaria», cambiando las bases por 3, restando 1, y así sucesivamente. Empezando en 3, la sucesión es 3, 3, 3, 2, 1, 0. Empezando en 4, crece durante muchísimos pasos (4, 26, 41, 60, 83, …), pero el teorema dice que todas acaban en 0. Goodstein lo demostró en 1944, y Kirby y Paris probaron en 1982 que no se puede demostrar en la aritmética de Peano.
  • Principio de Paris-Harrington (1977): una variante del teorema de Ramsey que tampoco se puede demostrar en la aritmética de Peano, aunque sí en la aritmética de segundo orden.

Lo que los teoremas NO dicen

  • «Las matemáticas están llenas de cosas indecidibles». Los teoremas aseguran que existen, no que sean la mayoría.
  • «Ninguna teoría puede ser completa». Falso: la aritmética de Presburger (solo con suma, sin multiplicación) es consistente, completa y efectiva. No cumple la tercera hipótesis.
  • «No se puede demostrar la consistencia de la aritmética». Lo que no puede es demostrarla ella misma. Gerhard Gentzen la demostró usando un sistema distinto, con un principio de inducción más fuerte.
  • «No demostrable» es lo mismo que «falso». No: G es verdadera en los números naturales y, aun así, T no la demuestra.
  • Aplicarlo a la física, al derecho o a la mente sin comprobar las hipótesis es un abuso: el teorema se refiere a sistemas formales con aritmética.

Por qué fue importante: el programa de Hilbert

David Hilbert proponía encontrar un sistema de axiomas para toda la matemática que fuera completo y consistente, y demostrar su consistencia por métodos finitos. Para muchos lógicos, los teoremas de Gödel muestran que ese programa no se puede cumplir tal como se planteó, aunque el alcance exacto todavía se discute.

Relación con otros resultados

La aritmética a la que se refieren los teoremas suele formalizarse con los axiomas de Peano. Para entender la diferencia entre lo que es verdadero y lo que es demostrable conviene tener clara la guía de qué es un teorema y qué es un axioma. En informática, el problema de la parada, que Alan Turing demostró indecidible en un artículo enviado en 1936 y publicado en 1937, expresa una limitación parecida: no hay un programa que decida si cualquier programa termina.

Historia

Kurt Gödel publicó los dos teoremas en 1931 en el artículo «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I» («Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados I»).

Preguntas frecuentes

¿Qué dice el teorema de incompletitud de Gödel?

Que toda teoría consistente, axiomatizada de forma efectiva y con suficiente aritmética tiene enunciados que no puede demostrar ni refutar. El segundo teorema añade que no puede demostrar su propia consistencia.

¿En qué año los publicó Gödel?

En 1931, en el artículo «Sobre proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados I».

¿Significa que las matemáticas son contradictorias?

No. Habla de sistemas consistentes y dice que, si lo son, quedan enunciados sin decidir y no pueden probar su consistencia desde dentro.

¿Hay teorías completas?

Sí, si no cumplen las hipótesis. La aritmética de Presburger, que solo tiene suma, es completa y consistente.

¿Qué es un número de Gödel?

Un número natural que codifica de forma única una fórmula o una demostración, por ejemplo mediante potencias de primos.

Fuentes

Teoremas

RELACIONADOS

Subir