1. The Question Nobody Could Answer
On 8 September 1930, in the city of Königsberg, the most famous mathematician of his day stood up to give his retirement address. David Hilbert was sixty-eight years old, and he had spent his career insisting that every mathematical problem has an answer. He closed his speech with a slogan, delivered in German, that would later be carved onto his tombstone: "Wir müssen wissen — wir werden wissen." We must know. We will know.
The day before, in a small round-table discussion at the very same conference, a quiet twenty-four-year-old from Vienna had said something that made Hilbert's slogan impossible. Kurt Gödel had announced, almost as an aside, that he could construct a true statement of arithmetic that no formal system could prove. Almost nobody in the room quite grasped what they had heard — with one exception, John von Neumann, who understood at once. Hilbert gave his speech the next day as if nothing had changed.
I first met Gödel's theorems as a student, in a lecture hall much like any other, and I remember the peculiar feeling they left behind. Most theorems in mathematics feel like doors opening: here is a new result, here is a new tool, here is a new piece of territory. Gödel's incompleteness theorems felt like a door closing — gently, politely, and permanently. They did not say that mathematics was broken. They said something stranger: that no matter how carefully you build the foundations of mathematics, there will always be true statements your system cannot reach, and your system can never certify its own freedom from contradiction. The most careful foundation ever built has a limit built into it.
That is the question this article answers: can mathematics prove everything? The short answer is no, and the long answer is one of the most beautiful arguments ever made — an argument that turns mathematics into arithmetic, arithmetic into code, and code into a sentence that talks about itself. Along the way we will meet the boldest plan in the history of mathematics, the crisis that made it necessary, a numbering trick that turned proofs into numbers, and a machine that was invented to answer a question about logic and ended up inventing the computer. We will also clear away the myths, because Gödel's theorems are among the most misunderstood results in all of science.
What "prove everything" would actually mean
When a mathematician says a statement is proved, they mean something specific: starting from a small set of agreed starting points, called axioms, and following strict rules of reasoning, you can reach the statement in a finite number of steps. The axioms are the things you take for granted. The rules tell you which moves are legal. The proof is the path. If every true statement about numbers had such a path, mathematics would be, in a sense, finished — at least in principle. You would have a machine, or a method, that could settle any question. That was the dream, and it was not a naive dream. By 1930 it was the official programme of the greatest mathematician of the age, and it looked within reach.
The dream had three parts, and it helps to keep them separate, because Gödel destroyed them one at a time. First, consistency: the system must never prove a contradiction. Second, completeness: the system must prove every true statement, or disprove it — nothing left undecided. Third, decidability: there must be a mechanical procedure that can tell, for any statement, whether it is provable. Gödel showed that no system strong enough for ordinary arithmetic can have the first two together in the way Hilbert wanted, and a few years later Church and Turing showed the third was impossible too.
Why this matters to you
You do not need to be a mathematician to care about this. Every time a computer checks a proof, every time a programme verifies that a piece of software is safe, every time someone asks whether an artificial intelligence could ever fully understand itself, Gödel's theorems are standing in the background, quietly setting the terms. They are the reason that proof-checking software can be powerful without ever being complete, and the reason that the dream of a machine that settles all mathematical questions died in 1936.
2. What Is a Formal System?
Before we can understand what Gödel proved, we need to understand what he proved it about. The object at the centre of the story is the formal system, and it is a much simpler idea than its name suggests. A formal system is a game with written rules. You start with a small collection of symbols — letters, numbers, signs like plus and equals. You lay down a handful of starting statements, the axioms, which you accept without proof. You lay down rules of inference, which tell you exactly how to produce new statements from old ones. And then you play: every statement you can reach by following the rules, starting from the axioms, is a theorem of the system. Everything else is not.
That is all a formal system is. It has no opinions about what its symbols mean. Inside the system, "2 + 2 = 4" is not a claim about apples or coins; it is a string of symbols that can be produced by the rules. The meaning lives outside the system, in our heads. This separation between the symbols and their meaning is the whole trick of formal mathematics, and it is what makes Gödel's argument possible. Because once a proof is nothing but a sequence of symbols produced by rules, a proof is a kind of object — and objects can be counted, coded, and talked about inside the system itself.
Think of chess. The rules of chess do not mention strategy, beauty, or who is winning. They say which moves are legal from which positions. A game of chess is a sequence of legal moves from the starting position. A formal system works the same way: the axioms are the starting position, the rules of inference are the legal moves, and a proof is a game — a sequence of legal moves that ends at the statement you wanted to reach. If the statement can be reached, it is a theorem of that system, however true it might look from outside.
The rules of the game
Every formal system has the same four ingredients. First, an alphabet: the symbols you are allowed to write. Second, a grammar: the rules that say which strings of symbols count as well-formed statements. Third, axioms: the starting statements, accepted without proof. Fourth, rules of inference: the allowed moves, which let you derive new statements from ones you already have. The most famous rule of inference is modus ponens, and it is as simple as reasoning gets: if you have "if A then B" and you have "A", you may write down "B". That is the whole move. Proofs are built from such tiny steps, thousands of them, each one checked by a rule that a machine could follow.
The strictness is the point. In everyday argument, we skip steps, appeal to intuition, and say "obviously". A formal system forbids all of that: every step must be justified by a rule. That makes formal proofs long and tedious, but it also makes them checkable — a proof can be verified mechanically, symbol by symbol, without understanding a word of it. That mechanical checkability is what Hilbert wanted to exploit, and it is what Gödel turned against the dream.
Peano arithmetic in one paragraph
The formal system that matters most for this story is Peano arithmetic, named after the Italian mathematician Giuseppe Peano, who set down its axioms in 1889. Peano arithmetic is the system that captures ordinary arithmetic with whole numbers: zero, the successor operation (add one), addition, and multiplication. Its axioms say the obvious things — zero is a number, every number has a successor, different numbers have different successors, zero is not the successor of anything — and then come the rules for adding and multiplying, and one powerful rule called induction. Induction is the rule that says: if something is true of zero, and if whenever it is true of a number it is also true of the next number, then it is true of all numbers. Induction is the engine that lets a finite set of axioms say things about infinitely many numbers. Without it, arithmetic would be a list of facts. With it, arithmetic becomes a theory.
Peano arithmetic is small — a short list of axioms plus the induction rule, which is really a schema, a template standing for infinitely many axioms. And yet it is strong enough to express every fact about whole numbers that ordinary mathematics uses: prime numbers, divisibility, the fact that there are infinitely many primes, and a great deal more. That strength is exactly what makes it vulnerable to Gödel's argument. A weaker system, one that could only add and never multiply, would escape the theorems entirely.
Why formalise at all?
It is fair to ask why anyone would want to turn mathematics into a symbol game in the first place. The answer is certainty. For two thousand years, mathematicians had proved things the way Euclid did: with words, diagrams, and appeals to what seemed obvious. That worked wonderfully until the nineteenth century, when proofs turned out to rely on hidden assumptions and definitions turned out to be vague. And then, as we will see in section 4, a paradox appeared at the very heart of the subject, in the foundations of set theory, and the whole edifice shook.
Formalisation was the response: write down exactly what you assume, exactly what moves are legal, and then let the rules do the work. If mathematics could be rebuilt as a formal system, then every proof could be checked mechanically, every hidden assumption would be exposed, and certainty would be restored — not by intuition, but by rules. That was Hilbert's programme, and it is the subject of the next section. But first, one more point, because it is the point on which the whole story turns: a formal system cannot talk about itself. Or so everyone thought. Gödel's genius was to show that it can — that arithmetic is expressive enough to describe its own proofs, and that a system can be made to say, in its own language, "this statement cannot be proved".

