In this project the principal investigator will apply methods from computability theory and other branches of logic and theoretical computer science to study the effective content and proof-theoretic strength of various areas of mathematics. In particular, he will concentrate on effective randomness, computable model theory, and reverse mathematics and effectiveness of combinatorial principles. He will study the relative randomness of reals, using methods from computability theory and algorithmic information theory, concentrating in particular on the K-trivial reals, a natural class of reals that are far from random with with many compelling properties and applications. In computable model theory, he will continue the development of methods to address issues raised by effectivizing model-theoretic notions, including the relationships between the different ways that a given structure may be effectivized; the relationships between the degree of effectivity of different models of theories with few models; and the degrees of special models, such as prime, homogeneous, and saturated models, of complete decidable theories. He will also study computability-theoretic and proof-theoretic aspects of combinatorial principles such as versions of Ramsey's Theorem and principles related to partial and linear orderings, exploiting the connections between effective mathematics and the reverse mathematics program.
The study of the effective content of mathematics has received increasing attention in the last few decades. It is a natural outgrowth of the efforts to understand and formalize the notions of algorithm and computable function undertaken in the early part of the twentieth century. It is of both pure mathematical and foundational interest, and has important connections with computer science. This project aims to further our understanding of how structure affects computability, and how computability interacts with other fundamental notions of modern mathematics and foundations of mathematics, such as randomness and proof-theoretic strength. Computability theorists have developed a highly successful theory of relative computational complexity of sets of numbers, which, in addition to its intrinsic mathematical interest, has been influential in theoretical computer science. One of the goals of this project is to continue the development of an emerging parallel theory of relative algorithmic randomness, which can act as a theoretical framework in which to consider questions such as: When should we say that an infinite set is more random than another, and what consequences does the relative randomness of sets have for their relative computational complexity?
