Incompleteness Page 12

  In spirit Hilbert’s formalism was close to the antimystery attitudes of the Vienna Circle, and so the logical positivists very naturally embraced it, as Feigl tell us:

  With the formalists (e.g. Hilbert) we would consider mathematical proofs as procedures that start with a given set of sign combinations (premises, postulates) and according to rules of inference (transformation rules) lead to the derivation of a conclusion.

  Formalism confirms, at least in the sphere of mathematics, what the positivists had declared in their manifesto: viz. that man is the measure of all things. We create our formal systems and all of mathematics follows.

  For centuries, utopian epistemologists, like Descartes and Leibniz, had been inspired by the unique certainty and aprioricity of mathematics and had harbored dreams of extending those very features throughout the cognitive realm, obviating recourse to empirical evidence, which can give one, at best, mere probability. The special features of mathematical truth had led otherwise sober men, going back all the way to Plato, to near-mystical celebrations of its otherworldly reach. But now, with formalism, the nature of math’s aprioricity and certainty were claimed to derive from nothing more mystical than the stipulated mechanical rules of meaningless formal systems, replicable by the soon-to-be-invented electronic gadgetry. With the success of Hilbert’s program, the foundations of mathematics would at last be laid cleared, the murkiness that had encouraged rationalist giddiness dispelled.

  In 1899, David Hilbert published Grundlagen der Geo-metrie, or Foundations of Geometry, said to have been the most influential work in geometry since Euclid’s. Its importance reached far beyond geometry. He had shown that geometry could be captured in a formal system—conditional, that is, upon arithmetic’s being formalized, since geometry, like all branches of mathematics, presumes the truths of arithmetic. (In this sense, arithmetic is the most basic of all mathematical systems.)

  In 1900, a year after he had published his Grundlagen der Geometrie, Hilbert gave the keynote address at the Second International Congress of Mathematicians, held that year in Paris. The date, inaugurating a new century, was important. In the talk, called “Mathematical Problems,” Hilbert delegated himself the task of determining what the next century would bring by way of mathematical achievement. He laid out 23 problems that he considered the most important to solve.

  In his introduction, which has the distinct tone of a pre-game pep talk, Hilbert urges on his “team” of mathematicians with the assurance that no matter how difficult a particular problem may seem, victory is inevitable:

  This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.

  Hilbert describes this as a conviction “which every mathematician shares, but which no one has as yet supported by a proof.” Then he stated the 10 problems.

  It is of some interest that Gödel, even though a logician—merely a logician, according to the mathematical biases that persisted far into his own day (and dim echoes of which still sound today)—contributed enormously to the first two problems, as well as to the tenth, that Hilbert, the establishment figure in mathematics, determined as the most outstanding problems to be solved.

  The first of these is the problem revolving around Cantor’s continuum hypothesis. What is Cantor’s continuum hypothesis? The great nineteenth-century mathematician Georg Cantor had proved that (roughly speaking) there are more real numbers than there are natural numbers, even though there are an infinite number of both. Cantor showed, by means of an elegant argument called the “diagonal argument,” that in the infinite pairing of one natural number with one real number, every natural number will be paired with a real number, but some real number or other will forever be left out. The set of real numbers is thus of a higher ordinality (roughly speaking, there are more of them) than the set of natural numbers. Cantor hypothesized that there is no infinite set that intervenes between the set of natural numbers and the set of real numbers; that is, there is no set that has a higher ordinality than the natural numbers and a lower ordinality than the real numbers. This is Cantor’s continuum hypothesis and Hilbert’s first problem was to prove Cantor’s continuum hypothesis true. Gödel was to contribute to the solution to this problem, though not in a way that Hilbert welcomed. Gödel, together with Paul Cohen, proved that the continuum hypothesis can be proved neither true nor false within current set theory. In other words, the status of the continuum hypothesis is what Hilbert claimed there could not be: an ignorabimus—a claim that can neither be confirmed nor discredited, a claim about which we remain ignorant.

  But it is Hilbert’s second problem which is of particular concern to us. Here, too, Gödel’s solution of this problem could not have been less welcome to Hilbert.

  Hilbert’s Second Problem: The Consistency of Arithmetic (The Most Important Proof That Wasn’t to Be)

  Hilbert’s second problem was to prove the consistency of the axioms of arithmetic. For a system to be consistent means that it does not yield any logical contradictions.

  The urgency of the problem of consistency was a direct result of the veer toward formalism. When axioms were understood to be asserting true statements about actual objects, there was not as pressing a worry about inconsistency. When you said something was an axiom, you took it for granted that it was true in the most naïve sense of “true”: that is, that it described some state of affairs. This meant that neither the axiom, nor any theorem derived from the axiom, could possibly logically contradict any other axiom or theorem, because they were all true statements in the old-fashioned, prosaic sense of “true”: descriptive of actual things. True and precise descriptions about reality cannot be logically incompatible with one another.

  Think of it this way: If I am truthfully describing my apartment—that it is located in New York City, that it has (alas) only one bathroom—I don’t need to stop and worry whether some of these statements contradict each other, whether, for example, I will be able to derive that I live in suburban New Jersey and have four bathrooms. If all my statements are both unambiguous and truly descriptive, then they won’t contradict each other, since the objective truth of the matter underpins them all.

  But in a formal system, with axioms drained of meaning, and truth amounting to nothing beyond provability, it cannot be taken for granted that the axioms will not yield logically incompatible theorems. Our formal systems are constituted by stipulated rules. Who is to say that we—mere humans, after all—constructed these systems consistently, that the rules will not have contradictory implications? This is the downside of taking man as the mathematical measure of all things, with no independent reality to ensure the ultimate consistency of our axioms.

  Of course, if my axioms do lead to theorems that are logically incompatible, then my system is worthless, worse than the most speculative chain of barely probabilistic conjectures or of metaphysical artifices claiming to scope out the ends of Being and Ideal Grace. Anything at all can be deduced within an inconsistent system, since from a contradiction any proposition can be derived. You might say that on a strictly formalist interpretation, inconsistency loses its sting. What’s so awful if, through the manipulation of meaningless wffs, we arrive at contradictory meaningless wffs? The game is ruined, of course, since it just isn’t interesting to try to derive theorems if everything’s derivable; but it’s not as if inner contradictions are disastrously demonstrating that our systems can’t be true—the elimination of the extra-systematic truth being the whole point of formalism. You might also say that the exigency with which Hilbert urged that mathematics be proved consistent showed that he wasn’t really, deep down, a formalist after all. In any case, following the formalist agenda, if mathematics is to be successfully purged of intuitions in the service of certitude, then formal proofs of the consistency of the purged systems are a pressing necessity.

