Interactions between Computability Theory and Model Theory

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

While computability theory studies complexity of mathematical objects from a computational point of view, model theory studies complexity of mathematical objects from a structural point of view. This project aims to deepen understanding of the interactions between these two different notions of complexity. In general, one expects that the more structured an object is, the easier it is to compute information about it. This research project aims to elucidate how a mathematical object having an understandable theory relates to computability of facts about the object. In particular, this project works towards understanding certain problems in computable model theory: the spectrum of computable models question asks which sets of dimensions can arise as the dimensions of computable models of some uncountably categorical theory. The project will investigate distinguishing this problem based on the geometric nature of the theory, with the goal of advancing understanding in the cases where the theory satisfies the Zilber trichotomy. This project also aims to advance understanding of the degree spectra of theories. The degree spectrum of a theory measures how hard it is to compute any model of that theory. The investigator aims to develop a newer notion that will highlight connections between properties of the theory and the properties of the spectrum, providing a further link between computability and model theory. The project also investigates index sets of model theoretic notions; this is a computability-theoretic way to measure the complexity of a property. Knowing the exact complexity of a property aids in working with these properties in the most direct and efficient manner possible, thus spurring further research progress.