Provenly Unprovable

Solomon Feferman

  • Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein
    Norton, 224 pp, US $13.95, February 2006, ISBN 0 393 32760 4

Like Heisenberg’s uncertainty principle, Gödel’s incompleteness theorem has captured the public imagination, supposedly demonstrating that there are absolute limits to what can be known. More specifically, it is thought to tell us that there are mathematical truths which can never be proved. These are among the misconceptions that proliferate around Gödel’s theorem and its consequences. Incompleteness has been held to show, for example, that there cannot be a Theory of Everything, the so-called holy grail of modern physics. Some philosophers and mathematicians say it proves that minds can’t be modelled by machines, while others argue that they can be modelled but that Gödel’s theorem shows we can’t know this. Postmodernists have claimed to find support in it for the view that objective truth is chimerical. And in the Bibliography of Christianity and Mathematics (there really is such a publication) it is asserted that ‘theologians can be comforted in their failure to systematise revealed truth because mathematicians cannot grasp all mathematical truths in their systems either.’ The incompleteness theorem is also held to imply the existence of God, since only He can decide all truths.

Even Rebecca Goldstein’s book, whose laudable aim is to provide non-technical expositions of the incompleteness theorems (there are two) for a general audience and place them in their historical and biographical context, makes extravagant claims and distorts their significance. As Goldstein sees it, Gödel’s are ‘the most prolix theorems in the history of mathematics’ and address themselves ‘to the central question of the humanities: what is involved in our being human?’ – since they are concerned with ‘such vast and messy issues as the nature of truth and knowledge and certainty’. Unfortunately, these weighty claims disintegrate under closer examination, while the book is marred by a number of conceptual and historical errors.

On the face of it, Goldstein would appear an ideal choice to present Gödel’s work: she has taught philosophy of science and philosophy of mind at several universities and has also written successful novels and short stories, including The Mind-Body Problem and Properties of Light: A Novel of Love, Betrayal and Quantum Physics.

What she does very well is to provide a vivid biographical picture of Gödel, beginning midstream with his touching relationship with Einstein at the Institute for Advanced Study in Princeton, where, over the 15 years before Einstein’s death in 1955, they were often seen together. They were an odd-looking couple: ‘One of the men, dapperly dressed in a white linen suit with a matching white fedora, is still in his thirties, while the other, in baggy pants held up by old-world-style suspenders, is approaching 70.’ (Thus Gödel and Einstein in a widely reproduced summer photo. More often, even when it was warm, Gödel was bundled up in a heavy black overcoat.) In personality too they were opposites: Gödel was slight to the point of frailty, hypochondriac and buttoned up; Einstein was hearty and gregarious. But they had similar cultural backgrounds and each pursued central problems in his field. Both were German-speaking émigrés (‘exiles’, as Goldstein has it): Einstein was brought from Germany to the institute in 1933 by its founder, Abraham Flexner, as one of the first two permanent members (the other was the American mathematician Oswald Veblen, brother of Thorstein); Gödel fled Austria at the last minute in 1940 to avoid conscription and came to the institute as an ‘ordinary’ member, only later becoming a permanent one.

Gödel and Einstein had both already done their most important work, achieved in each case over a single, remarkable decade. In Einstein’s annus mirabilis of 1905 he published three seminal papers, including one on the special theory of relativity; the general theory of relativity was put forward in 1915. After that, he was increasingly sidelined in theoretical physics, which came to be dominated by the probabilistic theories of quantum mechanics. Until the end of his life, Einstein sought instead a deterministic unified theory of gravitation and electromagnetism, believing that ‘God does not play dice.’ For his part, Gödel’s three fundamental results were the completeness theorem for the first-order logic of predicates (in his PhD thesis of 1929); the incompleteness theorems a year later; and his proof of the consistency of two problematic hypotheses with the axioms of set theory in 1939. In the early 1940s, he worked on attempts to prove the independence of the first of these, the so-called Axiom of Choice, with only limited success; after that he devoted himself almost entirely to the philosophy of mathematics. Goldstein goes on to describe Gödel’s gradual descent via a surfeit of rationality into paranoia. Terrified of being poisoned, he died in January 1978 – according to the death certificate, of ‘malnutrition and inanition caused by personality disturbance’.

