• Search

×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

### System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

During this period, the E-commerce and registration of new users may not be available for up to 6 hours.
No Access

# Turing degrees in Polish spaces and decomposability of Borel functions

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore–Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture.

AMSC: 03E15, 54H05, 03D80

## References

• 1. A. Andretta, The SLO principle and the Wadge hierarchy, in Foundations of the Formal Sciences V, Studies in Logic (London), Vol. 11 (College Publication, London, 2007), pp. 11–38. Google Scholar
• 2. V. Brattka, Effective Borel measurability and reducibility of functions. MLQ Math. Log. Q. 51(1) (2005) 19–44. ISI
• 3. R. Carroy and B. Miller, Open graphs, Hurewicz-style dichotomies, and the Jayne–Rogers theorem, submitted (2015). Google Scholar
• 4. R. Carroy and B. Miller, Sigma-continuity with closed witnesses, submitted (2015). Google Scholar
• 5. S. Barry Cooper, Computability Theory (Chapman & Hall/CRC, Boca Raton, FL, 2004). Google Scholar
• 6. G. Debs, Effective decomposition of $σ$-continuous Borel functions, Fund. Math. 224(2) (2014) 187–202. ISI
• 7. J. E. Jayne, The space of class $α$ Baire functions, Bull. Amer. Math. Soc. 80 (1974) 1151–1156. ISI
• 8. J. E. Jayne and C. A. Rogers, Borel isomorphisms at the first level. I, Mathematika 26(1) (1979) 125–156. Google Scholar
• 9. J. E. Jayne and C. A. Rogers, First level Borel functions and isomorphisms, J. Math. Pures Appl. (9) 61(2) (1982) 177–205. Google Scholar
• 10. M. Kačena, L. Motto Ros and B. Semmes, Some observations on ‘A new proof of a theorem of Jayne and Rogers’, Real Anal. Exchange 38(1) (2012/2013) 121–132. Google Scholar
• 11. I. Sh. Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log. 3(2) (2003) 257–267. Google Scholar
• 12. A. S. KechrisY. N. Moschovakis, (eds.) Cabal Seminar 76–77, Lecture Notes in Mathematics, Vol. 689 (Springer, Berlin, 1978). Google Scholar
• 13. T. Kihara, Decomposing Borel functions using the Shore–Slaman join theorem, Fund. Math. 230(1) (2015) 1–13. ISI
• 14. T. Kihara and A. Pauly, Point degree spectra of represented spaces, submitted (2015). Google Scholar
• 15. A. Louveau, A separation theorem for $Σ11$ sets, Trans. Amer. Math. Soc. 260(2) (1980) 363–378. ISI
• 16. D. A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968) 687–689. ISI
• 17. J. S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69(2) (2004) 555–584. ISI
• 18. Y. N. Moschovakis, Descriptive Set Theory, 2nd edn., Mathematical Surveys and Monographs, Vol. 155 (American Mathematical Society, Providence, RI, 2009). Google Scholar
• 19. L. Motto Ros, On the structure of finite level and $ω$-decomposable Borel functions, J. Symbolic Logic 78(4) (2013) 1257–1287. ISI
• 20. A. Pauly and M. de Brecht, Non-deterministic computation and the Jayne Rogers theorem, preprint (2012), arXiv:1404:0079. Google Scholar
• 21. J. Pawlikowski and M. Sabok, Decomposing Borel functions and structure at finite levels of the Baire hierarchy, Ann. Pure Appl. Logic 163(12) (2012) 1748–1764. ISI
• 22. G. E. Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic (Springer-Verlag, Berlin, 1990). Google Scholar
• 23. B. Semmes, A game for the Borel functions, Ph. D. thesis, ILLC, University of Amsterdam, Amsterdam, Holland (2009). Google Scholar
• 24. R. A. Shore and T. A. Slaman, Defining the Turing jump, Math. Res. Lett. 6(5–6) (1999) 711–722. ISI
• 25. T. A. Slaman, Aspects of the Turing jump, in Logic Colloquium 2000, Lecture Notes in Logic, Vol. 19 (Association Symbolic Logic Urbana, IL, 2005), pp. 365–382. Google Scholar
• 26. T. A. Slaman and J. R. Steel, Definable functions on degrees, in Cabal Seminar 81–85, Lecture Notes in Mathematics Vol. 1333 (Springer, Berlin, 1988), pp. 37–55. Google Scholar
• 27. S. Solecki, Decomposing Borel sets and functions and the structure of Baire class $1$ functions, J. Amer. Math. Soc. 11(3) (1998) 521–550. ISI
• 28. J. R. Steel, A classification of jump operators, J. Symbolic Logic 47(2) (1982) 347–358. ISI
Published: 4 June 2020