Equivalence Relations in Computable Model Theory

The stand-alone project "Equivalence Relations in Computable Model Theory" is supported by the Austrian Science Fund FWF under the number P 27527.

Summary

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.

List of publications supported by the project

• D. Rossegger Dino, On functors enumerating structures, Siberian Electronic Mathematical Reports --- Sibirskie Elektronnye Matematicheskie Izvestiya, 14 (2017), pp. 690-702. pdf
• N. Bazhenov, E. Fokina, D. Rossegger, L. San Mauro Computable bi-embeddable categoricity, Algebra Logic 57 (2018), 392--396. pdf
• D. Rossegger Dino, Elementary Bi-embeddability Spectra of Structures, Proceedings of CiE 2018 - Sailing Routes in the World of Computation, Lecture Notes in Computer Science, 10936 (2018), pp. 349--358. pdf
• V. Doskoč Confident iterative learning in computational learning theory Current Trends in Theory and Practice of Computer Science (SOFSEM) 2018, 30--42. pdf
• E. Fokina, T. Kötzing, L. San Mauro. Limit learning equivalence structures, Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98 (2019), 383--403. arXiv
• E.Fokina, D.Rossegger, L. San Mauro, Bi‐embeddability spectra and bases of spectra, Mathematical Logic Quarterly, 65 (2019), 228--236. arXiv
• E. Fokina, D. Rossegger, L. San Mauro Measuring the complexity of reductions between equivalence relations Computability 8 (2019), 265-280. arXiv
• P. Semukhin, D. Turetsky, E. Fokina, Degree Spectra of Structures Relative to Equivalences. Algebra and Logic 58 (2019), 158--172. pdf
• N. Bazhenov, E. Fokina, D. Rossegger, L. San Mauro, Degrees of bi-embeddable categoricity of equivalence structures. Archive for Mathematical Logic, 58 (2019), 543--563. arXiv