Categories

# Goedel’s Theorem for Dummies

When people refer to “Goedel’s Theorem” (singular, not plural), they mean the incompleteness theorem that he proved and published in 1931. Kurt Goedel, the Austrian mathematician, actually proved quite a few other theorems, including a completeness theorem for first-order logic. But the incompleteness theorem is the one for which he is most famous.

To get some sense of the impact of Goedel’s Theorem on the mathematical community, consider how Herman Weyl, perhaps the greatest mathematician of the first half of the twentieth century, reacted to it. According to Weyl, up until Goedel’s Theorem, mathematicians were optimistic that all questions in mathematics could be definitively answered either one way or another (see his contribution to Oldenbourg’s Handbook of Philosophy).

Thus, for any mathematical claim, they thought a proof of either it or its negation exists. Goedel’s Theorem showed that this was not the case. Take the famous Goldbach Conjecture, which states that any even number greater than 2 can be written as the sum of two prime numbers (prime numbers are divisible only by themselves and one). To date, mathematicians have been able to find such a pair of prime numbers for any even number greater than 2 that they’ve considered. But they have not been able to prove that this result holds for all even numbers.

Perhaps the Goldbach’s Conjecture is false. But to show that, we would have to produce an even number greater than two that is not the sum of prime numbers. Perhaps it is true. In that case we’ll never find an even number greater than two that is not the sum of two prime numbers, but to actually prove this we cannot simply run through all even numbers, showing that the result holds in each case—that would require checking an infinite number of cases, and proofs in mathematics, some of which are thousands of pages long, nonetheless always consist of a finite number of steps.

What, then, about Goldbach’s Conjecture—does it or its negation admit a strict proof? Prior to Goedel’s Theorem, mathematicians thought that it did. Afterward, they could no longer be sure. Afterward, it might be that Goldbach’s Conjecture or its negation could be proved. But it could also be that Goldbach’s Conjecture was true but not provable. Or it might be false, but its falsehood was not provable.

Goedel’s Theorem shows that mathematical truth and mathematical proof are not the same thing (if they were, Goedel’s Theorem would have been a completeness theorem demonstrating the identity of mathematical truth and proof). Truth is about the way things are; proof is about what we can know to be true. Goedel’s Theorem shows us that there are many claims in mathematics that are true but whose truth we cannot know, at least not by mathematical proof (perhaps God can simply tell us that the claim is true, in which case we might have good reason to believe it, but we still wouldn’t know that it is true in the conventional mathematical sense of having a proof).

In mathematics, we consider ourselves as knowing the axioms of a given mathematical theory—these are usually taken to be self-evident truths and they form a manageable set in the sense that we know whether any claim is or isn’t an axiom. Besides the axioms, we also consider ourselves as knowing the claims that follow via the rules of logic from those axioms. The axioms and their logical consequences are the claims that we can prove. Goedel’s Theorem states that there are always truths that are not knowable in this sense.

Now one might say, well, if there are such truths, why don’t we just add them to our axioms. If we keep doing this, maybe we can render all mathematical truths provable in that way. But this strategy doesn’t work because Goedel’s Theorem shows that every time we add a new axiom, there’s a new “Goedel Sentence” that is true but not provable from the new axiom system.

The key to proving Goedel’s Theorem is constructing what has come to be called a Goedel Sentence, which asserts (and the assertion is provably true!) that it is not provable within the axiom system under consideration. The Goedel Sentence is a self-referential statement, much like “This sentence is false.” By accurately asserting of itself that it is not provable, it ends up being true but not provable. This is a mindbender, but it works, and it shows that there will always be true mathematical statements that we cannot prove. This is the upshot of Goedel’s Theorem.