{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T10:21:40Z","timestamp":1772446900399,"version":"3.50.1"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":1107,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u0151nig's Lemma and hence to the Hahn\u2013Banach 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.<\/jats:p>","DOI":"10.2178\/jsl\/1294170993","type":"journal-article","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T15:22:35Z","timestamp":1294154555000},"page":"143-176","source":"Crossref","is-referenced-by-count":62,"title":["Weihrauch degrees, omniscience principles and weak computability"],"prefix":"10.1017","volume":"76","author":[{"given":"Vasco","family":"Brattka","sequence":"first","affiliation":[]},{"given":"Guido","family":"Gherardi","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200002024_ref030","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"S0022481200002024_ref018","volume-title":"Classical recursion theory","volume":"125","author":"Odifreddi","year":"1989"},{"key":"S0022481200002024_ref028","volume-title":"The degrees of discontinuity of some translators between representations of the real numbers","author":"Weihrauch","year":"1992"},{"key":"S0022481200002024_ref017","unstructured":"Mylatz Uwe , Vergleich unstetiger Funktionen: \u201cPrinciple of Omniscience\u201d und Vollst\u00e4ndigkeit in der C\u2013hierarchic, Ph.D. thesis, Faculty for Mathematics and Computer Science, University H\u00e4gen, Germany, 2006."},{"key":"S0022481200002024_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310125"},{"key":"S0022481200002024_ref019","volume-title":"Mathematical Logic Quarterly","author":"Pauly"},{"key":"S0022481200002024_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1951-0042109-4"},{"key":"S0022481200002024_ref007","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1294186663"},{"key":"S0022481200002024_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61667-9"},{"key":"S0022481200002024_ref003","first-page":"224","volume-title":"Proceedings of the 26th international symposium on Mathematical Foundations of Computer Science 2001, Mari\u00e1nsk\u00e9 L\u00e1zn\u00e9, Czech Republic, August 27\u201331, 2001","volume":"2136","author":"Brattka","year":"2001"},{"key":"S0022481200002024_ref005","doi-asserted-by":"publisher","DOI":"10.1137\/060658023"},{"key":"S0022481200002024_ref006","first-page":"83","volume-title":"Proceedings of the sixth international conference on Computability and Complexity in Analysis, CCA 2009","author":"Brattka","year":"2009"},{"key":"S0022481200002024_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00693-X"},{"key":"S0022481200002024_ref009","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565663"},{"key":"S0022481200002024_ref010","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2009-018"},{"key":"S0022481200002024_ref011","unstructured":"Hertling Peter , Unstetigkeitsgrade von Funktionen in der effektiven Analysis, Dissertation, FernUniversit\u00e4t Hagen, Hagen, 11 1996."},{"key":"S0022481200002024_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73001-9_38"},{"key":"S0022481200002024_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90213-W"},{"key":"S0022481200002024_ref016","volume-title":"Vergleich unstetiger Funktionen in der Analysis","author":"Mylatz","year":"1992"},{"key":"S0022481200002024_ref020","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200002024_ref022","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200610012"},{"key":"S0022481200002024_ref023","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710001"},{"key":"S0022481200002024_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00121-X"},{"key":"S0022481200002024_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59971-2"},{"key":"S0022481200002024_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00109-8"},{"key":"S0022481200002024_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200002024_ref027","volume-title":"Vergleich nicht konstruktiv l\u00f6sbarer Probleme in der Analysis","author":"von Stein","year":"1989"},{"key":"S0022481200002024_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2740-3_37"},{"key":"S0022481200002024_ref029","volume-title":"The TTE-interpretation of three hierarchies of omniscience principles","volume":"130","author":"Weihrauch","year":"1992"},{"key":"S0022481200002024_ref031","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310001"},{"key":"S0022481200002024_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00095-4"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200002024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T15:24:29Z","timestamp":1556378669000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200002024\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S0022481200002024"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1294170993","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}