Gödel and the Incompleteness Theorems

Zusammenfassung

In 1931 a twenty-five-year-old Viennese logician named Kurt Gödel proved that mathematics can never be both complete and able to prove its own consistency. His incompleteness theorems demolished David Hilbert’s dream of mechanizing all of mathematics — but in doing so they introduced the techniques (arithmetization, self-reference, the encoding of statements as numbers) that Alan Turing would turn into the theory of computation five years later. Gödel showed that there are true statements no algorithm can ever reach. He spent his later life at Princeton’s Institute for Advanced Study, taking daily walks with Einstein, and died in 1978 of self-starvation, convinced he was being poisoned. He is widely regarded as the greatest logician since Aristotle.

A Quiet Logician from Brno

Kurt Gödel was born on April 28, 1906, in Brünn, Austria-Hungary — the city now called Brno, in the Czech Republic. A frail, anxious child who suffered a bout of rheumatic fever at age six, he became convinced for the rest of his life that his heart had been permanently damaged, the first sign of a hypochondria that would eventually kill him. The family was German-speaking; his nickname as a boy was der Herr Warum — “Mr. Why” — for his endless questions.

He entered the University of Vienna in 1924 intending to study physics, but switched to mathematics and logic. There he fell into the orbit of the Vienna Circle, the group of logical positivists led by Moritz Schlick. Gödel attended their meetings and absorbed their obsession with the foundations of knowledge — but he never shared their philosophy. Where the positivists held that mathematical truth was merely a matter of convention and language, Gödel was a committed Platonist: he believed mathematical objects exist independently of human minds, and that the mathematician discovers truths rather than inventing them. This conviction was not incidental. It was the engine behind his greatest result.

The Completeness Theorem

Gödel’s 1929 doctoral dissertation already contained a landmark result, one often overshadowed by what came next: the completeness theorem for first-order logic. It showed that in first-order predicate logic, every statement that is true in all models is provable from the axioms — semantic truth and syntactic provability coincide. This was good news for Hilbert’s program: it confirmed that the logical machinery itself was as powerful as one could want.

The catch — and Gödel found it almost immediately — was that this only held for pure logic. The moment you added enough arithmetic to talk about the natural numbers, everything changed.

1931: The Incompleteness Theorems

In 1931 Gödel published Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (“On Formally Undecidable Propositions of Principia Mathematica and Related Systems”) in the journal Monatshefte für Mathematik. It contained two theorems that ended Hilbert’s program (see David Hilbert and the Entscheidungsproblem).

The first incompleteness theorem: any consistent formal system powerful enough to express elementary arithmetic contains true statements that cannot be proved within the system. Mathematics is not complete — there will always be truths it cannot reach.

The second incompleteness theorem: such a system cannot prove its own consistency. The one thing Hilbert most wanted — a finitary proof that arithmetic contains no contradictions — is unobtainable from inside arithmetic itself.

How the proof works

Gödel’s method was as important as his conclusion. He invented Gödel numbering: a scheme that assigns a unique natural number to every symbol, formula, and proof in the formal system. Statements about the system (“formula X is provable”) thereby become statements about numbers — arithmetic that the system can talk about itself. This trick, arithmetization of syntax, let Gödel make a formal system reason about its own structure.

With it, he constructed a sentence G that, decoded, asserts: “This statement is not provable.” A mathematical cousin of the Liar’s paradox (“this sentence is false”), but engineered to be precise rather than self-destructive. Now reason it through: if the system could prove G, then G would be false, making the system inconsistent. So if the system is consistent, G is unprovable — which is exactly what G says. Therefore G is true but unprovable. The system is incomplete.

The self-reference at the heart of the proof — a system encoding statements about itself as data it can manipulate — is the same conceptual move that underlies a program that can take another program as input. It reappears five years later in Alan Turing’s halting problem and in the design of every compiler and interpreter since.

Why It Mattered for Computing

Gödel did not set out to found computer science, and his 1931 paper says nothing about machines. But the bridge is direct. The Entscheidungsproblem — Hilbert’s question of whether a mechanical procedure could decide any mathematical statement — was answered no in 1936 by Turing and by Alonzo Church, and their proofs lean on exactly Gödel’s machinery of encoding and self-reference. Turing’s halting problem is, in a sense, the incompleteness theorem recast in terms of computation: there are well-posed questions no algorithm can settle.

