Incompleteness

by Rebecca Goldstein

  And it was because of their volubility that Hilbert’s program was abandoned. Hilbert had tried to inoculate mathematics against paradox by eliminating all appeals to intuition. Gödel had proved that appeals to intuition could not be eliminated; he had undermined formalism’s inoculation program. In particular, our intuitions about infinity—as susceptible as they are to invalidating fallacies, as the infamous paradoxes make all too clear (and which we can only avoid by adopting such ad hoc rules as Russell and Whitehead had devised)—nonetheless cannot be replaced by the semantics-free mechanical processes of mindless symbol-manipulation.

  Such metamathematical conclusions, emerging from an a priori mathematical proof, are extraordinary enough in themselves. If these metamathematical results constituted all that followed from Gödel’s incompleteness theorems it would still be sufficient to mark his work as singularly gabby. But Gödel’s incompleteness theorems have been heard as addressing, in their irrepressible effusiveness, issues that range far beyond even metamathematics. Eminent thinkers have interpreted the incompleteness theorems as having something to say on the central question of the humanities, viz. what is it that makes us human? For mathematical theorems to have anything at all to say on such a subject as this—embedded deep in the messy matter of the human predicament—is to take what is already extraordinary and raise it to an altogether higher order of astoundingness.

  The formalists had tried to certify mathematical certitude by eliminating intuitions. Gödel had shown that mathematics cannot proceed without them. Restricting ourselves to formal syntactic considerations will not even secure consistency. But these mathematical intuitions that cannot be eliminated and cannot be formalized: what are they? How do they come to be available to the likes of us? We are once again thrown up against the mysterious nature of mathematical knowledge, against the mysterious nature of ourselves as knowers of mathematics. How do we come to have the knowledge that we do? How can we? Plato himself had argued that the very fact that our reasoning mind can come into contact with the eternal realm of abstraction suggests that there is something of the eternal in us: that the part of ourselves that can know mathematics is the part that will survive our bodily death. Spinoza was to argue along similar lines.

  Few scientifically minded, post-Gödel thinkers would perhaps be ready to follow Plato and Spinoza into drawing conclusions of our immortality from our capacity for mathematical knowledge. After all, we are not only living with the truth of Gödel but also the truth of Darwin. Our minds are the products of the blind mechanism of evolution. Still, many scientifically minded, post-Gödel thinkers have testified to hearing, within the strange music of Gödel’s mathematical theorems, tidings about our essential human nature. They have argued from Gödel’s incompleteness theorems to conclusions about what we are; or rather, to be more precise, about what we are not. Gödel’s theorems tell us, according to this line of reasoning, what our minds simply could not be.

  In particular, what our minds could not be, so goes the reasoning, are computers. The mathematical knowledge that we possess cannot be captured in a formal system. That is what Gödel’s first incompleteness theorem seems to tell us. But formal systems are precisely what captures the computing of computers, which is why they are able to figure things out without having any recourse to meanings. Computers run according to algorithms and we, it seems, do not, from which it straightforwardly follows that our minds are not computers.

  The first of the arguments claiming a connection between Gödel’s first incompleteness theorem and the nature of the mind was published in 1961 by the Oxford philosopher John Lucas:

  Gödel’s theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines. So also has it seemed to many other people: almost every mathematical logician I have put the matter to has confessed to similar thoughts, but has felt reluctant to commit himself definitely until he could see the whole argument set out, with all objections fully stated and properly met. This I attempt to do.

  Lucas’s argument was stalwartly straightforward. No matter how complicated a “thinking” machine we engineer, he argued, this machine will run according to hard-wired rules that can be stated in a formal system, and when we ask this machine to tell us what the true propositions are it will be able to do this only by seeing which propositions follow according to the rules of the system. There will therefore be a proposition that eludes its grasp of truth, which is nothing but rule-determined provability—a proposition that our minds will nonetheless be able to grasp as true. No matter how we strengthen the machine, by adding in the previously elusive propositions as axioms, there will be yet another proposition that will elude it . . . but not us:

  This formula the machine will be unable to produce as being true, although a mind can see that it is true. And so the machine will still not be an adequate model of the mind. We are trying to produce a model of the mind which is mechanical—which is essentially “dead” —but the mind, being in fact “alive,” can always go one better than any formal, ossified, dead system can. Thanks to Gödel’s theorem, the mind always has the last word.

  The mathematician Roger Penrose, also an Oxford don, has published two books, The Emperor’s New Mind and Shadows of the Mind, arguing the case that Gödel’s incompleteness theorems entail the falsity of mechanism, the dead-endedness of the field of artificial intelligence, if artificial intelligence presumes to fully explain our thinking. His argument is much the same as Lucas’s, though he does an even more thorough job of trying to anticipate and answer all possible objections.

  What did Gödel’s theorem achieve? It was in 1930 that the brilliant young mathematician Kurt Gödel startled a group of the world’s leading mathematicians and logicians, at a meeting in Königsberg, with what was to become the famous theorem. It rapidly became accepted as being a fundamental contribution to the foundations of mathematics—probably the most fundamental ever to be found—but I shall be arguing that in establishing his theorem, he also initiated a major step forward in philosophy of mind.

  Among the things that Gödel indisputably established was that no formal system of sound mathematical rules of proof can ever suffice, even in principle, to establish all the true propositions of ordinary arithmetic. This is certainly remarkable enough. But a powerful case can also be made that his results showed something more than this, and established that human understanding and insight cannot be reduced to any set of rules. It will be part of my purpose here to try to convince the reader that Gödel’s theorem indeed shows this, and provides the foundation of my argument that there must be more to human thinking than can ever be achieved by a computer, in the sense that we understand the term “computer” today.

  Penrose believes that even though the mind is not a computer, it is nevertheless a physical system. The mind is identical with the brain. Therefore, the nonmechanistic nature of the mind following, he claims, from Gödel’s first incompleteness theorem, should direct our thinking toward nonmechanistic physical laws of just such a sort as are suggested by quantum mechanics. The mathematically intuiting mind, which demonstrably can’t be captured mechanistically, is nonetheless a physical system; we should, therefore, look toward developing a nonmechanistic, radically new sort of science—the mysteries of quantum mechanics should be our guide here—so that the noncomputational aspects of mind can be accommodated. The noncombinatorial but nevertheless physical nature of thinking shows us the noncombinatorial nature of basic physical laws.

  Gödel himself was far more reserved about drawing conclusions concerning the nature of the human mind from his famous mathematical theorems. What is rigorously proved, he suggested in his conversations with Hao Wang as well as in the Gibbs lecture that he gave in Providence, Rhode Island, 26 February 1951 (which he never published), is not a categorical proposition as regards the mind. Rather what follows is a disjunction, an “either-or” sort of a proposition. That is, he was admitting that nonmechanism doesn’t follow, clean and simply
