Saturday, January 29, 2022

Douglas R. Hofstadter Summary of Gödel’'s Incompleteness Theorem

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