Computing with Positive Information: Definability and Structure of Enumeration Degrees

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Turing degrees are used to measure how difficult it is to determine whether an arbitrary number is a member of a given set of natural numbers. This measure can be extended to capture the effective content of other objects in mathematics, such as real numbers. In other cases, Turing reducibility is not sufficient. For example, it is known to be impossible 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 constructive mathematics. However, enumeration degrees have not been as thoroughly investigated as Turing degrees. The goal of this project is to expand understanding of the structure of enumeration degrees and their relationship to Turing degrees. The project aims to develop new methods, investigate combinatorial properties of the structure, and isolate special classes of degrees that determine the logical character of the structure, with a special focus on first-order definability. Constructive mathematics, specifically algebra and topology, will be the source for such classes. The project aims to utilize the intimate interplay between the partial orders of the Turing degrees and the enumeration degrees to extract new information in both directions. A major open problem in degree theory asks if the structure of the Turing degrees is rigid. This problem is strongly connected to a possible classification of the first-order definable relations on the Turing degrees. Prior work has established a link between this problem and the rigidity problem for the enumeration degrees: if the Turing degrees are rigid then so are the enumeration degrees. The rigidity of the enumeration degrees, while still open, can turn out to be more approachable. The investigator and collaborators have established the first-order definability of a series of relations on the structure of the enumeration degrees via natural structural relations. An important goal of this project is to continue this line of investigation, building an arsenal of first-order definable relations on the enumeration degrees and bringing us closer to a solution to the rigidity problem for the enumeration degrees. 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.