Computable model theory and invariant descriptive computability theory

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Mathematical logic grew out of a need to develop rigorous foundations for mathematics. Within mathematical logic, three major subfields are studied. Model theory understands mathematical objects by considering them through the lens of a formal language. Computability theory understands mathematical objects by considering them through the lens of computational complexity. Set theory understands mathematical objects through the foundational axioms of mathematics and how those axioms imply the object’s existence. This project focuses on some connections between computability theory and the other two subfields of logic. Regarding model theory, the project involves exploring the phenomenon when two mathematical objects look the same in terms of their formal languages, but one can be computed while the other cannot. In set theory, there is a rich theory exploring the complexity of 2-dimensional sets in terms of constructively embedding one into another. These embeddings are constructible in terms of the basic set-theoretic operations of unions and complements, but they may not be computable. The project will explore an analogous theory where one considers embeddings that must be computable. This project involves work with undergraduate and graduate students. The computable spectrum of a first-order theory asks which dimensions of models of that theory are computable. The spectrum problem in computable model theory, which has been a major open problem since the 70s, asks for which sets may be computable spectra of uncountably categorical theories, with a focus on strongly minimal theories. In this project, the aim is to give a reduction of the problem from a fully general framework down to the locally modular strongly minimal theories, which are geometrically tame and are closely related to groups. From there, the hope is to be able to give concrete answers as to which sets are spectra. Separately, this project will examine computable reduction on equivalence relations. One major direction is to use this complexity notion to examine algebraic decision problems in detail. In the past, the Turing degrees have been used to analyze algebraic decision problems, but these form a coarse yardstick, so all computably enumerable degrees seem to contain all natural algebraic decision problems. Using computable reductions on equivalence relations, there should be a much more interesting structure emerging. 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.