Computability and definability in mathematical logic

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

ABSTRACT Cholak plans on studying the interaction between definability and computability in various structures in mathematical logic. Primarily, but not totally, Cholak will focus on the collection of all computably enumerable sets under the inclusion relation and the computably enumerable degrees under Turing reducibility. Cholak's long range goals are to provide a complete understanding of the relationships between these two structures and their automorphisms and definable orbits. Cholak's main focus is on definability and computability. These notions are both important in measuring the complexity of an answer to a mathematical problem. One develops an intertwined hierarchy of definability and computability. Only answers which lay on the lowest level of complexity are computable and even then are not always feasibly computable given today's computers. Answers of higher complexity provide useful mathematical information and allows the user to test the limits of their mathematical techniques.