We provide an introduction to methods and recent results on infinitely generated abelian groups with decidable word problem.

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) .

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...) definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...) A special focus of our work is on the existence of infima and suprema of c-degrees. (shrink)

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)

We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

We introduce agreement reducibility and highlight its major features. Given subsets A and B of, we write if there is a total computable function satisfying for all,.We shall discuss the central role plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on based on set‐agreement. We end by describing the (...) origin of agreement reducibility and presenting some results in that context. (shrink)

We prove that for any computable successor ordinal of the form α = δ + 2k there exists computable torsion-free abelian group that is relatively Δα0 -categorical and not Δα−10 -categorical. Equivalently, for any such α there exists a computable TFAG whose initial segments are uniformly described by Σαc infinitary computable formulae up to automorphism, and there is no syntactically simpler family of formulae that would capture these orbits. As far as we know, the problem of finding such optimal examples (...) of Δα0-categorical TFAGs for arbitrarily large α was first raised by Goncharov at least 10 years ago, but it has resisted solution 315–356]). As a byproduct of the proof, we introduce an effective functor that transforms a 0″-computable worthy labeled tree into a computable TFAG. We expect that this techni... (shrink)