Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T07:40:24.981Z Has data issue: false hasContentIssue false

EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS

Published online by Cambridge University Press:  12 July 2019

URI ANDREWS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USA E-mail: andrews@math.wisc.edu URL: http://www.math.wisc.edu/andrews/
ANDREA SORBI
Affiliation:
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE E SCIENZE MATEMATICHE UNIVERSITÀ DI SIENA SIENA, I-53100, ITALY E-mail: andrea.sorbi@unisi.it URL: http://www3.diism.unisi.it/sorbi/
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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$ where ω denotes the set of natural numbers and the following four conditions hold: (1) $\wedge , \vee$ are binary computable operations; (2) ${ \le _L}$ is a computably enumerable preordering relation, with $0{ \le _L}x{ \le _L}1$ for every x; (3) the equivalence relation ${ \equiv _L}$ originated by ${ \le _L}$ is a congruence on L such that the corresponding quotient structure is a nontrivial bounded lattice; (4) the ${ \equiv _L}$-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 if L is an e.i. prelattice then ${ \le _L}$ is universal with respect to all c.e. preordering relations, i.e., for every c.e. preordering relation R there exists a computable function f reducing R to ${ \le _L}$, i.e., $xRy$ if and only if $f\left( x \right){ \le _L}f\left( y \right)$, for all $x,y$. In fact (Corollary 5.3) ${ \le _L}$ is locally universal, i.e., for every pair $a{ < _L}b$ and every c.e. preordering relation R one can find a reducing function f from R to ${ \le _L}$ such that the range of f is contained in the interval $\left\{ {x:a{ \le _L}x{ \le _L}b} \right\}$. Also (Theorem 5.7) ${ \le _L}$ is uniformly dense, i.e., there exists a computable function f such that for every $a,b$ if $a{ < _L}b$ then $a{ < _L}f\left( {a,b} \right){ < _L}b$, and if $a{ \equiv _L}a\prime$ and $b{ \equiv _L}b\prime$ then $f\left( {a,b} \right){ \equiv _L}f\left( {a\prime ,b\prime } \right)$. Some consequences and applications of these results are discussed: in particular (Corollary 7.2) for $n \ge 1$ the c.e. preordering relation on ${{\rm{\Sigma }}_n}$ sentences yielded by the relation of provable implication of any c.e. consistent extension of Robinson’s system R or Q 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.

Information

Type
Research Article
Copyright
© Association for Symbolic Logic 2019