{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:09:16Z","timestamp":1772514556578,"version":"3.50.1"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":4976,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p>The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.<\/jats:p><jats:p>We will work in the structure of the computably enumerable sets. The language is just inclusion, \u2286. This structure is called \u03b5.<\/jats:p><jats:p>All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.<\/jats:p><jats:p>We will also consider the quotient structure \u03b5 modulo the ideal of finite sets, \u03b5*. \u03b5* is a definable quotient structure of \u03b5 since \u201c\u03a7 is finite\u201d is definable in \u03b5; \u201c\u03a7 is finite\u201d iff all subsets of \u03a7 are computable (it takes a little computability theory to show if \u03a7 is infinite then \u03a7 has an infinite non-computable subset). We use A* to denote the equivalent class of A under the ideal of finite sets.<\/jats:p>","DOI":"10.2307\/421206","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T03:13:57Z","timestamp":1146971637000},"page":"185-196","source":"Crossref","is-referenced-by-count":6,"title":["Definable Encodings in the Computably Enumerable Sets"],"prefix":"10.1017","volume":"6","author":[{"given":"Peter A.","family":"Cholak","sequence":"first","affiliation":[]},{"given":"Leo A.","family":"Harrington","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600006570_ref012","first-page":"179","volume-title":"Logic, methodology and philosophy of science, VIII","author":"Herrmann","year":"1989"},{"key":"S1079898600006570_ref013","first-page":"431","volume":"33","author":"Lachlan","year":"1968","journal-title":"Degrees of recursively enumerable sets which have no maximal supersets"},{"key":"S1079898600006570_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-96-00181-6"},{"key":"S1079898600006570_ref020","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19660120125"},{"key":"S1079898600006570_ref025","unstructured":"Wald Kevin [1999], Automorphism and noninvariant properties of the computably enumerable sets, Ph.D. thesis , University of Chicago."},{"key":"S1079898600006570_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600006570_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/0541"},{"key":"S1079898600006570_ref005","unstructured":"Cholak Peter and Harrington Leo A. [n.d.b], Definable encodings in the computably enumerable sets, submitted, draft available."},{"key":"S1079898600006570_ref016","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1980.87.135"},{"key":"S1079898600006570_ref011","first-page":"66","volume-title":"Frege conference","author":"Herrmann","year":"1984"},{"key":"S1079898600006570_ref018","first-page":"51","volume":"49","author":"Maass","year":"1984","journal-title":"On the orbit of hyperhypersimple sets"},{"key":"S1079898600006570_ref022","first-page":"695","volume":"41","author":"Shoenfield","year":"1976","journal-title":"Degrees of classes of recursively enumerable sets"},{"key":"S1079898600006570_ref023","doi-asserted-by":"publisher","DOI":"10.2307\/1970842"},{"key":"S1079898600006570_ref008","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1687"},{"key":"S1079898600006570_ref003","unstructured":"Cholak Peter , Downey Rod , and Harrington Leo A. [n.d.], Automorphisms of the computably enumerable sets: -completeness, in preparation."},{"key":"S1079898600006570_ref014","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0227009-1"},{"key":"S1079898600006570_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0704618-2"},{"key":"S1079898600006570_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760850"},{"key":"S1079898600006570_ref001","unstructured":"Cholak Peter [1994], Notes on 3 theorems by Leo Harrington, handwritten notes."},{"key":"S1079898600006570_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761377"},{"key":"S1079898600006570_ref007","unstructured":"Harrington Leo A. [1983], The undecidability of the lattice of recursively enumerable sets, handwritten notes."},{"key":"S1079898600006570_ref021","first-page":"1097","volume-title":"Handbook of Boolean algebras","volume":"3","author":"Remmel","year":"1989"},{"key":"S1079898600006570_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(96)83748-1"},{"key":"S1079898600006570_ref009","first-page":"199","volume":"2","author":"Harrington","year":"1996","journal-title":"Definability, automorphisms, and dynamic properties of computably enumerable sets"},{"key":"S1079898600006570_ref004","unstructured":"Cholak Peter and Harrington Leo A. [n.d.a], -automorphisms of the computably enumerable sets, in preparation."}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600006570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T17:17:09Z","timestamp":1557335829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600006570\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,6]]}},"alternative-id":["S1079898600006570"],"URL":"https:\/\/doi.org\/10.2307\/421206","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}