Mathematical Logic Quarterly 51 (1):19-44 (2005)
AbstractThe investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level
Added to PP
Historical graph of downloads
Citations of this work
Effective Choice and Boundedness Principles in Computable Analysis.Vasco Brattka & Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (1):73-117.
Searching for an Analogue of Atr0 in the Weihrauch Lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
The Bolzano–Weierstrass Theorem is the Jump of Weak Kőnig’s Lemma.Vasco Brattka, Guido Gherardi & Alberto Marcone - 2012 - Annals of Pure and Applied Logic 163 (6):623-655.
Closed Choice and a Uniform Low Basis Theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
Weihrauch Degrees, Omniscience Principles and Weak Computability.Vasco Brattka & Guido Gherardi - 2011 - Journal of Symbolic Logic 76 (1):143 - 176.
Similar books and articles
Borel Reducibility and Hölder(Α) Embeddability Between Banach Spaces.Longyun Ding - 2012 - Journal of Symbolic Logic 77 (1):224-244.
Bi-Borel Reducibility of Essentially Countable Borel Equivalence Relations.Greg Hjorth - 2005 - Journal of Symbolic Logic 70 (3):979 - 992.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Cofinal Families of Borel Equivalence Relations and Quasiorders.Christian Rosendal - 2005 - Journal of Symbolic Logic 70 (4):1325-1340.
Borel Reducibility and Classification of von Neumann Algebras.Román Sasyk & Asger Törnquist - 2009 - Bulletin of Symbolic Logic 15 (2):169-183.
A Borel Reducibility Theory for Classes of Countable Structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Borel Structures and Borel Theories.Greg Hjorth & André Nies - 2011 - Journal of Symbolic Logic 76 (2):461 - 476.
Monotone Reducibility and the Family of Infinite Sets.Douglas Cenzer - 1984 - Journal of Symbolic Logic 49 (3):774-782.
Borel Reducibility and Finitely Hölder (Α) Embeddability.Longyun Ding - 2011 - Annals of Pure and Applied Logic 162 (12):970-980.
Comparing Borel Reducibility and Depth of an Ω-Stable Theory.Martin Koerwien - 2009 - Notre Dame Journal of Formal Logic 50 (4):365-380.