Turing degrees in Polish spaces and decomposability of Borel functions

Journal of Mathematical Logic 21 (1):2050021 (2020)
  Copy   BIBTEX

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,569

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555-584.
Quasi-Polish Spaces.Matthew de Brecht - 2013 - Annals of Pure and Applied Logic 164 (3):356-381.
On Turing Degrees of Points in Computable Topology.Iraj Kalantari & Larry Welch - 2008 - Mathematical Logic Quarterly 54 (5):470-482.
Effective Borel Degrees of Some Topological Functions.Guido Gherardi - 2006 - Mathematical Logic Quarterly 52 (6):625-642.
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Martin’s Conjecture and Strong Ergodicity.Simon Thomas - 2009 - Archive for Mathematical Logic 48 (8):749-759.
A Quasi-Order on Continuous Functions.Raphaël Carroy - 2013 - Journal of Symbolic Logic 78 (2):633-648.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Calculus of Variations and Descriptive Set Theory.Nikolaos E. Sofronidis - 2009 - Mathematical Logic Quarterly 55 (5):535-538.
Borel Globalizations of Partial Actions of Polish Groups.H. Pinedo & C. Uzcategui - 2018 - Archive for Mathematical Logic 57 (5-6):617-627.

Analytics

Added to PP
2020-04-30

Downloads
8 (#980,226)

6 months
2 (#278,494)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Definability of the Jump Operator in the Enumeration Degrees.I. Sh Kalimullin - 2003 - Journal of Mathematical Logic 3 (02):257-267.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.

View all 7 references / Add more references