{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:52:06Z","timestamp":1772520726478,"version":"3.50.1"},"reference-count":53,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":593,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We survey the theory of Mu\u010dnik (weak) and Medvedev (strong) degrees of subsets of <jats:sup>\u03c9<\/jats:sup>\u03c9 with particular attention to the degrees of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600000123_inline1\"\/> subsets of <jats:sup>\u03c9<\/jats:sup>2. Sections 1\u20136 present the major definitions and results in a uniform notation. Sections 7\u201316 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.<\/jats:p>","DOI":"10.2178\/bsl\/1333560805","type":"journal-article","created":{"date-parts":[[2012,4,4]],"date-time":"2012-04-04T14:17:21Z","timestamp":1333549041000},"page":"161-229","source":"Crossref","is-referenced-by-count":14,"title":["A Survey of Mu\u010dnik and Medvedev Degrees"],"prefix":"10.1017","volume":"18","author":[{"given":"Peter G.","family":"Hinman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600000123_ref018","first-page":"1044","article-title":"Calculus of the weak law of the excluded middle. (Russian)","volume":"32","author":"Jankov","year":"1968","journal-title":"Rossi\u013eskaya Akademiya Nauk Izvestiya. Seriya Matematicheskaya"},{"key":"S1079898600000123_ref019","first-page":"191","volume-title":"Logic, methodology and philosophy of science VIII","author":"Jockusch","year":"1989"},{"key":"S1079898600000123_ref036","doi-asserted-by":"publisher","DOI":"10.2307\/2964680"},{"key":"S1079898600000123_ref032","volume-title":"The mathematics of metamathematics","author":"Rasiowa","year":"1970"},{"key":"S1079898600000123_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S1079898600000123_ref029","first-page":"1328","article-title":"On strong and weak reducibility of algorithmic problems","volume":"4","author":"Muchnlk","year":"1963","journal-title":"Sibirskii Mathematicheskii Zhurnal"},{"key":"S1079898600000123_ref030","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"S1079898600000123_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12898-5"},{"key":"S1079898600000123_ref021","first-page":"33","article-title":"classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S1079898600000123_ref040","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdl015"},{"key":"S1079898600000123_ref012","doi-asserted-by":"publisher","DOI":"10.4249\/scholarpedia.2574"},{"key":"S1079898600000123_ref024","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdp049"},{"key":"S1079898600000123_ref041","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2008-002"},{"key":"S1079898600000123_ref028","first-page":"501","article-title":"Degrees of difficulty of the mass problem","volume":"104","author":"Medvedev","year":"1955","journal-title":"Doklady Akademiya Nauk SSSR"},{"key":"S1079898600000123_ref039","first-page":"352","volume-title":"Reverse mathematics 2001","author":"Simpson","year":"2005"},{"key":"S1079898600000123_ref051","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-005-0278-y"},{"key":"S1079898600000123_ref010","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1096901775"},{"key":"S1079898600000123_ref053","volume-title":"Transactions of the American Mathematical Society","author":"Terwijn"},{"key":"S1079898600000123_ref045","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635751"},{"key":"S1079898600000123_ref047","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629167.015"},{"key":"S1079898600000123_ref046","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19910370905"},{"key":"S1079898600000123_ref048","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.03.002"},{"key":"S1079898600000123_ref001","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn021"},{"key":"S1079898600000123_ref015","unstructured":"Higuchi K. , Effectively closed mass problems and intuitionism, preprint."},{"key":"S1079898600000123_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-009-0150-6"},{"key":"S1079898600000123_ref026","unstructured":"Lewis A. E. M. , Shore R. A. , and Sorbi A. , Topological aspects of the Medvedev lattice, Archive for Mathematical Logic, to appear."},{"key":"S1079898600000123_ref007","first-page":"623","volume-title":"Studies in Logic and the Foundation of Mathematics","volume":"2","author":"Cenzer","year":"1998"},{"key":"S1079898600000123_ref043","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600000123_ref050","unstructured":"Stanford Encyclopedia of Phllosophy, http:\/\/plato.stanford.edu\/entries\/logic-intuitionistic."},{"key":"S1079898600000123_ref038","first-page":"1","volume":"11","author":"Simpson","year":"2005","journal-title":"Mass problems and randomness"},{"key":"S1079898600000123_ref017","doi-asserted-by":"crossref","DOI":"10.1201\/b10690","volume-title":"Fundamentals of mathematical logic","author":"Hinman","year":"2005"},{"key":"S1079898600000123_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-003-0195-x"},{"key":"S1079898600000123_ref013","first-page":"360","article-title":"Certain properties of the Medvedev lattice","volume":"101","author":"Dyment","journal-title":"Rossi\u013eskaya Akademiy Nauk. Matematicheski\u013e Sbornik (NS)"},{"key":"S1079898600000123_ref044","doi-asserted-by":"publisher","DOI":"10.2307\/2274668"},{"key":"S1079898600000123_ref025","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/978-3-642-03073-4_33","volume-title":"Mathematical theory and computational practice","volume":"5635","author":"Lewis"},{"key":"S1079898600000123_ref049","unstructured":"Sorbi A. , Intuitionistic logic and Muchnik degrees, preprint, arXiv: 1003.4489, 2010."},{"key":"S1079898600000123_ref031","first-page":"917","article-title":"A note on the cardinality of the Medvedev lattice","volume":"25","author":"Platek","year":"1970","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S1079898600000123_ref035","unstructured":"Shafer P. , Coding true arithmetic in the Medvedev degrees of classes, preprint."},{"key":"S1079898600000123_ref023","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/IV.14.107"},{"key":"S1079898600000123_ref052","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208359059"},{"key":"S1079898600000123_ref042","first-page":"171","article-title":"Exact interpretation of the intuitionistic propositional calculus by means of an initial segment ofthe Medvedev lattice","volume":"29","author":"Skvortsova","year":"1988","journal-title":"Sibirski\u013e Matematicheski\u013e Zhurnal"},{"key":"S1079898600000123_ref004","first-page":"37","volume-title":"Studies in Logic and the Foundation of Mathematics","volume":"140","author":"Cenzer","year":"1999"},{"key":"S1079898600000123_ref014","unstructured":"FOM (Foundations of Mathematics), online forum archive, http:\/\/www.cs.nyu.edu\/pipermail\/fom\/."},{"key":"S1079898600000123_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-007-0062-2"},{"key":"S1079898600000123_ref037","unstructured":"Simpson S. G. , Natural r.e. degrees; Pi0l classes, FOM Archives: http:\/\/www.cs.nyu.edu\/pipermail\/fom\/1999-August\/003327.html."},{"key":"S1079898600000123_ref034","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1294171000"},{"key":"S1079898600000123_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-002-0166-7"},{"key":"S1079898600000123_ref022","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S1079898600000123_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S1079898600000123_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-007-0058-y"},{"key":"S1079898600000123_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310034"},{"key":"S1079898600000123_ref020","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200041104"},{"key":"S1079898600000123_ref033","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"}],"container-title":["The Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600000123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T16:45:12Z","timestamp":1556210712000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600000123\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["S1079898600000123"],"URL":"https:\/\/doi.org\/10.2178\/bsl\/1333560805","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}