Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-22T20:43:22.341Z Has data issue: false hasContentIssue false
  • English
  • Français

The work of Kurt Gödel

Published online by Cambridge University Press:  12 March 2014

Stephen C. Kleene
Stephen C. Kleene*
Affiliation:
University of Wisconsin, Madison, Wisconsin 53706
Get access Rights & Permissions [Opens in a new window]

Extract

I first heard the name of Kurt Gödel when, as a graduate student at Princeton in the fall of 1931, I attended a colloquium at which John von Neumann was the speaker, von Neumann could have spoken on work of his own; but instead he gave an exposition of Gödel's results of formally undecidable propositions [1931].

Today I shall begin with Gödel's paper [1930] on The completeness of the axioms of the functional calculus of logic, or of what we now often call “the first-order predicate calculus”, using “predicate” as synonymous with “propositional function”.

Alonzo Church wrote ([1944, p. 62] and [1956, pp. 288–289]), “the first explicit formulation of the functional calculus of first order as an independent logistic system is perhaps in the first edition of Hilbert and Ackermann's Grundzüge der theoretischen Logik (1928).” Clearly, this formalism is not complete in the sense that each closed formula or its negation is provable. (A closed formula, or sentence, is a formula without free occurrences of variables.) But Hilbert and Ackermann observe, “Whether the system of axioms is complete at least in the sense that all the logical formulas which are correct for each domain of individuals can actually be derived from them is still an unsolved question.” [1928, p. 68].

This question Gödel answered in the affirmative in his Ph.D. thesis (Vienna, 1930), of which the paper under discussion is a rewritten version.

