Computability and Complexity in Mathematics

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Antonio Montalban will study problems in Computability Theory. He is interested in the interplay between complexity and mathematics. In mathematics, as we all know, some structures are more complicated than others, some constructions more complicated than others, and some proofs more complicated than others. He plans to apply methods from computability theory to study the complexity of various areas of both classical mathematics and foundations of mathematics. One of our objectives is to study of the computational properties of counterexamples to Vaught's conjecture, which is one of the most well-known and longest-standing conjectures in logic. This is with an eye towards either showing that those counterexamples do not exist, or just trying to understand them if they do exist. Montalban has already shown that being a counterexample to Vaught's conjecture is equivalent to a couple of purely computability-theoretic properties, and he has in mind a few other properties that might also end up being equivalent.