3. Hilbert's Dream: The Program to Secure Mathematics
David Hilbert was not a man who doubted. In the summer of 1900, at the International Congress of Mathematicians in Paris, he stood before his colleagues and laid out twenty-three problems that he believed would shape the new century. He presented ten of them in person, on 8 August, at the Sorbonne; the full list was published later, and translated into English in 1902. The problems ranged across the whole of mathematics, from the continuum hypothesis to the physics of fluids. But the second problem on the list was different from the rest. It was not a problem inside mathematics. It was a problem about mathematics itself: prove that the axioms of arithmetic are consistent — that they can never, by any chain of reasoning, lead to a contradiction.
That question became the centre of Hilbert's life's work, and in the 1920s it grew into a full programme: Hilbert's program. The plan had two stages. First, formalise mathematics — write down a complete formal system, with explicit axioms and rules, that captures all of mathematical reasoning. Second, prove, using only simple, concrete, finitistic reasoning — reasoning that deals with finite objects and finite steps, the kind of reasoning nobody could doubt — that the system is consistent, complete, and decidable. If that could be done, mathematics would be secure forever. Every proof could be checked. Every true statement could, in principle, be proved. And no contradiction could ever appear, because the consistency proof would rule it out in advance.
Hilbert's confidence was total, and it was eloquent. He believed that every well-posed mathematical problem could be solved, that there were no permanently unanswerable questions in mathematics. The Latin slogan of the sceptics was ignorabimus — "we do not know, and we shall not know". Hilbert's answer, given in that Königsberg address in 1930, was the opposite: "For us there is no ignorabimus... our slogan shall be: We must know — we will know!" The words were later carved on his tombstone in Göttingen, and they are worth remembering, because Gödel's theorems are, in a precise sense, the reply.
"Wir müssen wissen — wir werden wissen!" — "We must know — we will know!" — David Hilbert, closing his retirement address to the Society of German Scientists and Physicians, Königsberg, 8 September 1930.
Paris 1900
The 1900 lecture is one of the most famous lectures in the history of mathematics. Hilbert was thirty-eight, at the height of his powers, and he was not merely listing hard problems. He was setting the agenda for a century, with a philosophy: that mathematics is a single, connected enterprise, that its problems are solvable, and that solving them is a matter of finding the right methods. The first problem on the list, Cantor's continuum hypothesis — is there an infinity strictly between the countable infinity of the whole numbers and the infinity of the real numbers? — would take until 1963 to settle, and the answer would turn out to depend on Gödel's work in a way nobody in Paris could have foreseen. The second problem, consistency, was the one Hilbert himself cared about most, because everything else rested on it. If arithmetic were inconsistent, then a contradiction could be proved from its axioms, and from a contradiction, by the rules of logic, anything follows — every statement would become provable, and mathematics would collapse into nonsense.
That is why consistency mattered so much. An inconsistent system is not merely wrong about one thing; it is wrong about everything. It proves every statement, true and false alike. So the first demand on any foundation is that it must not contradict itself. The second demand is that it must be complete: every true statement must be provable, or at least every statement must be settled one way or the other. And the third is decidability: there must be a mechanical method for deciding, for any statement, whether it is provable. Hilbert wanted all three, proved by finitistic means, for a system strong enough to hold all of mathematics.
The three demands
The three demands sound abstract, so here they are in plain language, with the verdict that history delivered on each.
| Demand | What it asks | What happened |
|---|---|---|
| Consistency | The system never proves both a statement and its negation. | Gödel's second theorem (1931): a consistent system for arithmetic cannot prove its own consistency. Gentzen proved consistency in 1936, but only with methods outside Hilbert's finitistic limits. |
| Completeness | Every true statement about numbers is provable — or at least, every statement is proved or disproved. | Gödel's first theorem (1931): any consistent system for arithmetic contains true statements it can neither prove nor disprove. |
| Decidability | A mechanical procedure decides, for any statement, whether it is provable. | Church and Turing (1936): no such procedure exists. The Entscheidungsproblem has no solution. |
Table 1: Hilbert's three demands on a foundation for mathematics, and the verdict history delivered on each.
Notice the shape of the story. Hilbert asked for three things. Gödel took the first two, and Church and Turing took the third, five years later. But the story is not a simple defeat. Hilbert's programme failed in its original form, and yet it succeeded in a deeper sense: the attempt to formalise mathematics gave birth to mathematical logic, to proof theory, to computability theory, and eventually to the computer itself. The programme's failure was one of the most productive failures in the history of science.
Why it mattered
It is easy, a century later, to wonder why anyone cared so much about foundations. Mathematicians were proving theorems every day, and the theorems worked. Why worry about whether the axioms were consistent? The answer is that the worry was forced on them. In the decades before Hilbert's programme, the foundations of mathematics had suffered two shocks. The first was the discovery of non-Euclidean geometry: for two thousand years, Euclid's geometry had seemed to be the unique, necessary description of space, and then mathematicians found consistent geometries in which Euclid's parallel postulate was false. The second shock was worse, because it struck at logic itself. It is the subject of the next section, and it is the reason Hilbert's programme felt urgent rather than academic.

