Gödel’s Incompleteness Theorems Explained Simply

Why Math Will Never Be Complete – Part 1

Tereza Tizkova

Jun 30, 2025

https://terezatizkova.substack.com/

This is my attempt to explain Gödel’s Incompleteness Theorems in a way that actually makes sense.

If you’ve ever:

• Come across Gödel’s theorems but didn’t fully get them,
• Or heard people say that math is “broken” or “paradoxical” and want to finally understand why, even without a math background,

Then this post is for you. And if you get stuck at any part, please leave me a comment so I can explain better.

We’ll start with the “why,” then build up to what the theorems actually say, and then we’ll go deeper and actually walk through the outline of Gödel’s proof.

First – A Mini Exercise

Think about this sentence:

“This sentence cannot be proven.”

If it could be proven, then it would be false, because it says it can’t be proven. But if it can’t be proven, then it’s actually true.
This kind of self-referential trap is going to be very important later. And it’s exactly the intuition behind the paradoxes Gödel showed is built deep into math.

Kurt Gödel. Source

Then – Some Story

In the early 1900s, mathematicians were trying to build a perfect foundation for math – something clean, completely describing math, and contradiction-free. One of the most famous mathematicians, David Hilbert, believed this was absolutely possible. He even laid out a research program called Hilbert’s Program to formalize math and find this perfect system.

David Hilbert. Source

But then in 1931, Gödel (just 25 years old) published a short paper that completely destroyed Hilbert’s dream.

Gödel said that we can never find a complete and consistent foundation for all of math. And he proved it.

So… what did Gödel prove exactly?

First Meeting With The Theorems.

There are two Gödel’s Incompleteness Theorems, even though the first one is the more famous one. The first one says:

First Incompleteness Theorem: Any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete.

Here, I made a quick explanation of its every part, but we get to this later in more detail:

The second theorem says something that follows up from the first theorem and is also a bit spooky:

Second Incompleteness Theorem: A formal system like that (described in the first theorem) can’t prove its own consistency.

Intuitively, the second theorem says you can’t even prove from within math that math itself is trustworthy.

My Note About Why I’m Explaining The Theorems

Note that there are many formulations of the theorems, some are more vague and less rigid. For example, an equivalent statement of the first theorem is “Every mathematical system will have some statements that can never be proved.”
But that’s one tricky fact about Godel’s theorems. I think they are getting huge popularity, partially because they sound normal and not dangerous. They don’t use any weird symbols and equations, like many math theorems that you see and immediately think “No thanks, I won’t even try to read that”… Such as the mean value theorem:

Source: Wikipedia

Godel’s theorems at first glance look like you might understand them, because they contain words like “powerful” or “system” or “consistency” or “provability,” which you have some intuition for already, from normal life. But all these terms have their rigorous definitions in math, and we need to understand them even more because they look so “normal”. From my experience, the normal-sounding math can be the most tricky one because your brain tells you that it’s already familiar, and you don’t realize you don’t actually understand.

So let me explain the theorems in detail, and only after we focus on understanding what the theorems really say, can we move to the next part: proving them & enjoying it!

Explaining Every Piece of The Theorems

Now, back to my visual:

I made this with Napkin.ai – really recommend that tool!

💛 Consistent

A set of axioms is consistent if there is no statement such that both the statement and its negation can be proven from those axioms.
In other words, the system doesn’t contradict itself.

We obviously need to require consistency in the theorem. Because if the system were inconsistent, then you could prove literally anything, even false things, which makes the whole system useless. That’s why Gödel’s theorems only apply to consistent systems.

🧡 Formal system

A formal system is something very central to math, and you probably already know what it is, maybe without realizing. A formal system is just a mathematical theory – that is, a framework, or we could say “structured setup” consisting of:

1. Axioms – basic rules or statements that we accept as true without needing to prove them.
   For example: “0 is a number.”
2. Symbols – a notation to write down statements.
   For example: 0 for zero, +, ×, = for addition, multiplication, and equality, ∃ for “there exists”, ∀ for “for all”, → for “implies”, and ¬ for “not”.
3. Theorems & rules of inference – statements & rules for how to make new true statements from old ones.
   These are things like:
   • If P and P → Q both are true, then Q is true.
   • Induction: If a statement is true for 0, and if the statement being true for x implies it’s true for x + 1 – Then it’s true for all natural numbers.

You start with axioms, use symbols to write statements, and apply rules of inference to build more and more complex theorems — ideally, all of mathematics. I’m always saying that we build math like LEGO.

Sometimes we call a “formal system” a theory, and the statements we prove inside it – using those axioms and rules – are theorems.

This is the core of how math works, in my opinion. Super important.

❤️ “A certain amount of elementary arithmetic can be carried out”

This is the part that often confuses people, but it’s actually quite simple.

Gödel just means that the system is powerful enough to express the basic facts of arithmetic. In other words, it must be able to write down and reason about simple number-based statements using its axioms and rules of inference.

So the system should be able to say things like:

• x + 0 = x
• x × 1 = x
• “For every number, there is a next number”
• “There exists a number y such that x = y × y”

