Godel's Incompleteness Theorems

The Limits of Proof

Can mathematics prove everything that is true?

In the early 1900s, mathematicians believed the answer was yes. David Hilbert, one of the greatest mathematicians of his time, championed a bold vision: to establish a complete and consistent foundation for all of mathematics. Every true statement would be provable. Every false statement would be disprovable. Mathematics would be a perfect, self-contained system.

In 1931, a 25-year-old Austrian logician named Kurt Godel published a paper that shattered this dream. He proved, with mathematical rigor, that Hilbert's program was impossible. Not difficult. Not impractical. Impossible.

Godel showed that any mathematical system powerful enough to express basic arithmetic must be either incomplete (unable to prove all truths) or inconsistent (able to prove contradictions). Since we certainly want consistency, incompleteness is unavoidable. There will always be true statements that cannot be proven.

This page will walk you through the actual construction, step by step. By the end, you will understand not just what Godel proved, but how he proved it.

Formal Systems: The Rules of the Game

Before we can understand what Godel proved, we need to understand what he was talking about: formal systems.

A formal system is like a game with very precise rules. It has three components:

• Axioms: Starting truths we accept without proof. These are the foundation, the bedrock assumptions we build upon.
• Inference rules: Logical rules that tell us how to derive new truths from existing ones. If we know A and we know "A implies B," we can conclude B.
• Theorems: Statements we can prove by starting from axioms and applying inference rules step by step.

The power of formal systems is that proofs become mechanical. No intuition required, no leaps of faith. Just follow the rules.

The tree above shows how a simple theorem is built from axioms. Each step follows strict logical rules. This mechanical nature is what makes formal systems powerful and what Godel exploited to prove his theorems.

For the rest of this page, we will work with a formal system called Peano Arithmetic (PA), which captures the basic properties of natural numbers: 0, 1, 2, 3, and so on, along with addition and multiplication.

The Liar's Paradox: A Dangerous Idea

To understand Godel's insight, we first need to meet an ancient troublemaker: the Liar's Paradox.

Consider this statement: "This statement is false."

Think about it carefully. Is it true or false?

• If the statement is true, then what it says must be correct. But it says it's false. So it must be false.
• If the statement is false, then what it says is wrong. But it says it's false, so if that's wrong, it must be true.

Neither answer works. The statement cannot be consistently assigned a truth value. It breaks logic itself.

The Liar's Paradox has been known since ancient Greece, and philosophers have debated it for millennia. Most dismissed it as a curiosity, a trick of language. Godel saw something deeper: the power of self-reference.

But you cannot write "This statement is false" in the language of arithmetic. Numbers do not talk. So Godel needed a way to make arithmetic talk about itself.

Part I: Godel Numbering

Step 1: Assign Numbers to Symbols

The first step is to assign a unique number to every symbol in our formal language. This is arbitrary but must be consistent.

Every symbol gets a number. The logical symbols get small numbers. Variables get prime numbers starting from 13 (we will see why primes matter soon).

With this assignment, any sequence of symbols becomes a sequence of numbers. For example:

• The formula 0 = 0 becomes the sequence [6, 5, 6]
• The formula s(0) = s(0) (meaning 1 = 1) becomes [7, 8, 6, 9, 5, 7, 8, 6, 9]

Step 2: Encode Sequences as Single Numbers

A sequence of numbers is not yet a single number. We need a way to encode any sequence as one unique number that we can later decode.

Godel used prime factorization. The Fundamental Theorem of Arithmetic tells us that every positive integer has a unique prime factorization. We exploit this:

To encode the sequence $[a_1, a_2, a_3, \ldots, a_n]$, compute:

where $p_n$ is the $n$-th prime number.

For example, the formula 0 = 0 with symbol sequence [6, 5, 6] becomes:

This number 243,000,000 is the Godel number of the formula "0 = 0".

Try encoding different formulas. Notice how each formula gets a unique Godel number. We can also go backwards: given 243,000,000, we can factor it to recover [6, 5, 6], then look up the symbols to get "0 = 0".

