{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T14:10:52Z","timestamp":1772374252672,"version":"3.50.1"},"reference-count":27,"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":3388,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,12]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>A set <jats:italic>X<\/jats:italic> is <jats:italic>prime bounding<\/jats:italic> if for every complete atomic decidable (CAD) theory <jats:italic>T<\/jats:italic> there is a prime model <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007428_inline1\"\/> of <jats:italic>T<\/jats:italic> decidable in <jats:italic>X<\/jats:italic>. It is easy to see that <jats:italic>X<\/jats:italic> = 0\u2032 is prime bounding. Denisov claimed that every <jats:italic>X<\/jats:italic> &lt;<jats:sub>T<\/jats:sub> 0\u2032 is <jats:italic>not<\/jats:italic> prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets <jats:italic>X<\/jats:italic> \u2264<jats:sub>\u03c4<\/jats:sub> 0\u2032 are exactly the sets which are not low<jats:sub>2<\/jats:sub>. Recall that <jats:italic>X<\/jats:italic> is low<jats:sub>2<\/jats:sub> if <jats:italic>X<\/jats:italic>\u2033 \u2264<jats:sub>\u03c4<\/jats:sub> 0\u2033. To prove that a low<jats:sub>2<\/jats:sub> set <jats:italic>X<\/jats:italic> is <jats:italic>not<\/jats:italic> prime bounding we use a 0\u2032 -computable listing of the array of sets {<jats:italic>Y : Y<\/jats:italic> \u2264<jats:sub>\u03c4<\/jats:sub><jats:italic>X<\/jats:italic> } to build a CAD theory <jats:italic>T<\/jats:italic> which diagonalizes against all potential <jats:italic>X<\/jats:italic>-decidable prime models <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007428_inline1\"\/> of <jats:italic>T<\/jats:italic>, To prove that any <jats:italic>non<\/jats:italic>-low<jats:sub>2<\/jats:sub><jats:italic>X<\/jats:italic> is indeed prime bounding. we fix a function <jats:italic>f<\/jats:italic> \u2264<jats:sub>T<\/jats:sub><jats:italic>X<\/jats:italic> that is not dominated by a certain 0\u2032-computable function that picks out generators of principal types. Given a CAD theory <jats:italic>T<\/jats:italic>. we use <jats:italic>f<\/jats:italic> to eventually find, for every formula <jats:italic>\u03c6<\/jats:italic>(<jats:italic>x\u0304<\/jats:italic>) con sistent with <jats:italic>T<\/jats:italic>. a principal type which contains it. and hence to build an <jats:italic>X<\/jats:italic>-decidable prime model of <jats:italic>T<\/jats:italic>. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory.<\/jats:p>","DOI":"10.2178\/jsl\/1102022214","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:49:47Z","timestamp":1109800187000},"page":"1117-1142","source":"Crossref","is-referenced-by-count":12,"title":["Bounding prime models"],"prefix":"10.1017","volume":"69","author":[{"given":"Barbara F.","family":"Csima","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis R.","family":"Hirschfeldt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia F.","family":"Knight","sequence":"additional","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":"S0022481200007428_ref019","doi-asserted-by":"crossref","first-page":"165\u2013178","DOI":"10.1305\/ndjfl\/1039724885","article-title":"Computable models of theories with few models","volume":"38","author":"Khoussainov","year":"1997","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200007428_ref013","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1972-113-9"},{"key":"S0022481200007428_ref026","volume-title":"Saturated model theory","author":"Sacks","year":"1972"},{"key":"S0022481200007428_ref021","first-page":"289\u2013309","volume-title":"Handbook of recursive mathematics","volume":"138\u2013139","author":"Knight","year":"1998"},{"key":"S0022481200007428_ref018","first-page":"1177\u20131231","volume-title":"Handbook of recursive mathematics","volume":"138\u2013139","author":"Khisamiev","year":"1998"},{"key":"S0022481200007428_ref010","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1182353917"},{"key":"S0022481200007428_ref012","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-01-05923-8"},{"key":"S0022481200007428_ref009","first-page":"3\u2013114","volume-title":"Handbook of recursive mathematics","volume":"138\u2013139","author":"Harizanov","year":"1998"},{"key":"S0022481200007428_ref004","first-page":"430\u2013442","volume":"69","author":"Csima","year":"2004","journal-title":"Degree spectra of prime models"},{"key":"S0022481200007428_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219289"},{"key":"S0022481200007428_ref011","first-page":"305\u2013309","volume":"39","author":"Harrington","year":"1974","journal-title":"Recursively presentable prime models"},{"key":"S0022481200007428_ref016","first-page":"51\u201355","volume-title":"Izvestiya Akademiya Nauk Kazakhstan SSR, Seriya Fiziko-Matematicheskaya","author":"Khisamiev","year":"1981"},{"key":"S0022481200007428_ref015","volume-title":"Infinite Abelian groups","author":"Kaplansky","year":"1954"},{"key":"S0022481200007428_ref025","doi-asserted-by":"crossref","first-page":"307\u2013314","DOI":"10.1305\/ndjfl\/1022615611","article-title":"A new spectrum of recursive models","volume":"40","author":"Nies","year":"1999","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200007428_ref001","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S0022481200007428_ref002","volume-title":"Model theory","volume":"73","author":"Chang","year":"1990"},{"key":"S0022481200007428_ref003","first-page":"107\u2013124","article-title":"On initial segments of computable linear orders","volume":"14","author":"Coles","year":"1998","journal-title":"Order"},{"key":"S0022481200007428_ref005","unstructured":"Csima B. F. , Harizanov V. S. , Hirschfeldt D. R. , and Soare R. I. , Bounding homogeneous models, to appear."},{"key":"S0022481200007428_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF01980232"},{"key":"S0022481200007428_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF00967009"},{"key":"S0022481200007428_ref014","first-page":"33\u201356","article-title":"classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200007428_ref017","first-page":"572\u2013585","article-title":"Theory of abelian groups with constructive models","volume":"27","author":"Khisamiev","year":"1986","journal-title":"Siberian Mathematics Journal"},{"key":"S0022481200007428_ref020","first-page":"1034\u20131042","volume":"51","author":"Knight","year":"1986","journal-title":"Degrees coded in jumps of orderings"},{"key":"S0022481200007428_ref022","first-page":"295\u2013310","article-title":"Classes of recursively enumerable sets and degrees of unsolvability","volume":"12","author":"Martin","year":"1966","journal-title":"Zeitschrift f\u00fcr mathematische Logik unddie Grundlagen der Mathematik"},{"key":"S0022481200007428_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(78)90030-X"},{"key":"S0022481200007428_ref024","first-page":"171\u2013181","volume":"48","author":"Millar","year":"1983","journal-title":"Omitting types, type spectrums, and decidability"},{"key":"S0022481200007428_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T19:38:50Z","timestamp":1557171530000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007428\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12]]}},"alternative-id":["S0022481200007428"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1102022214","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12]]}}}