World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Reduction games, provability and compactness

    https://doi.org/10.1142/S021906132250009XCited by:1 (Source: Crossref)

    Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between Π21 principles over ω-models of RCA0. They also introduced a version of this game that similarly captures provability over RCA0. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication QP between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between Π21 principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of BΣ20, uncovering new differences between their logical strengths.

    amsc: 03D30, 03B30, 03D80, 03F35

    References

    • 1. A. Bauer, Reductions in computability theory from a constructive point of view, slides from a presentation at the Logic Colloquium/Vienna Summer of Logic (2014), math.andrej.com/wp-content/uploads/2014/07/lc2014-slides-notes.pdf. Google Scholar
    • 2. A. Bauer, Instance reducibility and Weihrauch degrees, preprint (2021), arXiv: 2106.01734. Google Scholar
    • 3. A. Bauer, Instance reducibility and Weihrauch degrees, recording of a talk at the Seminar for Foundations of Mathematics and Theoretical Computer Science, University of Ljubljana (2021), https://www.youtube.com/watch?v=_CoDNlF-zoI. Google Scholar
    • 4. A. Bauer and K. Yoshimura , The Weihrauch lattice is too small, Computability and Complexity in Analysis (2014) Google Scholar
    • 5. A. Bauer and K. Yoshimura , Instance reducibility and extended Weihrauch degrees, Abstracts from Computability, Continuity, Constructivity 2019 — From Logic to Algorithms (2019), pp. 10–12. www.fmf.uni-lj.si/˜simpson/CCC2019_abstracts.pdf Google Scholar
    • 6. V. Brattka, M. de Brecht and A. Pauly , Closed choice and a uniform low basis theorem, Ann. Pure Appl. Log. 163 (2012) 986–1008. Crossref, Web of ScienceGoogle Scholar
    • 7. V. Brattka, G. Gherardi and A. Pauly , Weihrauch complexity in computable analysis, in Handbook of Computability and Complexity in Analysis, eds. V. BrattkaP. Hertling, Theory and Applications of Computability (Springer, Cham, 2021), pp. 367–417. CrossrefGoogle Scholar
    • 8. V. Brattka and A. Pauly , On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci. 14 (2018) 1–36. Web of ScienceGoogle Scholar
    • 9. V. Brattka and T. Rakotoniaina , On the uniform computational content of Ramsey’s theorem, J. Symb. Log. 82 (2017) 1278–1316. Crossref, Web of ScienceGoogle Scholar
    • 10. P. A. Cholak, C. G. Jockusch, Jr. and T. A. Slaman , On the strength of Ramsey’s Theorem for pairs, J. Symb. Log. 66 (2001) 1–55. Crossref, Web of ScienceGoogle Scholar
    • 11. C. T. Chong, S. Lempp and Y. Yang , On the role of collection principles for Σ20 formulas in second-order reverse mathematics, Proc. Amer. Math. Soc. 138 (2010) 1093–1100. Crossref, Web of ScienceGoogle Scholar
    • 12. C. T. Chong, T. A. Slaman and Y. Yang , The metamathematics of stable Ramsey’s Theorem for pairs, J. Amer. Math. Soc. 27 (2014) 863–892. Crossref, Web of ScienceGoogle Scholar
    • 13. F. G. Dorais, D. D. Dzhafarov, J. L. Hirst, J. R. Mileti and P. Shafer , On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc. 368 (2016) 1321–1359. Crossref, Web of ScienceGoogle Scholar
    • 14. D. D. Dzhafarov , Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143 (2015) 869–876. Crossref, Web of ScienceGoogle Scholar
    • 15. D. D. Dzhafarov , Strong reductions between combinatorial principles, J. Symb. Log. 81 (2016) 1405–1431. Crossref, Web of ScienceGoogle Scholar
    • 16. E. Frittaion and A. Marcone , Linear extensions of partial orders and Reverse Mathematics, Math. Log. Q. 58 (2012) 417–423. Crossref, Web of ScienceGoogle Scholar
    • 17. P. Hájek and P. Pudlák , Metamathematics of First-Order Arithmetic, Perspectives in Mathematical Logic (Springer-Verlag, Berlin, 1993). CrossrefGoogle Scholar
    • 18. D. R. Hirschfeldt , Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Note Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28 (World Scientific, Singapore, 2014). LinkGoogle Scholar
    • 19. D. R. Hirschfeldt and C. G. Jockusch, Jr. , On notions of computability-theoretic reduction between Π21 principles. J. Math. Log. 16 (2016) 1650002. Link, Web of ScienceGoogle Scholar
    • 20. D. R. Hirschfeldt, R. A. Shore and T. A. Slaman , The atomic model theorem and type omitting, Trans. Amer. Math. Soc. 361 (2009) 5805–5837. Crossref, Web of ScienceGoogle Scholar
    • 21. J. L. Hirst, Combinatorics in Subsystems of Second Order Arithmetic, PhD Dissertation, The Pennsylvania State University (1987). Google Scholar
    • 22. J. L. Hirst and C. Mummert , Using Ramsey’s theorem once, Arch. Math. Logic 58 (2019) 857–866. Crossref, Web of ScienceGoogle Scholar
    • 23. C. G. Jockusch Jr. , Ramsey’s theorem and recursion theory, J. Symb. Log. 37 (1972) 268–280. Crossref, Web of ScienceGoogle Scholar
    • 24. R. Kossak , On extensions of models of strong fragments of arithmetic, Proc. Amer. Math. Soc. 108 (1990), 223–232. Crossref, Web of ScienceGoogle Scholar
    • 25. R. Kuyper , On Weihrauch reducibility and intuitionistic reverse mathematics, J. Symb. Log. 82 (2017) 1438–1458. Crossref, Web of ScienceGoogle Scholar
    • 26. B. Monin and L. Patey , SRT22 does not imply RT22 in ω-models, Adv. Math. 389 (2021) 107903. Crossref, Web of ScienceGoogle Scholar
    • 27. A. Montalbán and R. A. Shore , Conservativity of ultrafilters over subsystems of second order arithmetic, J. Symb. Log. 83 (2018) 740–765. Crossref, Web of ScienceGoogle Scholar
    • 28. E. Neumann and A. Pauly , A topological view on algebraic computation models, J. Complexity 44 (2018) 1–22. Crossref, Web of ScienceGoogle Scholar
    • 29. L. Patey, The reverse mathematics of Ramsey-type theorems, PhD Dissertation, Université Paris Diderot (Paris VII) (2016). Google Scholar
    • 30. L. Patey , The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math. 216 (2016) 905–955. Crossref, Web of ScienceGoogle Scholar
    • 31. A. Pauly, W. Fouché and G. Davie , Weihrauch-completeness for layerwise computability, Log. Methods Comput. Sci. 14(2) (2018) 11. Web of ScienceGoogle Scholar
    • 32. S. G. Simpson , Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, 1st edn. (Springer-Verlag, Berlin, 1999) CrossrefGoogle Scholar
    • 33. S. G. Simpson , Subsystems of Second Order Arithmetic, Perspectives in Logic, 2nd edn. (Cambridge University Press, Cambridge and Association for Symbolic Logic, Poughkeepsie, NY, 2009). CrossrefGoogle Scholar
    • 34. R. I Soare , Turing Computability: Theory and Applications (Spring-Verlag, Berlin, 2016). CrossrefGoogle Scholar
    • 35. P. Uftring, Proof-Theoretic Characterization of Weihrauch Reducibility, Master’s Thesis, Technische Universität Darmstadt (2018). Google Scholar
    • 36. P. Uftring , The characterization of Weihrauch reducibility in systems containing E-PAω + QF-AC0,0, J. Symb. Log. 86 (2021) 224–261. Crossref, Web of ScienceGoogle Scholar
    • 37. H. Wang, Popular Lectures on Mathematical Logic (Dover Publications Inc., New York, 1993), revised reprint of the 1981 second edition. Google Scholar
    • 38. L. B. Westrick , A note on the diamond operator, Computability 10 (2021) 107–110. Crossref, Web of ScienceGoogle Scholar