Computability theory and descriptive set theory

Computability theory and descriptive set theory are two subfields of mathematical logic which have long been closely connected, both conceptually and in terms of the techniques used in each. On a conceptual level, both fields focus partly on results which show that certain mathematical problems have, in some sense, no satisfactory solution. For example, in computability theory, a common goal is to show that some mathematical problem cannot be solved by any algorithm, while in descriptive set theory, a common goal is to show that some construction cannot be done in a "measurable" way (which essentially means in a manner which can be analyzed using the tools of calculus). On a technical level, both fields rely on the general notion of quantifier complexity as well as specific techniques such as forcing and priority arguments. The goal of this project is to further the interaction between these two fields and, in particular, to apply tools from descriptive set theory to solve problems from computability theory and vice versa. The project also includes outreach to undergraduate students, training graduate students and mentoring postdocs who are working at the intersection of the two fields. This project will focus on three specific topics. The first topic is Martin's Conjecture, a long-standing open problem in computability theory which roughly states that every definable function on the Turing degrees is eventually equal to either a constant function or an iterate of the Turing jump. In previous joint work with Benjamin Siskind, the PI has proved certain special cases of Martin's Conjecture and one goal of this project is to continue that work and prove further special cases. Another, related, goal of this project is to apply ideas developed in work on Martin's Conjecture to problems in the theory of countable Borel equivalence relations, especially the question (raised by Boykin and Jackson) of whether every countable Borel equivalence relation is Borel bounded. The second topic is Borel combinatorics, which is an area focused on when Borel instances of combinatorial problems admit Borel solutions. One of the goals of the project is to use techniques from computability theory to build counterexamples in Borel combinatorics via effectively diagonalizing against all Borel functions. In particular, the PI plans to investigate whether a technique due to Leo Harrington, which produces computable trees in Baire space whose branches are all fairly generic relative to each other, can be used to produce counterexamples in Borel combinatorics. The third topic is measure reducibility of countable Borel equivalence relations. One of the goals of the project is to continue ongoing joint work between the PI and Jan Grebík aimed at using spectral graph theory to produce a countable Borel equivalence relation with interesting behavior with respect to measure reducibility (in particular, a successor of E0 for measure reducibility). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.