Gödel’s incomplete theorems are famously profound, strange, and interesting pieces of math. But it’s hard to understand them, and especially hard to understand why they are true. I’ve never been quite satisfied with the explanations I’ve seen for the general public, so I wanted to take a crack at explaining what these theorems say and give a flavor of why they hold. See what you think:
Incompleteness Theorem 1 is about whether all mathematical truths can be proven.
The first incompleteness theorem says there will always be unprovable truths within every sufficiently powerful and non-contradictory mathematical system.
In order to prove these “unprovable” truths, you’d have to go outside that system into a bigger system, but that bigger system would then have its own unprovable truths as well, and to prove those, you’d need an even bigger system, and so on.
The exceptions are mathematical systems that you can’t use for arithmetic and mathematical systems that are self-contradictory (and therefore useless).
Why is this theorem true?
Step 1: Number all mathematical statements so that they can talk about each other
Gödel figured out how to assign a unique number to each statement in arithmetic. So, for instance, the statement “1+1=2” might be (just to make up a simple example) statement #1, and “4 < 5” might be statement #2 (realistically, these would be assigned huge numbers, but to keep things simple I’ll use small numbers).
Numbering all of the statements allows statements to make claims about each other in the language of arithmetic. For instance, maybe statement #3 says, “Statement #2 cannot be proven” (but it says it in the completely precise language of arithmetic, not in words – these statements are completely normal math, much like a typical mathematical statement you’d find in a math textbook, and so you’d expect each of these statements to either be true or false just like 1+1=2 is true and 1+1=3 is false).
Step 2: Create a self-referential statement
Gödel then considers a special statement, which he proved always will exist (say, for simplicity, that it’s statement #4). Statement #4 says, “Statement #4 *cannot* be proven in this system.” So, it refers to itself. In essence, in completely precise mathematics (rather than words), the statement says, referring to itself, “I cannot be proven.” That’s not the same as a statement that says “I am false” – being unprovable and being false are different, as we’ll see.
Step 3: Produce a contradiction
Now, we can show that statement #4 cannot be proven.
That’s because if the mathematical system *could* be used to prove that statement #4 is true, that would produce a contradiction. Statement #4 claims that statement #4 *cannot* be proved – so if you prove it’s true, then that implies you can’t prove it’s true!
Since we’ve assumed our mathematical system contains no contradictions, that means statement #4 can’t be proved in that system – which is precisely what statement #4 claims! So, statement #4 is true. Hence, it is a true statement that can’t be proved in that system.
Since Gödel showed that a statement like statement #4 can always be created in any mathematical system powerful enough to allow for arithmetic, any such system that has no contradictions has true statements that the system can’t be used to prove!
Incompleteness Theorem 2 is about whether you can prove that mathematical systems contain contradictions.
If a mathematical system contained a contradiction (e.g., that 1=2), that would make the system useless, so it would be really nice to be able to show that such a system contains no contradictions.
However, Incompleteness Theorem 2 says that a mathematical system with no contradictions that’s powerful enough to include arithmetic can’t prove that it itself has no contradictions. Or, more formally, that means that you can’t use the system to prove: “This system’s axioms do not lead to a contradiction.”
Yet another way to put it is, if such a mathematical system proves that it itself has no contradictions, then that system actually has contradictions!
Why? Well, let’s return to our statement #4 from before. Recall that this statement refers to itself, as it’s the statement that says, “I can’t be proven in this system” (though in completely precise mathematics, not in words).
Note that if statement #4 is false, that would produce a contradiction. Since statement #4 claims that statement #4 can’t be proven to be true, if that’s false, then statement #4 *can* be proven to be true, which is the same as saying it’s actually a true statement – so it being false implies it is true, which is contradictory!
What this means is that if we can prove that the system we’re working in has no contradictions, then that proof ALSO implies that statement #4 is true (i.e., that the system can prove statement #4).
But we already know from the first theorem that statement #4 can’t be proven to be true using the system!
Hence, the system must not be able to prove that it itself contains no contradictions (because if it did, it would violate theorem 1).
This tells us that any mathematical system powerful enough to include arithmetic can’t be used to prove that it itself has no contradictions (unless it actually contains contradictions).
A big thanks goes to Norman Perlmutter for his very helpful feedback on an earlier draft of this post!
This post was first written on November 17, 2023, and first appeared on my website on January 3, 2024.
Comments