{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T04:28:04Z","timestamp":1648960084860},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2110,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004497_inline01\" \/>. the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200004497_inline01\" \/>. and in fact that these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice.<\/jats:p>","DOI":"10.2178\/jsl\/1208359059","type":"journal-article","created":{"date-parts":[[2008,4,16]],"date-time":"2008-04-16T19:50:47Z","timestamp":1208375447000},"page":"543-558","source":"Crossref","is-referenced-by-count":3,"title":["On the structure of the Medvedev lattice"],"prefix":"10.1017","volume":"73","author":[{"given":"Sebastiaan A.","family":"Terwijn","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200004497_ref015","unstructured":"Sorbi Andrea and Terwijn Sebastiaan A. , Intermediate logics and factors of the Medvedev lattice, to appear in Annals of Pure and Applied Logic ."},{"key":"S0022481200004497_ref006","first-page":"1328","article-title":"On strong and weak reducibility of algorithmic problems","volume":"4","author":"Muchnik","year":"1963","journal-title":"Sibirskii Mathematicheskii Zhurnal"},{"key":"S0022481200004497_ref002","doi-asserted-by":"publisher","DOI":"10.1070\/SM1976v030n03ABEH002277"},{"key":"S0022481200004497_ref012","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1107959497"},{"key":"S0022481200004497_ref007","volume-title":"Classical recursion theory, I","volume":"125","author":"Odifreddi","year":"1989"},{"key":"S0022481200004497_ref005","first-page":"194","article-title":"Negative answer to the problem of reducibility in the theory of algorithms","volume":"108","author":"Muchnik","year":"1956","journal-title":"Doklady Akademii Nauk SSSR (N.S.)"},{"key":"S0022481200004497_ref003","volume-title":"Set theory: An introduction to independence proofs","author":"Kunen","year":"1983"},{"key":"S0022481200004497_ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629167.015"},{"key":"S0022481200004497_ref013","first-page":"831","volume":"55","author":"Sorbi","year":"1990","journal-title":"Some remarks on the algebraic structure of the Medvedev lattice"},{"key":"S0022481200004497_ref009","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":"S0022481200004497_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-003-0195-x"},{"key":"S0022481200004497_ref004","first-page":"501","article-title":"Degrees of difficulty of the mass problems","volume":"104","author":"Medvedev","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200004497_ref008","volume-title":"Classical recursion theory, II","volume":"143","author":"Odifreddi","year":"1999"},{"key":"S0022481200004497_ref010","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200004497_ref011","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19610070109"},{"key":"S0022481200004497_ref016","unstructured":"Terwijn Sebastiaan A. , The finite intervals of the Muchnik lattice, posted on arXiv, 06 28, 2006."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200004497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:32:33Z","timestamp":1556667153000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200004497\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["S0022481200004497"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1208359059","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}