{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T22:41:10Z","timestamp":1698360070628},"reference-count":4,"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":10968,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1984,3]]},"abstract":"<jats:p>An r.e. set <jats:italic>A<\/jats:italic> is <jats:italic>nowhere simple<\/jats:italic> if for every r.e. set <jats:italic>W<\/jats:italic><jats:sub><jats:italic>e<\/jats:italic><\/jats:sub> such that <jats:italic>W<\/jats:italic><jats:sub><jats:italic>e<\/jats:italic><\/jats:sub> \u2212 <jats:italic>A<\/jats:italic> is infinite, there is an infinite r.e. set <jats:italic>W<\/jats:italic> such that <jats:italic>W<\/jats:italic> \u2286 <jats:italic>W<jats:sub>e<\/jats:sub><\/jats:italic> \u2212 <jats:italic>A<\/jats:italic>. The definition of nowhere simple sets is due to <jats:italic>R<\/jats:italic>. Shore in [4]. In [4], Shore studied various properties of nowhere simple sets and showed that they could be used to give an elegant and simple proof of the fact that every nontrivial class of r.e. sets <jats:italic>C<\/jats:italic> closed under recursive isomorphisms is an automorphism base for <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200033995_inline1\" \/>, the lattice of r.e. sets modulo finite sets, (that is, an automorphism <jats:italic>\u03b1<\/jats:italic> of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200033995_inline1\" \/> is completely determined by its action on <jats:italic>C<\/jats:italic>; see Theorem 8 of [4]). Shore also defined the notion of effectively nowhere simple sets.<\/jats:p><jats:p>Definition. An r.e. set <jats:italic>A<\/jats:italic> is <jats:italic>effectively nowhere simple<\/jats:italic> if there is a recursive function <jats:italic>f<\/jats:italic> such that for every <jats:italic>i<\/jats:italic>, <jats:italic>W<\/jats:italic><jats:sub><jats:italic>f(i)<\/jats:italic><\/jats:sub> \u2286 <jats:italic>W<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> \u2212 <jats:italic>A<\/jats:italic> and <jats:italic>W<\/jats:italic><jats:sub><jats:italic>f(i)<\/jats:italic><\/jats:sub> is infinite iff <jats:italic>W<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> \u2212 A is infinite. <jats:italic>f<\/jats:italic> is called a <jats:italic>witness function<\/jats:italic> for <jats:italic>A<\/jats:italic>.<\/jats:p><jats:p>Other than to produce examples of effectively nowhere simple sets and nowhere simple sets that are not effectively nowhere simple, Shore did not concern himself with the properties of effectively nowhere simple sets since he felt that effectively nowhere simple sets were unlikely to be lattice invariant in either <jats:italic>E<\/jats:italic>, the lattice of r.e. sets, or in <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200033995_inline1\" \/>.<\/jats:p>","DOI":"10.2307\/2274096","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:07:02Z","timestamp":1146938822000},"page":"129-136","source":"Crossref","is-referenced-by-count":6,"title":["Effectively nowhere simple sets"],"prefix":"10.1017","volume":"49","author":[{"given":"D.","family":"Miller","sequence":"first","affiliation":[]},{"given":"J. B.","family":"Remmel","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200033995_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0704618-2"},{"key":"S0022481200033995_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0227009-1"},{"key":"S0022481200033995_ref003","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200033995_ref004","first-page":"322","volume":"43","author":"Shore","year":"1978","journal-title":"Nowhere simple sets and the lattice of recursively enumerable sets"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200033995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T17:26:42Z","timestamp":1558632402000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200033995\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,3]]},"references-count":4,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,3]]}},"alternative-id":["S0022481200033995"],"URL":"https:\/\/doi.org\/10.2307\/2274096","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,3]]}}}