Some results on projective equivalence relations Citation Li, Xuhua (1998) Some results on projective equivalence relations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/pn2n-7z61. https://resolver.caltech.edu/CaltechTHESIS:01202017-113604553 Abstract We construct a ∏ 1 1 equivalence relation E on ω ω for which there is no largest E-thin, E-invariant ∏ 1 1 subset of ω ω . Then we lift our result to the general case. Namely, we show that there is a ∏ 1 2n+1 equivalence relation for which there is no largest E-thin, E-invariant ∏ 1 2n+1 set under projective determinacy. This answers an open problem raised in Kechris [Ke2]. Our second result in this thesis is a representation for thin ∏ 1 3 equivalence relations on u ω . Precisely, we show that for each thin ∏ 1 3 equivalence relation E on u ω , there is a Δ 1 3 in the codes map p: ω ω → u ω and a ∏ 1 3 in the codes equivalence relation e on u ω such that for all real numbers x and y, xEy ↔ (p(x),p(y))∈ e This lifts Harrington's result about thin ∏ 1 1 equivalence relations to thin ∏ 1 3 equivalence relations. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Kechris, Alexander S. Thesis Committee: Ramakrishnan, Dinakar Luxemburg, W. A. J. Defense Date: 22 June 1997 Record Number: CaltechTHESIS:01202017-113604553 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:01202017-113604553 DOI: 10.7907/pn2n-7z61 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 10016 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 23 Jan 2017 20:48 Last Modified: 09 Nov 2022 19:19 Thesis Files Preview PDF - Final Version See Usage Policy. 22MB Repository Staff Only: item control page

