{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:56:50Z","timestamp":1772445410298,"version":"3.50.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":10328,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1985,12]]},"abstract":"<jats:p>For sets of natural numbers <jats:italic>A<\/jats:italic> and <jats:italic>B, A<\/jats:italic> is enumeration reducible to <jats:italic>B<\/jats:italic> if there is some effective algorithm which when given any enumeration of <jats:italic>B<\/jats:italic> will produce an enumeration of <jats:italic>A<\/jats:italic>. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib <jats:bold>0<\/jats:bold>. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0\u2033 is an upper bound for the minimal pair constructed in \u00a71, and in \u00a72 we improve this bound to any \u03a3<jats:sub>2<\/jats:sub>-high \u0394<jats:sub>2<\/jats:sub> degree. In contrast to this we show that every low degree <jats:bold>c<\/jats:bold> bounds a degree <jats:bold>a<\/jats:bold> which is not in any minimal pair bounded by <jats:bold>c<\/jats:bold>. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In \u00a73 we show that if <jats:bold>a, b<\/jats:bold> is any minimal pair of co-r.e. degrees such that <jats:bold>a<\/jats:bold> is low then <jats:bold>a, b<\/jats:bold> is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0\u2032. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In \u00a74 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings.<\/jats:p><jats:p>As usual, {<jats:italic>W<jats:sub>i<\/jats:sub><\/jats:italic>}<jats:sub><jats:italic>i<\/jats:italic> \u2208 <jats:italic>\u03c9<\/jats:italic><\/jats:sub> is the standard listing of the recursively enumerable sets, <jats:italic>D<jats:sub>u<\/jats:sub><\/jats:italic> is the finite set with canonical index <jats:italic>u<\/jats:italic> and {\u2039 <jats:italic>m, n<\/jats:italic> \u203a}<jats:sub><jats:italic>m, n<\/jats:italic> \u2208 <jats:italic>\u03c9<\/jats:italic><\/jats:sub> is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.<\/jats:p>","DOI":"10.2307\/2273985","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:15:32Z","timestamp":1146953732000},"page":"983-1001","source":"Crossref","is-referenced-by-count":34,"title":["On minimal pairs of enumeration degrees"],"prefix":"10.1017","volume":"50","author":[{"given":"Kevin","family":"McEvoy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Barry","family":"Cooper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200031960_ref004","first-page":"503","volume":"49","author":"Cooper","year":"1984","journal-title":"Partial degrees and the density problem. Part 2: The enumeration degrees of the \u03a32 sets are dense"},{"key":"S0022481200031960_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/042\/791052"},{"key":"S0022481200031960_ref016","volume-title":"Recursively enumerable sets anddegees","author":"Soare"},{"key":"S0022481200031960_ref013","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200031960_ref007","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-16.1.537"},{"key":"S0022481200031960_ref011","first-page":"839","volume":"50","author":"McEvoy","year":"1985","journal-title":"Jumps of quasi-minimal enumeration degrees"},{"key":"S0022481200031960_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90003-9"},{"key":"S0022481200031960_ref002","first-page":"655","volume":"39","author":"Cooper","year":"1974","journal-title":"Minimal pairs and high recursively enumerable degrees"},{"key":"S0022481200031960_ref003","first-page":"854","volume":"47","author":"Cooper","year":"1982","journal-title":"Partial degrees and the density problem"},{"key":"S0022481200031960_ref005","unstructured":"Gutteridge L. , Some results on enumeration reducibility, Ph.D. Dissertation, Simon Fraser University, Burnaby, 1971. (Abstract: Dissertation Abstracts International , vol. 33B (1972), pp. 319B\u2013320B.)"},{"key":"S0022481200031960_ref006","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S0022481200031960_ref008","first-page":"150","volume-title":"Conference in Mathematical Logic\u2013London 1970","volume":"255","author":"Lachlan","year":"1972"},{"key":"S0022481200031960_ref009","unstructured":"Lagemann J. , Embedding theorems in the reducibility ordering of the partial degrees, Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1972."},{"key":"S0022481200031960_ref012","unstructured":"McEvoy K. , On the structure of the enumeration degrees, Ph.D. Thesis, University of Leeds, Leeds. 1984."},{"key":"S0022481200031960_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S0022481200031960_ref014","first-page":"71","volume-title":"Recursive functions","author":"Rozinas","year":"1978"},{"key":"S0022481200031960_ref017","doi-asserted-by":"publisher","DOI":"10.2307\/1969604"},{"key":"S0022481200031960_ref018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170131"},{"key":"S0022481200031960_ref019","first-page":"159","volume":"31","author":"Yates","year":"1966","journal-title":"A minimal pair of recursively enumerable degrees"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200031960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T20:55:37Z","timestamp":1558558537000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200031960\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["S0022481200031960"],"URL":"https:\/\/doi.org\/10.2307\/2273985","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}