From Frege to Gödel

A Source Book in Mathematical Logic, 1879-1931

Jean van Heijenoort

• Publisher: Harvard University Press
• Year: 2002
• ISBN:
  9780674257245
• Topic: Philosophie
• Subtopic: Geschichte & Theorie der Philosophie

The fundamental texts of the great classical period in modern logic, some of them never before available in English translation, are here gathered together for the first time. Modern logic, heralded by Leibniz, may be said to have been initiated by Boole, De Morgan, and Jevons, but it was the publication in 1879 of Gottlob Frege's Begriffsschrift that opened a great epoch in the history of logic by presenting, in full-fledged form, the propositional calculus and quantification theory.Frege's book, translated in its entirety, begins the present volume. The emergence of two new fields, set theory and foundations of mathematics, on the borders of logic, mathematics, and philosophy, is depicted by the texts that follow. Peano and Dedekind illustrate the trend that led to Principia Mathematica. Burali-Forti, Cantor, Russell, Richard, and König mark the appearance of the modern paradoxes. Hilbert, Russell, and Zermelo show various ways of overcoming these paradoxes and initiate, respectively, proof theory, the theory of types, and axiomatic set theory. Skolem generalizes Löwenheim's theorem, and he and Fraenkel amend Zermelo's axiomatization of set theory, while von Neumann offers a somewhat different system. The controversy between Hubert and Brouwer during the twenties is presented in papers of theirs and in others by Weyl, Bernays, Ackermann, and Kolmogorov. The volume concludes with papers by Herbrand and by Gödel, including the latter's famous incompleteness paper.Of the forty-five contributions here collected all but five are presented in extenso. Those not originally written in English have been translated with exemplary care and exactness; the translators are themselves mathematical logicians as well as skilled interpreters of sometimes obscure texts. Each paper is introduced by a note that sets it in perspective, explains its importance, and points out difficulties in interpretation. Editorial comments and footnotes are interpolated where needed, and an extensive bibliography is included.

Investigations in proof theory: The properties of true propositions

JACQUES HERBRAND

(1930)

The present text is Chapter 5 of Herbrand’s thesis. The date given at the end of the thesis is 14 April 1929, but the defense at the Sorbonne did not take place until 11 June 1930 (in October 1929 Herbrand was drafted for a year of service in the French army). Herbrand was granted his doctorate in mathematics with highest honors. There is no indication that he introduced revisions into the text of the thesis between April 1929 and June 1930; a paper of his (1931), dated September 1929, contains emendations to the thesis, and this shows, it seems, that the text of the thesis remained unchanged after April 1929.

Chapter 5 of the thesis contains the statement of the now famous Herbrand theorem (fundamental theorem, p. 554 below) and an attempted proof of it. The section devoted to the theorem and its proof is preceded by a study of certain properties (A, B, and C) of provable formulas of quantification theory and followed by examples of applications of the theorem (to several cases of the decision problem and to the study of the consistency of various systems). The chapter is relatively self-contained, and the definitions, culled from the previous chapters of the thesis, that we give a few paragraphs below should provide the reader with the necessary background information.

Herbrand’s thesis bears the marks of hasty writing; this is especially true of Chapter 5. Some sentences are poorly constructed, and the punctuation is haphazard. Herbrand’s thoughts are not nebulous, but they are so hurriedly expressed that many a passage is ambiguous or obscure. To bring out the proper meaning of the text the translators had to depart from a literal rendering, and more rewriting has been allowed in this translation than in any other translation included in the present volume.

In 1939 Bernays remarked that “Herbrand’s proof is hard to follow” (Hilbert and Bernays 1939, footnote 1, p. 158), but he did not point out any specific difficulty. In the fall of 1963 Professor Gödel informed the editor that in the early forties he had discovered an essential gap in Herbrand’s argument, but he never published anything on the subject. In the spring of 1963 counterexamples to the lemma of 3.3 and to Lemma 3 of 5.3, lemmas upon which Herbrand’s proof of his fundamental theorem rests, had been published by Dreben, Andrews, and Aanderaa (1963). Dreben (1963) stated a substitute for the lemma of 3.3, and two notes (Dreben, Andrews, and Aanderaa 1963a and Dreben and Aanderaa 1964) outlined how Herbrand’s argument could be repaired; Dreben and...

Table of contents

• Cover
• Title
• Copyright
• Preface
• Contents
• Frege (1879). Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought
• Peano (1889). The principles of arithmetic, presented by a new method
• Dedekind (1890a). Letter to Keferstein
• Burali-Porti (1897 and 1897a). A question on transfinite numbers and On well-ordered classes
• Cantor (1899). Letter to Dedekind
• Padoa (1900). Logical introduction to any deductive theory
• Russell (1902). Letter to Frege
• Frege (1902). Letter to Russell
• Hilbert (1904). On the foundations of logic and arithmetic
• Zermelo (1904). Proof that every set can be well-ordered
• Richard (1905). The principles of mathematics and the problem of sets
• König (1905a). On the foundations of set theory and the continuum problem
• Russell (1908a). Mathematical logic as based on the theory of types
• Zermelo (1908). A new proof of the possibility of a well-ordering
• Zermelo (1908a). Investigations in the foundations of set theory I
• Whitehead and Russell (1910). Incomplete symbols: Descriptions
• Wiener (1914). A simplification of the logic of relations
• Löwenheim (1915). On possibilities in the calculus of relatives
• Skolem (1920). Logico-combinatorial investigations in the satisfiability or provability of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem
• Post (1921). Introduction to a general theory of elementary propositions
• Fraenkel (1922b). The notion “definite” and the independence of the axiom of choice
• Skolem (1922). Some remarks on axiomatized set theory
• Skolem (1923). The foundations of elementary arithmetic established by means of the recursive mode of thought, without the use of apparent variables ranging over infinite domains
• Brouwer (1923b, 1954, and 1954a). On the significance of the principle of excluded middle in mathematics, especially in function theory, Addenda and corrigenda, and Further addenda and corrigenda
• von Neumann (1923). On the introduction of transfinite numbers
• Schönfinkel (1924). On the building blocks of mathematical logic
• Hilbert (1925). On the infinite
• von Neumann (1925). An axiomatization of set theory
• Kolmogorov (1925). On the principle of excluded middle
• Finsler (1926). Formal proofs and undecidability
• Brouwer (1927). On the domains of definition of functions
• Hilbert (1927). The foundations of mathematics
• Weyl (1927). Comments on Hilbert’s second lecture on the foundations of mathematics
• Bernays (1927). Appendix to Hilbert’s lecture “The foundations of mathematics”
• Brouwer (1927a). Intuitionistic reflections on formalism
• Ackermann (1928). On Hilbert’s construction of the real numbers
• Skolem (1928). On mathematical logic
• Herbrand (1930). Investigations in proof theory: The properties of true propositions
• Gödel (1930a). The completeness of the axioms of the functional calculus of logic
• Gödel (1930b, 1931, and 1931a). Some metamathematical results on completeness and consistency, On formally undecidable propositions of Principia mathematica and related systems I, and On completeness and consistency
• Herbrand (1931b). On the consistency of arithmetic
• References
• Index