𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Effective Borel measurability and reducibility of functions

✍ Scribed by Vasco Brattka

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
389 KB
Volume
51
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

Effective Borel degrees of some topologi
Effective Borel degrees of some topological functions
✍ Guido Gherardi 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝ^__n

BOUNDS IN THE TURING REDUCIBILITY OF FUN
BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
✍ Karol Habart; K. Habart 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

## Abstract A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated.

On the stable rank and reducibility in a
On the stable rank and reducibility in algebras of real symmetric functions
✍ R. Rupp; A. Sasane 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB

## Abstract Let __A__~ℝ~(𝔻) denote the set of functions belonging to the disc algebra having real Fourier coefficients. We show that __A__~ℝ~(𝔻) has Bass and topological stable ranks equal to 2, which settles the conjecture made by Brett Wick in [18]. We also give a necessary and sufficient conditi

Borel Partitions of Products of Finite S
Borel Partitions of Products of Finite Sets and the Ackermann Function
✍ Carlos A. Di Prisco; Jimena Llopis; Stevo Todorcevic 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 147 KB

It is shown that for every primitive recursive sequence [m i ] i=0 of positive integers, there is an ackermannic sequence [n i ] i=0 of positive integers such that for every partition of the product > i=0 n i into two Borel pieces, there are sets H i n i with |H i |=m i such that the subproduct > i=

Addendum to the Paper „On the Measurabil
Addendum to the Paper „On the Measurability of Positive Definite and Conditionally Positive Definite Functions”
✍ Zoltán Sasvári 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

Let f be a positive definite function on a locally compact abelian group G. In [3] we showed that measurability of 1 on an open neighbourhood of the zero implies measurability of f on G. As a main tool we used a result about the support of f [3, Th. I]. The aim of this note is to simplify the proof