4. The Crisis Before Gödel
The crisis began with a letter. On 16 June 1902, Bertrand Russell wrote to the German logician Gottlob Frege, pointing out a contradiction in the system Frege had spent his life building. Frege had spent decades trying to derive all of arithmetic from pure logic, and his great work, the Grundgesetze der Arithmetik, was nearly complete. Russell's letter showed that Frege's system allowed the construction of a set that both belonged to itself and did not belong to itself — a contradiction, at the very foundation. Frege replied within days, and in the appendix to the second volume of his work, published in 1903, he admitted that the foundation of his edifice had been shaken. The system he had built his life's work on was inconsistent.
The contradiction Russell found is easy to state, and that is what made it so devastating. Consider the set of all sets that do not contain themselves. Does that set contain itself? If it does, then by its own definition it does not contain itself. If it does not, then by its own definition it does contain itself. Either way, contradiction. This is Russell's paradox, and it is a close cousin of the liar paradox — "this sentence is false" — which our article on mathematical paradoxes explores in full, along with Zeno's paradoxes and the foundations crisis they fed into. The paradox showed that the naive idea of a set — any collection you can describe is a set — was broken. And sets were supposed to be the foundation of everything.
The shock was not that a clever puzzle had been found. The shock was that the puzzle lived in the foundations, in the very definitions on which arithmetic was meant to rest. If you could prove a contradiction from the basic principles of set theory, then nothing built on those principles was safe. Some, like the intuitionist L. E. J. Brouwer, argued that mathematics had to be rebuilt on stricter, more constructive grounds. Some carried on as if nothing had happened. And Hilbert chose the boldest response of all: rebuild the whole of mathematics as a formal system, and then prove, by unimpeachable means, that the system was safe.
The set that broke everything
Russell's paradox deserves a moment of its own, because it is the direct ancestor of Gödel's argument. Both turn on self-reference: a sentence, or a set, that talks about itself. The liar paradox says "this sentence is false", and it breaks because the sentence refers to its own truth. Russell's set is "the set of all sets that do not contain themselves", and it breaks because the set refers to its own membership. Gödel's sentence will say "this statement is not provable", and it works — rather than breaking — because it refers to its own provability. The difference between a paradox and a theorem, in this story, is the difference between truth and provability.
It is worth noting that Russell's paradox was not the first warning. Cantor's work on infinity had already produced paradoxes of a similar flavour — the set of all sets, the largest cardinal number — and Cantor himself had noticed the trouble. But Russell's version was crisp, undeniable, and published, and it could not be ignored. The foundations crisis was real, and it lasted for decades. It was still unresolved when Gödel arrived in Vienna as a student.
Three volumes to prove 1 + 1 = 2
Russell and Whitehead's answer to the crisis was one of the most ambitious books in the history of mathematics: Principia Mathematica, published in three volumes in 1910, 1912, and 1913. Their plan was to derive all of mathematics from logic, starting from a small set of axioms and rules, and to do it so carefully that no paradox could creep in. The key device was the theory of types: a hierarchy that forbids a set from containing itself, by assigning every object a level and insisting that a set can only contain objects of lower levels. Self-reference, the source of the paradox, was banned by construction.
The book is nearly two thousand pages long, written in a dense symbolic notation, and its most famous detail is also its most revealing. It is not until 54.43, in the first volume, that Russell and Whitehead reach the proposition from which it follows, once addition has been defined, that 1 + 1 = 2 — and the proof itself is only completed in the second volume, with the dry comment that "the above proposition is occasionally useful". Hundreds of pages of logic, to earn the right to say that one plus one is two. The detail is often told as a joke, but it is a measure of how seriously they took the foundations: if you want certainty, you must build it from the ground up, and the ground is a long way down.
Principia Mathematica was the system Gödel chose as his target, and the choice was deliberate. It was the most careful, most complete formalisation of mathematics that existed. If Gödel could show that even Principia was incomplete — that even the most thorough system ever built could not prove every truth — then no system could. And that is what he did. His paper is titled "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", and the "related systems" are the point: the argument works for any system like Principia, any system strong enough to do arithmetic. The specific system does not matter. The limit is general.
5. Kurt Gödel: The Quiet Young Man from Brno
Kurt Gödel was born on 28 April 1906, in Brünn, then part of Austria-Hungary and now Brno in the Czech Republic, into a German-speaking family. His father managed a textile factory. As a boy he was known as "Herr Warum" — Mr Why — for his habit of asking questions nobody could answer. He was a sickly child, and the habit of reading and thinking indoors stayed with him for life. In 1924 he went to the University of Vienna, intending to study physics, and fell instead under the influence of the Vienna Circle, the group of philosophers and scientists who met to discuss logic, language, and the foundations of science. The Circle was the liveliest intellectual gathering in Europe, and Gödel, quiet and precise, became one of its most formidable members.
Gödel completed his doctorate in 1930, at the age of twenty-four, with a dissertation that proved the completeness theorem for first-order logic. The completeness theorem says something remarkable: in first-order logic — the logic of "for all" and "there exists" — every statement that is true in all interpretations is provable. Truth and provability coincide, for that logic. It is a beautiful result, and it is the reason the incompleteness theorems are so often misunderstood. People hear "incompleteness" and assume Gödel proved that logic is broken. He proved the opposite for first-order logic: it is complete. The incompleteness appears only when the logic is strong enough to talk about arithmetic — when the system can express addition and multiplication of whole numbers.
I remember the moment this distinction clicked for me, years after my first encounter with the theorems. I had been carrying around a vague sense that Gödel had shown mathematics to be somehow uncertain, and then a teacher drew the line on a blackboard: first-order logic, complete; arithmetic, incomplete. The line was the whole story. The incompleteness is not a fog over everything. It is a specific, sharp fact about a specific kind of system, and its sharpness is what makes it a theorem rather than a mood.
The completeness theorem, and why it matters
The completeness theorem deserves a paragraph, because without it the incompleteness theorems look like a verdict on logic itself, and they are not. First-order logic is the language in which mathematicians write their proofs: variables, quantifiers, connectives, and rules like modus ponens. Gödel's dissertation showed that this logic is complete — that if a statement is valid, meaning true in every possible interpretation, then there is a formal proof of it. There is no gap between truth and proof, at the level of pure logic.
Arithmetic changes the picture, because arithmetic is not pure logic. It is logic plus the axioms about numbers, and those axioms give the system enough expressive power to talk about itself. The completeness theorem says that the logical machinery is perfect. The incompleteness theorems say that the moment you add arithmetic to that machinery, the combined system can express statements it cannot settle. The logic is fine. The arithmetic is where the limit lives.
Vienna, 1930
In the autumn of 1930, Gödel was twenty-four, newly doctored, and working on the problem that would make him famous. The Vienna Circle met regularly, and the foundations of mathematics were its central topic. Hilbert's programme was the orthodoxy of the day. Gödel's result was not a frontal attack on it — he was, by temperament, a quiet man who avoided confrontation — but it was decisive all the same. He announced the first incompleteness theorem at the Königsberg conference on 7 September 1930, in a round-table discussion, in a few modest sentences. The paper itself, submitted on 17 November 1930 and published in January 1931, is short — and it changed the world.
The response was swift, at least among those who understood it. John von Neumann grasped the result at once and wrote to Gödel within weeks; he had independently derived the second theorem and immediately conceded priority to Gödel. Hilbert, by contrast, took longer to absorb the blow. But the mathematical community did. Within a few years, the incompleteness theorems were the central fact of mathematical logic, and Hilbert's programme, in its original form, was over.
6. The First Incompleteness Theorem
Here is the first of Gödel's incompleteness theorems, in plain language. Take any formal system that is consistent — it never proves a contradiction — and strong enough to express basic arithmetic, the addition and multiplication of whole numbers. Then there is a true statement about the whole numbers that the system can neither prove nor disprove. The system is incomplete: there are truths it cannot reach.
Read that again, slowly, because every word is doing work. "Consistent" matters: an inconsistent system proves everything, including falsehoods, so incompleteness is the price of consistency, not a symptom of failure. "Strong enough to express basic arithmetic" matters: weaker systems escape, and we will see how. "True" matters: the unprovable statement is not a mystery or a coin flip. It is true, in the ordinary sense that it correctly describes the whole numbers, and yet the system cannot prove it. And "neither prove nor disprove" matters: the statement is undecidable within the system — the system cannot settle it either way. It is not that the proof is long or hard. It is that no proof exists, in that system, at all.
The theorem is often stated in a sharper form: for any such system F, there is a statement G that is true but unprovable in F, and whose negation is also unprovable in F. G is the famous Gödel sentence, and the next three sections build it from scratch: first the numbering trick that lets arithmetic talk about proofs, then the diagonal argument that lets a sentence talk about itself, then the proof itself, step by step.
The statement, in plain English
To see what the theorem claims, consider a simpler, smaller system: one that only knows about the numbers from zero to ten, with axioms for addition up to ten. Such a system is incomplete in an obvious, boring way: it cannot prove anything about eleven, because eleven is not in its world. Gödel's theorem is not about that kind of incompleteness. It is about a system that knows about all the whole numbers, with all the axioms of arithmetic, and still cannot prove some true statement about them. The incompleteness is not a matter of missing axioms. It is structural. Add more axioms and you will prove the old Gödel sentence — but the new, larger system will have a new Gödel sentence of its own, true and unprovable in it. You can chase completeness forever, adding axioms one by one, and you will never catch it.
That is the part that makes the theorem feel so strange. It is not that one particular system has a hole in it. It is that every system of that kind has a hole, and the hole moves when you patch it. The limit is not in the system. It is in the very idea of a formal system strong enough for arithmetic.
True but unprovable
The phrase "true but unprovable" is the one that causes the most confusion, so it is worth being precise about it. When mathematicians say the Gödel sentence is true, they mean it is true about the ordinary whole numbers — the numbers 0, 1, 2, 3, and so on, the ones we count with. The Gödel sentence says, in effect, "this statement is not provable in the system F". And it is true, because the proof of the theorem shows that F indeed cannot prove it. The truth of the sentence is established by reasoning about F from outside F. Inside F, the sentence cannot be proved. Outside F, we can see that it is true. There is no contradiction here, because "true" and "provable in F" are different things.
This is also why the theorem does not mean that mathematics is broken. Mathematicians prove things about systems from outside those systems all the time. The incompleteness theorem itself is a proof, carried out in ordinary mathematics, that a certain statement is true and unprovable in F. The theorem does not say we cannot know the truth. It says the system cannot prove it. We, standing outside, can know it perfectly well.
Rosser's improvement
Gödel's original proof needed a slightly stronger assumption than plain consistency, called omega-consistency: a system is omega-consistent if it never proves that a property fails for some number while also proving, for each particular number, that the property holds. In 1936, the American logician J. Barkley Rosser found a way to remove it. Rosser's version of the Gödel sentence says, in effect, "for every proof of this statement, there is a shorter proof of its negation" — a sentence that is undecidable assuming only that the system is consistent. The improvement matters because it shows the theorem needs nothing beyond consistency itself.
7. Gödel Numbering: Turning Maths into Arithmetic
The first step of Gödel's proof is a trick so simple that it feels like cheating, and so powerful that it changed the subject forever. If a formal system is made of symbols, and symbols can be given numbers, then every statement in the system can be given a number, and every proof — which is just a sequence of statements — can be given a number too. Once statements and proofs are numbers, the system can talk about them, because the system talks about numbers. Arithmetic becomes a language in which arithmetic can describe its own proofs. That is Gödel numbering.
Here is a toy version, small enough to check by hand. Give each symbol a code number:
- 0 gets the code 1
- = gets the code 2
- S (the successor symbol, meaning "add one") gets the code 3
- + gets the code 4
- ( gets the code 5
- ) gets the code 6
Now take a formula, a string of symbols, and turn it into a single number by raising the first prime to the power of the first symbol's code, the second prime to the power of the second symbol's code, and so on. The formula "0 = 0" has the symbol codes 1, 2, 1, so its Gödel number is 2 to the power 1, times 3 to the power 2, times 5 to the power 1 — that is, 2 times 9 times 5, which is 90. The number 90 is the formula "0 = 0", written as a number. And the trick is reversible: factorise 90 into primes, and you get 2 times 3 squared times 5, which reads back as the codes 1, 2, 1, which is "0 = 0". The fundamental theorem of arithmetic — every number has exactly one prime factorisation — guarantees that no two formulas share a Gödel number, and that every Gödel number decodes to exactly one formula.
The numbers grow fast. The formula "S0 = S0" — "the successor of zero equals the successor of zero", or 1 = 1 — has the symbol codes 3, 1, 2, 3, 1, and its Gödel number is 2 to the power 3, times 3 to the power 1, times 5 to the power 2, times 7 to the power 3, times 11 to the power 1, which works out to 2,263,800. A short sentence already has a Gödel number in the millions. A real proof, with thousands of symbols, would have a Gödel number with thousands of digits. But the size does not matter. What matters is that the coding is mechanical: given a formula, you can compute its number, and given a number, you can check whether it is the code of a formula, and which one.
From symbols to numbers
Gödel's real numbering was more elaborate than our toy version — he gave a code to every symbol of Principia Mathematica, and a way of coding whole sequences of formulas, so that an entire proof became a single number — but the idea is exactly the one you have just seen. Once proofs are numbers, statements about proofs become statements about numbers. "The sequence of formulas coded by the number p is a proof of the formula coded by the number q" becomes a claim about the numbers p and q, a claim that arithmetic itself can express. The system has gained the ability to talk about itself.
This is the move that makes the whole proof possible, and it is worth pausing to admire it, because it is the same move that sits underneath the modern computer. A computer programme is a sequence of symbols, and in a computer it is stored as numbers. Code is data, and data is code. Gödel's numbering was the first time anyone had made that identification precise, and it is no accident that the theory of computation grew directly out of it. When Turing invented his machine five years later, he was walking a road Gödel had paved.
Why primes?
Why prime numbers, rather than some simpler code? Because prime factorisation is unique. If you coded a formula by adding up the symbol codes, two different formulas could easily give the same total, and then the code would be ambiguous. Prime powers solve the problem completely: the exponents in the prime factorisation of a number are unique, so the code of a formula can always be read back, symbol by symbol, in order. The code is a perfect, lossless translation from the world of symbols into the world of numbers.
There is a quiet beauty in the choice. The fundamental theorem of arithmetic — that every whole number factors uniquely into primes — is one of the oldest results in mathematics: Euclid proved that every number is a product of primes, and Gauss stated the uniqueness in full in 1801. Gödel used a result from the third century BC to prove a result about the limits of proof in the twentieth century AD.

