{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:25:44Z","timestamp":1761611144425},"reference-count":31,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T00:00:00Z","timestamp":1101340800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2010valued as well as for multi\u2010valued 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\u2010Srivastava in order to prove a generalization of the Representation Theorem of Kreitz\u2010Weihrauch 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\u2010Hausdorff\u2010Lebesgue 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. (\u00a9 2004 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200310125","type":"journal-article","created":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T08:46:31Z","timestamp":1101372391000},"page":"19-44","source":"Crossref","is-referenced-by-count":59,"title":["Effective Borel measurability and reducibility of functions"],"prefix":"10.1002","volume":"51","author":[{"given":"Vasco","family":"Brattka","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,11,25]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/2045932"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"E.Bishop andD. S.Bridges Constructive Analysis (Springer\u2010Verlag Berlin 1985).","DOI":"10.1007\/978-3-642-61667-9"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00095-4"},{"key":"e_1_2_1_5_2","unstructured":"V.Brattka Recursive and computable operations over topological structures. Informatik Berichte 255 FernUniversit\u00e4t Hagen Fachbereich Informatik Hagen July 1999."},{"key":"e_1_2_1_6_2","unstructured":"V.Brattka Computability of Banach space principles. Informatik Berichte 286 FernUniversit\u00e4t Hagen Fachbereich Informatik Hagen June 2001."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"V.Brattka Computability over topological structures. In: Computability and Models (S. B. Cooper and S. S. Goncharov eds.) pp. 93\u2013136 (Kluwer Academic Publishers New York 2003).","DOI":"10.1007\/978-1-4615-0755-0_5"},{"key":"e_1_2_1_8_2","unstructured":"V.Brattka Plottable real number functions and the computable graph theorem. Informatik Berichte 300 FernUniversit\u00e4t in Hagen Fachbereich Informatik Hagen July 2003."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00693-X"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00286-2"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00069-X"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310003"},{"key":"e_1_2_1_13_2","unstructured":"P.Hertling Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Informatik Berichte 208 FernUniversit\u00e4t Hagen Hagen November 1996."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00098-X"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"A. S.Kechris Classical Descriptive Set Theory (Springer\u2010Verlag Berlin 1995).","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"e_1_2_1_16_2","unstructured":"K.\u2010I.Ko Complexity Theory of Real Functions (Birkh\u00e4user Boston 1991)."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90208-7"},{"key":"e_1_2_1_18_2","first-page":"397","article-title":"A general theorem on selectors","volume":"13","author":"Kuratowski K.","year":"1965","journal-title":"Bulletin de L'Acad\u00e9mie Polonaise des Sciences"},{"key":"e_1_2_1_19_2","unstructured":"Y. N.Moschovakis Descriptive Set Theory (North\u2010Holland Publ. Comp. Amsterdam 1980)."},{"key":"e_1_2_1_20_2","unstructured":"U.Mylatz Vergleich unstetiger Funktionen in der Analysis. Diplomarbeit Fachbereich Informatik FernUniversit\u00e4t Hagen 1992."},{"key":"e_1_2_1_21_2","unstructured":"P.Odifreddi Classical Recursion Theory (North\u2010Holland Publ. Comp. Amsterdam 1989)."},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"M. B.Pour\u2010El andJ. I.Richards Computability in Analysis and Physics (Springer\u2010Verlag Berlin 1989).","DOI":"10.1007\/978-3-662-21717-7"},{"key":"e_1_2_1_23_2","first-page":"141","article-title":"Fonctions bor\u00e9liennes sur un quotient","volume":"100","author":"Saint Raymond J.","year":"1976","journal-title":"Bull. Sci. Math. (2)"},{"key":"e_1_2_1_24_2","unstructured":"M.Schr\u00f6der Topological spaces allowing type 2 complexity theory. In: Computability and Complexity in Analysis (K.\u2010I. Ko and K. Weihrauch eds.) Vol. 190 ofInformatik Berichte FernUniversit\u00e4t Hagen Sept. 1995 pp. 41\u201353."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00109-8"},{"key":"e_1_2_1_26_2","unstructured":"T.v. Stein Vergleich nicht konstruktiv l\u00f6sbarer Probleme in der Analysis. Diplomarbeit Fachbereich Informatik Fern Universit\u00e4t Hagen 1989."},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"K.Weihrauch Computability (Springer\u2010Verlag Berlin 1987).","DOI":"10.1007\/978-3-642-69965-8"},{"key":"e_1_2_1_28_2","unstructured":"K.Weihrauch The degrees of discontinuity of some translators between representations of the real numbers. Technical Report TR\u201092\u2010050 International Computer Science Institute Berkeley July 1992."},{"key":"e_1_2_1_29_2","unstructured":"K.Weihrauch The TTE\u2010interpretation of three hierarchies of omniscience principles. Informatik Berichte 130 FernUniversit\u00e4t Hagen Hagen September 1992."},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","unstructured":"K.Weihrauch Computable Analysis (Springer\u2010Verlag Berlin 2000).","DOI":"10.1007\/978-3-642-56999-9"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310001"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200310125","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200310125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T19:56:46Z","timestamp":1697659006000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200310125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,25]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1002\/malq.200310125"],"URL":"https:\/\/doi.org\/10.1002\/malq.200310125","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,11,25]]}}}