View Full Document


Unformatted text preview:

Contemporary Mathematics Recursion Theory in Set Theory Theodore A Slaman 1 Introduction Our goal is to convince the reader that recursion theoretic knowledge and experience can be successfully applied to questions which are typically viewed as set theoretic Of course we are not the first to make this point The detailed analysis of language the absoluteness or nonabsoluteness of the evaluation of statements and the interaction between lightface and relativized definability are thoroughly embedded in modern descriptive set theory But it is not too late to contribute and recursion theoretic additions are still welcome We will cite some recent work by Slaman Hjorth and Harrington in which recursion theoretic thinking was applied to problems in classical descriptive set theory It is the parameter free or lightface theory that seems closest to our recursion theoretic heart Where another might see a continuous function we see a function which is recursive relative to a real parameter In the same way we can see the Borel sets through the hyperarithmetic hierarchy and the co analytic sets by means of well founded recursive trees We will make our way through most of the relevant mathematical terrain without invoking concepts which are not natively recursion theoretic At the end we will mention some problems which are similarly accessible We owe a debt to Sacks s 1990 text on higher recursion theory and to Kechris s 1995 text on descriptive set theory These are valuable resources and we recommend them to anyone who wishes to learn more about what we will discuss here In the following we will cite theorems from the nineteenth and early twentieth centuries without giving the original references the motivated reader can find the history of descriptive set theory well documented in these texts 2 The Classical Theory Here is the framework We speak exclusively about subsets of Baire space and refer to an sequence of natural numbers as a real number A basic open set B is determined

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...

Join to view Recursion Theory in Set Theory and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursion Theory in Set Theory and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?