Computability on Cones

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Computability theory is an area within mathematical logic that studies the complexity of countable mathematical objects. In mathematics, as we all know, some objects, constructions, or proofs are more complicated than others. Logicians have developed various ways of measuring this complexity. When one is interested in countable objects, which are central to a wide range of mathematics, the tools to measure these complexities come from computability theory. The objective of this project is to draw connections between complexity issues and structural issues to improve understanding of what forms complexity can take. The investigator will also continue work on a book series that aims to make it easier for the logic community to learn about the subject of computable structure theory, to help graduate students reach a research-level understanding of the subject, and to provide researchers with a modern reference. The main component of this project is the study of the structure that emerges when considering computability theoretic properties on a cone, that is, properties that hold relative to almost every oracle with respect to Martin's measure. The project will study generalizations of the uniform Martin's conjecture and the almost-everywhere structure of Turing equivalence. The study of on-a-cone properties led to structural characterizations for a variety of notions from computable structure theory over the last decade. This project investigates the one-a-cone structure of the Turing degrees, of Turing equivalence, and of other recursion theoretic objects. The research will pursue two lines of inquiry. On the one hand, recent work suggests Martin's conjecture is just the tip of the iceberg, and that there are other situations where one can get a nice structural classification of relativizable objects. This research will search further for such structural classifications for equivalence relations other than Turing equivalence. On the other hand, conjectures about properties of the Turing equivalence and its interactions with its sub-equivalence relations may provide information on where Turing equivalence is located in the landscape of Borel equivalence relations, and the project will investigate this possibility. 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.