Gödel’s Incompleteness Theorem – An Informal Explanation Of The Argument

Gödel’s first Incompleteness Theorem involves some significant technical achievements but is actually based on a very straightforward argument.  Let’s examine that argument.

In brief, what Gödel argues is that any formal language that is sufficiently rich that it can:

(i)            Enumerate formulas;

(ii)          Refer to formulas by their numbers;

(iii)         Express the predicate ‘x is provable’; and

(iv)         Express negation;

will have the following property:

If the system is sound, i.e. contains no falsehoods, then there will be formulas expressible in the system that are not provable in that system. 

Gödel shows that the formal language of Russell and Whitehead’s Principia Mathematica, which can produce the formulas of arithmetic, is just such a language.  Accordingly, he concludes that arithmetic can contain unprovable formulas.  This is a more technical part, so I will just focus on how the core argument works.

To begin, suppose we can enumerate, i.e. list, all the formulas of our system.  For example:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 2 + 2 = 2 + 1 +1

(4) 1 + 1 > 0 + 1

…

Okay, now a question arises: how shall we order this list?  It isn’t really important how so long as we have a 1-1 correspondence between numbers and formulas in our list, so we will choose something such as the following: we list our formulas in ascending order of number of terms in the formula; where there is a tie, we break it alphabetically, e.g. 1 = 1 comes before 2 = 2.

So, let’s put our list in order:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 1 + 1 > 0 + 1

(4) 2 + 2 = 2 + 1 + 1

…

Okay, that’s (i) above.  Now consider the following addition to our list:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 1 + 1 > 0 + 1

(4) 2 + 2 = 2 + 1 + 1

(5) Formula (4) has more terms than formula (3)

What we have done in formula (5) is pick out, or refer to, other formulas by their numbers, i.e. location in the list.  This is straightforward, so that’s (ii).  Next, let’s continue our list but add a new resource, the predicate ‘x is provable’:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 1 + 1 > 0 + 1

(4) 2 + 2 = 2 + 1 + 1

(5) Formula (4) has more terms than formula (3)

(6) Formula (4) is provable.

What we have done at this step is nothing other than what we have already done, except for the addition of the new predicate.  So that’s (iii).

Pause here for a moment to notice that the order in which we list our formulas is arbitrary: we could have chosen another order just as easily (maybe in descending order of number of terms, for example).  Accordingly, what has ended up here as formula (4) might have been formula (3,245) in another list.  We can think of it this way: suppose we write each formula on a card and instead of stacking the cards randomly, we put them in order according to our rule.  So the card with ‘2 + 2 = 2 + 1 + 1’ ends up as the fourth card in our stack, but wouldn’t have had we used another ordering rule.  Still, once cards are put in their place on the list, we can refer to them by their number.

What this means is that the card with ‘Formula (4) is provable’ written on it will be true or false depending on how we stack the cards: one ordering may put a card in slot (4) that is not provable; another one may put a card there that is.  Also, the card with ‘Formula (4) is provable’ written on it may occur in slot (6) as above, but it may otherwise have occurred in slot (1) or slot (1,000,000).

Okay, so let’s continue our list of formulas.  We will use the resources we have used so far with the addition of one more, negation:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 1 + 1 > 0 + 1

(4) 2 + 2 = 2 + 1 + 1

(5) Formula (4) has more terms than formula (3)

(6) Formula (4) is provable

(7) It is not the case that formula (1) is provable

By employing negation, formula (7) tells us that the first formula on the list is unprovable (assume for now that this is true).  We have now made use of all of (i) – (iv) above.

So, let’s put all the resources together in one more addition to our list:

(1) 0 = 0

(2) 1 + 0 = 1

(3) 1 + 1 > 0 + 1

(4) 2 + 2 = 2 + 1 + 1

(5) Formula (4) has more terms than formula (3)

(6) Formula (4) is provable

(7) It is not the case that formula (1) is provable

(8) It is not the case that formula (8) is provable

Formula (8) is almost exactly like formula (7); though it refers to formula (8) rather than formula (1), there is nothing untoward in that.  Recall that the formulas could have been put in another order if we had so chosen; it is simply ‘luck’ that the card with ‘It is not the case that formula 8 is provable’ landed in spot (8) on our list – had we ordered things differently, it might have ended up in slot (2).  But, the point is that there is nothing fishy about this formula landing in slot (8) – if a formula can refer to a formula by number, it can refer to itself by its own number: it is very easy to create such a formula, as has just been done above, all in accord with (i) – (iv).

In sum, formula (8) refers to a formula by its number, employs the predicate ‘x is provable’, and makes use of negation.  It is a perfectly legitimate entry in any list that involves a language rich enough to include (i) – (iv). 

Okay, but now consider formula (8).  If (8) is provable, then (8) must be false.  Why?  Well, simply because (8) expresses the proposition that it is note the case that (8) is provable, which can only be true if (8) is not provable.  So, (8) can only be provable if it is false, in which case the system as a whole contains a false formula (namely, (8)).  But that is the argument in a nutshell: if we assume the system contains no falsehoods, and is rich enough to allow for (i) – (iv), then there will always be a formula expressible in the system – (8) in our little example – that is not provable. 

So, a sound system rich enough to allow for recursive enumeration, negation and the predicate ‘x is provable’ will always admit unprovable formulas.  That’s the gist of the first incompleteness theorem.  Once Gödel showed that arithmetic is a formal system in which all these conditions apply, he had proven that arithmetic is incomplete with respect to provability. 

Notice that we know that (8) is true.  If (8) were provable, then the system would contain a falsehood, so (8) must not be provable, which is precisely what it expresses.  Hence, something can be true without being provable. For Gödel, it is the assumption of universal provability that leads to trouble, not the assumption of soundness, i.e. universal truth, in a formal system.

What is particularly interesting, in my opinion, is Gödel’s employment of Gödel Numbering to show that formulas that express “such-and-such is a proof of so-and-so” can be rendered as ordinary arithmetic equations.  Hence, all of the foregoing can be done from within the language of mathematics itself.  The language of mathematics is suitable for meta-mathematics, at least in this instance.