Godel's Proof

Ernest Nagel, James R. Newman

• Publisher: Routledge
• Year: 2012
• ISBN:
  9781135865399
• Edition: 3
• Topic: Philosophy
• Subtopic: Philosophy History & Theory

'Nagel and Newman accomplish the wondrous task of clarifying the argumentative outline of Kurt Godel's celebrated logic bomb.' – The Guardian

In 1931 the mathematical logician Kurt Godel published a revolutionary paper that challenged certain basic assumptions underpinning mathematics and logic. A colleague of physicist Albert Einstein, his theorem proved that mathematics was partly based on propositions not provable within the mathematical system. The importance of Godel's Proof rests upon its radical implications and has echoed throughout many fields, from maths to science to philosophy, computer design, artificial intelligence, even religion and psychology. While others such as Douglas Hofstadter and Roger Penrose have published bestsellers based on Godel's theorem, this is the first book to present a readable explanation to both scholars and non-specialists alike. A gripping combination of science and accessibility, Godel's Proof by Nagel and Newman is for both mathematicians and the idly curious, offering those with a taste for logic and philosophy the chance to satisfy their intellectual curiosity.

Kurt Godel (1906 – 1978) Born in Brunn, he was a colleague of physicist Albert Einstein and professor at the Institute for Advanced Study in Princeton, N.J.

1

INTRODUCTION

In 1931 there appeared in a German scientific periodical a relatively short paper with the forbidding title “Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme” (“On Formally Undecidable Propositions of Principia Mathematica and Related Systems”). Its author was Kurt Gödel, then a young mathematician of 25 at the University of Vienna and since 1938 a permanent member of the Institute for Advanced Study at Princeton. The paper is a milestone in the history of logic and mathematics. When Harvard University awarded Gödel an honorary degree in 1952, the citation described the work as one of the most important advances in logic in modern times.

At the time of its appearance, however, neither the title of Gödel’s paper nor its content was intelligible to most mathematicians. The Principia Mathematica mentioned in the title is the monumental three-volume treatise by Alfred North Whitehead and Bertrand Russell on mathematical logic and the foundations of mathematics; and familiarity with that work is not a prerequisite to successful research in most branches of mathematics. Moreover, Gödel’s paper deals with a set of questions that has never attracted more than a comparatively small group of students. The reasoning of the proof was so novel at the time of its publication that only those intimately conversant with the technical literature of a highly specialized field could follow the argument with ready comprehension. Nevertheless, the conclusions Gödel established are now widely recognized as being revolutionary in their broad philosophical import. It is the aim of the present essay to make the substance of Gödel’s findings and the general character of his proof accessible to the non-specialist.

Gödel’s famous paper attacked a central problem in the foundations of mathematics. It will be helpful to give a brief preliminary account of the context in which the problem occurs. Everyone who has been exposed to elementary geometry will doubtless recall that it is taught as a deductive discipline. It is not presented as an experimental science whose theorems are to be accepted because they are in agreement with observation. This notion, that a proposition may be established as the conclusion of an explicit logical proof, goes back to the ancient Greeks, who discovered what is known as the “axiomatic method” and used it to develop geometry in a systematic fashion. The axiomatic method consists in accepting without proof certain propositions as axioms or postulates (e.g., the axiom that through two points just one straight line can be drawn), and then deriving from the axioms all other propositions of the system as theorems. The axioms constitute the “foundations” of the system; the theorems are the “superstructure,” and are obtained from the axioms with the exclusive help of principles of logic.

The axiomatic development of geometry made a powerful impression upon thinkers throughout the ages; for the relatively small number of axioms carry the whole weight of the inexhaustibly numerous propositions derivable from them. Moreover, if in some way the truth of the axioms can be established—and, indeed, for some two thousand years most students believed without question that they are true of space—both the truth and the mutual consistency of all the theorems are automatically guaranteed. For these reasons the axiomatic form of geometry appeared to many generations of outstanding thinkers as the model of scientific knowledge at its best. It was natural to ask, therefore, whether other branches of thought besides geometry can be placed upon a secure axiomatic foundation. However, although certain parts of physics were given an axiomatic formulation in antiquity (e.g., by Archimedes), until modern times geometry was the only branch of mathematics that had what most students considered a sound axiomatic basis.

But within the past two centuries the axiomatic method has come to be exploited with increasing power and vigor. New as well as old branches of mathematics, including the familiar arithmetic of cardinal (or “whole”) numbers, were supplied with what appeared to be adequate sets of axioms. A climate of opinion was thus generated in which it was tacitly assumed that each sector of mathematical thought can be supplied with a set of axioms sufficient for developing systematically the endless totality of true propositions about the given area of inquiry.

Gödel’s paper showed that this assumption is untenable. He presented mathematicians with the astounding and melancholy conclusion that the axiomatic method has certain inherent limitations, which rule out the possibility that even the ordinary arithmetic of the integers can ever be fully axiomatized. What is more, he proved that it is impossible to establish the internal logical consistency of a very large class of deductive systems— elementary arithmetic, for example—unless one adopts principles of reasoning so complex that their internal consistency is as open to doubt as that of the systems themselves. In the light of these conclusions, no final systematization of many important areas of mathematics is attainable, and no absolutely impeccable guarantee can be given that many significant branches of mathematical thought are entirely free from internal contradiction.

Gödel’s findings thus undermined deeply rooted preconceptions and demolished ancient hopes that were being freshly nourished by research on the foundations of mathematics. But his paper was not altogether negative. It introduced into the study of foundation questions a new technique of analysis comparable in its nature and fertility with the algebraic method that René Descartes introduced into geometry. This technique suggested and initiated new problems for logical and mathematical investigation. It provoked a reappraisal, still under way, of widely held philosophies of mathematics, and of philosophies of knowledge in general.

The details of Gödel’s proofs in his epoch-making paper are too difficult to follow without considerable mathematical training. But the basic structure of his demonstrations and the core of his conclusions can be made intelligible to readers with very limited mathematical and logical preparation. To achieve such an understanding, the reader may find useful a brief account of certain relevant developments in the history of mathematics and of modern formal logic. The next four sections of this essay are devoted to this survey.

2

THE PROBLEM OF CONSISTENCY

The nineteenth century witnessed a tremendous expansion and intensification of mathematical research. Many fundamental problems that had long withstood the best efforts of earlier thinkers were solved; new departments of mathematical study were created; and in various branches of the discipline new foundations were laid, or old ones entirely recast with the help of more precise techniques of analysis. To illustrate: the Greeks had proposed three problems in elementary geometry: with compass and straight-edge to trisect any angle, to construct a cube with a volume twice the volume of a given cube, and to construct a square equal in area to that of a given circle. For more than 2,000 years unsuccessful attempts were made to solve these problems; at last, in the nineteenth century it was proved that the desired constructions are logically impossible. There was, moreover, a valuable by-product of these labors. Since the solutions depend essentially upon determining the kind of roots that satisfy certain equations, concern with the celebrated exercises set in antiquity stimulated profound investigations into the nature of number and the structure of the number continuum. Rigorous definitions were eventually supplied for negative, complex, and irrational numbers; a logical basis was constructed for the real number system; and a new branch of mathematics, the theory of infinite numbers, was founded.

But perhaps the most significant development in its long-range effects upon subsequent mathematical history was the solution of another problem that the Greeks raised without answering. One of the axioms Euclid used in systematizing geometry has to do with parallels. The axiom he adopted is logically equivalent to (though not identical with) the assumption that through a point outside a given line only one parallel to the line can be drawn. For various reasons, this axiom did not appear “self-evident” to the ancients. They sought, therefore, to deduce it from the other Euclidean axioms, which they regarded as clearly self-evident.¹ Can such a proof of the parallel axiom be given? Generations of mathematicians struggled with this question, without avail. But repeated failure to construct a proof does not mean that none can be found any more than repeated failure to find a cure for the common cold establishes beyond doubt that mankind will forever suffer from running noses. It was not until the nineteenth century, chiefly through the work of Gauss, Bolyai, Lobachevsky, and Riemann, that the impossibility of deducing the parallel axiom from the others was demonstrated. This outcome was of the greatest intellectual importance. In the first place, it called attention in a most impressive way to the fact that a proof can be given of the impossibility of proving certain propositions within a given system. As we shall see, Gödel’s paper is a proof of the impossibility of demonstrating certain important propositions in arithmetic. In the second place, the resolution of the parallel axiom question forced the realization that Euclid is not the last word on the subject of geometry, since new systems of geometry can be constructed by using a number of axioms different from, and incompatible with, those adopted by Euclid. In particular, as is well known, immensely interesting and fruitful results are obtained when Euclid’s parallel axiom is replaced by the assumption that more than one parallel can be drawn to a given line through a given point, or, alternatively, by the assumption that no parallels can be drawn. The traditional belief that the axioms of geometry (or, for that matter, the axioms of any discipline) can be established by their apparent self-evidence was thus radically undermined. Moreover, it gradually became clear that the proper business of the pure mathematician is to derive theorems from postulated assumptions, and that it is not his concern as a mathematician to decide whether the axioms he assumes are actually true. And, finally, these successful modifications of orthodox geometry stimulated the revision and completion of the axiomatic bases for many other mathematical systems. Axiomatic foundations were eventually supplied for fields of inquiry that had hitherto been cultivated only in a more or less intuitive manner. (See Notes, no. 1.)

