Weihrauch degrees, omniscience principles and weak computability. (English) Zbl 1222.03071

This paper is a sequel to [G. Gherardi and A. Marcone, Notre Dame J. Formal Logic 50, No. 4, 393–425 (2009; Zbl 1223.03052)]. The abstract that the authors give is very adequate: “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 semilattice. It turns out that parallelization is a closure operator for this semilattice 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.”


03F60 Constructive and recursive analysis
03B30 Foundations of classical theories (including reverse mathematics)
03D30 Other degrees and reducibilities in computability and recursion theory
03D45 Theory of numerations, effectively presented structures
03E15 Descriptive set theory


Zbl 1223.03052
Full Text: DOI arXiv Link


[1] DOI: 10.1002/malq.200310001 · Zbl 1018.03049
[2] DOI: 10.1002/malq.200710001 · Zbl 1111.03322
[3] Mathematical Logic Quarterly
[4] Classical recursion theory 125 (1989)
[5] DOI: 10.1002/malq.200610012 · Zbl 1110.03059
[6] DOI: 10.1016/S0304-3975(01)00109-8 · Zbl 1042.68050
[7] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[8] Varieties of constructive mathematics 97 (1987)
[9] DOI: 10.1016/S0304-3975(02)00693-X · Zbl 1071.03027
[10] DOI: 10.2178/bsl/1294186663 · Zbl 1226.03062
[11] Proceedings of the sixth international conference on Computability and Complexity in Analysis, CCA 2009 pp 83– (2009)
[12] DOI: 10.1137/060658023 · Zbl 1165.03052
[13] DOI: 10.1002/malq.200310125 · Zbl 1059.03074
[14] Proceedings of the 26th international symposium on Mathematical Foundations of Computer Science 2001, Mariánské Lázné, Czech Republic, August 27–31, 2001 2136 pp 224– (2001)
[15] DOI: 10.1016/S0304-3975(98)00095-4 · Zbl 0915.68047
[16] Constructive analysis 279 (1985) · Zbl 0656.03042
[17] Vergleich unstetiger Funktionen in der Analysis (1992)
[18] DOI: 10.1090/S0002-9947-1951-0042109-4
[19] DOI: 10.1016/0168-0072(93)90213-W · Zbl 0795.03086
[20] Computation and logic in the real world, CiE 2007 4497 pp 368– (2007)
[21] From topology to computation: Proceedings of the Smalefest (New York) pp 395– (1993)
[22] DOI: 10.1215/00294527-2009-018 · Zbl 1223.03052
[23] The TTE-interpretation of three hierarchies of omniscience principles 130 (1992)
[24] The degrees of discontinuity of some translators between representations of the real numbers (1992)
[25] Vergleich nicht konstruktiv lösbarer Probleme in der Analysis (1989)
[26] Recursively enumerable sets and degrees (1987)
[27] Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[28] DOI: 10.1016/S0168-0072(01)00121-X · Zbl 1016.03064
[29] Computable analysis (2000) · Zbl 0956.68056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.