{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T03:32:00Z","timestamp":1648697520553},"reference-count":13,"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":4302,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2002,6]]},"abstract":"Let {We<\/jats:sub><\/jats:italic>}e<\/jats:italic>\u2208\u03c9<\/jats:italic><\/jats:sub> be a standard enumeration of the recursively enumerable (r. e.) subsets of \u03c9<\/jats:italic> = {0, 1, 2, \u2026}. The lattice of recursively enumerable sets, is the structure ({We<\/jats:sub><\/jats:italic>}e<\/jats:italic>\u2208\u03c9<\/jats:italic><\/jats:sub>, \u222a, \u2229). is the sublattice of consisting of the recursive sets.<\/jats:p>Suppose is a lattice of subsets of \u03c9<\/jats:italic>. \u2261 is said to be a congruence relation on if \u2261 is an equivalence relation on and if for all U<\/jats:italic>, U\u2032<\/jats:italic> \u2208 and V<\/jats:italic>, V<\/jats:italic> \u2208 , if U<\/jats:italic> \u2261 U<\/jats:italic>\u2032 and V<\/jats:italic> \u2261 V<\/jats:italic>\u2032 then U<\/jats:italic> \u222a U<\/jats:italic>\u2032 \u2261 V<\/jats:italic> \u222a V<\/jats:italic>\u2032 and U<\/jats:italic> \u2229 U<\/jats:italic>\u2032 \u2261 V<\/jats:italic> \u2229 V<\/jats:italic>\u2032. [U<\/jats:italic>] = {V<\/jats:italic> \u2208 | V<\/jats:italic> \u2261 U<\/jats:italic>} is the equivalence class of U<\/jats:italic>. If \u2261 is a congruence relation on , the elements of the quotient lattice \/ \u2261 are the equivalence classes of \u2261. [U<\/jats:italic>] \u222a [V<\/jats:italic>] is defined as [U<\/jats:italic> \u222a V<\/jats:italic>], and [U<\/jats:italic>] \u2229 [V<\/jats:italic>] is defined as [U<\/jats:italic> \u2229 V<\/jats:italic>].<\/jats:p>The quotient lattices of (or of some sublattice ) correspond naturally with the congruence relations which give rise to them, and in turn the congruence relations of sublattices of can be characterized in part by their computational complexity. The aim of the present paper is to characterize congruence relations in some of the most important complexity classes.<\/jats:p>","DOI":"10.2178\/jsl\/1190150093","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T14:13:31Z","timestamp":1197555211000},"page":"497-504","source":"Crossref","is-referenced-by-count":0,"title":["Congruence relations on lattices of recursively enumerable sets"],"prefix":"10.1017","volume":"67","author":[{"given":"Todd","family":"Hammond","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200009579_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(82)90016-X"},{"key":"S0022481200009579_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BF01670108"},{"key":"S0022481200009579_ref006","unstructured":"Harrington L. , The lattice of r. e. sets is undecidable (again), handwritten notes, 1983."},{"key":"S0022481200009579_ref005","first-page":"1177","volume":"58","author":"Hammond","year":"1993","journal-title":"Nonisomorphism of lattices of recursively enumerable sets"},{"key":"S0022481200009579_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90007-5"},{"key":"S0022481200009579_ref004","unstructured":"Hammond T. , Friedberg splittings in \u03a33 0 congruence lattices E, in preparation."},{"key":"S0022481200009579_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0704618-2"},{"key":"S0022481200009579_ref009","doi-asserted-by":"publisher","DOI":"10.4064\/fm-90-1-45-52"},{"key":"S0022481200009579_ref010","first-page":"173","volume":"32","author":"Owings","year":"1967","journal-title":"Recursion, metarecursion, and inclusion"},{"key":"S0022481200009579_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200009579_ref011","volume-title":"The inclusion lattice and degrees of unsolvability of the recursively enumerable sets","author":"Robinson","year":"1966"},{"key":"S0022481200009579_ref003","first-page":"309","volume":"23","author":"Friedberg","year":"1958","journal-title":"Three theorems on recursive enumeration: I. Decomposition, II. Maximal set, III. Enumeration without duplication"},{"key":"S0022481200009579_ref007","unstructured":"Harrington L. , Lachlan A. H. , Maass W. , and Soare R. I. , Algebraic properties of low2 computable sets, in preparation."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200009579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T21:06:05Z","timestamp":1557176765000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200009579\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,6]]}},"alternative-id":["S0022481200009579"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1190150093","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}