Incompleteness

by Rebecca Goldstein

  8 The study of model theory—interpretations both standard (with the natural numbers as the universe of discourse) and nonstandard—as distinct from proof theory—the study of the purely syntactic features of formal systems—was opened up as a result of Gödel’s incompleteness proof. Not only had Gödel’s proof put logic, in the words of Simon Kochen, “on the mathematical map,” but it also had pointed the way to new and distinct regions of technical research. Gödel himself never showed much interest in doing research in the areas his proof engendered, not so surprising in light of his audacious ambition to restrict himself only to mathematics with metamathematical implications.

  9 For example, the logician Stephen Kleene recounted how Gödel “entered my intellectual life. . . . One day in the fall of 1931 the speaker in the mathematics colloquium at Princeton was John von Neumann. Instead of talking on work of his own (of which there was plenty) he spoke on the results of Gödel’s 1931 paper, which had recently come out in the Monatshefte, but which Church and we in his course had not yet noticed. Von Neumann had had a preview of the first of those truths (accompanied by intellectual intercourse with Gödel) at the Königsberg meeting of September 1930. After the colloquium, Church’s course continued uninterruptedly concentrating on his formal system; but on the side we read Gödel’s paper, which to me opened up a whole new world of fascinating ideas and perspective. The impression this made on me was so much the greater because of the conciseness and incisiveness of Gödel’s treatment.”

  10 The crux of the raging debate carried on between Turing and Wittgenstein that semester was whether contradictions and paradoxes can have any significance. Wittgenstein maintained that they cannot. Take, for example, the case of the liar’s paradox. Wittgenstein’s view about it was: “It is very queer in a way that this should have puzzled anyone—much more extraordinary than you might think: that this would be the thing to worry human beings. Because the thing works like this: if a man says ‘I am lying’ we say that it follows that he is not lying, from which it follows that he is lying and so on. Well, so what? You can go on like that until you are black in the face. Why not? It doesn’t matter.” But Turing, being committed to mathematical logic and aware of the use to which Gödel had put traditional paradoxes such as the liar’s paradox, was very much under the impression that the liar’s paradox—that paradoxes and contradictions in general—do matter, and that they are sometimes pointing the way to almost necessarily surprising truths. When Wittgenstein remained adamant that a contradiction in a system was no cause for concern, since everything reduced ultimately to the arbirtrariness of language-games, Turing stopped attending the lectures. Soon after this, Turing produced his metamathematical proof. Where Gödel had subjected the concepts of “provability” and “completeness” to his transformative techniques, Turing would give mathematical expression to the concepts of “decidability” and “computability.” A mathematical question of a certain type (that includes an infinite number of specific questions) is decidable if and only if there exists an algorithm—one single computable series of operations—for determining, for any such question, whether the answer is yes or no, without necessarily explaining why the answer is yes or no. You don’t have to understand why an algorithm works for it to be an algorithm and for it to work. In particular, there is the sort of mathematical question that asks whether or not a proposition is formally provable. It’s not hard to see, though a little beyond the scope of this footnote, that Hilbert’s formalism—or more precisely the notion, shown to be false by Gödel, that for every mathematical proposition either it or its negation admits of a proof—implies that the question of whether a proposition is provable is in fact decidable. If one had an algorithm for showing whether a proposition or its negation was provable, then, given Hilbert’s formalism, one would have an algorithm for mathematical truth. Such an algorithm would provide a purely finitary combinatoric method for capturing the concept of mathematical truth (just as the concept of mathematical provability had been captured). Turing proved that no such algorithm exists, providing yet another frustration to Hibert’s formalist hope. His proof is so closely allied with Gödel’s that it is possible to derive an alternative proof of Gödel’s first incompleteness theorem from it. Gödel was so gladdened by Turing’s work that, in 1963, when his famous paper of 1931 was republished, he appended a paragraph stating that his own two incompleteness theorems had been strengthened by Turing’s work. “In consequence of later advances, in particular of the fact that due to A.M. Turing’s work (Turing [1937] ‘On computable numbers, with an application to the Entscheidungsproblem,’ Proceedings of the London Mathematical Society, 2nd series, 42, 230-65) a precise and unquestionably adequate definition of the general notion of formal system can now be given, a complete general version of Theorems VI and XI is now possible. That is, it can be proved rigorously that in every consistent formal system that contains a certain amount of finitary number theory there exist undecidable arithmetic propositions and that, moreover, the consistency of any such system cannot be proved in the system.” Unfortunately, Turing and Gödel never met. Turing died at the age of 42, a suicide.

  11 The dark mirroring is reflected in a remark of Furtwängler’s, who had been Gödel’s favorite mathematics professor at university, reported by Olga Taussky-Todd in her memoir of Gödel. “Auguste Bick has supplied me with an amusing remark by Furtwängler concerning Gödel’s result, when the latter had one of his paranoia attacks: ‘Is his illness a consequence of proving the nonprovability or is his illness necessary for such an occupation?’ ”

  IV

  Gödel’s Incompleteness

  Pink Flamingo

  There it was, inconceivably, K. Goedel, listed just like any other name in the bright orange Princeton community phonebook.

  It was a sweetly surreal moment. I had just arrived as a graduate student at Princeton and, just for the thrilling improbability of it, had looked up the name of the town’s most dazzling mind, the reigning, if reclusive, god at the fabled Institute for Advanced Study, a bucolic three-minute stroll from where I was living.

  It seemed almost axiomatic to me in those days that the greatest mathematical mind, which happened at that moment in history to be identical with Kurt Gödel’s mind, was necessarily identical with the greatest of all minds. K. Goedel. It was like opening up the local phonebook and finding B. Spinoza or I. Newton.

  The Princeton community phonebook had offered me the unbelievable largesse not only of a telephone number but also of a street address for Gödel. Of course, once I had this information there was nothing else for me to do but to hop on my bike and pedal my way over to see the house on 145 Linden Lane. It was a simple wooden affair, orthogonally situated in relation to the street, unlike all the other forward-facing houses, and this singularity seemed somehow just right. The place itself was compact and modest, vaguely “European” with its red-tiled roof. By comparison, the house at 112 Mercer Street where Einstein had lived had been a mansion (and it wasn’t).

  The neighborhood certainly wasn’t Princeton’s choicest. It was a hot September day and the street was treeless, depressingly exposed to the high noon sun. There wasn’t a soul stirring around the Gödel house, but the visit did manage to deliver yet another surreal wallop. The sliver of a front yard was completely dominated by one of those pink, plastic flamingoes that stands poised on one skinny leg.

  I stared in disbelief at the bird. How could a man who had produced one of the most exquisite masterpieces of human thought have planted a pink flamingo on his front lawn?

  Of course, there was a Mrs. Gödel, a former cabaret dancer, by popular report. Visions of Der Blaue Engel danced through my head, and I hastily attributed the lawn ornament to a Marlene Dietrich–type turned unlikely New Jersey Hausfrau.

  I was hardly the only Princeton denizen who was fascinated with the elusive celebrity of pure thought in our midst. I once found the philosopher Richard Rorty standing in a bit of a daze in Davidson’s food market. He to
