{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T09:40:03Z","timestamp":1775468403722,"version":"3.50.1"},"reference-count":8,"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":15717,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1971,3]]},"abstract":"<jats:p>A pair of sets (<jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub>) forms a <jats:italic>minimal pair<\/jats:italic> if <jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub> and <jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub> are nonrecursive, and if whenever a set <jats:italic>B<\/jats:italic> is recursive both in <jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub> and in <jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub> then <jats:italic>B<\/jats:italic> is recursive. C. E. M. Yates [8] and independently A. H. Lachlan [4] proved the existence of a minima] pair of <jats:italic>recursively enumerable (r.e.)<\/jats:italic> sets thereby establishing a conjecture of G. E. Sacks [6]. We simplify Lachlan's construction, and then generalize this result by constructing two disjoint pairs of r.e. sets (<jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>B<\/jats:italic><jats:sub>0<\/jats:sub>) and (<jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>B<\/jats:italic><jats:sub>1<\/jats:sub>) such that if <jats:italic>C<\/jats:italic><jats:sub>0<\/jats:sub> separates (<jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>C<\/jats:italic><jats:sub>1<\/jats:sub> separates (<jats:italic>B<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>B<\/jats:italic><jats:sub>1<\/jats:sub>), then <jats:italic>C<\/jats:italic><jats:sub>0<\/jats:sub> and <jats:italic>C<\/jats:italic><jats:sub>1<\/jats:sub> form a minimal pair. (We say that <jats:italic>C<\/jats:italic> separates (<jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>A<\/jats:italic><jats:sub>1<\/jats:sub>) if <jats:italic>A<\/jats:italic><jats:sub>0<\/jats:sub> \u2282 <jats:italic>C<\/jats:italic> and <jats:italic>C<\/jats:italic> \u2229 = <jats:italic>\u2205<\/jats:italic>.) The question arose in our study of (Turing) degrees of members of certain <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200083948_inline1\"\/> classes, where we proved the weaker result [2, Theorem 4.1] that the above pairs may be chosen so that <jats:italic>C<\/jats:italic><jats:sub>0<\/jats:sub> and <jats:italic>C<\/jats:italic><jats:sub>2<\/jats:sub> are merely Turing incomparable. (There we used a variation of the weaker result to improve a result of Scott and Tennenbaum that no complete extension of Peano arithmetic has minimal degree.)<\/jats:p>","DOI":"10.2307\/2271516","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:05:56Z","timestamp":1146949556000},"page":"66-78","source":"Crossref","is-referenced-by-count":14,"title":["A minimal pair of \u03a0<sub>1<\/sub><sup>0<\/sup> classes"],"prefix":"10.1017","volume":"36","author":[{"suffix":"Jr","given":"Carl G.","family":"Jockusch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert I.","family":"Soare","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200083948_ref004","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-16.1.537"},{"key":"S0022481200083948_ref005","volume-title":"Theory of recursive functions and effective computabttity","author":"Rogers","year":"1967"},{"key":"S0022481200083948_ref002","unstructured":"Jockusch C. G. Jr. , and Soare R. I. , \u03a01 0 classes and degrees of theories (to appear)."},{"key":"S0022481200083948_ref007","first-page":"233","article-title":"Degrees of models","volume":"25","author":"Shoenheld","year":"1960","journal-title":"this Journal"},{"key":"S0022481200083948_ref006","volume-title":"Annals of mathematics studies","author":"Sacks","year":"1963"},{"key":"S0022481200083948_ref003","unstructured":"Jockusch C. G. Jr. , and Soare R. I. , Degrees of members of \u03a01 0 classes (to appear)."},{"key":"S0022481200083948_ref008","first-page":"159","volume":"31","author":"Yates","year":"1966","journal-title":"A minimal pair of r.e. degrees"},{"key":"S0022481200083948_ref001","unstructured":"Friedman H. , Borel sets and hyperdegrees (to appear)."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200083948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T20:20:11Z","timestamp":1559334011000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200083948\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1971,3]]},"references-count":8,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1971,3]]}},"alternative-id":["S0022481200083948"],"URL":"https:\/\/doi.org\/10.2307\/2271516","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1971,3]]}}}