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.

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

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

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)

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

We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...) equivalence relations and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations. (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)

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

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.

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)

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)

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)