On this page
Most students meet mathematics as a subject where every question has an answer you can prove, if you are clever enough. In 1931 a young logician in Vienna showed that this hope has a hard limit. This post explains what Kurt Godel proved in plain language, walks through the coding trick at the heart of his proof with numbers you can check, and clears up the most common misreading of his result.
Who was Kurt Godel?
The MacTutor biography from the University of St Andrews records that Godel was born on 28 April 1906 in Brunn, Austria-Hungary (now Brno in Czechia), and died in Princeton on 14 January 1978. At school he was strong in mathematics and languages. He entered the University of Vienna in 1923 unsure whether to study mathematics or theoretical physics, and chose mathematics after the lectures of Philipp Furtwangler. He completed his doctorate under Hans Hahn in 1929, proving the completeness of first-order logic.
After moving to the United States in 1940 he worked at the Institute for Advanced Study in Princeton, where Einstein became one of his closest friends. MacTutor lists the Einstein Award in 1951 and the National Medal of Science in 1974. Georg Kreisel's Royal Society memoir remains the standard scientific account of his work.
What problem was Godel working on?
In the early twentieth century, mathematicians wanted to put all of mathematics on a fixed set of axioms and rules, so that every true statement could, in principle, be derived mechanically. Russell and Whitehead's Principia Mathematica was one attempt; David Hilbert's formalist programme was another. MacTutor notes that Godel's results dealt Hilbert's programme "a severe blow" and showed that mathematics is not a finished object.
Godel's paper, On formally undecidable propositions of Principia Mathematica and related systems, appeared in Monatshefte fur Mathematik und Physik in 1931.
What do the two incompleteness theorems say?
The Stanford Encyclopedia of Philosophy gives careful modern statements:
First theorem: any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete. There are statements in its language that it can neither prove nor disprove.
Second theorem: such a system, if consistent, cannot prove its own consistency.
"Consistent" means the system never proves both a statement and its opposite. "Formal system" means a precise list of axioms and rules, the kind a computer could check.
The Stanford entry calls the "unprovable truths" reading a common misunderstanding. The theorems are about provability inside one fixed system, not about proof in some absolute sense.
How can a statement talk about proofs?
Godel's key move was to give every symbol, formula and proof a code number. Statements about formulas then become statements about numbers, which arithmetic can express. Using that, he built a sentence that, read through the code, says roughly "this sentence is not provable in the system". If the system could prove it, the system would prove something false; so, if the system is consistent, the sentence is unprovable, and what it says is true.
Worked example: coding formulas as numbers
Here is a toy version of Godel numbering. It is not his exact scheme, but it uses his idea. Give each symbol a number: 0 is 1, = is 2, S (meaning "the next number after") is 3. To code a string of symbols, raise the primes 2, 3, 5, 7, 11 and so on to those symbol numbers and multiply.
Code "0 = 0". The symbol numbers are 1, 2, 1. The code is 2¹ × 3² × 5¹ = 2 × 9 × 5 = 90.
Decode 90. Factorise: 90 = 2 × 3² × 5. The exponents in order are 1, 2, 1, so the string is "0 = 0".
Code "S0 = S0" (1 + 0 = 1 + 0, in effect). The symbol numbers are 3, 1, 2, 3, 1, so the code is 2³ × 3¹ × 5² × 7³ × 11¹ = 8 × 3 × 25 × 343 × 11 = 2,263,800.
Decoding always works because every whole number above 1 factorises into primes in only one way. That is the fundamental theorem of arithmetic from Class 10, and it is what lets a number stand in for a formula with no ambiguity.
Common mistakes when you try this yourself: skipping a prime (the second symbol must use 3, not 5), multiplying exponents instead of powers, and forgetting that the order of symbols is carried by the order of the primes.
How did his work connect to computers?
MacTutor notes that the theorems imply no computer can be programmed to answer every mathematical question. A few years later Alan Turing reached a related limit for machines, which our post on Alan Turing and computing covers. MacTutor names John von Neumann among his friends at Princeton.
What can a student take from Godel's way of working?
Ask what a method cannot do. Godel's result came from turning a question about mathematics back onto mathematics itself.
State things precisely. The theorems are easy to misquote. Their power is in the exact conditions: consistent, formal, enough arithmetic.
Use simple tools in a new way. Prime factorisation is school mathematics. Godel used it to encode proofs.
If proof by contradiction or prime factorisation still feels shaky, the Fermi Concept Library has every concept in mathematics with its own lesson, so you can fix that one gap before going further.
Try it now: decode the toy Godel number 2³ × 3³ × 5 × 7² × 11³ × 13 with the symbol code above, write out the string, and decide whether the statement is true.
