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

Original Announcement

This workshop 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:

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

A list of open problems.