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 by a finite sequence from x B if and only if is an initial segment of x A function f is continuous if any finite initial segment of f x is determined by a finite initial segment of x If we think of this Slaman wishes to thank L Harrington G Hjorth J Steel and W H Woodin for the information and advice that they provided during the preparation of this paper Slaman was also partially supported by NSF Grant DMS 97 96121 c 0000 copyright holder 1 2 THEODORE A SLAMAN correspondence between the argument and the domain as having been coded by a real number then f is recursive relative to that real Conversely if f is is recursive relative to some real parameter then f is continuous Definition 2 1 1 The Borel subsets of are those sets which can be obtained from open sets by a countable iteration of countable union and complementation 2 The analytic sets are the continuous images of the Borel sets The classical notions correspond to levels in the descriptive hierarchy of second order arithmetic Definition 2 2 able as follows 1 1 A is a 11 set if and only if membership in A is defin x A w n R n x n w n a n where a is a fixed element of w ranges over n ranges over and R is recursive 2 A is a 11 set if and only if both A and its complement are 11 sets Here is the connection A set C is closed if and only if there is an a and there is a recursive predicate R such that for all x x A n R n x n a n By a classical fact for every analytic set A there is a closed set C such that for all x x A if and only if there is a witness w such that x w C Thus a set is analytic if and only if it is 11 Similarly by a classical theorem of Suslin the Borel sets are exactly those analytic sets whose complements are analytic Consequently B is Borel if and only if it is 11 Definition 2 3 The projective sets are obtained from the Borel sets by closing under continuous images and complements Similarly to the above the projective sets are those sets which can be defined in second order arithmetic using real parameters Initially the projective sets were studied topologically Much of the progress was limited to the Borel sets and the 11 sets for which a variety of regularity properties were established 2 1 Perfect set theorems Recall a set P is perfect if it is nonempty closed and has no isolated points Equivalently P is perfect if and only if there is a perfect tree T such that every element of T has incompatible extensions in T and P is T the collection of infinite paths through T Theorem 2 4 1 Cantor Bendixson Every uncountable closed subset of has a perfect subset 2 Alexandrov Hausdorff Every uncountable Borel subset of has a perfect subset 3 Suslin Every uncountable analytic subset of has a perfect subset Suslin s Theorem follows directly from the representation of analytic sets given in 1 Suppose that A is uncountable and is defined by x A w n R n x n w n a n RECURSION THEORY IN SET THEORY 3 We build a tree T of pairs such that if T then there are uncountably many x extending for which there is a w extending such that n R n x n w n a n We use the fact that A is not countable to ensure that the projection of T onto the first coordinates of its elements is a perfect tree T1 Each path x through T1 is an element of A as it is associated with a witness w to that fact in T 2 2 Representations of Borel sets A diagonal argument shows that there is no universal Borel set However in a different sense the Borel sets are closer to having a universal element than one might have thought Theorem 2 5 Luzin Suslin For every Borel set B there is a closed set C and a continuous function f which maps C bijectively to B Proof Whether x belongs to B is determined at a countable ordinal in the jump hierarchy relative to x and the Borel code b for B Let C be the set of triples x b s such that s is the Skolem function verifying the relevant hyperarithmetic statement about x and b Corollary 2 6 Every uncountable Borel subset of is a continuous injective image of the sum of with a countably infinite discrete set Proof By Theorem 2 5 it is enough to show that every uncountable closed set is a continuous injective image of the sum of with a countably infinite discrete set This follows from the Cantor Bendixson analysis of closed sets Now we prove the converse Theorem 2 7 Luzin Suslin Suppose that B is a Borel subset of and that f is a continuous function that is injective on B Then the range …