ld me in hushed tones that he’d just seen Gödel in the frozen food aisle, pushing his food cart. I went tearing through the aisles, but the phantom of logic had vanished.

  “What was he buying?” I asked Rorty, for the rumor was that the man ate next to nothing. Rorty shook his head lugubriously and said he’d been too stunned to notice.

  “But I guess we can assume it was something frozen.”

  I remember more than one party in which we, graduate students and faculty members alike—philosophers, mathematicians, physicists—sat in a circle and traded stories of Gödel. Someone had noticed that every book related to Leibniz in Firestone Library had been checked out to a K. Goedel. The library slips quickly disappeared, the lucky ones who got there first carrying them off as trophies.

  At one party, a fellow graduate student alleged that someone had snuck up on Gödel as he sat reading in his office, to peer over his shoulder at the book, which was (uncorroborated) Ovid’s love poetry in the original Latin. This same graduate student (now a prominent philosopher who shall go unnamed) at one party in which things got a bit out of hand, actually called Gödel at home, when the question arose as to whether the international phone system could become sufficiently complex to become conscious. I think I remember that he slammed down the phone when he heard Mrs. Gödel call out “Kurtsy!”

  We all speculated about what our hero might be working on. There were strange rumors about a proof for God’s existence—which turned out to be veridical. Gödel, like Leibniz, believed that some version of the infamous “ontological proof for God’s existence” was valid. This is an argument that tries to deduce the existence of God from the right definition of God.1 He mentioned to at least one colleague at the Institute, the philosopher Morton White, that there remained just one step to be clinched before his new version of the ontological argument for God’s existence could be published.

  The tone of our fascination with Gödel wasn’t consistently reverential. There was even a decided undercurrent of flippancy. We found it hilarious, for example, that the greatest logician since Aristotle deluded himself into believing that God’s existence could be proved a priori, that he was perhaps contemplating the day when atheists would be brought round by a good stiff course in quantificational logic. The stories we swiped were gratifying in the way that stories of geniuses acting oddly are always gratifying; we cut our prodigies down to human size, domesticate their grandeur into cuddliness with tales of their quotidian weirdness. Sometimes we miss seeing what is truly human within these prodigious talents, yet one more irony that Gödel’s story suggests.

  Gödel’s story has forced me to confront a more personal irony, too, since it has required me to reacquaint myself with a field, mathematical logic, in which I had once been so much more deeply immersed and fluent. Years of a different kind of immersion, in the shadowy realm of fiction, interceded. It’s not that fiction forsakes hard logic, though fiction’s is not logic as we formally understand it; and it’s not that fiction’s logic isn’t as elusive, complex, and startling as mathematical logic. Still, the logic of fiction is something quite different from formal proofs, and I know that I was the better mathematician in my youth, when I sat with others and callowly swapped stories of Gödel’s genius and looniness. Yet I wonder whether I could have understood his story in quite the same way, back in the days when I was more blinded by lucidity.

  Gödel, recluse though he was, made a rather surprise appearance once at an Institute garden party held for new temporary members in 1973, and, as Oskar Morgenstern wrote in his journal, the logician was in especially droll form that evening, ending up “holding court in the midst of a group of young logicians.” I was there in that group, one of the acolytes agape at the god. There was a giant tent spread on the lawn behind Olden Farm, the domicile of the president of the Institute, who was then Karl Kaysen. It was a balmy October afternoon and Gödel, dapper in a dark suit, was also muffled in a long woolen scarf. I read somewhere that his height was 5’ 6”, but he seemed even smaller to me, and of course he was bird-thin. We all knew that the man barely ate. He was, as Morgenstern described it, in rare form (only I did not yet know how truly rare it was), clearly trying to make the youngsters feel welcome. We were mostly awed into stupidity (certainly I was). So we didn’t ply him with the questions that we all wished we had, as we commiserated with one another after he had, with a brief nod and good wishes for our future work, disappeared into the falling dusk. I remember particularly regretting that I had not gotten up the nerve to ask him what he thought of the paper that the Oxford philosopher John Lucas had published, claiming that conclusions in the philosophy of mind followed from the first incompleteness theorem.

  We all agreed that we wished we had asked him about what he was working on now. He was said to go almost every day to his office at the Institute, to sit quietly there and work. What conceptual revolutions had the gnomish logician laid in wait for us? Though the number of his publications didn’t amount to much—the sum total of pages equalling less than 100—in content each one had been far more than merely remarkable. But the last time he had published had been in 1958: a consistency proof for arithmetic in the journal Dialectica.2

  This particular issue of the journal was a Festschrift in honor of the seventieth birthday of the mathematician Paul Bernays, the former Hilbert assistant who had not found, since having been dismissed as a non-Aryan from Göttingen, any academic post commensurate with his ability. It was Paul Bernays who had first presented a fully worked-out proof of the second incompleteness theorem, having learned the details on board the SS Georgia from his shipmate, Gödel. And Bernays had improved on von Neumann’s axiomatization of set theory in a way of which Gödel highly approved and had used in his own work on set theory. So it was altogether fitting that Gödel should overcome his reluctance to publish in order to contribute something to the Festschrift.

  Gödel had written about a new sort of proof for the consistency of arithmetic, one which was not finitary, and so therefore was consistent with his second incompleteness theorem. (But since it wasn’t finitary it didn’t meet the requirements of Hilbert’s challenge.) He had lectured on this new sort of proof for consistency at Yale and at the Institute back in 1941. The 1958 paper was a beautifully concise statement of those ideas. Still the article hadn’t contained any new results.

  People reported that there were notebooks upon notebooks of ideas that he had never published.3 And why was he so reluctant to publish? There is much evidence that Gödel suspected that his ideas would be greeted skeptically and dismissively. Hao Wang wrote: “Gödel would probably have published more if he found himself living in a more sympathetic philosophical community. For instance, he declined to speak to what he expected to be a hostile audience.”

  More and more reclusive, once he lost the great friend of his life in Einstein, he was not inclined to air his views in a climate he judged to be perhaps as positivist as what he’d known back in the grungy room at the University of Vienna where the Schlick group had met on Thursday evenings at six. His sense of a world increasingly under the sway of the long-scattered Vienna Circle wasn’t entirely unfounded. As Feigl recounts in his essay “The Wiener Kreis in America,” positivists such as himself and men like Hans Reichenbach and Peter Hempel, who had come to America to flee the Nazis, had had much success in bruiting their ideas abroad. In England there was the highly influential A. J. Ayer, whose Language, Truth, and Logic had largely been constructed out of what he’d heard in Vienna. Harvard’s Willard Van Orman Quine, who had also visited with the Vienna Circle and imbibed their general outlook (though he was to disagree with them on specifics in such articles as “Two Dogmas of Empiricism” in his From A Logical Point of View) became the most dominant force in American philosophy. Wittgenstein’s name posthumously loomed ever more prominently, the awed inclination to accept him a priori (prior even to understanding what he might have meant) persisting in analytic circles, even in the absence of his persuasive presence. And in physi
