by Ernest Nagel, James R. Newman, Douglas R. Hofstadter
You have 111 highlighted passages
You have 18 notes
Last annotated on November 26, 2013
Great summary of the idea from RationalWiki: “ Gödel shows that it is impossible to be completely truthful and completely universal; you can never say every true statement without saying some false ones, or, alternatively, you can never say only true things without being forced to withhold some true statements.”
http://rationalwiki.org/wiki/Essay:G%C3%B6del's_incompleteness_theorem_simply_explained
Foreword to the New Edition by Douglas R. Hofstadter
People were convinced that mathematical thinking could be captured by laws of pure symbol manipulation. From a fixed set of axioms and a fixed set of typographical rules, one could shunt symbols around and produce new strings of symbols, called “theorems.” The pinnacle of this movement was a monumental three-volume work by Bertrand Russell and Alfred North Whitehead called Principia Mathematica, which came out in the years 1910–1913. Russell and Whitehead believed that they had grounded all of mathematics in pure logic, and that their work would form the solid foundation for all of mathematics forevermore. A couple of decades later, Gödel began to doubt this noble vision, Read more at location 85
since the subject matter of Principia Mathematica was numbers, and since Gödel had turned the medium of the volumes also into numbers, this showed that Principia Mathematica was its own subject matter, or in other words, that the patterned formulas of Russell and Whitehead’s system could be seen as saying things about each other, or possibly even about themselves. This wraparound was a truly unexpected turn of events, for it inevitably brought ancient paradoxes of self-reference to Gödel’s mind—above all, “This statement is false.” Using this type of paradox as his guide, Gödel realized that, in principle, he could write down a formula of Principia Mathematica that perversely said about itself, “This formula is unprovable by the rules of Principia Mathematica.” The very existence of such a twisted formula was a huge threat to the edifice of Russell and Whitehead, for they had made the absolute elimination of “vicious circularity” a sacred goal, and had been convinced they had won the battle. But now it seemed that vicious circles had entered their pristine world through the back door, and Pandora’s box was wide open. The self-undermining Gödelian formula had to be dealt with, and Gödel did so most astutely, showing that although it resembled a paradox, it differed subtly from one. In particular, it was revealed to be a true statement that could not be proven using the rules of the system—indeed, a true statement whose unprovability resulted precisely from its truth. In this shockingly bold manner, Gödel stormed the fortress of Principia Mathematica and brought it tumbling down in ruins. Read more at location 93
**** Gödel destroyed the hopes of those who believed that mathematical thinking is capturable by the rigidity of axiomatic systems, and he thereby forced mathematicians, logicians, and philosophers to explore the mysterious newly found chasm irrevocably separating provability from truth. Read more at location 107
Gödel’s great stroke of genius—as readers of Nagel and Newman will see—was to realize that numbers are a universal medium for the embedding of patterns of any sort, and that for that reason, statements seemingly about numbers alone can in fact encode statements about other universes of discourse. In other words, Gödel saw beyond the surface level of number theory, realizing that numbers could represent any kind of structure. Read more at location 153
I Introduction
In 1931 there appeared in a German scientific periodical a relatively short paper with the forbidding title “Über 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 Read more at location 186
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. Read more at location 199
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. Read more at location 211
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 properties of the nonnegative 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—number theory, 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. Read more at location 217
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. Read more at location 230
II: The Problem of Consistency
**** 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 formally demonstrating certain important propositions in number theory. 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. 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 pure mathematicians is to derive theorems from postulated assumptions, and that it is not their concern whether the axioms assumed are actually true. Read more at location 260
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. Read more at location 267
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. 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 assumed or the conclusions deduced from them are true, but whether the alleged conclusions are in fact the necessary logical consequences of the initial assumptions. Read more at location 275
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 people’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. Read more at location 285
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. Read more at location 296
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. Read more at location 300
For example, on this interpretation the elliptic parallel postulate reads: Through a point on the surface of a sphere, no great circle can be drawn parallel to a given great circle. (See Fig. 2.) At first glance this proof of the consistency of elliptic geometry may seem conclusive. But a closer look is disconcerting. For a sharp eye will discern that the problem has not been solved; it has merely been shifted to another domain. The proof attempts to settle the consistency of elliptic geometry by appealing to the consistency of Euclidean geometry. What emerges, then, is only this: elliptic geometry is consistent if Euclidean geometry is consistent. The authority of Euclid is thus invoked to demonstrate the consistency of a system which challenges the exclusive validity of Euclid. The inescapable question is: Are the axioms of the Euclidean system itself consistent? Read more at location 339
Another answer is that the axioms jibe with our actual, though limited, experience of space and that we are justified in extrapolating from the small to the universal. But, although much inductive evidence can be adduced to support this claim, our best proof would be logically incomplete. For even if all the observed facts are in agreement with the axioms, the possibility is open that a hitherto unobserved fact may contradict them and so destroy their title to universality. Inductive considerations can show no more than that the axioms are plausible or probably true. Read more at location 347
The geometric statement that two distinct points uniquely determine a straight line is then transformed into the algebraic truth that two distinct pairs of numbers uniquely determine a linear relation; the geometric theorem that a straight line intersects a circle in at most two points, into the algebraic theorem that a pair of simultaneous equations in two unknowns (one of which is linear and the other quadratic of a certain type) determine at most two pairs of real numbers; and so on. In brief, the consistency of the Euclidean postulates is established by showing that they are satisfied by an algebraic model. This method of establishing consistency is powerful and effective. Yet it, too, is vulnerable to the objection already set forth. Read more at location 362
**** The proof is clearly relative to the assumed consistency of another system and is not an “absolute” proof. Read more at location 368
**** In the various attempts to solve the problem of consistency there is one persistent source of difficulty. It lies in the fact that the axioms are interpreted by models composed of an infinite number of elements. This makes it impossible to encompass the models in a finite number of observations; hence the truth of the axioms themselves is subject to doubt. In the inductive argument for the truth of Euclidean geometry, a finite number of observed facts about space are presumably in agreement with the axioms. But the conclusion that the argument seeks to establish involves an extrapolation from a finite to an infinite set of data. How can we justify this jump? Read more at location 370
Unfortunately, most of the postulate systems that constitute the foundations of important branches of mathematics cannot be mirrored in finite models. Read more at location 381
It is tempting to suggest at this point that we can be sure of the consistency of formulations in which nonfinite models are described if the basic notions employed are transparently “clear” and “distinct.” But the history of thought has not dealt kindly with the doctrine of clear and distinct ideas, or with the doctrine of intuitive knowledge implicit in the suggestion. Such contradictions (technically referred to as “antinomies”) have emerged in the theory of infinite numbers, developed by Georg Cantor in the nineteenth century; and the occurrence of these contradictions has made plain that the apparent clarity of even such an elementary notion as that of class* (or aggregate) does not guarantee the consistency of any particular system built on it. Since the mathematical theory of classes, which deals with the properties and relations of aggregates or collections of elements, is often adopted as the foundation for other branches of mathematics, and in particular for number theory, it is pertinent to ask whether contradictions similar to those encountered in the theory of infinite classes infect the formulations of other parts of mathematics. Read more at location 393
Russell’s antinomy can be stated as follows. Classes seem to be of two kinds: those which do not contain themselves as members, and those which do. A class will be called “normal” if, and only if, it does not contain itself as a member; otherwise it will be called “non-normal.” In short, N is normal if, and only if, N is non-normal. It follows that the statement ‘N is normal’ is both true and false. This fatal contradiction results from an uncritical use of the apparently pellucid notion of “class.” Other paradoxes were found later, each of them constructed by means of familiar and seemingly cogent modes of reasoning. Mathematicians came to realize that in developing consistent systems familiarity and intuitive clarity are weak reeds to lean on. Read more at location 408
in most instances the problem requires the use of a non-finite model, the description of which may itself conceal inconsistencies. We must conclude that, while the model method is an invaluable mathematical tool, it does not supply a final answer to the problem it was designed to solve. Read more at location 413
III: Absolute Proofs of Consistency
An alternative to relative proofs of consistency was proposed by Hilbert. He sought to construct “absolute” proofs, by which the consistency of systems could be established without assuming the consistency of some other system. The first step in the construction of an absolute proof, as Hilbert conceived the matter, is the complete formalization of a deductive system. This involves draining the expressions occurring within the system of all meaning: they are to be regarded simply as empty signs. How these signs are to be combined and manipulated is to be set forth in a set of precisely stated rules. The purpose of this procedure is to construct a system of signs (called a “calculus”) which conceals nothing and which has in it only that which we explicitly put into it. Read more at location 421
A few examples will help to convey an understanding of Hilbert’s distinction between mathematics (i.e., a system of meaningless signs) and meta-mathematics (meaningful statements about mathematics, the signs occurring in the calculus, their arrangement and relations). ...‘2 + 3 = 5’ is an arithmetical formula ...the following statement belongs to meta-mathematics: The formula ‘0 = 0’ is derivable from the formula ‘x = x’ by substituting the numeral ‘0’ for the variable ‘x’. ...the next statement belongs to meta-mathematics: Formal system X is consistent Read more at location 465
**** The formal systems that mathematicians construct belong in the file labeled “mathematics”; the description, discussion, and theorizing about the systems belong in the file marked “meta-mathematics.” The importance to our subject of recognizing the distinction between mathematics and meta-mathematics cannot be overemphasized. Failure to respect it has produced paradoxes and confusion. Recognition of its significance has made it possible to exhibit in a clear light the logical structure of mathematical reasoning. Read more at location 477
An “absolute” proof achieves its objectives by using a minimum of principles of inference, and does not assume the consistency of some other set of axioms. Read more at location 496
IV: The Systematic Codification of Formal Logic
Ordinarily, even when mathematical proofs conform to accepted standards of professional rigor, they suffer from an important omission. They embody principles (or rules) of inference not explicitly formulated, of which mathematicians are frequently unaware. Read more at location 524
For almost two thousand years Aristotle’s codification of valid forms of deduction was widely regarded as complete and as incapable of essential improvement. As late as 1787, the German philosopher Immanuel Kant was able to say that since Aristotle, formal logic “has not been able to advance a single step, and is to all appearances a closed and completed body of doctrine.” The fact is that the traditional logic is seriously incomplete, and even fails to give an account of many principles of inference employed in quite elementary mathematical reasoning.6 A renaissance of logical studies in modern times began with the publication in 1847 of George Boole’s The Mathematical Analysis of Logic. Read more at location 554
Principia provides a remarkably comprehensive system of notation, with the help of which all statements of pure mathematics (and of number theory in particular) can be codified in a standard manner; and it makes explicit most of the rules of formal inference used in mathematical demonstrations (eventually, these rules were made more precise and complete). Principia, in sum, created the essential instrument for investigating the entire system of number theory as an uninterpreted calculus—that is, as a system of meaningless marks, whose formulas (or “strings”) are combined and transformed in accordance with stated rules, of operation. Read more at location 601
V: An Example of a Successful Absolute Proof of Consistency
The formalization proceeds in four steps. First, a complete catalogue is prepared of the signs to be used in the calculus. These are its vocabulary. Second, the “Formation Rules” are laid down. They declare which of the combinations of the signs in the vocabulary are acceptable as “formulas” (in effect, as sentences). The rules may be viewed as constituting the grammar of the system. Third, the “Transformation Rules” are stated. They describe the precise structure of formulas from which other formulas of given structure are derivable. These rules are, in effect, the rules of inference. Finally, certain formulas are selected as axioms (or as “primitive formulas”). They serve as foundation for the entire system. Read more at location 614
The variables may have sentences substituted for them and are therefore called “sentential variables.” They are the letters ‘p’, ‘q’, ‘r’, etc. The constant signs are either “sentential connectives” or signs of punctuation. The sentential connectives are: ‘~’ which is short for ‘not’ (and is called the “tilde”), ‘V’ which is short for ‘or’, ‘⊃’ which is short for ‘if . . . then . . .’, and ‘·’ which is short for ‘and’. Read more at location 624
Two Transformation Rules are adopted. One of them, the Rule of Substitution (for sentential variables), says that from a formula containing sentential variables it is always permissible to derive another formula by uniformly substituting formulas for the variables. It is understood that, when substitutions are made for a variable in a formula, the same substitution must be made for each occurrence of the variable. Read more at location 642
Finally, the axioms of the calculus (essentially those of Principia) are the following four formulas: 1. (p V p) ⊃ p or, in ordinary English, if either p or p, then p 1. If (either Henry VIII was a boor or Henry VIII was a boor) then Henry VIII was a boor 2. p ⊃ (p V q) that is, if p, then either p or q 2. If psychoanalysis is fashionable, then (either psychoanalysis is fashionable or headache powders are sold cheap) 3. (p V q) ⊃ (q V p) that is, if either p or q, then either q or p 3. If (either Immanuel Kant was punctual or Hollywood is sinful), then (either Hollywood is sinful or Immanuel Kant was punctual) 4. (p ⊃ q) ⊃ ((r V p) ⊃ (r V q)) that is, if (if p then q) then (if (either r or p) then (either r or q)) 4. If (if ducks waddle then 5 is a prime) then (if (either Churchill drinks brandy or ducks waddle) then (either Churchill drinks brandy or 5 is a prime)) Read more at location 654
Each of these axioms may seem “obvious” and trivial. Nevertheless, it is possible to derive from them with the help of the stated Transformation Rules an indefinitely large class of theorems which are far from obvious or trivial. Read more at location 674
The task, therefore, is to show that there is at least one formula that cannot be derived from the axioms. The way this is done is to employ meta-mathematical reasoning upon the system before us. The actual procedure is elegant. It consists in finding a characteristic or structural property of formulas which satisfies the three following conditions. (1) The property must be common to all four axioms. (One such property is that of containing not more than 25 elementary signs; however, this property does not satisfy the next condition.) (2) The property must be “hereditary” under the Transformation Rules—that is, if all the axioms have the property, any formula properly derived from them by the Transformation Rules must also have it. Since any formula so derived is by definition a theorem, this condition in essence stipulates that every theorem must have the property. (3) The property must not belong to every formula that can be constructed in accordance with the Formation Rules of the system—that is, we must seek to exhibit at least one formula that does not have the property. If we succeed in this threefold task, we shall have an absolute proof of consistency. Read more at location 691
VI: The Idea of Mapping and Its Use in Mathematics
What did Gödel establish, and how did he prove his results? His main conclusions are twofold. In the first place (though this is not the order of Gödel’s actual argument), he showed that it is impossible to give a meta-mathematical proof of the consistency of a system comprehensive enough to contain the whole of arithmetic (such as Principia Mathematica)—unless the proof itself employs rules of inference different in certain essential respects from the Transformation Rules used in deriving theorems within the system. Read more at location 757
Gödel’s second main conclusion is even more surprising and revolutionary, because it demonstrates a fundamental limitation in the power of the axiomatic method. Gödel showed that Principia, or any other system within which arithmetic can be developed, is essentially incomplete. In other words, given any consistent formalization of number theory, there are true number-theoretical statements that cannot be derived in the system. Read more at location 766
The idea of “mapping” is well known and plays a fundamental role in many branches of mathematics. It is used, of course, in the construction of ordinary maps, where shapes on the surface of a sphere are projected onto a plane, so that the relations between the plane figures mirror the relations between the figures on the spherical surface. It is used in coordinate geometry, which translates geometry into algebra, so that geometric relations are mapped onto algebraic ones. Read more at location 821
The basic feature of mapping is that an abstract structure of relations embodied in one domain of “objects” can be shown to hold between “objects” (usually of a sort different from the first set) in another domain. It is this feature which stimulated Gödel in constructing his proofs. If complicated meta-mathematical statements about a formalized system of arithmetic could, as he hoped, be translated into (or mirrored by) arithmetical statements within the system itself, an important gain would be achieved in facilitating meta-mathematical demonstrations. Read more at location 844
The exploitation of the notion of mapping is the key to the argument in Gödel’s famous paper. Read more at location 850
Gödel showed that meta-mathematical statements about a formalized arithmetical calculus can indeed be represented by arithmetical formulas within the calculus. As we shall explain in greater detail in the next section, he devised a method of representation such that neither the arithmetical formula corresponding to a certain meta-mathematical statement, nor the arithmetical formula corresponding to the denial of the statement, is demonstrable within the calculus. Since one of these arithmetical formulas must codify an arithmetical truth, yet neither is derivable from the axioms, the system is incomplete. Read more at location 852
Gödel’s method of representation also enabled him to construct a number-theoretical statement corresponding to the meta-mathematical statement ‘The calculus is consistent’ and to show that the formal translation of this statement into the notation of the formal calculus is not demonstrable within the calculus. Read more at location 856
VII: Gödel’s Proofs
Gödel’s paper is difficult. Forty-six preliminary definitions, together with several important preliminary propositions, must be mastered before the main results are reached. Read more at location 862
A Gödel numbering
Gödel described a formalized calculus, which we shall call “PM,” within which all the customary arithmetical notations can be expressed and familiar arithmetical relations established.15 The formulas of the calculus are constructed out of a class of elementary signs, which constitute the fundamental vocabulary. A set of primitive formulas (or axioms) are the underpinning, and the theorems of the calculus are formulas derivable from the axioms with the help of a carefully enumerated set of Transformation Rules (or rules of inference). Read more at location 866
Gödel first showed that it is possible to assign a unique number to each elementary sign, each formula (or sequence of signs), and each proof (or finite sequence of formulas). This number, which serves as a distinctive tag or label, is called the “Gödel number” of the sign, formula, or proof. Read more at location 870
The elementary signs belonging to the fundamental vocabulary are of two kinds: the constant signs and the variables. We shall assume that there are exactly twelve constant signs,17 to which the integers from 1 to 12 are attached as Gödel numbers. Most of these signs are already known to the reader: ‘~’ (short for ‘not’); ‘V’ (short for ‘or’); ‘⊃’ (short for ‘if . . . then . . .’); ‘=’ (short for ‘equals’); ‘0’ (the numeral representing the number zero); ‘+’ (short for ‘plus’); ‘×’ (short for ‘times’); and three signs of punctuation, namely, the left parenthesis ‘(’, the right parenthesis ‘)’, and the comma ‘,’. In addition, two other signs will be used: the inverted letter ‘E’, which may be read as ‘there is’, and which occurs in so-called “existential quantifiers”; and the lowercase letter ‘s’, which is prefixed to numerical expressions to designate the immediate successor of a number. To illustrate: the formula ‘(∃x) (x = s0)’ may be read ‘There is an x such that x is the immediate successor of zero’.
the interpretation of a symbol hinges on how the symbol behaves inside theorems of PM (and this, in turn, hinges on the axioms and the rules of inference of PM). Read more at location 899
In order to lock in the standard interpretations of the symbols in the formal system PM, Gödel showed, in Proposition V of his 1931 paper, that there is an infinite class of theorems of PM, every one of which, if interpreted according to the table of usual meanings above, expresses an arithmetical truth, and conversely, that there is an infinite class of arithmetical truths (the primitive recursive ones) every one of which, if it is converted into a formal statement via the table above, yields a theorem of PM.18 This highly systematic correspondence of truths and interpreted theorems does two things at once: not only does it confirm the power of PM as an axiomatic system for number theory, but it also pins down the conventional interpretations for each and every symbol. In short, Gödel convincingly demonstrated that the symbols of PM do indeed merit their “meanings” Read more at location 908
Today, Gödel’s key result is known as the “Correspondence Lemma,” the name coming from the two-tier correspondence that it confirms—firstly, that every primitive recursive truth, when encoded as a string of symbols of the formal calculus, is a theorem, and secondly, that on a one-by-one basis, the formal symbols merit their intended interpretations. One sees hereby the way in which truth and meaning are inextricably intertwined. Read more at location 916
Besides the constant signs, three kinds of variables appear in PM: the numerical variables ‘x’, ‘y’, ‘z’, etc., for which numerals (such as ‘ss0’) and numerical expressions (such as ‘x + y’) may be substituted; the sentential variables ‘p’, ‘q’, ‘r’, etc., for which formulas (sentences) may be substituted; and the predicate variables ‘P ‘, ‘Q’, ‘R’, etc., for which predicates, such as “is prime”, or “is greater than,” may be substituted. Read more at location 919
The variables are assigned Gödel numbers in accordance with the following rules: (i) with each distinct numerical variable, associate a distinct prime number greater than 12; (ii) with each distinct sentential variable, associate the square of a prime number greater than 12; (iii) with each distinct predicate variable, associate the cube of a prime number greater than 12. Read more at location 924
B The arithmetization of meta-mathematics
Gödel’s next step is an ingenious application of mapping. He showed that all meta-mathematical statements about the structural properties of expressions in the formal calculus can be accurately mirrored within the calculus itself. The basic idea underlying his procedure is this: Since every expression in PM is associated with a particular (Gödel) number, a meta-mathematical statement about formal expressions and their typographical relations to one another may be construed as a statement about the corresponding (Gödel) numbers and their arithmetical relations to one another. In this-way meta-mathematics becomes completely “arithmetized.” Read more at location 977
In sum, there is a theorem of PM that is a translation of the true meta-mathematical statement “The initial symbol of ‘~(0 = 0)’ is the tilde.” We thus see our first example of how PM is actually able to talk about itself faithfully (i..e, with meta-mathematical truths being mirrored by theorems of PM), thanks firstly to the ingenious mapping device of Gödel numbering, and secondly to the Correspondence Lemma, guaranteeing that symbols merit their meanings. Read more at location 1014
The extremely simple case we have just given exemplifies a very general and deep insight that lies at the heart of Gödel’s discovery: typographical properties of long chains of symbols can be talked about in an indirect but perfectly accurate manner by instead talking about the properties of prime factorizations of large integers. This is what we mean by the phrase “the arithmetization of meta-mathematics.” When we combine this idea with that of the formalization of arithmetic (i.e., number theory) within PM, we arrive at the idea of the formalization of meta-mathematics within PM. Read more at location 1018
Gödel took great pains, in his paper, to convince his readers that dem (x, z) is a primitive recursive relationship between the numbers x and z, and from this fact (which we shall accept on faith) it follows, via Gödel’s Correspondence Lemma, that there is a formula of PM expressing this relationship in the formal notation. We shall denote this formula by the abbreviation ‘Dem (x, z)’, with a capital ‘D’, which signals its formality. Read more at location 1036
This rather circular-seeming idea of substituting a string’s own Gödel number into the string itself (and then taking the Gödel number of the result) was one of Gödel’s key insights, as we shall see, and he again took great pains to convince his readers that this function is sufficiently straightforwardly calculable as to be primitive recursive, and thus to fall under the scope of the Correspondence Lemma. Read more at location 1063
we shall abbreviate that expression by ‘Sub (x, 17, x)’, drawing the crucial distinction between the informal arithmetical concept and its formal typographical counterpart as we did before—namely, by using lowercase and uppercase initial letters, respectively. You should keep in mind that whereas ‘sub (243,000,000, 17, 243,000,000)’ designates a number (i.e., a magnitude or quantity),27 what the abbreviation ‘Sub (243,000,000, 17, 243,000,000)’ designates is a string inside PM. Read more at location 1071
the “meaningless” string ‘ss0 + ss0’ acts as the formal representative inside PM for the very simple calculation “two plus two” (and thus, although more indirectly, for the concept “four”). Read more at location 1078
C The heart of Gödel’s argument
Gödel showed (i) how to construct a formula G of PM that represents the meta-mathematical statement: ‘The formula G is not demonstrable using the rules of PM’.29 This formula thus ostensibly says of itself that it is not demonstrable. Read more at location 1083
Gödel then showed (iii) that, though G is not formally demonstrable, it nevertheless is a true arithmetical formula (see the remarks about loose parlance in footnote 23). G is true in the sense that it claims that a certain arithmetical property defined by Gödel is possessed by no integer—and indeed, no integer possesses the property, as Gödel shows. Read more at location 1093
Step (iv) is the realization that since G is both true and formally undecidable (within PM), PM must be incomplete. In other words, we cannot deduce all arithmetical truths from the axioms and rules of PM. Moreover, Gödel established that PM is essentially incomplete: even if PM were augmented by additional axioms (or rules) so that the true formula G could be formally derived within the enhanced calculus, then another true formula G′ could be constructed in a precisely analogous manner, and G′ would be formally undecidable inside the enhanced calculus. Read more at location 1096
In step (v), Gödel described how to construct a formula A of PM that represents the meta-mathematical statement: ‘PM is consistent’; and he showed that the formula ‘A ⊃ G’ is formally demonstrable inside PM. Finally, he showed that the formula A is not demonstrable inside PM. From this it follows that the consistency of PM cannot be established by any chain of logical reasoning that can be mirrored within the formal reasoning system that PM itself constitutes. Read more at location 1102
Gödel was in fact worried that because of the shock value of his paper, many people would doubt its validity, and he therefore intended to buttress his reasoning in the sequel. It turned out, however, that his paper was so cogently written that its conclusions were quickly accepted, thus obviating any need for a sequel. The point, then, is that Gödel’s results are not due to some odd defect in the specific system PM; they are applicable to any system that incorporates the arithmetical properties of the cardinal numbers, including addition and multiplication. Read more at location 1110
Now we shall broach Gödel’s argument more fully.
(i) The formula ‘Dem (x, z)’ has already been defined. It represents within PM the meta-mathematical statement: ‘The sequence of formulas with the Gödel number x is a proof for the formula with the Gödel number z’. Read more at location 1115
If we prefix this formula with the tilde, thus constructing its formal negation, we get: ‘~(∃x) Dem (x, z)’. This formula constitutes a formal paraphrase, within PM, of the meta-mathematical statement: ‘The formula with Gödel number z is not demonstrable’—or, to put it another way, ‘No proof can be adduced for the formula with Gödel number z’. What Gödel showed is that a certain special case of this formula is not formally demonstrable. Read more at location 1121
Since the formula on line (1) belongs to PM, it has a (very large) Gödel number that could, in principle, be calculated. Luckily, we shall not actually calculate it (nor did Gödel); we shall simply designate its value by the letter ‘n’. We now proceed to replace all occurrences of the variable ‘y’ in formula (1) by the number n (more precisely, by the numeral for the number n, which we will blithely write as ‘n’, just as we will write ‘17’, knowing that we really mean ‘sssssssssssssssss0’). This will yield a new formula, which we shall call ‘G’: ...We must now recall that G is the mirror image within PM of the meta-mathematical statement: ‘The formula with Gödel number g is not demonstrable’. It follows, then, that G represents, inside PM, the meta-mathematical statement: ‘The formula G is not demonstrable’. In a word, the PM formula G can be construed as asserting of itself that it is not a theorem of PM. Read more at location 1149
(ii) We come to the second step—the proof that G is not, in fact, a theorem of PM. Read more at location 1153
G is demonstrable if, and only if, ~G is demonstrable.34 But as we noted earlier, if a formula and its formal negation can both be derived in some formal calculus, then the calculus is not consistent. Turning this around, then, we reason that if PM is a consistent formal calculus, neither the formula G nor its negation can be demonstrable. In short, if PM is consistent, then G is necessarily formally undecidable.35 Read more at location 1158
(iii) To convince ourselves that G is true, it suffices to consider only the former interpretation.) But we have just shown that G is undecidable within PM, so in particular G has no proof inside PM. But that, recall, is just what G asserts! So G asserts the truth. The reader should carefully note that we have established a number-theoretical truth not by deducing it formally from the axioms and rules of a formal system, but by a meta-mathematical argument. Read more at location 1169
(iv) since we have just established that G is a true formula of PM that is not formally deducible within PM, it follows that PM is an incomplete system—on the hypothesis, of course, that it is consistent.36 Moreover, PM is in even greater trouble than one might at first think, for it turns out to be not just incomplete, but essentially incomplete: even if G were added as a further axiom, the augmented system would still not suffice to yield formally all arithmetical truths. For, if the initial axioms were augmented in this manner, another true but undecidable formula could be constructed in the enlarged system. The undecidable formula belonging to the new system is constructed merely by imitating the recipe by which Gödel specified a true but undecidable formula in PM itself. This method for producing undecidable formulas can be carried out no matter how often the initial system is enlarged. Nor does it depend in any crucial manner on peculiarities of Russell and Whitehead’s formal calculus PM. The trick works no matter what system is taken as a starting point, as long as that system is totally formal and as long as it contains axioms setting forth the elementary properties of whole numbers, including addition and multiplication. Read more at location 1183
**** We are thus compelled to recognize a fundamental limitation concerning the power of formal axiomatic reasoning. Contrary to all prior belief, the vast continent of arithmetical truth cannot be brought into systematic order by laying down for once and for all a fixed set of axioms and rules of inference from which every true arithmetical statement can be formally derived. For anyone inclined to believe that the essence of mathematics is purely formal axiomatic reasoning, this must come as a shocking revelation. Read more at location 1188
(v) The steps have been traced by which he grounded the meta-mathematical statement: ‘If PM is consistent, it is incomplete’. But it can also be shown that this conditional statement taken as a whole is represented by a demonstrable formula within PM. Read more at location 1192
(A) (∃y) ~ (∃x) Dem (x, y) Read more at location 1200
The formula A therefore represents the antecedent clause of the meta-mathematical statement ‘If PM is consistent, it is incomplete’. On the other hand, the consequent clause in this statement—namely, ‘It [PM] is incomplete’—is equivalent to saying, about any true but non-demonstrable formula X, ‘X is not a theorem of PM’. Luckily, we know of one such formula X—namely, our old friend, the formula G. We can therefore translate the consequent clause into the formal language of PM by writing the string that says ‘G is not a theorem of PM’. And it is none other than G itself that says this. And so G can be used as the consequent clause of our conditional meta-mathematical statement. Read more at location 1203
Where does this lead us? The formula A is a formal expression inside PM of the meta-mathematical claim ‘PM is consistent’. If, therefore, this meta-mathematical claim could be informally established by some chain of steps of reasoning, and if that chain of steps could be mapped onto a sequence of formulas constituting a proof in PM, then the formula A would itself be demonstrable inside PM. But this, as we have just seen, is impossible, if PM is consistent. The grand final step is thus before us: we are forced to conclude that if PM is consistent, its consistency cannot be established by any meta-mathematical reasoning that can be mirrored within PM itself! Read more at location 1217
**** This imposing result of Gödel’s analysis should not be misunderstood: it does not exclude a meta-mathematical proof of the consistency of PM. What it excludes is a proof of consistency that can be mirrored inside PM.37 Read more at location 1222
VIII: Concluding Reflections
The import of Gödel’s conclusions is far-reaching, though it has not yet been fully fathomed. These conclusions show that the prospect of finding for every deductive system (and, in particular, for a system in which the whole of number theory can be expressed) an absolute proof of consistency that satisfies the finitistic requirements of Hilbert’s proposal, though not logically impossible, is most unlikely.39 They show also that there are an endless number of true arithmetical statements which cannot be formally deduced from any given set of axioms by a closed set of rules of inference. It follows that an axiomatic approach to number theory cannot fully characterize the nature of number-theoretical truth. It follows, also, that what we understand by the process of mathematical proof does not coincide with the exploitation of a formalized axiomatic method. Consequently, no final account can be given of the precise nature of valid mathematical demonstrations. Read more at location 1238
Gödel’s conclusions bear on the question whether a calculating machine can be constructed that would match the human brain in mathematical intelligence. Today’s calculating machines have a fixed set of directives built into them; these directives correspond to the fixed rules of inference of formalized axiomatic procedure. ...But, as Gödel showed in his incompleteness theorem, there are innumerable problems in elementary number theory that fall outside the scope of a fixed axiomatic method, and that such engines are incapable of answering, however intricate and ingenious their built-in mechanisms may be and however rapid their operations. Given a definite problem, a machine of this type might be built for solving it; but no one such machine can be built for solving every problem. The human brain may, to be sure, have built-in limitations of its own, and there may be mathematical problems it is incapable of solving. But, even so, the brain appears to embody a structure of rules of operation which is far Read more at location 1246
**** It does not mean, as a recent writer claims, that there are “ineluctable limits to human reason.” It does mean that the resources of the human intellect have not been, and cannot be, fully formalized, and that new principles of demonstration forever await invention and discovery. We have seen that mathematical propositions which cannot be established by formal deduction from a given set of axioms may, nevertheless, be established by “informal” meta-mathematical reasoning. Read more at location 1255
The theorem does indicate that the structure and power of the human mind are far more complex and subtle than any non-living machine yet envisaged. Gödel’s own work is a remarkable example of such complexity and subtlety. It is an occasion, not for dejection, but for a renewed appreciation of the powers of creative reason. Read more at location 1261