Step 3: Arithmetic Can Talk About Syntax

Here is the key insight: once formulas are numbers, statements about formulas become statements about numbers.

Consider the metamathematical statement: "The first symbol of formula X is a tilde."

Since formulas are now Godel numbers, this becomes: "When you factor the number X, the exponent of 2 (the first prime) equals 1 (the code for tilde)."

This is a purely arithmetic statement. We can write it in the language of PA itself.

More powerfully, consider: "Formula X is provable in the system."

A proof is a sequence of formulas (each step in the proof). So a proof is a sequence of Godel numbers, which itself has a Godel number. "X is provable" means "there exists a number P that encodes a valid proof ending in X."

We can define an arithmetic predicate:

This is complicated to write out fully, but the crucial point is: it can be written in the language of arithmetic. The predicate $\text{Provable}(x)$ is expressible as an arithmetic formula.

Part II: The Substitution Function

Step 4: Defining Substitution

Here is where things get clever. We need to define a function that takes:

• The Godel number of a formula $\varphi(y)$ with a free variable $y$
• A number $n$

And returns the Godel number of the formula $\varphi(n)$, where we have substituted the numeral for $n$ in place of the variable $y$.

In Godel's original paper, the variable $y$ was assigned Godel number 17. So the substitution function is written:

This means: "Take the formula with Godel number $m$, find every occurrence of the variable with code 17 (that is, $y$), and replace it with the numeral representing $n$. Return the Godel number of the resulting formula."

Step 5: Sub is Arithmetic

The function $\text{Sub}(m, 17, n)$ looks complicated, but it is primitive recursive, meaning it can be computed by a definite algorithm using only basic operations. More importantly, it can be represented within arithmetic.

There exists an arithmetic formula $\text{sub}(m, n, r)$ such that:

The formal system PA can "compute" substitution using only its own language. This is not magic; it is a consequence of the fact that primitive recursive functions can be expressed in arithmetic.

Part III: Constructing the Godel Sentence

Now we have all the pieces. Let us build the sentence that says "I am not provable."

Step 6: The Unprovability Predicate

Define a formula $P(y)$ that says "the formula with Godel number $y$ is not provable":

This formula has one free variable, $y$. Let the Godel number of this formula $P(y)$ be $p$.

Step 7: The Diagonalization

Now we apply the substitution function to create self-reference.

Consider: what happens if we substitute $p$ (the Godel number of $P(y)$) for the variable $y$ in the formula $P(y)$ itself?

We get the formula $P(p)$, which says:

"The formula with Godel number $p$ is not provable."

But wait. The formula with Godel number $p$ is $P(y)$. So $P(p)$ says:

"$P(y)$ is not provable."

That is still not quite self-referential. We need to go one step further.

Step 8: The Godel Sentence G

Define $G$ as follows:

Unpacking this:

• Start with the formula $P(y)$, which has Godel number $p$
• Compute $\text{Sub}(p, 17, p)$: substitute $p$ for $y$ in $P(y)$, getting the formula $P(p)$
• Let $g = \text{Sub}(p, 17, p)$ be the Godel number of $P(p)$
• Then $G$ is the formula $P(g)$, which says "the formula with Godel number $g$ is not provable"

But $g$ is the Godel number of $P(g)$ itself. So $G$ says:

"The formula with Godel number $g$ is not provable" where $g$ is the Godel number of this very formula.

In other words: G says "G is not provable."

Step 9: The Diagonal Lemma (Why This Works)

What we just did is an instance of the Diagonal Lemma, which states:

For any formula $\varphi(x)$ with one free variable, there exists a sentence $G$ such that the system proves: $G \leftrightarrow \varphi(\ulcorner G \urcorner)$

where $\ulcorner G \urcorner$ denotes the Godel number of $G$.

We applied this with $\varphi(x) = \neg \text{Provable}(x)$, obtaining a sentence $G$ that is equivalent to $\neg \text{Provable}(\ulcorner G \urcorner)$.

