Science explainedCiencia explicada / LogicLógica
LogicLógica
Gödel's incompleteness, without the headacheLa incompletitud de Gödel, sin dolor de cabeza
In 1931 a young logician proved that no fixed set of rules can capture every truth about whole numbers. Here is what that means, and what it does not.En 1931, un joven lógico demostró que ningún conjunto fijo de reglas puede capturar todas las verdades sobre los números enteros. Esto es lo que significa, y lo que no.
In the 1920s the great mathematician David Hilbert set out an ambitious plan. Mathematics would be written down as a formal system, with precise axioms and rules, and then shown to be complete, able to prove every true statement, and consistent, never proving a contradiction. Better still, that consistency would be proved by simple, trustworthy reasoning.
In 1931 a young Austrian logician, Kurt Gödel, showed that the plan could not succeed. His two incompleteness theorems are among the most famous results of the twentieth century, and among the most misunderstood.
The first theorem
Take any formal system that is consistent, whose axioms can be listed by a mechanical procedure, and that is strong enough to do basic arithmetic with whole numbers. Gödel proved that such a system always contains statements that it can neither prove nor disprove. However many axioms you add, as long as these conditions hold, some questions about numbers stay out of reach.
The trick: a sentence that talks about itself
Gödel's key idea was to give every formula and every proof a code number. Statements about proofs then become statements about numbers, which the system itself can express. With this coding, he built a sentence, usually called G, that in effect says: “G cannot be proved in this system.”
Now follow the logic. If the system could prove G, it would be proving something false, because G says it has no proof. A consistent system therefore cannot prove G. But then what G says is true: it really cannot be proved. So G is a true statement that the system cannot prove. Gödel's original argument needed a slightly stronger assumption than consistency; in 1936 J. Barkley Rosser refined it so that plain consistency is enough.
The second theorem
Gödel then showed that such a system, if it is consistent, cannot prove its own consistency. This was the blow to Hilbert's plan: the consistency of arithmetic cannot be established using only the methods of arithmetic itself.
What the theorems do not say
They do not say that mathematics is broken, uncertain or arbitrary. The vast majority of theorems are proved without any trouble.
They do not apply to every system. Arithmetic with addition alone, studied by Mojżesz Presburger in 1929, is complete: every one of its statements can be decided.
“Unprovable” always means unprovable in a particular system. You can add G as a new axiom, but the stronger system then has a new sentence of its own that it cannot prove.
And they say nothing about society, law or human nature. Claims that Gödel proved that “everything is relative” stretch his results far beyond what they contain.
Real examples
Incompleteness is not only about strange self-referring sentences. The Continuum Hypothesis, a natural question about the sizes of infinite sets, can be neither proved nor disproved from the standard axioms of set theory, as Gödel (1940) and Paul Cohen (1963) showed between them. Goodstein's theorem, about sequences of numbers that grow enormously before shrinking to zero, is true, yet Laurie Kirby and Jeff Paris proved in 1982 that it cannot be proved in the usual axioms of arithmetic.
Why it matters
Gödel's ideas shaped the birth of computer science. In 1936 Alan Turing used related reasoning to show that no algorithm can decide, for every program, whether it will eventually stop. Together these results mark the limits of formal methods, and they explain why mathematics will always need new ideas, not just more computation.
En la década de 1920, el gran matemático David Hilbert propuso un plan ambicioso. La matemática se escribiría como un sistema formal, con axiomas y reglas precisas, y luego se mostraría que es completa, capaz de demostrar toda afirmación verdadera, y consistente, sin demostrar jamás una contradicción. Mejor aún, esa consistencia se probaría con razonamientos simples y confiables.
En 1931, un joven lógico austríaco, Kurt Gödel, mostró que el plan no podía funcionar. Sus dos teoremas de incompletitud están entre los resultados más famosos del siglo XX, y entre los peor entendidos.
El primer teorema
Tomemos cualquier sistema formal que sea consistente, cuyos axiomas puedan enumerarse mediante un procedimiento mecánico y que sea lo bastante potente para hacer aritmética básica con números enteros. Gödel demostró que un sistema así siempre contiene afirmaciones que no puede demostrar ni refutar. Por muchos axiomas que se agreguen, mientras se cumplan estas condiciones, algunas preguntas sobre los números quedan fuera de alcance.
El truco: una oración que habla de sí misma
La idea clave de Gödel fue asignar un número de código a cada fórmula y a cada demostración. Así, las afirmaciones sobre demostraciones se convierten en afirmaciones sobre números, que el propio sistema puede expresar. Con esa codificación construyó una oración, que suele llamarse G, que en esencia dice: “G no puede demostrarse en este sistema”.
Ahora sigamos la lógica. Si el sistema pudiera demostrar G, estaría demostrando algo falso, porque G dice que no tiene demostración. Por lo tanto, un sistema consistente no puede demostrar G. Pero entonces lo que G dice es verdad: realmente no puede demostrarse. Así, G es una afirmación verdadera que el sistema no puede demostrar. El argumento original de Gödel necesitaba un supuesto algo más fuerte que la consistencia; en 1936, J. Barkley Rosser lo refinó para que bastara la consistencia simple.
El segundo teorema
Gödel mostró además que un sistema así, si es consistente, no puede demostrar su propia consistencia. Ese fue el golpe al plan de Hilbert: la consistencia de la aritmética no puede establecerse usando solo los métodos de la propia aritmética.
Lo que los teoremas no dicen
No dicen que la matemática esté rota, sea incierta o arbitraria. La inmensa mayoría de los teoremas se demuestran sin ningún problema.
No se aplican a cualquier sistema. La aritmética que solo tiene suma, estudiada por Mojżesz Presburger en 1929, es completa: cada una de sus afirmaciones puede decidirse.
“Indemostrable” siempre significa indemostrable en un sistema determinado. Se puede agregar G como nuevo axioma, pero el sistema más fuerte tendrá entonces una nueva oración propia que no podrá demostrar.
Y no dicen nada sobre la sociedad, el derecho o la naturaleza humana. Afirmar que Gödel demostró que “todo es relativo” estira sus resultados mucho más allá de lo que contienen.
Ejemplos reales
La incompletitud no trata solo de extrañas oraciones que hablan de sí mismas. La hipótesis del continuo, una pregunta natural sobre los tamaños de los conjuntos infinitos, no puede demostrarse ni refutarse a partir de los axiomas habituales de la teoría de conjuntos, como mostraron entre ambos Gödel (1940) y Paul Cohen (1963). El teorema de Goodstein, sobre sucesiones de números que crecen enormemente antes de bajar hasta cero, es verdadero, y sin embargo Laurie Kirby y Jeff Paris demostraron en 1982 que no puede probarse con los axiomas usuales de la aritmética.
Por qué importa
Las ideas de Gödel marcaron el nacimiento de la informática. En 1936, Alan Turing usó un razonamiento emparentado para mostrar que ningún algoritmo puede decidir, para todo programa, si este terminará alguna vez. Juntos, estos resultados señalan los límites de los métodos formales y explican por qué la matemática siempre necesitará ideas nuevas, y no solo más cálculo.
Further readingPara leer más
- Kurt Gödel, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik und Physik 38 (1931): 173–198.
- Ernest Nagel and James R. Newman, Gödel's Proof (New York University Press, 1958).
- Torkel Franzén, Gödel's Theorem: An Incomplete Guide to Its Use and Abuse (A K Peters, 2005).
Do you research these questions?¿Investiga usted estas preguntas?
Fundamental Science Journal publishes peer-reviewed research in physics, mathematics, chemistry and logic, in English or Spanish.Fundamental Science Journal publica investigación arbitrada en física, matemática, química y lógica, en inglés o en español.