Gödel for Dummies

Gödel’s theorems say something important about the limits of mathematical proof.

Proofs in mathematics are (among other things) arguments. A typical mathematical argument may not be “inside” the universe it’s saying something about. The Pythagorean theorem is a statement about the geometry of triangles, but it’s hard to make a proof of it using nothing but points and lines in a plane! For instance, Euclid’s own proof (per Wikipedia) starts like this:

1. Let ACB be a right-angled triangle with right angle CAB.
2. On each of the sides BC, AB, and CA, squares are drawn, CBDE, BAGF, and ACIH, in that order. The construction of squares requires the immediately preceding theorems in Euclid, and depends upon the parallel postulate.^[13]
3. From A, draw a line parallel to BD and CE. It will perpendicularly intersect BC and DE at K and L, respectively…

The proof uses words, symbols and other tools that aren’t points and lines in a plane. Euclid’s proof thus is about geometry but isn’t inside geometry.

How does this apply to logic? Logic is (among other things) the mathematics of arguments. It’s reasonable to wonder if proofs about logic fit inside logic! More precisely, given a particular system of logic S, we can ask what S can and can’t say about itself.

Consider the Liar’s Paradox P:

P = “This sentence is false”.

If P is false, it’s true, and if P is true, it’s false. Thus P is neither. It’s a paradox, a malformed statement. P is a distant ancestor of Gödel’s theorem, in that it warns us of one kind of limit to logic: some statements are neither true nor false.

Let’s leave the Liar’s Paradox now, and look at something more subtle. Consider the statement P’:

P’ = “This sentence cannot be proved in S“.

P’ is not a paradox; P’ is something stranger. As before, there are two possibilities, but the implications are far different.

• If P’ is false, then P’ can be proved in S. This means you can prove false statements in S! S is broken–we say that S is inconsistent.
• If P’ is true, this doesn’t mean that it’s false. It means that P’ can’t be proved inside S. Informally, we have found a proof about S that can’t be stated inside S. So S is incomplete–there are true statements about S that can’t be proved inside S.*

This is the crucial fork in Gödel’s first incompleteness theorem, stated semiformally at Wikipedia as follows:

Any effectively generated** theory capable of expressing elementary arithmetic*** cannot be both consistent and complete.

There’s much more to be said, but to go further we’d need to tighten up the definitions and start building a whole lot of heavy machinery, so instead I’ll stop here.

This post is mostly based on Raymond Smullyan’s explanation of Gödel’s theorems in What Is the Name of This Book?  Smullyan has also presented longer popular examinations of related stuff (like Tarski’s undefinability theorem) in Forever Undecided and Satan, Cantor and Infinity. Smullyan is one of my Great Teachers, and I recommend his books enthusiastically.

*: More precisely, it means that we can create a new system of logic by adding P’ as an axiom to S, and this new system S + P’ is consistent if S is.

**: Here “effectively generated theory” means that the axioms of the theory are not too crazy–a finite computer program could list them. Otherwise, you might be tempted to just keep generating new sentences P’, P”, P”’… and new theories S’ = S + P’, S” = S’ + P”, S”’ = S” + P”’… and if you did that forever and a day, things might get weird.

***: The theory also needs to be able to do basic arithmetic, because the machinery of the proof relies on what we call Gödel numbers. The Gödel number of a formula (a string of symbols) is just a number that encodes that string uniquely, like a binary data file encodes this blog post uniquely. And you need arithmetic to have numbers!