Kurt Gödel,
whom some have called the greatest logician since Aristotle, undermined the
very foundations of classical mathematics with his Incompleteness Theorem (and,
by the way, thereby reaffirmed his belief in God). To mathematicians, his work was nothing short of
cataclysmic. To most of the rest
us, it is merely counter-intuitive, paradoxical and maddening. I invite you down the rabbit hole into
a realm of paradox worthy of Alice.
Until
Gödel proved his theorem, it was thought that mathematics—alone of the
sciences—was self-contained, not having to refer to anything outside
mathematics. Mathematics was created by
mathematicians as a complete, fenced-off entity, while other scientists had to discover the outside world. More precisely, mathematicians held that any true statement
in any properly set up mathematical system (say arithmetic or algebra) could be
shown to be true by using solely the axioms and rules of that system.
Gödel
proved the opposite. His theorem
shows that any properly set up mathematical system containing arithmetic has
true statements within it that cannot be
proved true by using solely the axioms and rules of that system. Mathematics is therefore not complete unto itself as was supposed. Confirmation of the truths not provable
within mathematics can only be found outside of what had previously been assumed to be a self-contained mathematics. This is where
God came in for Gödel—but more about that later.
It
all started at the turn of the twentieth century, when Bertrand Russell
realized that mathematical logic would always contain contradictions. He illustrated this by using a folksy
paradox about a lone, male barber in a town where every male keeps himself
clean-shaven either by shaving himself or being shaved by the barber. Then, Russell asked, who shaves the
barber? There's the paradox: If
the barber doesn't shave himself then he (the barber) must shave himself; if
the barber shaves himself, then he (the barber) doesn't shave himself.
Such
paradoxes are called self-referential.
In this one, all males must refer themselves to the barber if they don't
shave themselves. The barber,
being male, must thus refer himself to himself to be shaved if he doesn't shave himself, setting up the paradox.
The
proof of Gödel's Incompleteness Theorem is very complicated, but its core
consists of the construction of a true, self-referential arithmetical
proposition that is shown to be unprovable within arithmetic. A taste of the
core argument can be found in a much simpler argument about a supposedly
self-contained truth-telling machine:
1. Imagine a
truth-telling machine M that can answer all questions allowing
solely a yes or no answer about the truth of any statement submitted to it, but by axiom can only answer correctly; that is, it cannot lie. (M stands in the stead of Gödel's starting point of
arithmetic.)
2. Consider
the statement S, that “M will never say S is true.” (This is akin to the self-referential
proposition in arithmetic that Gödel constructed,
for the statement S is defined in terms of the statement S.)
3. Ask M if S
is true.
4. If M says S
is true, then "M will never say S is true" is thereby falsified, so M
has incorrectly answered a question.
Hence, M cannot say that S is true, since by axiom it gives only correct
answers.
5. Step 4 confirms that M will never say S is true,
verifying that the statement S in step 2 is indeed true.
6. Here’s the
dilemma: S is true but M cannot
say so. M is consequently an incomplete truth-telling machine. The answer to "Is S true?"
lies outside of M.
Gödel's
theorem, which rocked the world of mathematics, didn't shock Gödel. He had been a lifelong Platonist,
believing with Plato that anything we can see or conceive of is just a poor
shadow of an eternal, objective ideal that exists beyond the real world. It was hence no surprise to him that
there are mathematical truths that mathematics cannot prove. He concluded that proofs of those truths
are part of the omniscience of an eternal God who is external to the real
world, thus strengthening his long-held theism. In his later years, Gödel even tried to construct a formal
logical proof of God's existence.
Gödel
published his theorem in 1931, when he was just 25. He fled the Nazis from his
native Austria in 1938, and spent his last forty years at the Institute for
Advanced Study in Princeton, where he became Albert Einstein's closest
intellectual companion until Einstein's death in 1955.
As
I suggested at the outset, understanding paradoxes like those I've described
can be maddening—perhaps just reading this blog posting has had that effect on
you. Worse, they might quite
literally drive mad those whose life work involves them, and perhaps that's
what happened to Gödel. In a great
irony, Gödel died in 1978 in a self-referential sort of way, so convinced that
people were trying to poison him that he refused to eat and died of starvation.
If
you want to read more about Gödel—the man, his life, his times, and details
about his theorem and its proof—I recommend Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein.