{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T21:15:34Z","timestamp":1655068534129},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2384,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005181_inline2\" \/> subsets of 2<jats:sup>\u03c9<\/jats:sup> and Kolmogorov complexity play a major role in the proof.<\/jats:p>","DOI":"10.2178\/jsl\/1191333852","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T11:25:04Z","timestamp":1198063504000},"page":"1003-1018","source":"Crossref","is-referenced-by-count":3,"title":["\u03a0<sub>1<\/sub><sup>0<\/sup> classes and strong degree spectra of relations"],"prefix":"10.1017","volume":"72","author":[{"given":"John","family":"Chisholm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer","family":"Chubb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentina S.","family":"Harizanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis R.","family":"Hirschfeldt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"Carl G.","family":"Jockusch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy","family":"McNicholl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Pingrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200005181_ref037","volume-title":"Recursively enumerable sets and degrees. A study of computable functions and computably generated sets","author":"Soare","year":"1987"},{"key":"S0022481200005181_ref035","volume-title":"Classical recursion theory","author":"Odifreddi","year":"1989"},{"key":"S0022481200005181_ref027","first-page":"33","article-title":"classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200005181_ref026","first-page":"1205","volume":"49","author":"Jockusch","year":"1984","journal-title":"Pseudojump operators IT. transfinite iterations, hierarchies and minimal covers"},{"key":"S0022481200005181_ref023","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1305\/ndjfl\/1071505769","article-title":"Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures","volume":"43","author":"Hirschfeldt","year":"2002","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200005181_ref021","first-page":"441","volume":"66","author":"Hirschfeldt","year":"2001","journal-title":"Degree spectra of intrinsically ce. relations"},{"key":"S0022481200005181_ref020","doi-asserted-by":"publisher","DOI":"10.2307\/421207"},{"key":"S0022481200005181_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00056-0"},{"key":"S0022481200005181_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90049-R"},{"key":"S0022481200005181_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90097-6"},{"key":"S0022481200005181_ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629167.005"},{"key":"S0022481200005181_ref012","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1215\/ijm\/1256069291","article-title":"degrees and transfer theorems","volume":"31","author":"Downey","year":"1987","journal-title":"Illinois Journal of Mathematics"},{"key":"S0022481200005181_ref032","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200008)46:3<393::AID-MALQ393>3.0.CO;2-H"},{"key":"S0022481200005181_ref010","unstructured":"Downey R. , Greenberg N. , and Weber R. , Totally \u03c9-computably enumerable degrees I: bounding critical triples, submitted."},{"key":"S0022481200005181_ref034","first-page":"512","article-title":"A refinement of lown and highn for the r.e. degrees","volume":"32","author":"Mohrherr","year":"1986","journal-title":"Zeitschrift f\u00fcr matematische Logik und Grundlagen der Mathematik"},{"key":"S0022481200005181_ref009","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635924"},{"key":"S0022481200005181_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-005-0288-9"},{"key":"S0022481200005181_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90014-0"},{"key":"S0022481200005181_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00011-5"},{"key":"S0022481200005181_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0022481200005181_ref024","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0220595-7"},{"key":"S0022481200005181_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90067-9"},{"key":"S0022481200005181_ref013","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025971406116"},{"key":"S0022481200005181_ref019","first-page":"65","volume-title":"Contemporary mathematics","author":"Harizanov","year":"2000"},{"key":"S0022481200005181_ref006","unstructured":"Bickford M. and Mills C. F. , Lowness properties of r.e. sets, unpublished preprint."},{"key":"S0022481200005181_ref028","first-page":"178","article-title":"Solutions of the Goncharov\u2013Millar and degree spectra problems in the theory of computable models","volume":"61","author":"Khoussainov","year":"2000","journal-title":"Doklady Mathematics"},{"key":"S0022481200005181_ref003","first-page":"26","volume-title":"Aspects of effective algebra","author":"Ash","year":"1981"},{"key":"S0022481200005181_ref025","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1969.30.67"},{"key":"S0022481200005181_ref022","first-page":"697","volume":"67","author":"Hirschfeldt","year":"2002","journal-title":"Degree spectra of relations on computable structures in the presence of  isomorphisms"},{"key":"S0022481200005181_ref002","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S0022481200005181_ref029","first-page":"149","volume-title":"Stacs 2006: Twenty-Third Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23\u201325, 2006, Proceedings","author":"Kjos-Hanssen"},{"key":"S0022481200005181_ref015","first-page":"55","article-title":"On the spectrum of degrees of decidable relations","volume":"55","author":"Goncharov","year":"1997","journal-title":"Doklady Mathematics"},{"key":"S0022481200005181_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00014-1"},{"key":"S0022481200005181_ref033","unstructured":"Mohrherr J. , Index sets and truth-table degrees in recursion theory, PhD Dissertation, University of Illinois at Chicago, 1982."},{"key":"S0022481200005181_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0086116"},{"key":"S0022481200005181_ref008","first-page":"975","volume":"54","author":"Cenzer","year":"1989","journal-title":"On the ranked points of a  set"},{"key":"S0022481200005181_ref030","first-page":"621","article-title":"Analysis of the Cantor-Bendixson Theorem by means of the analytic hierarchy","volume":"7","author":"Kreisel","year":"1959","journal-title":"Bulletin de l'Acad\u00e9mie Polonaise des Sciences"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200005181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T17:20:24Z","timestamp":1556731224000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200005181\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["S0022481200005181"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1191333852","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}