As to the core of Goldstein’s book, anyone familiar with Gödel’s work has to flinch. Dozens of errors could have been avoided by an expert vetting of the manuscript. At the very least we would not have had ‘Kreisl’ for ‘Kreisel’, ‘Kline’ for ‘Kleene’ and ‘Tannenbaum’ for ‘Teitelbaum’ (the birth surname of Alfred Tarski, the great logician, whose significant interaction with Gödel barely merits Goldstein’s notice). We would not have had a seriously incorrect (even impossible) formulation of Gödel’s crucial lemma providing for the construction of mathematical statements that indirectly refer to themselves. We would not have had it said that the second incompleteness theorem is an immediate consequence of the first (the proof of the second requires much more delicate work). We would not have had Gödel paired with Paul Cohen – who proved the independence of the Axiom of Choice twenty years after Gödel’s failed efforts – as if they were colleagues, or teacher and student (at the time, Cohen was on the faculty at Stanford, on the other side of the continent from Princeton). We would not have had a misleading account of the origin and significance of non-standard models. And so on. Instead of enlarging on such errors, I will concentrate on those aspects of Incompleteness where one might have expected Goldstein’s background in philosophy to be put to better use. Even in this respect, she gets things seriously wrong.

Gödel entered the University of Vienna in 1924. At first, he was interested in physics, but switched to mathematics after attending Philip Furtwängler’s dazzling lectures in number theory. Within a few years, Gödel began more specialised studies in mathematical logic. At the invitation of his supervisor, Hans Hahn, he became a regular at meetings of the Vienna Circle, a select philosophical discussion group. The leading members of the circle called themselves logical positivists: they shunned metaphysics in favour of the logical analysis of scientific knowledge; statements of observation were the only ones granted a ‘primary’ meaning. In this they were greatly influenced by Ernst Mach’s empiricist (or positivist) philosophy of science and Wittgenstein’s ‘picture theory of meaning’, as developed in the Tractatus. Since mathematics is essential to the formulation of physical laws, the logical positivists also leaned heavily on Bertrand Russell’s programme to reduce all mathematical concepts and truths to those of pure logic (a programme that was later recognised to have failed).

Goldstein bases her story of the development of the incompleteness theorems on the supposed fact that – in contrast to the Vienna Circle – Gödel was already a confirmed Platonist. The philosophy of Platonic realism in mathematics holds that abstract objects such as numbers, points, sets and functions have an objective, immutable existence independent of the observer, and that the task of the mathematician is to establish truths about this reality. It is Goldstein’s conceit that Gödel fell in love with Platonism in 1925 during an introductory course on the history of philosophy. According to her, this put him completely at odds with the logical positivists. ‘Gödel’s audacious ambition to arrive at a mathematical conclusion that would simultaneously be a metamathematical result supporting mathematical realism,’ she writes, ‘was precisely what yielded his incompleteness theorems.’ Goldstein claims that by 1928 this ambition had driven him to begin work on the proof of the first incompleteness theorem, ‘which he interpreted as disproving a central tenet of the Vienna Circle . . . He had used mathematical logic, beloved of the logical positivists, to wreak havoc on the positivist antimetaphysical position.’ She believes that Gödel’s theorems were designed to refute the formalist programme of David Hilbert, according to which mathematics is just an arbitrary human creation, ‘a game played according to certain simple rules with meaningless marks on paper’.

Wrong, wrong, wrong! But we can see how Goldstein was misled. There is no doubt that the mature Gödel was a mathematical Platonist, as is attested by some of his published and unpublished papers from the 1940s onwards, and by his many communications with colleagues. True, Gödel himself said here and there that he had held these views since his student days. There is considerable evidence, however, that he was by no means fixed in his philosophical views before 1940. In a lecture to the Mathematical Association of America in 1933, for example, he made a strongly anti-Platonist statement about the axioms of set theory (proposed by some as a foundation for all of mathematics): namely, that ‘if interpreted as meaningful statements’, these axioms ‘necessarily presuppose a kind of Platonism, which cannot satisfy any critical mind and which does not even produce the conviction that they are consistent’.

Goldstein uses the word ‘metamathematics’ mistakenly throughout, taking it to refer to the philosophy of mathematics, by loose analogy with ‘metaphysics’. (Indeed, she frequently uses ‘meta’ as a neologising modifier: there is talk of ‘metaquestions’, ‘metaconviction’, ‘metalight’, ‘metaovertones’ etc.) This is not at all the sense in which the term has been used by logicians since the 1920s, when it was introduced by Hilbert. In this usage, metamathematics is a branch of mathematics: it studies the syntax and semantics of formal languages and axiomatic systems set up to model informal mathematical reasoning. In this sense, Gödel’s theorems are a contribution to metamathematics, but not in Goldstein’s sense. In addition, Hilbert never said that mathematics is just ‘a game played according to certain simple rules with meaningless marks on paper’, a view incorrectly ascribed to him by Eric Temple Bell, a mathematician but a very careless historian of mathematics. Hilbert, the most versatile and influential mathematician of the late 19th and early 20th centuries, certainly thought that mathematical concepts are determined by axiomatic systems, but he did not deny that those concepts had meaning; on the contrary.