cs departments the positivistic outlook of Niels Bohr and Werner Heisenberg had pretty much become the party line, where it still waxes strong. (It might be an interesting study to compare the figures of Niels Bohr and Ludwig Wittgenstein, both of them as charismatic as they were obscure, their obscurities pointing toward the same sort of conclusion: a prohibition against asking the sorts of questions that seek to make a connection between the abstract thought of their respective disciplines and objective reality.)

  So Gödel wasn’t being particularly paranoid in judging the climate of ideas as inimical to his own, though he perhaps both overestimated the degree of “positivism” in American universities and also underestimated his own reputation within the community and the commensurate respect that would have been accorded his views, the degree to which he might perhaps have even influenced the prevalent ideology had he braced himself to enter the fray. But that had never been his way. He certainly had never been afraid to privately dissent from the dominant views of his day; but there was a rigid reluctance to publicly voice his adversarial position in any terms other than conclusive proof.

  I mentioned to the philosopher Morton White that I had come, in writing this book, to regard Gödel as an intellectual exile, or, at least, as someone who had felt himself to be in exile. White thought for several moments and came up with this story. When he had been on the faculty at Harvard, he had been instrumental in having Gödel invited to deliver the prestigious William James series of lectures and had been chagrined when Gödel declined. This would have been in the 1960s. When White himself came to the Institute as a permanent member in 1970, he remembers having asked Gödel why he had turned down the invitation. Gödel’s answer had come in two parts.