This project involves both set theory and recursion theory, focusing on various degree structures and the applications of forcing to degree-theoretic questions. The investigator will continue to work on the analysis of priority arguments in the theory of recursively enumerable degrees and on the proof-theoretic strength of these arguments. Groszek and Theodore A. Slaman (Univ. of Chicago) have been developing a uniform presentation for all levels of priority argument and tying these arguments to a standard proof-theoretic hierarchy of fragments of Peano arithmetic. In addition to continuing this development, Groszek will investigate specific statements about the partial order of recursively enumerable Turing degrees, considering whether and how their proof- theoretic strength reflects this analysis. In a different vein, Groszek will work on some long-standing open questions regarding the degrees of constructibility. Finally, she will consider the question of which partial orders can be embedded into the Turing degrees (assuming the failure of CH), one of the remaining open questions about the global structure of the Turing degrees. Prominent among the questions to be addressed by this project are a number that bear on theoretical computability. They lie in what is known as recursion theory, which deals with a model of computability knowing no bounds on time or space. Although answers to such questions have the ability to illuminate practical questions, they are really practical only when their answers are negative, for it is a very strong statement indeed to say that something cannot be computed even when one puts no limits on resources available for the purpose. The finer structure of computability theory is sometimes more relevant to actual computations, and various aspects of that will also be considered. A major thrust of the project is to equate degrees of computability with specific levels in a well studied hierarchy dealing with the logic of arithmetic.
