Gödel's Second Incompleteness Theorem, Proof Sketch
Jan 17, 2025
In order for math to prove its own correctness, it would have to be incorrect. This result is Gödel’s second incompleteness theorem, and in this video, we provide a sketch of the proof.
In the previous video, we proved a slightly simpler version of Gödel's first incompleteness theorem.
Now, we'll strengthen the theorem by replacing soundness with consistency.
As a quick recap, we want to show that all sufficiently expressive math systems
are either incomplete or inconsistent.
In a complete math system, we can prove at least one of
pigs can fly or pigs can't fly.
In a consistent system, we can prove at most one.
Since we haven't yet had a video on Boolean logic, I need to get a little math out of the way.
By definition, for A to imply B, either the precondition is false or the conclusion is true.
If I start out with the assumption that pigs can fly,
I can make any statement afterward since the assumption is already false.
Similarly, if the conclusion is 1 plus 1 equals 2, it doesn't matter what my assumption is.
The whole implication is true because the conclusion is true.
A implies B is logically equivalent to not A or B.
In other words, to prove that math is incomplete or inconsistent,
we can equivalently show that if it's consistent, then it's incomplete.
So the outline of our improved proof is pretty simple.
First, we assume our math system is consistent.
We then create a program called Smith to ruin our day.
After analyzing the program, we realize it must be the case that our math system is incomplete.
Meaning, our math system must be either inconsistent or incomplete.
Let's take a look at this definition of Smith.
Much like the program we wrote in the previous video, we loop through all possible math proofs
and check if we have a proof that a program run on itself loops or halts.
With this program, we intentionally perform the opposite behavior as the program fed in.
For the same reason explained in the previous video,
this is a valid program that we can code right now.
Here's the important question.
What happens when we feed Smith into itself?
This question should sound familiar as it's extremely similar
to what we did to show that the halting problem is unsolvable.
Well, Smith run on itself must either halt or loop.
So let's take each possibility one at a time.
First, we look at the case in which we find a proof that the program loops.
As we execute the program, we will land inside the case
where we find the proof that Smith on Smith loops.
And then the program will actually halt.
If a program halts, there's definitely a proof that it does so.
We can just use a brute force proof that says what the program does
step by step and conclude it must halt.
Since Smith on Smith actually halts, we have a proof that it halts,
but we started with a proof that it loops.
This contradicts our initial assumption that our math system is consistent.
Now, let's look at the situation where we find a proof that Smith on Smith halts.
As we execute Smith on Smith, we will take some x number of steps,
find the proof, and enter an infinite loop state.
However, this means that there is definitely a proof that Smith on Smith loops,
since once again, we can use the brute force proof for x steps
and then show that it will get stuck in an infinite loop on step x plus 1.
We'll have both proofs that Smith on Smith loops and halts,
violating our assumption of consistency again.
Since both cases of having a proof that Smith on Smith either loops or halts
results in a contradiction, neither can be true.
Assuming our math system is consistent, we cannot prove within our math system
either Smith on Smith loops or halts.
In other words, our math system is incomplete.
Just out of curiosity, what does Smith run on Smith actually do?
Well, let's take a look.
Since we don't have a proof that Smith on Smith loops or halts,
the program will loop forever over all possible math proofs, unable to find a proof of either.
But wait, if we formalize this idea, we'll have a proof that Smith on Smith loops,
even though we just proved that we cannot prove Smith on Smith loops.
Did we just find a giant contradiction in all of mathematics?
Not quite.
We started this whole proof with an important assumption that our math system was consistent.
So currently, we have that if our math system is consistent, then Smith on Smith loops.
Previously, we showed that if our math system is consistent,
then we could not prove in our math system that Smith on Smith loops.
These two conclusions are not yet inherently contradictory.
However, if we could prove our system's own consistency,
we'd then have a valid proof that Smith on Smith loops,
creating a contradiction with the fact that we shouldn't be able to find such a proof.
In order to resolve this contradiction,
it must be that our math system cannot prove its own consistency.
If we have a sufficiently expressive math system that we assume to be consistent,
not only is it incomplete, a true statement it cannot prove is that the system is consistent.
These two parts make up Gödel's two incompleteness theorems.
At a high level, you can think of it like this.
We want math to be correct.
However, if we ever proved math was correct within our math system,
that would mean that our math system is actually incorrect.
In order for our math system to be correct,
we have to hope that its own correctness is a problem that remains unsolved forever.
There we have it, Gödel's first and second incompleteness theorems.
These theorems rip a hole in our understanding of math.
They show us that not only are there insurmountable problems,
but also the tools we've been using might have been broken this whole time.
It's easy to feel disappointed in the power of math when learning these theorems,
but they leave a lot of room for exploration.
In trying to answer all of our questions,
we necessarily ask new ones.
There will always be new math on the horizon.

