{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T00:11:57Z","timestamp":1775520717904,"version":"3.50.1"},"reference-count":4,"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":14346,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1974,12]]},"abstract":"<jats:p>A. H. Lachlan [2] and C. E. M. Yates [4] independently showed that minimal pairs of recursively enumerable (r.e.) degrees exist. Lachlan and Richard Ladner have shown (unpublished) that there is no uniform method for producing a minimal pair of r.e. degrees below a given nonzero r.e. degree. It is not known whether every nonzero r.e. degree bounds a r.e. minimal pair, but in the present paper it is shown (uniformly) that every <jats:italic>high<\/jats:italic> r.e. degree bounds a r.e. minimal pair. (A r.e. degree is said to be <jats:italic>high<\/jats:italic> if it contains a high set in the sense of Robert W. Robinson [3].)<\/jats:p><jats:p>Theorem. <jats:italic>Let <jats:bold>a<\/jats:bold> be a recursively enumerable degree for which <jats:bold>a<\/jats:bold><\/jats:italic>\u2032 = <jats:bold>0<\/jats:bold>\u2033. <jats:italic>Then there are recursively enumerable degrees <jats:bold>b<\/jats:bold><jats:sub>0<\/jats:sub> and <jats:bold>b<\/jats:bold><jats:sub>1<\/jats:sub> such that<\/jats:italic><jats:bold>0<\/jats:bold> &lt; <jats:italic><jats:bold>b<jats:sub>i<\/jats:sub><\/jats:bold><\/jats:italic> &lt; <jats:italic><jats:bold>a<\/jats:bold><\/jats:italic> for each <jats:italic><jats:bold>i<\/jats:bold><\/jats:italic> \u2264 1, <jats:italic>and <jats:bold>b<\/jats:bold><\/jats:italic><jats:sub><jats:bold>0<\/jats:bold><\/jats:sub> \u22c2 <jats:italic><jats:bold>b<\/jats:bold><\/jats:italic><jats:sub><jats:bold>1<\/jats:bold><\/jats:sub> = <jats:bold>0<\/jats:bold>.<\/jats:p><jats:p>The proof is based on the Lachlan minimal r.e. pair construction. For notation see Lachlan [2] or S. B. Cooper [1].<\/jats:p><jats:p>By Robinson [3] we can choose a r.e. representative <jats:italic>A<\/jats:italic> of the degree <jats:italic><jats:bold>a<\/jats:bold><\/jats:italic>, with uniformly recursive tower {<jats:italic>A<\/jats:italic><jats:sub>s<\/jats:sub>, \u2223 <jats:italic>s<\/jats:italic> \u2265 0} of finite approximations to <jats:italic>A<\/jats:italic>, such that <jats:italic>C<\/jats:italic><jats:sub>A<\/jats:sub> dominates every recursive function where<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200077136_eqnU01\"\/><\/jats:disp-formula><\/jats:p><jats:p>We define, stage by stage, finite sets <jats:italic><jats:bold>B<\/jats:bold><jats:sub>i,s<\/jats:sub><\/jats:italic>, <jats:italic>i<\/jats:italic> \u2264 1, <jats:italic>s<\/jats:italic> \u2265 0, in such a way that <jats:italic><jats:bold>B<\/jats:bold><\/jats:italic><jats:sub><jats:italic>i<\/jats:italic>, <jats:italic>s<\/jats:italic> + 1<\/jats:sub> \u2287 <jats:italic><jats:bold>B<\/jats:bold><jats:sub>i,s<\/jats:sub><\/jats:italic> for each <jats:italic>i, s<\/jats:italic>, and {<jats:italic><jats:bold>B<\/jats:bold><jats:sub>i,s<\/jats:sub><\/jats:italic> \u2223 <jats:italic>i<\/jats:italic> \u2264 1, <jats:italic>s<\/jats:italic> \u2265 0} is uniformly recursive.<\/jats:p>","DOI":"10.2307\/2272849","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:32:58Z","timestamp":1146951178000},"page":"655-660","source":"Crossref","is-referenced-by-count":39,"title":["Minimal pairs and high recursively enumerable degrees"],"prefix":"10.1017","volume":"39","author":[{"given":"S. B.","family":"Cooper","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200077136_ref002","first-page":"537\u2013569","article-title":"Lower bounds for pairs of recursively enumerable degrees","volume":"16","author":"Lachlan","year":"1966","journal-title":"Proceedings of the London Mathematical Society"},{"key":"S0022481200077136_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19680142105"},{"key":"S0022481200077136_ref001","first-page":"445\u2013450","article-title":"Minimal upper bounds for sequences of recursively enumerable degrees","volume":"5","author":"Cooper","year":"1972","journal-title":"Journal of the London Mathematical Society"},{"key":"S0022481200077136_ref004","first-page":"158\u2013168","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\/S0022481200077136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T20:42:28Z","timestamp":1559162548000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200077136\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,12]]},"references-count":4,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1974,12]]}},"alternative-id":["S0022481200077136"],"URL":"https:\/\/doi.org\/10.2307\/2272849","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,12]]}}}