Computable structure theory with respect to equivalence relations

Abstract

In computable structure theory computability theoretic properties of mathematical structures such as graphs, linear orders, or fields are studied. In contrast to the usual sets of natural numbers considered in computability theory, where Turing reducibility paints a clear picture of their information content, in the case of structures it is harder to make a precise statement on its computational complexity. For instance, if a structure is non-computable, i.e., its atomic diagram is not computable, there may still be computable isomorphic copies of it. To properly capture this behaviour degree spectra of structures are studied. The degree spectrum of a structure is the set of Turing degrees of all isomorphic copies of the structure. Beside degree spectra there are many other properties such as computable dimension, relative categoricity, Scott rank, degree spectra of relations, and theory spectra; together they capture the computational strength of a structure. In many areas in logic, like computability theory, descriptive set theory, or complexity theory, one is interested to compare the studied objects with respect to certain properties. This is usually done by using some notion of reduction. To compare structures with respect to their computational complexity we need a method of reduction that preserves all computability theoretic properties. Another important research question is of a more practical nature. If one finds a structure with some property, does there exist a structure with that property in familiar classes of structures mathematicians are interested in? So, not only do we want to compare structures to each other, we also want to compare classes of structures. Recently, a new, very strong notion of reduction between structures has been developed. An effective version of the category theoretic notion of a functor, called computable functor. Together with other effective versions of category theoretic concepts such as natural transformations and the related notion of reduction between classes of structures, uniform computable transformations, this has given rise to what we call computable category theory. There are also other possibilities to get an effective version of a functor. In some preliminary work with Ekaterina Fokina we studied enumerable functors. While computable functors make use of Turing reducibility to compare objects and morphisms, we used enumeration reducibility to compare objects. It turned out that enumerable functors are strictly stronger on the usual categories studied in computable structure theory, which have isomorphisms as arrows and structures with universe the natural numbers as objects. One of the two parts of this thesis concerns itself with the deeper investigation of this behaviour. - Is the relation the same on categories with different objects and arrows? We conjecture that this is not the case. - How do enumerable and computable functors relate to other possible notions of effective functors? - Which additional computability theoretic properties are preserved by enumerable functors and other possible notions? - What is the relation between effective functors and definability based notions such as effective interpretability? The other part of the thesis is concerned with applications to computable structure theory. - Which classes are complete for computable functors? - Which classes are complete for computable functors but not for enumerable functors? - What else can we say about the structure induced by effective functors? We believe that the study of those questions will lead to a better understanding of computable category theory and could lead to significant advancements in computable structure theory in the long term.

In computable structure theory computability theoretic properties of mathematical structures such as graphs, linear orders, or fields are studied. In contrast to the usual sets of natural numbers considered in computability theory, where Turing reducibility paints a clear picture of their information content, in the case of structures it is harder to make a precise statement on its computational complexity. For instance, if a structure is non-computable, i.e., its atomic diagram is not computable, there may still be computable isomorphic copies of it. To properly capture this behaviour degree spectra of structures are studied. The degree spectrum of a structure is the set of Turing degrees of all isomorphic copies of the structure. Beside degree spectra there are many other properties such as computable dimension, relative categoricity, Scott rank, degree spectra of relations, and theory spectra; together they capture the computational strength of a structure.