Effective Borel measurability and reducibility of functions

Mathematical Logic Quarterly 51 (1):19-44 (2005)
  Copy   BIBTEX


The 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



    Upload a copy of this work     Papers currently archived: 92,227

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

Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
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.
Measurable chromatic numbers.Benjamin D. Miller - 2008 - Journal of Symbolic Logic 73 (4):1139-1157.


Added to PP

37 (#433,311)

6 months
10 (#275,239)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

[Omnibus Review].Yiannis N. Moschovakis - 1968 - Journal of Symbolic Logic 33 (3):471-472.

Add more references