Journal of Symbolic Logic 76 (1):143 - 176 (2011)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense
Keywords Computable analysis   constructive analysis   reverse mathematics   effective descriptive set theory
Categories (categorize this paper)
DOI 10.2178/jsl/1294170993
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,410
Through your library

References found in this work BETA

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.

View all 11 references / Add more references

Citations of this work BETA

Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
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 15 citations / Add more citations

Similar books and articles

Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Computability & Unsolvability.Martin Davis - 1958 - Dover Publications.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Stability and Posets.Carl Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693 - 711.
The Degrees of Conditional Problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.


Added to PP index

Total views
14 ( #735,344 of 2,519,855 )

Recent downloads (6 months)
1 ( #406,012 of 2,519,855 )

How can I increase my downloads?


My notes