Incompleteness Read online

  Notice, by the way, that the second incompleteness theorem doesn’t say that the consistency of a formal system of arithmetic is unprovable by any means whatsoever. It simply says that a formal system that contains arithmetic can’t prove the consistency of itself.7 The formal system of arithmetic is clearly consistent, one might want to argue, if we avail ourselves of semantic considerations. After all, the natural numbers constitute a model of the formal system of arithmetic, and if a system has a model then it’s consistent. Recall the lessons learned from the description of my New York apartment. So long as I describe it unambiguously and accurately (it has, for example, one bathroom), I don’t need to worry about self-contradictions (it has four bathrooms) lurking in the description.) In other words, when the formal system of arithmetic is endowed with the usual meanings, involving the natural numbers and their properties, the axioms and all that follow from them are true and, therefore, consistent. This sort of argument for consistency, however, goes outside the formal system, making an appeal to the existence of the natural numbers as a model. This is not the kind of reasoning to offer solace to a formalist, however much it might gladden the heart of a Platonist like Gödel. Finitary formal systems were, according to Hilbert, anschaulich, transparently pure. With everything reduced to either stipulation or the logical consequences of the stipulated mechanical procedures, there is no place for obscurity (possibly infected with paradox) to creep in. Finitary formal systems were, according to Hilbert’s program, the means for draining the paradoxical substance out of the notion of the infinite:

  Operating with the infinite can be made certain only by the finite. The role that remains for the infinite to play is purely that of an idea—if one means by an idea, in Kant’s terminology, a concept of reason which transcends all experience and which completes the concrete as a totality—that of an idea, moreover, which we may unhesitatingly trust within the framework erected by our theory.

  Hilbert’s program—to expunge all reference to intuitions—was most particularly directed toward our intuitions of infinity; not surprisingly, finite creatures that we are, it is these intuitions that have proved themselves, from the very beginning, to be the most problematic. The deep uneasiness that even Euclid felt toward his fifth postulate and which was replicated down through the ages, stems from our altogether appropriate lack of confidence on all matters infinite. Yet one can’t do any mathematics at all, not even basic arithmetic, without referring implicitly to the infinite. If we could tame infinitude by capturing it within our finitary formal systems then we would have effected the perfect compromise. The infinite would, in Hilbert’s words, “be made certain by the finite.”

  Gödel’s result, in effect, proclaims the robustness of the mathematical notion of infinity; it can’t be drained of its vitality and turned into a ghostly Kantian-type idea hovering somewhere over, but without entering into, mathematics. The mathematician’s intuitions of infinity—in particular, the infinite structure that is the natural numbers—can no more be reduced to finitary formal systems than they can be expunged from mathematics.

  Another way of seeing the robustness of our intuition of infinity is to consider that it follows from Gödel’s work that there are “nonstandard models” of arithmetic. Specifically, Gödel’s completeness theorem—that Ph.D. thesis that turned out to be not as humdrum as it had first seemed—tells us, among other things, that every consistent formal system has a model. There is a way of specifying a universe of discourse and interpreting the predicates and relations and constants so that all the theorems of the formal system are true descriptions. It follows from this, together with Gödel’s first incompleteness theorem, that there is at least one nonstandard model of arithmetic: a model that satisfies all the axioms of the formal system of arithmetic but in which some of the truths of standard arithmetic—G, for example—will be false. So this nonstandard model isn’t going to consist of the natural numbers as we know and love them.8

  The natural numbers transcend the formal system of arithmetic, in the sense that that formal system does not uniquely pick out the natural numbers as its model; as being, that is, what the formal system is about. The same thing happens to be true of any larger formal system containing arithmetic. There remains something—always—that eludes capture in a formal system. It was in this metalight that Gödel viewed his incompleteness theorems.

  Gödel’s second incompleteness theorem, the direct consequence of the first, as von Neumann was quick to realize, effectively demolished Hilbert’s program for mathematical transparency, since finitary formal systems could only be proved consistent by resorting to arguments that couldn’t be expressed within the formal systems themselves, no matter how they were modified and extended.

  The second incompleteness theorem put formalism in an impossible bind: the formalist incentive was to banish the opacity of the nature of the thing in itself (space, numbers, sets) for the transparency of formal systems. But it’s of the highest priority that a formal system—drained of the descriptive content that would, so long as the axioms were truly descriptive, ensure its consistency—be proved consistent. This can only be done by going outside the formal system and making an appeal to intuitions that can’t themselves be formalized. (The last article that Gödel was to publish in his life showed how arithmetic could be shown to be consistent provided one makes certain assumptions about objective mathematical reality.) The purely syntactic aspects of formal systems—the transparent aspects—aren’t sufficient unto themselves, neither in being able to prove all the true arithmetical propositions expressible within the system (the first incompleteness theorem) nor in providing a proof of internal consistency (the second incompleteness theorem).

  What was Hilbert’s reaction to the logical wrench thrown into his beautiful plan? The mathematician, Paul Bernays (1888–1977), who had come to Göttingen to serve as Hilbert’s assistant, reveals in a letter that he had, sometime before Gödel’s proof, himself become “doubtful . . . about the completeness of the formal systems” and had “uttered [his doubts] to Hilbert.” Hilbert, according to Bernays, became angry; and he was angry when Gödel’s proof became known to him.

  But a proof is a proof, as Hilbert, of all people, appreciated.

  Wittgenstein and Incompleteness

  Wittgenstein’s reaction to Gödel’s proof was notably different from Hilbert’s. He did not live to accommodate himself to Gödel’s work, as Hilbert did, no matter how unpalatable to his philosophical outlook, to his entire program, it was. There is a logical incompatibility between Wittgenstein’s views on the foundations of mathematics (both early, positivist-sounding and later postmodernist-sounding Wittgenstein) and Gödel’s incompleteness theorems. Wittgenstein acknowledged the incompatibility; he did not, like so many others, take the mathematical results and bend them into some metamathematical shape more to his liking, the shape of positivism or existentialism or postmodernism. He acknowledged the incompatibility and countered that Gödel therefore could not have proved what he thought he had proved:

  Mathematics cannot be incomplete; any more than a sense can be incomplete. Whatever I can understand, I must completely understand. This ties up with the fact that my language is in order just as it stands, and that logical analysis does not have to add anything to the sense present in my propositions in order to arrive at complete clarity.

  It is really not so surprising that Wittgenstein would dismiss Gödel’s result with a belittling description like “logische Kunststücke,” logical conjuring tricks, patently devoid of the large metamathematical import that Gödel and other mathematicians presumed his theorems had. Gödel’s proof, the very possibility of a proof of its kind, is forbidden on the grounds of Wittgensteinian tenets that remained constant through the transformation from “early” to “later” Wittgenstein, where early Wittgenstein had a monolithic view of language and its rules and later Wittgenstein fractured language into self-contained language-games, each functioning according to its own set of rules. He wa
