Gödel's Incompleteness Theorems Explained Simply

Why Math Will Always Be Broken - Part 2

After introducing the theorems and explaining every part of them, we are going to the second, and more difficult part. The proof. The good news is, you don’t need to learn any other definitions for proving the theorems.

Bad news is, there will be a little mental gymnastics happening, so get your brain cells ready. :)

---

First, A Quick Recap

This is the first part,:

Gödel's Incompleteness Theorems Explained Simply

In Part 1, we talked about what Gödel’s theorems say: that any formal system powerful enough to describe arithmetic will always be incomplete. That means there are true statements that can’t be proved.

Before the proof, I also want to address one more question that might arise from part 1. That is, why are we talking just about arithmetic when stating and proving such serious theorems? If math is so big, how can Gödel’s theorems talk only about simple systems like Peano Arithmetic? Isn’t that too weak?

Why Elementary Arithmetic Is Enough

Peano Arithmetic (PA) is one of the simplest formal systems that can describe the basic structure of natural numbers: zero, successors, addition, and multiplication. And yet, even this tiny foundation is enough to carry out the kind of reasoning Gödel needs. It’s because PA (which I use here interchangeably with “elementary arithemtic) is maybe a small bunch of axioms, but powerful enough to express basic arithmetic truths, encode statements about statements, encode proofs, or support mathematical induction.

Once a system like PA can represent simple statements about numbers and logic, it’s already expressive enough to be vulnerable to Gödel’s technique! So actually, once we prove the theorems in this language, we can prove them in “stronger” axioms.

Gödel’s results don’t just apply to PA, they apply to any system strong enough to include PA. And that means almost all of math. And, maybe counter-intuitively, it’s because other systems are “bigger” than PA, and they somehow contain PA.

So yes, basic arithmetic really is the doorway into proving big truths about logic, provability, and the limits of formal systems.

---

How The Proof Works:

First, Encoding Math as Numbers

Gödel found a way to represent statements about math as statements inside math. Don’t worry, the proof actually isn’t difficult to understand.

The proof starts with a very clever trick. The proof is very, very numerical. We will be multiplying and raising numbers to powers.

Gödel found a way to encode every symbol, expression, and even sequence of mathematical formulas as a unique number! (These numbers are called Gödel numbers.)

First, he assigned a number to the simple symbols:

That’s clear, but how do we encode, for example, statements like 0 = 0, or 1 + 1 = 2? (Which is written as s(0) + s(0) = s(s(0))). Recall that we are using Peano arithmetic here, you can take a look at how I explained that inthe previous article:

Gödel's Incompleteness Theorems Explained Simply

To understand better, if you have a piece of paper, I want you to write a list of prime numbers:

2 3 5 7 11 13 17 19….

Now, if we want to encode a statement, let’s say 0 = 0, we look at the table to find numbers for the symbols… Which is 6, 5, and 6 again, respectively.

We then raise the first integers in the row to the power of these numbers:

2⁶ 3⁵ 5⁶.

And, finally, we multiply these powers of integers.

0 = 0 becomes 2⁶ × 3⁵ × 5⁶ = 243,000,000.

This way, every statement that uses symbols from the table. But it’s not just a smart way to encode all that math. It’s also unique! It’s because if we take any number, e.g., 243,000,000, it has only one way to decompose into powers of prime numbers. That’s just a fact. So we can be sure that no number represents more different statements.

---

Encoding Statements ABOUT Other Statements

So far, we’ve encoded symbols and formulas into numbers. Now we go meta.

Gödel shows that even statements about statements — like “This formula is provable” — can themselves be written as arithmetic formulas. This is sometimes called arithmetizing metamathematics (but to keep some remains of our sanity, I will call it informally “encoding statements as Gödel numbers”, “assigning numbers to math formulas”, etc.)

Take a simple (false) formula like ~(0 = 0).

To assign a Gödel number to the whole formula, we again,

• Take the primes in their order: 2, 3, 5, 7, 11, 13, ...

• Raise each to the power of the corresponding symbol's Gödel number

• Multiply them all together

So the Gödel number of ~(0 = 0) is:

2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ (You can check this in the table).

This unique number encodes the formula completely, and thanks to the uniqueness of prime factorization, there’s only one way to decode it.

Now comes the trick! We can formulate meta-statements about this formula in terms of its Gödel number. For example, the factual statement:

“The first symbol of the formula ~(0 = 0) is a tilde.”

…is actually an arithmetical statement about the number 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹: namely, that this huge number has exactly one factor of 2. (Factor means how many 2’s we multiply there. There’s just 2¹, so 2 has a factor 1).

So the trick is that a meta-level observation becomes an arithmetic fact about prime exponents. This is the core trick: we can “talk about” formulas using just numbers.

Another example: We can write:

“There exists a sequence of formulas (Gödel number = x) that proves the formula with Gödel number k.”

This becomes a formula about Gödel numbers. And this formula has its own Gödel number. Just try to get used to the fact that, within this proof, we are referring to all math in terms of Gödel numbers, and that’s okay.

Side note: Do all these numbers really correspond to meaningful formulas?