8. The Diagonal Argument: A Sentence That Talks About Itself
The second step of the proof is an old idea with a new job. In 1891, Georg Cantor showed that there are more real numbers than whole numbers, using an argument called the diagonal argument. Our article on infinity tells the full story of Cantor's argument and Hilbert's Hotel, so here is only the part we need. Imagine a list of binary strings — strings of zeros and ones — and suppose someone claims the list contains every such string. Cantor's trick is to build a new string that cannot be on the list: take the first digit of the first string and flip it, take the second digit of the second string and flip it, and so on down the diagonal. The new string differs from every string on the list in at least one position, so it is not on the list, and the list was not complete after all.
Here is a concrete example, with five strings of length five:
- Row 1: 0 1 0 1 1
- Row 2: 1 0 1 0 0
- Row 3: 0 0 1 0 1
- Row 4: 1 1 0 1 0
- Row 5: 0 1 1 1 0
The diagonal — the first digit of row 1, the second of row 2, the third of row 3, the fourth of row 4, the fifth of row 5 — is 0, 0, 1, 1, 0. Flip every digit, and you get 1, 1, 0, 0, 1. That string, 11001, differs from row 1 in the first position, from row 2 in the second, from row 3 in the third, from row 4 in the fourth, and from row 5 in the fifth. It is not on the list, and no list can ever be complete, because the diagonal trick works on any list you propose. The argument is five lines long and it defeats infinity.

From Cantor to the liar
Cantor used the diagonal argument to show that a list of real numbers can never be complete. Gödel used the same argument to build a sentence that talks about itself. The connection runs through the liar paradox: "This sentence is false." If the sentence is true, then what it says is the case, so it is false. If it is false, then what it says is not the case, so it is true. Either way, contradiction.
But provability is not truth. A sentence that says "this sentence is not provable" does not produce a contradiction. It produces a theorem. Suppose the sentence is provable: then what it says is the case, so it is not provable — contradiction. Suppose its negation is provable: then the sentence is false, which means it is provable — contradiction again. The only consistent possibility is that neither the sentence nor its negation is provable, and that the sentence is true. Self-reference breaks truth. It does not break provability. It reveals the gap between them.
The diagonal argument is what lets Gödel build the self-referential sentence inside arithmetic. Because every formula has a Gödel number, you can take a formula with one free variable — a formula that says something about a number — and feed it its own Gödel number. The formula then says something about the number that codes the formula itself. By choosing the formula carefully, you can arrange for it to say "the formula with this Gödel number is not provable" — and the formula with that Gödel number is the formula itself. It is the diagonal argument, applied not to a list of numbers, but to the list of all formulas.
The sentence that says "I am unprovable"
The result of the diagonal construction is the Gödel sentence, usually written G. In plain language, G says: "This statement is not provable in the system F." That is all it says. It does not say anything about numbers, or about geometry, or about the world. It says something about provability, and it says it about itself. And it is the sentence whose existence proves the first incompleteness theorem, because, as we will see in the next section, the system F can neither prove G nor disprove it, and G is true.
It is worth pausing on how strange this is. Inside the formal system, G is an ordinary statement about numbers — a long, complicated claim about whole numbers and their properties, built from addition, multiplication, and quantifiers. Nothing in its appearance suggests self-reference. But its Gödel number is a number, and the statement, decoded, is a claim about that very number — the claim that no number codes a proof of it. The self-reference is hidden in the coding, invisible to anyone who only looks at the symbols.

