Applications are closed
for this workshop

Invariant descriptive computability theory

November 7 to November 11, 2022

at the

American Institute of Mathematics, San Jose, California

organized by

Uri Andrews, Ekaterina Fokina, Su Gao, and Luca San Mauro

This workshop, sponsored by AIM and the NSF, will be devoted to connecting two parallel approaches towards the study of the complexity of equivalence relations. On the one hand, a popular tool for classifying equivalence relations on standard Borel spaces is Borel reducibility. Invariant descriptive set theory, centered around this notion, is a vibrant field which shows deep connections with topology, group theory, combinatorics, and ergodic theory. On the other hand, a natural effectivization of Borel reducibility, named computable reducibility, appears in computability theory. Computable reducibility has proven to be a key notion for measuring the complexity of equivalence relations on the natural numbers, with fruitful applications in a variety of fields, such as: the metamathematics of arithmetic, the study of word problems for groups, the theory of numberings, and computable model theory.

Despite the analogy between Borel and computable reducibility, there has been so far little effort to directly connect techniques, knowledge, and researchers of these separate fields. To counter this lack of communication, the proposed workshop will assemble a diverse group of mathematical logicians - drawn from both experts in invariant descriptive set theory and experts in computability theory working on computable reduction - to discuss on how their tools can align.

The main topics for the workshop are:

  • Presentations on state of the art tools from computability and from invariant set theory for classifying equivalence relations;
  • Construction, classification, and investigation of the properties of Borel, continuous, and effective reductions of equivalence relations;
  • Exchange of techniques developed by different research groups with the goal of advancing our understanding of how and when equivalence relations reduce to each other, as well as uniting the mathematical logic community.

This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email

Plain text announcement or brief announcement.