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

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
Keywords effective descriptive set theory  Effectively Borel measurable functions  computable analysis
Categories (categorize this paper)
DOI 10.1002/malq.200310125
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,379
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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

Add more references

Citations of this work BETA

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.

View all 22 citations / Add more citations

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 index

Total views
23 ( #495,394 of 2,519,679 )

Recent downloads (6 months)
2 ( #270,824 of 2,519,679 )

How can I increase my downloads?


My notes