The diagonal lemma is the formal heart of self-reference in arithmetic.

Part IV: The Incompleteness Argument

Step 10: Analyzing G

Now we have a sentence $G$ that says "G is not provable in PA." Let us think carefully about what this means.

Case 1: Suppose PA proves G.

If PA proves $G$, then $G$ is provable. But $G$ says "G is not provable." So PA has proven a false statement. This means PA is inconsistent, it proves falsehoods.

Case 2: Suppose PA does not prove G.

If PA does not prove $G$, then "G is not provable" is true. Since that is exactly what $G$ says, $G$ is a true statement. So we have a true statement that PA cannot prove.

Conclusion: If PA is consistent, then $G$ is true but unprovable.

Step 11: The First Incompleteness Theorem

We have just proven:

First Incompleteness Theorem: Any consistent formal system capable of expressing basic arithmetic contains true statements that cannot be proven within the system.

The system is incomplete. Not because we haven't worked hard enough, but because incompleteness is mathematically unavoidable.

Step 12: What About the Negation?

You might wonder: if PA cannot prove $G$, can it prove $\neg G$ (the negation of G)?

$\neg G$ says "G is provable." If PA proved $\neg G$, then PA would assert that $G$ is provable. But we established that $G$ is actually not provable (assuming consistency). So PA would be proving something false.

Therefore, if PA is consistent, it cannot prove $\neg G$ either.

This means $G$ is independent of PA: neither $G$ nor $\neg G$ is provable. The system cannot decide the truth of $G$.

Part V: The Second Incompleteness Theorem

Step 13: Formalizing Consistency

A system is consistent if it does not prove a contradiction. We can express this:

"PA is consistent" means "PA does not prove 0 = 1" (or any other obvious falsehood).

This is an arithmetic statement. The system can talk about its own consistency.

Step 14: Consistency Implies G

Look back at our argument. We showed:

If PA is consistent, then G is not provable.

This argument used only arithmetic reasoning, reasoning that PA itself can carry out. So PA can prove:

Step 15: The Bootstrap Problem

Now suppose PA could prove its own consistency:

Combined with Step 14, by modus ponens, PA would prove:

But we showed that if PA is consistent, PA cannot prove G. Contradiction.

Step 16: The Second Incompleteness Theorem

Second Incompleteness Theorem: No consistent formal system capable of expressing basic arithmetic can prove its own consistency.

A system cannot lift itself by its own bootstraps. To prove that PA is consistent, you need a stronger system, but that stronger system then cannot prove its own consistency.

What This Means

Godel's theorems are not about the limitations of human intelligence or the impracticality of certain proofs. They are about fundamental, unavoidable limits of formal reasoning.

For mathematics: There will always be truths that lie beyond any given proof system. Mathematics is not a closed book waiting to be read; it is an infinite landscape that no map can fully capture.

For computers: Godel's ideas led directly to the theory of computation. Alan Turing, inspired by Godel, proved that some problems are fundamentally undecidable. The Halting Problem, which asks whether a program will eventually stop, is the most famous example. The proof uses the same diagonal trick.

For philosophy: We cannot have a complete, consistent, self-verifying foundation for mathematics. Any foundation we choose will have truths it cannot reach and consistency it cannot prove. This is not a flaw to be fixed; it is the nature of formal systems.

Godel did not show that mathematics is broken. He showed that mathematics is deeper than any single formal system can capture. That is not a limitation. It is a kind of mathematical infinity.

Key Takeaways

• Godel numbering assigns unique numbers to formulas, allowing arithmetic to talk about itself
• The substitution function $\text{Sub}(m, 17, n)$ computes the Godel number of a formula with a value substituted in
• The Godel sentence $G$ is constructed via diagonalization: $G = P(\text{Sub}(p, 17, p))$
• $G$ says "I am not provable," which is true but unprovable in any consistent system
• The First Theorem: Consistent systems have true-but-unprovable statements
• The Second Theorem: Consistent systems cannot prove their own consistency
• These are structural limitations of formal systems, not human limitations