First time I seen this proof, it wasn’t clicking to me how do we know that these huge numbers we construct via substitution actually correspond to valid statements? The truth is: not always. Many Gödel numbers represent illogical nonsense. But that doesn’t matter. The system doesn’t care whether a formula is meaningful or not. It just manipulates symbols by rules.

Gödel carefully constructs his key formula to be syntactically valid. But the system itself works with structure, not semantics.

---

We’re Getting To The Core Of The Proof…

The Self-Referential Statement

Now comes the twist — the part that breaks everything.

Let’s walk through the construction of the famous Gödel sentence G, step by step.

---

Step 1: Start with a generic statement

We begin with a general formula:

“The formula with Gödel number k is provable.”

This is a claim about provability. And this claim has its own Gödel number (some long integer that we can generate when factoring primes on the power of the symbols from the table again). Let’s denote the Gödel number m.

Step 2: Negate the satement

Now construct a new formula:

“The formula with Gödel number k is not provable.”

This is a negated version of the previous formula, still using k as a placeholder.

Step 3: Substitute the formula's own number

Here’s the Gödel trick.

We now substitute m (the Gödel number of the formula from Step 2) into the placeholder k.

This creates a new formula that says:

“The formula with Gödel number m is not provable.”

Let’s say the Gödel number of this new formula is n.

And now comes, imo, the most difficult part of the proof:

Step 4: Realize that the formula talks about itself

We define n to be the Gödel number of the formula we just built. So now we have:

“The formula with Gödel number n is not provable.”

But this is exactly the formula we’re talking about - because n is its own Gödel number.

This is the Gödel sentence:

A formula that says of itself that it is not provable.

And because of how substitution works, this isn’t circular nonsense - it’s a valid formula. It’s just self-referential in a very clever, encoded way.

---

Side note vol.2: Why are we allowed to define n to be the Gödel number of the formula that says “The formula with Gödel number n is not provable”? How is that valid?

First: What does “define n to be…” actually mean?

It’s okay because we’re not arbitrarily declaring that n is the Gödel number of a self-referential sentence.

• Start with a formula schema:
  A general formula that says:

“The formula with Gödel number y is not provable.”
(This is a valid, generic formula — it’s not self-referential yet. Think of it as a function with variable input y.)

• This formula itself has a Gödel number.
  Let’s call that number n.
  So:

“The formula with Gödel number n is: ‘The formula with Gödel number y is not provable.’”

• Now we substitute y := n inside the formula.
  This gives us:

“The formula with Gödel number n is not provable.”

And that final formula - which says something about n - happens to have Gödel number n as a result of how substitution was done. It’s not an assumption, it’s a consequence!!!

Why this is valid (not circular):

It’s not that we started by saying “Let’s invent a formula with Gödel number n that says it’s unprovable.”

We went in the opposite direction and constructed a generic formula that refers to some number.

Then, we substituted n into the formula.

And the formula we ended up with, by mechanical calculation, happens to be the one with Gödel number n.

So it’s a fixed point: a number n such that the formula that says “Formula number n is not provable” has Gödel number n.

Why this trick works at all

Because Gödel figured out how to express substitution as an arithmetic function — sub(y, y, 17) — and then found an n such that:

n = sub(n, n, 17)

Intuitively, it’s like solving the equation x = f(x), and realizing there is such an x. Once you’ve found it, the formula is stable - it points to itself.

---

What Happens Now?

We’re pretty much done. Let’s call this self-referential formula we just constructed for example G.

If G can be proved, then it must be false (since it says it can't be proved).

But if G cannot be proved, then it’s true — just unprovable.

So:
If the system is consistent, G is true but unprovable.

And this is exactly what Gödel’s first incompleteness theorem says and what we wanted to prove. The second one follows from the first, because if a system could prove its own consistency, it would end up proving G, which it shouldn’t be able to do if it’s consistent.

Therefore:

No system can prove its own consistency — unless it’s inconsistent.

---

Side note vol. 3: You Can’t Escape With More Axioms

Maybe you're thinking: “Okay, just add G as a new axiom.” But if you add G to your system, you can repeat the trick and generate a new Gödel sentence G′, which will be unprovable in the new system. And then another. And another.

You can never catch your own tail. That’s why no consistent formal system can ever be complete.

---

Summary: What We Just Proved

Let’s restate the theorem:

Any consistent formal system that can express elementary arithmetic is incomplete.

And here’s how we got there:

• We took a system powerful enough to describe basic arithmetic (like Peano Arithmetic).

• We encoded formulas and statements about formulas as numbers.

• We constructed a valid formula G that says of itself: “I am not provable.”

• We showed that if the system is consistent, then G is true but unprovable.

Therefore:
The system is incomplete.

---

What To Do With Life Now?

Gödel’s proof didn’t just ruin Hilbert’s dream of a complete, tidy math. It also changed how we think about computers, logic, and even physics. Later, Turing used similar ideas to show that some problems are undecidable by machines — the famous halting problem.

And in math, Gödel’s shadow still watches above, looming over the math theories like Damocles’ sword. Every time we prove a theorem, we must remember it’s only within a specific system, and that some truths may lie forever just out of reach, no matter how rigorously we build the math.

How does it make you feel? Hope you didn’t get an existential crisis.

Thanks for reading. <3

---

First Part of This Series

Gödel's Incompleteness Theorems Explained Simply