Incompleteness Read online

  The answer seems to be that Carnap had not understood the nature of Gödel’s discovery at all. The idea that the criteria for semantic truth could be separated from the criteria for provability was so unthinkable from a positivist point of view that the substance of the theorem simply could not penetrate.

  This delay in grasping the significance of what Gödel was trying to tell him is borne out from another entry in Carnap’s journal, dated 7 February 1931, after Gödel’s famous paper had already been published. “Gödel hier. Über seine Arbeit, ich sage, dass sie doch schwer verständig ist. Gödel was here. About his work, I say that it’s very difficult to understand.”

  The thundering silence greeting Gödel’s announcement seems, in retrospect, a classic example of the sort of insensibility that Thomas Kuhn discusses in The Structure of Scientific Revolutions:

  In science . . . novelty emerges only with difficulty, manifested by resistance, against a background provided by expectation. Initially only the anticipated and usual are experienced even under circumstances where anomaly is later to be observed.

  Von Neumann Takes the Hint

  There happened to have been one person present at Königsberg who picked up on the anomalous remark of the young logician, and that was John von Neumann. His appreciation of Gödel’s terse remark is all the more impressive if we consider that von Neumann’s own views were entirely in keeping with Hilbert’s—he had been the designated spokesman in Königsberg for formalism—and that he harbored the sort of strongly positivist bent that would make Gödel’s reference to semantic truth, independent of a formal system, perhaps seem dangerously metaphysical. Nonetheless he buttonholed Gödel after the discussion ended for the day and pumped him for details. Gödel must have told him enough about how he had arrived at his conclusion for von Neumann to take what he heard seriously. He went back to Princeton, to the Institute for Advanced Study, and continued to ponder the astounding pronouncement he’d heard in Königsberg.

  Some time in the course of his pondering, von Neumann happened on a remarkable corollary to what Gödel had told him. Von Neumann had seen from what Gödel had told him that Gödel’s proof was conditional: what it says is that if a formal system S of arithmetic is consistent, then it’s possible to construct a proposition, call it G, that’s true but unprovable in that system. So if S is consistent, G is both true and unprovable. Trivially, then, if S is consistent then G is true. Von Neumann had also understood from what Gödel told him that this proof can itself be carried out in a system of arithmetic. (This is the trick that’s accomplished by Gödel numbering.) So if the consistency of S could be proved in S, then G would have been proved in S—since it follows from the consistency of S that G is true. But this contradicts that G is unprovable. The only way out of the contradiction is to deny that S can be formally proved to be consistent within the system of arithmetic. So from Gödel’s result another impossibility follows: it is impossible to formally prove the consistency of a system of arithmetic within that system of arithmetic.

  Von Neumann got in touch with Gödel, informing him of this corollary, and Gödel politely told von Neumann that the older man had indeed drawn the correct conclusion, one which Gödel had already rigorously proved. (One can imagine Gödel’s slight crooked grin in imparting this information to the intellectual titan, von Neumann.) This corollary is known as Gödel’s second incompleteness theorem, and though it’s merely a consequence of the first, it’s the one that first received attention, with von Neumann talking it up at the Institute. Hilbert’s program had provided the context for perceiving the significance of Gödel’s second incompleteness theorem. Gödel had proved that Hilbert’s second problem could not be solved: there would never be a finitary formal proof of the consistency of the axioms of arithmetic within the system of arithmetic. There would never be the proof that was to serve as the linchpin for Hilbert’s program. The consequences for formalism were stark and devastating.

  It’s clear from the semantic point of view—that is, when we think about what the strictly formal system of arithmetic means—that arithmetic is consistent, since it has a model in the natural numbers. We give a model of a formal system, also called an interpretation, by specifying a universe of discourse, also called a domain of individuals, over which the variables range, and by interpreting what the predicate and relational terms mean, and stipulating which members of the domain the individual constants refer to. When the formal system of arithmetic is endowed with the usual meanings, involving the natural numbers and their properties, its axioms are seen to be clearly true and thus must be consistent since true statements can’t have false consequences. It isn’t that the consistency of arithmetic was really in doubt—that is, if one really does believe in numbers. The question concerns how consistency can be proved—an important question from any metamathematical point of view, an urgent question for all but the Platonist.

  The consistency of a system amounts to the proposition that using the rules of the system no contradiction can be derived. This proposition is itself combinatoric; it concerns simple rules of symbol manipulation—rules that determine which string of symbols follow from which strings of symbols. This combinatoric proposition is, precisely because it is combinatoric, equivalent to something arithmetical. Thus it can itself be formulated within the system—and so the question naturally is whether it can be proved within the system, and the answer is that it can’t be. The syntactic features of formal systems—which were meant to obviate intuitions, those breeders of paradox—can’t capture all the truths about the system, including the truth of its own consistency. Gödel had proven that consistency, the very thing whose proof was supposed to secure the foundations of Hilbert’s program (which had been meant to preclude the formation of paradoxes in mathematics) transcended the grasp of that program.

  The possibility of paradox, meant to be forever eliminated by Hilbert’s program, reasserted itself. And one of the strangest things about the odd and beautiful proof that subverted Hilbert’s defense against paradox was the way in which paradox itself was incorporated into the very structure of the proof.

  The First Incompleteness Theorem: The Overall Strategy

  The twenty-odd pages of Gödel’s famous proof are densely compact. There are 46 preliminary definitions. There are also preliminary theorems that must be proved before the main event can take place: the construction of an arithmetical proposition that is both true and unprovable within the formal system under consideration. The lines of reasoning in the proof are highly compressed, composed of a hierarchy of interconnected levels of discourse, the blended voices of the symphony.4

  Though the details of the proof are difficult, the overall strategy is—happily!—almost simplicity itself. Simple but strange, as one would expect of a proof that draws so close to the edge of self-contradiction, proving that there are true arithmetical propositions that are not provable. One of the strangest things of all about the proof is that it co-opts the very structure of self-referential paradoxes, those abominations to reason, and reshapes that structure to its own ends. The overall strategy of the proof—the delightfully accessible part of the proof—can be grasped in the context of the oldest known paradox of all, the liar’s paradox.5 We can convey the gist of the proof in a breezy, easy way, which we will now proceed to do. Then in the next few sections we will concentrate on filling in a few more of the details, indicating how the hard work gets done.

  By tradition, the liar’s paradox is attributed to the Cretan Epimenides, who reputedly said something implying: All Cretans are liars. This sentence, in itself, isn’t paradoxical, except insofar as it suggests that what Epimenides was saying was something like this:

  This very sentence is false.

  Now that sentence, as we’ve already seen, is true if and only if it’s false—not a good situation, logically speaking. Gödel’s strategy involves considering an analogue to that paradoxical sentence, viz. the proposition:

  This very statement is not provabl
