We extend a study by Lempp and Hirst of infinite versions of some problems from finite complexity theory, using an intuitionistic version of reverse mathematics and techniques of Weihrauch analysis.
J.L.Hirst and S.Lempp, Infinite versions of some problems from finite complexity theory, Notre Dame J. Form. Log.37(4) (1996), 545–553. doi:10.1305/ndjfl/1040046141.
6.
J.L.Hirst and C.Mummert, Reverse mathematics and uniformity in proofs without excluded middle, Notre Dame J. Form. Log.52(2) (2011), 149–162. doi:10.1215/00294527-1306163.
7.
J.L.Hirst and C.Mummert, Using Ramsey’s theorem once, Arch. Math. Logic (2019), 1–10. doi:10.1007/s00153-019-00664-z.
8.
C.G.JockuschJr. and R.I.Soare, classes and degrees of theories, Trans. Amer. Math. Soc.173 (1972), 33–56. doi:10.2307/1996261.
9.
T.Kihara, A.Marcone and A.Pauly, Searching for an analogue of in the Weihrauch lattice, J. Symb. Log.85(3) (2020), 1006–1043. doi:10.1017/jsl.2020.12.
10.
U.Kohlenbach, Higher order reverse mathematics, in: Reverse Mathematics 2001, S.Simpson, ed., Lect. Notes Log., Vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 281–295. doi:10.1017/9781316755846.018.
11.
U.Kohlenbach, Applied Proof Theory: Proof Interpretations and Their Use in Mathematics, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2008, p. xx+532. ISBN 978-3-540-77532-4.
12.
A.Pauly, Personal communication, 2021.
13.
S.G.Simpson, Subsystems of Second Order Arithmetic, Perspectives in Logic, 2nd edn, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009, p. xvi+444. ISBN 978-0-521-88439-6. doi:10.1017/CBO9780511581007.
14.
A.S.Troelstra, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lect. Notes in Math., Vol. 344, Springer, Berlin, 1973, p. xvii+485. ISBN 0-387-06491-5. doi:10.1007/BFb0066739.