9. The Proof, Step by Step
We now have the two ingredients: Gödel numbering, which turns statements and proofs into numbers, and the diagonal argument, which builds a sentence that talks about itself. The proof itself is the assembly of those two ingredients, and it is shorter than you might expect. Gödel's paper is short, and most of it is machinery. The heart of the argument fits in a paragraph. Here it is, built step by step, with no step skipped.
Building the sentence
Start with a formal system F — Peano arithmetic, say, or Principia Mathematica — that is consistent and strong enough to express basic arithmetic. Inside F, consider the property "the number n codes a proof, in F, of the formula with Gödel number m". Because Gödel numbering is mechanical — given the numbers, you can decode them and check the proof, step by step, against the rules — this property can itself be expressed as a formula of arithmetic. Call it Prov(n, m).
Now consider the formula that says "there is no number n such that Prov(n, x)", where x is a free variable. In words, this formula says of a number x: "no proof exists of the formula coded by x". It has one free variable, x, and like every formula, it has a Gödel number of its own. Call that number k. Now feed the formula its own number: substitute k for x. The result is a sentence — a formula with no free variables — and it says: "there is no number n such that Prov(n, k)". But k is the Gödel number of the formula "there is no number n such that Prov(n, x)". So the sentence says, of itself, that no proof of it exists. That sentence is G, the Gödel sentence: "This statement is not provable in F."
That is the diagonal construction, and it is worth pausing on what has happened. We have not written a paradox. We have written a perfectly ordinary arithmetical statement — a long claim about numbers, built from addition, multiplication, and quantifiers — that happens, through the coding, to refer to its own provability.
Case one: suppose F proves G
Now the proof itself, in two cases. Case one: suppose F proves G. Then there is a proof of G, and that proof has a Gödel number, say p. Then Prov(p, k) is true, because p really does code a proof of the formula with Gödel number k — which is G itself. But G says that no such number exists. So if F proves G, then G is false, and F has proved a false statement. But F is consistent, and a consistent system never proves a false statement about the natural numbers. If F proves G, then what G says must be wrong, because G says it is unprovable and here is a proof. So case one is impossible: F cannot prove G.
Case two: suppose F proves not-G
Case two: suppose F proves the negation of G, the statement "not-G" — in effect, "this statement is provable". But we have just shown that G is not provable in F — that was case one. So F would be proving something false again — provided the system is omega-consistent, the slightly stronger assumption Gödel's original proof used: if F proves that a proof exists, then a proof really does exist. Once again, a consistent system cannot prove a false statement. So case two is also impossible: F cannot prove not-G either.
Rosser's 1936 improvement, described in section 6, removes the need for omega-consistency entirely, so that plain consistency is enough. The conclusion is the same either way: neither G nor its negation is provable in F.
What "undecidable" actually means
And now the payoff. G is a statement about the natural numbers. It is true — because it says it is unprovable, and we have just shown, by reasoning about F from outside F, that it is indeed unprovable. And yet F can neither prove it nor disprove it. G is undecidable in F: the system cannot settle it either way.
Notice what "undecidable" means here, because the word is used in two different senses, and confusing them is the most common mistake people make about the theorems. A statement is undecidable in a system if the system can neither prove it nor disprove it. That does not mean the statement is unknowable. We know G is true — we have just proved it, by standing outside F and reasoning about F as a mathematical object. Inside F, G is out of reach. Outside F, in ordinary mathematics, G is settled.
That is the first incompleteness theorem, proved. The argument used nothing special about F except consistency, effectively axiomatisable axioms and rules, and strength enough for arithmetic. Add G as a new axiom, and the enlarged system has a new Gödel sentence of its own. The incompleteness is not a flaw in one system. It is a feature of every system of that kind. Euclid's geometry, built from five postulates, was the first great axiom system in history — our article on Euclidean geometry tells how those five rules built a world — and Gödel's argument shows that no system built on that model, however carefully, can be complete.
10. The Second Incompleteness Theorem
The first incompleteness theorem says that a consistent system strong enough for arithmetic cannot prove every truth. The second says something sharper, and more unsettling: such a system cannot even prove its own consistency. This is the theorem that answered Hilbert's second problem in the negative, and it is the deeper blow, because consistency was the one thing Hilbert cared about most.
The idea is simple to state, and the Stanford Encyclopedia of Philosophy's entry on Gödel's incompleteness theorems gives the careful version. Inside the system F, we can write down a statement, Con(F), that says "F is consistent" — that is, "there is no number that codes a proof, in F, of a contradiction". Con(F) is a statement of arithmetic, like any other, and the question is whether F can prove it. Gödel showed that it cannot, unless F is inconsistent — in which case it proves everything, including Con(F), and the proof is worthless.
Why a system cannot vouch for itself
The reason is a short chain of reasoning. The proof of the first theorem, carried out inside F as far as possible, shows that if F is consistent, then G is true — or rather, it shows that F can prove the conditional statement "if F is consistent, then G is unprovable". That conditional, formalised inside F, is "Con(F) implies G". Now suppose, for the sake of argument, that F could prove Con(F). Then F could combine that proof with the proof of "Con(F) implies G" and conclude G. But the first theorem says F cannot prove G. Contradiction. Therefore F cannot prove Con(F). A consistent system cannot prove its own consistency.
The second theorem, numbered Theorem XI in the 1931 paper, does not say that a system is inconsistent, or that consistency cannot be proved at all. It says that consistency cannot be proved by the system itself, using only its own methods. Consistency can be proved from outside, by a stronger system — Gentzen did exactly that for Peano arithmetic in 1936, as we will see in section 13 — but the stronger system then has the same problem about itself, and the chain never ends.
Hilbert's Problem 2, answered
This is the second of Gödel's incompleteness theorems, and the sense in which Gödel answered Hilbert's second problem. Hilbert had asked for a finitistic proof of the consistency of arithmetic — a proof using only simple, concrete, undoubtable methods. Gödel showed that no proof of consistency can be given inside the system itself. It can be established by stronger means, but then the question simply moves up a level: who certifies the stronger system?
That is why the second theorem is the deeper blow. The first theorem says there are truths a system cannot reach. The second says the system cannot even confirm that it is safe. Hilbert's programme wanted a foundation that could certify itself. Gödel showed that no foundation can.

