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 everyx; (3) the equivalence relation${ \equiv _L}$originated by${ \le _L}$is a congruence onLsuch 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 ifLis an e.i. prelattice then${ \le _L}$is universal with respect to all c.e. preordering relations, i.e., for every c.e. preordering relationRthere exists a computable functionfreducingRto${ \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 relationRone can find a reducing functionffromRto${ \le _L}$such that the range offis 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 functionfsuch 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 systemRorQis 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. (shrink)

The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...) jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$. (shrink)

It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self-full degrees. We show that the poset can be embedded as an initial segment of the degrees of ceers with infinitely many (...) classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice as an initial segment of the degrees of ceers with infinitely many classes. (shrink)

This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called “computable reducibility”), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation (...) of the natural numbers). We observe, e.g., that every ceer is isomorphic to the word problem of some c.e. semigroup, but (answering a question of Gao and Gerdes) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is it in the same reducibility degree of some non‐periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphism type as the word problem of some non‐commutative and non‐Boolean c.e. ring. (shrink)

We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .