Godel's Proof, by Nagel and Newman (revised edition, 2001) 550
I found this short book most welcome because of the denseness of the subject matter. I think it is quite readable and well-written. Godel's incompleteness results, although initially presented in a mere 30-something page paper published in the early 1930s, is a tough mountain to climb even for experts. Nevertheless, it has laid down a gauntlet in logic, foundations of mathematics, and philosophy of mathematics that persists to this day.
Here are some points that stood out to me when I read this book.
Preliminaries
1. Around the year 1900, it was a dream of mathematics to consolidate the whole of mathematics through a proper formalization of its language. That is, through a correct and incisive selection of axioms (presuppositions) and rules of inference, as well as proper signs and notation, of course, mathematics could be developed so as to be deemed provably consistent and complete. Finitistic principles of pure mathematics could be demonstrably shown to be free of contradictions, and could even be applied to infinite domains of mathematics. Thus, any and all mathematical truths could be proven on the basis of a solid mathematical foundation. This program, often associated with Hilbert, was ultimately deemed untenable, if not outright impossible, in the aftermath of Godel's landmark paper.
2. Godel's paper was a paradigm shift in mathematics in the 1930s through the techniques of analysis that it introduced. This is felt in logic, computer science, philosophy, and beyond.
3. Earlier in the Nineteenth century, geometry also underwent a renaissance that shook the foundations of mathematics. It was shown to be possible that proofs of the impossibility of certain posits or suggestions can be rigorously proven. For instance, using writing apparatus, compass, and straightedge alone: squaring the circle, trisecting an angle, and constructing a cube whose volume is exactly double that of a given one. Even more significantly, it was shown that the parallel lines postulate could not be proven on the basis of Euclid's geometrical axioms. Hence non-Euclidean geometries. The spirit of these developments is something that is echoed in a different context in Godel's work, and this paper in particular.
4. The formal, or formalistic, approach gained in ascendency in the Twentieth century. This is a more abstract approach to mathematics. This is to say, axioms need only be taken as postulates. Their truth, meaning, and interpretation should take a backseat to the building of models, analyzing strings of symbols strictly in terms of their logical consequences, and developing new methods. The signs and symbols of mathematics could be construed to be about anything, or nothing. Structures and relations of statements, as well as possible constructions and fields of inquiry, rather than some ordained subject matter, became the focus of modern mathematics. Familiar connotations of the primitive terms and notions can be dispensed with. Even intuition can be stultifying.
5. Although Godel fits within the paradigm of item (4) to a degree, he also allows for a certain sort of metamathematical interpretation in his paper that is integral to his results. The mechanistic side of mathematics, under the hood, so to speak, that is, within formal systems, can be mirrored by metamathematical interpretation of the movement of the argument in his paper. On the one hand, mathematics is the meaningless manipulation of raw symbols under the formalist approach, on the other hand, we may, and indeed should, make interpretations about the mathematics that comes up from the outside, as it were, through a metamathematical demeanor.
6. The first step in Godel's incompleteness proofs is his method of Godel numbering. He devised an ingenious method of assigning all symbols, formulas, and proofs to a unique number. To this end, he uses the Fundamental Theorem of Arithmetic, which is part of number theory. So any bit of a claim of number theory or formal logic is able to be uniquely encoded, and able to be decoded, at least in theory. Using a particular formal system, that of Russell and Whitehead's Principia Mathematica, all symbols in Godel's reiteration of that system are numerically tabulated and then placed in the exponent position of the prime numbers in the order of the sequence of the primes. Just as all positive integers have a unique prime number factorization, i.e. the Fundamental Theorem of Arithmetic, so too does any statement or proof in the context of said formal system. Thus, any part of the given formal system, big or small, is assigned a unique Godel number, which can be theoretically decomposed in terms of prime numbers and their exponents, just as ordinary positive integers can. I say in theory because in practice these Godel numbers quickly get astronomically large, but this is inconsequential to the thrust of his arguments. Through this encoding, the formal system in question can be metamathematically construed as speaking about itself.
First Incompleteness Theorem
7. In the given system of formal logic, Godel cooks up a statement G:
G: There exists a sequence of formulas (with Godel number x) that does not constitute a demonstration of the formula with Godel number n by substituting for the variable with Godel number 17 (i.e. all occurrences of the letter 'n') the numeral for n.
But on the basis of how this statement was constructed, G is actually referring to itself! For G is formed precisely in the manner that it describes in its statement. So G can be metamathematically interpreted as expressing of itself that it is not a theorem in the given formal system.
8. There is a so-called principle of explosion whereby it is said that anything can follow from a contradiction. On this basis, we may assert that G is provable if and only if it is not provable. For G being provable is what is precluded from its own well-formed statement. If G was provable, we can just as well say that this implies G is not provable, and vice versa. Insofar as the given formal system is consistent, it follows that G is undecidable.
9. There is a crucial upshot to (7) above. Namely, that if we wish our given formal system to be consistent, i.e. free of contradiction, we must assent to the truth of formula/statement G. G asserts itself as a true statement, when viewed metamathematically.
Second Incompleteness Theorem
10. Godel cooks up another statement A:
A: There is at least one formula (whose Godel number is y) for which no proposed sequence of formulas (whose Godel number is x) constitutes a proof inside the given formal system.
At this point Godel actually calls us to form the statement 'If A, then G' (both A and G are shown above in ordinary language). More concisely, this can be rendered as 'If the given formal system is consistent, then it is incomplete'. Again, when we consider that the statement 'If A, then G' is formed number theoretically through the method of encodement by Godel numbering, we can metamathematically interpret the given formal system as speaking about itself. If we wish to uphold consistency in the context of the given formal system, we must verily accept that the system is incomplete. In a sense, this is a matter of choice, but most practitioners of mathematics would choose not to forego consistency.
Conclusion
11. One might question whether Russell and Whitehead's formal system of Principia Mathematica is sufficient to use for Godel's argumentation. It is indeed seen to be adequate to translate all of the rest of mathematics in the manner of axiomatic set theory. It is true that today, alternative but related systems tend to be used instead in axiomatic set theory. Although Principia Mathematica is often regarded as cumbersome and ultimately unsuccessful in grounding mathematics in logic, as it set out to do, it is seen as solid in its basic formulations, as well for the purpose of being used in Godel's paper.
12. Although Godel's argument does not totally destroy the possibility of an absolute proof of consistency for a formal system such as that of Principia Mathematica, he did show that no such proof can be mirrored within the formal system of Principia Mathematica. It should also be added that Godel does not necessarily preclude the prospect of a strictly finitistic proof of absolute consistency of arithmetic and number theory that is not capable of being mirrored inside Principia Mathematica. However, to the point of the writing of Nagel and Newman's book,1958, no one knows what such a proof would look like nor whether such a project is even coherent. Perhaps it is really the case that Godel's incompleteness results show inherent limitations to formal systems and the axiomatic method in mathematics. In short, perhaps truth just outruns provability.
