Gödel's Incompleteness Theorem

Intro

The title of this page is kind of a lie. Most people don't know this but Gödel actually had two different incompleteness theorems. The one everyone knows (and will not shut up about) is the 1st theorem. It states, more or less, that there are some questions which can be stated but not proven. The 2nd theorem, however, simply states that there is no way to evaluate how good a system is from within that system itself. Both are deceptively simple for how profound their implications are. And while I would like to raise more awareness about the 2nd theorem, I have to admit that the first one is far more interesting.

The 2nd theorem's conclusion is obvious. Of course a bad system can't tell how bad it is. You need outside information to have a frame of reference for what "good" and "bad" even mean. The 1st theorem is surprising however. Why can't it be the case some problems are just really, really hard? Fermat's Last Theorem took 400 years to solve and the invention of at least 3 different fields. How can we be sure that some problems are 100% impossible to prove? Well, over the course of this post, I'll show you how Gödel came to this conclusion.

The Size of Infinity

In order to talk about Gödel's proof, we first need to look at an entirely unrelated proof from 60 years earlier. Let's ask ourselves a rather simple question: are there more even numbers than odd numbers?

I think even a baby could tell you the answer to this is "no". There are an equal amount. Half of all numbers are even and half are odd. Therefore, they're equal. But now for a harder question: are there more whole numbers than even numbers?

This feels equally simple. We just established that half of all whole numbers are even. Therefore, there must be twice as many whole numbers as even numbers, right? Well, no. They're equal.

Earlier, it was easy to tell that even and odd numbers are equal because they always come in pairs. But we can just as easily pair up every whole number with two times that number.

This pairing means they have to be equal. Let's call the size of the whole numbers $\mathbb{N}$. Both the even numbers and ood numbers have size $\mathbb{N}$. What about the rational numbers? Is its size, $\mathbb{Q}$, greater than $\mathbb{N}$? Let's consider that next

The Size of the Rationals

It's trivial to say that the rationals are AT LEAST as big as the whole numbers. Sending any number to that same number divided by one implies $\mathbb{Q} \geq \mathbb{N}$.

But now let's do something very clever. Let's construct every single possible fraction. We just need to take a whole number and divide by another whole number.

If we rotate this grid, we can also think about this as a pyramid of all possible fractions

If we simply go across the rows, left to right, we can create a pairing between whole numbers and all possible fractions

This is a good mapping. It hits every single rational, by definition, but it's not one-to-one. $\frac{1}{1}$ is the exact same number as $\frac{2}{2}$, $\frac{3}{3}$, $\frac{4}{4}$, etc. and yet we've paired every one of those with a different whole number.

If you think about it, this implies that the rationals are AT MOST as big as the whole numbers. The whole numbers alone are enough to map to the rationals several times over. Therefore, $\mathbb{N} \geq \mathbb{Q}$.

The only way we can have both $\mathbb{Q} \geq \mathbb{N}$ and $\mathbb{N} \geq \mathbb{Q}$ is if the two sets are the same size. So the whole numbers, even numbers, odd numbers, and even the rational numbers all have the same size. Only one question remains: is the size of the real numbers ($\mathbb{R}$) also $\mathbb{N}$?

The Size of the Irrationals

Let's take all the real numbers between 0 and 1 and map them to a whole number.

Now let's go down the diagonal and create a new number. If we see a 9, we subtract one. Otherwise, we add one.

We now have the number .… — a brand new real number between 0 and 1. Notice that it differs from every single number in our list. It differs from the nth number at the nth digit. By definition, then, it cannot be in our list. We have paired every single whole number to a real number and somehow there are still real numbers left over. The real numbers must be STRICTLY LARGER than the whole numbers. $\mathbb{R} \gt \mathbb{N}$

Moving On

So then, what was the point of any this? The point was to introduce you to the concept of the diagonal argument. Even though this proof had nothing to do with Gödel's incompleteness theorem, it takes the exact same form. Gödel's argument will rely on creating a list of things, arguing something about the diagonal, and then drawing a conclusion from there. So then, without any further ado, let's finally prove Gödel's incompleteness theorem.

Gödel's Proof

A computer's entire job is to take in numbers and interpret them as something else. For example: when working with the ASCII standard, the number 8482 is interpreted as the trademark symbol. Thanks to computers, we can encode entire mathematical statements as a single number.

The most important consequence of this is that the relationship between a statement and a proof is now just a numerical property. In the same way that we can say 12 is a factor of 156 or that 15 is less than 16, we can say 13 is the proof of 56. (What we mean exactly is that the ASCII interpretation of 13 is the proof of the ASCII interpretation of 56.)

Let's write a function which automatically checks for this. The function IsProvable(x) returns true if there is a number out there—anywhere—which is the proof of x. If that seems unreasonable to you, consider the function IsPrime(x). This function appears in many code libraries and is even on some graphing calculators. What it does is rather simple to state but in practice it's not clear at all how it's supposed to work. How is our function supposed to know that $2^{132 ,049}-1$ is prime but $2^{132 ,048}-1$ isn't? Both of these numbers have over 39,000 digits. Really, the way the function works isn't important. The point is that every number either is prime or not and function tells us that. The function IsProvable(x) would be hard to actually calculate in practice but for any number there is a definite answer, provable or not. Even if we don't know how it works, this function exists.

Gödel's Diagonal Argument

With that small prerequisite in mind, let's create a list of all possible functions which only take one variable as input.

If we think about our table as a function, it is a function of two variables, T(f,n). The first variable chooses a function from the list and the second variable passes a number into that function. $T(6,2) = \zeta(2) = \frac{\pi^2}{6}$

This function cannot be in our list. But if we take T(n,n) then this function would be in our list because it only uses one variable. If you think about what it means, it takes the nth function and evaluates it on n as an input. It prints the value on the diagonal of our table

Notice that IsProvable(x) only uses one variable. We can construct IsProvable(T(n,n)) without introducing a new variable. So this too is in our list.

Now let's negate this function. Wherever the function had true, our new function will have false. And vice versa

Let's call this function S(n) for short. What does S(n) even do? It says that the number T(n,n) is NOT provable. If S(n) shows up on row k of our list, what happens if we try to evaluate S(k)?

S(k) means "the number T(k,k) is not provable". And what is T(k,k)? The kth function is S(n) and we're putting in k as an input. At this point the problem should be obvious. The S(k) literally evaluates to "the number S(k) is not provable". We have managed to construct the sentence "this sentence is false".

Discussion

The fact we were able to construct S(k) has profound implications. It means that math will never be both consistent (can't prove false things true) and complete (can prove any statement).

S(k) says that it is unprovable. What if that's true? That's a problem. That means there are some true statements which we can never prove. Math is incomplete.

What about the opposite? If S(k) is false then there actually is a proof for it somewhere. This is equally bad. It's possible to prove things which are not true. Math is inconsistent.

Because allowing inconsistency is unacceptable (if we can prove something like "1=2", we can't trust any proof anymore) we must settle for a system that is incomplete.

Conclusion

No matter what we do, no matter how clever we are when we're designing our system, we cannot avoid having this issue. There will always be an infinite number of problems which lack proofs. Any problem which seems incredibly hard might actually be 100% impossible to prove. It's a scary thought really. Years spent trying to prove the Riemann hypothesis might have been wasted. And it's all thanks to Gödel's argument.

At a later date I might discuss a direct consequence of Gödel's incompleteness theorem. Mainstream mathematics is built upon a system of math known as ZFC. The C here stands for "the axiom of choice". This is a statement which is impossible to prove in ZF alone. ZFC assumes that it is true without requiring a proof.