A future episode of my podcast will be interviewing a friend who is a "math nerd" on the mathematics of infinity, Gödel’'s Incompleteness Theorem, and how it all relates to Latter-day Saint theology. In preparation for it, I read Douglas R. Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid. Here is his overview of the Theorem:
Gödel’s Theorem appears as
Proposition VI in his 1931 paper “On Formally Undecidable Proposition in Principia
Mathematica and Related Systems I.” It states:
To every ω-consistent recursive class k
of formulae there correspond recursive class-signs r, such as
neither v Gen r nor Neg (v Gen r) belongs to Flg (k)
(where v is the free variable of r).
Actually, it was in German, and
perhaps you feel that it might as well be in Germany anyway. So here is a
paraphrase in more normal English:
All consistent axiomatic
formulations of number theory
include undecidable propositions.
That is the pearl.
In this pearl it is hard to see a
Strange Loop. That is because the Strange Loop is buried in the oyster—the
proof. The proof of Gödel’s Incompleteness Theorem hinges upon the writing of a
self-referential mathematical statement, in the same way as the Epimenides
paradox is a self-referential statement of language. But whereas it is very
simple to talk about language in language, it is not at all easy to see how a
statement about numbers can talk about itself. In fact, it took genius merely
to connect the idea of self-referential statements with number theory. Once Gödel
had the intuition that such a statement could be created, he was over the major
hurdle. The actual creation of the statement was the working out of this one
beautiful spark of intuition. . . . I will sketch here, in a few strokes, the
core of the idea . . . Mathematical statements—let us concentrate on
number-theoretical ones—are about properties of whole numbers. Whole numbers
are not statements, nor are their properties. A statement of number theory is
not about a statement of number theory; it just is a statement of number
theory. This is the problem, but Gödel realized that there was more here than
meets the eye.
Gödel had the insight that a
statement of number theory could be about a statement of number theory
(possibly even itself), if only numbers could somehow stand for statements. The
idea of a code, in other words, is at the heart of his construction. In
the Gödel Code, usually called “Gödel-numbering”, numbers are made to stand for
symbols and sequences of symbols. That way, each statement of number theory,
being a sequence of specialized symbols, acquires a Gödel number, something
like a telephone number or a license plate, by which it can be referred to. And
this coding trick enables statements of number theory to be understood on two
different levels: as statements of number theory, and also as statements
about statements of number theory.
Once Gödel had invented this coding
scheme, he had to work out in detail a way of transporting the Epimenides
paradox into a number-theoretical formalism. His final transplant of Epimenides
did not say, “This statement of number theory is false”, but rather, “This
statement of number theory does not have any proof”. A great deal of confusion
can be caused by this, because people generally understand the notion of
“proof” rather vaguely. In fact, Gödel’s work was just part of a long attempt
by mathematicians to explicate for themselves what proofs are. The important
thing to keep in mind is that proofs are demonstrations within fixed systems
of propositions. In the case of Gödel’s work, the fixed system of
number0-theoretical reasoning to which the word “proof” refers to that of Principia
Mathematica (P.M.), a giant opus by Bertrand Russell and Alfred North
Whitehead, published between 1910 and 1913. Therefore, the Gödel sentence G.
should more properly be written in English as:
This statement of number theory
does not have any proof
in the system of Principia Mathematica.
Incidentally, this Gödel sentence
G is not Gödel Theorem—no more than the Epimenides sentence is the observation
that “The Epimenides sentence is a paradox.” We can now state what the effect
of discovering G is. Whereas the Epimenides statement creates a paradox since
it is neither true nor false, the Gödel G is unprovable (inside P.M.)
but true. The grand conclusion? That the system of Principia Mathematica is
“incomplete”—there are true statements of number theory which its methods of
proof are too weak to demonstrate.
But if Principia Mathematica was
the first victim of this stroke, it was certainly not the last! The phrase “and
Related Systems” in the title of Gödel’s article is a telling one; for if Gödel’s
result had merely pointed out a defect in the work of Russell and Whitehead,
then others could have been inspired to improve upon P.M. and to outwit Gödel’s
Theorem. But this was not possible: Gödel’s proof pertained to any axiomatic
system which purported to achieve the aims which Whitehead and Russell had set
for themselves. And for each different system, one basic method di the trick.
In short, Gödel showed that provability is a weaker notion than truth, no
matter what axiomatic system is involved.
Therefore Gödel Theorem had an
electrifying effect upon logicians, mathematicians, and philosophers interested
in the foundation of mathematics, for it showed that no fixed system, no matter
how complicated, could represent the complexity of the whole numbers: 0, 1, 2,
3, . . . Modern readers may not be nonplussed by this as readers of 1931 were,
since in the interim our culture has absorbed Gödel’s Theorem, along with the
conceptual revolutions of relativity and quantum mechanics, and their
philosophically disorientating messages have reached the public, even if
cushioned by several layers of translation (and usually obfuscation). There is
a general mood of expectation, these days, of “limitative” results—but back in
1931, this came as a bolt from the blue. (Douglas R. Hofstadter, Gödel,
Escher, Bach: An Eternal Golden Braid [New York: Basic Books, 1979, 1999],
17-19)
Further Reading
Stanford Encyclopedia of Philosophy, Gödel’s Incompleteness Theorems