On the structure of the Wadge degrees of bqo-valued Borel functions

Kihara, Takayuki; Montalbán, Antonio

doi:10.1090/tran/7621

On the structure of the Wadge degrees of bqo-valued Borel functions
HTML articles powered by AMS MathViewer

by Takayuki Kihara and Antonio Montalbán PDF

Trans. Amer. Math. Soc. 371 (2019), 7885-7923 Request permission

Abstract:

In this article, we give a full description of the Wadge degrees of Borel functions from $\omega ^\omega$ to a better-quasi-ordering $\mathcal {Q}$. More precisely, for any countable ordinal $\xi$, we show that the Wadge degrees of $\mathbf {\Delta }^0_{1+\xi }$-measurable functions $\omega ^\omega \to \mathcal {Q}$ can be represented by countable joins of the $\xi$th transfinite nests of $\mathcal {Q}$-labeled well-founded trees.

References

Alexander C. Block, Operations on a Wadge-type hierarchy of ordinal-valued functions, Master’s thesis, Universiteit van Amsterdam, 2014.
Adam Day, Rod Downey, and Linda B. Westrick, Reducibilities for discontinuous functions, unpublished, 2017.
J. Duparc, Wadge hierarchy and Veblen hierarchy, part II: Borel sets of infinite rank, unpublished.
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
Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
P. Hertling, Unstetigkeitsgrade von Funktionen in der effectiven Analysis, Ph. D. thesis, FernUniversität Hagen, Informatik-Berichte 208 (1996).
Takayuki Kihara, Ordinal ranks on the Baire and non-Baire class functions, unpublished, 2017.
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 and Antonio Montalbán, The uniform Martin’s conjecture for many-one degrees, to appear in Trans. Amer. Math. Soc.
Richard Laver, Better-quasi-orderings and a class of trees, Studies in foundations and combinatorics, Adv. in Math. Suppl. Stud., vol. 1, Academic Press, New York-London, 1978, pp. 31–48. MR 520553
Alain Louveau and Jean Saint-Raymond, On the quasi-ordering of Borel linear orders under embeddability, J. Symbolic Logic 55 (1990), no. 2, 537–560. MR 1056369, DOI 10.2307/2274645
John M. Macintyre, Transfinite extensions of Friedberg’s completeness criterion, J. Symbolic Logic 42 (1977), no. 1, 1–10. MR 491099, DOI 10.2307/2272313
Alberto Marcone and Antonio Montalbán, The Veblen functions for computability theorists, J. Symbolic Logic 76 (2011), no. 2, 575–602. MR 2830417, DOI 10.2178/jsl/1305810765
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
Richard and Weitkamp Mansfield Galen, Recursive aspects of descriptive set theory, with with a chapter by Stephen Simpson, Oxford University Press, New York, 1985.
C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697–720. MR 175814, DOI 10.1017/s0305004100039062
V. L. Selivanov, Hierarchies of hyperarithmetic sets and functions, Algebra i Logika 22 (1983), no. 6, 666–692, 720 (Russian). MR 781399
V. L. Selivanov, Fine hierarchies and Boolean terms, J. Symbolic Logic 60 (1995), no. 1, 289–317. MR 1324514, DOI 10.2307/2275522
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 Selivanov, A fine hierarchy of $\omega$-regular $k$-partitions, Models of computation in context, Lecture Notes in Comput. Sci., vol. 6735, Springer, Heidelberg, 2011, pp. 260–269. MR 2843646, DOI 10.1007/978-3-642-21875-0_{2}8
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 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 \cite{Mansfield-Weitkamp}, 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
Robert Van Wesep, Wadge degrees and descriptive set theory, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77) Lecture Notes in Math., vol. 689, Springer, Berlin, 1978, pp. 151–170. MR 526917
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