Equivalence relations in computable model theory

Equivalence relations represent the idea of resemblance between mathematical objects. Objects identified up to an equivalence relation have similar structural properties. From the point of view of computable model theory there are several approaches to study the role of equivalence relations. In the project we address two possible directions. The first approach is connected to the question of algorithmic complexity of various presentations of a structure. To characterize the degrees of isomorphic copies of a given structure, one uses the notion of the degree spectra of a structure. It consists of all the Turing degrees of isomorphic copies of the structure. The degree spectra of structures with various computability and model-theoretic properties have been studied by many authors. More recently the notion of the degree spectrum of a theory was introduced. It consists of all the Turing degrees of the countable models of the theory. We propose a new notion that generalizes the ideas of spectra for structures and for theories. Our spectra consist of all the degrees of structures that are equivalent to a given structure, with respect to an arbitrary chosen equivalence relations. For the current project we consider equivalence relations that are restrictions of the relations of isomorphism, elementary equivalence and bi-embeddability. The main question here is: what are the possible spectra for various equivalence relations? The second approach deals with the problem of complexity of descriptions of equivalence relations. We identify equivalence relations on computable structures with the relations on indices for such structures. We compare their complexity through the computable reducibility which is a two-dimensional version of the standard m-reducibility. We suggest to study the question of representability of arbitrary equivalence relations on the natural numbers through fixed equivalence relations on computable structures. We also propose to study relativizations of the computable reducibility to higher levels of complexity.

Equivalence relations reflect the idea of resemblance between mathematical objects. One of the essential questions is the question of existence, up to an equivalence relation, of mathematical structures with particular properties. Applied to computable structure theory, one investigates whether or not a particular structure has a computable presentation, that is, is equivalent to a computable structure. If not, what are the possible degrees of equivalent presentations of the structure? This question was the main focus of the project. We studied a general notion of degree spectra with respect to equivalence relations, which generalised the existing ideas of the degree spectrum of a structure and a theory. Furthermore, we studied the complexity of functions realizing equivalences between structures, in the spirit of classical approach of computable categoricity. We also investigated the structure of equivalence relations under computable reducibility. Finally, we started a new line of research about on- the-fly classification of structures, up to an equivalence relation, combining ideas from computable structure theory and algorithmic learning.