, from his incompleteness theorem. There are possible outs for the mechanist.

  According to Wang, Gödel believed that what had been rigorously proved, presumably on the basis of the incompleteness theorem, is: “Either the human mind surpasses all machines (to be more precise it can decide more number theoretical questions than any machine) or else there exist number theoretical questions undecidable for the human mind.”

  What exactly did Gödel have in mind with this second disjunct? I think that what he is considering here is the possibility that we are indeed machines—that is, that all of our thinking is mechanical, determined by hard-wired rules—but that we are under the delusion that we have access to unformalizable mathematical truth. We could possibly be machines who suffer from delusions of mathematical grandeur. What follows from his theorem, he seems to be suggesting, is that just so long as we are not delusional as regards our grasp of mathematical truths, just so long as we do have the intuitions that we think we have, then we are not machines. If indeed we truly have the intuitions that we do, then it is impossible for us to formalize (or mechanize) all of our mathematical intuitions, which means that we truly are not machines. Of course there is no proof that we know all that we think we know, since all that we think we know can’t be formalized; that, after all, is incompleteness. This is why we can’t rigorously prove that we’re not machines. The incompleteness theorem, by showing the limits of formalization, both suggests that our minds transcend machines and makes it impossible to prove that our minds transcend machines. Again, an almost-paradox.

  So Gödel was cautious about the consequences for human nature of his incompleteness theorem. Though he did have intuitions concerning the nature of the mind, he did not, scrupulous logician that he was, deduce any such conclusions from his incompleteness theorems alone. For Gödel, the distinction between intuitions and rigorous proof was always vividly clear. After all, it was the unavoidability of that very distinction that had been so strongly suggested by his famous proof.

  The second disjunct in Gödel’s disjunctive conclusion concerning our mathematically knowing minds, then, consists in this possibility: we are delusional in our claims to a mathematical knowledge that exceeds all formalization. This possibility—its being precisely the possibility that gave Gödel pause—is particularly interesting when we consider an aspect of Gödel’s opaque inner life that we have touched upon before: his own serious delusions.

  Gödel’s theorems are darkly mirrored in the predicament of psychopathology: Just as no proof of the consistency of a formal system can be accomplished within the system itself, so, too, no validation of our rationality—of our very sanity—can be accomplished using our rationality itself. How can a person, operating within a system of beliefs, including beliefs about beliefs, get outside that system to determine whether it is rational? If your entire system becomes infected with madness, including the very rules by which you reason, then how can you ever reason your way out of your madness?11

  As one textbook on psychopathology puts it: “Delusions may be systematized into highly developed and rationalized schemes which have a high degree of internal consistency once the basic premise is granted. . . . The delusion frequently may appear logical, although exceedingly intricate and complex.”

  Paranoia isn’t the abandonment of rationality. Rather, it is rationality run amuck, the inventive search for explanations turned relentless. A psychologist friend of mine put it this way: “A paranoid person is irrationally rational. . . . Paranoid thinking is characterized not by illogic, but by a misguided logic, by logic run wild.”

  It’s ironic to conclude this very chapter, conveying some small sense of the superhuman beauty of Gödel’s incomparable proof, with remarks on the tragic parallel between the limitations of proof ingeniously demonstrated by Aristotle’s successor and the predicament of psychopathology.

  1 Notice that parentheses are used for punctuation in limpid logic. ∼(p & q), or “it is not the case that both p and q,” is an altogether different proposition from ∼p & q, or “not p is true and also q.” So “it’s not the case that the president is both good-natured and stupid” is not the same assertion as “the president isn’t good-natured and he’s stupid.”

  2 Gödel was many years later to write Wang that his completeness proof for the predicate calculus, i.e., his dissertation problem, had also been guided by his Platonist convictions: “The completeness theorem, mathematically, is indeed an almost trivial consequence of Skolem 1922 [“Some Remarks on Axiomatized Set Theory”]. However, the fact is that, at that time, nobody (including Skolem himself) drew this conclusion. . . . This blindness is indeed surprising. But I think the explanation is not hard to find. It lies in a widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning. Non-finitary reasoning in mathematics was widely considered to be meaningful only to the extent to which it can be ‘interpreted’ or ‘justified’ in terms of finitary metamathematics. (Note that this, for the most part, has turned out to be impossible in consequence of my results and subsequent work.) According to this idea metamathematics is the meaningful part of mathematics, through which the mathematical symbols (meaningless in themselves) acquire some substitute of meaning, namely rules of use. Of course, the essence of this viewpoint is a rejection of all kinds of abstract or infinite objects, of which the prima facie meanings of mathematical symbols are instances.”

  3 “Goldbach and Fermat” refer, respectively to “Goldbach’s conjecture” and “Fermat’s last theorem.” Goldbach, as was mentioned in footnote 8 in chapter I, had conjectured that all even numbers greater than 2 are the sum of two primes. The French mathematician Pierre de Fermat (1601–1665) had written in a margin of a book, found after his death, that he had “discovered a truly marvelous demonstration of the proposition” that there are no integers x, y, z, n, with n > 2, such that xn + yn = zn, “which this margin is too narrow to contain.” At the time of Gödel’s announcement, neither Goldbach’s conjecture nor Fermat’s last theorem had been proved either true or false, though generations of mathematicians had ardently tried. In 1991, Andrew Wiles of Princeton University succeeded in demonstrating, in a complicated proof that required the results of many other mathematicians and took more than 150 pages, Fermat’s last theorem. Goldbach’s conjecture has still neither been proved nor disproved. (Disproof would be easy enough: finding an even number that isn’t the sum of two primes.) The possibility that Gödel was asserting in his Sternstunde was that such propositions as these two may, in fact, be true but unprovable within formalized number theory. What his famous proof does, of course, is to produce such a proposition, one that can be seen to be true even as it is proved to be unprovable.

  4 There are, first of all, the statements within the formal system S under consideration (call them S-sentences); when you interpret these S-sentences under the natural interpretation (i.e., as being about the natural numbers) they turn into arithmetical statements (call them A-sentences). The S-sentences each get numbered with the so-called Gödel numberings. Then there are the metamathematical statements about the S-sentences and about the formal system (call them M-sentences). M-sentences, which describe the purely formal relationships between the elements of the formal system, are combinatoric statements, so in a sense you might almost think of them as already mathematical statements. But it takes the ingenious encoding system of Gödel numbering to transform the M-sentences into A-sentences, so that in talking about the formal system of arithmetic (M-sentences) you are also making arithmetical statements (A-sentences).

  5 In Gödel’s famous paper of 1931, in which the proof is first set forth, he mentions the liar’s paradox and Richard’s paradox, offering them to us as heuristic grips for hoisting ourselves up into the strange country of his proof. We are already acquainted with the liar’s paradox. Richard’s paradox was the creation of French mathematician Jules Richard. It’s rather a complicated one to state, requiring, much like Gödel’s
