{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T21:40:56Z","timestamp":1697665256975},"reference-count":20,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2004,4,7]],"date-time":"2004-04-07T00:00:00Z","timestamp":1081296000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2004,5]]},"abstract":"Abstract<\/jats:title>We focus on a particular class of computably enumerable (c. e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering (\u211c\ufe01, \u2264) of c. e. degrees under Turing reducibility. We demonstrate that the latticeM<\/jats:italic>5<\/jats:sub> cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M<\/jats:italic>5<\/jats:sub> can be embedded below every nonlow2<\/jats:sub> degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow2<\/jats:sub> degrees. We note also that there are embeddings of M<\/jats:italic>5<\/jats:sub> in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0<\/jats:bold> but the other four are array noncomputable. (\u00a9 2004 WILEY\u2010VCH Verlag GmbH & Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200310092","type":"journal-article","created":{"date-parts":[[2004,4,7]],"date-time":"2004-04-07T15:02:27Z","timestamp":1081350147000},"page":"219-235","source":"Crossref","is-referenced-by-count":0,"title":["Lattice embeddings and array noncomputable degrees"],"prefix":"10.1002","volume":"50","author":[{"given":"Stephen M.","family":"Walk","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,4,7]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200027961"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00028-8"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90220-8"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"P. A.Cholak R. G.Downey andR. A.Shore Intervals without critical triples. In: Logic Colloquium '95 (J. A. Makowsky and E. V. Ravve eds.) Lecture Notes in Logic11 pp. 17\u201343 (Springer\u2010Verlag Berlin et al. 1998).","DOI":"10.1007\/978-3-662-22108-2_2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90062-7"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"R. G.Downey C. G.Jockusch andM.Stob Array nonrecursive sets and multiple permitting arguments. In: Recursion Theory Week (Proceedings Oberwolfach 1989) (K. Ambos\u2010Spies G. H. M\u00fcller and G. E. Sacks eds.) Lecture Notes in Mathematics 1432 pp. 141\u2013173 (Springer\u2010Verlag Berlin et al. 1990).","DOI":"10.1007\/BFb0086116"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"R. G.Downey C. G.Jockusch andM.Stob Array nonrecursive degrees and genericity. In: Computability Enumerability Unsolvability: Directions in Recursion Theory (S. B. Cooper T. A. Slaman and S. S. Wainer eds.) London Math. Soc. Lecture Series 224 pp. 93\u2013104 (Cambridge University Press Cambridge 1996).","DOI":"10.1017\/CBO9780511629167.005"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762706"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19890350102"},{"key":"e_1_2_1_11_2","unstructured":"C. G.Jockusch Jr. Personal communication 1996."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.2307\/2273510"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268789"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-16.1.537"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"A. H.Lachlan Embedding nondistributive lattices in the recursively enumerable degrees. In: Conference in Mathematical Logic London '70 (W. Hodges ed.) Lecture Notes in Mathematics 255 pp. 149\u2013177 (Springer\u2010Verlag Berlin\u2010Heidelberg 1972).","DOI":"10.1007\/BFb0059544"},{"key":"e_1_2_1_16_2","unstructured":"B.Schaeffer Abstract Complexity Theory and the Degrees of Unsolvability. PhD thesis University of Illinois at Urbana\u2010Champaign 1998."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"R. I.Soare Recursively Enumerable Sets and Degrees (Springer\u2010Verlag New York et al. 1987).","DOI":"10.1007\/978-3-662-02460-7"},{"key":"e_1_2_1_18_2","unstructured":"M.Stob EmbeddingM5. Unpublished handwritten notes 1980."},{"key":"e_1_2_1_19_2","unstructured":"S. M.Walk Toward the Definability of the Array Noncomputable Degrees. PhD thesis University of Notre Dame 1999."},{"key":"e_1_2_1_20_2","unstructured":"B.Weinstein On Embedding of the Lattice 1\u20103\u20101 into the Recursively Enumerable Degrees. PhD thesis University of California at Berkeley 1988."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.2307\/2269807"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200310092","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200310092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T21:04:43Z","timestamp":1697663083000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200310092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,4,7]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,5]]}},"alternative-id":["10.1002\/malq.200310092"],"URL":"https:\/\/doi.org\/10.1002\/malq.200310092","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,4,7]]}}}