|
|
Effective Borel Measurability and Reducibility of Functions
Vasco Brattka, in: Computability and Complexity in Analysis, Informatik-Bericht 302, FernUniversität in Hagen, 2003
Abstract
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.
Electronical Versions