The misconception of Hilbert as a formalist stems from his aim to secure mathematics against paradoxes that had emerged at the turn of the century by axiomatising it in formal systems representing the various parts of the subject – number theory, analysis, geometry, set theory etc – and establishing that each axiomatised system was consistent. This was to be done step by step, beginning with number theory – the study of the positive integers (1, 2, 3 and so on) – and, following that, in what mathematicians call ‘analysis’, the study of real numbers via sets or sequences of rational numbers (or fractions); and then on to still higher parts of mathematics. Hilbert insisted that consistency proofs be finitary, i.e. make use only of concepts and reasoning involving finite objects and finite collections of them. His programme had a prima facie plausibility since mathematical proofs as represented in formal systems are special finite sequences of symbols, and the consistency of a system would be established by showing that no such sequence produces a contradiction.

As Gödel explained to Hao Wang, who was writing an article about his work, the incompleteness theorems came out of his attempt in 1930 to contribute to Hilbert’s programme by providing a consistency proof of an axiomatic system for analysis. Whatever his philosophical views may have been at the time, his motivation had nothing to do with undermining logical positivism or formalism. To understand Gödel’s intervention, and the way Goldstein has misconstrued it, we need to take account of some more logical terminology. A formal system is said to be complete if for each sentence A in its language, either A or its negation, not-A, is provable; and it is said to be incomplete if that does not hold, i.e. if for some sentence A, both A and not-A are unprovable. The notions of provability, completeness and incompleteness are purely syntactical: they have to do only with the form of expressions and the formal relations between them; the notion of a system’s consistency is, similarly, a syntactical one. By contrast, the notion of truth is semantic, having to do with the meaning assigned to expressions in the language of the system. Hilbert had conjectured that number theory is complete and that its consistency can be proved by finitary means.

In pursuit of Hilbert’s programme, Gödel’s plan was to reduce the consistency of analysis to the consistency of number theory and then to prove the consistency of number theory by finitary means. It was in trying to carry out the first step that he realised he would need to formally express the concept of truth for number theoretical sentences in the language of number theory itself, but that if he could do this, he would be able to produce a form of the Liar Paradox – a statement that asserts its own falsity – within number theory. This would be a contradiction. His plan, he now saw, could not be carried out. On the other hand, since the concept of provability could be formally expressed in the system, a number-theoretical statement A could be formed which asserted its own unprovability. Now if it were possible to prove A in the system for number theory it would contradict its own statement of unprovability; therefore, it is indeed unprovable and hence true, so number theory is incomplete.

This argument presumes that the axioms of number theory are true and that its rules of inference preserve truth, so no contradictions can be met among its provable statements. To meet the finitary restrictions that Hilbert placed on metamathematics, Gödel dispensed with the notion of truth in favour of certain consistency assumptions in the general formulation of his first incompleteness theorem. In part, this showed that if S is any consistent formal system which contains number theory, and A is a statement that asserts its own unprovability in S, then A is indeed not provable in S.

The success of these arguments depends on taking seriously the idea that the metamathematics of a formal system is simply a branch of mathematics, and that when the principles underlying metamathematical arguments are analysed, it may be possible to formalise some or all of them within the system under consideration. In particular, Gödel carefully examined his metamathematical proof of the statement ‘If S is consistent then A is not provable in S,’ and verified that each step of the argument could be formalised in number theory; this makes use of the fact that the consistency of S can be expressed within number theory. Thus S proves that the consistency of S implies the statement A, and since A is not provable in S if S is consistent, it follows that the consistency of S is not provable in S under the same conditions. That is Gödel’s second incompleteness theorem.

Is there any system S for which it is possible to give a finitary proof of its consistency? It follows from Gödel’s second theorem that if S is such that all finitary arguments can be represented within it, then the answer will be no. At the conclusion of Gödel’s incompleteness paper, he asserted that it may well be that there are finitary proofs that cannot be represented in the basic system for number theory used there. Gödel had taken Hilbert’s programme seriously from beginning to end in his work on the incompleteness theorems and had no intention to undermine it. A few years later, though, he came to the conclusion that all finitary arguments can be formalised in number theory and hence that Hilbert’s programme to establish the consistency of mathematics cannot be carried out for that system and, a fortiori, for any system containing it. There is now general agreement that Hilbert’s programme as originally conceived cannot be carried out other than for some relatively weak formal systems. This is not a philosophical conclusion, but concerns only the aims and methodology of metamathematics.

