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 outline the Hrushovsk-Sokolović proof of Vaught's Conjecture for differentially closed fields, focusing on the use of dimensions to code graphs.

This article studies the complexity of decomposability of rings from the perspective of computability. Based on the equivalence between the decomposition of rings and that of the identity of rings, we propose four kinds of rings, namely, weakly decomposable rings, decomposable rings, weakly block decomposable rings, and block decomposable rings. Let R be the index set of computable rings. We study the complexity of subclasses of computable rings, showing that the index set of computable weakly decomposable rings is m-complete Σ10 (...) within R and that the index set of computable decomposable (resp., weakly block decomposable, block decomposable) rings is m-complete Σ20 within R. (shrink)

The main result of this paper states that the isomorphism problem for ω-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies showing that the isomorphism problem for ω-automatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to (...) our main results, we show lower and upper bounds for the isomorphism problem for ω-automatic trees of every finite height: It is decidable , for height 1 , -hard and in for height 3, and - and -hard and in for height . All proofs are elementary and do not rely on theorems from set theory. (shrink)

Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...) classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields. (shrink)

We introduce the notion of finitary computable reducibility on equivalence relations on the domainω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be${\rm{\Pi }}_{n + 2}^0$-complete under computable reducibility, we show that, for everyn, there does exist a natural equivalence relation which is${\rm{\Pi }}_{n + 2}^0$-complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, (...) and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy. (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)

Here we prove that if T and T′ are strongly minimal theories, where T′ satisfies a certain property related to triviality and T does not, and T′ is model complete, then there is no computable embedding of Mod(T) into Mod(T′). Using this, we answer a question from [4], showing that there is no computable embedding of VS into ZS, where VS is the class of infinite vector spaces over Q, and ZS is the class of models of Th(Z, S). Similarly, (...) we show that there is no computable embedding of ACF into ZS, where ACF is the class of algebraically closed fields of characteristic 0. (shrink)