Incompleteness Read online

  Rudolf Carnap traveled by train from Vienna with Gödel to deliver a paper entitled “The Main Ideas of Logicism,” presenting the view that mathematical truths are ultimately reducible to the tautologies of logic. Arend Heyting, a Dutch mathematician, spoke on “The Intuitionist Foundations of Mathematics,” urging the banishing of all but strictly constructivist proofs, not making reference to any notions that are not strictly finite or at least denumerable. (The result would be to eliminate a great deal of beautiful mathematics.) David Hilbert, the leading spokesperson for formalism, did not travel from Göttingen, but his formalist point of view had an eminently worthy spokesman in John von Neumann. There was also a paper entitled “The Nature of Mathematics: Wittgenstein’s Standpoint” by the long-suffering Wittgensteinian epigone, Frederich Waismann.

  Logicism, intuitionism, formalism, Wittgenstein: there was no representative of Platonism to argue that point of view on the first day in Königsberg. All the views represented there that day were committed to the claim that the notion of mathematical truth was reducible to provability; the disagreements between them were on the conditions of provability.

  It had been because Waismann was preparing for his talk in Königsberg that Wittgenstein had been meeting with him and Schlick, in Schlick’s house, on a regular basis in the summer of 1930. The central points of Waismann’s lecture, according to Wittgenstein’s biographer Ray Monk, were: “. . . the application of the Verification Principle to mathematics to form the basic rule: ‘The meaning of a mathematical concept is the mode of its use and the sense of a mathematical proposition is the method of its verification.’ ”

  Monk goes on to say: “In any event, Waismann’s lecture, and all other contributions to the conference, were overshadowed by the announcement there of Gödel’s famous Incompleteness Proof.”

  This is not, in point of fact, how it went at the conference in Königsberg. It is understandable that Wittgenstein’s biographer would assume that the announcement of Gödel’s “famous Incompleteness Proof” would have caused a sensation among the participants at the conference, who had heard talks on that first day incompatible with such a result as Gödel’s, each talk presuming that the concept of mathematical truth is, one way or another, reducible to provability. But Gödel’s “announcement” went almost unheard.

  It is true that Waismann’s talk did not hold its own among the other three, but this is because, as Menger and others report, the other participants agreed that Wittgenstein’s views were not yet ripe enough for debate. Waismann was not shoved into the shadows because Gödel took the limelight. In fact, Gödel’s announcement, delivered during the summarizing session on the third and last day of the conference, was so understated and casual—so thoroughly undramatic—that it hardly qualified as an announcement, and no one present, with one exception, paid it any mind at all.

  Gödel’s First Great Overlooked Moment: A Triviality Not So Trivial

  The 20-minute talk that Gödel had delivered on the second day of the conference had also attracted little attention. It was basically a précis of the work he had done the year before for his Ph.D. dissertation, work not on incompleteness but rather on completeness. What Gödel had done was to prove the completeness of what is called the “predicate calculus” or sometimes “first-order logic” or again “quantificational logic.” Never mind the ugly names, causing poetic souls to duck for cover. Let’s rechristen the relevant system of formal logic “limpid logic.” Gödel proved that limpid logic is complete. Its axioms and rules of inference allow one to prove all logically true, or tautologous, propositions within it. But what is this notion of logically true or tautologous?

  Limpid logic’s symbolism allows one to represent propositions so that they are stripped down to their naked logical form. It provides a way of symbolizing the logical form of propositions and displaying the logical connections between them. It has symbols for such words as not, and, or, if . . . then . . . , if and only if as well as such “quantificational” concepts as all, none, and some. Words such as these are the logically relevant ones. It’s the meanings of these terms, as defined by the rules of the system, that determine the logical form of propositions. Different sentences can share the same logical form and, from the point of view of limpid logic, these sentences are essentially the same, since they are logically the same (thus continuing the move toward logical generality, which is one and the same with the development of the science of logic fathered by Aristotle.

  So, for example, consider the sentences “all married men are married,” “all beautiful babies are beautiful,” “all valid arguments are valid.” All of these sentences are spun out from the more general proposition that if something has two predicates P and Q, say, being both a baby and being beautiful, then it has one of those predicates, say, being beautiful.

  Limpid logic categorizes whole hosts of sentences in terms of their shared logical form, stripping away all the meanings of specific predicates and subjects to get down to the naked logic. So far as the nonlogical terms go, these refer either to individuals—whether to specific ones or to any of them—and to predicates and relations between them. To refer to any of the individuals we use variables like x and y, and to refer to specific individuals we use constants, like a or b. Properties are designated by predicate constants like P and Q, and then there are relational terms like R. The easiest thing we can say in limpid logic is that some individual has some predicate: P(a). We read this as: P of a. A slightly more complicated statement is that some individual bears a particular relation to another: R(a b). Then we might want to say something like: there is some individual or other that has a particular property. This is symbolized as ∃xP(x), and is read: there exists an x such that P of x. Or we might want to say that all individuals have P. In limpid logic this is symbolized as (x)P(x), and is read: given any x, P of x. A logically true proposition, or a tautology, is one that is true no matter what meanings we substitute for the nonlogical terms. (Since “logically true” thus makes reference to meanings—something is logically true if it’s true no matter what meanings we assign to its nonlogical terms—it’s a semantic, rather than syntactic, notion.)

  So, for example, suppose we want to say that if something has two specific predicates then it has one of those predicates. We would symbolize this:

  (x) (P(x) and Q (x)) → Q(x)1

  This is read: given any x, if x has the property P and x also has the property Q, then x has the property Q. This is logically true and will generate a whole heap of true propositions, formed by substituting in particular meanings for P and Q.

  Here’s another logically true proposition from limpid logic:

  (x) (y) ((x = y) → (P(x) ↔ P(y)))

  This means: for all x, for all y, if x equals y, then x has the property P if and only if y has the property P. Of course it doesn’t take too much thought to see that this has to be the case, that is, that if two things are really not two but rather identical, then all the properties of the one are the properties of the other. (What we really have in the case of identity, is one thing being designated, or picked out, in two ways.)

  From this last formally true proposition of limpid logic we can get out such verities as: If Gödel is the author of the incompleteness theorems, then Gödel is a Platonist if and only if the author of the incompleteness theorems is a Platonist. If Professor Moriarty is the mastermind behind all the crime in London then Professor Moriarty is a mathematician if and only if the mastermind behind all the crime in London is a mathematician. If the moon is the goddess Diana, then the moon is made out of green cheese if and only if the goddess Diana is made out of green cheese. Obviously, you can fill in anything at all for your predicate P and generate a trivially true statement, because (x) (y) (x = y) → (P(x) ↔ P(y)) is logically true. It’s a tautology, its truth a function of the meanings of the logical terms that compose it.

  Gödel’s completeness theorem, the result he presented to the conference of logical luminaries, proved that al
l such logically true propositions are provable within the formal system of limpid logic. Another way of stating Gödel’s completeness result is that in limpid logic syntactic and semantic truth are equivalent: the truths that follow from the rules of the system (the syntactic truths) yield all the logically true propositions expressible within the system. Limpid logic is, then, not only consistent (its consistency had already been proved) but also complete. (Inconsistent systems are of course complete, because we can prove anything at all in them. They’re overcomplete. It’s of consistent systems that the question is posed: are they complete? Do their formal syntactic rules allow one to prove everything one would like to be able to prove? Do they allow one to prove all the truths that are expressible within the system?)

  Completeness is exactly what one would like from one’s formal system of logic, and it was one of the problems for which Hilbert had demanded a solution. It was reassuring to have a proof, but since the conclusion had never really been in doubt, Gödel’s Ph.D. result hardly seemed exciting. The young man had taken the trouble to prove what everyone already took for granted.

  In hindsight, we can see that what Gödel had proven in his dissertation was far more interesting—cause for far more concern among formalists and fellow travelers—than it had first appeared. Gödel had proven the expected result—completeness—but the difficulty of proving it—the substantive proof, of many steps, it required—should have struck people as unexpected, even alarming. In showing how complicated it was to actually prove the completeness of limpid logic Gödel was certainly creating room for the possibility that other consistent formal systems, those, for example, enriched by the axioms of arithmetic, might not be complete. The nontriviality of the proof of completeness for limpid logic must have forcefully presented the possibility to Platonist Gödel that there were propositions that were arithmetically true but not provable within a formal system of arithmetic.2

  The Quietest Explosion: Gödel Announces His Result

  Gödel gave no indication of the revolution he was hiding up his sleeve until the last day of the conference, which had been reserved for general discussion of the papers of the two preceding days. He waited until quite late in the general discussion and then he mentioned, in a single immaculately worded sentence, that it was possible that there might be true, though unprovable, arithmetical propositions, and moreover that he had proved that there are:

  One can (assuming the [formal] consistency of classical mathematics) even give examples of propositions (and indeed of such a type as Goldbach and Fermat3) which are really contextually [materially] true but unprovable in the formal system of classical mathematics.

  That was it. The proof that was to become the “famous Incompleteness Proof” had apparently been accomplished the year before, when Gödel was 23, and it was to be submitted in 1932 as his Habilitationsschrift, the last stage in the prolonged process of becoming an Austrian or German Dozent. It is one of the most astounding pieces of mathematical reasoning ever produced, astounding both in the simplicity of its main strategy and in the complexity of its details, the painstaking translating of metamathematics into mathematics by way of what has come to be called Gödel numbering. It is a thoroughly ordered blending of several layers of “voices,” both mathematical and metamathematical, counterpoint merging into harmonic chords never before heard. Music does seem to provide a particularly apt metaphor, which is why Ernest Nagel and James R. Newman in their classic explicatory work, Gödel’s Proof, described the proof as an “amazing intellectual symphony.”

  It must have been an extraordinarily exhilarating experience to have produced such mathematical music, especially since it is mathematics that sings, at least in the ear of its composer, of his beloved Platonism. But Gödel had not let a single note of his symphonic proof escape until this muted moment in Königsberg. Such a noiseless, inexpressive exterior enclosing such a swelling mathematical noise. Then, at long last, he pronounced one tersely precise sentence, dropped in medias res on the last day of a conference, in the middle of the rehashing of the previous days’ pronouncements. Gödel brought it out with no fanfare, played it barely pianissimo.

  The idiosyncratic “announcement” is congruent with the logician’s personality. The concise statement that composed his “shining hour,” lasting maybe 30 seconds tops, is meticulously crafted, a miniature masterpiece. It says what it needs to say, and not a word more. He must have prepared it “to the last detail” (to echo the encomium he bestowed on Hahn’s lectures) and given careful thought, too, as to the precise moment when he would launch it into the discussion: toward the end of the three days, as the conclusive refutation of all the metapositions heretofore argued. The man who indicated with slight movements of his head when he agreed, disagreed, or was skeptical, must have thought that the vast significance of his remark would emerge in stunning relief for the audience at Königsberg.

  Delivery, even on the most rigorous subjects, can make quite a difference to the reception of one’s ideas. Self-importance helps; a heavy, elaborately carved frame can make the sketchiest artwork seem important. We have no first-hand accounts of the manner of Gödel’s presentation that October day in 1930; of the sort of expressive framing he gave to what was the mathematical analogue to a painting representing the nature of beauty itself. But we know enough about the emphatically anti-charismatic Gödel, with his aversion to external drama and his absolute faith in logical implication, to be able to imagine how it went. The somber and uninflected statement of the crux of the matter, with no rhetorical flourishes, no hyped-up context to help his listeners grasp the importance of what was being said. No Sturm und Drang, only zipped-up genius emitting an austere sentence that implied the existence of a proof of unprecedented nature and scope.

  “The more I think about language,” he had remarked to Menger, walking home after an evening with the “Wittgensteinians,” “the more it amazes me that people ever understand each other.” Such pessimism about the possibilities for communication—even at this early age, before the decades that brought so much celebratory misunderstanding of his work—must certainly have stoked his desire to find a strict mathematical proof to say all that he had to say on the nature of mathematical truth and knowledge. Now he had such a proof and he was announcing its result, or at least the first of the two theorems to follow from it. Had he anticipated that dumbfounded disbelief would follow the dropping of his bombshell, and then a violent volley of targeted questions? Had he prepared himself conscientiously for all the demands for further elucidation that would be expected quite naturally to follow, much as Wittgenstein’s biographer had imagined the scene?

  Gödel was always to be disappointed by the abilities of others to draw the implications he had scrupulously prepared for them, and his experience at Königsberg must have been a magnificent disappointment, for the response was a resounding silence. The immaculately composed sentence was delivered . . . and the discussion proceeded as if it hadn’t been. The edited transcript of the discussion that day was published in the journal Erkenntnis (edited by Carnap and Reichenbach, and the main organ for the dissemination of the views of both the Vienna Circle and Reichenbach’s Berlin group) and it does not include any discussion of Gödel’s remark at all. No mention of Gödel made it into the account of the meeting written up by Hans Reichenbach either.

  Even taking into account Gödel’s anti-charismatic mode of being in the world, shouldn’t his remark have provoked a ripple of disturbance, an “Excuse me, Herr Gödel, but I somehow thought you just said that you’d proved the existence of unprovable arithmetical truths. Of course, you couldn’t have been saying that because, besides flying in the face of all of our views on the nature of mathematical truth, that sounds like a contradiction in terms. How could you prove that there are arithmetical propositions that are both unprovable and true? Wouldn’t that proof, in showing them to be true, constitute a proof of them, thus contradicting your claim that the proof proves them unprovable? Logician that you are
, you couldn’t be asserting a blatant contradiction like that. So what did you really say?”

  Gödel’s dissertation advisor, Hans Hahn, was present at Königsberg. In fact, he chaired the last-day discussion at the conference. Had Gödel shared nothing of his incompleteness proof with his advisor? We don’t know for sure either way. Hao Wang writes that Gödel completed his dissertation, the completeness proof for predicate logic (i.e., limpid logic), without showing it to Hahn. That result was being prepared for publication at the time of the conference (and, presumably, Hahn had read it by then). In his introductory remarks to the dissertation, which for some unknown reason were deleted from the published version, Gödel had raised the possibility of the incompleteness of arithmetic, though he gave no indication that he had proved it. Hahn must have read that remark and not taken it seriously. Maybe it was he who advised the young author to delete it. Maybe he didn’t want his student to go out on a fragile limb with no proof to support him, having assumed, from all that Gödel had told him (or, more relevantly hadn’t), that there was no supporting proof.

  Another person at the conference who might have been expected to react to Gödel’s remark was Rudolf Carnap. Carnap had had more time than the others to digest Gödel’s news, since Gödel had confided his result to Carnap several weeks before. On 26 August 1930, according to Carnap’s Aufzeichnungen in his Nachlass, he had met with Gödel, Feigl, and Waismann in the Café Reichsrat in Vienna to discuss their travel plans to Königsberg. After settling the practicalities, the discussion turned, in Carnap’s words, to “Gödel’s Entdeckung: Unvollständigkeit des Systems der PM; Schwierigkeit des Widerspruchsfreiheitbeweises: Gödel’s discovery. The incompleteness of the system of Principia Mathematica. The difficulty of proving consistency.” (Note that he says “difficulty” here, not yet impossibility. Gödel didn’t fully prove his second incompleteness theorem until after the conference.) Then again, three days later, Carnap records that the same four met at the same café and that before Feigl and Waismann arrived “erzählt mir Gödel von seinen Entdeckungen—Gödel told me about his discoveries.” Still, at the conference Carnap had pushed his old line, that consistency was the sole criterion for judging the adequacy of formal theories of mathematics, with the question of completeness not even raised. How, given Gödel’s Entdeckungen, could he not have questioned his former thinking?