{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:39:08Z","timestamp":1774625948021,"version":"3.50.1"},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":13068,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1978,6]]},"abstract":"Ever since Post [4] the structure of recursively enumerable sets and their classification has been an important area in recursion theory. It is also intimately connected with the study of the lattices and of r.e. sets and r.e. sets modulo finite sets respectively. (This lattice theoretic viewpoint was introduced by Myhill [3].) Key roles in both areas have been played by the lattice of r.e. supersets, , of an r.e. set A<\/jats:italic> (along with the corresponding modulo finite sets) and more recently by the group of automorphisms of and . Thus for example we have Lachlan's deep result [1] that Post's notion of A<\/jats:italic> being hyperhypersimple is equivalent to (or ) being a Boolean algebra. Indeed Lachlan even tells us which Boolean algebras appear as \u2014precisely those with \u03a33<\/jats:sub> representations. There are also many other simpler but still illuminating connections between the older typology of r.e. sets and their roles in the lattice . (r<\/jats:italic>-maximal sets for example are just those with completely uncomplemented.) On the other hand, work on automorphisms by Martin and by Soare [8], [9] has shown that most other Post type conditions on r.e. sets such as hypersimplicity or creativeness which are not obviously lattice theoretic are in fact not invariant properties of .<\/jats:p>In general the program of analyzing and classifying r.e. sets has been directed at the simple sets. Thus the subtypes of simple sets studied abound \u2014 between ten and fifteen are mentioned in [5] and there are others \u2014 but there seems to be much less known about the nonsimple sets. The typologies introduced for the nonsimple sets begin with Post's notion of creativeness and add on a few variations. (See [5, \u00a78.7] and the related exercises for some examples.) Although there is a classification scheme for r.e. sets along the simple to creative line (see [5, \u00a78.7]) it is admitted to be somewhat artificial and arbitrary. Moreover there does not seem to have been much recent work on the nonsimple sets.<\/jats:p>","DOI":"10.2307\/2272830","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:47:35Z","timestamp":1146952055000},"page":"322-330","source":"Crossref","is-referenced-by-count":23,"title":["Nowhere simple sets and the lattice of recursively enumerable sets"],"prefix":"10.1017","volume":"43","author":[{"given":"Richard A.","family":"Shore","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200049665_ref009","doi-asserted-by":"publisher","DOI":"10.2307\/1970842"},{"key":"S0022481200049665_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S0022481200049665_ref003","first-page":"220","volume":"21","author":"Myhill","year":"1956","journal-title":"The lattice of recursively enumerable sets"},{"key":"S0022481200049665_ref010","unstructured":"Soare R. I. , Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets (to appear)."},{"key":"S0022481200049665_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0227009-1"},{"key":"S0022481200049665_ref006","volume-title":"Annals of Mathematical Studies","author":"Sacks","year":"1966"},{"key":"S0022481200049665_ref002","article-title":"R-Maximal major subsets","author":"Lerman","journal-title":"Israel Journal of Mathematics"},{"key":"S0022481200049665_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1974-13350-1"},{"key":"S0022481200049665_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1977-0446931-5"},{"key":"S0022481200049665_ref005","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200049665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T19:57:29Z","timestamp":1558987049000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200049665\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,6]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1978,6]]}},"alternative-id":["S0022481200049665"],"URL":"https:\/\/doi.org\/10.2307\/2272830","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,6]]}}}