{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:35:26Z","timestamp":1773149726979,"version":"3.50.1"},"reference-count":10,"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":14802,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1973,9]]},"abstract":"<jats:p>A <jats:italic>standard enumeration<\/jats:italic> of the recursively enumerable (r.e.) sets is an acceptable numbering {<jats:italic>W<jats:sub>n<\/jats:sub><\/jats:italic>}<jats:sub><jats:italic>n<\/jats:italic>\u2208<jats:italic>N<\/jats:italic><\/jats:sub> of the r.e. sets in the sense of Rogers [5, p. 41], together with a 1:1 recursive function <jats:italic>f<\/jats:italic> with range <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200054827_inline01\"\/> In his quest for nonrecursive incomplete r.e. sets Post [4] constructed a hypersimple set <jats:italic>H<jats:sub>f<\/jats:sub><\/jats:italic>, relative to a fixed but unspecified standard enumeration <jats:italic>f<\/jats:italic>. Although it was later shown that hyper-simplicity does not guarantee incompleteness, the ironic possibility remained that Post's own <jats:italic>particular<\/jats:italic> hypersimple set might be incomplete. We settle the question by proving that <jats:italic>H<\/jats:italic>, may be either complete or incomplete depending upon <jats:italic>which<\/jats:italic> standard enumeration <jats:italic>f<\/jats:italic> is used. In contrast, D. A. Martin has shown [3] that Post's <jats:italic>simple<\/jats:italic> set <jats:italic>S<\/jats:italic> [4, p. 298] is complete for <jats:italic>any<\/jats:italic> standard enumeration. Furthermore, what most modern recursion theorists would regard as the \u201cnatural\u201d construction of a hypersimple set (which we give in \u00a71) is also complete for any standard enumeration.<\/jats:p><jats:p>There are two conclusions to be drawn from these results. First, they substantiate the often repeated remark among recursion theorists that Post's hypersimple set construction is a precursor of priority constructions because priorities play a strong role, and because there is a great deal of \u201crestraint\u201d which tends to keep elements out of the set. Secondly, the results warn recursion theorists that more properties than might have been supposed depend upon <jats:italic>which<\/jats:italic> standard enumeration is chosen at the beginning of the construction of some r.e. set.<\/jats:p>","DOI":"10.2307\/2273042","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:24:44Z","timestamp":1146950684000},"page":"446-452","source":"Crossref","is-referenced-by-count":8,"title":["Post's problem and his hypersimple set"],"prefix":"10.1017","volume":"38","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":"S0022481200054827_ref009","volume-title":"Annals of Mathematics","author":"Soare"},{"key":"S0022481200054827_ref006","volume-title":"Annals of Mathematical Studies","author":"Sacks","year":"1966"},{"key":"S0022481200054827_ref003","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1966-0216950-5"},{"key":"S0022481200054827_ref005","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200054827_ref010","first-page":"A","article-title":"Automorphisms of the lattice of recursively enumerable sets. II: Complete sets","volume":"19","author":"Soare","year":"1972","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200054827_ref001","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.40.605"},{"key":"S0022481200054827_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S0022481200054827_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1968-0221933-7"},{"key":"S0022481200054827_ref007","volume-title":"Degrees of unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0022481200054827_ref008","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1972-110-4"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200054827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:37:09Z","timestamp":1559245029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200054827\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1973,9]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1973,9]]}},"alternative-id":["S0022481200054827"],"URL":"https:\/\/doi.org\/10.2307\/2273042","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1973,9]]}}}