s adamant on the impossibility of being able to speak about a formal language in the way that Gödel’s proof does. He was also adamant in denying that paradoxes, being trivial epiphenomena of the ways in which language works, could have large and interesting consequences. (He was to argue this very point with the logician Alan Turing, who ignored Wittgenstein and went on to produce another extraordinary proof which shares many attributes with Gödel’s; so many, in fact, that it yields an alternative proof for the incompleteness of formal systems rich enough to express arithmetic.) He was, more generally, adamant in denying that mathematical results, being the results of mere syntax, could have large and extra-mathematically interesting consequences: “No calculus can decide a philosophical problem. A calculus cannot give us information about the foundations of mathematics.” He was, in short, adamant in denying the possibility of a proof such as Gödel’s.

  All of which adamant irreconcilabilities provide context for understanding a statement of Wittgenstein’s that has tended to irritate mathematicians: “My task is not to talk about Gödel’s proof, for example. But to by-pass it.” Yet Wittgenstein does circle back, again and again, in his Remarks on the Foundations of Mathematics, to Gödel’s incompleteness theorem, deconstructing it, as the postmodernists would say, trying to show that its meaning is at odds with its intent, that it cannot mean what it purports to mean.

  Yet, if one pushes beyond the metamathematical irreconcilabilities separating Wittgenstein and Gödel, one comes upon a surprising commonality, at least between the early Wittgenstein and the logician, masked by the positivist interpretation of Wittgenstein. In a sense, the early Wittgenstein put forth an incompleteness thesis of his own in his final proposition of the Tractatus. Just as Gödel demonstrated that our formal systems cannot exhaust all that there is to mathematical reality, so the early Wittgenstein argued that our linguistic systems cannot exhaust all that there is to nonmathematical reality. All that can be said can be said clearly, according to the Tractatus; but we cannot say the most important things. We cannot speak the unspeakable truths, but they exist. Again, we see why Wittgenstein fulminated against the positivists, why he sometimes became so enraged with his would-be disciples that he turned his back to them and faced the wall, reciting the poetry of a mystic Indian (an act hostile to positivists, if ever there was one: curious that its latent hostility seems to have passed them by).

  For Gödel, for each formal system there will be truths expressible in that system that will not be provable; and one of the most important truths about the system, that it is consistent, will not be provable within the system. So both Gödel and the early Wittgenstein are united against the positivists’ reiteration of the ancient Sophist’s slogan that man is the measure of all things. Both men assert a fundamental incompleteness that takes the measure of man.

  Wittgenstein’s is, by far, the more radical statement of incompleteness. For Gödel’s there is expressible knowledge which cannot be formalized. The limits of formalization, of our attempt to reduce all mathematical knowledge to the specified rules of a system, are not congruent with the limits of our knowledge. Our mathematical knowledge exceeds our systems. For early Wittgenstein there is no expressible knowledge that escapes the limits he delineates. On the other side of meaningfulness lies all the most important subjects: ethics and aesthetics and the meaning of life itself. “There are, indeed, things that cannot be put into words. They make themselves manifest. They are what is mystical.”

  Wittgenstein’s unpositivistically positive attitude toward the idea of the mystical—even though it is the meaningless mystical—might have struck a responsive chord in Gödel. Gödel was even receptive to the suggestion that his incompleteness theorems had consequences in the mystical, or at least religious, sphere. In a letter to his mother on 20 October 1963 he remarked with regard to an article that she had sent him, and which he had not yet read, concerning the implications of his work: “It was something to be expected that sooner or later my proof will be made useful for religion, since that is doubtless also justified in a certain sense.” At the very least, Gödel believed his first incompleteness theorem supported Platonism’s insistence on the existence of a suprasensible domain of eternal verities. Platonism isn’t of course tantamount to religion or mysticism, but there are affinities.

  For early Wittgenstein, as for Gödel, the attempt to systematize reality, to capture it all within our limpid constructions designed to keep out all contradictions and paradox, are doomed to failure. Gödel’s first incompleteness theorem tells us that any consistent formal system adequate for the expression of arithmetic must leave out much of mathematical reality, and his second theorem tells us that no such formal system can even prove itself to be self-consistent. Of course, Gödel believes that these systems are consistent, since they have a model in the truly existent abstract realm. Wittgenstein so ardently embraces the futility of attaining both completeness and self-consistency that he allows the Tractatus itself to bare its self-contradiction in plain sight, speaking of that of which one cannot speak, even while pronouncing the very statement that forbids it.

  Gödel would most likely not have known that, on some level, he and (the early) Wittgenstein shared a profound conviction of incompleteness, a shared rejection of the logical positivists’ endorsement of the Sophist’s “measure of all things.” After all, as he reported on his Grandjean questionnaire, he never studied Wittgenstein for himself. His acquaintance with the philosopher was, by his own estimation, superficial, presumably because he was not sufficiently excited by what he heard to study the philosopher for himself; he knew only what he learned by way of the discussions of the Vienna Circle. And the logical positivists, studying the precisely obscure Tractatus proposition by proposition, were intent on systematically ignoring those aspects that would have been congenial to Gödel, speaking to his own conviction of a reality always escaping our ordered attempts at precision.

  Of course, Gödel and Wittgenstein located the escaped parts of reality in irreconcilably different ways. Gödel’s conviction, the metamathematical interpretation he gave his incompleteness theorems (as well as his work on the continuum hypothesis), was that it was aspects of mathematical reality that must escape our formal systematizing (although not our knowledge), and Wittgenstein’s view on the foundations of mathematics would not countenance this conviction. For Wittgenstein, at least early Wittgenstein, all of knowledge, a fortiori mathematical knowledge, is systematizable; what systematically escapes our systems is the unsayable, which includes all that is important. Gödel believed our expressible knowledge, demonstrably our mathematical knowledge, is greater than our systems. Whereof we cannot formalize, thereof we can still know, the mathematician might have said, had he had any inclination toward the oracular.

  Wittgenstein never allowed Gödel’s result to tamper with his views on metamathematics, which subject increasingly obsessed him in the years after the Tractatus was published and subsequently renounced by its author. His aim, as he said, was to bypass Gödel’s proof. This is both interesting in itself and interesting because of its galling effect on Gödel. The philosopher had spoken of necessary silence. Gödel, one suspects, would have liked that silence to envelope the philosopher himself.

  The Spreading Incompleteness

  The incompleteness proof opened up entirely new areas of research, most notably model theory and recursion theory. Gödel was never interested in pursuing the problems of those fields for himself. Much like his soulmate Einstein, he was interested in pursuing what Einstein called problems of “genuine importance,” that is problems that lay in the interstice between exact science and philosophy, problems that radiated meta-implications. He left the “mop-up work” (in Thomas Kuhn’s colorful terminology) to others. The vaulting intellectual ambition and confidence—so incongruously coupled with worldly fearfulness and self-effacement—may have meant that he left behind fewer results than he might have, but it also meant that the reach of his results was vast.

  G�
�del’s incompleteness theorems do not stun us simply because they open up promising new areas of technical research. Deep discoveries in the exact sciences quite often do exactly that. What makes Gödel’s results so stunning is the sheer volume of all that they have to say. The passionate Platonist, who had sat mum among the positivists, not murmuring a word of demurral, had produced the most loquacious theorems in the history of mathematics.

  It was because of their volubility that a philosopher like Wittgenstein could not accept them, that his self-assigned task was not to discuss them but to bypass them.

  (Wittgenstein was to carry on his extended argument against the very possibility of such a result as Gödel’s with the young English logician Alan Turing, who would go on to produce a proof that has great affinity with Gödel’s. Turing, too, would manage to give sharp mathematical expression to metamathematical concepts and to appropriate the structure of self-referential paradoxicality to his own ends. Alan Turing had spent the academic year 1936–37 at the Institute for Advanced Study, where Gödel’s incompleteness theorems were very much the topic of the day among von Neumann and his circle. (Von Neumann did more than anyone else to disseminate the news of Gödel’s accomplishments.9) Turing returned to Cambridge, with his mind dwelling on Gödel’s proof. His first semester back in England, he gave a course in Cambridge on the “Foundations of Mathematics.” That same semester Wittgenstein was also giving a course there entitled “Founda-tions of Mathematics,” but the two courses could not have been more dissimilar. While Turing’s course was, in effect, an introduction to mathematical logic, Wittgenstein devoted his course primarily to arguing against the possibility of mathematical logic in general, and against its implications for metamathematics in particular. Turing attended Wittgenstein’s lectures, at least for a while, and Wittgenstein was so intent on changing Turing’s mind that, while the logician attended, Wittgenstein’s lecture was focused entirely on that aim; when Turing once mentioned that he would not be able to attend the seminar the next week, Wittgenstein remarked that then the discussion that week would be “parenthetical.”10 Eventually Turing stopped attending, and soon after produced his own important metamathematical result.)