The incompleteness theorems in and of themselves do not support mathematical Platonism. The first of them looks as though it vindicates some form of mathematical realism when expressed in the form that for any sufficiently strong, consistent S, there are statements A that are true but not provable in S, since it seems to tell us something significant about the truth of statements of S. But the vindication is only apparent, since the notion of truth is already presumed in the very formulation of the theorem. Moreover, on closer examination, it is not the truth of mathematical statements in general that is at issue, but only the truth of number-theoretic statements of a very special form.

In other words, not only is Goldstein mistaken about Gödel’s philosophical motivations for proving his incompleteness theorems, she is also wrong about their supposed philosophical consequences. She has, perhaps, been misled by the fact that Gödel himself thought they had such consequences, though not until much later, during the 1950s. He made such claims only in unpublished lectures and essays which, after his death, were retrieved from his Nachlass and published in his Collected Works. Towards the end of a 1951 lecture, ‘Some Basic Theorems on the Foundations of Mathematics and Their Implications’, he says of his arguments in favour of Platonism: ‘Of course I do not claim that the foregoing considerations amount to a real proof of this view about the nature of mathematics. The most I could assert would be to have disproved the nominalistic view, which considers mathematics to consist solely in syntactic conventions and their consequences.’

Between 1953 and 1959, he elaborated this claim in an essay entitled ‘Is Mathematics Syntax of Language?’ Gödel prepared six versions of this essay, but in the end did not submit it (it had been intended for the Library of Living Philosophers volume on Rudolf Carnap). He wrote to the editor: ‘It is easy to allege very weighty and striking arguments in favour of my views, but a complete elucidation of the situation turned out to be more difficult than I had anticipated.’ Gödel was extremely cautious about publishing his philosophical convictions when he could not arrive at completely unassailable arguments in their favour.

Goldstein makes much of Gödel’s supposed ‘decades-smouldering resentment’ towards Wittgenstein, the ‘idol’ of the Vienna Circle. Despite the important influence of the Tractatus on the circle, he was not a positivist or one of its members, and he and Gödel never met or corresponded. It is generally agreed that Wittgenstein, in his Remarks on the Foundations of Mathematics (1956), seriously misunderstood the content of Gödel’s theorems. When this was brought to Gödel’s attention a few years later, he was quite annoyed, but he couldn’t understand why Wittgenstein was questioning their philosophical significance. The two were talking past each other, but were not at ‘loggerheads’as Goldstein would have it.

Although the incompleteness theorems do not have direct philosophical consequences for the nature of mathematical truth, let alone the nature of truth in general (and even less for ‘what is involved in our being human’), they certainly raise questions of great interest for the philosophy of mathematics. If, for example, mathematics is to be founded on systems of axioms, on what basis are those systems to be chosen? The incompleteness theorems tell us that whatever system is accepted, one will need further axioms to arrive at previously unprovable truths. But which axioms, and why? Various answers have been proposed, but none has gained universal acceptance. (Meanwhile, mathematicians have happily gone on doing their thing; for as Gödel himself observed in his 1951 lecture on the foundations of mathematics, it is safe to say that 99.9 per cent of mathematics follows from a small, settled part of the axiomatic theory of sets.)

Other philosophical questions about the nature of mathematics are invited by the incompleteness theorems. If mathematics is about a non-physical Platonic reality, how can mathematicians gain knowledge of it? If, alternatively, it is a human creation, what confers on it its exceptional certainty, which distinguishes it from most other areas of human thought? From either point of view, how come mathematics is so useful in describing the physical world? Gödel’s theorems have also been brought to bear when considering whether the mind is in essence a computing machine, or, more specifically, whether in pursuing mathematical problems the human mind is encompassed by a formal system. In his 1951 lecture, Gödel claimed to have proved a weaker statement: either mind (in principle) surpasses any machine, or there are certain absolutely unsolvable number-theoretic problems. It is clear that Gödel believed that mind is not mechanical, but he could not produce an unassailable proof; even his ‘proof’ of the disjunction lacks mathematical precision, involving as it does so vague a concept of mind.

Those who are fascinated by Gödel’s theorems – and the general idea of limits to what we can know – may still hunger for a more universal view of their possible significance. They should not be satisfied with Goldstein’s ‘vast and messy’ goulash: hers is not a recipe for true understanding.