jebmo’s posthaven

Roughly speaking, Gödel’s Incompleteness Theorem states that there are true mathematical statements that cannot be proven. When I was in 11-th grade, my geometry teacher Mr. Olsen, my friend Uma Roy, and I spent five weeks reading through Gödel’s original proof of the theorem. Why did it take so long? Partly because Uma and I were high-school students. Partly because Gödel was a less-than-talented writer. But mostly because the proof is actually pretty hard.

That might seem surprising, since it’s easy to present a one-paragraph summary of essentially how the proof works: Gödel begins by constructing a mathematical statement essentially equivalent to the sentence,

This statement cannot be proven.

Then Gödel considers what would happen if the statement were false. That would mean that the statement could be proven. But any statement that can be proven must be true, a contradiction. From this Gödel deduces that the statement must be true. But, since the statement is true, it follows that the statement cannot be proven. Note that this final statement is not a contradiction. Rather, it’s a proof of Gödel’s theorem.

So what makes the actual proof so hard? The trickiness comes from the fact that what might sound like a valid mathematical statement in English often isn’t (especially when the sentence is self-referential). Consider, for example, the sentence,

This sentence is false.

The sentence is nonsensical: it cannot be false (since that would make it true) and it cannot be true (since that would make it false). And it certainly cannot be written as a formal mathematical statement.

Here’s another example (known as the Berry paradox):

Define to be the smallest positive integer that cannot be defined in under words.

This might look like a valid mathematical definition. But again it’s nonsensical. And, importantly for the sanity of mathematics, no analogous statement can be made mathematically formal.

Even statements that use math symbols can be nonsensical:

.

(i.e., is the set of sets which are not elements of themselves.)

This is again a nonsensical definition (known as Russell’s Paradox). In particular, once we’ve defined we can ask ourselves, does contain itself? If it does, then cannot be a member of , a contradiction; and if it doesn’t, then will be a member of , a contradiction.

The point of the above three examples is that, if you want to prove a theorem about mathematical statements, then you have be extremely careful that what you’re proving the theorem about really is a mathematical statement. And, indeed, from the 46 definitions at the start, to the remarkably dense proofs at the end, Gödel’s original paper is nothing if not a massive exercise in carefulness.