World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
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

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

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


    • 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. Crossref, ISIGoogle Scholar
    • 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. Crossref, ISIGoogle Scholar
    • 7. J. E. Jayne, The space of class α Baire functions, Bull. Amer. Math. Soc. 80 (1974) 1151–1156. Crossref, ISIGoogle Scholar
    • 8. J. E. Jayne and C. A. Rogers, Borel isomorphisms at the first level. I, Mathematika 26(1) (1979) 125–156. Crossref, ISIGoogle 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. CrossrefGoogle Scholar
    • 11. I. Sh. Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log. 3(2) (2003) 257–267. LinkGoogle Scholar
    • 12. A. S. KechrisY. N. Moschovakis, (eds.) Cabal Seminar 76–77, Lecture Notes in Mathematics, Vol. 689 (Springer, Berlin, 1978). CrossrefGoogle Scholar
    • 13. T. Kihara, Decomposing Borel functions using the Shore–Slaman join theorem, Fund. Math. 230(1) (2015) 1–13. Crossref, ISIGoogle Scholar
    • 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. ISIGoogle Scholar
    • 16. D. A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968) 687–689. Crossref, ISIGoogle Scholar
    • 17. J. S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69(2) (2004) 555–584. Crossref, ISIGoogle Scholar
    • 18. Y. N. Moschovakis, Descriptive Set Theory, 2nd edn., Mathematical Surveys and Monographs, Vol. 155 (American Mathematical Society, Providence, RI, 2009). CrossrefGoogle Scholar
    • 19. L. Motto Ros, On the structure of finite level and ω-decomposable Borel functions, J. Symbolic Logic 78(4) (2013) 1257–1287. Crossref, ISIGoogle Scholar
    • 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. Crossref, ISIGoogle Scholar
    • 22. G. E. Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic (Springer-Verlag, Berlin, 1990). CrossrefGoogle 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. Crossref, ISIGoogle Scholar
    • 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. CrossrefGoogle 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. Crossref, ISIGoogle Scholar
    • 28. J. R. Steel, A classification of jump operators, J. Symbolic Logic 47(2) (1982) 347–358. Crossref, ISIGoogle Scholar