                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

Gödel: The Completeness and Incompleteness Theorems

Kurt Gödel (1906–1978)

1930 - The completeness of first-order logic 1931 - On formally undecidable statements of Principia Mathematica and related

systems I

Gödel’s first paper proves the completeness of the axioms and rules of first-order logic, essentially as given in Hilbert and Ackermann. There has been much discussion as to why Skolem (or Herbrand) were so close, yet did not think of the question. Gödel makes use of a simple transformation which shows that it is enough to prove that a (derivation) consistent set of sentences has a model. Then he uses the Skolem normal forms of his sentences to aid in constructing the model. A proof based on ideas of Henkin is given in LMCS. And also, at the end of Chapter V of LMCS one can find a simple diagram linking the work of Löwenheim, Skolem, Herbrand and Gödel.

The second paper was far more sophisticated. Recall that in 1930 it was well known that all traditional mathematical proofs could be expressed in powerful systems like Principia Mathematica and ZFC. The open question was whether or not they were powerful enough for all future mathematics as well, i.e., were they complete? Gödel, using only elementary number theory, showed that one could encode the workings of these powerful systems into formulas about numbers. Then he was able to construct true sentences (in these formalisms) about numbers which could not be proved using these systems.

Finally he added a brief remark to the effect that a sentence which expresses the consistency of such a system could not be proved in the system. This has widely been regarded as the end of Hilbert’s program to prove the consistency of mathematics by finitary means.

References

[1] K. Gödel, Die Vollständigkeit der Axiome des logisch Funktionenkalküls. Monatshefte für Mathematik und Physik, 37 (1930), 349–360. 1930.

[transl. in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]

[2] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter System. I. Monatshefte für Mathematik und Physik, 38 (1931), f173–198. [transl. in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]