Gödel himself recognized Turing’s analysis as the decisive one. He later wrote that the notion of a formal system had only been made fully precise by Turing’s work, and that the incompleteness theorems could now be stated in their sharpest, most general form because of the Turing machine. The limits of provability (Gödel) and the limits of computability (Turing) turned out to be two faces of the same boundary — and that boundary is the subject matter of theoretical computer science.

Princeton, Einstein, and the Constitution

As Austria slid toward Nazism — Schlick was murdered by a former student in 1936, and Gödel suffered repeated nervous breakdowns — Gödel emigrated. In 1940 he and his wife Adele traveled across Siberia and the Pacific to reach the United States, joining the Institute for Advanced Study in Princeton, where he became a permanent member in 1946 and a professor in 1953.

At Princeton he formed his famous friendship with Albert Einstein. The two took long walks together almost daily; Einstein once said he went to his office mainly for the privilege of walking home with Gödel. As a tribute for Einstein’s seventieth birthday in 1949, Gödel produced a startling result in general relativity: an exact solution to Einstein’s field equations describing a rotating universe that permits closed timelike curves — paths through spacetime that loop back to their own past. Gödel had found, buried in Einstein’s own theory, the mathematical possibility of time travel.

The most-told Gödel story comes from his 1947 U.S. citizenship examination. Studying the Constitution to prepare, the literal-minded logician became convinced he had discovered an internal contradiction that would legally permit the country to be turned into a dictatorship. His witnesses at the hearing were Einstein and the economist Oskar Morgenstern, who spent the drive to Trenton trying to keep Gödel from raising the subject. When the judge remarked that, unlike Austria, the United States could never become a dictatorship, Gödel began to object — “On the contrary, I can prove it!” — and the others hurriedly changed the subject. He was granted citizenship and took his oath on April 2, 1948.

Later Work: The Continuum Hypothesis

Gödel’s other major mathematical contribution was in set theory. In 1938–1940 he proved that the continuum hypothesis (CH) and the axiom of choice are consistent with the standard ZF axioms — you cannot disprove them. He did this by constructing the constructible universe L, an inner model of set theory in which both hold. The other half of the story arrived in 1963, when Paul Cohen invented the method of forcing to show that CH can also be denied consistently. Together, Gödel and Cohen established that the continuum hypothesis is independent of the ZF axioms — undecidable in exactly the sense Gödel’s 1931 theorem had foreshadowed. This was Hilbert’s very first Paris problem, settled not by an answer but by a proof that no answer exists within the standard axioms.

⚠️ Dead End: The Dream of a Self-Certifying Mathematics

Gödel’s career is itself the record of a great dead end — not his, but Hilbert’s. Hilbert’s program sought a complete, consistent formalization of all mathematics, with consistency provable by finite, uncontroversial means. It was a beautiful and reasonable goal, and an entire generation of logicians worked toward it. Gödel proved it impossible. No sufficiently powerful formal system can be complete; none can certify its own consistency. The aspiration to reduce mathematics to a closed, self-validating machine was permanently abandoned.

What is striking is how productive this dead end was. The techniques developed to kill Hilbert’s dream — arithmetization, encoding, the treatment of proofs and programs as data — became the foundation of the field that did succeed: computation. The lesson recurs throughout this encyclopedia: the most fertile results in computing history were often proofs that something cannot be done.

The Tragic End

Gödel’s lifelong hypochondria deepened into severe paranoia in his final years, including a fixed delusion that he was being poisoned. He would eat only food prepared and tasted by Adele. When she was hospitalized for six months in 1977, Gödel essentially stopped eating. He was admitted to Princeton Hospital and died there on January 14, 1978, weighing about 65 pounds (29 kg). The death certificate recorded “malnutrition and inanition caused by personality disturbance.” The man who had mapped the outermost limits of reason was destroyed by his own.

His standing is undimmed. The logician Solomon Feferman and many others rank him as the greatest logician since Aristotle, and the term “Gödelian” entered the language to describe arguments that turn a system’s own power against itself — the same maneuver, ultimately, that gave us the theory of the computable.