11. What the Theorems Do NOT Mean
Gödel's incompleteness theorems are among the most misunderstood results in all of science, and the misunderstandings matter, because they are routinely used to support claims the theorems never made. So before we go further, here is what the theorems do not mean — stated plainly, because the precision is the point.
Myth one: mathematics is broken
The most common misunderstanding is that Gödel showed mathematics is broken, unreliable, or somehow wrong. He showed nothing of the kind. The incompleteness theorems are themselves theorems of mathematics, proved with complete rigour, and they say something precise about formal systems: that no consistent system strong enough for arithmetic is complete. Mathematics as a human activity goes on exactly as before. Mathematicians prove theorems, and the theorems are as reliable as they ever were. What changed is our understanding of what a formal system can do. A system cannot prove every truth, but mathematics is not a single system. It is a living activity, carried out by people who can step outside any given system, add new axioms, and prove what the old system could not. The theorems did not break mathematics. They mapped its coastline.
Myth two: truth is relative
The second misunderstanding is that because some truths are unprovable, truth itself must be relative — that anything goes, that all opinions are equal. The Gödel sentence is true, in the ordinary, objective sense: it correctly describes the natural numbers. Its truth is not relative to the system, and we know it by reasoning from outside the system. The theorems do not relativise truth. They separate truth from provability, and they show that truth is the larger concept.
Myth three: machines can never think
The third misunderstanding is the most famous, and the most contested. In 1961, the philosopher J. R. Lucas argued that Gödel's theorems show the human mind cannot be a machine: a human can see that the Gödel sentence is true, while the machine — the formal system — cannot prove it, so the mind must be doing something no machine can do. Roger Penrose later developed a version of the same argument. The argument is ingenious, but it is not a consequence of the theorems. It depends on extra assumptions — that the mind is a consistent formal system, that it knows its own consistency, and that it can be identified with a single fixed system — and most logicians and philosophers of mind reject at least one of them. The theorems say nothing about minds or machines. They say something about formal systems.
Myth four: there are things we can never know
The fourth misunderstanding is the claim that Gödel proved there are things we can never know. The theorems prove that there are statements undecidable in a given system — but a statement undecidable in one system is often provable in a stronger one. Goodstein's theorem, which we will meet in section 13, is unprovable in Peano arithmetic and provable in stronger systems. Undecidable in a system is not the same as unknowable. It means: not provable here, with these axioms. The theorems describe a boundary between systems, not a boundary around human knowledge. And self-reference is not self-similarity: the patterns in our article on fractals repeat a shape at every scale, while a Gödel sentence refers to itself through code.
12. 1936: Church, Turing, and the Decision Problem
Five years after Gödel's paper, the third of Hilbert's three demands fell. The decision problem — the Entscheidungsproblem — asked for a mechanical procedure that could decide, for any mathematical statement, whether it was provable. Hilbert had posed it in 1928, with Wilhelm Ackermann, in their textbook on logic. It was the natural capstone of the programme: if mathematics could be formalised, and if proofs could be checked mechanically, then surely a machine could be built that would decide, for any statement, whether a proof existed. In 1936, two men, working independently and by different routes, showed that no such machine can exist.
Church's lambda calculus
The first was Alonzo Church, at Princeton. Church had invented a system called the lambda calculus, a spare, elegant notation for describing functions and computation, and in a paper published on 15 April 1936 in the American Journal of Mathematics — "An Unsolvable Problem of Elementary Number Theory" — he proved that there is no mechanical procedure that decides, for every statement of elementary number theory, whether it is provable. In a short companion note, "A Note on the Entscheidungsproblem", received the same day, Church extended the result to first-order logic and drew the explicit conclusion: the Entscheidungsproblem itself has no solution. The paper introduced the lambda calculus as a definition of what it means for something to be computable. Church's route was through logic and functions. Turing's route, taken a few weeks later, was through machines.
Turing's machine
Alan Turing was twenty-three years old, a fellow at King's College, Cambridge, when he submitted his paper, "On Computable Numbers, with an Application to the Entscheidungsproblem", on 28 May 1936. It appeared in the Proceedings of the London Mathematical Society later that year, in two parts, running to thirty-six pages. Turing's paper invents the computer — not as a physical device, but as an idea. A Turing machine is an imaginary device with an infinitely long tape, divided into squares, and a read-write head that can read a symbol, write a symbol, and move left or right, following a finite table of instructions. Turing showed that it captures exactly the idea of a mechanical procedure: anything that can be computed by any mechanical means can be computed by a Turing machine.
And then Turing proved the halting problem has no solution: no general mechanical procedure can look at a programme and its input and decide whether the programme will ever stop. If there were, you could use it to solve the decision problem, and Church had already shown that has no solution. The halting problem is the computational cousin of the Gödel sentence, and the argument, like Gödel's, turns on self-reference — the diagonal trick again, in a new costume.
The connection between the two 1936 papers is the Church–Turing thesis: the claim that the lambda calculus and the Turing machine define the same class of computable functions, and that this class is exactly the class of functions computable by any effective procedure. The thesis is not a theorem — "effective procedure" is an informal idea — but it is one of the most widely accepted claims in mathematics, and it is the foundation of computer science. Two independent definitions of computability, invented in the same year, turned out to coincide.
The computer is born from a question about logic
Hilbert's decision problem was a question about the foundations of mathematics, posed by a man who wanted to secure mathematics forever. The attempt to answer it created the theory of computation, and the theory of computation created the computer. The machine on which you are reading this article is a descendant of a device invented to answer a question about logic — a question whose answer was no. Between them, Gödel's incompleteness theorems and the results of 1936 drew the boundary of what formal reasoning can do, and in doing so they invented the science that would define the next century.
The Königsberg of 1930 was also the Königsberg of the bridges: Euler's solution to the bridge problem invented a whole new branch of mathematics by treating a puzzle as a question about what moves are legal — the story our article on graph theory tells. Turing's machine is that idea applied to computation itself.

