Three topological reducibilities for discontinuous functions

Day, Adam; Downey, Rod; Westrick, Linda

doi:10.1090/btran/115

Three topological reducibilities for discontinuous functions
HTML articles powered by AMS MathViewer

by Adam R. Day, Rod Downey and Linda Westrick HTML | PDF

Trans. Amer. Math. Soc. Ser. B 9 (2022), 859-895

Abstract:

We define a family of three related reducibilities, $\leq _{\mathbf {T}}$, $\leq _{\mathbf {tt}}$ and $\leq _{\mathbf {m}}$, for arbitrary functions $f,g:X\rightarrow \mathbb R$, where $X$ is a compact separable metric space. The $\equiv _{\mathbf T}$-equivalence classes mostly coincide with the proper Baire classes. We show that certain $\alpha$-jump functions $j_\alpha :2^\omega \rightarrow \mathbb {R}$ are $\leq _{\mathbf {m}}$-minimal in their Baire class. Within the Baire 1 functions, we completely characterize the degree structure associated to $\leq _{\mathbf {tt}}$ and $\leq _{\mathbf {m}}$, finding an exact match to the $\alpha$ hierarchy introduced by Bourgain [Bull. Soc. Math. Belg. Sér. B 32 (1980), pp. 235–249] and analyzed in Kechris & Louveau [Trans. Amer. Math. Soc. 318 (1990), pp. 209–236].

References

