We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem is the strongest problem with codomaixn ω that is Weihrauch reducible to . We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature.
Get full access to this article
View all access options for this article.
References
1.
V.Brattka, G.Gherardi and A.Marcone, The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma, Ann. Pure Appl. Logic163(6) (2012), 623–655. doi:10.1016/j.apal.2011.10.006.
2.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis. in: Handbook of Computability and Complexity in Analysis, Theory Appl. Comput.2021, 367–417.
3.
V.Brattka, M.Hendtlass and A.P.Kreuzer, On the uniform computational content of computability theory, Theory Comput. Syst.61(4) (2017), 1376–1426. doi:10.1007/s00224-017-9798-1.
4.
V.Brattka and A.Pauly, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci., to appear.
5.
V.Brattka and T.Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic82(4) (2017), 1278–1316. doi:10.1017/jsl.2017.43.
6.
P.A.Cholak, C.G.Jockusch and T.A.Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic66(1) (2001), 1–55. doi:10.2307/2694910.
7.
V.Cipriani, A.Marcone and M.Valenti, The Weihrauch lattice at the level of : The Cantor–Bendixson theorem.
8.
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(2) (2016), 1321–1359. doi:10.1090/tran/6465.
9.
R.G.Downey and D.R.Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.
10.
D.D.Dzhafarov, J.Le Goh, D.R.Hirschfeldt, L.Patey and A.Pauly, Ramsey’s theorem and products in the Weihrauch degrees, Computability9(2) (2020), 85–110. doi:10.3233/COM-180203.
11.
D.D.Dzhafarov and C.Mummert, On the strength of the finite intersection principle, Israel J. Math.196(1) (2013), 345–361. doi:10.1007/s11856-012-0150-9.
12.
D.D.Dzhafarov and C.Mummert, Reverse Mathematics: Problems, Reductions, and Proofs, Theory and Applications of Computability, Springer, New York, 2022.
13.
M.Fiori-Carones, L.A.Kołodziejczyk, T.L.Wong and K.Yokoyama, An isomorphism theorem for models of Weak König’s lemma without primitive recursion, J. Europ. Math. Soc. (2021).
14.
G.Gherardi and A.Marcone, How incomputable is the separable Hahn–Banach theorem? in: Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), Electron. Notes Theor. Comput. Sci., Vol. 221, Elsevier Sci. B. V., Amsterdam, 2008, pp. 85–102.
15.
P.Hájek, Interpretability and fragments of arithmetic, in: Arithmetic, Proof Theory, and Computational Complexity, Prague, 1991, Oxford Logic Guides, Vol. 23, Oxford Univ. Press, New York, 1993, pp. 185–196.
16.
D.R.Hirschfeldt, Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, World Scientific Publishing Company Incorporated, 2014.
17.
D.R.Hirschfeldt and C.G.JockuschJr., On notions of computability-theoretic reduction between principles, J. Math. Log.16(1) (2016), 1650002, 59.
18.
D.R.Hirschfeldt, R.A.Shore and T.A.Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc.361(11) (2009), 5805–5837. doi:10.1090/S0002-9947-09-04847-8.
19.
J.L.Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, The Pennsylvania State University, 1987.
20.
C.G.Jockusch, Jr. Ramsey’s theorem and recursion theory, J. Symbolic Logic37 (1972), 268–280. doi:10.2307/2272972.
21.
J.Le Goh, A.Pauly and M.Valenti, Finding descending sequences through ill-founded linear orders, J. Symb. Log.86(2) (2021), 817–854. doi:10.1017/jsl.2021.15.
22.
S.G.Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Perspectives in Logic, Cambridge University Press, Cambridge, 2009.
23.
S.G.Simpson and R.L.Smith, Factorization of polynomials and induction, in: Special issue: Second Southeast Asian logic conference, Bangkok, 1984, Vol. 31, 1986, pp. 289–306.
24.
T.A.Slaman and K.Yokoyama, The strength of Ramsey’s theorem for pairs and arbitrarily many colors, J. Symb. Log.83(4) (2018), 1610–1617. doi:10.1017/jsl.2018.19.
25.
R.I.Soare, Turing Computability: Theory and Applications, 1st edn, Springer Publishing Company, Incorporated, 2016.
26.
G.Solda and M.Valenti, Algebraic properties of the first-order part of a problem, Ann. Pure Appl. Logic174(7) (2023), 103270.
27.
W.Wang, Some reverse mathematics of rainbow Ramsey theorems, unpublished.