e within this system.

  Let’s call this sentence G. G, unlike its analogue, isn’t paradoxical, though it is, like all self-referential propositions, somewhat strange. (Even the nonparadoxical self-referential This very statement is true is mystifyingly strange. What’s it saying? Where’s its content?)

  Through the system of encoding we have come to call “Gödel numbering” (of course self-effacing Gödel didn’t name it so) G can be rendered in arithmetical notation, so that it also makes an arithmetical statement. Here is one of the places where the hard work comes in, and a bit later on in this chapter we’ll dip a little deeper into this aspect of the proof. Gödel found an ingenious way of making an arithmetical language speak of its own formalism. The upshot of the technique is that G is simultaneously making two different statements, asserting an arithmetical claim and also asserting its own unprovability. In other words, what G has to say, in addition to its straightforward arithmetical content (it’s going to be a weird arithmetical proposition, what with all the fiddlefaddling that gets us to it) is:

  G is unprovable in the system.

  The negation of G thus amounts to the proposition:

  G is provable in the system.

  If G were provable then its negation—which, after all, says that G is provable—would be true. But if the negation of a proposition is true, then the proposition itself is false. So if G is provable then it is false. But if G is provable, then it is also true. After all, what else does a proof show, assuming of course that the system is consistent (since in an inconsistent system all propositions are provable). So, assuming the consistency of the system, if G is provable then it is both true and false—a contradiction—which means that G is not provable. Thus if the system is consistent, then G is not provable in it. But that is exactly what G says: that it isn’t provable. So G is true. Therefore, G is both unprovable and true, which is precisely the famous conclusion of Gödel’s proof, that there is a true but unprovable proposition expressible in the system if the system is consistent. And because G also has a straightforwardly arithmetical meaning which, of course, is true if G is true (because it is G) Gödel’s proof shows that there are arithmetical truths (for example, G!) that cannot be proved within the formal system, assuming the system to be consistent. The formal system is either inconsistent or incomplete.

  What is more, the proof demonstrates that should we try to remedy the incompleteness by explicitly adding G on as an axiom, thus creating a new, expanded formal system, then a counterpart to G can be constructed within that expanded system that is true but unprovable in the expanded system. The conclusion: There are provably unprovable, but nevertheless true, propositions in any formal system that contains elementary arithmetic, assuming that system to be consistent. A system rich enough to contain arithmetic cannot be both consistent and complete.

  That’s really the overall strategy. In some sense (once one assimilates the strange idea of a single proposition that can speak simultaneously of itself and of arithmetic), it is simple. Of course, the devil is all in the details; and it’s to the diabolical details that we will now turn.

  Step One: Lay Out a Formal System

  Gödel begins his proof by laying out his formal system, which consists, as do all formal systems, of an alphabet of symbols, rules for combining these symbols into wffs, a special set of wffs called the “axioms,” and a deductive apparatus for deriving (as “logical consequences”) wffs from other wffs that must be either axioms or consequences of axioms.

  In most systems of formal logic, it is convenient to have symbols for “and”(conjunction) and “or” (disjunction), as well as for the expressions “if . . . then . . .” (material implication) and “. . . if and only if . . .”. There are also symbols that express the quantificational notions of “all” and “some.” However, it will be more convenient to have as few basic symbols as possible. We can eliminate conjunctions in favor of disjunctions since “p and q” means the same thing as “it’s not the case that p is false or q is false.” So I want to eat and I want to be thin is equivalent to It’s not true that either I don’t want to eat or don’t want to be thin. Then we can take our elimination one step further since disjunction can be eliminated in favor of material implication because “if p, then q” means the same thing as “not-p or q.” We can also eliminate the notion of “some,” by using the notion of “all” since “there are some x’s that are F” is the same as “it is not the case that all x’s are not F.” So Some logicians are rational is equivalent to Not all logicians are irrational. After our eliminations, we’re left with nine primitive concepts, and corresponding symbols, with which to express all of arithmetic in a formal system.

  Step Two: Gödel Numbering

  The next step in the proof is to devise a mechanical method of assigning a unique number to every proposition of the system. It’s by assigning these numbers that the blending of the voices is accomplished, with arithmetical statements also making metamathematical statements.

  The logician Simon Kochen beautifully described Gödel’s proof to me as bearing a marked similarity to Kafka’s work (which Gödel happened to admire). In both Kafka and Gödel, there is a certain Alice-in-Wonderland quality, a sense that one has entered a strange universe where things morph into others, including meanings themselves. Yet everything proceeds stepwise according to the most rigorous rule-bound logic. (The rigorous logic of Kafka is under-appreciated.) So much of the work in Gödel’s proof amounts, in Kochen’s words, to “bookkeeping.” This double aspect of the proof mirrors something, Kochen also said, essential about Gödel’s mind as well, the wild leaps of imagination coupled with a sort of legalistic ploddingness. Both of these aspects emerge in the Gödel numbering. Here’s the basic idea:

  The formal system, remember, involves a variety of types of objects: the symbols of the alphabet, the combinations of symbols into wffs, and special sequences of wffs (in other words, proofs). Everything is built out of the basic symbols of the alphabet: a wff is a sequence of these symbols, and a proof is a sequence of wffs (with the conclusion simply the last entry in the sequence).

  The Gödel numbering thus begins by assigning each primitive symbol of the alphabet a number. Once each of the primitive symbols has a number, one continues with a rule for assigning numbers to the wffs themselves, based on the corresponding numbers of their constituents. Then, once we have a Gödel number for each wff, the Gödel numbering is completed with a rule for assigning numbers to sequences of wffs, which, of course, are what proofs are.

  Furthermore, once every wff has been assigned a corresponding number, we will be able to analyze the structural relationships between the propositions by merely analyzing the arithmetical relationships between their corresponding numbers. Or vice versa. For example, one wff will be a consequence of another one precisely in case the Gödel numbers of the wffs are arithmetically related to each other in just the right way. In other words, two different sorts of descriptions will be collapsed into one another: arithmetical descriptions, setting forth relationships between numbers that are expressible within the formal system; and metadescriptions about the logical relationships holding between the wffs in the system. These metastatements are purely syntactic, as they are simply the consequences of the syntax of the formal system, that is, its rules.

  The idea of Gödel numbering is basically the idea of encoding, which allows you to move back and forth between the original propositions and the code. In elementary school, my friends and I had a similar code we’d use to pass notes in class, assigning each letter of the alphabet a number between 1 and 26, with “A” assigned 1, “B” assigned 2, etc. “Meet me” was rendered as: 13 5 5 20 13 5.

  The encoding system Gödel used had to ensure that the same Gödel number wouldn’t be assigned to different things, say to both some wff as well as to a sequence of wffs (a proof). The rules for encoding give us an algorithm (which is, remember, a set of rules which tell us, at each step, how to proceed, often based on the result we
get from a previous application of rules in the set) for getting from any wff, or sequence of wffs, to a unique Gödel number. There is also an algorithm for the reverse process: given any Gödel number, we can effectively figure out what formal object in the system it stands for. The Gödel numbering must obey one further condition: the translation of syntactic descriptions of the logical relationships between wffs in the system into arithmetical propositions that it provides must be such that these arithmetical propositions are themselves expressible within the system.

  The spirit of Gödel numbering can be conveyed simply, though were we to be rigorous, as Gödel of course was, there would be nothing simple about the encoding. The modern positional notation is so familiar to us that we forget it is itself a coding system, requiring proof in the formal system. So, for example, the usual digital symbol 365 is shorthand for 3 times 10 squared, plus six times 10, plus five. Gödel’s system of encoding used the exponential products of prime numbers and relied on the prime factorization theorem which states that every number can be uniquely factored into the product of primes. The prime factorization theorem ensured that there was an algorithm for getting from any wff or sequence of wffs to a Gödel number and vice versa. The digit juxtaposition we use below would, if made rigorous, be every bit as complicated as the system that Gödel used. But we won’t be rigorous.