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

We study the degree structure of the ω-c.e., n-c.e., and Π10 equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-c.e. and n-computably enumerable equivalence relations. We provide computable enumerations of the degrees of ω-c.e., n-c.e., and Π10 equivalence relations. We prove that for all the degree classes considered, upward density (...) holds and downward density fails. (shrink)

By an unfounded chain for a function f:X→X we mean a sequence nω of elements of X s.t. fxn+1=xn for every n. Unfounded chains can be regarded as a generalization of fixed points, but on the other hand are linked with concepts concerning non-well-founded situations, as ungrounded sentences and the hypergame. In this paper, among other things, we prove a lemma in general topology, we exhibit an extensional recursive function from the set of sentences of PA into itself without an (...) unfounded chain, and we prove that every term in a Magari algebra has an unfounded chain. (shrink)

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)

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...) types of some of these partial orders. (shrink)

In this paper we study the reducibility order m (defined in a natural way) over n 0 -equivalence relations. In particular, for every n> 0 we exhibit n 0 -equivalence relations which are complete with respect to m and investigate some consequences of this fact (see Introduction).

We discuss the effectivity of Arslanov’s completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the effectivity of another extension of the recursion theorem, namely Visser’s ADN theorem, as well as that of a joint generalization of the ADN theorem and Arslanov’s completeness criterion.

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

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)

In this short paper, we analyse whether assuming that mathematical objects are “thin” in Linnebo's sense simplifies the epistemology of mathematics. Towards this end, we introduce the notion of transparency and show that not all thin objects are transparent. We end by arguing that, far from being a weakness of thin objects, the lack of transparency of some thin objects is a fruitful characteristic mark of abstract mathematics.

We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness (...) of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

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)

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

Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers, that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always (...) contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete. (shrink)