The General Idea Behind Gödel’s Proof

In the next several chapters we will be studying incompleteness proofs for various axiomatizations of arithmetic. Gödel, 1931, carried out his original proof for axiomatic set theory, but the method is equally applicable to axiomatic number theory. The incompleteness of axiomatic number theory is actually a stronger result since it easily yields the incompleteness of axiomatic set theory. Gödel begins his memorable paper with the following startling words. . . . “The development of mathematics in the direction of greater precision has led to large areas of it being formalized, so that proofs can be carried out according to a few mechanical rules. The most comprehensive formal systems to date are, on the one hand, the Principia Mathematica of Whitehead and Russell and, on the other hand, the Zermelo-Fraenkel system of axiomatic set theory. Both systems are so extensive that all methods of proof used in mathematics today can be formalized in them—i.e. can be reduced to a few axioms and rules of inference. It would seem reasonable, therefore, to surmise that these axioms and rules of inference are sufficient to decide all mathematical questions which can be formulated in the system concerned. In what follows it will be shown that this is not the case, but rather that, in both of the cited systems, there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms.” . . . Gödel then goes on to explain that the situation does not depend on the special nature of the two systems under consideration but holds for an extensive class of mathematical systems. Just what is this “extensive class” of mathematical systems? Various interpretations of this phrase have been given, and Gödel’s theorem has accordingly been generalized in several ways. We will consider many such generalizations in the course of this volume. Curiously enough, one of the generalizations that is most direct and most easily accessible to the general reader is also the one that appears to be the least well known.