Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-05T09:21:35.880Z Has data issue: false hasContentIssue false

On Formalism Freeness: Implementing Gödel's 1946 Princeton Bicentennial Lecture

Published online by Cambridge University Press:  05 September 2014

Juliette Kennedy*
Affiliation:
Department of Mathematics and Statistics, P.O. Box 68 (Gustaf Hällströmin Katu 2B), FI-00014, University of Helsinki, Finland, E-mail: [email protected]

Abstract

In this paper we isolate a notion that we call “formalism freeness” from Gödel's 1946 Princeton Bicentennial Lecture, which asks for a transfer of the Turing analysis of computability to the cases of definability and provability. We suggest an implementation of Gödel's idea in the case of definability, via versions of the constructible hierarchy based on fragments of second order logic. We also trace the notion of formalism freeness in the very wide context of developments in mathematical logic in the 20th century.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2013

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] Adler, Hans, Thorn-forking as local forking, Journal of Mathematical Logic, vol. 9 (2009), no. 1, pp. 2138.Google Scholar
[2] Arana, Andrew and Mancosu, Paolo, On the relationship between plane and solid geometry, Review of Symbolic Logic, vol. 5 (2012), no. 2, pp. 294353.CrossRefGoogle Scholar
[3] Baldwin, John T., Formalization, primitive concepts, and purity, The Review of Symbolic Logic, vol. 6 (2013), no. 2, pp. 87128.CrossRefGoogle Scholar
[4] Baldwin, John T., Completeness and categoricity (in power): Formalization without foundationalism, preprint.Google Scholar
[5] Baldwin, John T., Hyttinen, Tapani, and Kesää, Meeri, Beyond first order logic: From number of structures to structure of numbers part I, Bulletin of the Iranian Mathematical Society, vol. 39 (2013), no. 1, pp. 126.Google Scholar
[6] Baldwin, John T., Beyond first order logic: From number of structures to structure of numbers part II, Bulletin of the Iranian Mathematical Society, vol. 39 (2013), no. 1, pp. 2748.Google Scholar
[7] Barwise, Jon, Absolute logics and L∞ω , Annals of Mathematical Logic, vol. 4 (1972), pp. 309340.CrossRefGoogle Scholar
[8] Barwise, Jon, Axioms for abstractmodel theory, Annals of Mathematical Logic, vol. 7 (1974), pp. 221265.CrossRefGoogle Scholar
[9] Barwise, Jon, Kaufmann, Matt, and Makkai, Michael, Stationary logic, Annals of Mathematical Logic, vol. 13 (1978), no. 2, pp. 171224.Google Scholar
[10] Bishop, Errett, Foundations of constructive analysis, McGraw-Hill Book Co., 1967.Google Scholar
[11] Bourbaki, Nicholas, The architecture of mathematics, The American Mathematical Monthly, vol. 57 (1950), pp. 221232.CrossRefGoogle Scholar
[12] Brouwer, L. E. J., Brouwer's Cambridge lectures on intuitionism, Cambridge University Press, Cambridge, 1981, edited by van Dalen, D..Google Scholar
[13] Burgess, John, Putting structuralismin its place, retrieved from www.princeton.edu/~jburgess/anecdota.htm, 2009.Google Scholar
[14] Buss, Samuel R., Kechris, Alexander S., Pillay, Anand, and Shore, Richard A., The prospects for mathematical logic in the twenty-first century, this Bulletin, vol. 7 (2001), no. 2, pp. 169196.Google Scholar
[15] Davis, Martin, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., 1958.Google Scholar
[16] Davis, Martin (editor), The undecidable, Dover Publications Inc., Mineola, NY, 2004, corrected reprint of the 1965 original [Raven Press, Hewlett, NY].Google Scholar
[17] Detlefsen, Michael, Poincaré vs. Russell on the rôle of logic in mathematics, Philosophia Mathematica. Series III , vol. 1 (1993), no. 1, pp. 2449.CrossRefGoogle Scholar
[18] Detlefsen, Michael, What does Gödel's second theorem say?, Philosophia Mathematica. Series III , vol. 9 (2001), no. 1, pp. 3771, The George Boolos Memorial Symposium, II.Google Scholar
[19] Detlefsen, Michael and Arana, Andrew, Purity of methods, Philosophers' Imprint, vol. 11 (2011), no. 2, pp. 120.Google Scholar
[20] Dickmann, M. A., Large infinitary languages, Studies in Logic and the Foundations of Mathematics, vol. 83, North-Holland, 1975.Google Scholar
[21] Ebbinghaus, H.-D., Extended logics: the general framework, Model-theoretic logics, Perspectives in Mathematical Logic, Springer, 1985, pp. 2576.Google Scholar
[22] Fagin, Ronald, Probabilities on finite models, The Journal of Symbolic Logic, vol. 41 (1976), no. 1, pp. 5058.Google Scholar
[23] Feferman, Solomon, Arithmetization of metamathematics in a general setting, Polska Akademia Nauk. Fundamenta Mathematicae, vol. 49 (1960/1961), pp. 3592.Google Scholar
[24] Floyd, Juliet, The varieties of rigorous experience, The Oxford handbook of the history of analytic philosophy (Beaney, M., editor), Oxford Handbooks in Philosophy, Oxford University Press, Oxford, 2013.Google Scholar
[25] Fraenkel, Abraham A. and Bar-Hillel, Yehoshua, Foundations of set theory, Studies in Logic and the Foundations of Mathematics, North-Holland, 1958.Google Scholar
[26] Franks, Curtis, The autonomy of mathematical knowledge, Cambridge University Press, Cambridge, 2009.Google Scholar
[27] Franks, Curtis, Logical completeness, form, and content: an archaeology, Interpreting Gödel (Kennedy, J., editor), Cambridge University Press, Cambridge, to appear.Google Scholar
[28] Gandy, Robin, The confluence of ideas in 1936, The universal Turing machine: a half-century survey, Oxford Science Publications, Oxford University Press, 1988, pp. 55111.Google Scholar
[29] Gödel, Kurt, Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatshefte für die Mathematik, vol. 37 (1930), pp. 349360.CrossRefGoogle Scholar
[30] Gödel, Kurt, The Consistency of the Continuum Hypothesis, Annals of Mathematics Studies, no. 3, Princeton University Press, Princeton, NJ, 1940.Google Scholar
[31] Gödel, Kurt, Remarks before the Princeton bicentennial conference of problems in mathematics, 1946, reprinted in Collected Works. II, (Feferman, S. et al., editors), Oxford University Press, Oxford, 1990.Google Scholar
[32] Gödel, Kurt, What is Cantor's continuum problem?, The American Mathematical Monthly, vol. 54 (1947), pp. 515525.Google Scholar
[33] Gödel, Kurt, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, vol. 12 (1958), pp. 280287.CrossRefGoogle Scholar
[34] Gödel, Kurt, Collected Works. I: Publications 1929–1936, (Feferman, S. et al., editors), Oxford University Press, Oxford, 1986.Google Scholar
[35] Gödel, Kurt, Collected Works. II: Publications 1938–1974, (Feferman, S. et al., editors), Oxford University Press, Oxford, 1990.Google Scholar
[36] Gödel, Kurt, Collected Works. III: Unpublished essays and lectures, (Feferman, S. et al., editors), Oxford University Press, Oxford, 1995.Google Scholar
[37] Gödel, Kurt, Collected Works. IV: Correspondence A–G, (Feferman, S. et al., editors), Oxford University Press, Oxford, 2003.Google Scholar
[38] Gödel, Kurt, Collected Works. V: Correspondence H–Z, (Feferman, S. et al., editors), Oxford University Press, Oxford, 2003.Google Scholar
[39] Heyting, A., Intuitionism: An introduction, second revised ed., North-Holland, 1966.Google Scholar
[40] Hilbert, David, Grundlagen der Geometrie, fourteenth ed., Teubner-Archiv zur Mathematik. Supplement, vol. 6, 1999.Google Scholar
[41] Hodges, Wilfrid, What is a structure theory?, Bulletin of the London Mathematical Society, vol. 19 (1987), pp. 209237.Google Scholar
[42] Hrushovski, Ehud and Zilber, Boris, Zariski geometries, Journal of the American Mathematical Society, vol. 9 (1996), no. 1, pp. 156.CrossRefGoogle Scholar
[43] Hyttinen, Tapani and Tuuri, Heikki, Constructing strongly equivalent nonisomorphic models for unstable theories, Annals of Pure and Applied Logic, vol. 52 (1991), no. 3, pp. 203248.Google Scholar
[44] Kanamori, Akihiro, The higher infinite, second ed., Springer Monographs in Mathematics, Springer, 2009.Google Scholar
[45] Kaufmann, Matt, Set theory with a filter quantifier, The Journal of Symbolic Logic, vol. 48 (1983), no. 2, pp. 263287.Google Scholar
[46] Kazhdan, D., Lecture notes in motivic integration, available online at www.ma.huji.ac.il/~kazhdan/.Google Scholar
[47] Keisler, H. Jerome, Logic with the quantifier “there exist uncountably many”, Annals of Pure and Applied Logic, vol. 1 (1970), pp. 193.Google Scholar
[48] Kennedy, Juliette, On embedding models of arithmetic into reduced powers, Matemática Contemporânea, vol. 24 (2003), pp. 91115, 8thWorkshop on Logic, Language, Informations and Computation—WoLLIC'2001.Google Scholar
[49] Kennedy, Juliette, Gödel's thesis: An appreciation, Kurt Gödel and the foundations of mathematics (Baaz, M. et al., editors), Cambridge University Press, Cambridge, 2011, pp. 95109.Google Scholar
[50] Kennedy, Juliette, Magidor, Menachem, and Väänänen, Jouko, Inner models from extended logics, preprint.Google Scholar
[51] Kleene, S. C., Recursive functionals and quantifiers of finite types. I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 152.Google Scholar
[52] Koepke, Peter and Siders, Ryan, Register computations on ordinals, Archive for Mathematical Logic, vol. 47 (2008), no. 6, pp. 529548.Google Scholar
[53] Kreisel, G., Informal rigour and completeness proofs, Proceedings of the International Colloquium in the Philosophy of Science (Lakatos, Imre, editor), vol. 1, North-Holland, 1967, pp. 138157.Google Scholar
[54] Kreisel, G., Which number theoretic problems can be solved in recursive progressions on Π1 1-paths through O?, The Journal of Symbolic Logic, vol. 37 (1972), pp. 311334.Google Scholar
[55] Kueker, David W., Abstract elementary classes and infinitary logics, Annals of Pure and Applied Logic, vol. 156 (2008), no. 2–3, pp. 274286.Google Scholar
[56] Lindström, Per, On extensions of elementary logic, Theoria, vol. 35 (1969), pp. 111.Google Scholar
[57] López-Escobar, E. G. K., Introduction, Infinitary logic: in memoriam Carol Karp, Lecture Notes in Mathematics, vol. 492, Springer, Berlin, 1975, pp. 116.Google Scholar
[58] Luzin, N., Sur les ensembles projectifs de M. Henri Lebesgue, Comptes Rendus de l'Académie des Sciences. Paris, vol. 180 (1925), no. 2, pp. 15721574.Google Scholar
[59] Macintyre, Angus, Ramsey quantifiers in arithmetic, Model theory of algebra and arithmetic, Lecture Notes in Mathematics, vol. 834, Springer, Berlin, 1980, pp. 186210.Google Scholar
[60] Maddy, Penelope, Some naturalistic reflections on set theoretic method, Topoi. An International Review of Philosophy, vol. 20 (2001), no. 1, pp. 1727.Google Scholar
[61] Maddy, Penelope, Second philosophy, Oxford University Press, Oxford, 2009.Google Scholar
[62] Maddy, Penelope, Defending the axioms: on the philosophical foundations of set theory, Oxford University Press, Oxford, 2011.Google Scholar
[63] Mancosu, P., From Brouwer to Hilbert, Oxford University Press, Oxford, 1998.Google Scholar
[64] McAloon, Kenneth, Consistency results about ordinal definability, Annals of Pure and Applied Logic, vol. 2 (1970/1971), no. 4, pp. 449467.Google Scholar
[65] McLarty, Colin, Poincaré: mathematics & logic & intuition, Philosophia Mathematica. Series III , vol. 5 (1997), no. 2, pp. 97115.CrossRefGoogle Scholar
[66] Myhill, John and Scott, Dana, Ordinal definability, Axiomatic Set Theory, American Mathematical Society, Providence, RI, 1971, pp. 271278.Google Scholar
[67] Noë, Alva, Varieties of presence, Harvard University Press, 2012.Google Scholar
[68] Parsons, Charles, Some consequences of the entanglement of logic and mathematics, Reference, rationality, and phenomenology: Themes from Follesdal (Frauchiger, Michael, editor), Lauener Library of Analytical Philosophy, vol. 2, Ontos Verlag, Frankfurt, 2013, pp. 153178.Google Scholar
[69] Pillay, Anand and Steinhorn, Charles, Definable sets in ordered structures, Bulletin of the American Mathematical Society. New Series , vol. 11 (1984), no. 1, pp. 159162.Google Scholar
[70] Quine, W. V., Philosophy of logic, second ed., Harvard University Press, Cambridge, MA, 1986.Google Scholar
[71] Robinson, Abraham, On the metamathematics of algebra, Studies in Logic and the Foundations of Mathematics, North-Holland, 1951.Google Scholar
[72] Schmerl, James H. and Simpson, Stephen G., On the role of Ramsey quantifiers in first order arithmetic, The Journal of Symbolic Logic, vol. 47 (1982), no. 2, pp. 423435.CrossRefGoogle Scholar
[73] Scott, Dana, On constructing models for arithmetic, Infinitistic Methods, Pergamon, Oxford, 1961, pp. 235255.Google Scholar
[74] Shapiro, Stewart (editor), The Oxford handbook of philosophy of mathematics and logic, Oxford Handbooks in Philosophy, Oxford University Press, Oxford, 2005.Google Scholar
[75] Shelah, Saharon, Classification Theory for Abstract Elementary Classes, Studies in Logic: Mathematical logic and foundations, vol. 18, College Publications, 2009.Google Scholar
[76] Shelah, Saharon, Classification Theory for Abstract Elementary Classes 2, Studies in Logic: Mathematical Logic and Foundations, vol. 20, College Publications, 2009.Google Scholar
[77] Shelah, Saharon, Nice infinitary logics, Journal of the American Mathematical Society, vol. 25 (2012), no. 2, pp. 395427.Google Scholar
[78] Sieg, Wilfried, Gödel on computability, Philosophia Mathematica. Series III , vol. 14 (2006), pp. 189207.Google Scholar
[79] Tait, W. W., Remarks on finitism, Reflections on the foundations of mathematics, Lecture Notes in Logic, vol. 15, Association for Symbolic Logic, Urbana, IL, 2002, pp. 410419.Google Scholar
[80] Väänänen, Jouko, Second-order logic and foundations of mathematics, this Bulletin, vol. 7 (2001), no. 4, pp. 504520.Google Scholar
[81] Väänänen, Jouko, Second-order logic or set theory?, this Bulletin, vol. 18 (2012), no. 1, pp. 91121.Google Scholar
[82] van Atten, Mark and Kennedy, Juliette, Gödel's modernism: On set-theoretic incompleteness, revisited, Logicism, intuitionism, and formalism, what has become of them? (Lindstrom, S., Palmgren, E., Segerberg, K., and Stoltenberg-Hansen, V., editors), Synthese Library, vol. 341, Springer, 2009, pp. 303355.Google Scholar
[83] van den Dries, Lou, A generalization of the Tarski–Seidenberg theorem, and some nondefinability results, Bulletin of the American Mathematical Society. New Series , vol. 15 (1986), no. 2, pp. 189193.Google Scholar
[84] Vopenka, P., Balcar, B., and Hajek, P., The notion of effective sets and a new proof of the consistency of the axiom of choice (abstract), The Journal of Symbolic Logic, vol. 33 (1968), pp. 495496.Google Scholar
[85] Wang, Hao, A logical journey, Representation and Mind, MIT Press, Cambridge, MA, 1996.Google Scholar
[86] Woodin, W. Hugh, Supercompact cardinals, sets of reals, and weakly homogeneous trees, Proceedings of the National Academy of Sciences of the United States of America, vol. 85 (1988), no. 18, pp. 65876591.Google Scholar
[87] Woodin, W. Hugh, The axiomof determinacy, forcing axioms, and the nonstationary ideal, revised ed., de Gruyter Series in Logic and its Applications, vol. 1, Walter de Gruyter, Berlin, 2010.Google Scholar
[88] Zilber, Boris, A categoricity theorem for quasi-minimal excellent classes, Logic and its applications, Contemporary Mathematics, vol. 380, American Mathematical Society, Providence, RI, 2005, pp. 297306.Google Scholar