Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-22T06:28:39.958Z Has data issue: false hasContentIssue false
  • English
  • Français

Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic

Published online by Cambridge University Press:  15 January 2014

Richard Zach
Richard Zach*
Affiliation:
Group in Logic and the Methodology of Science, University of California, Berkeley, Berkeley, CA 94720–3840, E-mail:[email protected], URL: http://www.math.berkeley.edu/~zach/
Get access Rights & Permissions [Opens in a new window]

Abstract

Some of the most important developments of symbolic logic took place in the 1920s. Foremost among them are the distinction between syntax and semantics and the formulation of questions of completeness and decidability of logical systems. David Hilbert and his students played a very important part in these developments. Their contributions can be traced to unpublished lecture notes and other manuscripts by Hilbert and Bernays dating to the period 1917–1923. The aim of this paper is to describe these results, focussing primarily on propositional logic, and to put them in their historical context. It is argued that truth-value semantics, syntactic (“Post-”) and semantic completeness, decidability, and other results were first obtained by Hilbert and Bernays in 1918, and that Bernays's role in their discovery and the subsequent development of mathematical logic is much greater than has so far been acknowledged.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 5 , Issue 3 , September 1999 , pp. 331 - 366
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Abrusci, Vito Michele, David Hilbert's Vorlesungen on logic and the foundations of mathematics, Atti del convegno internazionale di storia della logica, le teorie delle modalità. 5–8 December 1987, San Gimignano (Bologna) (Corsi, Giovanna, Mangione, Corrado, and Mugnai, Massimo, editors), CLUEB, 1989, pp. 333–338.Google Scholar
[2] Ackermann, Wilhelm, Begründung des “tertium non datur” mittels der Hilbertschen Theorie der Widerspruchsfreiheit, Mathematische Annalen, vol. 93 (1925), pp. 1–36.CrossRefGoogle Scholar
[3] Behmann, Heinrich, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, Mathematische Annalen, vol. 86 (1922), pp. 163–229.CrossRefGoogle Scholar
[4] Behmann, Heinrich, Mathematische Logik, Universität Göttingen, Sommer-Semester 1922. Unpublished lecture notes. Behmann Nachlaß, Institut für Philosophie, Universität Erlangen.Google Scholar
[5] Bernays, Paul, Beiträge zur axiomatischen Behandlung des Logik-Kalküls, Habilitationsschrift, Universität Göttingen, 1918, Bernays Nachlaß, WHS, Bibliothek, ETH Zürich, Hs 973.192.Google Scholar
[6] Bernays, Paul, Axiomatische Untersuchungen des Aussagen-Kalkuls der “Principia Mathematica”, Mathematische Zeitschrift, vol. 25 (1926), pp. 305–20.CrossRefGoogle Scholar
[7] Bernays, Paul, Probleme der theoretischen Logik, Unterrichtsblätter für Mathematik und Naturwissenschaften, vol. 33 (1927), pp. 369–77.Google Scholar
[8] Bernays, Paul, Axiomatic set theory, North-Holland, Amsterdam, 1958.Google Scholar
[9] Bernays, Paul, A short biography., Sets and classes (Müller, Gert H., editor), North-Holland, Amsterdam, 1976, pp. xi–xiii.Google Scholar
[10] Bernays, Paul, Interviews with J.-P. Sydler and E. Clavadetscher, Bernays Nachlaß, WHS, ETH Zürich, T 1285, 1977.Google Scholar
[11] Bernays, Paul and Schönfinkel, Moses, Zum Entscheidungsproblem der mathematischen Logik, Mathematische Annalen, vol. 99 (1928), pp. 342–372.CrossRefGoogle Scholar
[12] Birkhoff, Garrett and Bennett, Mary Katherine, Hilbert's “Grundlagen der Geometrie”, Rendiconti del Circolo Matematico di Palermo, Serie II, vol. 36 (1987), pp. 343–389.CrossRefGoogle Scholar
[13] Bocheński, I. M., Formale Logik, Alber, Freiburg, 1956.Google Scholar
[14] Church, Alonzo, Introduction to mathematical logic, Princeton University Press, Princeton, N.J., 1956.Google Scholar
[15] Corcoran, John, Categoricity, History and Philosophy of Logic, vol. 1 (1980), pp. 187–207.CrossRefGoogle Scholar
[16] Corcoran, John, From categoricity to completeness, History and Philosophy of Logic, vol. 2 (1981), pp. 113–119.Google Scholar
[17] Davis, Martin, Emil L. Post: His life and work, Solvability, provability, definability: The collected works of Emil L. Post (Davis, Martin, editor), Birkhäuser, Boston, 1994, pp. xi–xxviii.Google Scholar
[18] Davis, Martin, American logic in the 1920s, this Bulletin, vol. 1 (1995), pp. 273–278.Google Scholar
[19] Došen, Kosta, A historical introduction to substructural logics, Substructural logics (Schröder-Heister, Peter and Došen, Kosta, editors), Oxford University Press, Oxford, 1993, pp. 1–30.Google Scholar
[20] Dreben, Burton and Heijenoort, Jean van, Introductory note to Gödel 1929, 1930, and 1930a, In Feferman, et al. [22], pp. 44–59.Google Scholar
[21] Ewald, William Bragg (editor), From Kant to Hilbert. A source book in the foundations of mathematics, vol. 2, Oxford University Press, Oxford, 1996.Google Scholar
[22] Feferman, Solomon et al.(editors), Kurt Gödel. Collected works, vol. 1, Oxford University Press, Oxford, 1986.Google Scholar
[23] Gentzen, Gerhard, Untersuchungen über das logische Schließen I–II, Mathematische Zeitschrift, vol. 39 (1934), pp. 176–210, 405–431.CrossRefGoogle Scholar
[24] Gentzen, Gerhard, The collected papers of Gerhard Gentzen, North-Holland, Amsterdam, 1969.Google Scholar
[25] Gödel, Kurt, Über die Vollständigkeit des Logikkalküls, Dissertation, Universität Wien, 1929, Reprinted and translated in [22], pp. 60–101.Google Scholar
[26] Gödel, Kurt, Zum intuitionistischen Aussagenkalkül, Anzeiger der Akademie der Wissenschaften in Wien, vol. 69 (1932), pp. 65–66, Reprinted and translated in [22], pp. 222–225.Google Scholar
[27] Heyting, Arend, Die formalen Regeln der intuitionistischen Logik, Sitzungsberichte der Preussischen Akademie der Wissenschaften (1930), pp. 42–56, Translated in [56], pp. 311–334.Google Scholar
[28] Hilbert, David, Mathematische Probleme, Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Math.-Phys. Klasse (1900), pp. 253–297, Lecture given at the International Congress of Mathematicians, Paris, 1900.Google Scholar
[29] Hilbert, David, Über den Zahlbegriff, Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 8 (1900), pp. 180–84.Google Scholar
[30] Hilbert, David, Grundlagen der Geometrie, 2nd ed., Teubner, Leipzig, 1903.Google Scholar
[31] Hilbert, David, Logische Principien des mathematischen Denkens, Vorlesung, Sommer-Semester 1905. Lecture notes by Ernst Hellinger. Unpublished manuscript. Bibliothek, Mathematisches Institut, Universität Göttingen.Google Scholar
[32] Hilbert, David, Über die Grundlagen der Logik und der Arithmetik, Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904 (Leipzig) (Krazer, A., editor), Teubner, 1905, English translation in [73], pp. 129–38, pp. 174–85.Google Scholar
[33] Hilbert, David, Prinzipien der Mathematik, Lecture notes by Paul Bernays. Winter-Semester 1917–1918. Unpublished typescript. Bibliothek, Mathematisches Institut, Universität Göttingen.Google Scholar
[34] Hilbert, David, Axiomatisches Denken, Mathematische Annalen, vol. 78 (1918), pp. 405–15, Lecture given at the Swiss Society of Mathematicians, 11 09 1917. Reprinted in [42], pp. 146–56. English translation in [21], pp. 1105–1115.CrossRefGoogle Scholar
[35] Hilbert, David, Logik-Kalkül, Vorlesung, Winter-Semester 1920. Lecture notes by Paul Bernays. Unpublished typescript. Bibliothek, Mathematisches Institut, Universität Göttingen.Google Scholar
[36] Hilbert, David, Grundlagen der Mathematik, Vorlesung, Winter-Semester 1921–1922. Lecture notes by Paul Bernays. Unpublished typescript. Bibliothek, Mathematisches Institut, Universität Göttingen.Google Scholar
[37] Hilbert, David, Neubegründung der Mathematik: Erste Mitteilung, Abhandlungen aus dem Seminar der Hamburgischen Universität, vol. 1 (1922), pp. 157–77, Reprinted with notes by Bernays in [42], pp. 157–177. English translation in [21], pp. 1115–1134.Google Scholar
[38] Hilbert, David, Die logischen Grundlagen der Mathematik, Mathematische Annalen, vol. 88 (1923), pp. 151–165, Lecture given at the Deutsche Naturforscher-Gesellschaft, 09 1922. Reprinted in [42], pp. 178–191. English translation in [21], pp. 1134–1148.Google Scholar
[39] Hilbert, David, Die Grundlagen der Mathematik, Abhandlungen aus dem Seminar der Hamburgischen Universität, vol. 6 (1928), pp. 65–85, English translation in [73], pp. 464–479.Google Scholar
[40] Hilbert, David, Probleme der Grundlegung der Mathematik, Atti del congresso internazionale dei matematici. 3–10 September 1928, Bologna (Zanichelli, Nicola, editor), 1928, pp. 135–141.Google Scholar
[41] Hilbert, David, Probleme der Grundlegung der Mathematik, Mathematische Annalen, vol. 102 (1929), pp. 1–9, Lecture given at the International Congress of Mathematicians, 3 09 1928. English translation in [56], pp. 266–73.Google Scholar
[42] Hilbert, David, Gesammelte Abhandlungen, vol. 3, Springer, Berlin, 1935.Google Scholar
[43] Hilbert, David and Ackermann, Wilhelm, Grundzüge der theoretischen Logik, Springer, Berlin, 1928.Google Scholar
[44] Hilbert, David and Bernays, Paul, Logische Grundlagen der Mathematik, Winter-Semester 1922–1923. Lecture notes by Helmut Kneser. Unpublished manuscript.Google Scholar
[45] Hilbert, David and Bernays, Paul, Logische Grundlagen der Mathematik, Vorlesung, Winter-Semester 1922–1923. Lecture notes by Paul Bernays, with handwritten notes by Hilbert. Hilbert-Nachlaß, Niedersächsische Staats- und Universitätsbibliothek, Cod. Ms. Hilbert 567, 1922–1923.Google Scholar
[46] Hilbert, David and Bernays, Paul, Grundlagen der Mathematik, vol. 1, Springer, Berlin, 1934.Google Scholar
[47] Hilbert, David and Bernays, Paul, Grundlagen der Mathematik, vol. 2, Springer, Berlin, 1939.Google Scholar
[48] Huntington, Edward V., The inter-deducibility of the new Hilbert-Bernays theory and Principia Mathematica, Annals of Mathematics, vol. 36 (1935), pp. 313–324.CrossRefGoogle Scholar
[49] Jørgensen, Jørgen, A treatise of formal logic, Levin & Munksgaard, Copenhagen, 1931.Google Scholar
[50] Kneale, William and Kneale, Martha, The development of logic, Oxford University Press, Oxford, 1962.Google Scholar
[51] König, Julius, Neue Grundlagen der Logik, Arithmetik und Mengenlehre, Veit, 1914.CrossRefGoogle Scholar
[52] Lauener, Henri, Paul Bernays (1888–1977), Zeitschrift für allgemeine Wissenschaftstheorie, vol. 9 (1978), pp. 13–20.CrossRefGoogle Scholar
[53] Lewis, C. I., A survey of symbolic logic, University of California Press, Berkeley, 1918.CrossRefGoogle Scholar
[54] Łukasiewicz, Jan, Démonstration de la compatibilité des axiomes de la théorie de la déduction (Abstract), Annales de la Société Polonaise de Mathématique, vol. 3 (1924), p. 149, Talk given 13 06 1924.Google Scholar
[55] Majer, Ulrich, Husserl and Hilbert on completeness, Synthese, vol. 110 (1997), pp. 37–56.CrossRefGoogle Scholar
[56] Mancosu, Paolo (editor), From Brouwer to Hilbert. The debate on the foundations of mathematics in the 1920s, Oxford University Press, Oxford, 1998.Google Scholar
[57] Mancosu, Paolo (editor), Hilbert and Bernays on metamathematics, In From Brouwer to Hilbert [56], pp. 149–188.Google Scholar
[58] Mancosu, Paolo (editor), Between Russell and Hilbert: Behmann on the foundations of mathematics, this Bulletin, vol. 5 (1999), no. 3 (this issue), pp. 303–330.Google Scholar
[59] Mollerup, Johannes, Die Definition des Mengenbegriffs, Mathematische Annalen, vol. 64 (1907), pp. 231–238.CrossRefGoogle Scholar
[60] Moore, Gregory H., Hilbert and the emergence of modern mathematical logic, Theoria (Segunda Época), vol. 12 (1997), pp. 65–90.Google Scholar
[61] O'Leary, Daniel J., The propositional logic of Principia Mathematica and some of its forerunners, Russell, vol. 8 (1988), pp. 92–115.CrossRefGoogle Scholar
[62] Peckhaus, Volker, Hilbertprogramm und Kritische Philosophie, Vandenhoeck und Ruprecht, Göttingen, 1990.Google Scholar
[63] Peckhaus, Volker, Logic in transition: The logical calculi of Hilbert (1905) and Zermelo (1908), Logic and philosophy of science in uppsala (Prawitz, Dag and Westerståhl, Dag, editors), Kluwer, Dordrecht, 1994, pp. 311–323.CrossRefGoogle Scholar
[64] Peckhaus, Volker, Hilberts Logik: Von der Axiomatik zur Beweistheorie, Internationale Zeitschrift für Geschichte und Ethik der Naturwissenschaften, Technik und Medizin, vol. 3 (1995), pp. 65–86.Google Scholar
[65] Post, Emil L., Introduction to a general theory of elementary propositions, American Journal of Mathematics, vol. 43 (1921), pp. 163–185.CrossRefGoogle Scholar
[66] Reid, Constance, Hilbert, Springer, New York, 1970.CrossRefGoogle Scholar
[67] Russell, Bertrand, The theory of implication, American Journal of Mathematics, vol. 28 (1906), pp. 159–202.CrossRefGoogle Scholar
[68] Schröder, Ernst, Vorlesungen über die Algebra der Logik, vol. 1, Teubner, Leipzig, 1890.Google Scholar
[69] Sieg, Wilfried, Hilbert's programs: 1917–1922, this Bulletin, vol. 5 (1999), no. 1, pp. 1–44.Google Scholar
[70] Specker, Ernst, Paul Bernays, Logic colloquium '78 (Boffa, M., Dalen, D. van, and McAloon, K., editors), North-Holland, Amsterdam, 1979, pp. 381–89.Google Scholar
[71] Surma, Stansław J., A historical survey of the significant methods of proving Post's theorem about the completeness of the classical propositional calculus, Studies in the history of mathematical logic (Surma, Stanisław J., editor), Polish Academy of Sciences, Institute of Philosophy and Sociology, Wrocław, 1973, pp. 19–32.Google Scholar
[72] Toepell, Michael-Markus, Über die Entstehung von Hilbert's “Grundlagen der Geometrie”, Vandenhoek und Ruprecht, Göttingen, 1986.Google Scholar
[73] Heijenoort, Jean van (editor), From Frege to Gödel. A source book in mathematical logic, 1897–1931, Harvard University Press, Cambridge, Mass., 1967.Google Scholar
[74] Whitehead, Alfred North and Russell, Bertrand, Principia mathematica, vol. 1, Cambridge University Press, Cambridge, 1910.Google Scholar