I shall not describe Gödel's proof. Perhaps no theorem in modern logic has been proved more often than Gödel's completeness theorem for the first-order predicate calculus. It stands at the focus of a complex of fundamental theorems, which different scholars have approached from various directions (e.g. Kleene [1967, Chapter VI]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 4 , December 1976 , pp. 761 - 778
Copyright
Copyright © Association for Symbolic Logic 1976

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

Ackermann, Wilhelm [1928] Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen, vol. 99, pp. 118–133.CrossRefGoogle Scholar
Bernays, Paul, [1940] Review of Gödel [1939], this Journal, vol. 5, pp. 117–118.CrossRefGoogle Scholar
Bernays, Paul, [1968] On the original Gentzen consistency proof for number theory, Intuitionism and proof theory, Proceedings of the Summer Conference at Buffalo, N. Y., 1968, North-Holland, Amsterdam and London, 1970, pp. 409–417.Google Scholar
Burali-Forti, Cesare, [1897] Una questione sui numeri transfiniti, Rendiconti del Circolo Matematico di Palermo, vol. 11, pp. 154–164.CrossRefGoogle Scholar
Cantor, Georg, [1874] Über eine Eigenschaft des Inbegriffes alter reellen algebraischen Zahlen, Journal für die reine und angewandte Mathematik, vol. 77, pp. 258–262.Google Scholar
Cantor, Georg, [1878] Ein Beitrag zur Mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik vol. 84, pp. 242–258.Google Scholar
Cantor, Georg, [1884] Über unendliche, lineare Punktmannigfaltigkeiten, Mathematische Annalen, vol. 23, pp. 453–488.CrossRefGoogle Scholar
Cantor, Georg [1890–1891] Über eine elementare Frage der Mannigfaltigkeitslehre, Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 1, pp. 75–78.Google Scholar
Cantor, Georg [1895–1897] Beiträge zur Begründung der transfiniten Mengenlehre, Mathematische Annalen, vol. 46 (1895), pp. 481–512 and vol. 49 (1897), pp. 207–246.CrossRefGoogle Scholar
Church, Alonzo, [1936] An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58, pp. 345–363.CrossRefGoogle Scholar
Church, Alonzo, [1944] Introduction to mathematical logic. Part I, Annals of Mathematics Studies, no. 13, Princeton University Press, Princeton, N.J.Google Scholar
Church, Alonzo, [1956] Introduction to mathematical logic, Vol. 1, Princeton University Press, Princeton, N.J.Google Scholar
Church, Alonzo, [1966] Paul J. Cohen and the continuum problem, Proceedings of the International Congress of Mathematicians, Moscow, August 16–26, 1966, Izdatél′stvo “MIR”, Moscow, 1968, pp. 15–20.Google Scholar
Cohen, Paul J. [1963–1964] The independence of the continuum hypothesis, and Proceedings of the International Congress of Mathematicians, Moscow, August 16–26, 1966, Izdatél′stvo “MIR”, Moscow, 1968, pp. 15–20 II. Proceedings of the National Academy of Sciences, vol. 50 (1963), pp. 1143–1148 and vol. 51 (1964), pp. 105–110.Google Scholar
Davis, Martin (editor) [1965] The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, Hewlitt, N.Y.Google Scholar
Dedekind, Richard, [1888] Was sind und was sollen die Zahlent Braunschweig, 6th. edition, 1930.Google Scholar
Fraenkel, Abraham A. [1922] Der Begriff “definit” und die Unabhängigkeit des Auswahlaxioms, Sitzungsberichte der Preussische Akademie der Wissenschaften, Physikalische-mathematische Klasse, 1922, pp. 253–257.Google Scholar
Gentzen, Gerhard [1936] Die Widerspruchsfreiheit der reinen Zahlentheorie, Mathematische Annalen, vol. 112, pp. 493–565.CrossRefGoogle Scholar
Gödel, Kurt [1930] Die Völlständigkeit der Axiome des logischen Funktionenkalküls, Monatshefte für Mathematik und Physik, vol. 37, pp. 349–360.CrossRefGoogle Scholar
Gödel, Kurt [1931] Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I, Monatshefte für Mathematik und Physik, vol. 38, pp. 173–198.CrossRefGoogle Scholar
Gödel, Kurt [1931–1912] Über Vollständigkeit und Widerspruchsfreiheit, Ergebnisse eines mathematischen Kolloquiums, Heft 3 (for 1930–1, published 1932), pp. 12–13.Google Scholar
Gödel, Kurt [1932] Zum intuitionistischen Aussagenkalkül, Akademie der Wissenschaften in Wien, Mathematisch-naturwissenschaftliche Klasse, Anzeiger, vol. 69, pp. 65–66.Google Scholar
Gödel, Kurt [1932–1933] Zur intuitionistischen Arithmetik und Zahlentheorie, Ergebnisse eines mathematischen Kolloquiums, Heft 4 (for 1931–3, published 1933), pp. 34–38.Google Scholar
Gödel, Kurt [1934] On undecidable propositions of formal mathematical systems, Notes by S. C. Kleene and Barkley Rosser on lectures at the Institute for Advanced Study, 1934, Princeton, N.J., 30 pp., Reprinted in Davis [1965].Google Scholar
Gödel, Kurt [1934a] Review of Skolem [1933], Zentralblatt für Mathematik und ihre Grenzgebiete, vol. 7, pp. 193–194.Google Scholar
Gödel, Kurt [1936] Über die Länge von Beweisen, Ergebnisse eines mathematischen Kolloquiums, Heft 7 (for 1934–5, published 1936), pp. 23–24.Google Scholar
Gödel, Kurt [1938] The consistency of the axiom of choice and of the generalized continuum -hypothesis, Proceedings of the National Academy of Sciences, vol. 24, pp. 556–557.CrossRefGoogle ScholarPubMed
Gödel, Kurt [1939] Consistency-proof for the generalized continuum-hypothesis, Proceedings of the National Academy of Sciences vol. 25, pp. 220–224.CrossRefGoogle ScholarPubMed
Gödel, Kurt [1940] The consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory, Notes by George W. Brown on lectures at the Institute for Advanced Study, autumn term 1938–9, Annals of Mathematics Studies, no. 3, Princeton University Press, Princeton, N.J., 66 pp. Reviewed (at the invitation of J. D. Tamarkin) by S. C. Kleene in Mathematical Reviews, vol. 2 (1941), pp. 66–67.Google Scholar
[1947]What is Cantor's continuum problem? American Mathematical Monthly, vol. 54, pp. 515–525.CrossRefGoogle Scholar
Gödel, Kurt [1958] Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, vol. 12, nos. 47/48, pp. 280–287.CrossRefGoogle Scholar
Henkin, Leon [1947] The completeness of formal systems, Ph.D. thesis, Princeton.Google Scholar
Henkin, Leon [1950] Completeness in the theory of types, this Journal, vol. 15, pp. 81–91.Google Scholar
Heyting, Arend [1934] Mathematische Grundlagenforschung, Intuitionismus, Beweistheorie, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 3, no. 4, Springer, Berlin.Google Scholar
Hilbert, David [1900] Mathematische Probleme, Vortrag, gehalten auf dem internationalen Mathematiker-Kongress zu Paris 1900, Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, pp. 253–297, French translation with emendations and additions, Compte rendu du Deuxième Congrès International des Mathématiciens tenu à Paris du 6 au 12 août 1900, Gauthier-Villars, Paris, 1902, pp. 58–114.Google Scholar
Hilbert, David [1904] Über die Grundlagen der Logik und der Arithmetik, Verhandlungen des Dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904, Teubner, Leipzig, 1905, pp. 174–185.Google Scholar
Hilbert, David [1925] Über das Unendliche, Address at Munster, 06 4, 1925 (Westphalian Mathematical Society), Mathematische Annaten, vol. 95 (1926), pp. 161–190.CrossRefGoogle Scholar
Hilbert, David [1927] Die Grundlagen der Mathematik, Address at Hamburg July 1927, Abhandlungen aus dem Mathematischen Seminar der Hamburgischen Universität, vol. 6 (1928), pp. 65–85.CrossRefGoogle Scholar
Hilbert, David and Ackermann, Wilhelm [1928] Grundzüge der theoretischen Logik, Springer, Berlin.Google Scholar
Hilbert, David and Bernays, Paul [1939] Grundlagen der Mathematik, vol. 2, Springer, Berlin.Google Scholar
Kleene, Stephen C. [1935] A theory of positive integers in formal logic, American Journal of Mathematics, vol. 57, pp. 153–173, 219–244.CrossRefGoogle Scholar
Kleene, Stephen C. [1936] General recursive functions of natural numbers, Mathematische Annalen, vol. 112, pp. 727–742.CrossRefGoogle Scholar
Kleene, Stephen C. [1936a] λ-definability and recursiveness, Duke Mathematical Journal, vol. 2, pp. 340–353.CrossRefGoogle Scholar
Kleene, Stephen C. [1943] Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53, pp. 41–73.CrossRefGoogle Scholar
Kleene, Stephen C. [1952] Introduction to metamathematics, North-Holland, Amsterdam, Noordhoff, Groningen, and Van Nostrand, Princeton, New York and Toronto, Seventh reprint, Wolters–Noordhoff, Groningen, North-Holland, Amsterdam-Oxford, American Elsevier, New York, 1974.Google Scholar
Kleene, Stephen C. [1959] Recursive functionals and quantifiers of finite types I, Transactions of the American Mathematical Society, vol. 91, pp. 1–52.Google Scholar
Kleene, Stephen C. [1967] Mathematical logic, John Wiley and Sons, New York, London, Sydney.Google Scholar
Löwenheim, Leopold [1915] Über Moglichkeiten im Relativkalkül, Mathematische Annalen, vol. 76, pp. 447–470.CrossRefGoogle Scholar
Markov, Andrei Andreeviˇ [1951] Theory of algorithms, Translations of the American Mathematical Society (2), vol. 15 (1960), pp. 1–14, Russian original, 1951.Google Scholar
Peano, Giusseppe [1889] Arithmetices principia, nova methodo exposita, Bocca, Turin.Google Scholar
Post, Emil Leon [1936] Finite combinatory processes—formulation I, this Journal, vol. 1, pp. 103–105.Google Scholar
Kleene, Stephen C. [1943] Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, vol. 65, pp. 197–215.Google Scholar
Rosser, Barkley [1936] Extensions of some theorems of Godel and Church, this Journal, vol. 1, pp. 87–91.Google Scholar
Sheperdson, J. C. and Sturgis, H. E. [1963] The computability of partial recursive functions, Journal of the Association for Computing Machinery, vol. 10, pp. 217–255.CrossRefGoogle Scholar
Skolem, Thoralf [1920] Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen, Skrifter utgit av Videns-kapsselskapet i Kristiana, I. Matematisk-naturvidenskabelig klasse 1920, no. 4, 36 pp.Google Scholar
Skolem, Thoralf [1922] Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre, Wissenschaftliche Vorträge gehalten auf dem Fünften Kongress der Skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922, Helsingfors, 1923, pp. 217–232.Google Scholar
Skolem, Thoralf [1923] Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbare Veränderlichen mit unendlichem Ausdehnungsbereich, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig klasse 1923, no. 6, 38 pp.Google Scholar
Skolem, Thoralf [1933] Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems, Norsk matematisk forenings skrifter, ser. 2, no. 10, pp. 73–82.Google Scholar
Skolem, Thoralf [1934] Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen, Fundamenta Mathematicae, vol. 23, pp. 150–161.CrossRefGoogle Scholar
Tarski, Alfred [1933] Der Wahrheitsbegriff in den formalisierten Sprachen, Studio Philosophica, vol. 1 (1936), pp. 261–405 (offprints dated 1935). Translated from Polish original 1933.Google Scholar
Tarski, Alfred [1956] Logic, semantics, metamathematics, papers from 1923 to 1938, Clarenden, Oxford.Google Scholar
Turing, Alan Mathison [1936–1937] On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser. 2, vol. 42, pp. 230–265.Google Scholar
Van Heijenoort, Jean (editor) [1967] From Frege to Gödel, a source book in mathematical logic, 1879–1931, Harvard University Press, Cambridge.Google Scholar
von Neumann, John [1923] Zur Einfuhrung der transfiniten Zahlen, Acta litterarum ac scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio scientiarum mathematicarum, vol. 1, pp. 199–208.Google Scholar
Weyl, Hermann [1910] Über die Definitionen der mathematischen Grundbegriffe, Mathematisch-naturwissenschaftliche Blätter, vol. 7, pp. 93–95, 109–113.Google Scholar
Weyl, Hermann [1918] Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis, Gruyter, Leipzig.CrossRefGoogle Scholar
Whitehead, Alfred North and Russell, Bertrand [1910–1913] Principia mathematica, Vol. 1, 1910, Vol. 2, 1912, Vol. 3, 1913, University Press, Cambridge, England.Google Scholar
Zermelo, Ernst [1904] Beweis, dassjede Menge wohlgeordnet werden kann, Mathematische Annalen, vol. 59, pp. 514–516.CrossRefGoogle Scholar
Zermelo, Ernst [1908] Neuer Beweiss für die Möglichkeit einer Wohlordnung, Mathematische Annalen vol. 65, pp. 107–128.CrossRefGoogle Scholar
Zermelo, Ernst [1908a] Untersuchungen uber die Grundlagen der Mengenlehre I, Mathematische Annalen, pp. 261–281.Google Scholar