Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T17:52:25.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Open Questions in Reverse Mathematics

Published online by Cambridge University Press:  15 January 2014

Antonio Montalbán
Antonio Montalbán*
Affiliation:
Department of Mathematics, University of chicago, 5734 S. University Ave. Chicago, IL 60637, USAE-mail: [email protected], URL: www.math.uchicago.edu/~antonio
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a list of open questions in reverse mathematics, including some relevant background information for each question. We also mention some of the areas of reverse mathematics that are starting to be developed and where interesting open question may be found.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 17 , Issue 3 , September 2011 , pp. 431 - 454
Copyright
Copyright © Association for Symbolic Logic 2011

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

[ARI0] Afshari, Bahareh and Rathjen, Michael, A note on the theory of positive induction, , Archive for Mathematical Logic, vol. 49 (2010), no. 2, pp. 275–281.Google Scholar
[ASKHLS04] Ambos-Spies, Klaus, Kjos-Hanssen, Bjørn, Lempp, Steffen, and Slaman, Theodore A., Comparing DNR and WWKL, The Journal of Symbolic Logic, vol. 69 (2004), no. 4, pp. 1089–1104.Google Scholar
[Avi09] Avigad, Jeremy, The metamathematics of ergodic theory, Annals of Pure and Applied Logic, vol. 157 (2009), no. 2–3, pp. 64–76.CrossRefGoogle Scholar
[AS06] Avigad, Jeremy and Simic, Ksenija, Fundamental notions of analysis in subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 139 (2006), no. 1–3, pp. 138–184.Google Scholar
[Bla05] Blass, Andreas, Some questions arising from Hindman s theorem, Scientiae Mathematicae Japonicae, vol. 62 (2005), no. 2, pp. 331–334.Google Scholar
[BHS87] Blass, Andreas, Hirst, Jeffry L., and Simpson, Stephen G., Logical analysis of some theorems of combinatorics and topological dynamics, Logic and combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, RI, 1987, pp. 125–156.Google Scholar
[BW] Bovykin, A. and Weiermann, A., The strength of infinitary Ramseyan principles can be accessed by their densities, Annals of Pure and Applied , to appear.Google Scholar
[BMN] Brattka, Vasco, Miller, Joseph, and Nies, Andre, Randomness and differentiability, in preparation.Google Scholar
[Bus86] Buss, Samuel R., Bounded arithmetic, Studies in Proof Theory. Lecture Notes, vol. 3, Bibliopolis, Naples, 1986.Google Scholar
[Car88] Carlson, Timothy J., Some unifying principles in Ramsey theory, Discrete Mathematics, vol. 68 (1988), no. 2-3, pp. 117–169.Google Scholar
[CarOl] Carlson, Timothy J., Elementary patterns of resemblance, Proceedings of the XIth Latin American Symposium on Mathematical Logic (Mérida, 1998), vol. 108, 2001, pp. 19–77.Google Scholar
[Car09] Carlson, Timothy J., Patterns of resemblance of order 2, Annals of Pure and Applied Logic, vol. 158 (2009), no. 1-2, pp. 90–124.Google Scholar
[CS84] Carlson, Timothy J. and Simpson, Stephen G., A dual form of Ramsey's theorem, Advances in Mathematics, vol. 53 (1984), pp. 265–290.Google Scholar
[CGHJ05] Cholak, Peter A., Giusto, Mariagnese, Hirst, Jeffry L., and Jockusch, Carl G., Free sets and reverse mathematics, Reverse mathematics 2001 (Simpson, Stephen G., editor), Lecture Notes in Logic, vol. 21, Association for Symbolic Logic, La Jolla, CA, 2005, pp. 104–119.Google Scholar
[CJS01] Cholak, Peter A., Jockusch, Carl G., and Slaman, Theodore A., On the strength of Ramsey's theorem for pairs, The Journal of Symbolic Logic, vol. 66 (2001), no. 1, pp. 1–55.Google Scholar
[CJS09] Cholak, Peter A., Corrigendum to: On the strength of Ramsey’s theorem for pairs, The Journal of Symbolic Logic, vol. 74 (2009), no. 4, pp. 1438–1439.CrossRefGoogle Scholar
[CMS04] Cholak, Peter A., Marcone, Alberto, and Solomon, Reed, Reverse mathematics and the equivalence of definitions for well and better quasi-orders, The Journal of Symbolic Logic, vol. 69 (2004), no. 3, pp. 683–712.Google Scholar
[CLY10] Chong, C. T., Lempp, Steffen, and Yang, Yue, On the role of the collection principle for -formulas in second-order reverse mathematics, Proceedings of the American Mathematical Society, vol. 138 (2010), no. 3, pp. 1093–1100.Google Scholar
[CHM09] Chubb, Jennifer, Hirst, Jeffry L., and Mcnicholl, Timothy H., Reverse mathematics, computability, and partitions of trees, The Journal of Symbolic Logic, vol. 74 (2009), no. 1, pp. 201–215.Google Scholar
[Con10] Conidis, C. J., Chain conditions in computable rings, Transactions of the American Mathematical Society, vol. 362 (2010), no. 12, pp. 6523–6550.Google Scholar
[Con] Conidis, C. J., The strength of the Bolzano-Weierstrass theorem, submitted for publication.Google Scholar
[CGM] Corduan, J., Groszek, M., and Mileti, J., A note on reverse mathematics and partitions of trees, submitted for publication.Google Scholar
[dJP77] de Jongh, D. H. J. and Parikh, Rohit, Well-partial orderings and hierarchies, Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen Series A. Indagationes Mathematicae, vol. 39 (1977), no. 3 [80], pp. 195–207.Google Scholar
[DHLS03] Downey, Rodney G., Hirschfeldt, Denis R., Lempp, Steffen, and Solomon, Reed, Computability-theoretic and proof-theoretic aspects of partial and linear orderings, Israel Journal of Mathematics, vol. 138 (2003), pp. 271–352.Google Scholar
[DH09] Dzhafarov, Damir D. and Hirst, Jeffry L., The polarized Ramsey's theorem, Archive for Mathematical Logic, vol. 48 (2009), no. 2, pp. 141–157.CrossRefGoogle Scholar
[DLH10] Dzhafarov, Damir D., Lakins, T. J., and Hirst, J. L., Ramsey's theorem for trees: the polarized tree theorem and notions of stability, Archive for Mathematical Logic, vol. 49 (2010), no. 3, pp. 399–415.Google Scholar
[EM64] Erdős, P. and Moser, L., On the representation of directed graphs as unions of orderings, Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 9 (1964), pp. 125–132.Google Scholar
[FF02] Fernandes, António M. and Ferreira, Fernando, Groundwork for weak analysis, The Journal of Symbolic Logic, vol. 67 (2002), no. 2, pp. 557–578.Google Scholar
[Fra48] Fraïssé, Roland, Sur la comparaison des types d'ordres, Comptes rendus de l'Académie des sciences de Paris, vol. 226 (1948), pp. 1330–1331.Google Scholar
[Fri75] Friedman, Harvey, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), vol. 1, Canadian Mathematics Congress, Montreal, Quebec, 1975, pp. 235–242.Google Scholar
[Fri09] Friedman, Harvey, The inevitability of logical strength: strict reverse mathematics, Logic Colloquium 2006 (Cooper, Barry, Geuvers, Herman, Pillay, Anand, and Väänänen, Jouko, editors), Lecture Notes in Logic, vol. 32, Association for Symbolic Logic, Chicago, IL, 2009, pp. 135–183.Google Scholar
[Fri] Friedman, Harvey, Metamathematics of ulm theory, manuscpript dated November 2001.Google Scholar
[FMW] Friedman, Harvey, Montalbán, Antonio, and Weiermann, Andreas, A characterization of ATR0 in terms of a Kruskal-like tree theorem, unpublished draft.Google Scholar
[FS00] Friedman, Harvey and Simpson, Stephen G., Issues and problems in reverse mathematics, Computability theory and its applications (Boulder, CO, 1999), Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, 2000, pp. 127–144.Google Scholar
[FSS83] Friedman, Harvey, Simpson, Stephen G., and Smith, Rick L., Countable algebra and set existence axioms, Annals of Pure and Applied Logic, vol. 25 (1983), no. 2, pp. 141–181.CrossRefGoogle Scholar
[GHR10] Gács, Peter, Hoyrup, Mathieu, and Rojas, Cristóbal, Randomness on computable probability spaces—a dynamical point of view, Theory of Computing Systems, special issue STACS 09, 2010.Google Scholar
[Gir81] Girard, Jean-Yves, -logic. I. Dilators, Annals of Mathematical Logic, vol. 21 (1981), no. 2-3, pp. 75–219.Google Scholar
[Gir87] Girard, Jean-Yves, Proof theory and logical complexity, Bibliopolis, Naples, 1987.Google Scholar
[GM98] Giusto, Mariagnese and Marcone, Alberto, Lebesgue numbers and A tsuji spaces in subsystems of second-order arithmetic, Archive for Mathematical Logic, vol. 37 (1998), no. 5-6, pp. 343–362.Google Scholar
[GS00] Giusto, Mariagnese and Simpson, Stephen G., Located sets and reverse mathematics, The Journal of Symbolic Logic, vol. 65 (2000), no. 3, pp. 1451–1480.Google Scholar
[GM08] Greenberg, N. and Montalbán, A., Ranked structures and arithmetic transfinite recursion, Transactions of the AMS, vol. 360 (2008), pp. 1265–1307.Google Scholar
[HS07] Hirschfeldt, Denis R. and Shore, Richard A., Combinatorial principles weaker than Ramsey's theorem for pairs, The Journal of Symbolic Logic, vol. 72 (2007), no. 1, pp. 171–206.Google Scholar
[Hir94] Hirst, Jeffry L., Reverse mathematics and ordinal exponentiation, Annals of Pure and Applied Logic, vol. 66 (1994), no. 1, pp. 1–18.Google Scholar
[Hir04] Hirst, Jeffry L., Hindman's theorem, ultrafilters, and reverse mathematics, The Journal of Symbolic Logic, vol. 69 (2004), no. 1, pp. 65–72.Google Scholar
[Hun08] Hunter, James, Higher-order reverse topology, Ph.D. thesis, University of Wisconsin-Madison, 2008.Google Scholar
[Joc72] Jockusch, Carl G., Ramsey's theorem and recursion theory, The Journal of Symbolic Logic, vol. 37 (1972), pp. 268–280.Google Scholar
[JS72] Jockusch, Carl G. and Soare, Robert I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[Kap69] Kaplansky, Irving, Infinite abelian groups, revised ed., The University of Michigan Press, Ann Arbor, Michigan, 1969.Google Scholar
[KP77] Kirby, L. A. S. and Paris, J. B., Initial segments of models of Peano's axioms, Set theory and hierarchy theory, V (Proceeding of the Third Conference, Bierutowice, 1976), Lecture Notes in Mathematics, vol. 619, Springer, Berlin, 1977, pp. 211–226.Google Scholar
[Koh05] Kohlenbach, Ulrich, Higher order reverse mathematics, Reverse mathematics 2001 (Simpson, Stephen G., editor), Lecture Notes in Logic, vol. 21, Association for Symbolic Logic, La Jolla, CA, 2005, pp. 281–295.Google Scholar
[Lav71] Laver, Richard, On Fraïssé's order type conjecture, Annals of Mathematics (2), vol. 93 (1971), pp. 89–111.Google Scholar
[MW85] Mansfield, Richard and Weitkamp, Galen, Recursive aspects of descriptive set theory, Oxford Logic Guides, vol. 11, The Clarendon Press Oxford University Press, New York, 1985, with a chapter by Stephen Simpson.Google Scholar
[Mar96] Marcone, Alberto, On the logical strength of Nash–Williams' theorem on trans-finite sequences, Logic: from foundations to applications (Staffordshire, 1993), Oxford Sciene Publications, Oxford University Press, New York, 1996, pp. 327–351.Google Scholar
[Mar05] Marcone, Alberto, Wqo and bqo theory in subsystems of second order arithmetic, Reverse mathematics 2001 (Simpson, Stephen G., editor), Lecture Notes in Logic, vol. 21, Association for Symbolic Logic, La Jolla, CA, 2005, pp. 303–330.Google Scholar
[MM] Marcone, Alberto and Montalbán, Antonio, The Veblen functions for computability theorists, submitted for publication.Google Scholar
[MM09] Marcone, Alberto, On Fraïssé’s conjecture for linear orders offinite Hausdorff rank, Annals of Pure and Applied Logic, vol. 160 (2009), pp. 355–367.Google Scholar
[McN95] McNicnoll, T. H., The inclusion problem for generalized frequency classes, Ph.D. thesis, The George Washington University, 1995.Google Scholar
[MT07] Medsalem, Medyahya Ould and Tanaka, Kazuyuki, -determinacy, comprehension and induction, The Journal of Symbolic Logic, vol. 72 (2007), no. 2, pp. 452–462.Google Scholar
[Mil04] Mileti, Joseph R., Partition theorems and computability theory, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2004.Google Scholar
[MS04] Miller, Joseph S. and Solomon, Reed, Effectiveness for infinite variable words and the dual Ramsey theorem, Archive for Mathematical Logic, vol. 43 (2004), no. 4, pp. 543–555.CrossRefGoogle Scholar
[Mon] Montalbán, Antonio, Ordinal functors and pi-1-1-ca-knot, unpublished notes dated December 7, 2009.Google Scholar
[Mon05] Montalbán, Antonio, Up to equimorphism, hyperarithmetic is recursive, The Journal of Symbolic Logic, vol. 70 (2005), no. 2, pp. 360–378.Google Scholar
[Mon06a] Montalbán, Antonio, Equivalence between Fraïssé's conjecture and Jullien's theorem, Annals of Pure and Applied Logic, vol. 139 (2006), no. 1-3, pp. 1–42.Google Scholar
[Mon06b] Montalbán, Antonio, Indecomposable linear orderings and hyperarithmetic analysis, Journal of Mathematical Logic, vol. 6 (2006), no. 1, pp. 89–120.Google Scholar
[Mon07] Montalbán, Antonio, On the equimorphism types of linear orderings, this Bulletin, vol. 13 (2007), no. 1, pp. 71-99.Google Scholar
[MS] Montalbán, Antonio and Shore, Richard A., The limits of determinacy in second order arithmetic, submitted for publication.Google Scholar
[NW65] Nash-Williams, C. St. J. A., On well-quasi-ordering transfinite sequences, Proceedings of the Cambridge Philosophical Society, vol. 61 (1965), pp. 33–39.CrossRefGoogle Scholar
[NW68] Nash-Williams, C. St. J. A., On better-quasi-ordering transfinite sequences, Proceedings of the Cambridge Philosophical Society, vol. 64 (1968), pp. 273–290.Google Scholar
[Nee] Neeman, I., Necessary use of induction in a reversal, to appear.Google Scholar
[Nem09] Nemoto, Takako, Determinacy of Wadge classes and subsystems of second order arithmetic, Mathematical Logic Quarterly, vol. 55 (2009), no. 2, pp. 154–176.Google Scholar
[NOMT07] Nemoto, Takako, Medsalem, Medyahya Ould, and Tanaka, Kazuyuki, Infinite games in the Cantor space and subsystems of second order arithmetic, Mathematical Logic Quarterly, vol. 53 (2007), no. 3, pp. 226–236.CrossRefGoogle Scholar
[Pat09] Pathak, Noopur, A computational aspect of the Lebesgue differentiation theorem, Journal of Logic and Analysis, vol. 1 (2009), pp. 1–15, Paper 9.Google Scholar
[Rat] Rathjen, Michael, ω-models and well-ordering principles, to appear.Google Scholar
[RW93] Rathjen, Michael and Weiermann, Andreas, Proof-theoretic investigations on Kruskal's theorem, Annals of Pure and Applied Logic, vol. 60 (1993), no. 1, pp. 49–88.Google Scholar
[RW] Rathjen, Michael, Reverse mathematics and well-ordering principles, Computability in context: Computation and logic in the real world , to appear.Google Scholar
[Ros84] Rosenstein, Joseph G., Recursive linear orderings, Orders: description and roles (L'Arbresle, 1982), North-Holland Mathematics Studies, vol. 99, North-Holland, Amsterdam, 1984, pp. 465–475.Google Scholar
[SY04] Sakamoto, Nobuyuki and Yamazaki, Takeshi, Uniform versions of some axioms of second order arithmetic, Mathematical Logic Quarterly, vol. 50 (2004), no. 6, pp. 587–593.Google Scholar
[Sch79] Schmidt, Diana, Well-partial orderings and their maximal order types, Habilitationsschrift, University of Heidelberg, 1979.Google Scholar
[Sh093] Shore, Richard A., On the strength of Fraïssë's conjecture, Logical methods (Ithaca, NY, 1992), Progress in Computer Science and Applied Logic, vol. 12, Birkhäuser Boston, Boston, MA, 1993, pp. 782–813.Google Scholar
[SholO] Shore, Richard A., Reverse mathematics: The playground of logic, this Bulletin, vol. 16 (2010), no. 3, pp. 378–402.Google Scholar
[Sho] Shore, Richard A., Reverse mathematics, countable and uncountable: A computational approach, to appear.Google Scholar
[Sim09] Simpson, Stephen G., Subsystems of second order arithmetic, second ed., Perspectives in Logic, Cambridge University Press, Cambridge, 2009.CrossRefGoogle Scholar
[Sim 10] Simpson, Stephen G., The Gödei hierarchy and reverse mathematics, Kurt Gödel: essays for his centennial (Feferman, Solomon, Parsons, Charles, and Simpson, Steven G., editors), Lecture Notes in Logic, vol. 33, Association for Symbolic Logic, La Jolla, CA, 2010, pp. 109–127.Google Scholar
[SS86] Simpson, Stephen G. and Smith, Rick L., Factorization of polynomials and induction, Annals of Pure and Applied Logic, vol. 31 (1986), no. 2-3, pp. 289–306, Special issue: Second Southeast Asian logic conference (Bangkok, 1984).Google Scholar
[Sla] Slaman, T. A., A note on dual Ramsey theorem, unpublished note dated January 1997.Google Scholar
[Sm085] Smoryński, C., Nonstandard models and related developments, Harvey Friedman’s research on the foundations of mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, North-Holland, Amsterdam, 1985, pp. 179–229.Google Scholar
[Wel] Welch, Philip, Weak systems of determinacy and arithmetical quasi-inductive definitions, submitted for publication.Google Scholar
[Wil06] Wilken, Gunnar, The Bachmann-Howard structure in terms of Σ1-elementarity, Archive for Mathematical Logic, vol. 45 (2006), no. 7, pp. 807–829.Google Scholar
[WÌ107] Wilken, Gunnar, Assignment of ordinals to patterns of resemblance, The Journal of Symbolic Logic, vol. 72 (2007), no. 2, pp. 704–720.Google Scholar
[YS90] Yu, Xiaokang and Simpson, Stephen G., Measure theory and weak Königs lemma, Archive for Mathematical Logic, vol. 30 (1990), no. 3, pp. 171–180.Google Scholar