{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:53:16Z","timestamp":1760028796423},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T00:00:00Z","timestamp":1562889600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>We study effectively inseparable (abbreviated as e.i.) prelattices (i.e., structures of the form$L = \\langle \\omega , \\wedge , \\vee ,0,1,{ \\le _L}\\rangle$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>where\u03c9<\/jats:italic>denotes the set of natural numbers and the following four conditions hold: (1)$\\wedge , \\vee$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>are binary computable operations; (2)${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is a computably enumerable preordering relation, with$0{ \\le _L}x{ \\le _L}1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>for everyx<\/jats:italic>; (3) the equivalence relation${ \\equiv _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>originated by${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is a congruence onL<\/jats:italic>such that the corresponding quotient structure is a nontrivial bounded lattice; (4) the${ \\equiv _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-equivalence classes of 0 and 1 form an effectively inseparable pair of sets). Solving a problem in (Montagna & Sorbi, 1985) we show (Theorem 4.2), that ifL<\/jats:italic>is an e.i. prelattice then${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is universal with respect to all c.e. preordering relations, i.e., for every c.e. preordering relationR<\/jats:italic>there exists a computable functionf<\/jats:italic>reducingR<\/jats:italic>to${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, i.e.,$xRy$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>if and only if$f\\left( x \\right){ \\le _L}f\\left( y \\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for all$x,y$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In fact (Corollary 5.3)${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is locally universal, i.e., for every pair$a{ < _L}b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and every c.e. preordering relationR<\/jats:italic>one can find a reducing functionf<\/jats:italic>fromR<\/jats:italic>to${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>such that the range off<\/jats:italic>is contained in the interval$\\left\\{ {x:a{ \\le _L}x{ \\le _L}b} \\right\\}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Also (Theorem 5.7)${ \\le _L}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is uniformly dense, i.e., there exists a computable functionf<\/jats:italic>such that for every$a,b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>if$a{ < _L}b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>then$a{ < _L}f\\left( {a,b} \\right){ < _L}b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and if$a{ \\equiv _L}a\\prime$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and$b{ \\equiv _L}b\\prime$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>then$f\\left( {a,b} \\right){ \\equiv _L}f\\left( {a\\prime ,b\\prime } \\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Some consequences and applications of these results are discussed: in particular (Corollary 7.2) for$n \\ge 1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>the c.e. preordering relation on${{\\rm{\\Sigma }}_n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>sentences yielded by the relation of provable implication of any c.e. consistent extension of Robinson\u2019s systemR<\/jats:italic>orQ<\/jats:italic>is locally universal and uniformly dense; and (Corollary 7.3) the c.e. preordering relation yielded by provable implication of any c.e. consistent extension of Heyting Arithmetic is locally universal and uniformly dense.<\/jats:p>","DOI":"10.1017\/s1755020319000273","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T09:50:12Z","timestamp":1562925012000},"page":"838-865","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":6,"title":["EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS"],"prefix":"10.1017","volume":"14","author":[{"given":"URI","family":"ANDREWS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANDREA","family":"SORBI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"S1755020319000273_r16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00284977"},{"key":"S1755020319000273_r5","doi-asserted-by":"publisher","DOI":"10.4064\/fm-124-3-221-233"},{"key":"S1755020319000273_r24","first-page":"82pp","article-title":"Subalgebras of diagonalizable algebras of theories containing arithmetic","volume":"323","author":"Shavrukov","year":"1993","journal-title":"Dissertationes Mathematicae"},{"key":"S1755020319000273_r19","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-00-02652-0"},{"key":"S1755020319000273_r27","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2798754"},{"key":"S1755020319000273_r31","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(82)90024-9"},{"key":"S1755020319000273_r26","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-009-0161-3"},{"key":"S1755020319000273_r28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75462-3"},{"key":"S1755020319000273_r29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1755020319000273_r11","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.001"},{"key":"S1755020319000273_r6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01761704"},{"key":"S1755020319000273_r1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_25"},{"key":"S1755020319000273_r9","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.11"},{"key":"S1755020319000273_r13","volume-title":"Metamathematics of First-Order Arithmetic","author":"Hajek","year":"1998"},{"key":"S1755020319000273_r20","volume-title":"Classical Recursion Theory (Volume II)","volume":"143","author":"Odifreddi","year":"1999"},{"key":"S1755020319000273_r17","doi-asserted-by":"publisher","DOI":"10.2307\/2274228"},{"key":"S1755020319000273_r22","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S1755020319000273_r7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1093\/oso\/9780198538622.003.0008","volume-title":"Logic: From Foundations to Applications, European Logic Colloqium","author":"de Jongh","year":"1996"},{"key":"S1755020319000273_r30","first-page":"259","volume-title":"To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism","author":"Visser","year":"1980"},{"key":"S1755020319000273_r25","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420107"},{"key":"S1755020319000273_r12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.042"},{"key":"S1755020319000273_r14","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.33"},{"key":"S1755020319000273_r4","volume-title":"Distributive Lattices","author":"Balbes","year":"1974"},{"key":"S1755020319000273_r3","first-page":"2","volume-title":"Handbook Proof Theory","author":"Avigad","year":"1998"},{"key":"S1755020319000273_r2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.8"},{"key":"S1755020319000273_r33","first-page":"147","article-title":"Shavrukov\u2019s theorem on the subalgebras of diagonalizable algebras of theories containing $I{{\\rm{\\Delta }}_0} + {\\rm{Exp}}$ .","volume":"34","author":"Zambella","year":"1993","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S1755020319000273_r15","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330106"},{"key":"S1755020319000273_r8","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1327068695"},{"key":"S1755020319000273_r32","unstructured":"Visser, A. (1985). Evaluation, provably deductive equivalence in Heyting Arithmetic of substitution instances of propositional formulas. Logic Group Preprint Series 4, University of Utrecht, Utrecht."},{"key":"S1755020319000273_r23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0755-0_14"},{"key":"S1755020319000273_r21","doi-asserted-by":"publisher","DOI":"10.4064\/fm-61-2-141-163"},{"key":"S1755020319000273_r18","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/042\/791067"},{"key":"S1755020319000273_r10","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1961-022-8"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1755020319000273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T22:32:30Z","timestamp":1721514750000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1755020319000273\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["S1755020319000273"],"URL":"https:\/\/doi.org\/10.1017\/s1755020319000273","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,12]]},"assertion":[{"value":"\u00a9 Association for Symbolic Logic 2019","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}