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

The Prospects for Mathematical Logic in the Twenty-First Century

Published online by Cambridge University Press:  15 January 2014

Samuel R. Buss ,
Alexander S. Kechris ,
Anand Pillay  and
Richard A. Shore
Samuel R. Buss
Affiliation:
Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USAE-mail:[email protected]
Alexander S. Kechris
Affiliation:
Department of Mathematics, California Institute of Technology, Pasadena, CA 91125, USAE-mail:[email protected]
Anand Pillay
Affiliation:
Department of Mathematics, University of Illinois, Urbana-Champaign, IL 61801, USAE-mail:[email protected]
Richard A. Shore
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY 14853, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 7 , Issue 2 , June 2001 , pp. 169 - 196
Copyright
Copyright © Association for Symbolic Logic 2001

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] Becker, H. and Kechris, A. S., The descriptive set theory of Polish group actions, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, 1996.CrossRefGoogle Scholar
[2] Blum, L., Cucker, F., Shub, M., and Smale, S., Complexity and real computation, Springer-Verlag, Berlin, 1997.Google Scholar
[3] Blum, L., Shub, M., and Smale, S., On a theory of computation and complexity over the real numbers: NP- completeness, recursive functions and universal machines, Bulletin of the American Mathematical Society, vol. 21 (1999), no. NS, pp. 1–46.CrossRefGoogle Scholar
[4] Camerlo, R. and Gao, S., The completeness of the isomorphism relation of countable Boolean algebras, Transactions of the American Mathematical Society, vol. 353 (2001), pp. 491–518.CrossRefGoogle Scholar
[5] Cherlin, G. and Hrushovski, E., Finite structures with few types, preprint, 2000.Google Scholar
[6] Cholak, P., Lempp, S., Lerman, M., and Shore, R. A., Computability theory and its applications: Current trends and open problems, Contemporary Mathematics, vol. 257, American Mathematical Society, 2000.CrossRefGoogle Scholar
[7] Chong, C. T., Positive reducibility of the interior of filled Julia sets, Journal of Complexity, vol. 10 (1994), pp. 437–444.CrossRefGoogle Scholar
[8] Chong, C. T., The polynomial topological complexity of Fatou-Julia sets, Advances in Computational Mathematics, vol. 3 (1995), pp. 369–374.CrossRefGoogle Scholar
[9] Cooper, S. B., The jump is definable in the structure of the degrees of unsolvability (research announcement), Bulletin of the American Mathematical Society, vol. 23 (1990), no. NS, pp. 151–158.CrossRefGoogle Scholar
[10] Cooper, S. B., On a conjecture of Kleene and Post, Department of Pure Mathematics, Leeds University, 1993 Preprint Series No. 7, 1993.Google Scholar
[11] Cooper, S. B., The Turing definability of the relation of “computably enumerable in”, Computability Theory Seminar, University of Leeds: http://www.amsta.leeds.ac.uk/pure/staff/cooper/preprints.html, 2000.Google Scholar
[12] Dales, H. G. and Woodin, W. H., An introduction to independence for analysts, London Mathematical Society Lecture Note Series, vol. 115, Cambridge University Press, 1987.CrossRefGoogle Scholar
[13] Dehornoy, P., Braids and self distributivity, to appear in Progress in Mathematics, Birkhäuser, Basel.Google Scholar
[14] Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society, vol. A 400 (1985), pp. 97–117.Google Scholar
[15] Deutsch, D., Ekert, A., and Lupacchini, R., Machines, logic and quantum physics, this Bulletin, vol. 6 (2000), pp. 265–283.Google Scholar
[16] Ershov, Y. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W. (editors), Handbook of recursive mathematics, studies in logic and the foundations of mathematics, vol. I & II, Elsevier, Amsterdam, 1998.Google Scholar
[17] Feferman, S., Proof theory on the eve of the year 2000, 1999, available from http://www-logic.stanford.edu/proofsurvey.html. Responses to a survey on proof theory.Google Scholar
[18] Foreman, M., Kanamori, A., and Magidor, M., Handbook of set theory, to appear Kluwer, Dordrecht.Google Scholar
[19] Foreman, M., Kechris, A. S., Louveau, A., and Weiss, B. (editors), Descriptive set theory and dynamical systems, London Mathematical Society Lecture Note Series, vol. 277, Cambridge University Press, 2000.CrossRefGoogle Scholar
[20] Foreman, M., Magidor, M., and Shelah, S., Martin's maximum, saturated ideals and non-regular ultrafilters, parts I and II, Annals of Mathematics, vol. 127 (1988), pp. 1–47, 521–545.CrossRefGoogle Scholar
[21] Friedman, H., Finite functions and the necessary use of large cardinals, Annals of Mathematics, vol. 148 (1998), no. 3, pp. 803–893.CrossRefGoogle Scholar
[22] Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures, The Journal of Symbolic Logic, vol. 54 (1989), pp. 894–914.CrossRefGoogle Scholar
[23] Gandy, R., Church's thesis and principles for mechanisms, The Kleene symposium (Barwise, J. et al., editors), North-Holland, Amsterdam, 1980, pp. 123–148.CrossRefGoogle Scholar
[24] Groszek, M. J. and Slaman, T. A., A basis theorem for perfect sets, this Bulletin, vol. 4 (1999), pp. 204–209.Google Scholar
[25] Halpern, J. Y., Harper, R., Kolaitis, P. G., Vardi, M. Y., and Vianu, V., On the unusual effectiveness of logic in computer science, this Bulletin, vol. 6 (2000), pp. 265–283.Google Scholar
[26] Hirschfeldt, D., Khoussainov, B., Shore, R. A., and Slinko, A., Degree spectra and computable dimension in algebraic structures, to appear in Annals of Pure and Applied Logic.Google Scholar
[27] Hjorth, G., Around nonclassifiability for countable torsion free abelian groups, Abelian groups and modules (Eklof, P. C. and Göbel, R., editors), Trends in Mathematics, Birkhäuser, Basel, 1999, pp. 269–292.CrossRefGoogle Scholar
[28] Hjorth, G., Classification and orbit equivalence relations, Mathematical Surveys and Monographs, vol. 75, American Mathematical Society, 2000.Google Scholar
[29] Hodges, W. A., Model theory, Cambridge University Press, 1993.CrossRefGoogle Scholar
[30] Hrushovski, E., Pseudofinite fields and related structures, preprint, 1992.Google Scholar
[31] Hrushovski, E., Mordell-Lang conjecture for function fields, Journal of the American Mathematical Society, vol. 9 (1996), pp. 667–690.CrossRefGoogle Scholar
[32] Hrushovski, E. and Zilber, B., Zariski geometries, Journal of the American Mathematical Society, vol. 9 (1996), pp. 1–56.CrossRefGoogle Scholar
[33] Jensen, R., The fine structure of the constructible hierarchy, Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
[34] Kahane, J.-P. and Salem, R., Ensembles parfaits et séries trigonométigues, 2 ed., Hermann, Paris, 1994.Google Scholar
[35] Kechris, A. S., Actions of polish groups and classification problems, analysis and logic, to appear London Mathematical Society Lecture Note Series, Cambridge University Press, 2001.Google Scholar
[36] Kechris, A. S., Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, Berlin, 1995.CrossRefGoogle Scholar
[37] Kechris, A. S. and Louveau, A., Descriptive set theory and the structure of sets of uniqueness, London Mathematical Society Lecture Notes Series, vol. 128, Cambridge University Press, 1989.Google Scholar
[38] Keisler, H. J., Quantifier elimination for neocompact sets, The Journal of Symbolic Logic, vol. 63 (1998), pp. 1442–1472.CrossRefGoogle Scholar
[39] Khoussainov, B. and Shore, R. A., Effective model theory: the number of models and their complexity, Models and computability (Cooper, S. B. and Truss, J. K., editors), London Mathematical Society Lecture Note Series, vol. 259, Cambridge University Press, 1999, pp. 193–239.CrossRefGoogle Scholar
[40] Kim, B., Forking in simple unstable theories, Journal of the London Mathematical Society, vol. 57 (1998), pp. 257–267.CrossRefGoogle Scholar
[41] Kim, B. and Pillay, A., Simple theories, Annals of Pure and Applied Logic, vol. 88 (1997), pp. 149–164.CrossRefGoogle Scholar
[42] Löwe, B. and Steel, J. R., An introduction to core model theory, sets and proofs, Logic colloquium 1997, vol. 1, London Mathematical Society Lecture Note Series, no. 258, Cambridge University Press, 1999.Google Scholar
[43] Martin, D. A. and Steel, J. R., A proof of projective determinacy, Journal of the American Mathematical Society, vol. 2 (1989), pp. 71–125.CrossRefGoogle Scholar
[44] Moschovakis, Y. N., Descriptive set theory, Elsevier-North Holland, Amsterdam, 1980.Google Scholar
[45] Moschovakis, Y. N., On founding the theory of algorithms, Truth in mathematics (Dales, H. G. and Oliveri, G., editors), Clarendon Press, Oxford, 1998, pp. 71–104.CrossRefGoogle Scholar
[46] Nabutovsky, A. and Weinberger, S., The fractal nature of Riem/Diff, to appear.Google Scholar
[47] Peterzil, Y. and Starchenko, S., A trichotomy theorem for o-minimal structures, Proceedings of the London Mathematical Society, vol. 77 (1998), pp. 481–523.CrossRefGoogle Scholar
[48] Shelah, S., Infinite abelian groups, Whitehead problem and some constructions, Israel Journal of Mathematics, vol. 18 (1974), pp. 243–256.CrossRefGoogle Scholar
[49] Shelah, S., Simple unstable theories, Annals of Mathematical Logic, vol. 19 (1980), pp. 177–203.CrossRefGoogle Scholar
[50] Shore, R. A., Computable structures: presentations matter, Proceedings of the international congress lmps (Krakow, Poland), 08 1999, to appear.Google Scholar
[51] Shore, R. A., Natural definability in degree structures, Computability theory and its applications: Current trends and open problems (Cholak, P., Lempp, S., Lerman, M., and Shore, R. A., editors), Contemporary Mathematics, vol. 257, AMS, 2000, pp. 255–272.CrossRefGoogle Scholar
[52] Shore, R. A. and Slaman, T. A., A splitting theorem for n-REA degrees, to appear in Proceedings of the American Mathematical Society.Google Scholar
[53] Shore, R. A. and Slaman, T. A., Defining the Turing jump, Mathematical Research Letters, vol. 6 (1999), pp. 711–722.CrossRefGoogle Scholar
[54] Sieg, W., Step by recursive step: Church's analysis of effective calculability, this Bulletin, vol. 3 (1997), pp. 154–180.Google Scholar
[55] Simpson, S. G., Reverse mathematics, in preparation.Google Scholar
[56] Simpson, S. G., Subsystems of second order arithmetic, Springer-Verlag, Berlin, 1999.CrossRefGoogle Scholar
[57] Slaman, T. A., Aspects of the Turing jump, to appear in Logic Colloquium '00, Lecture Notes in Logic, ASL.Google Scholar
[58] Slaman, T. A., On a question of Sierpinski, Fundamenta Mathematica, vol. 159 (1999), pp. 153–159.CrossRefGoogle Scholar
[59] Slaman, T. A. and Woodin, H., Definability in degree structures, in preparation.Google Scholar
[60] Soare, R. I., Computability theory and differential geometry, in preparation.Google Scholar
[61] Steel, J. R., An outline of inner model theory, to appear in Handbook of Set Theory, Kluwer, Dordrecht,.CrossRefGoogle Scholar
[62] Todorcevic, S., Partition problems in topology, Contemporary Mathematics, vol. 84, American Mathematical Society, 1989.CrossRefGoogle Scholar
[63] Turing, A. M., On computable numbers with an application to the “Entscheidungsproblem”, Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265.Google Scholar
[64] den Dries, L. van, Tame topology and o-minimal structures, Cambridge University Press, 1998.CrossRefGoogle Scholar
[65] White, W., Characterizations for computable structures, Ph.D. thesis , Cornell University, 2000.Google Scholar
[66] Wilkie, A. J., Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function, Journal of the American Mathematical Society, vol. 9 (1996), pp. 1051–1094.CrossRefGoogle Scholar
[67] Woodin, W. H., Supercompact cardinals, sets of reals, and weakly homogeneous trees, Proceedings of the National Academy of Science, vol. 85 (1988), pp. 6587–6591.CrossRefGoogle ScholarPubMed
[68] Woodin, W. H., The axiom of determinacy, forcing axioms, and the nonstationary ideal, vol. 1, W. de Gruyter, Berlin, 1999.CrossRefGoogle Scholar