Gödel's Incompleteness Theorems, As Simply As Possible

God exists, since mathematics is consistent, and the Devil exists, since we cannot prove it.
— André Weil (as quoted by Paul Rosenbloom, The Elements of Mathematical Logic)

Proof

0. Every grammatically correct sentence in a mathematical system is either true or false.
1. By the Fundamental Theorem of Arithmetic, all grammatically correct sentences in our mathematical system have a unique associated number.
2. The sentence \(S =\) “The sentence with number \(N\) has no proof” is grammatically correct.
3. Sentence \(S\) has number \(N\).
4. We now have two cases, depending on whether \(S\) is provable or not:
   1. If \(S\) is provable, then our system can check that proof, so it can also prove “\(S\) has a proof”. But \(S\) says “\(S\) has no proof”, so our system proves both a statement and its opposite. In other words, our system is contradictory.
   2. If \(S\) is not provable, then it’s true, and there exists a true statement that our system can express but cannot prove. In other words, our system is incomplete.

This is a proof of Gödel's first incompleteness theorem:

Theorem (Gödel, I) Any logical system (with a computable list of axioms) that can express the natural numbers \(\N = \set{ 0, 1, 2, 3, \ldots}\) is either contradictory or incomplete.

We can build off this to prove the second incompleteness theorem:

Theorem (Gödel, II) Any consistent logical system (with a computable list of axioms) that can express the natural numbers cannot prove its own consistency.

Proof

0. The proof of the first theorem is just an argument about numbers, so our system can carry it out internally.
1. Let \(C\) be the sentence \(C =\) “our system is consistent”.
2. In case a of the original theorem (where the system is contradictory) we obtain \(P_1 =\) “if \(C\), then \(S\) has no proof”.
3. But “\(S\) has no proof” is exactly what \(S\) says, so our system proves \(P_2 =\) “if \(C\), then \(S\)”, and \(P_1\) and \(P_2\) are logically equivalent.
4. However, the first theorem prevents a consistent system from proving \(S\), so by contraposition, a consistent system cannot prove \(C\). In other words, a consistent system cannot prove its own consistency.

There you go. That’s the gist of both proofs. I have read an entire book and several articles that wax poetic about how mysterious, counterintuitive, or philosophically important the damn theorems are for eons before presenting them so I can judge for myself — and then they usually only present the first theorem!

I hope you are not nearly as exhausted by my presentation as I was by practically everyone else’s. If you still have gas in the tank, I am happy to provide some brief technical commentary.

Commentary on the Proofs

The First Proof

The first proof has only two subtle points that it relies on:

1. Statement 0, which is known as the law of excluded middle, and which most mathematicians don’t care to dispute. (And even the logicians who don’t like it still have an equivalent version of Gödel’s theorem.)
2. Statement 1, which requires the fundamental theorem of arithmetic to assign unique numbers; basically, we just assign every letter in the sentence a prime power, then multiply them all together to get a unique natural number. It’s quick and dirty, but it works.

The only difficult part is actually constructing \(S\) to say “no proof exists for some statement…”, but this is just an exercise in mathematical logic that is not very interesting. However, connecting \(S\) to \(N\) requires a clever trick known as diagonalization.

Finding \(N\)

Define the function \(G(s)\) to be the function assigning a sentence \(s\) to its Gödel number, and the function \(S(x)\) to be the function that produces the sentence “The sentence with number \(x\) has no proof”. It’s tempting to look for an \(n\) that is a fixed point of \(G(S(x))\), that is, \(n = G(S(n))\), but there isn’t one: \(S(n)\) contains \(n\) written out, so for any sensible numbering its number \(G(S(n))\) is always larger than \(n\).

The trick is to have \(S\) describe how to compute its own number instead of writing it down. Consider the template

\(F(x) =\) “Plug the number \(x\) into the template with number \(x\). The resulting sentence has no proof.” Feeding \(x\) into the template with number \(x\) is where the diagonalization step takes place.

Templates get numbers just like sentences do, so let \(m = G(F)\), and let

\(S = F(m) =\) “Plug the number \(m\) into the template with number \(m\). The resulting sentence has no proof.”

Plugging \(m\) into the template with number \(m\), which is \(F\), produces exactly \(F(m) = S\). So \(S\) says “\(S\) has no proof”, and it has a number \(N = G(S)\), even though \(N\) itself never appears anywhere inside \(S\).

Interestingly enough, there are systems that don’t have the fundamental theorem of arithmetic and therefore are actually both consistent and complete: Euclidean plane geometry is not subject to incompleteness because it has no way to express any notion of counting, and therefore is not subject to the first theorem. (Plane geometry is not nearly powerful enough to prove its own consistency, of course.)

As a neat historical note: Euclid incorrectly believed there were five axioms necessary to describe plane geometry; David Hilbert, E.H. Moore, and R.L. Moore showed that Euclid actually needed 15 more for a complete system. (The first proof in Euclid’s Elements is correct, but the proof requires axioms that Euclid doesn’t provide!)

The first printed edition of Euclid’s Elements, Erhard Ratdolt, Venice, 1482. Folger Shakespeare Library, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

The Second Proof

The first step, that “our system can carry out the proof of the first theorem internally”, hides the real nuts and bolts; it needs the system to prove facts about its own provability, like “if \(S\) has a proof, then it’s provable that \(S\) has a proof”. These statements are known as the Hilbert–Bernays–Löb derivability conditions.

For now, I leave the interpretation to the philosophers.