13. After Gödel: Gentzen, Cohen, and the Limits That Kept Coming
Gödel's incompleteness theorems did not end the story. In the decades that followed, mathematicians found that incompleteness and undecidability were not isolated curiosities but a landscape, and they mapped it, result by result. Here are the landmarks.
Gentzen and the ordinal epsilon-zero
The first landmark came in 1936, the same year as Church and Turing. Gerhard Gentzen, a young German logician, proved that Peano arithmetic is consistent — the very thing Hilbert had wanted, and the very thing Gödel's second theorem said the system could not prove about itself. Gentzen's proof used transfinite induction up to the ordinal epsilon-zero, written ε0. ε0 is the first ordinal α with ω raised to the power α equal to α — the limit of ω, ω to the power ω, and so on, climbing forever. Gentzen showed that if you are allowed induction up to ε0, you can prove the consistency of arithmetic. The proof does not contradict Gödel's second theorem, because the method is stronger than the methods of Peano arithmetic itself: a proof from outside, by a stronger system, exactly as the second theorem requires. And ε0 is, in a precise sense, the exact amount of extra strength needed. The limit has a shape, and Gentzen found it.
The continuum hypothesis: independent at last
The second landmark concerns the first problem on Hilbert's 1900 list: the continuum hypothesis, Cantor's question of whether any infinity lies strictly between the whole numbers and the real numbers. Gödel himself made the first move. In 1940, in a short monograph published by Princeton University Press, he showed that the continuum hypothesis is consistent with the standard axioms of set theory: he built a model of set theory, the constructible universe, usually called L, in which the continuum hypothesis holds, so it cannot be disproved from the axioms. Twenty-three years later, in 1963, Paul Cohen completed the picture. Cohen invented a technique called forcing, and used it to build a model of set theory in which the continuum hypothesis fails, so it cannot be proved from the axioms either. The continuum hypothesis is independent of the standard axioms: it can neither be proved nor disproved from them. Cohen won the Fields Medal in 1966 for the work.
Tarski, Löb, and the shape of truth
The third landmark is Alfred Tarski's undefinability of truth, published in 1936. Tarski showed that truth, for a formal language, cannot be defined inside that language. A system can talk about provability, as Gödel showed, but it cannot talk about truth — not without contradiction. The liar paradox is the reason: a sentence that says "this sentence is false" breaks truth, and Tarski's theorem is the precise, general version of that observation.
The fourth landmark is Löb's theorem, proved by Martin Löb in 1955. Löb showed that if a system can prove the statement "if this sentence is provable, then it is true", then it can prove the sentence itself. The consequence is serious: a system cannot prove its own soundness — the claim that everything it proves is true — without collapsing into inconsistency. It is another way of saying that a system cannot certify itself, and it closes a loophole that Gödel's second theorem had left open.
Goodstein's theorem, and the whiteboard
The fifth landmark is the one I like best, because it is the most concrete. In 1944, the English mathematician Reuben Goodstein defined a sequence of numbers that seems, at first sight, to grow forever, and yet always reaches zero. The rule is simple to state and strange to believe. Take a number, write it in base 2, replace every 2 by a 3, and subtract 1. Then write the result in base 3, replace every 3 by a 4, and subtract 1. Then base 4, then base 5, and so on, the base climbing by one at every step. The numbers grow — the sequence starting at 4 goes 4, 26, 41, 60, 83, 109, 139, and keeps climbing for an enormously long time — and yet Goodstein proved that every such sequence eventually reaches zero. The proof needs transfinite induction, like Gentzen's, and in 1982 Laurie Kirby and Jeff Paris proved that Goodstein's theorem is unprovable in Peano arithmetic. Here, at last, is an undecidable statement that is not a clever self-referential trick but an ordinary claim about numbers. The incompleteness is not confined to sentences about provability. It reaches into ordinary arithmetic.
I once wrote the first few terms of the Goodstein sequence for 4 on a whiteboard, in front of a small audience, and watched the room go quiet as the numbers climbed: 4, 26, 41, 60, 83, 109, 139. Someone asked when it would come down. The honest answer — that it climbs for longer than any human can follow, and yet certainly reaches zero, and yet Peano arithmetic cannot prove that it does — is the whole story of incompleteness in miniature.
Chaitin and the limits of information
The sixth landmark is Gregory Chaitin's work on algorithmic information theory, in a 1974 paper. Chaitin showed that a formal system of a given size — measured in bits — cannot prove that a string of symbols has a complexity much greater than the size of the system itself. A short system cannot prove that a long string is random, because the proof would have to contain, in effect, the information it is trying to certify. It is Gödel's theorem in the language of information: the number of bits in your axioms limits the complexity of the truths you can prove. A fuller history is given in the Stanford Encyclopedia of Philosophy's entry on Hilbert's program.
| Year | Result | What it showed |
|---|---|---|
| 1879 | Frege's Begriffsschrift | Logic itself could be formalised. |
| 1889 | Peano's axioms | Arithmetic set down as a short list of axioms plus induction. |
| 1900 | Hilbert's 23 problems | Problem 2 asks for a proof that arithmetic is consistent. |
| 1901 | Russell's paradox (discovered) | Naive set theory is inconsistent. |
| 1910–13 | Principia Mathematica | Mathematics rebuilt from logic; 1 + 1 = 2 at 54.43. |
| 1931 | Gödel's incompleteness theorems | No consistent system for arithmetic is complete, or can prove its own consistency. |
| 1936 | Church and Turing | The decision problem has no solution; halting is undecidable. |
| 1936 | Gentzen | Arithmetic is consistent — proved with induction up to ε0. |
| 1936 | Tarski | Truth cannot be defined inside the language it describes. |
| 1940 | Gödel | The continuum hypothesis is consistent with the axioms of set theory. |
| 1955 | Löb | A system cannot prove its own soundness. |
| 1963 | Cohen | The continuum hypothesis is independent. |
| 1974 | Chaitin | A system cannot prove complexity much beyond its own size in bits. |
| 1982 | Kirby and Paris | Goodstein's theorem is unprovable in Peano arithmetic. |
Table 2: A timeline of the limits, from Frege's formalisation of logic in 1879 to the proof in 1982 that Goodstein's theorem is unprovable in Peano arithmetic.
14. Why It Matters Today
Gödel's incompleteness theorems are nearly a century old, and they are not museum pieces. They shape the tools mathematicians use today, the limits of software verification, and the oldest question about artificial intelligence. Here is where the theorems live now.
Proof assistants
The most direct descendant of Hilbert's programme is the proof assistant: software that checks mathematical proofs, step by step, with the rigour of a formal system. Lean, Coq, and Isabelle are the best known, and they are used to verify some of the most difficult proofs in mathematics — the four-colour theorem, the Kepler conjecture, parts of the classification of finite simple groups. A proof assistant is, in effect, a formal system with a friendly interface, and it inherits exactly the properties Gödel proved: it can check any proof you give it, and it can never prove every truth. The assistant is a tireless, exact checker, not an oracle. The hope of a machine that settles every mathematical question died in 1936. The reality of machines that check our proofs, tirelessly and exactly, is one of the great achievements of modern mathematics. The idea of a limit — what a process approaches but never reaches — is the subject of our article on how calculus works, and Gödel's theorems are a limit of a different kind: a limit on what proof itself can reach.
Software that checks itself
The same limits apply to software verification, the attempt to prove that a programme does what it is supposed to do. For safety-critical software — the code in an aeroplane, a medical device, a nuclear plant — engineers would like a guarantee, a proof that the programme cannot fail. Gödel's theorems, and the halting problem, say that no general guarantee is possible: there is no mechanical procedure that can verify every programme. What is possible is verification of particular programmes, in particular systems, with particular properties — and that is an active, successful field. The limits do not stop the work. They define it.
In logic, the question is what stays provable when a system is stretched by new axioms — and the answer, again and again, is that something always stays out of reach. It is the same shape of question as in topology, where the question is what stays the same when everything else is stretched.
AI and the old question
The oldest question the theorems touch is the one about artificial intelligence: can a machine think, understand, or know itself? Gödel's theorems do not answer it, as section 11 explained, but they set the terms of the debate. Any AI built on formal reasoning inherits the limits of formal reasoning: it cannot prove its own consistency, and it cannot settle every question in its own system. Modern AI systems are not formal systems in Gödel's sense — they are statistical, learned, and messy — but the question of whether a machine can fully understand itself is the same question Gödel posed in 1931, in a new costume.
In a letter to John von Neumann dated 20 March 1956, Gödel asked whether a machine could find a proof of length n in time that grows only polynomially with n — an early form of the question now known as P versus NP, one of the great open problems of computer science. Gödel was thinking about the limits of computation a quarter of a century before the field existed.