Just this much arithmetic is enough for Gödel’s theorems to apply to all math. (In the next section, we explain why).

🩷 Incomplete

Incomplete means that there exists a statement in the language of the system that is not provable — it can be neither proved nor disproved from the axioms of the system.

This is the conclusion of the theorem. We first describe what system we talk about (needs to be consistent, and the other conditions), and the,n as the conclusion, we state that such systems are always incomplete.

So intuitively, there is always a statement in mathematical formal systems that is out of logical reach.

Example of Formal System: Peano Arithmetic

A lot of versions of Gödel’s theorems’ proofs use Peano Arithmetic as an example of a formal system that follows the conditions of the theorem. So I say a few words about Peano Arithmetic (PA). You already know it, though – from elementary school.

I said every formal system has axioms, symbols, theorems, and rules of inference. For Peano, it’s these:

1. Axioms of Peano Arithmetic

1. Zero is a natural number. (Some formulations use 1 instead of 0 as the «first» natural number)
2. Every natural number x has a successor s(x) in the natural numbers.
3. Zero is not the successor of any natural number.
4. If the successor of two natural numbers is the same, then the two original numbers are the same.
5. If a set contains zero and the successor of every number is in the set, then the set contains the natural numbers.

These are basically just saying that there are numbers like 0, 1, 2, 3, 4, 5, … there is always the next one, it starts with 0, and the numbers are unique.

2. Symbols of Peano Arithmetic

Symbols are basically the 0, 1, 2, 3, …, the +, -, and other signs, and some formulations, for example, denote the successor of a number x by S(x).

3. Rules of inference and statements (theorems)

Let’s say we have a theorem

0 + x = x for all natural numbers x.

This feels intuitively true and totally obvious, but in a formal system like PA, we need to prove it using only the allowed axioms and inference rules. We’ll use a proof technique called mathematical induction, and we try to prove this theorem, just so you get a sense of how a formal system is built.

1. Base Case (x = 0):

We check the statement for x = 0:

0 + 0 = 0

This is one of the axioms of Peano Arithmetic, so it’s an obvious truth we can use to start with. So the base case is automatically proven.

2. Inductive Step:

Now we assume that the statement holds for some arbitrary number x. This is called the inductive hypothesis:

0 + x = x

Now we want to prove that if it holds for an arbitrary number x, it also holds for the next number, s(x) (the successor of x):

0 + s(x) = s(x)

Using the recursive definition of addition from PA:

0 + s(x) = s(0 + x)
(This is just how we decided to define addition in PA)

But from the inductive hypothesis, we know:

0 + x = x

And if we apply the successor, it follows that:

s(0 + x) = s(x)

And therefore:

0 + s(x) = s(x)

This completes the inductive step.

Conclusion of the proof:

By the principle of mathematical induction, we have shown that “if the thing is true for x, it’s true for x + 1 every time”, which applies it to all natural numbers, and hence:

For all natural numbers x, 0 + x = x

This is now an example of a theorem in the Peano Arithmetic system. And we’ve proven using only axioms and inference rules.

This is basically the core of math. We always start with axioms in any mathematical theory and derive the rest, using different logical techniques.

Summary Of What We Learned

Let’s get back to the theorems once again:

First Incompleteness Theorem: Any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete.

• Consistent:
  The system never proves both a statement and its negation. In other words, it doesn’t contradict itself.

• Formal system:
  A mathematical theory built from:
  • Axioms – basic obvious assumptions we take as true (like “0 is a number”),
  • Symbols – notations like 0, +, =,
  • Theorems & rules of inference – statements & rules of how we derive new statements from old ones.
• Elementary arithmetic can be carried out:
  The system can express and reason about basic properties of natural numbers, like addition, multiplication, and induction. The system can define numbers and talk about its own logic
• Incomplete:
  There exists a statement in the system’s language that is true, but cannot be proven using the system’s own axioms and inference rules.
  It’s not false. It’s not provable. It’s undecidable within the system.

Second Incompleteness Theorem: No formal system (like the one described in the first theorem) can’t prove its own consistency.

Ready For Part Two?

For the first blog post, it’s enough to understand what the theorems are really saying, and get used to it. In the second blog post, we sketch the proof of the first theorem. And we will clarify more questions you might now have. Such that

• If math is so huge, how can Gödel’s theorems talk just about formal systems that express elementary arithmetic?
• How is some simple arithmetic enough to prove big truths about all mathematical systems?
• How do we use math to prove the theorems… if they are actually talking about math? Won’t we be going in circles?

Stay tuned for the second part, and please leave me a comment! 🙂

Subscribe to Tereza Tizkova

Launched 2 years ago

Science, tech, startups growth, and some chill blogging

By subscribing, you agree Substack’s Terms of Use, and acknowledge its Information Collection Notice and Privacy Policy.

Tereza Tizkova

Gödel’s Incompleteness Theorems Explained Simply

Why Math Will Always Be Broken – Part 2

Tereza Tizkova

Jul 19, 2025

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

Tereza Tizkova

June 30, 2025

Read full story

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

Tereza Tizkova

June 30, 2025

Read full story

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