{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T22:22:04Z","timestamp":1648938124496},"reference-count":7,"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":16082,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1970,3]]},"abstract":"Martin [4, Theorems 1 and 2] proved that a Turing degree a<\/jats:bold> is the degree of a maximal set if, and only if, a\u2032<\/jats:bold> = 0\u2033.<\/jats:bold> Lachlan has shown that maximal sets have minimal many-one degrees [2, \u00a71] and that every nonrecursive r.e. Turing degree contains a minimal many-one degree [2, Theorem 4]. Our aim here is to show that any r.e. Turing degree a<\/jats:bold> of a maximal set contains an infinite number of maximal sets whose many-one degrees are pairwise incomparable; hence such Turing degrees contain an infinite number of distinct minimal many-one degrees. This theorem has been proved by Yates [6, Theorem 5] in the case when a = 0<\/jats:bold>\u2032.<\/jats:p>The need for this theorem first came to our attention as a result of work done by the author [3, Theorem 2.3]. There we looked at the structure \/ obtained from the recursive functions of one variable under the equivalence relation f<\/jats:italic> ~ g<\/jats:italic> if, and only if, f<\/jats:italic>(x<\/jats:italic>) = g<\/jats:italic>(x<\/jats:italic>) a.e., that is, for all but finitely many x<\/jats:italic> \u2208 , where M<\/jats:italic> is a maximal set, and M<\/jats:italic> is its complement. We showed that \/1<\/jats:sub> \u2261 \/2<\/jats:sub> if, and only if, 1<\/jats:sub> =m<\/jats:italic><\/jats:sub>2<\/jats:sub>, i.e., 1<\/jats:sub>. and 2<\/jats:sub> have the same many-one degree. However, it might be possible that some Turing degree of a maximal set contains exactly one many-one degree of a maximal set. Theorem 1 was proved to show that this was not the case, and hence that the theory of \/ is not an invariant of Turing degree.<\/jats:p>","DOI":"10.1017\/s0022481200092197","type":"journal-article","created":{"date-parts":[[2014,3,13]],"date-time":"2014-03-13T12:46:30Z","timestamp":1394714790000},"page":"29-40","source":"Crossref","is-referenced-by-count":4,"title":["Turing degrees and many-one degrees of maximal sets"],"prefix":"10.1017","volume":"35","author":[{"given":"Manuel","family":"Lerman","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200092197_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0241295-4"},{"key":"S0022481200092197_ref007","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19620080313"},{"key":"S0022481200092197_ref005","volume-title":"Annals of mathematics studies","author":"Sacks","year":"1963"},{"key":"S0022481200092197_ref003","unstructured":"Lerman M. , Recursive functions modulo co-maximal sets, Dissertation, Cornell University, Ithaca, N.Y., 1968."},{"key":"S0022481200092197_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19660120125"},{"key":"S0022481200092197_ref001","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S0022481200092197_ref002","unstructured":"Lachlan A. H. , Many-one degrees (unpublished)."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200092197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T19:24:14Z","timestamp":1559417054000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200092197\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1970,3]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1970,3]]}},"alternative-id":["S0022481200092197"],"URL":"http:\/\/dx.doi.org\/10.1017\/s0022481200092197","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":["Logic","Philosophy"],"published":{"date-parts":[[1970,3]]}}}