&nbs
p; The highest priority of all was to prove the consistency of arithmetic. Other systems of mathematics, for example geometry, had been shown to be consistent provided arithmetic, the most basic of all mathematical systems, is consistent. These sorts of proofs, which establish the consistency of one system as a consequence of the consistency of another system, are called relative proofs of consistency. All of these relative proofs of consistency were related to the consistency of arithmetic, which thus became the next step, the one that would provide the linchpin for the Hilbert program. The proof of arithmetic’s consistency could not be relative, as the other consistency proofs were; it had to be an “absolute proof.”

  The tone of Hilbert’s 1900 talk to the mathematical troops is extremely optimistic; he felt pretty sure that an absolute proof of the consistency of arithmetic was imminent. But in a series of talks which Hilbert gave through the 1920s, his buoyancy modulated into something more guarded. His change in mood was brought about by the paradoxes of set theory, including most conspicuously Russell’s paradox of 1902, which brought the set of all sets that are not members of themselves to the horrified attention of mathematicians, adding insult to the injury of Cantor’s paradox, involving the impossible universal set, the set of all sets.5 Hilbert regarded “the situation with respect to the paradoxes” with dismay:

  Admittedly, the present state of affairs where we run up against the paradoxes is intolerable. Just think, the definitions and deductive methods which everyone learns, teaches, and uses in mathematics, lead to absurdities! If mathematical thinking is defective, where are we to find truth and certitude?

  But he still continues to express his confidence that there is “a completely satisfactory way of escaping the paradoxes without committing treason” against the spirit of mathematics.

  “Treason” against the spirit of mathematics would consist of such acts as expelling the very notion of the infinite from mathematics in the way that mathematicians such as the Dutch Luitzen Brouwer were advocating. Brouwer was a leading exponent of the intuitionist school of mathematics, yet another metamathematical outlook.6 The intuitionists were the most fundamentally opposed to Platonism of all the non-Platonist schools. Even formalism can be interpreted in such a way so that it doesn’t preclude a basically Platonic approach to mathematics, just so long as Platonically sanctioned intuitions do not in any way enter into mathematical practice. Hilbert himself often sounds like a Platonist, albeit one who is very strict with himself.

  Hilbert certainly wanted to avoid the extreme limitations that the intuitionists would place on mathematical practice in order to avoid the possibility of paradoxes. The approach that Hilbert had in mind, when he spoke of “completely clarifying the nature of the infinite,” lay within the reach of finitary formal systems.7 In other words, the way out of the morass visited upon mathematics by the paradoxes of set theory lay, according to Hilbert, in the purification process of formalization—that is, in solving the problems of what Hilbert dubbed “proof theory.”

  Chief among these was the problem that Hilbert placed second in his list in the 1900 talk, that of finding a finitary proof of the consistency of the axioms, first of arithmetic, then of progressively stronger axiomatic systems. It would all begin, then, with the “single but absolutely necessary” step of proving the formal system of arithmetic consistent. The work first of Gottlob Frege, and then, after the discovery of Russell’s paradox, of Russell and Whitehead in Principia Mathematica, had prepared the ground for this ultimate sanctifying proof. The formal system laid out in Principia Mathematica was sufficient for expressing all the truths of arithmetic; it was also, presumably, consistent. The ad hoc rules of the Theory of Types barred the formation of inconsistency-breeding sets like the set of all sets not members of themselves. Still a formal proof of consistency was a necessity. Then, if it could be shown that such a formal system was both complete, allowing us to prove all arithmetical truths, as well as consistent, the linchpin of the Hilbert program would have been secured, the crisis posed by the paradoxes overcome.

  Enter Gödel.

  1 These rules of inference are perfect laws of truth-inheritance. The truth that belongs to the ancestors (the axioms) cannot help but be bequeathed to the descendents (the theorems). So, if you know that all x’s are P’s, and you know that some individual, i, is an x, then, by the rule of inference known as “universal instantiation,” you know that i is a P. For example, say you know for certain that all mathematicians do their greatest work before the age of 40, and you also know that Gödel was a mathematician, then you also know that Gödel did his greatest work before the age of 40.

  2 The fifth of Euclid’s five postulates was the notorious parallels postulate, which states that through any point outside a line, only a single line can be drawn parallel to the original line. Euclid himself wasn’t all that happy with this last postulate, sensing how different it was from the others, with its covert reference to infinity, and he had avoided using it in his derivations whenever he could. Why does the parallels postulate invoke infinity? Two lines are parallel if and only if they’ll never intersect. But if you take a finite region of space then you can draw more than one line through a point that will be parallel (i.e., won’t intersect) the line. So the parallels postulate makes implicit reference to infinity, and we are always rightly suspicious of our intuitions about infinity. Euclid’s suspicion about this one element of his system (his masterpiece was entitled The Elements) was duplicated down through the ages, with various mathematicians attempting to convert the problematic axiom into a theorem by deriving it from the other four axioms. Then, in the nineteenth century, mathematicians changed their tactics, attempting to show that the fifth postulate followed from the other four indirectly: by taking the four and the negation of the fifth and seeing whether a contradiction could be derived. Instead of a contradiction, an entirely new and self-consistent geometry was derived! Three mathematicians independently derived non-Euclidean geometry: the incomparable Carl Friedrich Gauss (1777–1855), known as “the prince of mathematicians”; Nicolai Ivanovich Lobachevsky (1792–1856); and the young János Bolyai (1802–1860), who on stumbling on this new mathematical world in 1823 wrote to his father, Farkas Bolyai, himself a mathematician and a friend of Gauss, “I have discovered things so wonderful that I was astounded. . . . Out of nothing I have created a strange new world.” When Gauss was shown the results, he wrote, “I regard this young geometer Bolyai as a genius of the first order,” but he had to inform the young genius that he was not the first to derive such a strange new world. He himself had done so, but had suppressed the results because he felt them to be too controversial.

  3 The very fruitful mathematical concept of a recursive function was first defined by Gödel in his proof of the first incompleteness theorem.

  4 The word comes from the name of the ninth-century Persian mathematician Abu Ja’far Mohammad ibn Mûsâ al-Khowâsizm, who wrote an important mathematical book in about AD 825 that was called Kitab al jabr w’al-muqabala. We also derive our word “algebra” from the title of his book.

  5 See note 11 in chapter I.

  6 The intuitionists were the most severe of all when it came to the question of acceptable methods of proof. Mathematical proofs were to be limited, according to the intuitionist, to “constructive proofs,” i.e., those that employed concrete operations on finite or “potentially” (but not actually) infinite structures. Reference to completed infinite structures were forbidden, as were indirect proofs making reference to the law of the excluded middle. Using the severe strictures of intuitionist mathematics a great deal of accepted mathematics, for example parts of classical analysis and even classical logic, would be deemed no longer acceptable. Brouwer himself renounced much of the former work he had done before becoming an intuitionist convert. “Intuitionism,” by the way, might seem like a misleading name, considering the way we have been speaking of intuitions up until now, as just the sort of appeals to objective mathematical truth that formalists and i