15. The Man After the Theorem
Gödel's life after 1931 is a story of honours and of retreat. He visited the Institute for Advanced Study in Princeton in 1933, and emigrated to the United States in 1940, travelling by the Trans-Siberian Railway and across the Pacific, a long and anxious journey in wartime. He became a permanent member of the Institute in 1946, and a full professor in 1953. He won the Albert Einstein Award in 1951 and the National Medal of Science in 1974. And he worked, steadily and quietly, on the deepest problems in logic and set theory, including the continuum hypothesis, which he had already advanced in 1940.
He also became, in his later years, a more private and more fearful man. He was a close friend of Albert Einstein, and the two of them walked together most days around the Institute grounds. Einstein once said that he went to the Institute mainly for the privilege of walking home with Gödel. In 1949, Gödel found a solution to Einstein's equations of general relativity that described a rotating universe — a universe in which time travel would be possible, in principle.
The citizenship exam
The most famous story from Gödel's later life is also the most revealing. On 5 December 1947, Gödel took his examination for American citizenship, with Einstein and the economist Oskar Morgenstern as his witnesses. On the way, Gödel told his friends that he had studied the United States Constitution and had found a logical flaw in it — a route by which it could be turned, legally, into a dictatorship. Einstein and Morgenstern spent the journey trying to distract him, afraid he would raise the point with the examiner. At the examination, the judge remarked that a dictatorship could not happen in America, and Gödel, unable to resist, began to explain that it could, and how. Morgenstern quickly intervened, the judge laughed, and Gödel became an American citizen. The story is told in many versions, and the details vary, but the shape of it is right, and the shape is the point: Gödel could not help seeing the logical structure of a thing, even when the thing was a constitution and the occasion was his own citizenship examination. It is the same habit of mind that found the incompleteness in Principia Mathematica.
I have always thought that story is the best portrait of the man. Not the recluse of his final years — he died in Princeton on 14 January 1978, aged seventy-one, after a long illness during which his fear of being poisoned led him to eat almost nothing — but the young man who looked at the most careful system ever built and asked, quietly, whether it could really do everything it claimed. The answer was no, and the no changed mathematics. The fullest account of his life is given in the MacTutor biography of Kurt Gödel, and the Encyclopaedia Britannica's entry on Kurt Gödel gives a concise summary of the life and the work.
A note on the later years
It would be dishonest to end this section without acknowledging that Gödel's later life was marked by serious mental illness, and that he died, in part, because of it. The fear of poisoning, the refusal of food, the withdrawal from the world — these are not footnotes to a genius, and they are not the explanation of the genius either. The theorems do not belong to the illness. They belong to the young man of 1930, who was healthy, clear-eyed, and exact.
16. The Limits of Proof — and What Remains
So what remains, after Gödel? A great deal. The incompleteness theorems did not end mathematics. They did not make proof unreliable, truth relative, or knowledge impossible. They did something subtler and more valuable: they mapped the coastline of formal reasoning. They showed that no single formal system can capture all of arithmetic truth, that no system can certify its own consistency, and that no mechanical procedure can decide every question. And in showing that, they gave birth to mathematical logic as a modern subject, to the theory of computation, and to the computer.
The theorems are, in the end, a story about limits, and limits are not defeats. A map that shows where the land ends is more useful than a map that pretends the land goes on forever. Hilbert wanted a foundation that could prove everything, and he did not get it. What he got instead was better: a precise understanding of what foundations can and cannot do, and a new science — the science of computation — built on the attempt.
If you take one idea away from this article, let it be this: Gödel's incompleteness theorems are not a counsel of despair. They are a precise, beautiful, and ultimately optimistic result. They say that mathematics is larger than any system we can write down, that truth is larger than proof, and that the work of mathematics — of finding new axioms, new methods, new ways of seeing — can never be finished by a machine, because it can never be finished at all. There will always be more to discover. The limits of proof are also the guarantee that the subject will never run out.
That is the answer to the question with which we began: can mathematics prove everything? No. And the no is the beginning, not the end. Gödel's incompleteness theorems showed us the edge of the map, and beyond the edge, the territory goes on.
Frequently Asked Questions
What did Gödel prove?
Gödel's incompleteness theorems are two theorems about formal systems, proved in 1931. The first says that any consistent formal system strong enough to express basic arithmetic contains a true statement about the natural numbers that the system can neither prove nor disprove. The second says that such a system cannot prove its own consistency. Together, they show that no single formal system can capture all of arithmetic truth.
Can mathematics prove everything?
No. Gödel's incompleteness theorems show that no consistent formal system strong enough for arithmetic can prove every true statement about the natural numbers. But statements unprovable in one system are often provable in a stronger one, and mathematicians prove things from outside systems all the time — including the incompleteness theorems themselves.
What is a formal system?
A formal system is a game with written rules: an alphabet of symbols, a grammar saying which strings of symbols count as statements, a set of axioms accepted without proof, and rules of inference that tell you how to derive new statements from old ones. A proof is a sequence of legal moves from the axioms to the statement you want. Peano arithmetic, the system for ordinary whole-number arithmetic, is the running example in this article.
Can a system prove its own consistency?
No — not if it is consistent and strong enough for arithmetic. That is Gödel's second incompleteness theorem. A system can prove the consistency of a weaker system, and its own consistency can be proved from outside, by a stronger system — Gentzen did this for Peano arithmetic in 1936 — but the stronger system then needs one above it in turn. The chain never ends.
Does Gödel's theorem mean maths is broken?
No. Gödel's incompleteness theorems are themselves rigorous theorems of mathematics, and they say something precise about formal systems, not about mathematics as a whole. Mathematics is not a single formal system. It is a living activity, and mathematicians work by stepping outside any given system, adding new axioms, and proving what the old system could not. The theorems mapped the limits of formal systems. They did not break mathematics.
What is the Gödel sentence?
The Gödel sentence, usually written G, is a statement about the natural numbers that says, in effect, "This statement is not provable in the system F." It is built using Gödel numbering, which turns statements and proofs into numbers, and the diagonal argument, which lets a sentence refer to itself. G is true — because F really cannot prove it — and yet F can neither prove it nor disprove it. It is the sentence whose existence proves the first incompleteness theorem.
Did Gödel prove that computers can never think?
No. Gödel's theorems say nothing about minds or machines. They say something about formal systems. The argument that the theorems show the human mind is not a machine — made by J. R. Lucas in 1961 and later by Roger Penrose — depends on extra assumptions that most logicians and philosophers reject. Whether machines can think is a question for philosophy and neuroscience, and Gödel's theorems do not settle it.
Is the continuum hypothesis true?
That depends on what you mean by "true". The continuum hypothesis — that there is no infinity strictly between the countable infinity of the whole numbers and the infinity of the real numbers — can neither be proved nor disproved from the standard axioms of set theory. Gödel showed in 1940 that it is consistent with those axioms, and Cohen showed in 1963 that its negation is consistent with them too. Whether it is true in some absolute sense is a question mathematicians still debate, and it depends on which axioms you accept.
Sources
- 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. DOI: 10.1007/BF01700692
- Kurt Gödel, "Die Vollständigkeit der Axiome des logischen Funktionenkalküls", Monatshefte für Mathematik und Physik 37 (1930), 349–360. (Journal version of his 1929 doctoral dissertation, "Über die Vollständigkeit des Logikkalküls", University of Vienna.) DOI: 10.1007/BF01696781
- Panu Raatikainen, "Gödel's Incompleteness Theorems", Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/entries/goedel-incompleteness/
- Richard Zach, "Hilbert's Program", Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/entries/hilbert-program/
- David Hilbert, "Mathematical Problems", lecture at the International Congress of Mathematicians, Paris, 1900; English translation by Mary Frances Winston Newson, Bulletin of the American Mathematical Society 8 (1902), 437–479. DOI: 10.1090/S0002-9904-1902-00923-3
- Bertrand Russell, letter to Gottlob Frege, 16 June 1902, in Jean van Heijenoort (ed.), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, 1967.
- Alfred North Whitehead and Bertrand Russell, Principia Mathematica, Volume I, Cambridge University Press, 1910; Volume II, 1912; Volume III, 1913.
- J. Barkley Rosser, "Extensions of Some Theorems of Gödel and Church", Journal of Symbolic Logic 1(3) (1936), 87–91. DOI: 10.2307/2269028
- Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics 58(2) (1936), 345–363. DOI: 10.2307/2371045
- Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936–37), 230–265. DOI: 10.1112/plms/s2-42.1.230
- Gerhard Gentzen, "Die Widerspruchsfreiheit der reinen Zahlentheorie", Mathematische Annalen 112 (1936), 493–565. DOI: 10.1007/BF01565428
- Alfred Tarski, "Der Wahrheitsbegriff in den formalisierten Sprachen", Studia Philosophica 1 (1936), 261–405.
- Kurt Gödel, "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory", Annals of Mathematics Studies No. 3, Princeton University Press, 1940.
- Martin Löb, "Solution of a Problem of Leon Henkin", Journal of Symbolic Logic 20(2) (1955), 115–118. DOI: 10.2307/2266895
- Paul Cohen, "The Independence of the Continuum Hypothesis", Proceedings of the National Academy of Sciences 50(6) (1963), 1143–1148. DOI: 10.1073/pnas.50.6.1143
- Gregory Chaitin, "Information-Theoretic Limitations of Formal Systems", Journal of the ACM 21(3) (1974), 403–424. DOI: 10.1145/321832.321839
- Laurie Kirby and Jeff Paris, "Accessible Independence Results for Peano Arithmetic", Bulletin of the London Mathematical Society 14 (1982), 285–293. DOI: 10.1112/blms/14.4.285.
- John W. Dawson Jr., Logical Dilemmas: The Life and Work of Kurt Gödel, A. K. Peters, 1997.
- Ernest Nagel and James R. Newman, Gödel's Proof, New York University Press, 1958.
- Rebecca Goldstein, Incompleteness: The Proof and Paradox of Kurt Gödel, W. W. Norton, 2005.
- O'Connor and Robertson, "Kurt Gödel", MacTutor History of Mathematics Archive, University of St Andrews. https://mathshistory.st-andrews.ac.uk/Biographies/Godel/
- "Kurt Gödel", Encyclopaedia Britannica. https://www.britannica.com/biography/Kurt-Godel
- Stephen Cole Kleene, Introduction to Metamathematics, North-Holland, 1952.
- Peter Smith, An Introduction to Gödel's Theorems, 2nd edition, Cambridge University Press, 2013.
- Torkel Franzén, Gödel's Theorem: An Incomplete Guide to Its Use and Abuse, A. K. Peters, 2005.
- Alonzo Church, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic 1(1) (1936), 40–41. DOI: 10.2307/2269326.
