{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:20:30Z","timestamp":1775809230928,"version":"3.50.1"},"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":10511,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1985,6]]},"abstract":"<jats:p>When dealing with axiomatic theories from a recursion-theoretic point of view, the notion of r.e. preordering naturally arises. We agree that an <jats:italic>r.e. preorder<\/jats:italic> is a pair <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200032734_inline1\"\/> = \u3008<jats:italic>P<\/jats:italic>, \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub>\u3009 such that <jats:italic>P<\/jats:italic> is an r.e. subset of the set of natural numbers (denoted by <jats:italic>\u03c9<\/jats:italic>), \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub> is a preordering on <jats:italic>P<\/jats:italic> and the set {\u3008;<jats:italic>x, y<\/jats:italic>\u3009: <jats:italic>x<\/jats:italic> \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub><jats:italic>y<\/jats:italic>} is r.e.. Indeed, if <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200032734_inline2\"\/> is an axiomatic theory, the provable implication of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200032734_inline2\"\/> yields a preordering on the class of (G\u00f6del numbers of) formulas of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200032734_inline2\"\/>.<\/jats:p><jats:p>Of course, if \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub> is a preordering on <jats:italic>P<\/jats:italic>, then it yields an equivalence relation ~<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub> on <jats:italic>P<\/jats:italic>, by simply letting <jats:italic>x<\/jats:italic> ~<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub><jats:italic>y<\/jats:italic> iff <jats:italic>x<\/jats:italic> \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub><jats:italic>y<\/jats:italic> and <jats:italic>y<\/jats:italic> \u2264<jats:sub><jats:italic>P<\/jats:italic><\/jats:sub><jats:italic>x<\/jats:italic>. Hence, in the case of <jats:italic>P<\/jats:italic> = <jats:italic>\u03c9<\/jats:italic>, any preordering yields an equivalence relation on <jats:italic>\u03c9<\/jats:italic> and consequently a numeration in the sense of [4]. It is also clear that any equivalence relation on <jats:italic>\u03c9<\/jats:italic> (hence any numeration) can be regarded as a preordering on <jats:italic>\u03c9<\/jats:italic>. In view of this connection, we sometimes apply to the theory of preorders some of the concepts from the theory of numerations (see also Er\u0161ov [6]).<\/jats:p><jats:p>Our main concern will be in applications of these concepts to logic, in particular as regards sufficiently strong axiomatic theories (essentially the ones in which recursive functions are representable). From this point of view it seems to be of some interest to study some remarkable prelattices and Boolean prealgebras which arise from such theories. It turns out that these structures enjoy some rather surprising lattice-theoretic and universal recursion-theoretic properties.<\/jats:p><jats:p>After making our main definitions in \u00a71, we examine universal recursion-theoretic properties of some r.e. prelattices in \u00a72.<\/jats:p>","DOI":"10.2307\/2274228","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:13:30Z","timestamp":1146953610000},"page":"397-406","source":"Crossref","is-referenced-by-count":13,"title":["Universal recursion theoretic properties of r.e. preordered structures"],"prefix":"10.1017","volume":"50","author":[{"given":"Franco","family":"Montagna","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":[[2014,3,12]]},"reference":[{"key":"S0022481200032734_ref011","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200032734_ref005","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210164"},{"key":"S0022481200032734_ref006","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/malq.19770231902","article-title":"Theorie der Numerierungen. III","volume":"23","author":"Er\u0161ov","year":"1977","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"S0022481200032734_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71123-6"},{"key":"S0022481200032734_ref003","first-page":"529","volume":"48","author":"Bernardi","year":"1983","journal-title":"Classifying positive equivalence relations"},{"key":"S0022481200032734_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF01837553"},{"key":"S0022481200032734_ref013","first-page":"259","volume-title":"To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism","author":"Visser","year":"1980"},{"key":"S0022481200032734_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19730191901"},{"key":"S0022481200032734_ref010","volume-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik","author":"Montagna"},{"key":"S0022481200032734_ref007","volume-title":"Lattice theory","author":"Gr\u00e4tzer","year":"1971"},{"key":"S0022481200032734_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF00284977"},{"key":"S0022481200032734_ref002","volume-title":"Fundamenta Mathematicae","author":"Bernardi"},{"key":"S0022481200032734_ref008","doi-asserted-by":"crossref","first-page":"141","DOI":"10.4064\/fm-61-2-141-163","article-title":"Deduction preserving recursive isomorphism between theories","volume":"61","author":"Kripke","year":"1967","journal-title":"Fundamenta Mathematicae"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200032734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T22:35:55Z","timestamp":1558564555000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200032734\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,6]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,6]]}},"alternative-id":["S0022481200032734"],"URL":"https:\/\/doi.org\/10.2307\/2274228","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,6]]}}}