Some Results on Projective Equivalence Relations Thesis By Xuhua Li In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1998 (Submitted June 22, 1997) 11 Abstract We construct a IIi equivalence relation E on ww for which there is no largest E-thin, E-invariant IIi subset of ww. Then we lift our result to the general case. Namely, we show that there is a II~n+l equivalence relation for which there is no largest E-thin, E-invariant II~n+l set under projective determinacy. This answers an open problem raised in Kechris [Ke2]. Our second result in this thesis is a representation for thin II§ equivalence relations on 11.w. Precisely, we show that for each thin II§ equivalence relation E on Uw, there is a .6..§ in the codes map p: ww - r 11.w and a II§ in the codes equivalence relation e on 11.w such that for all real numbers x and y, .TEy ¢:::::=? (p(x) ,p(y)) Ee. This lifts Harrington 's result about thin IIi equivalence relations to thin II§ equivalence relations. lll Dedication IV Acknowledgement I would like to begin by expressing my gratitude to my advisors, Professor A.S. Kechris and Professor G. Hjorth for helping me to choose the right problems and for their guidance and encouragement during my graduate years at Caltech. Professor Kechris was the person who opened the new world of descriptive set theory to me. I learned all of the fundamental knowledge in classical and effective set theory from him. He was always there to answer my questions, provide sugestions and keep a close eye on my research. I would like to express my sincere gratitude to him. I worked more closely with Professor Hjorth who taught me tools and skills of modern set theory. I worked more closely with him in my research. The work would not have been possible without his help. He has been an invaluable source of ideas, insights and knowledge . I can hardly thank him enough for his help. I am grateful to Professor Dinakar Ramakrishnan and Professor W.A.J. Luxemburg for their precious time taken for my thesis defense. I thank my wife for staying with me for five years to struggle for my degree. We helped each other and overcame many difficulties. I also thank my parents for their giving me a supportive family. My years at Caltech were enriched by all the wonderful people I met here. I v also thank the mathematics department for its financial aid. Vl Table of Contents 1. Introduction.... .. ............ .. . ..... .................. 1 2. Largest E-thin, E-invariant Sets below .6.§ . . . . . . . . . . . . . . . 8 3. The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4. :E§, II§ and .6.§ in the Codes Subsets of Uw . . . . . . . . . . . . . . . . 41 5. A Technical Lemma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6. Representation of Thin II§ Equivalence Relations . . . . . . . . 71 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Vita .. .................................... ........ ...... 88 1 1. Introduction As ZFC fails to resolve many important questions about general sets, and even large cardinals cannot determine the size of ww, set theorists turn to consider the definable objects. It is descriptive set theorists' main interest to study various set theoretic properties of definable objects. ww used to be our magic garden with various flowers like II~ sets, L::j singletons and so on. Now, there is also strong interest in the quotient space ww /Eby definable equivalence relation E. Our interests are also restricted to this new playground in this thesis. Let us have a basic picture of this classical garden of set theory at first; a more detailed and global description can be found from [Mol] or [Ke6]. We will call X a product space, if X can be written as a product of w, ww, 2w. We call a product space X perfect if and only if it is perfect (i.e., no isolated point) under the product topology. In this thesis, we will always use X, '}:I to represent product spaces; we also always use x, y, z and the corresponding letters with scripts to represent typical elements in product spaces. Let {Nn}nEw be the "natural" basis of a product space X, (1) we will call a set A~ X I:~ (in some .T E ww) or semirecursive (in some x E ww) set if there is a recursive (in x) function E: w _, w such that A= LJnEw NE(n)· (2) We will call an A ~ X II~ (in x) if and only if X \ A is I:~ (in x). I:~ sets are the effective version of the open sets, which are the open sets 2 that we have algorithms to determine the membership in them. (3) We will call a set A s;;; :X ~i if and only if there is a B s;;; X x ww such that A = projww (B), namely, for all x E :X, x E A if and only if :Jy E ww such that (x, y) E B. We also write projww (B) as p(B) or even pB in this thesis. (4) As;;; Xis called a ITi (in x) set if and only if X \A is a ~i (in x) set. (5) In general, we can define ~1+i (in x) sets as the projections along ww of IT1 (in x) sets, and IT1+i (in x) sets as the compliments of ~1+1 (in :r;) sets. (6) We call a set 61 (in x) if and only if it is both ~1 (in .T) and IT1 (in x). (7) We call a set A s;;; :X ~1 (Ilk, Llk, ~z, IIZ,, -6..Z,) if and only if it is ~1 (IT1, 61, ~z , ITZ, , 6Z, respectively in some x). ~z, IIZ,, -6..Z,) if and only if G.r = { (x, n) : f(x) E N(Zf, n)} is ~1 (Ilk, 61, ~Z,, ITZ,, 6Z,, ~1, Ilk, Llk, ~Z,, IIZ,, LlZ, respectively), where N(ZI, n) is a basis of Zf. (9) We call an ordinal a ~1 (Ilk, 61, ~z, ITZ,, 6Z,, ~1 in x, IT1 in x, 61 in x, ~z in .T, IlZ, in x, 6Z, in .T) if and only if there is a ~1 (IT1, 61, ~z., ITZ,, ;\ 0 "1 . rr1 . t\ 1 . '10 . uk, LJk m x, k m x, uk m x, LJk m x, nok m . x, uk ;\ 0 m. x respective . 1 ) y well-ordering on a subset of w which has the ordertype a. Each of these ordinals can be coded by a real number. 3 It is well known that a set A ~ X is Ai if and only if it is a Borel set and a function is Ai if and only if it is a Borel function. We will call A ~ X perfect if and only if A is closed and has no isolated points. We will call A ~ X thick if it includes a perfect subset. Of course, we will call A thin if and only if A is not thick. The continuum problem is the chief stimulus for studying perfect sets. The continuum hypothesis cannot be determined from ZFC. Even large cardinals fail to determine the size of the continuum. However, the effective version of the continuum hypothesis (i.e., the perfect set theorem) can be proved from suitable large cardinals. Speaking roughly, every "definable" uncountable set of real numbers is thick, hence, equinumerous with ww. Definable thin subsets of a product space X were extensively investigated by various researchers in descriptive set theory. Let us summarize some related results about thin sets below. At first we know that for any perfect product space X, there is no largest thin I:i subset of X. It suffices to prove this for ww, since any perfect product space is homeomorphic to ww through a LJ.i bijection. Suppose we have a largest one among all of the thin I:i subsets of ww, it must be B = { x : x is LJ.i} since a I:i subset of ww is thin if and only if it contains only LJ.i reals by the effective perfect set theorem. However, B is not I:i by Kleene's lower classification theorem on LJ.i. 4 However, for IJi , we have a different story. Theorem ( Guaspari, Kechris, Sacks) 1.1. For any given product space X, there is a largest thin IIi subset C1 (X) ~ X that includes all thin IIi subsets ofX. The largest thin IIi subset of ww can be defined as C1(ww) = {.r,: 'v'y(w~::; w{ _, x E 6.i(y))} = { x : :r; E Lw~ } , where wI = the least ordinal which is not recursive in x = the least ordinal which is not 6.i in x. A classical construction of the largest thin IIi set using IIi norms can be found in [Mol] also. Assuming that all ~ 1 games on w are determined, the projection of C 1 (Xx ww) to X gives us the largest I:§ subsets of X. So, we also have the largest I:§ subset of X. The largest thin I:§ subset of ww is actually equal to the set of all constructible reals. It is easy to see that there is no largest thin II§ subset of any perfect product space X. Otherwise, suppose A is the largest thin II§ subset of ww, A cannot be X, so B = X \A -=/= 0, B must contain a 6.§ real x by the basis theorem for 6.§ sets. Now, A U { x} is larger than A but still thin and II§. 5 In general, we have the following Theorem (Kechris and Moschovakis) 1.2. (1) Assume Det(:E§ 11 ). For each perfect product space X, there is a largest thin I1§ 11 + 1 set C2 11 + 1 (X) S: X of X. (2) Assume Det(:E§ 11 + 1 ). For each perfect product space X, there is a largest thin (or equivalently countable) ~§ 11 + 2 set C2n+2 (X) S: X ~§ 11 + 2 . (3) Assume Det(:EtJ. For every perfect product space X, there is no largest thin ~§n+l subset of X which contains every thin ~§ 11 + 1 subset of X. (4) Assume Det(.6..§ 7.J. For all perfect product spaces, there is no largest thin I1§ 11 +2 subset of X. We will investigate similar properties in the context of X / E for some definable equivalence relation E in this thesis. We could easily lift all the definitions we mentioned before to the context of X / E by considering [A] E = {x : 3a E A(xEa)} for any A S: X/ E. Equivalently, we can consider E-invariant sets but still work in X. We will follow the latter. Fix E a definable equivalence relation on X and r a lightface pointclass. In this thesis, we only care about the cases that r is ~k or II1 for some k E w. We will call a set A (1) E-invariant if and only if for any :r, y E ww, x EA/\ .r,Ey ====? y EA, (2) E-thick if and only if there is a perfect subset B s;;; A such that for any x, y EB, x -:j:. y ====? :rfty, 6 (3) E-thin if and only if it is not E-thick, (4) largest E-thin, E-invariant r set if and only if it is a E-thin, E-invariant r set that contains all of other E-thin, E-invariant r sets. We will see when we have a largest E-thin, E-invariant r subset of a perfect product space for a r' equivalence relation E, where r, r' the above classes. If r is ~§n+l or II§ 71 , the solution is immediate. We have two recursive equivalence relations E 1 and E2 such that there is a largest E 1 -thin E 1 -invariant r set but no largest E2-thin E 2 invariant set. We can let E 1 be the largest equivalence relation on :X (i.e., :X x :X) and E2 be the smallest equivalence relation on :X (i.e., the identity relation id(X)). Problem 1.3. Assuming Projective Determinacy, for what II§n+l equivalence relations E on a perfect product space, is there a largest E-thin, E-invariant ~§n+i set or a largest E-thin E-invariant II§n+ 2 set? It is obviously true for thin equivalence relations. But, is it true or false that for any thick II§n+l equivalence relation E, there is no largest E-thin E-invariant ~§n+l set or largest E-thin E-invariant II§n+ 2 sets? If r is II§n+i or ~§n+ 2 , the classical results about E = id(X) tell us that there is a recursive equivalence relation E such that we have a largest E-thin E-invariant II§n+l set and a largest E-thin E-invariant ~§ 71 + 2 set. But, how about the other II§n+l equivalence relations. We will deal with this problem in the following chapters. 7 In Chapter 1, we will prove that there is a ITi equivalence relation E on ww, for which there is no largest E-thin, E-invariant ITi subset of ww. Then, we prove a similar result in a more general context, we get a IT§n+l equivalence relation Eon WW for which there is no largest E-thin, E-invariant rr§n+l subset of ww. In the last section, we lift Harrington's representation theorem for thin ITi equivalence relations to thin IT§ equivalence relations assuming that Vx E ww(x~ exists). 8 2. Largest E-thin, E-invariant Sets below ~1 In [Kel], Kechris proved the following Theorem (Kechris) 2 .1. Let E be a IIi equivalence relation on ww, if A <; : ; ww is ITi and E-thin, then for each .T 0 E A, there is Ao ~i in an ordinal smaller than w~ 0 such that Xo E Ao <; : ; [:r;o]E n A. For a Tii E, if we let A= {x: 3S(S is ~i in an ordinal smaller than wf and.TES<;;::; [x]E)}. A is clearly a Tii set which contains every E-thin Tii subset of ww. A is also E-thin, otherwise, we can play the ordinary forcing trick to blow up the continuum to get a contradiction. If A is E-thick, we can expand our universe V to some generic extension V[G] by some so that in V[G], we have 2No = N2 . Shoenfield absoluteness guarantees that A is still E-thick in V[G]. So, there must be N2 many S's to witness the membership in A. But that is impossible because we only have N1 many such S's in V[G]. So we get a Tii set which is E-thin and contains every E-thin Tii subset of ww as a subset. As every I:§ set can be decomposed as N1 union of Borel sets, we can adjust the definition a little bit to get a largest E-thin I:§ set. Let C2(E) = {x: 3S( Sis ~i in a countable ordinal /\ x ES<;;::; [x]E)}. 9 In [Kel] , Kechris observed that this C 2 [E] is the largest E-thin, E-invariant 2:§ set for the IIi equivalence relation E. Hence we have Theorern(Kechris) 2.2. For any IIi equivalence relation E on a product space X, there is a largest E-thin, E-invariant 2:§ set. If E is actually 6.i, Kechris also noticed the following Theorern(Kechris) 2.3. For any 6.i equivalence relation E on a product space X, there is a largest E-thin, E-invariant IIi set. The largest E-thin, E-invariant set mentioned above can be defined as C 1 (E) = LJ{ C :C is an E-equivalence class /\ Vx E C (C is 6. i in an ordinal smaller than wf)} . After these results , Kechris raised the following Problern(Kechris). Is it true or false that for any IIi equivalence relation E, there will be a largest E-thin , E-invariant IIi subset of ww? We will answer this negatively. Namely, we will construct a IIi equivalence relation E for which there is no largest E-thin, E-invariant IIi subset of ww. The idea is the following. We list all possible candidates of the largest Ethin, E-invariant IIi sets, i.e. , we list all IIi subsets of ww as { ArJnEw· We will construct our equivalence relation E step by step, the possibility of each An as the largest E-thin, E-invariant subset of ww is destroyed at some step 10 of our construction. If An is given attention at some stage of our construction, we will pick some IIi singleton {x} which has some nice properties. If this x is not in An, we will let { x} be an equivalence class of our E which is being constructed. Hence, An cannot be the largest E-thin, E-invariant IIi set since An U{x} is obviously larger than An and still an E-thin, E-invariant IIi set. If this xis already in An, we will find some real y which is not in An and put (x, y) into the equivalence relation E. Hence, An cannot be E-invariant. To make the above idea work, we have to make our construction carefully, otherwise, we cannot guarantee that our equivalence relation E is IIi. That is why we need the Kleene recursion theorem. Let D~ = sup{ a : a is a countable ordinal coded by a 6.~ real}. We will call an ordinal a stable if and only if for all 2: 1 formulas cp(x 1 , · · · , xn) in the Levy hierarchy of ZFC formulas, and for any a 1 , · · · , an E L(l'., We will call an ordinal a weakly stable if and only if for all 2: 1 formulas without parameters in the Levy hierarchy of ZFC formulas, L I= cp <;=> L(l'. I= cp. It is a well-known fact that o~ = the least stable ordinal 11 the least weakly stable ordinal . We do not need this result in our proof in this chapter, if we just replace all of the appearances of 8~ by o- 0 , the least stable ordinal. But this fact suggests that it should be enough to use the IIi singletons as our building blocks. We will need the following Lemma 2.4. For any given a< 8~, any sentence 1jJ which is true in L, there is a {3 such that (1) a~f3<8~, (2) L(3 I= ZFC* /\ v = L /\ 1/;, (3) Lf3 = SkolemHull(Lf3), (4) x = Th(Lf3), (5) x is a IIi singleton, where ZFC* means a large enough Enite fragment of ZFC. We also use ZFL * to denote ZFC* + (V = L). Remark. This lemma claims that we have unbounded many such {J's. We only need the existence of one {3 to prove our main result in this chapter. But they are actually equivalent. We state the lemma in only an apparently stronger form. Proof. Since a is smaller than 8~ which is the least weakly stable cardinal, a cannot be a weakly stable cardinal. So, there must be a 2:: 1 formula <p such that 12 L I= cp and Vf3 < a (L f3 F cp). Let us fix such a cp in our proof. Consider the set A= {x: '3f3(Lf3 I= (ZFL* /\ 'ljJ /\ cp) and x codes Th(Lf3)}. Claim. A is not empty. Proof of the claim: As o~ is stable, for any finite many sentences cp 1 , · · · , cpn of the language of set theory, we can find a ry < D~ such that L'Y I= cp 1 /\ · · · /\ cpn. Let /30 be an ordinal such that L f3o I= ZFL * /\ cp /\ 'ljJ. Let M = SkolemH ull (L f3o). As M is elementary equivalent to Lf30 , M I= ZFL *. If we put enough axioms of ZFL into ZFL *, we can guarantee that M is isomorphic to some Lf3 for some f3 :::; f3 0 since M is clearly wellfounded. Let x code the theory of Lf3. This x is clearly in A. 0 (claim) Claim. A is IIi. Proof of claim: It suffices to show that for any real number :r, x E A if and only if there is a f3 recursive in x such that x codes Th(Lf3) and ZFL* ~ Th(Lf3) and cp, 'ljJ E Th(Lf3)· Let x in A. From the definition of A, there is a /3' such that such that x codes Th(Lf3') and ZFL* ~ Th(Lf3') and cp, 'ljJ E Th(Lf3' ). Let M be the Skolem hull of L~. M must be isomorphic to some Lf3 for some f3 :::; /3' and Th(Lf3) = Th(Lf3' ). As Mis the Skolem hull of itself, M can be reconstructed effectively from its theory by a classical model theory construction. /3, as the order type of OrdM, is recursively reconstructible from Th(M) = Th(Lf3) as well. Hence, f3 is recursive in x. D( claim) Now, by the basis theorem for the rrt subsets of WW) there is ax in A which 13 is a IIi singleton. Let :r; code some L131, (3 1 < o~, since L~ I= cp. We can play the same trick as before. Let M b e the Skolem hull of L131. We know that M is isomorphic to some L13 for some (3 :::; (3' < o~. This (3 is what we want in the lemma. D (lemma) Let A ~ w x ww and E ~ w x ww x ww be "good" universal IIi sets for which the s-m-n theorem applies. Let Ak = {x: (k,x) EA} and Ek= {(x,y): (k, x, y) EE}. Then {Ak}kEw enumerate all IIi subsets of ww in a IIi way and {Ek} kEw enumerate all IIi subsets of ww x ww in a IIi way. Lemma 2.5. Let Thi ck(m , n) <===::} A m is E,,-thick. Then Thi ck(m, n) is I;~. This could b e proved usmg Theorem 2. 1. We give below a direct proof without using Theorem 2.1 because we think that the characterization of Ethickness that we obtain may be also interesting as well. Proof. To make our notation simple, we just prove that it is I;~ to say that A is E-thick, for any given IIi A ~ ww and IIi E ~ ww x ww. The proof for the general case is the same but notationally more complicated. Fix a T ~ (w x w x w)<w to be a recursive pruned tree such that •E = p[T] where p[T] is the projection of [T] to the second and third coordinates. Also fix a map 7r from ww to LO = { x : x co des a linear ordering of a subset of w} 14 such that for all x, .r, EA ~ f(x) E WO, where W 0 = { x : x codes a well-ordering of a subset of w}. Claim. the following are equivalent: (1) A is E-thick. (2) There is a continuous function f: 2w ----> ww such that (i) for all x in 2w, f(x) EA, (ii) for all :r;, yin 2w, if x =/= y, then f(x)l/)f(y). (3) There is a countable ordinal a, a continuous function f: 2w ----> ww and a continuous function g: ww x ww ----> ww such that (i) for all x, 7r(f (x)) <a, (ii) for all x, yin 2w, if x =/= y, then f(x) =/= f(y), (iii) for all .r, and y, if x =/= y, then g(f(x), f(y)) witnesses that (f(x),f(y)) r$ E. (4) There is a real number r, a function fo: 2<w----> 2<w and a function go: w<w x w<w ----> w<w such that (i) for alls and tin 2<w, ifs Ct, then fo(s) C fo(t), (ii) for any s and t in 2<w, if len(s) = len(t), then len(f0 (s)) len(f0 ( t)), where len( s) is the length of s, (iii) for alls in 2<w , fo(s~O) =/= fo(s~l), (iv) for all (so, s1) and (to , t1) in w<w x w<w, if (so, s1) C (to, t 1), then go(so, s1) ~ go(to, t1), 15 (v) for all (so, s1) in w<w x w<w, if there is a v, E w<w such that (7L, so, s1) ET, then (go( so, s1), so, s1) ET, (vi) for any s and t in 2<w , if len(s) = len(t) and s =/=- t, then there is a 11, E 2<w such that (u, fo(s), fo(t)) ET, (vii) for all x in 2w, if Vn E w3s E 2<w(x f n = fo(s)), then x is recursive m r. Proof of the above claim: (4) ::::? (3): Assume that we have the Jo, g0 and r satisfying all the requirements of (4). Let a = w].'. Let f = fa, namely, f( .r) = UnEwfo(x f n). This f is well-defined since Jo is monotonic by (i). From (iii), f is one to one. f is also continuous from Theorem 2.6 in [K6]. From (v), we know that Vx E 2w(7r(f(x)) < a). We define g in a similar way, namely, g(x, y) = 9o(x, y) = UnEw9o(x f n, y f n). Then g is also continuous. Now, for any x and y in 2w, if .r =/=- y, there is a N such that for all n ?: N, x f n =/=- y f n. Hence, (go(fo(x f n) , fo(Y f n)), fo(x f n) , fo(Y f n)) E T for all n ?: N by (iv), (v) and (vi). As [T] is closed, (g(f(x),f(y)),f(x) , f(y)) E [T]. Hence, g(f(x),f(y)) witnesses that (f(.r), f(y)) tj_ E since •E = p[T]. (3) ::::? (2): Obvious. (2) ::::? (1): Since 2w is compact, f[2w] is a compact subset of ww. As ww is a Hausdorf space, it must be a closed set. Hence, this perfect subset of A witnesses that A is E-thick. 16 ( 1) ::::? ( 4): Assume ( 1). The construction of fo is the routine Cantor scheme construction. (See [Ke6] for the Cantor scheme construction.) We can construct a Cantor scheme (Us)sE2 <w (i.e., a family (As)sE2 <w of subsets of some Polish space X such that (1) As ~ o n As~ 1 = 0, for all s E 2<w, and (2) As~i ~ As, for all s E 2 <w and i E { 0, 1}.) such that (1) Us is of the form Nt = { x : .c: contains t} for some t E 2<w, (2) if len(s) = len(t), Us= Ns' and Ut = Nt', then len(s') = len(t'), (3) diam( Us) ::; 2-l en (s), i.e., if Us = Ns', then len(s') ~ 2len(s) , (4) Us~i ~Us, for any s E 2<w and i E {O, 1}, (5) if Us = Ns' and Ut = Nt' , then there is some 1L E 2<w such that (1J,, s' , t') ET. This Cantor scheme can be constructed as usual by induction on the length of s since A is E- thick. Let fo(s) = t if and only if Us= Nt. Let f( x ) = f'()(x) = UnEwfo(x f n). f is a continuous injection from 2w into A. As n[f[2w]] is a ~i subset of WO, it is bounded below some countable ordinal a. Therefore, there is a r E ww such that a is recursive in r. For any .t: such that Vn E w:3s E 2<w (x f n = fo(s)), we know that (n(f(x)) codes a well-ordering with an order-type smaller than a, hence, recursive in r. We can also construct the map g 0 by induction on the length of (s 0 , s 1 ) . We let g0 (0) = 0. Suppose we have already defined go for all (s 0 , s 1 ) with 17 len(so) = len(s i) < n, consider to = so'"'i and ti = si'"'j for i,j E w, if there is a 11. E 2<w such that (u, to, ti) E T , we let go(to, t 1 ) be some 11, such that (u, to , ti) E T. works. Otherwise, go( to, ti) = on . It is easy to check that g0 D (claim) As (4) is clearly 2:§, it is 2:§ to say that A is E-thick. So is Thick( m, n). D Let 8( m, n) ¢::::::} Lemma 2.6. Am is the largest Rn-thin Rn-invariant subset of ww . B(m, n) is absolute between L and V . Proof. Let Bo(m, n) ¢::::::} Am is a Rn-thin Rn-invariant subset of ww . 80 ( m, n) is II§ since Thi ck( m , n) as specified as in the lemma before is 2:§ and it is II§ to say that Am is Rn invariant. As B(m , n) ¢::::::} Bo(m, n) /\ Vk(Bo(k , n) ===> Ak ~Am), B(m, n) is absolute between L and V by the Shoenfield absoluteness t heorem . D Since B(m , n) is absolute between L and V , we can assume that V without loss of generality, since if we proved that LI= 3n(En is an equivalence relation /\ Vm•B(m,n)), we must have VI= 3n(En is an equivalence relation /\ Vm•B(m, n)) L 18 as well. Let us define a set A ~ w x ww x ww as following: 19 (e, x, y) E S {::::::::} EITHER (1) OR x = y; (2) 3a3n E w such that (2.1) Le. = SkolemHull(Lc.), (2.2) Le. I= ZFL* /\ e(n, e), (2.3) x codes Th(Lc.), (2.4) x is a IIi singleton, (2.5) Vm < n(Lc. F e(m, e)), (2.6) x E An, (2. 7) Le. I= "y is the <L°' -least element subject to the following requirements: (2.7.1) y E (Le.\ An) n WW' (2.7.2) y is not a IIi singleton, (2.7.3) 'r/z(z is a IIi singleton ~ •(z, y) E Ee);" OR (3) 3a 3n E w such that (3.1) Le. = SkolemHull(Lc.), (3.2) Le. I= ZFL* /\ e(n,e), (3.3) y codes Th(Lc.), 20 rrt singleton, (3.4) y is a (3.5) Vm < n(La [F e(m, e)), (3.6) y E An, (3.7) L a I= "x is the <Ln -least element subject to the following requirements: (3.7.2) :r: is not a rrt singleton, (3.7.3) Vz(z is a IIi singleton--+ -.( z, .r) E Ee)·" Lemma 2.7. Sis a IIi subset of w x ww x ww. Proof. It suffices to show that (2) is a IIi formula. But (2) ¢:::::=? :Jn[(2.4) /\ (2.6) /\ :Ja((2 .1) /\ (2.2) /\ (2.3) /\ (2.5) /\ (2.7)] ¢:::::=? :ln[(2.4) /\ (2.6) /\ Lw~' ·Y(x,y) I= (:Ja((2.1) /\ (2.2) /\ (2.3) /\ (2.5) /\ (2.7)) ]. The second equivalence comes from the fact that a can be recursively constructed from x and (2.1), (2.2), (2.3), (2.5) and (2 .7) are 6i formulas which are absolute between Lw"l ·11(:r;,y) and L , and Lw"'l ·Y(x,y) correctly computes La for any a E Lw"'·Y (.r, y). l Since Lw"'·u(x,y) l I= (:Ja((2.1) /\ (2.2) /\ (2.3) /\ (2.5) /\ (2.7)) is IIi by the Spector-Gandy theorem, it suffices to show that it is IIi to say that x is a IIi 21 singleton. Let B ~ ww x w be a universal Ilf set. Let B* be a Ilf set which uniformizes B by the uniformization theorem of Ilf sets. Namely, B* is a Ilf set such that (1) for all m E w, 3x E ww((x, m) EB) <====? 3x E ww((x, m) EB *) (2) for all m E w, there is at most one x such that (:r, m) E B *. Then it clear that x is a Ilf singleton if and only if 3m E w((:r:, m) E B*). Hence , (2.4) is Ilf. D By the s-m-n theorem, there is a recursive function f: w ___... w such that Yx E ww'lly E ww((e,:r:,y) E S <====? (f(e),x,y)) EE. Now, by the effective recursion theorem, there is a fixed point for f, i.e., there is a e E w such that for all real number x and y, (e , x, y) E S if and only if (e, x, y) EE. From now on, let us fix this e E w in this chapter. Lemma 2.8. Suppose that x =/=- y. If (x, y) E Ee, then the one and only one element from the E e-equivalent pair {:r:, y} is a Ilf singleton. Proof. It is clear from the construction. Lemma 2.9. Ee is an equivalence relation. Proof. ( 1) refiexi ty. Clear. (2) symmetry. Clear. (3) transitivity. Assume (x , y) E E e and (y, z) E Ee. Case 1. x = y or y = z, it is trivially true in this case. 22 Case 2. x "/::- y and y "/::- z. Subcase 2.1. y is a Di singleton. In t his case, neither .'.C nor z can be a Di singletons by the Lemma 2.8. Then , x = z = <L -the lease element subject to the same requirement. So, (x, z) E E e. Subcase 2.2. y is not a Di singleton. In this case, both x and z must be Di singletons. Assume that x "/::- z towards a cont radiction. Let a( x) = the unique a corresponding to :r; in the construction, a(z) = the unique a corresponding to z in the construction. Without loss of generality, let us assume that a(x) < a(z). Let n be the least number such that L a (z) I= B(n , e). As (y, z) E E e, from the construction, La( z ) I= "y is the <L" -least element subj ect to the following requirements: y is not a Di singleton, Vz(z is a Di singleton ----. •(z, y) E E e) ." But x E L a (z), since x is definable from a(x) in L a (z) and L a (z) = SkolemHull (La(z))· L a (z) would also think that x is a Di singleton since L a (z ) I= ZFL*. 23 So, La(z) I= (x, y) tJ. E e. But La(z) I= ZFL*, so we have (x , y) tJ. E e. Actually, if La I= KP + "every well-ordering is isomorphic to some ordinal in an order-preserving map," La is absolute for all Di formulas. We can always put enough axioms into ZFL * to guarantee this . But, (:r:, y) E Ee, by our assumption. So, we have a contradiction. D Lemma 2.10. For any Ee-thin Di set A, L I= :Jx(x tJ. A/\ .T is not a Di singleton/\ Vy(y is Di-singleton ====? (x, y) tJ. E e)). Proof. At first, we will show that A is thin. If A is thick, since every Eeequivalence class has at most two elements, there are continuum many Ee inequivalent elements in A. But we know that A is Ee-thin, by Theorem 2.1, so, for every x E A, we can find a A 0 which is 6-i in some ordinal smaller than w'l such that x E Ao ~ A. We have only N1 many such A 0 's. If we blow up the continuum to N2 by the product of N2 copies of Cohen forcing , we will get a contradiction. L 8 21 n ww is also a thin set by the same forcing trick. Now, by the Shoenfield absoluteness theorem, L think that both ww n Loi2 and A are thin. So is their 24 union. Since (Loi2 u A) is thin in L, L I= WW n (L \(Loi2 u A)) -1- 0. Let us pick any x in WW n (L \(Loi2 u A)). This :y; is not a rrt singleton since all rrt singletons are in L 0 ~. Hence this x is not in any Lex, for all a's which are coded by a Di singleton in the sense of our construction. So , x is only E e-equivalent to itself. So, this x witnesses the validity of the sentence of this lemma in L. Theorem 2.11. Th ere is no largest E e-thin Ee-invariant Proof. Assume that there is a largest E e-thin E e-invariant D(lemma) rrt subset of rrt subet of WW. WW. Let n be t he least index for this set wit h the universal Di set A ~ w x ww. L I= ::h (x tJ. An /\ x is not a II i singleton/\ Vy(y is Di-singleton ===? (x, y) tJ. E e) Vm < n(-,B(m, e)). By Lemma 2.4, we can always find x and a such that (2) Lex J= ZFL* /\ B(n ,e) /\ Vm < n-iB(m ,e) /\ 3w(w tJ. An/\ w is not a Di-singleton /\ Vy(y is a Di singleton ===? (w, y) tj. Ee)), (3) Lex = SkolemHull(Lex), (4) x codes Th (Lex) and x is a Di singleton. If x E An, since Lex l=3w( w tJ. An /\ w is not a Di -singleton 25 /\ Vw' (w' is a rJi singleton =? ( w, w') tf. Ee)), let y be the < L,, -least real number in La. Then, (x, y) E Ee by the construction. This contradicts the assumption that An is Ee-invariant. If x tf. An, then An U { x} is still a E-thin, E-invariant IIi set but larger than An. This contradicts the assumption that An is the largest among all the E-thin, E-invariant IIi subsets of ww. Hence, for Ee, there is no largest Ee-thin Ee-invariant set. D(theorem) Remark. By theorem transfer theorem, we know that the same thing is true for all perfect product spaces :X. Next, let us consider "Bi equivalence relations. It is easier to construct a "Bi equivalence relation E for which there is no largest E-thin, E-invariant IIi set. Let A be a "Bi but not IIi subset of w. Let (:r:, y) EE ¢::=;> x = y V (x(O) = y(O) EA). E is clearly a "Bi equivalence relation. If there is a largest E-thin, E-invariant IIi set, say B, we can recover A from B in a IIi way. Claim. n EA ¢::=;> Vx(x(O) = n =? x EB). Proof of the claim. For any n E A, since Dn {x x(O) n} is E-thin, E-invariant IIi set, Dn ~ B. So, .TE B. If n tf. A, we can clearly find a x tf. B such that .r,(O) = n, since Dn = {x : x(O) = n} is E-thick. D 26 Hence, A would be Di, which contradicts the assumption on A. From the argument above, we know that we can actually find a L;i equivalence relation for which there is no E-thin Di set which contains all recursive E-thin, E-invariant subsets of ww. Similar constructions would give us a IT§ equivalence relation for which there is no largest E-thin, E-invariant L;§ subsets of ww. Let A~ w be a IT§ but non- L;§ set, For any :r; and y in ww, let ( x, y) E E if and only if either x = y or x(O) = y(O) E A. If there is a largest E-thin, E-invariant L;§ set B, A can be recovered from B in a L;i way, namely, for all n E w, n E A if and only if 3x(.T(0) = n Ax E B). Actually, there is no E-thin L;§ set which contains all recursive E-thin, E-invariant subsets of ww. The next problem is if there is a L;i equivalence relation E on ww for which there is no largest E-thin, E-invariant L;§ subset of ww. Hjorth showed that the above is false under the assumption that there is O~. Theorem(Hjorth) 2.12. Assume that O~ exists. For any L;i equivalence relation E, there is a largest E-thin, E-invariant L;§ subset CE of ww. To summarize, we have the following table: 27 Pointclass of the Largest Set Pointclass of E L). l 1 2:1 1 rr1 1 L). l 2 2:1 2 2:1 1 rr1 1 2:1 2 rr1 2 x x x x x x ./ x x x x x ./ x x x x x x .; (on) ./ ? ? x II~ Table on the existence of a largest E-thin, E-invariant set for a definable equivalence relation E below b.§. The following problems are open: Open Problems. (1) Is it true or false that for any 2:~ equivalence relation E, there is a largest E-thin, E-invariant subset of ww? (2) Is it true or false that for any b.~ equivalence relation E, there is a largest E-thin, E -invariant subset of ww? 28 3. The General Case In this chapter, we will solve the following problem negatively. Problem. Is it true that there is always a largest E-thin, E-invariant subset of ww for any given II~n+ 1 equivalence relation E? In Chapter 2, we solved the problem for IIi equivalence relations negatively. We constructed a IIi equivalence E for which there is no largest E-thin, Einvariant set. Using t he work of Kechris and Martin in [KMl], it seems not difficult to lift our result to II§ equivalence relations. But the same argument cannot go any furth er without a generalization of the work in [KMl] to higher levels. It seems that J ackson has finished this generalization recently. But we can get around the difficulty by using Q-theory and the Martin-Solovay basis result for 2=~n+l sets. We will answer the general problem negatively in this chapter. Before we go any furt her, let us fix our notation first. Let GX be a good universal system for the II~n+l sets of the Polish space X. For simplicity, let E = Gwwxww ~w x(wwxww),A =Gww ~wxww,G=Gwxwxww ~wx(wxwxww). Let G uniformize Gas a subset of (w x w x w) x ww, i.e., \Im, n, k[:Jx(m , n, k , x) E G -7 :Jx(m, n, k, x) E G] !\\Im, n, k, x, y((m, n, k , :r) E G /\ (m, n, k, y) E G - 7 x = y) . 29 We always use m,n,k,l,d,e for natural numbers and a,/3,:r,y,n,v for reals in this chapter. All of the other notations should be standard as in [Mol]. We always assume .6.§n determinacy throughout this chapter. Let Az enumerate all the II§n+l sets . We will use a sequence {xk}kEw of II§n+l singletons to destroy the possibility of Az being a largest E-thin, E- invariant set. For each l, if xz E Az, we will introduce an element y such that yEx 1 but y ti. A 1. This will make A 1 not invariant. If x z ti. Az, we will ensure that x is the only element which is E-equivalent to x. That will make A 1 not the largest, since Az U { :r;} will be invariant if Az is. We have to work carefully to ensure that our equivalence relation Eis II§n+i · We ensure this by using the recursion theorem and some I.;§n+l elementary models generated by singletons. Since our main building blocks for our II§n+l equivalence relation E are II§n+l singletons, let us review a theorem of Harrington about II§n+l singletons. Theorem(Harrington) 3.1. To each real a, we can associate a real Y2n+l such that: (1) For each a, Y2n+l is a (representative of the ~§n+ 1 (a) degree of the) flrst non-trivial II§n+l (a) singleton. The formula . rr12n+l · lS (2) For each a, a ~T Y2n+ 1 , and a ~T /3 ---> Y2n+l ~T Ygn+i · In fact, these reductions are uniform. For instance, there is total recursive p : w ____, w 30 such that (3) For all a, (3, (4) Let £i2n+i(a) = {YA,c/) :A E ~~n ,A #- 0,¢ is an excellent ~~n+ 1 ( a) scale on A}. Then Y2n+ 1 E £i2n+ 1 (a) and every real in £i2n+i (a) is recursive in Y2n+l· In particular, Y2n+i is a recursive basis for ~§n+ 1 (a), i.e., every non-empty ~§n+ 1 (a) set contains a real recursive in Y2n+i· Proof. See [KMS] D Definition. Let U ~ w x ww x w x w) be a semi-recursive set universal for all semi-recursive sets of w x w. Let tJ uniformize U as a subset of (w x ww x w) x w. We will call a real x good iff (1) x =(x 0 ,x 1), · H 2n+1 ( x 0 (·) · t he (2) x O(·1, + 1) = y 2xo(i) n+l, 1,.e., 1, , x 0 (·1, + 1)) , w here H 2n+1 as in above theorem of Harrington, (3) 1 . . x(1,,J,n) = { m, if \fn:JmU(j, x 0 (i), n, m) and U(j , x 0 (i), n, m), 0 if :Jn\fm-,tJ(j, x 0 (i), n, m). 31 If x is good, then for any i,j, let Xi ,j be the real defined as following: It is easy to see that {xi,.i: j E w} ~ {y: y :Sti.t :r:0 (i)}. If x is good, let Mx =d.f. {y: y :Sr x 0 (i) for some i E w} ( = {:r:i,.i: for some i,j}.) It is II§n+l to say that x is good , namely, we have Lemma 3.2. There is a II§n+ l formula ¢(:1:) s11 ch that '"( x ) <===? 'F P roof. Clear. "x 1s. goo d" . D We have a natural well-ordering among reals of M,r, for any good :r:. For any y and z in Mx, let (iy, Jy) be the first pair of integers such that y = Xiv ,.iv and (i z, j z) be the first pair of integers such that y = xi z ,.i z where Xi ,.i is as given in t he definition of being good . Let It is clear that this well-ordering is recursive in x. Lemma 3.3. If x is good , ¢(x 0 , ... , ::r n) is projective, then there is an arith- metical formula 'lfJ(x , xo, ... , xn) such that lvfr, F= ¢(xo, ... , Xn) <===? 'l/J(x, xo, ... , Xn)· 32 Proof. It is easy to see that we can always replace all quantifiers over reals by quantifiers over natural numbers because any element of Mx can be recursively recovered from x. Lemma 3.4. D If x is good, then Mx -<E12n+l V , i. e., for any I:§n+l formula cp(xo, ... , ::r;n), any Yo, ... ,yn E M.r Proof. We use induction on the complexity of ¢. It is obviously true for arithmetical formulas. Assume that it is true for all I:l (and hence Ill) formulas with k < 2n + 1. Let ¢(xo, . . . , .Tn) = 3w1f.; (w , xo, ... , xn) be I:§n+l· Let Yo , ... ,yn E Mx, if Mx I= ¢(yo, .. . , Yn), it is clear that ¢(yo, ... , Yn) holds. Now, assume that ¢(yo, .. . , Yn) holds. As Yo, . .. , Yn is in Mx, t here is an i E w such that Y.i °'5:.T .r,(i) for 0 "'5:. j "'5:. n. Let D = {w : ?j.;(w,yo, ... ,yn)}, D is II§n(x(i)). By Martin-Solovay basis results, there is Wo E D such that Wo E rr§n+ 1 ( x (i + 1) ). By Harrington's theorem, wo °'5:.T x(i + 2). Thus wo E Mx. We get M.r I= ¢(yo, .. . ,yn)· D Definition. Let B ~ w x w x w x ww be the set defined as following: ( d, e, l , x) E B iff (1) x is good, (2) Mx I= "\::/k < l Ak is not the largest E e-thin E e-invariant set," 33 (3) 'Ilk < l Gd ,e, k #- 0 and st.unif.(Gd,e,k) E M.'E where st.unif. stands for standard uniformization, i.e., 'Ilk < l,3y E M.'E ((d,e,k,y) E G). Lemma 3.5. Bis II§n+I · Proof. (2) is II§n+l because of Lemma 3.4. Lemma 3.6. D There is ad* E w such that (d*, e, l, x ) EB if and only if(d*, e, l, x) E G . Proof. This is by the recursion theorem. From now on, let us fix this d*. We will construct our equivalence relation by the recursion theorem again. Definition. Let S ~ w x ww x ww be defined as following: (e, x, y) E S iff EITHER x = y , OR for some l (1) x E Az, (2) x = st.unif.(Bd*,e,1), i.e., (d*,e ,l,x) E G, (3) y =the ~M,, -least real in M.'E subject to the following requirements: (i) y E (M.'E \Az) n ww (ii) 'Ilk < l y$est.unif.(Gd*,e,k )· 34 OR for some l (1) y E Az, (2) y = st.unif.(Bd* ,e, z) , i.e., (d*, e, l, y) E G, (3) x = the ::SM11 -least real in My subject to the following requirements: (ii) Lemma 3. 7. Vk < l, xJ?est.unif.(Gd*,e,k)· S is II§n+i · Proof. Lemma 3.4 implies that (3) 's are II~n+i · All others are clearly II§n+i · D By the recursion theorem again, we have the following Lemma 3.8. There is a natural number e* such that (e*, x, y) ES if and only if( e*, x, y) EE. Lemma 3.9. E e* is an equivalence relation. Proof. Refiexity and symmetry are clear from our definition. Let st.unif. (Gd* ,e* ,k), rk = { 0 ' if Gd· ,e• ,k =I 0 otherwise. Actually, we will show that Gd· ,e• ,k =I 0 for all k E w later in this chapter. We will next show that Ee· is transitive. Assume xEe•Y, and yEe*z . 35 Case 1: x = y or y = z, it is obviously true. Case 2: x -/::- y and y -/::- z. From the construction, our Ee• has the following properties: (1) No Ee•-equivalence class has more than two elements. (2) If .TE e· y, then either :r = y or exactly th of x and y must be a rk for some k E w. Subcase 2.1: y is a II§n+l singleton. In this case, both x and z cannot be II§n+l singletons. So, :r; = y = the "5:.M 11 -least element subject to the same requirements. Subcase 2.2: y is not a II§n+l singleton. In this case, x and z are II§n+l singletons. Assume that ;r; -/::- z, towards a contradiction. Suppose lx and l11 are the corresponding l in our construction of Ee*, lx -/::- l71 since x and y are uniquely determined by (d*, e*, lx) and (d*, e*, l11 ) respectively. Without loss of generality, we assume that lx < l11 • From the construction, x = st. unif. ( Bd· ,e• ,z,,) and y = st.unif.(Bd•,e•,1J. As lx < l11 , from the construction of B , we know that st.unif.(Bd•,e•,zJ E M11' Now, we get a II§n+ l singleton x = rz,, E M 11 such that ( z, x) E Ee•, which contradicts with the assumption yEe* z and y -/::- z. Theorem 3.10. D Assuming A.§n determinacy, there is no largest E e· -thin, E e· -invariant set for the II§n+I equivalence relation Ee*. Proof. Let A ~ w x ww universal for II§n+l sets as fixed at the beginning. By 36 induction on l, we will show that for all l, (1) Gd* ,e*, l =/:- 0, (2) for any good .T, if rz E Mx, then M.r, F= "Az is NOT the largest E e* -thin, Ee*-invariant set," (3) A 1 is NOT the largest Ee*-thin, E e* -invariant set. Assume ( 1), ( 2) and (3) for all k < l. Now , we will show that they are still true when k = l. ( 1) It is clear because any good .T such that Xi E M x for all 0 :::; i < l is an element of Gd*, e* ,l, where xi= st.unif.(Gd*,e*,i)· (2) Let x be a good real and rz E Mx. Let us work in M.r,. If rz ti Az (= At1"') , [rz]E,,* = {rz}. So , Az U {rz} is E e* -thin, Ee*-invariant but larger than Az. Thus, we have Mx F "Az is NOT the largest E e* -thin, Ee*-invariant set." If rz E Az , as V F ":Jy(y ti Az /\ y Jfe*ro /\ · · · /\ y Jfe*rz_i) and Mx -<L:12n+l V , there must be such yin M.r,. Thus M x F "Az is not Ee*-invariant." Thus, Mx F "Az is NOT the largest Ee·-thin, Ee*-invariant set." (3) It is similar with (2) but simpler. D Let us give a summary of the relative results before we finish this chapter. In [Kel], Kechris proved the following 37 Theorem (Kechris) 3.11. Assume Det(Ll~), let E be a II§ equivalence relation on ww. If A ~ ww is II§ and E-thin, then for each x 0 E A, there is an Ao 6§ in an ordinal smaller than KI 0 such that Xo E Ao ~ [xo]E n A. For a II§ E, if we let CE= {x: 3S(S is 61 in an ordinal smaller than r;;f and x ES~ [x]E)}. A is an E-thin II§ set which contains every E-thin II§ subsets of ww. So, there is a largest E-thin II§ subset of ww. Let C4(E) = {x: :::JS ( Sis 61 in a ordinal< K1 /\.TES~ [x]E)}. In [Kel], Kechris observed that this C 4[E] is the largest E-thin, E-invariant I:! set for the II§ equivalence relation E. Hence we have the following Theorem (Kechris) 3.12. For any II§ equivalence relation E on a product space X, there is a largest E-thin, E-invariant I:! set which contains every E-thin, E-invariant I:! subset of X. If E is actually 6§, Kechris also noticed the following Theorem(Kechris) 3.13. For any 6§ equivalence relation E on a product space X, there is a largest E-thin, E-invariant II§ set. 38 The largest E -thin, £-invariant set mentioned above can be defined as C 3 (E) = LJ{C :C is an £-equivalence class /\ Vx E C( C is 6.~ in an ordinal smaller than K~)}. A similar construction as in Chapter 2 would give us a I;§ equivalence relation Eon ww for which there is no largest £-thin, £-invariant 11§ set. Also, we can construct a 111 equivalence relation Eon ww for which there is no largest E -thin, £-invariant L:;l set. Hence, we have the fo llowing table: Pointclass of the Largest Set Pointclass of E 6.§ I; 1 3 11§ 6_ l 4 I; 1 4 111 4 I; 1 3 111 3 I; 1 111 x x x x x x ./ x x x x x ./ x x x x x x 4 ? ./ ? ? x 4 Table on the existence of a largest E -thin, £ -invariant set for a definable equivalence relation E below 6.g. The fo llowing problems are open: Op e n P roblems . (1) Is it true or false that for any L:;l equivalence relation E, there is a largest E -thin, £-invariant subset of ww including all E -thin, £ -invariant L:;l 39 subset of ww? (2) Is it true or false that for any .6.l equivalence relation E, there is a largest E-thin, E-invariant subset of ww including all E-thin , E-invariant I:l SU bset of WW ? (3) Is it true or false that for any I:§ equivalence relation E, there is a largest E-thin, E-invariant subset of ww including all E-thin, E-invariant I:l subset of ww? In the most general case, we know less than in the case of the third and fourth levels . The following is a table which summarizes what we know right now Pointclass of the Largest Set Pointclass of E I:§n+l x x x x x x rr§n+l ? .6.§n+l x I:§n+l x II§n+1 x .6.§n+2 x I:§n+2 x II§n+ 2 Table on the existence of a largest E-thin, E-invariant set for a definable equivalence relation E below .6.§n+ 3 . I:§n+2 ? ? ? ? ? x II§n+2 x x x x x x The following problem is open: Open Problems. (1) Is it true or false that for any I:§n+ 2 equivalence relation E, there is a 40 largest E-thin, E-invariant subset of ww? (2) Is it true or false that for any .6.§n+ 2 equivalence relation E, there is a largest E-thin, E-invariant subset of ww? (3) Is it true or false that for any L;§n+l equivalence relation E, there is a largest E-thin, E-invariant subset of ww? (4) Is it true or false that for any .6.§n+ 1 equivalence relation E, there is a largest E-thin, E-invariant subset of ww? (5) Is it true or false that for any II§n+I equivalence relation E, there is a largest E-thin, E-invariant subset of ww? 41 4. ~1, II1 and D..1 in the Codes Subsets of Uw In this chapter, we will prove some technical lemmas on ~§, II§ and .6.§ in the codes subsets of nw. On one hand results about the ~§ in the codes, II§ in the codes and .6.§ in the codes sets are close relatives of results about the third level of the analytical hierarchy on real numbers. On the other hand, they can be considered as the IIi, ~i and .6.i subsets of (nw, <, { n 11,}) under the full determinacy. Even without AD, they often look like sets of the first level of the analytical hierarchy. All of the results in this chapter should be considered as folklore or direct generalizations of the classical results. However, we have to be careful when we generalize the classical results to this context. We collect here some results we will use later on to prove our theorem in Chapter 6 because it is not easy to find them in the literature. To fully investigate the analytical hierarchy on nw, the full determinacy is required to code all subsets of nw. We do not deal with it here. [Kel] is a good reference for the related results, while [Ke2] is a good reference for the analytical hierarchy over ~ 1 . We assume ~~ determinacy from now on. Harrington showed that IIi determinacy implies that V.r, E ww(x~ exists), so, we have all the sharps for reals available. We adopt the standard coding system for the ordinals smaller than Uw as in [KMl]. Let w E WOw if and only if w = (n, x~) for some n E w, x E ww. For any 42 IW I -_ TnL[x] ( 7J,1, . . . , 11,kn ) , where n°' is the ath uniform indiscernible and Tn is the nth term in a recursive enumeration of all terms in the language of ZF+ V = L[x] always taking ordinal values. From Solovay's theorem, Uw = {lwl : w E WOw}· clear that ""'w is an equivalence relation. We call P( w, x) ""'w-invariant on w if and only if for any w1, w2 in WOw, and :r; in ww, if w1 ""'w w2 and P(w1, x), then P(w2, x). The following theorem is essential for getting results in the third level of the analytic hierarchy, and is the cornerstone of our results in this chapter too. Theorem (Kechris and Martin) 4.1. Assuming A~ determinacy, if P (w, x) is II§ and ""'w-invariant on w and 3w E WOwP(w, x), then 3w E WOw n 6.§(x)P(w,x). Proof. See [KMl]. Corollary 4. 2. D Assuming A~ determinacy, if P (w, x) is '"'"'w-invariant on w and II§, and R(w,:r:) ¢::::::> ::lw E WOwP(w,x), then R(w,x) is also II§. Let m. times n times k times ~ X m,,n,k = Uw m , X ( W w)n X W k = 1Lw X · · · X 1Lw X W w X · · · X W w X W X · ·· X W . 43 For A ~ :x:m,n,k, let be the pullback of A under the coding map given by the uniform indiscernibles and Skolem terms at the beginning of this chapter. For notational simplicity, we will use i for .T 1, · · · , Xn, if for Y1 , · · · , Ym, i for 'l1, ... , ik Xm and a for 0'.1, ... , O'.m. We use i E WOw to express X1 E WOw,. .. , E WOw. We also use x and a to represent (i, if, i) and (a, iJ, i) respectively to simplify the notation further , if it is clear from the context. We write Iii to Definition. For A~ :x:m,n,k, we call A~§ (II§, ~§(x), II§(x), ~§, ~§(x)) in the codes if and only if A* ~ :X:o,m+n,k is ~§ (II§, ~§(x), II§(x), ~§, ~§(x) respectively). ~§(:X:m,n,k), ~§(x, :x:m ,n,k ) respectively) to represent the corresponding point- classes. It is easy to see the following Lemma 4.3. '\f1Lw . Moreover ' ~ 31 (:X:m,n,k) is closed under ::iww ' II 31(:X:m,n,k) is closed 44 t:i.§(Xm ,n,k) is closed under'· Proof. (1) By Lemma 4.1, l:§(Xm ,n,k ) is closed under \f1'·w and II§(Xm,n,k) is closed under :::J 7lw. All of the others are trivial. (2) Let U0 ~ w x Xo,m+n,k be a universal 2:§ set for all 2:§ subsets of Xo,m+n ,k. Let U1 = {(n , x, y,i): .i E WOw}, which is t:i.§. Let U2 = {(n ,x,y,i): (n ,x, y,i) E U1tdx1 (.i ' E WOwAlx'I = lxlA(n,x,y,i) E U1)}. Let W = {(n, a, y, i) : 3£ E WOw(a = Jxj) /\ (n, x, y,i) E U2). It is easy to check that Wis l:§(Xm ,n ,k) and universal for all l:§(Xm,n,k) subsets of xm,n ,k. It is similar to prove that II§(Xm ,n,k) is w-parametrized . D Remark. Similar facts hold for the pointclasses l:§(x, Xm ,n,k), II§(.T, xm ,n,k) and "1 ( x, xm.,n ,k) a 1so. LJ. 3 45 Definition. Let a E 1Lw, we call A s;;; :xm,n,k I.:§ in a in the codes (II§ in a in the codes respectively) if and only if A* s;;; '.Xo,m+n ,k is "uniformly" I.:§(x) (II§(x) respectively) for all :r; such that lxl = a , i.e., there is a I.:§ (pth respectively) . B C _ '.X O,m+n+l,k sueh th a t for a 11 x co d"mg· a, for a 11 x1, · · · , Xm,, Y1, · · · , Yn m We will use I.:§(a,'.Xm. ,n,k) (II§(a,'.Xm. ,n,k), 6§(a,'.Xm. ,n,k) respectively) to represent the corresponding pointclasses. We will use *I.:§('.Xm. ,n,k) (*II§('.Xm. ,n,k), * 6§('.Xm.,n,k) respectively)to represent '.Xm.,n,k) (LJ Ill( '.Xm.,n,k) LJ 61( '.Xm.,n,k) UaEWOw I_;l( 3 a, aEWOw 3 a, ' aEWOw 3 a, respectively). It is easy to see that for any A s;;; :xm,n,k , A is I.:§( a) ( II§( a) or 6§( a)) in the codes iff there is a I.:§ (II§ or 6§ respectively) in the codes B s;;; 11.w x :xm,n,k such that A= Ba = {(a, y, i) : (a, a, y, i) EB)}. As usual, we have Lemma 4.4. '.Xm,,n ,k) , Ill( a, '.Xm. ,n,k) an d uA 1( a, '.Xm,,n,k) are c·1ose d un d er"' " V, (1) "l( L.J 3 a , 3 3 3uw V1'w ' . Moreover I.: 1 (a :xm,n,k) is closed under 3ww II 1 (a :xm,n,k) ' 3 ) ' is closed under'iww and 6§(a ,'.Xm. ,n,k) is closed under-,. 3 ) 46 . d. u 3 ( a, xm.,n ,k) an d Ill3 (a, xm.,n,k) are w-parame t nze (2) "'l Remark. The relativized version holds as well. Lemma 4.5. *I:§(Xm,n,k) and *II§(:Xm,n ,k) are 71.w-parametrized, i.e., there are I:§ in the codes U ~ 11.w x xm,n,k and II§ in the codes V ~ 11.w x xm ,n,k such that for any I:§( a) in the codes A ~ xm,n,k and II§( a) in the codes B ~ xm,n)c, there are f3o, f31 E 71.w with A= Uf3 0 = {(ci, y,i): (f3o, ci, y, i) EU} A= vf3 1 = {(a,y,i) : (f31,a,y,i) Ev}. Proof. Let f: 71.w x w --+ 71.w be a ~§ in the codes bijection between 71.w x w and 11.w. Let W ~ w x xm+l ,n,k be a I:§ in the codes set universal for all I:§ in the codes sets of nw x xm ,n,k. Let U ~ ?/,w x x m,n,k be defined as the following It is easy to check that U works. We can define V in a similar way. D Sometimes, we need a better parametrization for the *-pointclasses. We have the following refinement. Lemma (The Good Parametrization Lemma) 4.6. We can associate with each space xm ,O,k a I:§ in the codes set cm,k ~ 11.w x xm,O ,k and a II§ in 47 the codes set Hm,k s: Uw x xm,O,k such that (1) cm,k is universal for all *~§(xm,O,k) sets and Hm,k is universal for all (2) for p S,: Xm,O ,k, (3) for each m 1 ,m2 k 1 , k2 in w, there are a .6.§ in the codes (which means Proof. We will prove the ~§ part of this lemma, i.e., we will construct the cm,k only. The II§ part can be proved similarly. Let h: nw x ?J,w ----7 ?Lw be a .6.§ in the codes bijection between v,w x 7Lw and 1J,w such that (1) h[w x w] = w (2) there are .6.§ h1: 7Lw ----7 11,w and h2: 7Lw-----) w decoding h, i.e., if h(a, n) = {3, then h 1 (f3) = a and h2 (f3) = n . 48 Let U ~ w x 1Lw x xm,o,k parametrize ~j(?Lw x xm,o ,k). Let G*(ex,ci,i) = U(h'2(ex),h1(ex),ci,i). It is easy to check that G* satisfies (1) and (2). So, we can always assume that we have a parameterization system satisfying (1) and (2). Ok fi x 7r m,k: 1Lw x -vm 0 k · · h d b"IJect10n · · -A- ., ' ·, -A- . , ' , ----+ 1J,w a recursive m t e co es For -vm and universal for the *~j(v,w x 1Lw) subsets of 1J,w x ?Lw so that (1) and (2) hold. Define cm,k ~ 1Lw x xm ,O,k by It is clear that cm,k is ~§ in the codes. D Claim. cm ,k is universal for the *~j(xm,O,k) sets and satisfies (2). Proof of the claim. Suppose Q ~ xm ,O,k is *~j(xm,O,k), let where Pm,k: 1Lw x xm ,O,k ----+ xm,O,k is the projection map on xm,O,k. Now, Q' is *~§(v,w x 1J,w)· For any ex, taking {3 = Km,k(ex, ci, i), we have Q(ci,i) ¢::::::} Q'(ex,7rm,k(ex,ci,i)) ¢::::::} V(c, ex , Km,k(ex, ci, i)) ~ ~ cm,,k(( c:,ex,ex ) ,ex,1,. __, -;') 49 If Q is I:§ in the codes, Q' is also I:§ in the codes, by our selection of V, we can choose c E w above. If we choose a E w too, we get c=;* = (c , a, a) E w and k( * - -:') Qa,1, ( - -:') ¢=:::>G m ·,·s,a,1,. D Claim. {Gm,k}m,kEw satisfies (3). { (/J, )) : (/J, )) E :x:m 2 ,O,k 2 }. We will try to construct a ~§ in the codes Put P( a, (3) ¢=:::> Ji (Pm1 ,k 1 ( 7f~.~ ,k 1 ( ( O'. )i))' Ji (Pm2 ,k2 ( 7f~.~ ,k 2 ( ( O'. )2)))' where fo: Xm,O,k _, Xm,O ,O is defined as fo(a, i) =a, and fi: Xm,O,k -+ XO,O,k is defined as Ji (a, i) = i. Now, P is 'E§ in the codes, so there must be a s* E w such that (**) P(a,(3) ¢=:::> V(s* ,a,(3). 50 then by the definition of cm 2 ,k 2 ' we have that 7 m.1,m.2,k1,k2( E,cx,i ) = ( E, * (E,7rm 1 ,k 1 (E, cx,1, - 7)) ,E, ) from th e argument a b ove, L e t s:B The following effective recursion theorem is the main tool we used in the next section to construct the II§ in the codes equivalence relation e on 1Lw. Lemma (Effective Recursion Theorem) 4. 7. Let {Gm ,k}m ,kEw and {Hm.,k}m.,kEw be the good parametrization system given by the last lemma. (1) For any*~§ (or *IT§) in the codes subset A of?J.w x Xm.,o,k, there is an E E 1Lw such that (or - -;') A( E,cx,1. <===:;:. Hm"·1r ( E,cx,1,, - -;') respectively). (2) For any ~§ (or II§) in the codes subset A of w x xm,O,k, there is an E E w such that (or respectively). 51 Proof. This can be proved by the classical diagonal method. We will prove the I;§ part only because the proof of the other part is similar. (1) Let A~ Uw x xm,O,k is *I;§ in the codes. We define for (5, i) E xm ,O,k and rt E uw, B(rt, 5, i) {::::::::} A(sl,O,m.,k(T/, rt), 5, i). As A is *I;§ in the codes, so is B, hence, for some EB E v.w, one has - -:') B (c,CI.,?, {::::::::} cm+ k ( EB,E,CI.,?,. - -:') . 1 '. lOmk( . c wor ks, as Lt ' ' EB, EB ) , we c1aim e c = Si A(c, 5, i) {::::::::} A( SL;1,0,m.,k ( EB,EB ) ,Cl.,?, - -:') by the definition of c {::::::::} B(cB, 5, i) by the definition of B {::::::::} cm+l ,k (c {::::::::} cm,,k (c, 5, i) B, c B, 5 "i) by the definition of s~O,m.,k by the definition of c. (2) Let A ~ w x xm,O ,k is I;§ in the codes. We define for (5, i) E xm,O,k and n E w, - 7) B( n,a,1, {::::::::} A( sOlmk( --:') . ' ' " n,n ) ,a,1, As A is I;§ in the codes, so is B, hence, for some EB E uw, one has - -:') {::::::::} cm., k+l( - n, -:') · c B , a, ?, • B( n, a,?, k( c B , c B ) , from th e d efi n1·t·10n of s O,l,m.,k Let 'c-' = s O,l,m,, L: L: , '-'c E W. It i·s similar to show that c works. 52 D Lemma (Spector-Gandy Theorem for rg, Becker and Kechris) 4.8. There is a tree T2 satisfying the following requirements: (1) T2 <:;;: (w x 11.w)<w is .6.§ in the codes, (2) p[T2 ] is the complete II~ set of ww. (3) For any A<:;;: ww, A is II§ if and only if there is a I; 1 formula SoA(x) such that Proof. Though the proof in [BKl] works for different trees , by checking the proof in detail, we can adopt the proof there to get this lemma. D From now on, let us fix such a Martin-Solovay tree T 2 . Corollary (Spector-Gandy Type Theorem for II§(Xm,o,k )) 4.9. Ac xm,O ,k - For any ' (1) A is II§ in the codes if and only if there is a I; 1 formula SoA such that (2) A is II§ in the codes if and only if there is a I; 1 formula rp A such that (3) A is .6.§ in the codes if and only if there is a .6. 1 formula rp A such that 53 From this corollary, it is easy to see that every 6.§ in the codes subset of some uw is in LK.3 [T2 ] . The similar result is not t rue for I:§ and II§ subsets. But Professor Hjort h has the following Lemma (Hjorth). All IT§ in the codes subsets of some a< uw ar e in L K, 3 [T2 ]. Now we are aiming towards proving the norm property and some corollaries from it. The following theorem of Solovay provides the norms for the pointxm.,n,k) . c1asses IT 3l(x m.,n,k) an dITl( 3 a, Lemma (Solovay) 4.10. Assuming a § determinacy, let,....., be a I:§ equiva- lence relation on a space (ww) 1, let P ~ (ww)l be rv-invariant (i. e., .T E P /\ :r; ,....., y - t y E P ), then there is a rv-invariant (i.e., for any x and y in P , if x ,. . ., y, then rp( x) = rp(y)) norm IT§: P - t Ord. Proof. See [Ke2]. D Corollary 4.11. IT§( a, x m,n,k) is normed, i. e., for any IT§( a) in the codes A ~ x m,n,k, there is a f; E Ord and a rp: A - t f; such that the relations x :::;~ x * and x <~ x * are IT§(a) in the codes, where x -< cp* x * <===::;> x EA/\ (x* t/-. AV rp(x):::; rp(x*)), x <~ x * <===::;> x EA /\ (x* tJ. AV rp(x) < rp(x*)). Corollary (Kreisel Uniformization Theorem) 4.12. If A~ xm.,n,k x w is IT§( a) in the codes, then there is a B ~ x m,n,k x w which is IT§( a) in the 54 codes such that (1) V(a, i, i) E :xm,n ,k (::Jn E w(a, i, i, n) EA---+ :3!n(a, i, i, n) EB), (2) B ~A. Corollary (Kuratowski Reduction Theorem) 4.13. Let A and B be two II§(a) in the codes subsets of:Xm,n ,\ then there are two 6§(a) in the codes A' and B' with A' c A ' B' c B ' AU B =A' U B' and A' n B' = 0. Corollary (Seperation Theorem) 4.14. Let A and B be two L::§(a) in the codes sets of:Xm.,n,\ An B = 0. Then there is a 6§(a) in the codes C which separates A from B, i.e., such that A~ C and C n B = 0. With the help of these results, we can code the * 6§ subsets of :xm,O,k. Lemma (Coding the* 6§(:Xm,O,k) Sets) 4.15. There is a pair (D, W) such that ( 1) D ~ 7Lw is IT§ in the codes and W ~ 7Lw x :xm.,O,k is 6§ in the codes in D x :xm,O,k, i.e., there are I:§ in the codes WI: ~ 7Lw x :xm,O,k and II§ in the codes wrr ~ 7Lw x :xm ,O,k such that w = (D x :xm,O,k) n WI; = (D x :xm,O ,k ) n wrr ' (3) if A ~ Uw is *IT§ in the codes and B ~ Ax :xm,O,k is* 6§ in the codes in A x :xm ,O,k, then there must be a 6§ in the codes function f: 7Lw ---+ 7Lw such that for all a EA, f(a) ED and W.r(°') = B°'. 55 Proof. Let V 0 = {(c:,a ,i): ((c:) 0,a,i) E Hm.,k}, v 1 = {(c:,a,i): ((c:)i,a,i) E Hm,k} . By the Kuratowski reduction theorem, let (U 0 , U 1 ) reduce (V 0 , V 1 ), i.e., U 0 and U 1 are II 31 in the codes ) u0 c- v 0 ) U 1 c- V 1 ) U 1 nU 1 = 0 and u 0 uu 1 = v 0 uv 1 . Let D = {c E Uw: \l(a,i) E Xm,O,k((c: ,a, i) E U 0 V (c:,a,i) E U 1 )}. D ~ v,w is II§ in the codes. Let w = { ( c) a) i) : c E D /\ (c) a) i) E u 0 } . Clearly, w is .6.§ in the codes in D x xm.,O,k) as c E D /\ (c, a, i) fj. W ¢:=:? c E D /\ (c:, a, i) E U 1 , by the definition of D. As (2) is a particular case of (3) when A= D and B = Hm,k, we will show (3) directly here. Let A ~ uw be *II§ in the codes and B ~ A x xm,O,k be *II§ in the codes. Let 7 - 7) - i ) E B} , B o = {c, a, 1, E Uw x xm 'o' k : c E A /\ (c, a, - 1,-;') E 11,w X xm. ,O ,k : c E A/\ (c, a, - 7) rf B} , B l = { c, a, 1, 'F- 56 are both *II§ in the codes in Uw x xm,O,k. Hence, there are ~§ in the codes functions f o : Uw -+ ?Lw and Ji : ?Lw -+ Uw, such that for i = 0 or 1, (*) Set f(c) = (fo(c) , fi(c)). We check that this f works. Fix EE A. We have B E: = B E:0 and B E:1 = xm,o ,k\B E:· Now ' vo Hm,k f(ro) = .fo(ro) by the definition of v 0 by (*) , =BoE: and vif(ro) = Hm,k .fi(ro) = B1E: by the definition of v 0 by (*)' so that V?(ro) n Vhro) = 0 and V?(ro) U Vhro) = xm,o,k. But this implies that U.~(ro) = V?(ro) and U.~(ro) = V?(ro)' so that U.~(ro) U U}(ro) = Xm.,o,k, i.e., f(c) ED, and moreover W as desired. f(ro) = uo .f(ro) Bo = Vo.f(ro) = Hm,k .fo(c) = c D We have coded the ordinals smaller than Uw using sharps at the beginning of this section. But that is not enough. We need an induction all the way to "' 3 to get a representation theorem for the II§ thin equivalence relations. We have 57 to find a method to code all of the ordinals smaller than K 3 . We will do this coding using ordinals smaller than 11.w in the following. Let D ~ 11.w II§ in the codes and W ~ D x nw x v,w 6.§ in the codes in D x 1Lw x 1Lw as given by the lemma above, let WE and wn as given in the lemma above also. Definition of LOnw and WOnw. LOnw = {a : a E D and Wa is a linear ordering on 11.w} WOuw = {a : a E D and Wa is a well-ordering on v,w} As for any a E D , a E L0 11 w if and only if Vf3o < nw"Vf31 < 11,w(f30W~f31 _, f3oW;f3o !\ f31 w;f31) /\ Vf3o < 1Lw V/31 < 11.w (f3o W ~ /31 !\ f31 W ~ f3o - t f3o = /31) !\Vf3o < nwVf31<1Lw"Vf32 < nw(f30W~f31 /\f31W~f32 - t f30W;f32) !\Vf3o < 1Lw Vf31 < 1Lw (f3o W~ f3o !\ f31 W~ f31 - t f3o w; f31 V /31 w; f3o), by the Kechris-Martin theorem, it is I:§ in the codes in D x xm,O,k. On the other hand, for any a E D, a E L0 1,w if and only if Vf3o < 1Lw"Vf31 < nw(f30W;f31 - t f3oW~f3o /\ /31 W~f31) !\ Vf3o < 1Lw V/31 < 1Lw (f3o W; /31 !\ f31 W; f3o - t f3o = /31) !\ Vf3o < 1Lw V/31 < 11,w V/32 < 1Lw (f3o W; /31 !\ f31 W; /32 - t f3o W ~ /32) !\Vf3o < nwVf31<11,w(f30W;f30 !\f31W;f31 _, f30W~f31 V f31W~f30), 58 it is II§ in the codes in D x Xm,O,k. Hence, it is .6.§ in the codes in D x Xm,O,k. As /\ {3(n + l)Waf3(n)) _. 3n(f3(n + 1) = {3(n))), wo1Lw is II§ in the codes. Definition. For each CY E WOuw, let llCYll =the length of the wellordering coded by CY. Lemma 4.16. For any CY E wotlw) Proof. It suffices to show that llCYllL"3 [T2 l = llCYll · If CY E wo1lw) let Ra (~) rJ) be the .6.§ in the codes wellordering on Uw coded by CY. As Ra is .6.1 in the model LK 3[T2] and LK 3[T2] I= KP, Ra E LK, 3[T2]. LK 3 [T2] I= KP also implies that there is a rank function for Ra in LK 3 [T2], since Ra is a well ordering in V. This can be proved by an induction along the wellordering Ra· So, it makes sense to talk about llCYllL"3[T2 l. If llCYllL"3[T2 l = (3, then there is an order preserving one-to-one onto map h: Uw _. f3o in LK 3[T2]. This his also in V. This h witnesses that llCYll = (3. D 59 Definition. For any a, /3 in v,w, let a ::;* /3 {::=} a E wo1Lw /\ (/3 E wo1Lw ---7 llall ::; 11/311) a -<* /3 {::=} a E WOv.w /\ (/3 E WOuw ---7 llall ::; 11/311 · Lemma 4.17. Both =S* and -<* are II§ in the codes. Proof. Let D, W, wn and WL: as in Lemma 4.15. Let 'PL: (c, ~, 'T/) be a II 1 formula such that for all c, ~ and rJ in 71,w, Let cpn (c, ~, 'T/) be a ~ 1 formula such that for all c, ~ and rJ in v,w, It is easy to check that for all a and /3 in 71,w, 3y3f (y = 71,w /\ f is a function from y to y /\ f is one-to-one on the domain of a /\ '11~,'T/ E y(cpn(a,~,rJ) /\ •cpL:(a,~,rJ) ---7 cpL:(j(/3), ~' f(rJ)) /\ •cpII(j(/3), ~' f(rJ)))) a =S* /3 is clearly II§ in the codes, as we can replace y = 71,w by Ly[T2 ] f= KP. It is also easy to check that for all a and /3 in 71,w, 60 3y3f3z E y(y = nw /\ f is a function from y to z /\ f is one-to-one on the domain of a /\ V~,'T/ E y(</1 (a,~,'TJ) /\ •cp~(a,~,'TJ) ~ cp~(f((3),~ , f(rJ)) /\ •cprr(f((3),~, f(rJ)))). Hence, -<* is also II§ in the codes, by the Spector-Gandy theorem. D The following relation will be needed in the next section also . Definition. We define Lim(O") {::::::::} O" E WOuw /\ O" codes a limit ordinal Succ( 7], O') {::::::::} 7] E WOuw /\ O' E WOuw /\ O' codes an ordinal which is the successor of the ordinal coded by 'T/· Lemma 4.18. Both Lim and Succ are~§ in the codes in wo1Lw. Proof. Let Lim~(O') {::::::::} Va E 'IJ,w(a -<* O' ~ 3(3 E v,w(a -<* (3 -<* lT)) , Limrr(O') {::::::::} Va E nw(O' i* a~ 3(3 E v,w(a -<* f3 -<* lT)) . It clear that Lim~ and Limn witness that Lim is ~§ in the codes in WOuw. For Succ(rJ, O"), we can define Succ~('T/, O") {::::::::} Va E 11,w(a -<* O" ~ 7] -/.* a), Succrr(77, O") {::::::::} 3a E v,w(77 -<*a-<* O"). 61 Theses Succ'L: and Succn witness that Succ is 6§ in the codes in WOuw. D By the proceeding lemma, both Lim(O") and Succ(77, O") are 6§ in the codes. The same remark after the proceeding lemma applies to these relations too. Now, let us proceed towards our last lemma in this chapter. We will show how to decompose II§ in the codes sets into the union of K. 3 many * 6§ sets in a uniform and effective way. Lemma 4.19. Let cm,k ~ 1/,w x xm,O ,k and Hm,k ~ 1J.w x xm,O ,k as given in Lemma 4.6, then there are 6§ in the codes f, g: nw x nw ---+ nw such that (1) for any a, c E W011w' cm ,k _ Hm,k .f(a,c:) g(a,c:)' (3) for any c E nw, u cm,k .f(a ,c:) - u Hm,k g(a ,c:) . Proof. Let <.pH be the l:o formula such that for all c E 7/,w and (a, i) E '.Xm,O,k, ~ -:>) E <ym.,O ,k 1 t For any a, c E nw an d ( a, 1, .A. , e 62 A(a,s,a,i) is .6.§ in the codes, because and L11a1i[T2] I= 3xcpH(x, c, a, i) can be expressed by a II1 formula. Let We have that 2,0,m,,k( ) L et f( a, c ) = sL: cA, a, c . Now, for any a, c E Uw and (a, i) E :x:m,O,k, let Similarly, B(a, c, a, i) is II§ in the codes, so, there is a CB E Uw such that _, 7 ) B( a,s,a,1, ~ Hm+2 _, -:>) , ' k( cA,a,s,a,1,. We have that Let g(a, c) = s~O,m,k(cA, a, s). It is easy to see that f and g work. D 63 5. A Technical Lemma In this chapter, we will prove Hjorth's lemma mentioned in Chapter 4. The following proof is suggested by him. Lemma (Hjorth). Assuming A.~ determinacy, for any x E ww and n E w, if A is a IT§(x) in the codes subset of nn, then A E L <dT2, x]. 1 Proof. We will show this by induction on n E w. For each x E ww and n E w, let P(n, x) stand for the proposition corresponding to the x and n, i.e., for any x E ww and n E w, if A is a IT§(x) in the codes subset of n 71., then A E LK, 3 [T2 , x]. Base Case. n = 1. At first, we will show that for any x E ww, ex < 1J. 1 = w 1 and n E w, if A is a IT§(x) in the codes subset of ex, then A E L,.,,'f,[T2 , x]. To make the notations simple, we will drop the parameter x in the proof below, i.e. , we will show that for any ex < n 1 = w 1 and n E w, if A is a IT§ in the codes subset of ex, then A E LK, 3 [T2 ]. The relative version can be proved in a similar way. Subcase 1. ex< w. It is obviously true in this case. Subase 2. ex= w. This case is well-known. A proof about this case can be found from [KMS]. Subcase 3. ex < w1 = n1. 64 P = {p : p is a function from some finite subset of w to ex}. We define a partial order on Pas p::::; q {::::::::} p 2 q. We call it Coll(w, ex). It is clear that Coll(w, a) E lllf . Let G ~ Coll(w, ex) be a M-generic subset of P. Then f c = U{p : p E G} gives an onto map from w to ex. It is easy to see that Let A = fa [A] . Let w be a real coding f c. Then, A is I;§(w). Using and 1 relativizing the argument in Subcase 2, we know that A E M[G] and it is .6 1 definable over M[G] using the parameter G. Let A be the forcing name such that A[G] =A in all M[G]. From the forcing theorem, A = {.T : II- .i; E A}. As the forcing relation is .6 1 , A is a .6 1 definable subset of ex E L"' 3 [T2] using the parameter A E L",3 [T2]. Hence, A E L"' 3 [T2]. Now , it is time to prove P(l , x). We will show P(l, 0) only, the relative case being similar. Let A is a .6§ in the codes subset of u 1 . Since A is 2:; 1 over L".3 [T2], there is a .6 0 formula1/J(.T,y) such that for all {3 <ex, For each {3 E A, let p({J) = the least 'Y such that Ly[T2] f= 3y1/J({3, y). 65 It suffices to show that sup,8EA p(/3) < K, 3 , since if this is true, then This is a ..6. 1 definition, so A E L,,.3 [T2]. Now, we assume that sup,8EA p(/3) = K, 3 , towards a contradiction. For any 5 < w 1 , let w(5) be a real in L,,. 3 [T2 ] which codes 5. As An5 ~ 5 < w 1 and An5 is II§(w(5)) in the codes, An5 E L,,,s(T2 ,w(5)] = L,,, 3 [T2 ] by Subcase 3. As and p[A n 5] is bounded below K,3. Let P8 = sup p[A n 5]. Since SUP,BEA p(/3) = r;,3, then (P8)8Ewi is a non-decreasing sequence of ordinals cofinal in r;, 3. So, cf (r;,3) =cf (wi) = ~1, this contradicts the fact that cf (r;,3) = w. Inductive Step. Assume P(n, x), we will show P(n + 1, x). At first, we will show the following Claim. For all x E ww and a < 1J,n+ 1 , every II§( x) in the codes subset of a is in L,,, 3 [T2]. Proof of the claim. We will show this by contradiction. Assume that there is a x E ww, an a < nn+1 and a II§(x) in the codes A ~ a such that A tj. L,,.3 [T2 ], towards a contradiction. 66 Let a be coded by some y E W0 11,w, i.e., y = (k, ztt) such that _ L[z] ( ) a - Tk n 1 , · · · , 11.z(k) , where (Tn)nEw lists all the Skolem terms taking ordinal values in L[z] and l(k) is the number of variable of Tn· Let (6i)iEw enumerate the first w many L[z] indiscernibles after 11,n in an increasing order. This sequence is definable from 1Ln over L(ztt), hence in L[y]. Let A= {(6,-·· ,~.f,i,p): i,j,p E w,l(i) =j +p Let f: H;;w ---> nn be a 6.1 L-definable from 1L11 bijection, let 7rI: and 7rn be the 'E 1 and Ili formulas which define f over L, i.e., for all g E L, Let (TiJ.iEw be the Skolem terms which define f in the following sense: for The sequence (Ti)iEw is simple enough, say, 6.§(z) in the codes. Let (TmJ .iEw be the Skolem terms which define .f- 1 in the following sense: for any~ E Hn and j < len(.f- 1 (~)), 67 The sequence ('TmJ.iEw is also simple enough, say, .6.j(z) in the codes. Let A= J[A] ~ 1J,n· Since ~ 3i,j,pEw ,6, ··· ,(7 E?J,n(l(i) =j+p A'TiL[z](6,··· ,~.f,81,·· · ,bp) E AA /\ ~l ='T;;:;.\2 l(f3,?J,1,·· · ,11,n)) l~l~.i ~ 3i,j,pEw,~1, ··· ,~.f,'"'{Euw( l(i) =j+pA'"'(EA Let e(x,y) = 3y() 0 (x,y) be a 2: 1 formula which define A over L11:;3[T2 ,x]. Let For f3 E A, let cp(,8) = the least {3 > uw such that Lf3[T2, x] I= ()(,8). For f3 E A, let cp(/3) = the least /3 > nw such that Ls[T2 , x, y] I= R(/3). It is easy to see that for every f3 E A, there is a /3 E A such that cp(/3) 2:: cp(,8). 68 Since A tf_ LK;s[T2, x], <pis unbounded below K,;3, i.e., sup <p({3) = K,3. ,6EA As As:;;; v,n, A is II§(x, y), by the induction hypothesis, sup(/;(~) < K,~,y . .@EA But, sup (/;(~) ~ sup <p(f3), ,6EA ,6EA we have that By Lemma 14.4 in [KMS], Y3 ~~ (x, y), where y3 is an element in the first nontrivial .6..§(x) degree of all II§(x) singletons under the .6..§(x) reduction, and ~~ is the Q-reduction defined in [KMS]. We do not have to care about the exact definition of Q-reductions here, because we have Y3 ~3 (x, y), actually, since Q(x, y) consists of only trivial II§(x, y) singletons and y3 is a II§(x, y) singleton. So far, we have showed the following: for any y coding a, y3 ~3 (x,y). 69 Let where x rvw y iff .T and y code the same ordinal smaller than uw. B is II§(x). We have showed that B is not empty. By the Kechris-Martin theorem, there is a .6.§(x) real y* E B. As Y3 E .6.§(x, y*), y3 E .6.§(x), which is a contradiction. D(Claim) Now, let us prove P(n + 1, x). We will actually prove P(n + 1, 0) below, the relative case can be proved in a similar way. Let A is a .6.§ in the codes subset of un+l · Since A is L:: 1 over Li;; 3 [T2 ], there is a .6. 0 formula 1/J(x, y) such that for all f3 <a, For each f3 E A, let p(f3) = the least I such that L,[T2] f= 3y1j;(f3, y). It suffices to show that sup,8EA p(f3) < K, 3 , since if this is true, then and this is a .6. 1 definition, so A E Li;; 3 [T2]. Now, we assume that sup.BEA p(f3) = K,3 towards a contradiction. 70 For any 8 < 11,n+i, Let w(8) be a real in LK, 3 [T2] which codes 8. As An 8 ~ 8 < un+l and An 8 is II§(w(8)) in the codes, An 8 E LK,s[T2,w(8)] = LK,s[T2] by Subcase 2. As and LK.3 [T2] I= 6. 1 collection axiom, p[A n 8] is bounded below K3. Let P8 = sup p[A n 8]. Since sup.BEA p({3) = K3, then (P8)8Eu,.+i is a non-decreasing sequence of ordinals cofinal in K3. cf(r;, 3 ) = cf(1Ln+i) =/:- w, this contradicts the fact that cf(r;,3) = w. Inductive Step) D(Lemma) So, D(The 71 6. Representation of Thin II~ Equivalence Relations We have standard thin IIi equivalence relations on reals, namely, any equivalence relations .6.i reducible to IIi equivalence relations on w. Harrington showed that these are all the thin IIi equivalence relations on reals actually. Theorem (Harrington) 6.1. For any thin IIi equivalence relation on ww, there is a .6.i function p from ww tow and an equivalence relation e on w such that for any x, y in ww, xEy ¢::::::} Proof (Harrington) . See to [Hal]. (p(x),p(y)) Ee. D Harrington's idea is as follows: Let Ebe a thin equivalence relation on ww, let {Xi}iEw be a .6.i enumeration of .6.i subsets of ww such that (1) \:Ix E ww:3i E w(x E Xi), (2) Vi E w\:/x E ww\:/y E ww(x E X1. /\ y E Xi~ (x, y) EE). He defined p : ww ~ w as p( x) = i ¢::::::} i is the least natural number such that x E Xi. It is natural to think to define an equivalence relation e on w by letting (i, j) E e if and only if all real numbers in p- 1 (i) U p- 1 (j) are E equivalent. But, this does not work, since if there is some i such that p- 1 (i) = 0, e defined as before 72 will become w x w. Harrington built this e step-by-step using induction all the way to wf K. At each step, he put only at most one carefully selected pair and all pairs induced by this pair into e. More precisely, he built a sequence of .6.i equivalence relations {eO'}O'<wcK. Let e be the union of these e(J'. He started from e 0 = id( w x w). For O' a limit ordinal, he simply took a union to define eO'. For O' a successor of a non-limit ordinal, he put nothing new into eO'. For O' a successor of a limit ordinal >., he put the first pair (i, j) rf_ e such that for unbounded many rJ < >., the IIi assertion "all reals in Y:,77 U ~i77 are E-equivalent" can be seen to be true in less than >. steps, where Yi = { x : (p( x), i) E e}. Many similarities between IIi and II§ were found by Kechris, Martin, Moschovakis, Solovay and others (see [Ke5] for a summary). For example, we have the prewell-ordering property, scale property, the Martin-Solovay representation theorem, the Spector-Gandy theorem for the third level, which are counterparts of the corresponding results for the first level. It seems that the following is a good analog: where T2 is the Martin-Solovay tree and To the recursive tree on w whose branches produce the complete II~ set of ww. However, there are many differences between them, for example, the natural generalization of the basis theorem fails in the context of~§, L[T2 ] -<2::14 V fails while (L[To] = )L -<2::12 V holds. These similarities and differences make it pretty interesting to consider 73 what will be the counterpart of the Harrington representation theorem in the third level. To work in the third level of the analytical hierarchy, we need some determinacy. From now on, we will always assume ~~ determinacy. We can show the following theorem later in this thesis. Theorem. For any thin IT§ equivalence relation on ww, there is a ti.§ in the codes function p from ww to 11.w and a II§ in the codes equivalence relation e on 11.w such that for any x, y in ww, xEy ¢::::::} (p(x))e(p(y)). Hjorth lifted Harrington's proof of the Silver perfect set theorem to the third level in [Hj 1]. He had Lemma (Folklore) 6.2. Let E be a thin IT§ equivalence relation on ww. Then for any :r; E ww, there are n E w, a E Hw, D ~ ww, a :E§ M ~ ww x ww and a II§ N ~ ww x ww with (1) 3y E ww(T!,[Y](1J.1, . . . ,v·k(n)) =a), (2) \:/y E ww(Trf'l11 l(11.1, ... ,11.k(n)) =a----+ D = M 11 =Ny), (3) x ED, (4) D ~ [x]E· From this lemma, it is easy to show Lemma 6.3. If E is a thin IT§ in the codes equivalence relation, then there 74 is a sequence {Xa}o«uw such that (1) Xa ~ some E-equivalence class, (2) the relation "x E Xa" is .6.§ in the codes, (3) for all reals x, there is a a in v,w such that x E Xa. Proof. Let E be a thin II§ equivalence relation. From the above lemma, for any x E ww, there is a E nw and C ~ ww such that (1) x E C ~ [x]E, (2) c is uniformly .6.§(a), i.e., there are I:§ c~ ~ WW x w and II§ err c ww x ww such that Let fix D ~ 11,w, W, wrr, w~ ~ Hw x 1Lw as in Lemma 4.15. Then, for any x E ww, there is an a ED such that x E Wa ~ [x]E· Now, let A= {(x,a): a ED and x E Wa ~ [x]E}. A is II§ in the codes. Let the II§ in the codes set Ao uniformize A. As Ao is the graph of some function, Ao is actually .6.§ in the codes. Let B = {a E 1Lw : 3x E ww ( ( x, a) E Ao)}. B is I:§ in the codes and B ~ D. Let Bo be a .6.§ in the codes set separating B from 11w \ D, i.e., B ~Bo ~ D. By effective induction, there is a .6.§ in the 75 codes function f : 1Lw ___... 1Lw enumerating Bo. Let Xa = Wf(a). It is easy to check that {Xa}a <nw works. D There are two major difficulties in lifting Harrington's result. In Harrington's proof, he can code the whole process of induction by a real number since only recursive ordinals are needed in his proof. He can guarantee that e(J' is .0..i by showing that it is both :Ei and IJi using a real coding the induction process. It is a method for showing .0..i from the top. We have to prove that our construction is .0..§ from the bottom up since we are doing induction all the way to K. 3 which is a much larger ordinal compared with wf K, and we cannot code our process by a real number. That is why we have to develop the effective theory of :E§, II§ and .0..§ in Chapter 4. We can show that our process is .0..§ by two effective inductions. The other difficulty comes from a very good property of w. It is a small cardinal but has many combinatorial properties of large cardinals. Harrington used the obvious fact that all finite sets of recursive ordinals have upper bounds. He needed the upper bound to freeze the construction at some step for all smaller natural numbers, to guarantee that every pair of natural numbers can get attention at some step of his construction. To lift Harrington's result, we have to consider an infinite set of ordinals. The existence of the upper bound is not trivial this time. However , Hjorth's lemma helps us out. For any x E ww, let p(x) be the least a< 1Lw such that x E Xa. The graph of this p is .0..§ in the codes. 76 We will build our equivalence relation e on Hw by induction along ordinals up to K, 3 , where K,3 = the least ordinal K, > 1Lw such that L,,,, [T2] I= KP = sup{>. : >. is the length of a ~1 (a) well-ordering of subsets of Hw for some a E Hw}. Let us give an informal description of our construction before we go into the tedious details . We will build a sequence {e(]" }(J"<,,,, 3 of * ~§ in the codes equivalence relations on Hw. For each a E ?Lw, we let We will guarantee that all reals in Y; are E-equivalent and from our construction. (1) Let e 0 be the equality relation on 1Lw. (2) For O' a limit ordinal, let e(J" = LJ(J", <(J" eO"' · (3) For O' a non-limit ordinal, let eO"+l = e(]". (4) For O' a limit ordinal, let us define eO"+l as follows: See if there are ordinals a and j3 smaller than Hw such that (a, /3) ~ e(]" and for unboundedly many 'TJ < O' the II§ assertion: (*) all reals in Y; U Yd are E-equivalent 77 can be seen to be true in < (]' steps. In our formal construction, we will work carefully to guarantee that Y: is .6.1 (a,(]') in the codes so that the assertion (*) above is really II1 in the codes. If there are no such pair of ordinals, let eO"+l = e(T. Otherwise, let (a, {3) be the first such pair of ordinals under the natural well-ordering of 1J.w x 7Lw, and let eO"+l be the smallest equivalence relation on 71,w such that eO"+l 2 e(T and (a, {3) E eO"+l · Then let e = UO"<K,3 e(T. Now, let us go to the formal details to guarantee e is II1 in' the codes. Basically, we need two effective inductions to guarantee that Y: is .6.1 (a,(]') in the codes, one for II§( a,(]') and another for II§( a,(]'). Let H ~ 1J,w x 1J,w x 71,w x 71,w be a good universal II1 in the codes set for the *II§ subsets of Hw x 1J.w x 1J,w' G ~ 1J.w x 7Lw x Hw x Uw x Hw a universal :E§ in the codes set for the * :E1 in the codes subsets of 1J.w x nw x 71,w x 71,w, i.e., H = H 3 ,o and G = G 4 , 0 . These G and Hare trying to witness that Y: is .6.§(a, (]')in the codes. Let Vx, y((G(d, m,p(.r,), (]',a) V G(d, m,p(x), (]', {3)) P(d, m, a,(]', {3) ¢::::::;> /\(G(d, m,p(y), (]',a) V G(d, m,p(y), (]', {3)) ---+ xEy). After we "diagonalize" d and m, i.e., let d = d* and m = m*, where d* and m* are the fixed points to be determined by the recursion theorem later in this 78 chapter, P(d, m, a, <7, (3) will mean that for all .r, y in Yi UY$, (x, y) E E, where Y: = {x: (p(x), a) E eu} and eu is the equivalence relation constructed up to the <7-step. This P(d, m , a, <7, (3) is clearly II§ in the codes. So, there is a l E w such that P(d, m, a, <7, (3) -<==> H 3 , 2 (l, <7, a, (3, d, m). Hence, there is some .6.§ in the codes function s~ 1 ' 2 ' 0 : w x ww x ww x w x w _, nw such that for all <7, a , (3, d and m, The superscripts are pretty annoying, so we introduce some new notation to simplify them. Let U(E,a) -<==> G 1'0(E,a) , V(E, a) -<==> H 1'0(E, a), h(l, d, m, a , (3) = s;' 1 ' 2 ' 0 (z, a, (3, d, m). So, P(d, m, a, <7, (3) -<==> V(h(l, d, m, a, (3), <7). Let gu and fv be given by the last lemma in Chapter 3. Let 79 After the diagonalization, Rr, is a ~§ formula claiming that a is not equivalent to f3 up to the o--th stage of our construction, before which there are unboundedly many stages at which the P can be witnessed to be true. Let Lim( a-) /\ •G( d, m, a, a-, /3) /\ Vo-o E 1Lw (a- ~* o-o Rn (d, m, a, a-, /3) {::::=} /\ V(Jv(o-2,h(l,d,m,a,/3)),0-1)). Rn expresses the same fact as R"E. after the diagonalization, i.e., for any a, f3 E Hw and O" E WOnw) where d* and m* are the fixed points to be determined by the recursion theorem later in this chapter. However, Rn is a II§ formula now. Let B ~ w x w x Hw x Hw x 1Lw be defined as the follows: for any d, m, a, a-, f3 in Hw, (d, m, a, a-, /3) EB if and only if EITHER a = f3, OR a- E LOnw /\ Lim(o-) /\ 377(0- ~ 77 /\ G(d, m, a, a-, /3)), OR a- E LOnw /\ 377( •Lim( 77) /\ 77 E L01Lw /\ Succ( 77, a-) /\ G( d, m, a, 17,{3)), OR a E L0 11 w /\ 377(Lim(77) /\ Succ(77, o-) /\ 3n E w3s E nw <n(/\a = s(O) /\ f3 = s(n - 1) 80 '\/k < n- l(G(d,m,s(k),rJ,s(k + 1)) V R(d, m, s(k), rJ, s(k + 1)))), where Ry:, (d, m, a, (j' {3)/\ R(d,m,a,(j,/3) ~ { Va' /3' ((a', /3') -<uw xuw (a, /3)) ---7 •RIT (d, m, a, (j' /3)). From our construction above, B is I:§. Let d* be the fixed point from the recursion theorem, i.e., for all m,a,(j,/3 in 1Lw, (d*,m,a,(j,/3) EB ~ G(d*,m,l,a,(j,/3). Let us fix this d* from here on. Let '\Ix, y((G(d*, m,p(x), (j' a) V G(d*, m,p(x), (j' /3)) Q(m, a, (j' /3) ~ /\(G(d*, m, l,p(y), (j' a) V G(d*, m, l,p(y), (j' /3)) ---t xEy). Let N ~ 1Lw x v,w a good universal II§ set for all *II§ subsets of v,w and M ~ 1Lw x v,w a good universal I:§ set for all *I:§ subsets of 1Lw. Let f N ,g M be the function given in the last lemma of Chapter 4. By the s-m-n theorem, there must be a ~§ in the codes h: w 2 x v,w 2 such that for all m, a, (j' /3, Q(m,a,(j,/3) ~ N(h,(l',m,a,/3),(j), where l' is a natural number which is the index of Q. 81 Let SL, has similar meaning as RL., the only difference is that at this stage, we have a fixed d*. Let Lim(O") /\-iG(d*,m,a,0",/3) /\ 'i/O"o E ?J,w(O" i* O"o S11 expresses the same fact as SL. but in a II§ form. Let A ~ ?J,w x ?J,w x ?J,w x ?J,w be defined as the following: for any m, o:, O", j3 in ?J,w, (m , o:, O", /3) E A if and only if EITHER o: = j3, OR (}' E LOuw /\ Lim((}') /\ 377( 77 -<* (}' /\ H (m, o:, O", /3)), OR (}' E L0 1J,w /\ 377(-,Lim( 77) /\ 77 E LOv.w /\ Succ( 77, (}') /\ H (m, o:, O", /3)), OR (}' E LOuw /\ 377(Lim(77) /\ Succ(77, (}') /\ 3n E w3s E ?1.w <n(/\a = s(O) /\ j3 = s(n - 1) Vk < n - l(H(m, s(k), 77, s(k + 1)) V S(m, s(k), 77, s(k + 1)))), 82 where srr (m, a, a-, {3)/\ S(m, a, a-, {3) {:::=:} { Va'f3'((a',f3') -<1LwX71.w (a,{3)) ---t •Sr:,(m,a,a-,{3)). It is easy to see that B is II§. Let m* be the fixed point from the recursion theorem, i.e., for all a,a-,{3 in uw, (m*,a,a-,{3) EB {:::=:} H(m*,a,a-,{3). Let us fix this m* from here. For any a,{3 in Uw, let this e is clearly a II§ in the codes equivalence relation on 7Lw. By the induction on Ila-II, we have the following Lemma 6.4. For any a, f3 and a- in WOuw, G(d*,m*,a,a-,{3) {:::=:} H(m*,a,a-,{3). This lemma guarantees that thee defined before this lemma is just the equivalence relation that we described informally at the beginning of this chapter. Now, it is time to prove that for all x and y in ww, (x, y) EE {:::=:} (p(x),p(y)) Ee. For any a E Uw, let Ya= {x: (p(x),a) Ee}. It suffices to prove the following 83 Lemma 6.5. For each a and (3 in ww, if all reals in Ya are E-equivalent to the reals in Y.6, then (a, (3) Ee. Proof. For this a and (3, let S = {(a',(3'): (a',(3') -<uwxv.w (a,(3)}. This is a TI§ subset of a, so, A E LK 3 [T2] by Hjorth's lemma in Chapter 3. As and there is a B E LK 3 [T2] such that Let O"o = sup{ O" : O" E B}, O"o < r;,3 since B E LK 3 [T2]. For this O"o, Va 1(3 1 ((a 1 ,(31 ) -<uwxv.w (a,(3) /\ (a',(3') Ee---+ (a',(3') E e0). Let us define an increasing sequence of ordinals smaller than r;, 3 by letting O"n+l = max(gv(O"n, h(l, d*, a, (3)), fu(O"n, h(l, d*, a, (3)), 9N(O"n, h,(l', m*, a, (3)), fM(O"n, h,(l', m*, a, (3))). Since this sequence is .6.§ (a, (3) in the codes, its upper bound is also an ordinal .6.Ha, (3) in the codes and hence smaller than r;, 3 . Let ~=sup O"n. nEw 84 If (a,{3) E ef., then (a,{3) Ee, we are done. So, we suppose that (a,{3) ~ ef.. In this case, from our construction, and because all reals in Yci< are E-equivalent to the reals in Y,a, (a,{3) E eE.+ 1 . Hence, (a,{3) E e. D Finally, we have our main theorem. Theorem 6.6. For any thin II§ equivalence relation on ww, there is a ~§ in the codes fun ction p from ww to uw and a II§ in the codes equivalence relation e on Uw such that for any x, y in ww, .r,Ey ~ (p(x),p(y)) E e. Proof. Let E be a II§ thin equivalence relation on 11.w, p and e as defined in this chapter. From our construction, we know that Ya must be a subset of some E equivalence class. We also know that Ya is E-invariant from Lemma 6.5. So, Ya is either an equivalence class or the empty set. But, it cannot b e the empty set, otherwise, (a, {3) E e for all f3 E 11.w from Lemma 6.5. So, for all f3 E nw, Ya = Y,a . Hence, Y,a = 0 for all f3 E uw. This is impossible. So, we have (x, y) EE ~ (p(x),p(y)) E e. D It seems t h at J ackson lifted the Kechris-Martin theorem to higher levels. We hope his result could be used to lift Harrington 's representation theorem 85 further. 86 References [BKl] H.S. Becker & A.S. Kechris, Sets of ordinals constructible from trees and the third victoria delfino problem, Contemporary Mathematics 31 (1984), 13-29. [BK2] H. Becker & A.S. Kechris, The descriptive set theory of Polish group actions, Cambridge University Press, New York, 1996. [Hal] L.Harrington, A Powerless proof of a theorem by Silver, Circulated notes (1976). [Hjl] G. Hjorth, Variations of the Martin-Solovay tree, Journal of Symbolic Logic 61(1) (1996), 40-51. [Hj2] G. Hjorth, 8j and the reals of L[T2], Handwritten note (1994). [Jel] T.Jech, Set theory, Academic Press, New York San Francisco London, 1978. [Lil] X.Li, On the non-e.r:istence of the largest E-thin, E-invariant IIi set for some IIi Equivalence Relation E, handwritten note (1995). [Li2] X.Li, On the non-existence of the largest E-thin, E-invariant II~n+l set for some II~n+l equivalence relation E, Submitted to the Journal of Symbolic Logic (1996). [Li3] X.Li, On the representation of the thin II§ equivalence relations on ww, preprint (1996) . [Kal] A. Kanamori, The higher infinity, Springer-Verlag Publishing Company, Berlin Heidelberg New York, 1994. [Kel] A.S. Kechris, Thin sets for IIi equivalence relations and the perfect set theorem for i1.w, Circulated note ( 1979). [Ke2] A.S. Kechris, Countable ordinals and the analytical hierarchy, II, Annals of Mathematical Logic 15 (1978), 193-223. [Ke3] A.S. Kechris, Countable ordinals and the analytical hierarchy, I, Pacific Journal of Mathematics 60(1) (1975), 223- 227. [Ke4] A.S. Kechris, The theory of countable analytical sets, Transactions of Amer. Math. Soc. 202 (1975), 259- 297. [Ke5] A.S. Kechris, Recent advances in the theory of higher level projective sets, The Kleene Symposium (1980), North-Holland Publishing Company, Amsterdam New York Oxford, 149-166. [Ke6] A.S. Kechris, Classical descriptive set theory, Springer-Verlag, Amsterdam New York Oxford, 1994. [KMl] A.S. Kechris & D. A. Martin, On the theory of II§ sets of reals, Circulated notes (1977). [KMS] A.S.Kechris, D. A. Martin, R. M. Solovay, Introduction to Q-theory, Cabal Seminar 79-81, Lecture Notes in Mathematics 1019 (1983), SpringerVerlag, Amsterdam New York Oxford, 199- 282. [Mol] Y.N.Moschovakis, Descriptive set theory, North-Holland Publishing Company, Amsterdam New York Oxford, 1980. 87 (Sal] G. Sacks, Higher recursion theory, Springer-Verlag Publishing Company, Berlin Heidelberg New York, 1990. 88 Vita Xuhua Li M.Sc. in Applied Mathematics, Tsinghua University, 1988 B.Sc. in Mathematics, Beijing University, 1986 89 SOME RESULTS ON PROJECTIVE EQUIVALENCE RELATIONS Xuhua Li , Ph.D . Department of Mathematics California Institute of Technology, 1997 Dr. A. Kechris and Dr. G. Hjorth, Advisors We construct a IIi equivalence relation E on ww for which there is no largest E-thin, E-invariant IJi subset of ww. Then we lift our result to t he general case. Namely, we show that there is a II~n+l equivalence relation for which there is no largest E-thin, E-invariant II~n+l set under projective determinacy. This answers an open problem raised in Kechris [Ke2]. Our second result in this thesis is a representation for thin II§ equivalence relations on V.w. Precisely, we show that for each t hin II§ equivalence relation E on 1Lw, there is a ~§ in the codes map p: ww ---+ 11.w and a II§ in t he codes equivalence relation e on 1Lw such that for all real numbers x and y, .r, E y {:::::::} (p(x),p( y)) Ee. This lifts Harrington's result about t hin IIi equivalence relations to thin II§ equivalence relations.