proof itself, a certain sort of mapping. One orders the properties of the natural numbers and assigns a number to each of the properties. The number assigned to a property may or may not actually have that property. So, say, 22 corresponds to the property “being an even number.” Then 22 itself has the property to which it corresponds in the Richardian ordering. Now define this property: “not having the property assigned to itself in the Richardian ordering.” Call this property “being Richardian.” The paradox-generating question is: is the number that corresponds to being Richardian itself Richardian?

  All other formulations of his proof—for example, those by Alan Turing and G.J. Chaitin—have incorporated features of paradoxes, though different paradoxes from Gödel’s—into their own versions of the proof. These paradoxes, though different from one another, are all of the self-referential variety. The affinity between the incompleteness result and self-referential paradox is therefore very deep, since every proof of incompleteness has some version of self-referential paradoxicality lurking around in the background.

  6 Compare this to Richard’s paradox (footnote 5 above), which Gödel cites, together with the liar’s paradox, as a heuristic aid to understanding his proof. Richard’s paradox also has the (illusive) feel of attributing a contrived, or unreal, property to numbers (the property of being Richardian) which a number will or won’t have because of the arbitrary assignments of numbers to properties.

  7 In 1936 Gerhard Gentzen, a member of the Hilbert school, proved the consistency of arithmetic, but it wasn’t within a finitary formal system. His proof involved the sort of transfinite reasoning that Hilbert had proposed be banished in favor of finitary formal systems.