Invariant descriptive computability theory
November 7 to November 11, 2022
American Institute of Mathematics,
San Jose, California
and Luca San Mauro
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
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
Material from the workshop
A list of participants.
The workshop schedule.
A list of open problems.