C. J. Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc. 298 (1986), no. 2, 497–514. MR 860377, DOI 10.1090/S0002-9947-1986-0860377-7
Vasco Brattka and Guido Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic 76 (2011), no. 1, 143–176. MR 2791341, DOI 10.2178/jsl/1294170993
Vasco Brattka, Guido Gherardi, and Arno Pauly, Weihrauch complexity in computable analysis, Handbook of computability and complexity in analysis, Theory Appl. Comput., Springer, Cham, [2021] ©2021, pp. 367–417. MR 4300761, DOI 10.1007/978-3-030-59234-9_{1}1
J. Bourgain, On convergent sequences of continuous functions, Bull. Soc. Math. Belg. Sér. B 32 (1980), no. 2, 235–249. MR 682645
Vasco Brattka, Effective Borel measurability and reducibility of functions, MLQ Math. Log. Q. 51 (2005), no. 1, 19–44. MR 2099383, DOI 10.1002/malq.200310125
Raphaël Carroy, A quasi-order on continuous functions, J. Symbolic Logic 78 (2013), no. 2, 633–648. MR 3145199
Adam Day, Noam Greenberg, Matthew Harrison-Trainor, and Dan Turetsky, The strength of Borel Wadge comparability, 2021, Presentation delivered by Noam Greenberg at the Midwest Computability Seminar joint with the Computability Theory and Applications Online Seminar, April 2021, Slides available at http://www.math.uchicago.edu/~drh/mcs/greenberg_slides2.pdf, accessed July 2021.
Rod Downey and Antonio Montalbán, The isomorphism problem for torsion-free abelian groups is analytic complete, J. Algebra 320 (2008), no. 6, 2291–2300. MR 2437501, DOI 10.1016/j.jalgebra.2008.06.007
Adam Day and Andrew Marks, A completeness criterion for Borel sets, 2019, Presentation delivered by Adam Day at the National University of Singapore Institute for Mathematical Sciences Workshop: Higher Recursion Theory and Set Theory, May-June 2019, Slides available at https://imsarchives.nus.edu.sg/oldwww2/events/2019/recur/files/adam.pdf, accessed July 2021.
Márton Elekes, Viktor Kiss, and Zoltán Vidnyánszky, Ranks on the Baire class $\xi$ functions, Trans. Amer. Math. Soc. 368 (2016), no. 11, 8111–8143. MR 3546795, DOI 10.1090/tran/6764
A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 86756, DOI 10.4064/fm-42-1-168-202
A. Grzegorczyk, On the definitions of computable real continuous functions, Fund. Math. 44 (1957), 61–71. MR 89809, DOI 10.4064/fm-44-1-61-71
Noam Greenberg and Daniel Turetsky, Completeness of the hyperarithmetic isomorphism equivalence relation, Adv. Math. 403 (2022), Paper No. 108356, 56. MR 4402976, DOI 10.1016/j.aim.2022.108356
Peter Hertling, Topological complexity with continuous operations, J. Complexity 12 (1996), no. 4, 315–338. Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). MR 1422714, DOI 10.1006/jcom.1996.0021
Peter Hertling, Unstetigkeitsgrade von Funktionen in der effectiven Analysis, Ph.D. Thesis, FernUniversität Hagen, Informatik-Berichte 208, 1996.
Graham Higman and Elizabeth Scott, Existentially closed groups, London Mathematical Society Monographs. New Series, vol. 3, The Clarendon Press, Oxford University Press, New York, 1988. Oxford Science Publications. MR 960689
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
Takayuki Kihara, Topological reducibilities for discontinuous functions and their structures, Preprint, arXiv:1906.10573, 2019.
Takayuki Kihara, Decomposing Borel functions using the Shore-Slaman join theorem, Fund. Math. 230 (2015), no. 1, 1–13. MR 3332281, DOI 10.4064/fm230-1-1
A. S. Kechris and A. Louveau, A classification of Baire class $1$ functions, Trans. Amer. Math. Soc. 318 (1990), no. 1, 209–236. MR 946424, DOI 10.1090/S0002-9947-1990-0946424-3
S. C. Kleene, Recursive functionals and quantifiers of finite types. I, Trans. Amer. Math. Soc. 91 (1959), 1–52. MR 102480, DOI 10.1090/S0002-9947-1959-0102480-9
Takayuki Kihara and Antonio Montalbán, On the structure of the Wadge degrees of bqo-valued Borel functions, Trans. Amer. Math. Soc. 371 (2019), no. 11, 7885–7923. MR 3955538, DOI 10.1090/tran/7621
Christoph Kreitz and Klaus Weihrauch, Theory of representations, Theoret. Comput. Sci. 38 (1985), no. 1, 35–53. MR 805132, DOI 10.1016/0304-3975(85)90208-7
Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. I, C. R. Acad. Sci. Paris 240 (1955), 2478–2480 (French). MR 72079
Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris 241 (1955), 13–14, 151–153 (French). MR 72080
Steffen Lempp and Manuel Lerman, A general framework for priority arguments, Bull. Symbolic Logic 1 (1995), no. 2, 189–201. MR 1335987, DOI 10.2307/421040
A. Louveau and J. Saint-Raymond, Borel classes and closed games: Wadge-type and Hurewicz-type results, Trans. Amer. Math. Soc. 304 (1987), no. 2, 431–467. MR 911079, DOI 10.1090/S0002-9947-1987-0911079-0
Alain Louveau and Jean Saint-Raymond, The strength of Borel Wadge determinacy, Cabal Seminar 81–85, Lecture Notes in Math., vol. 1333, Springer, Berlin, 1988, pp. 1–30. MR 960893, DOI 10.1007/BFb0084967
Joseph S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69 (2004), no. 2, 555–584. MR 2058189, DOI 10.2178/jsl/1082418543
Antonio Montalbán, Priority arguments via true stages, J. Symb. Log. 79 (2014), no. 4, 1315–1335. MR 3343540, DOI 10.1017/jsl.2014.11
U. Mylatz, Vergleich unstetiger Funktionen: “Principle of Omniscience” und Vollstaendigkeit in der C-Hierarchie, 2006. Thesis (Ph.D.)–Feruniversitaet, Gesamthochschule in Hagen.
Arno Pauly, On the (semi)lattices induced by continuous reducibilities, MLQ Math. Log. Q. 56 (2010), no. 5, 488–502. MR 2742884, DOI 10.1002/malq.200910104
Jan Reimann and Theodore A. Slaman, Effective randomness for continuous measures, J. Amer. Math. Soc. 35 (2022), no. 2, 467–512. MR 4374955, DOI 10.1090/jams/980
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
Matthias Schröder, Extended admissibility, Theoret. Comput. Sci. 284 (2002), no. 2, 519–538. Computability and complexity in analysis (Castle Dagstuhl, 1999). MR 1923914, DOI 10.1016/S0304-3975(01)00109-8
Jean Saint-Raymond, Fonctions boréliennes sur un quotient, Bull. Sci. Math. (2) 100 (1976), no. 2, 141–147 (French). MR 460578
A. M. Turing, Systems of Logic Based on Ordinals, Proc. London Math. Soc. (2) 45 (1939), no. 3, 161–228. MR 1576807, DOI 10.1112/plms/s2-45.1.161
Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9