Wadge-like degrees of Borel bqo-valued functions
HTML articles powered by AMS MathViewer
- by Takayuki Kihara and Victor Selivanov
- Proc. Amer. Math. Soc. 150 (2022), 3989-4003
- DOI: https://doi.org/10.1090/proc/15930
- Published electronically: April 7, 2022
- PDF | Request permission
Abstract:
We unite two well known generalisations of the Wadge theory. The first one considers more general reducing functions than the continuous functions in the classical case, and the second one extends Wadge reducibility from sets (i.e., $\{0,1\}$-valued functions) to $Q$-valued functions, for a better quasiorder $Q$. In this article, we consider more general reducibilities on the $Q$-valued functions and generalise some results of L. Motto Ros [J. Symbolic Logic 74 (2009), pp. 27–49] in the first direction and of T. Kihara and A. Montalbán [Trans. Amer. Math. Soc. 370 (2018), pp. 9025–9044] in the second direction: Our main result states that the structure of the $\mathbf {\Delta }^0_\alpha$-degrees of $\mathbf {\Delta }^0_{\alpha +\gamma }$-measurable $Q$-valued functions is isomorphic to the $\mathbf {\Delta }^0_\beta$-degrees of $\mathbf {\Delta }^0_{\beta +\gamma }$-measurable $Q$-valued functions, and these are isomorphic to the generalized homomorphism order on the $\gamma$-th iterated $Q$-labeled forests.References
- Alexander C. Block, Operations on a Wadge-type hierarchy of ordinal-valued functions, Master’s thesis, Universiteit van Amsterdam, 2014.
- J. Bourgain, On convergent sequences of continuous functions, Bull. Soc. Math. Belg. Sér. B 32 (1980), no. 2, 235–249. MR 682645
- Adam R. Day, Rod Downey, and Linda Brown Westrick, Three topological reducibilities for discontinuous functions, arXiv:1906.07600, 2019.
- J. Duparc, Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank, J. Symbolic Logic 66 (2001), no. 1, 56–86. MR 1825174, DOI 10.2307/2694911
- J. Duparc, The Steel hierarchy of ordinal valued Borel mappings, J. Symbolic Logic 68 (2003), no. 1, 187–234. MR 1959317, DOI 10.2178/jsl/1045861511
- Peter Hertling, Topologische komplexitätsgrade von funktionen mit endlichem bild., Ph.D. thesis, Fernuniversität Hagen, 1993.
- Daisuke Ikegami, Philipp Schlicht, and Hisao Tanaka, Borel subsets of the real line and continuous reducibility, Fund. Math. 244 (2019), no. 3, 209–241. MR 3893424, DOI 10.4064/fm644-10-2018
- 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
- Alexander S. Kechris, Benedikt Löwe, and John R. Steel (eds.), Wadge degrees and projective ordinals. The Cabal Seminar. Volume II, Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012. MR 2906066
- 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
- Takayuki Kihara, Topological reducibilities for discontinuous functions and their structures, arXiv:1906.10573, 2021, To appear in Israel J. Math.
- Takayuki Kihara and Antonio Montalbán, The uniform Martin’s conjecture for many-one degrees, Trans. Amer. Math. Soc. 370 (2018), no. 12, 9025–9044. MR 3864404, DOI 10.1090/tran/7519
- 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
- Antonio Montalbán, Martin’s conjecture: a classification of the naturally occurring Turing degrees, Notices Amer. Math. Soc. 66 (2019), no. 8, 1209–1215. MR 3967172
- Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093, DOI 10.1090/surv/155
- Luca Motto Ros, Borel-amenable reducibilities for sets of reals, J. Symbolic Logic 74 (2009), no. 1, 27–49. MR 2499419, DOI 10.2178/jsl/1231082301
- Luca Motto Ros, Philipp Schlicht, and Victor Selivanov, Wadge-like reducibilities on arbitrary quasi-Polish spaces, Math. Structures Comput. Sci. 25 (2015), no. 8, 1705–1754. MR 3417077, DOI 10.1017/S0960129513000339
- V. L. Selivanov, The quotient algebra of labeled forests with respect to $h$-equivalence, Algebra Logika 46 (2007), no. 2, 217–243 (Russian, with Russian summary); English transl., Algebra Logic 46 (2007), no. 2, 120–133. MR 2356524, DOI 10.1007/s10469-007-0011-5
- Victor Selivanov, Towards a descriptive theory of $\rm cb_0$-spaces, Math. Structures Comput. Sci. 27 (2017), no. 8, 1553–1580. MR 3724463, DOI 10.1017/S0960129516000177
- Victor Selivanov, $Q$-Wadge degrees as free structures, Computability 9 (2020), no. 3-4, 327–341. MR 4133719, DOI 10.3233/COM-180241
- Victor L. Selivanov, Hierarchies of $\Delta ^0_2$-measurable $k$-partitions, MLQ Math. Log. Q. 53 (2007), no. 4-5, 446–461. MR 2351943, DOI 10.1002/malq.200710011
- Victor L. Selivanov, Extending Wadge theory to $k$-partitions, Unveiling dynamics and complexity, Lecture Notes in Comput. Sci., vol. 10307, Springer, Cham, 2017, pp. 387–399. MR 3678767, DOI 10.1007/978-3-319-58741-7_{3}6
- Stephen G. Simpson, Bqo-theory and Fraïssé’s conjecture, Chapter 9 of R. Mansfield, G. Weitkamp. Recursive aspects of descriptive set theory. Oxford University Press, New York, 1985.
- Fons van Engelen, Arnold W. Miller, and John Steel, Rigid Borel sets and better quasi-order theory, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 199–222. MR 891249, DOI 10.1090/conm/065/891249
- William Wilfred Wadge, Reducibility and determinateness on the Baire space, ProQuest LLC, Ann Arbor, MI, 1983. Thesis (Ph.D.)–University of California, Berkeley. MR 2633374
Bibliographic Information
- Takayuki Kihara
- Affiliation: Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University, Nagoya 464-8601, Japan
- MR Author ID: 892476
- ORCID: 0000-0002-1611-952X
- Email: kihara@i.nagoya-u.ac.jp
- Victor Selivanov
- Affiliation: A. P. Ershov Institute of Informatics Systems, SB Russian Academy of Sciences, Lavrentyev av. 6, 630090 Novosibirsk, Russia
- MR Author ID: 195695
- Email: vseliv@iis.nsk.su
- Received by editor(s): July 14, 2020
- Received by editor(s) in revised form: November 28, 2021
- Published electronically: April 7, 2022
- Additional Notes: The first author was partially supported by JSPS KAKENHI Grant 19K03602, 21H03392, the JSPS Core-to-Core Program (A. Advanced Research Networks), and the JSPS-RFBR Bilateral Program (Grant JPJSBP120204809). The research of the second author was supported by RFBR-JSPS Grant 20-51-50001.
- Communicated by: Vera Fischer
- © Copyright 2022 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 150 (2022), 3989-4003
- MSC (2020): Primary 03E15; Secondary 03D55
- DOI: https://doi.org/10.1090/proc/15930
- MathSciNet review: 4446246