Once upon a time, mathematicians thought they would be able to prove everything. The endeavor was known as Hilbert’s Program. They would find a complete and consistent set of axioms, and on this foundation build all of mathematics. (Although to be fair, much of mathematics was already built and was to be placed upon on those foundations retroactively.) And then, if everything went well, they would generate an algorithm that could prove every statement either true or false.

To some extent, Hilbert’s Program was successful. We now have Zermelo-Fraenkel set theory, which is a solid foundation for the vast majority of mathematics. But there are two problems. First, set theory isn’t complete. Second, we can’t prove it’s consistent. And Gödel showed that these problems have no solutions.

Gödel’s First Incompleteness Theorem: No consistent formal system is complete.
Gödel’s Second Incompleteness Theorem: No consistent formal system can prove its own consistency.
(Both of these theorems have additional qualifiers that I’ll get to later.)

Here I will explain the proof for the First Incompleteness Theorem, and a few of its implications. In a later post, I will talk about the Second Incompleteness Theorem.

What does completeness mean?

A formal mathematical system starts with a set of axioms, and from those can prove many statements. The system is “complete” if every statement can be proven either true or false.

In a complete mathematical system, could I prove the sky is blue?

No. Only statements that are well-defined within the mathematical language count. Gödel isn’t trolling us.

So if math is incomplete, what does the unprovable statement look like?

Are you familiar with the liar paradox? “This statement is a lie.”

Informally, the unprovable statement (called Gödel’s statement) says “This statement cannot be proven.”

But that’s not allowed, is it?

You’re right. “This statement” is too vague and is not allowable within the mathematical language. In order to be clear, you must substitute “This statement” for the specific statement in question. Unfortunately this leads to an infinite recursion, which is also not allowed:

“‘”‘”‘”[…]” is a lie.’ is a lie.” is a lie.’ is a lie.” is a lie.’ is a lie.”

So Gödel’s proof is infinitely bogus?

No. Gödel found a trick to get around the infinite recursion. The general idea is that each statement can be assigned a number (called its Gödel number). This is easy and can be done in any number of ways. For instance, you could simply convert the statement to ascii code. And now instead of saying “this statement” we can refer to statements by number.

All that remains is to find some number n such that Statement n is equivalent to “Statement n cannot be proven.”

I don’t think it’s possible for a statement to include the ascii code of itself.

Right, it seems ridiculous. For illustration purposes, suppose we have the following:

Statement 11: “Statement 1 cannot be proven.”
Statement 111: “Statement 11 cannot be proven.”
Statement 1123: “Statement 123 cannot be proven.”
Statement 18953: “Statement 8953 cannot be proven.”

Hopefully you recognize the pattern, and can see that here we will never find n such that Statement n is “Statement n cannot be proven.” Fortunately, that’s not what Gödel needs. He needs two statements fulfilling the following conditions:

Statement n is logically equivalent to statement m.
Statement m is “Statement n cannot be proven.”

So what is Gödel’s statement?

I’ll get to that, but first I need to talk about substitution. Consider the statement “x is odd”. This statement is not well-defined (ie we can’t say whether it is true until the value of x is declared), but it does have a Gödel number. Let’s say its number is 3. Now suppose we substitute x with a specific number, let’s say the number 5. Now we have “5 is odd,” which is well-defined, and has a Gödel’s number of its own.

So let’s define sub(j,k) to be Gödel’s number of the statement j, where every instance of “x” is replaced the number k. For instance, sub(3,5) is the Gödel’s number of “5 is odd.”

Now, let d be the Gödel’s number of the statement “Statement sub(x,x) is well-defined and cannot be proven”. Gödel’s statement is

Statement sub(d,d) is well-defined and cannot be proven.

When we expand out the sub function we find that Gödel’s statement is equivalent to

“Statement sub(d,d) is well-defined and cannot be proven” is well-defined and cannot be proven.

Which of course simply means “Gödel’s statement is well-defined and cannot be proven.”

Wow, how did he come up with that?

Gödel used what we call Gödel’s Diagonal Lemma. Basically, if you have any function G(x), then the Diagonal Lemma finds some number n such that statement n is logically equivalent to G(n).

What’s diagonal about the Diagonal Lemma?

There’s some similarity between Gödel’s Diagonal Lemma and Cantor’s Diagonal Argument, the latter which was used to prove that real numbers are uncountable.

To prove the Diagonal Lemma, we draw out a table of sub(j,k).

We’re particularly interested in the diagonal of this table. We ask, is G(sub(1,1)) true? is G(sub(2,2)) true? And so on. Construct the function D(x) which basically says “G(sub(x,x))”. Of course, statement D(x) has its own Gödel number d, which corresponds to a row on the table. So we can construct D(d), whose Gödel number is sub(d,d), and which is logically equivalent to G(sub(d,d)).  And that is the statement we wanted.

Can I use the Diagonal Lemma to generate a liar paradox?

No. In order to prove Gödel’s First Incompleteness Theorem, we needed to formally construct the function “Statement x cannot be proven”. This is possible. But in order to create the liar paradox, we need to formally construct a function “Statement x is false”. This is not possible.  This was proven by Tarski’s Undefinability Theorem.

Tarski’s Undefinability Theorem is easy to prove. Basically, if you could construct “Statement x is false”, then by the Diagonal Lemma we could create a liar paradox, which is a contradiction.

Incidentally, this is related to Cantor’s Diagonal Argument. Cantor showed that real numbers are uncountable. Likewise, the set of all functions are uncountable. Thus, there are some functions that are impossible to assign a Gödel’s number. Which is to say, some functions cannot be formally constructed.  “Statement x is false” is one of those functions.

What if I create an exotic math system where none of this argument applies?

You can do that! First qualifier to Gödel’s Incompleteness Theorems: They only apply when the mathematical system includes some basic arithmetic.

What if we just add an axiom asserting that Gödel’s statement is true?

That… would be fine! Keep in mind, “provability” is always relative to a particular set of axioms. If we have axioms S, then we can construct Gödel’s statement, which is unprovable under S. Now we create a new set of axioms S’, adding an axiom asserting the truth of Gödel’s statement. Gödel’s statement still cannot be proven under S, but can be proven under S’. Of course, S’ is still incomplete, because we can construct a second Gödel’s statement from S’.

What if we add an infinite number of axioms stating that all of Gödel’s statements are true?

Depending on how you did it, you’d run into one of the following problems:

1. The axioms are still incomplete. That is, there exist yet more unprovable statements.
2. The axioms are complete but incomputable. That is, there is no effective method to determine whether a given statement is one of the axioms or not. Here the notion of “provability” is questionable, since in general you can’t actually show a proof. Second qualifier to Gödel’s Incompleteness Theorems: they only apply to computable sets of axioms.

Isn’t Gödel’s First Incompleteness Theorem itself a proof of the unprovable statement?

No, not unless you can use the axioms to prove their own consistency. Gödel’s Second Incompleteness Theorem says you can’t do that.

Can we add an axiom asserting that Gödel’s statement is false?

Yes. Remind me to come back to this later.

Where do you get your information?

Wikipedia and the Stanford Encyclopedia of Philosophy are good resources, although at times very technical. My goal is to translate such resources, while preserving more detail than the typical popular explanation.

Update: Part 2 has been posted.