Computable Mathematics Measured by Enumeration Degrees

Mathematical logic and computability arose from the need to develop stable and trustworthy foundations for mathematics, provide clear criteria for what constitutes a proof, what basic axioms give sufficient power to express the rest of mathematics, and what constitutes an algorithm or a computable function. The origins of the fields trace back to David Hilbert's program from the 1900's and to the work by Gödel, Church, and Turing that proved several aspects of this program impossible: there are problems in elementary number theory that do not have computable solutions.

Since then, incomputable problems have been identified in many different subfields of mathematics. Most famously, the solution sets to some Diophantine equations and the word problem for some finitely presented groups are incomputable. Computability theory proposes frameworks to study the relative algorithmic complexity of such problems.

This project proposes an in-depth investigation of two related frameworks in computability theory, and the complex structures that they give rise to. The project presents a diverse array of research avenues, suitable for all levels of experience. Soskova and Miller intend to continue their collaboration with undergraduate, graduate, and postgraduate students and facilitate the quick immersion of young researchers into this area through two textbooks: a beginner level Computability Theory textbook and a more specialized advanced textbook on the precise topic studied within this project.

They also maintain a visual online database that allows the quick identification of open problems. The project will support women's engagement in the field through a mentorship program organized by Soskova within the CiE Women in Computability focus group. Soskova and Miller will continue to support the Logic Community by organizing scientific meetings and through their editorial work.

In computability theory, the Turing degrees are used to measure the effective content of sets of natural numbers. This measure can be extended to capture the effective content of other objects in mathematics, such as the real numbers. In other cases, Turing reducibility is not sufficient.

For example, Miller proved that it is not possible to assign a Turing degree to every continuous function on the unit interval. In that and many other cases, an extension of Turing reducibility, enumeration reducibility, turns out to provide a better framework for effective mathematics. In 1967, Rogers posed a list of problems that strongly influenced the development of computability theory.

One of these problems asks whether the partial orders of the Turing degrees and the enumeration degrees are rigid structures, i.e., have no nontrivial automorphisms. Slaman and Woodin proved that the rigidity of the Turing degrees is equivalent to a complete characterization of its definable relations and to its biinterpretability with second order arithmetic.

Building on this, Soskova proved that the same equivalence holds for the enumeration degrees. Miller and Soskova (with collaborators) answered another problem from the list: there is a first order definable copy of the Turing degrees inside the enumeration degrees. This established a link between the rigidity problems for the two structures; if the Turing degrees are rigid then so are the enumeration degrees.

The rigidity of the enumeration degrees, while still open, could turn out to be more approachable. Definability within the enumeration degrees has already proved more approachable. The goal of this project is to expand our understanding of the structure of the enumeration degrees and its nontrivial connections to effective mathematics, with a focus on computable topology.

We would like to accumulate new methods investigate combinatorial properties of the structure, and isolate special classes of degrees that determine the logical character of the structure.

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.