Classifying Relations via Computable Reducibility

A major goal of contemporary mathematics is that of classifying structures and relations according to their complexity. Common questions in this direction are as follows: how much information is needed to solve a specific problem about a structure? Given two different structures, which one is more complicated? Computable structure theory is a vast research program that provides a formal setting in which this kind of questions can be formulated. In particular, a powerful concept for comparing the complexity of various mathematical objects is that of reducibility. The informal idea is as follows: an object is reducible to another if we can answer questions about the former when knowledge about the latter is provided. Many different reducibilities have been investigated, and they represent one of the key topic of modern mathematical logic. The main focus of this project is on computable reducibility, a long-standing reducibility that attracted a lot of interest in the literature and it has proven to be a very powerful tool for ranking the complexity of a class of relations of fundamental interests for mathematicians, i.e., equivalence relations. These latter appear everywhere in mathematics and they capture the notion of resemblance between mathematical objects. The goal of this project is two-fold. On the one hand, we aim at extending the scope of computable reducibility from equivalence relations to more general cases, including graphs, orderings, and many other cases that are central to many different fields. In particular, we are interested in the problem of determining, for different classes of relations, whether there are some relations that contain so much information that all others reduce to them. On the other hand, we want to relax the notion of computable reducibility by analysing cases in which a reduction cannot be performed algorithmically but only with the help of some additional information. In doing so, we will obtain a tool that, given a pair of relations, permits to nicely calibrate all different ways of defining a reduction between them. So, in a nutshell, the present project is designed to hopefully unleash the full potential of a notion whose fruitfulness as a classification tool is well-known and proved but for a yet limited case.

Equivalence relations capture the notion of similarity. They are a major object of study in logic and computer science. In this project, we explored a powerful classification tool for measuring the complexity of equivalence relations: computable reducibility. We used such a tool for achieving many goals, including the classification of equivalence relations which are computable up to finitely many mistakes, the study of word problems in algebra, and for calculating how much information is needed to perform reductions between given equivalence relations. Within the project we also addressed two other focuses that have sprung up naturally from working around the project goals. First, we analyzed many algorithmic properties of a natural way of relaxing isomorphism: the bi-embeddability relation. Secondly, we contributed to algorithmic learning theory, a long-standing research program which deals with the question of how a learner, provided with more and more data about some environment, is eventually able to achieve systematic knowledge about it. Borrowing ideas from computable structure theory, we developed a novel framework for formalizing the notion of learning an algebraic structure in the limit. Using infinitary logic, we were able to obtain a syntactic characterization of which families of structures are learnable, according to this framework. The scientific outputs of the project include 16 articles and 20 talks and seminars.