Gödel's incompleteness theorems

2015-10-04 by qntm

Update, 2016-10-10

This essay had some fairly serious technical errors. You would probably be better off reading this instead.

For every statement of mathematics* S, exactly one of the following two claims is true:

1. S can be proven
2. S cannot be proven

Every statement S has a negation which is also a statement:

~S

So, furthermore, for every statement S exactly one of the following two claims is also true:

A. ~S can be proven
B. ~S cannot be proven

(To put it another way, we might also say:

A. S can be disproven, or
B. S cannot be disproven)

Putting these together, for every statement S exactly one of the following four claims is true:

1A. S can be proven and ~S can be proven
1B. S can be proven and ~S cannot be proven
2A. S cannot be proven and ~S can be proven
2B. S cannot be proven and ~S cannot be proven

Case 1B uncontroversially indicates that S is "true" and case 2A uncontroversially indicates that S is "false". These cases are relatively straightforward and can be put aside.

If case 1A holds, both S and ~S can be proven. Thanks to something called the principle of explosion, this has the logical consequence that all mathematical statements can be proven. Thus, this case indicates that all of mathematics is inconsistent. This is highly undesirable because it renders mathematics totally useless. It would be nice if it were possible to prove that mathematics is consistent!

Case 2B, meanwhile, indicates that S is undecidable, and mathematics as a whole is incomplete — it has a hole in it, a statement which can neither be proven nor disproven. This is not as catastrophic as being inconsistent, but it is still undesirable. It would be nice if it were possible to prove that mathematics is also complete.

With me so far?

Gödel's first incompleteness theorem

Gödel's first incompleteness theorem proves that mathematics is either incomplete or inconsistent. This is done by constructing a special sentence G which is (2B) neither provable nor disprovable. G accomplishes this impressive feat by being self-referential; G can be interpreted as stating "G is not provable".

This is very disappointing, not to say somewhat alarming. Suppose S was a really important conjecture, such as "Every even number is the sum of two primes". Now, this statement is either true or false. And most people implicitly assume that if it is true then it can be proven, and if it is false then it can be disproven.

But Gödel's first incompleteness theorem gives a specific example which breaks this assumed linkage between truth and provability. There is an alarming third possibility: that the statement is true (or false), but it is impossible to prove that it is true (or false) using mathematics.

And if mathematics is inconsistent, there is an even worse fourth possibility: that the statement is true (or false), but it is possible to prove it false (or true)! Kaboom!

So, mathematics can be either complete or consistent, not both. If forced to choose, we would prefer consistent. Can we at least prove that much?

Gödel's second incompleteness theorem

Gödel's second incompleteness theorem proves that if mathematics can prove that it is consistent, then it is inconsistent.

Even more disappointing. Not only does this mean that we can call off the search for such a proof-of-consistency, it means that finding such a proof would be the absolute worst thing that could happen.

So where does this leave us?

In reality, mathematics seems to be consistent so far. Which means it is probably merely incomplete. And that's the best we can ask for.

Big asterisk!

Each time I said "mathematics" above, I was referring to a specific theory of mathematics. A theory of mathematics is a collection of axioms (statements which we assume to be true), combined with all of the statements which can be proven starting from those axioms. In this essay, I was using a very popular theory of mathematics called ZFC.

But you may pick any collection of axioms you wish, and each collection of axioms gives rise to a different theory of mathematics.

Gödel's incompleteness theorems do not apply to all theories of mathematics. There are some extra requirements:

The theory's axioms must be recursively enumerable.
The theory must be capable of supporting elementary arithmetic (addition and multiplication).

Note that ZFC does meet these requirements.

There are theories of mathematics which do not meet these requirements, which are complete and which can prove themselves to be consistent. Unfortunately, such theories are not generally terribly useful.

Another asterisk

Gödel's second incompleteness theorem specifically states that if a theory of mathematics can prove itself consistent, then it is inconsistent.

However, a theory of mathematics can prove the consistency of another theory. For example, ZFC can prove the consistency of Peano arithmetic. And it a more advanced theory of mathematics could prove that ZFC is consistent. But the upward chain doesn't stop...

Gödel's incompleteness theorems