ntuitionists meant to eliminate. The intuitionists claimed that their finitary constructions were actually mental constructions, and in fact, the only sort of mathematical mental constructions that we, being finite, could actually perform. So they were claiming that their strictures on mathematical proofs actually corresponded to human psychology.

  7 In speaking of formal systems so far in this book, we’ve been speaking of finitary formal systems only; i.e., formal systems with a finite or denumerable (or countable) alphabet of symbols, wffs of finite length, and rules of inference involving only finitely many premises. (Logicians also work with formal systems with uncountable alphabets, with infinitely long wffs, and with proofs having infinitely many premises.)

  III

  The Proof of Incompleteness

  Gödel in Königsberg

  What the logician Jaakko Hintikka had called Gödel’s Sternstunde, his shining hour, occurred 7 October 1930. The scene was the third and last day of a conference in Königsberg on “Epistemology of the Exact Sciences,” which had been organized by the Gesellschaft für empirische Philosophie, the Organization for Empirical Philosophy, an association that overlapped both with the Vienna Circle and the Society for Scientific Philosophy, a Berlin discussion group, whose leading light was Hans Reichenbach, a philosopher of physics. The aims and activities of the Berlin group were similar to those of the Vienna Circle and close ties existed between the two groups from the beginning. Some of the most influential mathematicians, logicians, and mathematical philosophers had been invited to deliver papers at the conference. Gödel, who had only just completed his Ph.D. dissertation, was not one of the big fish. He was scheduled, together with other small fry, to give a 20-minute talk on the second day of the conference.

  On the first day there were four speakers, each talking on behalf of a distinctive metamathematical position. The metaconcern addressed was, as is almost always the case when discussing metamathematics, the tantalizing aprioricity and certainty of mathematics. How have we been allowed membership in the most selective cognitive country club going?