The over-all conclusion that emerged from these critical studies of the foundations of mathematics is that the age-old conception of mathematics as “the science of quantity” is both inadequate and misleading. For it became evident that mathematics is simply the discipline par excellence that draws the conclusions logically implied by any given set of axioms or postulates. In fact, it came to be acknowledged that the validity of a mathematical inference in no sense depends upon any special meaning that may be associated with the terms or expressions contained in the postulates. Mathematics was thus recognized to be much more abstract and formal than had been traditionally supposed: more abstract, because mathematical statements can be construed in principle to be about anything whatsoever rather than about some inherently circumscribed set of objects or traits of objects; and more formal, because the validity of mathematical demonstrations is grounded in the structure of statements, rather than in the nature of a particular subject matter. The postulates of any branch of demonstrative mathematics are not inherently about space, quantity, apples, angles, or budgets; and any special meaning that may be associated with the terms (or “descriptive predicates”) in the postulates plays no essential role in the process of deriving theorems. We repeat that the sole question confronting the pure mathematician (as distinct from the scientist who employs mathematics in investigating a special subject matter) is not whether the postulates he assumes or the conclusions he deduces from them are true, but whether the alleged conclusions are in fact the necessary logical consequences of the initial assumptions.

Take this example. Among the undefined (or “primitive”) terms employed by the influential German mathematician David Hilbert in his famous axiomatization of geometry (first published in 1899) are ‘point’, ‘line’, ‘lies on’, and ‘between’. We may grant that the customary meanings connected with these expressions play a role in the process of discovering and learning theorems. Since the meanings are familiar, we feel we understand their various interrelations, and they motivate the formulation and selection of axioms; moreover, they suggest and facilitate the formulation of the statements we hope to establish as theorems. Yet, as Hilbert plainly states, insofar as we are concerned with the primary mathematical task of exploring the purely logical relations of dependence between statements, the familiar connotations of the primitive terms are to be ignored, and the sole “meanings” that are to be associated with them are those assigned by the axioms into which they enter.² This is the point of Russell’s famous epigram: pure mathematics is the subject in which we do not know what we are talking about, or whether what we are saying is true.

A land of rigorous abstraction, empty of all familiar landmarks, is certainly not easy to get around in. But it offers compensations in the form of a new freedom of movement and fresh vistas. The intensified formalization of mathematics emancipated men’s minds from the restrictions that the customary interpretation of expressions placed on the construction of novel systems of postulates. New kinds of algebras and geometries were developed which marked significant departures from the mathematics of tradition. As the meanings of certain terms became more general, their use became broader and the inferences that could be drawn from them less confined. Formalization led to a great variety of systems of considerable mathematical interest and value. Some of these systems, it must be admitted, did not lend themselves to interpretations as obviously intuitive (i.e., commonsensical) as those of Euclidean geometry or arithmetic, but this fact caused no alarm. Intuition, for one thing, is an elastic faculty: our children will probably have no difficulty in accepting as intuitively obvious the paradoxes of relativity, just as we do not boggle at ideas that were regarded as wholly unintuitive a couple of generations ago. Moreover, as we all know, intuition is not a safe guide: it cannot properly be used as a criterion of either truth or fruitfulness in scientific explorations.

However, the increased abstractness of mathematics raised a more serious problem. It turned on the question whether a given set of postulates serving as foundation of a system is internally consistent, so that no mutually contradictory theorems can be deduced from the postulates. The problem does not seem pressing when a set of axioms is taken to be about a definite and familiar domain of objects; for then it is not only significant to ask, but it may be possible to ascertain, whether the axioms are indeed true of these objects. Since the Euclidean axioms were generally supposed to be true statements about space (or objects in space), no mathematician prior to the nineteenth century ever considered the question whether a pair of contradictory theorems might some day be deduced from the axioms. The basis for this confidence in the consistency of Euclidean geometry is the sound principle that logically incompatible statements cannot be simultaneously true; accordingly, if a set of statements is true (and this was assumed of the Euclidean axioms), these statements are mutually consistent.

The non-Euclidean geometries were clearly in a different category. Their axioms were initially regarded as being plainly false of space, and, for that matter, doubtfully true of anything; thus the problem of establishing the internal consistency of non- Euclidean systems was recognized to be both formidable and critical. In Riemannian geometry, for example, Euclid’s parallel postulate is replaced by the assumption that through a given point outside a line no parallel to it can be drawn. Now suppose the question: Is the Riemannian set of postulates consistent? The postulates are apparently not true of the space of ordinary experience. How, then, is their consistency to be shown? How can one prove they will not lead to contradictory theorems? Obviously the question is not settled by the fact that the theorems already deduced do not contradict each other—for the possibility remains that the very next theorem to be deduced may upset the apple cart. But, until the question is settled, one cannot be cert...