Independence Results for Indescribable Cardinals Citation Hauser, Kai (1989) Independence Results for Indescribable Cardinals. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/40tv-qe43. https://resolver.caltech.edu/CaltechETD:etd-05222007-093217 Abstract No abstract submitted. 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): Woodin, W. Hugh Thesis Committee: Woodin, W. Hugh (chair) Luxemburg, W. A. J. Kechris, Alexander S. Laver, Richard Defense Date: 20 April 1989 Funders: Funding Agency Grant Number NSF DMS 87-18847 State of Baden Württemberg UNSPECIFIED Record Number: CaltechETD:etd-05222007-093217 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-05222007-093217 DOI: 10.7907/40tv-qe43 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 1949 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 24 May 2007 Last Modified: 06 Aug 2021 00:26 Thesis Files PDF - Final Version See Usage Policy. 3MB Repository Staff Only: item control page

INDEPENDENCE RESULTS FOR INDESCRIBABLE CARDINALS Thesis by Kai Hauser In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1989 (Submitted April 20, 1989) -11- © 1989 Kai Hauser All Rights Reserved -111- Acknowledgements Any reasonable complete listing of all the people who have had a direct impact on the writing of this thesis has to begin with my high-school math teacher, Gymnasialprofessor Bertram Koser whom I would like to thank for introducing me to what he used to refer to as "axiomatic thinking." During my time as a Caltech graduate student I enjoyed the hospitality of l\fr. Dan Lewis (head wrestling coach at Cal State Fullerton). I really appreciate the way in which he provided a welcome balance to the purely academic life-style at Caltech. I am deeply indebted to Professor Alexander S. Kechris for faciliating my stay• at Caltech and removing all bureaucratic obstacles. Moreover, I am grateful for the many conversations during which he shared with me some of his deep insight into descriptive set theory. If it is true that one of the major hurdles that a beginning graduate student has to overcome is finding a nontrivial thesis topic that can be solved in a reasonable amount of time, then certainly I cannot overemphasize how much I owe to Professor Gert H. Muller for suggesting the central problem of the thesis and for putting me on the right track towards solving it. In addition I am thankful for his continued interest in my mathematical education as well as my personal well-being ever since I was his student at Heidelberg University. The final remarks are reserved for my thesis advisor, Professor W. Hugh Woodin. Having received uncountable dazzling demonstrations of the many wonders of contemporary set theory I consider to be the most significant privilege of my entire mathematical career. There has never been a dull moment. Perhaps this is a good occasion to wish Hugh good luck for his return to the lava lake! The author is a fellow of the German Academic Exchange Service (DAAD). Research has been partially supported by grants from the State of Baden Wiirttemberg, and the National Science Foundation of the USA (grant DMS 87-18847). -IV- Notation Our set theoretical notation is quite standard: The letters a, (3, 1 , ... denote ordinals, while x:, .\, µ are reserved for inaccessible cardinals unless it is explicitly mentioned that they are not. We let [a,(3] = {(:a ~ ( ~ /3} and (a,/3) = {(:a < ( < /3} and similarly for half-open intervals. The notation f: A -> B expresses that f is a function with domain A and range contained in B. f(S] (f- 1 (S] resp.) denotes the pointwise image of S (preimage of S resp.). As usual L'g1 (.llg1 resp.) is the collection of all formulas in the E language of set theory with higher type variables and a unary predicate symbol whose prenex form has n alternating blocks of type m quantifiers starting with 3 (V resp.). A formula is ~g1 if it is equivalent with both a L'g1 and a .llg1 formula and L'o (or n 0 )if all quantifiers are of type <m. If we write down a formula <I> (X 1 , .. ,,Xn) then this is to mean that all free variables that occur in <I> are among x 1 , ... , Xn. Va (the a-th level of the von Neumann hierarchy) is often understood as the structure (Va ,E) (frequently with a finite sequence of possibly k-ary relations on Va added on); however, we will simply write Va F <I> (A) instead of (Va ,E,A) F <I> for example. Unless remarked otherwise we will be working in ZFC. ZF- ( depending on the context) and will always denote some suitable finite fragment of ZFC. Recall that we have a flat pairing function (i.e., one that does not raise the von Neumann rank) such that the coding and decoding is absolute for transitive models of a very weak fragment of ZF. Recall also that for each m > 1 and n ~ 1 there is a formula X L'g1 (x,$) in L'fil -v- such that for any limit ordinal a, V Cl:' F ~ (ffi) iff V Cl:' F X EW ('~',ffi) for all g; E V 11:+m and ~ (ffi) in EW where •~• denotes a code of ~ m V w. necessary details can be found m [Drake, 1974]. M ..,11b IV 11:+m-21 C M ..,11b .At, 1s All the Eg1 correct for ,- inside N iff in u· . J,, i.e., .At, is closed under sequences of length IV 11:+m- 2 1 m N where this means sequences of length <11: in case m 1. We call .At, EW (n ~ 1) correct for K (in parameters from V 11:+m) inside N if in addition to this .At, correctly computes the EW facts that hold in jf in parameters from V 11:+m n .At,. Given a model M of ZF- we will use the notation (M)a to denote M's version of Va for a E M. (M)a F ~- However we will also use the notation M F "Va F ~" rather than Regarding our forcing formalism we take V as a relative term for the ground model and construct generic extensions V[G] where partially ordered sets (posets) will be given preference over Boolean algebras. We contend that every element of V[G] has a name in V and let vP denote the class of all P names in V relative to a poset PE V. 0 In general, T, u will denote names but we will also use the notation A for a name for A E V[G]. In particular, if Q is a poset E V[G] and r E V[G] a Q name then we denote by i E vP a name for r. As usual x is the canonical name for x that happens to be in the ground model. Very often (for instance if xis an ordinal) the x notation will -VI- be supressed. By a mce name for a subset of (J' E yP we mean essentially a function that associates with each r E dom((J') an antichain of P. Frequently the symbol r will occur as a canonical name for the generic (for a given poset P). Thus we have for instance plf- p E r for all p E P. Fn(I,2,x:) will always denote a <x: support product of copies of the usual poset for adding a subset of x: where the copies are indexed by the ordinals E I. We say that a poset P is <x: closed if for any decreasing sequence of length <x: of conditions there is some condition extending all the conditions in the sequence. As a variant of this we will say that P is < x: directed closed if for any directed X ~ P (i.e., 'v'p,q E X 3r E X r :=; p,q) of size <x: there is some p E P with p :=; q for all q E X. P is said to be x: c.c. if every antichain has size <x:. P has the property x: if every subset of P of size x: has a subset of size x: that consists of pairwise compatible conditions. Finally P is x: centered if there is an equivalence relation on P with x: equivalence classes such that any two equivalent conditions are compatible. All the forcing terminology being used in this thesis and not being explained here can be found in [Baumgartner, 1983] and [Kunen, 1980]. -Vll- Introduction and Statement of Results Indescribability is closely related to the reflection principles of Zermelo Frankel set theory. In this axiomatic setting the universe of all sets stratifies into a natural cumulative hierarchy (Va: a E On) such that any formula of the language for set theory that holds in the universe already holds in the restricted universe of all sets obtained by some stage. The axioms of ZF prove the existence of many ordinals a such that this reflection scheme holds in the world Va if one considers only first-order parameters over Va. Hanf and Scott [1961] noticed that one arrives at a large cardinal notion if one allows second order parameters, i.e., predicates over Va. For a given collection O of formulas in the E language of set theory with higher type variables and a unary predicate they define an ordinal a to be O indescribable if for all formulas <I> in O and (Va , E ,A) F <I> ⇒ 3 (J < a (V f3 , E ,A n V fJ) F <I> • Since a sufficient coding apparatus is available this definition is (for the classes of formulas that we are going to consider) equivalent to the one that one obtains by allowing finite sequences of relations over Va some of which are possibly k-ary. We will be interested mainly in certain standardized classes of formulas. Let Eg1 (llg1 resp.) denote_ the class of all formulas in the language introduced above whose prenex form has n alternating blocks of quantifiers of type m starting with 3 ( V resp.). In [Hanf-Scott, 1961] it is shown that in ZFC, ll5 indescribability is equivalent to inaccessibility and lli indescribability coincides with weak compactness. Thus the existence of Eg1 (or llg1) indescribable cardinals is unprovable in ZFC. However [Vaught, 1963] has shown that below any measurable cardinal there -Vlll- are many totally indescribable cardinals ( where totally indescribable means Eg1 indescribable for all m, n). Moreover, it follows from the results in [Jensen, 1967] that already below 11:(w) (i.e., the last cardinal with 11: -+ (w);w), there are stationary many totally indescribable cardinals. Therefore, indescribable cardinals are rather tame inhabitants of the large cardinal zoo; in fact Eg1 and llg1 indescribability relativizes down to L. Since the ll5 indescribability of 11: is a lli property over V,,,, there are many ll5 indescribables below the least lli indescribable. Can this result be generalized to arbitrary m and n? By computing the complexity of a truth definition for llg1 and Eg1 formulas [Levy, 1971] was able to prove that in ZFC O' 1 1 n+l < 7r n+l and for m ~ 2 and n ~ 0, where 1rg1 (o-g1 resp.) is the least llg1 (Eg1 resp.) indescribable cardinal (if they exist). In fact he showed that the gaps are very large. Moreover he proved that for m ~ 2 and n ~ 1. The prominent question at this point is what can be said in ZFC about the relative size of o-g1 and 1rg1 for m ~ 2 and n ~ 1. [Moschovakis, 1976] provided an answer under the assumption that all sets are constructible; i.e., V showed that in L, o-g1 < 1rg1 = L. He -lX- The main results of this thesis are: Theorem III.LL (m ~ 2, n ~ 1) CON(ZFC + 3,c,,c 1(,c < ,c', 1,, is Jig-1 indescribable, and ,c 1 is Eg-1 indescribable)) ⇒ CON(ZFC + ug-1 > 1rg1 + GCH). Note that in ZFC + ug-1 □ > ,rg-1 one can prove that L m F (3 Eg-1 indescribable /\ Un 3 Jig1 indescribable); thus by Godel's second incompleteness theorem we cannot hope for a proof of CON(ZFC + 3 Eg-1 indescribable + 3 JI}P indescribable) ⇒ CON(ZFC + u}P > ,r}P) that is formalizable within ZFC unless ZFC + u}P > ,r}P is inconsistent. Therefore Ill.LL is stated optimally. There is also an Easton type result that says in effect that we have the ultimate freedom in arranging the relative sizes of u}P and ,r}P (simultaneously for m ~ 2 and n ~ 1) as far as the axioms of ZFC are concerned. Theorem III. 7.LAssuming the existence of E}P indescribables for all m ~ 2, n ~ 1 and given a function ~:{(m,n):m ~ 2, n ~ 1}-+ {0,1} there is a poset P ~ E L[~] such that GCH holds in (L[~]) GJ ~ and u}P < 1r}P if ~(m,n) = 0 { u}P > 1rg1 if ~(m,n) = 1. □ The proof of Ill.LL is based on two important techniques for obtaining consistency result for large cardinals: The first technique is known as iterated forcing and originates in the [Solovay-Tennenbaum, 1971] consistency proof of Martin's axiom. Its -x- underlying idea is that one defines the set of forcing condition by proceeding in stages and in our case at each stage we will kill off a potential candidate for a EW indescribable cardinal until we have taken care of all ordinals below a given llW indescribable cardinal. The hard part in the proof of III.LL will be to guarantee that the forcing which we define preserves the started out with. llW indescribability of the cardinal that we For this we will use master condition arguments. This way of reasoning was first employed by [Silver, 1971] and typically occurs in the following setting: We are given an elementary embedding j: M --+ N where M and N are modeling a large enough fragment of ZF together with posets P E M and Q = j(P) E N, and we want to find an M generic G and an N generic H such that j lifts to an embedding (that will again be called j) from M[G] into N[H]. A necessary and sufficient condition for this to work is to pick G and H with the property that (*) Vp E G j(p) E H. If we are given a generic G for P, then a master condition for Q relative to G will be a condition q E Q such that for any N generic H C Q with q E H, ( *) holds for G and H. In order to make the proof of III.LL amenable to master condition arguments we must first find a reformulation of ll-indescribability in terms of elementary embeddings. Theorem LL (m ~ 1, n ~ 1) "' is llW indescribable iff VM [M transitive, MF ZF-, IMI = "',"'EM, M<"' ~ M . ⇒. 3j, N [N transitive, INI j : M --+ N, cpt j = IV"'+m-ll, N E~-l correct for"', = "']]. □ m IV"'+m-21 ~ N (N <"' ~ N form where N is En-l correct for "' means N correctly computes the E~-l facts that hold in parameters from N = 1) and N n V "'+m. -xi- It is an interesting observation that this reformulation suggests that for m ~ 1, IJ 1 indescribability can be construed as an analogue of the concept of hypermeasurability in [Mitchell, 1979] and we will also rephrase it in the context of extenders ( cf. [MartinSteel, 1988]). As a warm up routine for the proof of III.1.1. we are going to apply this reformulation to evaluate the consistency strength of the failure of GCH at a JI indescribable cardinal. Theorem II.1. (n ~ 1) CON (ZFC + 3 JI{i indescribable cardinal) ¢=> CON (ZFC + 3 IC (1C is JI{i indescribable/\ 21C > 1C+)) D This theorem generalizes a result of Silver ( cf. [Kunen, 1980]) about the consistency strength of the failure of GCH at a weakly compact cardinal. In the case of Jig1 (m ~ 2, n ~ 1) indescribability we obtain a result that is reminiscent of the failure of GCH at a measurable cardinal. Theorem 11.2. (e ~ 1, m ~ 2, n ~ 1) CON (ZFC + 3 Jig1+e-l indescribable cardinal) ¢=> CON (ZFC + 3 IC (1C is Jig1 indescribable /\ 21C = IC +e)) D -xii- Table of Contents Acknowledgements ......................................................................................................... iii Notation ....................................................................................................................... iv Introduction And Statement of Results ...................................................................... vu CHAPTER I. A Reformulation of II Indescribability in Terms of Elementary Embeddings ...................................................................... 1 CHAPTER II. The Consistency Strength of the Failure of GCH at a II Indescribable Cardinal ..................................................................... 9 CHAPTER III. The Consistency of e1g1 > 1rg1(m2::2, n2::1) ......................................... 29 Section 1. Section 2. Section 3. General Remarks about the Construction ......................................... 29 (Ti/ 1rr ··············· .................... ······································· ...................... 40 e11 /1r1 m 2:: 3 ...................................................................................... 50 Section 4. e15/1r5 (The Generic Case) ................................................................. 52 Section 5. e1~/1r~ (n2::2) ................................................................................... 114 Section 6. e1g1 /1rg1 (m2::3, n2::2) ........................................................................ 144 Section 7. Oracles - The Final Word on Indescribability .................................. 148 Bibliography ............................................................................................................. 157 -1Ich bin dabei mit Seel' und Leib; Doch freilich wii rde mir behagen Ein wenig Freiheit und Zeitvertreib An schonen Sommerfeiertagen. J.W.v. Goethe Faust, part one of the tragedy, Studierzimmer CHAPTER 1- A REFORMULATION OF II INDESCRIBABILITY IN TERMS OF ELEMENTARY EMBEDDINGS We will introduce a reformulation of IJ-indescribability which will enable us to show that various notions of forcing used in Chapter II and Chapter III preserve certain .II-indescribable cardinals. Before we do this it is necessary to review a few elementary facts regarding the logical complexity of some frequently used set theoretical statements. Suppose we code a transitive set M of cardinality IV K+m-ll (where m ~ 1) by a binary relation ~ on For any g; E V K+m the statement "9; E M" is E~(9;,~) over VII': since it 1s equivalent to 3 GJ 3 X GJ collapses X to g; where GJ ranges over VII':+ m and X ranges over VII':+ m _ 1 and "GJ collapses X to g;" rs short for GJ is a function A dom GJ 2 {Y: ygx} A VY E dom GJ VZ~Y Z E dom GJ A VY E dom GJ GJ(Y) = {GJ(Z): zgy} A g; = {GJ(Y): ygx}. Hence this is E;(X,9;,~,GJ). Actually "9; E M" is ~l (9;,~) over VII': since one can show that "9; ~ M" can also be expressed in a Ei (X,g) way over VII': by using IV K+m n Ml :S IV K+m-1I• -2- But we will not need this in the sequel. . IV IC+m-21 Next we examme "M C M" (where for m 1 we mean by this M<IC ~ M). This is equivalent to 'v'X 3Y 'v'Z [zgy <==} 3 x Z = Xx], Here X, Y,Z range over V 1C+m-l and x over V IC+m- 2 (form= 1 x ranges over VIC). Recall that any X E V 1C+m-l codes IV IC+m- 2 1 many elements of V 1C+m-l via Xx = {y E V 1C+m- 2 : (x,y) E X}, where x, y range over V 1C+m- 2 (form = 1 there is an analogous remark). So the whole formula is E;(g) over VIC. Finally let us investigate the complexity of the statement "M is IC." For n = 0 recall that by definition this means M ordinal). m (., . ) :En ~ correct for M and we saw Recall that for each m, n ~ 1 there is a above that this is formula x IV IC+m-21 E: that is universal for E: uniformly for all Va ( where a is a limit So for n ~ 1 we can express "M is E: correct for IC in parameters from m 'v'X, Y([3%,Z[% collapses Z to IC /1. (V 1C+m-l'g) I= "X codes a En formula /1. Y E Vz+m /1. X Vz (X,Y)"] => - - E: :Em n 3'!f, k 3~, 9J['!f collapses X to k /1. ~ collapses Y to 9J /1. VIC I= X m :En 3'!f, k3~, 9J['!f collapses X to k /1. ~ collapses Y to 9J /1. VIC I= x 3%, Z[% collapses Z to IC /1. (V1C+m-l 'g) I= x V ! (X,Y)]) :En :r:; (k,9J)]] ./1.. (k,9J)] => -3- where 9J, GJ, (J, % range over V 1,,+m and X, Y, Z over V 1,,+m-l. Hence this formula . lS a m 1(~,1,,) over V K,. n+ Theorem 1- (m ~ 1, n ~ 1) 1,, is n: '<I M[M trans /\ M I= ZF- /\ IMI indescribable, iff = 1,, I\ 1,, E M /\ M <1,, ~ M . ⇒ 3j, N [N trans /\ IN I = IV,,, + m - l I /\ N N is E m n- 1 Proof. IV,,,+m-21 correct for 1,, I\ j: M --+ N /\ cpt(j) Suppose 1,, is n: . ~ N /\ = 1,,l]. ind and assume towards a contradiction that for some M as above there is no j, N as above. We can code the structure (M,E) by a binary relation E on 1,, such that under the Mostowski collapsing function II for (1,,,E) we have II(O) = 1,,. We let F ~ II -1 1,,, and T ~ {(n,e---+ ):n < w, ---+ e E ,,, < w , n is a (code of a) first order formula that holds in (1,,,E) under the assignment e}. ---> We abbreviate by <I>( 1,,,E,F ,T) the statement (1,,,E) is wellfoul'l.ded and extensional /\ F = .u-l 1,,, /\ II(O) = , , /\ T is the first order theory of (1,,,E). Note that E, F and T can be coded by subsets of 1,, in the usual way. If ZF- denotes a sufficiently large finite fragment of ZFC, then "(M,E) is bad" can be expressed as a n:(1,,,E,F,T) formula over V,,, by quantifying over models of ZF-: -4- '\;/ .At,(.At, trans I\ .At, .At, IV .At, i.+m- 21 I= ZF- /\ !Al = IV i.+m-11 /\ ~ .At, /\ .At, E:_ 1 correct for i. I\ i., E, F, T E .At,. ⇒ . I= "~(i.,E,F,T) /\-, 3j, N[N trans/\ !NI = IV i.+m-ll /\ NIV i.+m- 2 ! ~ N I\ N is Em correct for i. I\ j: trans coll(i.,E)--+ N I\ cpt j = i.]"]. n-1 By the JI: indescribability of i. this formula must reflect to some inccessible .,\ < K. Thus we have (.-\,E n .,\ x .,\) is wellfounded and extensional and F n (.,\ x .,\) = Mostowski collapsing function -l1 .,\, and O gets collapsed to .,\ and T n (w x .,\ <w) is the first order theory of (.-\,E n( .,\ x .-\)). Let (M* ,E) be the transitive collapse of (.-\,E n (.,\ x .-\)). Since (.,\,E n (.,\ x .,\)) -< (K,E) and by the choice of E and F there is j*: M* --+ M with cpt j* = .,\ and j*(.,\) = i.. In the usual way we can construct an elementary submode} (X,E) < (M,E) with !XI IV .-\+m-ll and X IV.-\+m-21 correct for .,\, since M is. ~ X and j*[M*] U{.,\} ~ X. Then X is clearly Now collapse X to a transitive N. elementary embedding j* followed by this collapsing map. Denote by j the Obviously cpt j V .-\+m-l U {.,\} ~ X. We have just shown 3J·, N[N trans /\ N = IV .-\+m-1 I /\ N IV I .-\+m- 2 C N /\ - N is Em correct for .,\ /\ j: transcoll (.X,E n .,\ x .X)--+ N /\ cpt j n- 1 but this contradicts the fact that the above JI: E:_ 1 = .X]; statement holds at V .,\. = .,\ since -5- n: For the other direction in the theorem suppose that <I>(A) is and A c;;; V 1,, and V 1,, F <I>(A). Pick a transitive M with IMI = IV 1,,I and M<1,, c;;; M and 1,,, A E M and M F ZF-, where ZF- is a suitable finite fragment of ZFC. transitive and E:_ 1 correct for 1,, and j : M --+ N with cpt j Then let N be = 1,,. Since <I> is n: and NF ZF- we get hence, by elementarity of j MF "3a < 1,,Va F <I>(A n Va)" but (M)a = Va for a ::; 1,, so that really □ end of Theorem 1. i.e., <I>(A) reflects. We will conclude this chapter by making some observations which will not be used m the sequel but are nevertheless interesting in their own right. The first observation involves the concept of hypermeasurability. Recall that a cardinal 1,, is m-hypermeasurable (m ~ 1) if there is an elementary embedding of V into some transitive inner model N with critical point 1,, such that V 1,,+m c;;; N. Theorem 1 suggests that n1 indescribability can be construed m-hypermeasurability for m > 1 in the same way that measurability. as an analogue of lli indescribability relates to -6- [Mitchell, 1979] and Dodd-Jensen ( cf. [Dodd, 1982]) have produced an analysis which shows that elementary embeddings j: V -+ M can be thought of as coming from an ultrapower by a system of measures. This leads to the notion of an extender. Given a transitive set X and a cardinal 1,,, we say that E is an extender with support X and critical point 1,, if E is a function with dom E = (X} <w (the set of all finite 1: 1 sequences of elements of X) and for s E (X}<w, E(s) = Es is a 1,, complete measure on (V ,,,}doms (the set of all 1: 1 sequences of elements of V,,, of length dom s) such that for at least ones E (X}<w Es is nonprincipal and (2) (Coherence) ifs -{ t (i.e., sis a subsequence oft) and s 1r: dom s Ll dom t then for all A ~ (V ,,,}dom s where A1r (3) = to 1r for some = {b E (V,,,)domt:bo1r EA} (Normality) for any s E (X)<w and f:(V,,,)doms-+ V such that there exists some t E (X) < w with s -{ t such that if s = t o 1r · h 1r.: d om s l: l d om t t h en .r1or some 1• E d om t wit --+ 0 Given a transitive set M which models ZF- and is closed under sequences of length <1,, we define an M extender with support X and critical point 1,, as above except that for - 7- s E (X}<w Es is an ultrafilter in P((VIC}doms) n Mand that in condition (3) we only consider f E M. Since each Es is countably complete and M<IC ~ M each ultrapower Ult (M,Es) is wellfounded and we can collapse it to a transitive (Ms, E}. Moreover the coherence condition (2) implies that we have a system of elementary embeddings (is t: Ms --+ Mt: s -< t and s, t E (X} <w} that commute; i.e., for r, s, t E X <w with ' r -< s -< t, ir t = is t o ir,s. ' Therefore we can form the direct limit of the system ' (Ms :s E (X}<w} which we denote by (M~,E~}. extender if (M ~ ,E ~) is wellfounded. We say that E is a wellfounded Note that E will automatically be wellfounded if we work with countable 1: 1 sequences rather than finite 1: 1 sequences. In the context of extenders we can rephrase Iff ( m ;::: 1) indescribability as follows: 1,, is Hi indescribable iff for every transitive model M of ZF- with !Ml = 1,,, M<K CM and IC E M there is a wellfounded M extender with support V Km+ 1 and critical point 1,,. Proof of this Fix m > 1. If IC is Hi indescribable and M is a transitive model of ZF- of size 1,, and - closed -under < IC sequences by theorem 1 we can find a transitive N with V IC + m- 1 C N and an elementary embedding j: M--+ N with ctp(j) = IC. Now for s E (V 1C+m-l) <w define Es by A E Es iff s E j(A) for A E P((V 1C}doms) n M. Then E is a wellfounded M extender smce the directed -8- system (Ms: s E (V 11:+m-l) <w) can be represented inside N by using the fact that each Es is defined from j. Conversely given any transitive M of size K with M F ZF- , K E M and M < ,-,; ~ M and a wellfounded M extender E with support V 11:+m-l and critical point r;, we take N to be the transitive collapse of (M~,E~) and let j denote the usual elementary embedding j:M---+ N that we obtain from collapsing (M~,E~). Clearly cpt(j) = ,-,; and by (1) together with the normality condition (3) V 11:+m-l ~ N. of the easy direction of theorem 1 shows that K is II 1 indescribable. Now the proof □ end of proof. -9- CHAPTER II. THE CONSISTENCY STRENGTH OF THE FAILURE OF GCH AT A II INDESCRIBABLE CARDINAL In this chapter we will evaluate the consistency strength of the failure of G CH at various II indescribable cardinals. In the simple case of a II~ indescribable 1,, one may force any number of new subsets of 1,, and keep 1,, inaccessible since the forcing is < 1,, closed. However already in the case of II~ indescribable cardinal this approach fails: If V model and we add a new subset X ~ 1,, via a = L holds in the ground < 1,, Baire forcing then in the generic extension the II~ statement "X jt L" does not reflect to any inaccessible .\ < K. For a given II indescribable cardinal 1,, in the ground model we will define a forcing iteration of length 1,, + 1 and then use the characterization in I.1. to guarantee that "' remains II indescribable in any generic extension. First we look at II! indescribable cardinals (n ~ 1). Theorem 1 generalizes a theorem of Silver ( cf. [Kunen, 1980]) which says that the failure of GCH at a weakly compact cardinal is equiconsistent with the existence of a weakly compact cardinal. Theorem 1- (n > 1) II! indescribable cardinal) ~ CON(ZFC + 3t. is II! indescribable /\ 2"' > +)) CON(ZFC + 3 t. (1,, Proof._- Suppose 1,, 1s II! indescribable. We can assume V = L since rem ams II K indescribable in L. Fix e ~ 2, we will define a forcing iteration P ,,_ + 1 such that K, +e " • l 11 -10- For limit ordinals A ~ K we let PA = lim dir PT/ TJ<A if A is inaccessible PA = lim in v PT/ TJ<A otherwise and for a ~ K let Qa E VP a a canonical term with 0 11-p a "Qa is the trivial poset if a is not inaccessible and Qa = Fn(a +e,2,a) if a is inaccessible". Note that for any inacessible A ~ 1,, and hence for any Mahlo cardinal A ~ "' since { a < A: Pa = r,<a lim dir PT/} is stationary in A. Moreover we have 11-p "A is inaccessible" A since for any a < A I~ Pa "P a,A is <µ closed" where µ is the next inaccessible ~ a because Pa is clearly µ c.c. Since IP A I get lr--p GCH->A A = A we also -11- and a straightforward calculation shows To finish the proof we have to show lh ""' is p K+l JI! indescribable." Fix a condition p* E P K+l and ~ in JI! and a P K+l name A for a subset of V"' and assume towards a contradiction 0 p*Jh "~(A) describes"'·" p K+l By the reflection principle fix an ordinal 8 > the least inaccessible above "' with 0 "~(A) describes ,,;,."] V Note that in particular P K!l = P K+l. Using standard arguments we can find a transitive M with IMI and E M and some i: M --+ V 8 with cpt i - OM A E M and = "' and M <"- ~ ]VI an elementary 0 0 . M ) = A. (,,;, +M ) and i(p M ) = p * and 1(A embedding . . Ill S Ince K- 1s n indesq,ibable we can find a transitive N with IN I = JV,,;, I = "' and N <"' C N and E 1 correct for K and an elementary embedding j: M --+ N with cpt j n- 1 Note that P K+l is ,,;, + cc and cpt i K. = (K +)M; hence we can use the pullback method to find an M generic GM for P~+l and a V generic GV for PK+l such that p* E G V and i lifts; i.e., -12- M[GM]_i__. V5[GV) PM K+l M P,_+1 i -+ V5. Suppose for a moment that we could find an N generic GN for PN such that j(,c)+l N[GN] is E 1 correct in V[G VJ and j lifts; i.e., n- 1 M[GM] j -+ PN K+l M N[GN] PN j(,c)+l j -+ N. Then we would arrive at a contradiction as follows. Since <I> is u! we get N[GN] F :la < j(,c) Va F <l>(j(S) n Va) where and s = j(S) n v ,_. Hence_-by elementarity But by standard arguments (M[GM])a = (V[GV])a for a~ K so that really in V[GV] -13- i.e., <I>(S) reflects, a contradiction. Hence in order to finish the proof we have only to construct GN with the properties above. First note that P~ j(p) = P 11: smce N <"' ~ N. P 11: ~ V 11: implies that we have = p for all p E P1,,, Let G11: = GV n P1,,, For any H that is N[G11:] generic for the tail pN 11:,J'( K, ) j will lift; i.e., M[G11:] -+ N[G11:*H] PN j(11:) M -+ N. 1 Now we construct an H that is pN '( ) generic over N[G,c] such that N[G11:*H] is E l 11:,J II: ncorrect for 11: inside V[G V]. First we need the following: Lemma Ll- N[G11:] is E and hence (N[G1,,]) 0 1 n- 1 correct for 11: inside V[G1,,], = (V[G1,,]) 0 for a ~ 11: since 11: is inaccessible in V[G]1,,, Thus Before we continue with the proof we need the following: Fact 1.2 ( R, ~ 0). Suppose P ~ V 11: is 11: c.c. and r E yP. r* E yP n V 11:+£ with Then we can find -14- Proof of Fact 1.2. We use induction on e and start with e T = O. Suppose we are given E yP and we already know that the claim holds for all terms of smaller rank than the rank of T. Since Pis IC c.c. there is a cardinal,\ < IC with lf-p (T E VIC ⇒ JTJ ~ ,\). We o pick a term f EV p . o onto with lf-p (TE VIC ⇒ f:,\ --+ T). For each a<,\ we let 0 Aa a max antichain {p E P: :3o- Edom T pJf-p f(a) = o-} and for each p E Aa we pick o-p,a E dom T with 0 p lf-p o-p,a Since for each o- E dom T = f(a). rank ( o') < rank( T) we can find terms o-;,a E vP n V ,c such that now define then T* ~ VIC and JT*I < 1Cj hence T* E VIC and moreover lf-p (TE VIC ⇒ T* = T). -15- Now suppose we have arrived at stage € + l. Let r* ~ {(o-*,p): (o-,p) Edom r} where for O" E dom T a-* E yP n V x:+e with lf-p (a- EV x:+€ => a- = a-*); clearly r* E V,,, + e+ 1 (if we use flat pairing) and □ end of 1.2. 11-p (r EV x:+€+l => T = r*). We can now continue with the proof of the lemma. We proceed by induction and show that for k ~ n - 1 N[G,,,] is E! correct for x: inside V[G,,,]. Let k + 1 ~ n - 1; it is enough to consider <I>(A) in JI!+l with A E (N[G,,,]),,,+l and (V,., F <l>(A))N[G,J and to show that (V,., F <I>(A)) V[G,,,] since by induction hypothesis N[G,,,] is E~ correct in V[G,,,] for x:. that AG,,, 0 p Pick p E G,,, and A E N "' n V x:+l (by applying fact 1.2. in N) such = A and PII~ "Vk F <l>(A)." Now in N (sine <I> is JI 1 x+ 1 ): 'v' .Ab[trans .Ab I\ .Ab F ZF- I\ I.Ab I 1 = IV,,, I I\ .Ab<"' C .Ab 0 I\ .Ab Ek correct for x: I\ P ,.,, A E .Al, . => . 0 .Al, F [Pl~,,, "V,,, F <l>(A)"ll 1 by using the induction hypothesis in N. But this formula is IIk the same formula holds in V, but then by reflection principle in V PII ~ "V K, F <I>(A)." +1 (p,P,,,,A,x:). Hence -16- So (V K F <I>(A)) V[G,d □ end of 1.1. . Now we consider N[G,.:]'s version of the forcing at stage i.:. Since N[G,-] <1. <;;; N[G,.:] in V[Gi.:] this is the initial segment of length (i.: +e)N[G,d of the forcing Fn V[Gi.:] (i.: +e ,2,i.:) that V[G,.:] wants to do at stage i.:. If G denotes the V(G,-] genenc. generic over N(G,,;], Moreover the following lemma shows that N[G,-,g] is E 1 n-1 E! correct (n ~ 0) for If correct for i.: in V[Gv]. Lemma Ll, Suppose .N' F ZF- and x<i.: <;;; .N' and .N' is 1.. correct in V[G] for i.:. Proof of Ll- Note that .N'[g]<i.: <;;; .N'[g] in V[G] since all posets are <i.: closed (we can assume that .N' satisfied choice). We proceed by induction on n. To handle n + 1 it is enougl! to consider <I>(A) in n!+l with A E (.N'[g])i.:+l and (V,.: F <I>(A)).N'[g] and to show that (V 1,, F <I>(A)) V[G] since by induction hypothesisN[g] is for i.:. Pick p E g and a nice Fn((i.: +£),N' ,2,i.:) name E! correct in V(G] A for A <;;; V,.: with -17- Since Fn( x: + €,2,x:) has the x: + c.c. there is a complete suborder Q E N of ~ Q x Fn(x: +€).N" ,2,x:) in .N" and Fn(x: +e ,2,x:) ~ Q x Fn(x: +e ,2,x:) in V. Hence if g = g n Q then in .N"[g] "V d= <I>(A)." +e II Fn((x: Note that A E (.N"[g]),-;;+l. ,2,x:) The following sublemma shows that .N"[g] is E 1 n+ 1 correct in V[g] for x:. Sublemma 1.3.1. Suppose .N" I= ZF- and x<x: ~ .N" and .N" is E~ correct (m 2: 0) for x:. If Q E .N" is a < x: Baire poset with IQ I = x: in .N", then for any G which is V generic for Q, .N"[G] is E~ correct for x: in V[G]. Proof of 1.3.1. Note that .N"[G]<x: C .N"[G] m V[G] smce Q 1s <x: Baire. We now proceed by induction on m. To handle m + 1 it is enough to consider <I>(B) in JJ~+l with B E (.N"[G]\;:+l and (V x: I= <I>(B)).N"[G] and to show that (V x: I= <I>(B)) V[G] since by induction hypothesis .N"[G] is E~ correct in V[G] for x:. Pick q E G and B E .N"Q a nice Q name for B ~ V x: with qj~ V x: I= <I>(B). Since !QI = x:, we can assume that Q ~ V Ii:; hence B EV x:+l · Now in .N" (since <I> is JJ~+ 1 ): 'v'.Ab[trans .Ab I\ .Ab I= ZF- I\ I.Ab!= IVx:l 11. .Ab <x: ~ .Ab 1 0 /\ .Al, Em correct for x: I\ Q, B E .Ab . => . 0 .Ab I= qjf-Q "V x: I= <I>(B)"]. -18- by using the induction hypothesis in N. But this formula is II 1 (q,Q,B,K). m+l Hence the same formula holds in V, but then by reflection principle in V 0 qj~ "V /,; F 4>(B)" so □ end of 1.3.1. Since q> is JI 1 n+ 1 the induction hypothesis applied within N[g] tells us that in N(g] 1 .Ab En correct for,,; /\ A E .Ab . ⇒ . .Ab F I But this formula lS Fn(,,; II +e 1 n+ ,2,,,;) l(i,;,A); "V ,,;F 4>(A)"J. hence by the sublemma it must hold 111 V[g], so in V[g] Fn(,,; +e ,2,,,;) "V /,; F 4>(A)." Therefore □ encl of 1.3. Next we have to construct h which is N[G,,; ,g] generic for the tail PN[G,,;_,g] . h can ,,;+lJ(K) be constructed in the usual way since N[G,,;,g]<,,; ~ N[G,,;,g] in V[GV] and the tail is certainly <,,; closed and IN[G,,;,g]I = ,,;. Moreover N[G,,;,g,h] will be V[G V] since the tail is highly closed. E!_ 1 correct in -19So we have arrived at M[G,cl -:-+ NLl(GK)l J M where j(GK) --+ j N 1 = GK * g * hand NLl(GK)] is E n-1 correct in V[G V] for K. In our final step we use a straightforward master condition argument to find a M[GK,] -:-+ NLl(GK)l J where GN = j(GK) * K. K can be constructed m V[G V] by using that FnNLl(GK)l(j(K)+e,2j(K)) is <K closed in V[Gv] and INLl(GK,)]I = K. N[GN] will still be E!_ 1 correct for Kin V[G V] since Fn(j(K) +e ,2j(K)) is <j(K) closed in NLl(GK)]. □ end of theorem 1. Actually the case m = 1 is very special when one tries to make GCH fail at a II:P indesctibable cardinal. This is because of the following II! (n ~ 0) indescribable by adding + many subsets then adding any number ,\ > of subsets of will force to be II! FACT: if one can force K to be of K K K K K indescribable. Thus in order to obtain the consistency of "K is II! indescribable and 2K = ,\" (where ,\ is some cardinal >K +) it is sufficient to define P K+l by adding at any inaccessible -20- stage µ ~ 1,, µ+ many subsets of µ and then to show that indescribable" if K. was already lfp-- "K. 1s nk nk indescribable in the ground model. K+l m Next we evaluate the consistency strength of the failire of GCH at a ll n indescribable with m ~ 2, n ~ 1. It will turn out that this is consistencywise stronger than the existence of a n: indescribable. Theorem 2_. (m ~ 2, n ~ 1, I!, ~ 2) CON(ZFC + :lK.(ll: ind "' /\ 2/'i, m+e-1 CON(ZFC + :lK. ll n ind 1,,). Assume that V m+e-1 L and K. is ll n indescribable. We define an iteration P"' + 1 by exactly the same clauses as in the proof of theorem 1 and we claim that I I - - "K, is llm indescribable /\ 2"' = "'+e " PK+l n The proof closely follows the ideas in the proof of theorem 1 and we will keep the notation that we used as much as possible. show that 11-- "K. is p1,,+l n: The hard part of the proof is again to indescribable." m+e-1 Now we know that 1,, is ll n indescribable in the ground model; hence there is a trans N, with NI= ZF-, INI = IV correct for K. I NIV K+m+e- 3 I ~ N and N Em+e-l K+m+l!,-2 ' n-1 and an elementary embedding j: M --+ N with cpt j "'· After -21- constructing GM and G V as in the proof of 1 we have only to come up with a generic GNsuch that N[GN] is Em n- 1 M - Pj( ,_) + 1 correct in V[G V] and j lifts; i.e., N. N +(m+C-3) As in the proof of theorem 1 Gx: is P x: = P x: generic but now N[Gx:t C is E m+e-1 n-1 Note that certainly ( "'~ +e)V[Gx:] _ So N [G x: ] wants to d o t h e same forcing at stage ,;; of P~( ) J II': +1 that V[Gx:] wants to do at stage x: of P x:+l; namely, Fn(x: +e ,2,x:) which we denote by P from here on. Before we continue with the proof we need some technical lemmas. Note that P is x: + c.c. and < x: closed and has size x: + e, so we can regard it as a subset Working in N[Gx:] we define by induction on r > 0 names 0 Let V x: (V x:r and to define Vx:+r E (N[G,_]l. Vx:+r+l choose for each nice p name T E N[G,.t for o N[Gx:] o a subset of V x:+r a maximal antichain A 7 ~ {p E P: PII p r ~ V x:+r}. Then let Y,-+r+l= LJ{r}xA 7 • r a mce P name 0 for a subset of V x:+r -22- Lemma 2.1. (r ~ 0) Vo II N[GK] P Proof. We use induction on r ~ 0. By the <K closure of P Now assume G is P generic over N[GK] and - V K,- K. X E (N[GK])p with :x.G C By induction hypothesis pick Po E G such that Poll N~G,,J 0 V K+r. Choose a nice name r E (N[GKk]) p O E yG K+r+l 0 for subset of V K+r with Poll- X Then {q ~ Po: :lp ~ q p E Ar} is dense below p 0 ; hence Ar 0 X C r. n G =/= 0. So :x.G = rG . Conversely if :x_G E yG then, by induction hypothesis clearly :x.G K+r+l □ end of 2.1. 0 0 Lemma 2.2. (r ~ 1) every V K+r and every nice P name for a subset of V K+r can be coded in a highly absolute way by an element of V K+r+e. Proof. Since P ~ V K+e has the K+ c.c. every P antichain A has a code A E V 11:+ e. Now we proceed by induction on r. r 0 = 1: a nice P name X for a subset of V K looks like this: O= X u {x} Ax X xEV,,, 0 where each Ax is an antichain m P. {(x,Ax):x E VK} which is E V,,,+e since IVKI Now we code X 1,,. 0 by X 'M code of -23- 0 Hence we can code V,,, + 1 by 0 V i,,+l = {(r,Ar): r a nice P name for a subset of V ,,,} 0 clearly V K+l E V K+l+e . 0 0 A nice P name X for a subset of V,,, + 1 looks like this: X = LJ {r} x Br 0 rEdomV i,,+l 0 where each Br is an antichain m P. By definition each r E dom V i,,+l is a mce P 0 name for a subset of V,,,; hence each r E dom V i,,+l has a code r E V ,,,+ e. 0 So we can code X by 0 Thus, clearly, X E V i,,+l+£. The induction step is now straightforward using exactly the same argument:Finally it is clear that there is a weak fragment ZF- of ZF such that for any trans M with M F ZF- and ,,,, P E M decoding if it has enough closure. M can correctly compute the coding and □ end of 2.2. Let us denote by G the P generic that we add at stage,,, of P i,,+l (i.e., G V = G,,, * G). -24- Proof. An Note that in V[G V] N[G11: ,Gt easy calculation shows that in V Therefore we get that (V[G D11:+m-l induction on O < k ~ n - 1. +(m+€-3) V[GV) ~ N[G11: ,G) because P is 11: + c.c. l(V[GV])11:+m- 2 1 = 11: +(m+e- 3 )_ = (N[G11: ,GD11:+m-l. If n 2:'.: 2 we proceed by In order to handle k + 1 < n - 1 it 1s enough to consider <l>(A) in -":+l with A E (N[G11: ,GD11:+m and N[G11: ,G] F <l>(A) and to show that V[G V] F <l>(A). We pick a nice P name A E N[G11:t for a subset of V11:+m-l with AG = A and p E G with PIIN[;11:J "VII: F <l>(A)." 0 0 0 0 Note that by lemma 2.2 A has a code A E V 11:+m+e-l such that decoding A from A is highly absolute. Now we have m+e-1 o /\.Ab Ek correctfor11: /\ P,A E .Ab ⇒ 0 ~0 .Ab F "plf-p "V 11: F <[> (theniceP nameforasubset of V 11:+m-l coded by A)"). This holds because <[> 1s .llm and we can apply k+l the induction hypothesis within m+e-1 o Since this last formula is .llk (11:,P,A) it must hold m V[Gd because +1 -25- m+e-1 N[G,d is E n-l correct for ,;, in V[G,,,]. Hence we get in V[G,,,] PIIV[;,,,] "V K, F <I>(A)." Therefore we conclude that in V[G V] □ end of 2.3. V K, F <I>(A). Now we continue as in the proof of theorem 1 and construct H that is N[G,,,,G] ·c ). This is done in the usual way by observing that the tail generic for the tail PN ,;,+l,J k is <µ closed in N[G,;, ,G] where µ is the least inaccessible > that IN[G,,, ,G]I "'· Moreover the closure of the tail will yield that N[G,,, ,G,H] 1s +(m+e-3) Em n-1 j(p) ,;, + 1 and by recalling correct in V[G V] and N[G,,, ,G,H]"' c N[G,,, ,G,H] in V[G V]. Since = p for p E P 11: j lifts; i.e., M --+ N In our final step as in the proof of theorem 1 we use a straightforward master condition argument to pick K which is Nu(G11:)] generic for Fn(j(11:) +e ,2j(,;,)) such that j lifts; i.e., -26- M where GN --+ N = Gx: * G*H*K. N[GN] will be Em correct in V[G VJ smce n-1 Fn(j( x:) + (! ,2,j( x:)) is <j( x:) closed in N[j( G x: )] . ........ " ".....,,. suppose x: is n: indescribable and 2x: = x: +£; we claim that m+£-1 L ( x: is ll n ind) . Let <l>(A) m+£-1 = Vffi ¢(ffi,A) where 'If' is E n-l and g; ranges over V x:+m+e-l and A E V x:+l n Land assume (V x: I= <I>(A)f. If n ~ 2 then we need the following lemma before we continue with the proof. Lemma 2.4. For n ~ 2, ¢L(ffi,A) is Em (ffi,A,x:) over V x:. n- 1 Proof. _- Let T be a finite fragment of ZF + V T we have M = L such that for any trans model JV! of = LonnM and write ¢(ffi,A) as where Q E {3, V} and the g;i range over V x:+m+£-l and 0 is E m+£-1 0 -27- Since V 11:+m+£-l n L ~ L +(m+£-l) (V 11: F 1P(ffi,A)f is equivalent to II: Now 11: +(m+£-2) ~ IV 11:+m-ll allows us to code each Lri with 'Yi < 11: +(m+e-1) by a subset 9Ji ~ V 11:+m-l; then the last formula is equivalent to 3 9J 1 FT · ·· Q9Jn- l FT Q .At,( .Al, trans /1. .Al, F ZF- /1. I.At,l=IV11:+m-ll/l..At, Note that for any such 1,, +(m+£-3) IV11:+m-21 .Al, 11: ⇒ ~.Al,/l.$,9J1,···,9Jn-l'AE.AI, ·/1.. +(m+£-2) ; hence V 1,,+m+e- 2 n L ~ L .At, = (11: +(m+£-2) .At, . ) smce IV ;;;+m- 2 1 > so that (V 1,, F 0) L . 1s absolute for .Al,. □ end of 2.4. Now fix M with IMI = 1,,, M trans and M F ZF- and M<K ~ Mand 1,, E M. By the m Il n indescribability of 1,, there is a trans N with N IV1,,+m-21 rn ~n-1 C N and N )' -28- correct and an elementary embedding j: M --+ N with cpt j = 1,,. By the lemma we get for n ~ 2 LN (Vffi E L n V1,,+m+e-1 (V,,, F ¢($,A)) ) . This holds also if n = 1 since then ¢($,A) is E Om+e-1 and we can use the argument from the last part of the proof of the lemma where we mentioned that (V 1,, F 0)L is absolute for ..At.. Hence by the elementarity of j, for some a < 1,, i.e., □ end of theorem 2. -29- CHAPTER III. THE CONSISTENCY OF ug1 > 1rg1(m ~ 2, n ~ 1). SECTION 1- General Remarks about the Construction. The aim of this chapter is to prove the following. Theorem Ll- (m ~ 2, n ~ 1) CON(ZFC + 3K, K 1 (K < K 1, K is => CON(ZFC + u~ > n: indescribable, and K 1 is E: indescribable) + GCH) In order to prove this theorem we will work in the theory ZF + V = L and assume that we have a n: indescribable cardinal K and a Then we will define a K + 1 stage iteration (1 .2) I~ L________ pn " P: E: indescribable cardinal K 1 > "'· such that 1 . d escn"b a bl es ~ K, K 1s . llm . d escn"b a bl e, K 1 1s • L.., ,,n t h ere are no Em n m n m 11 indescribable." Hence we will obtain The definition of P: will be motivated by the fact that we want no pm cardinals in V n below K. Thus P: E: indescribable will be essentially a K + 1 stage forcing iteration where at stage ,\ < ,-, where ,\ is Mahlo we do some forcing that ensures that ,\ will be -30- E: pm describable in V n (The fact that we also have to do something at stage ,;, will play a role later in the proof that P: preserves the n: indescribability of ,.,., - we already encountered this phenomenon in II.1. and II.2.) Thus - as a first approximation - we can define the stages in pm n,O P: as follows: = {0} and for limit ordinals a ~ 1,;: m Pn a ' = limdir (<a if a is inaccessible m Pn a ' = liminv otherwise. and (<a pm To define Pm A n, +1 for a Mahlo cardinal A < K we pick a canonical term Qm . n,A E V n,,\ such that 11-mp "Qm n,A n,A is a certain finite step iteration of A is inaccessible and GCH ~ A holds and A+e otherwise Qm n,A is the trivial poset." To define the successor Pm n,/3+1 for an ordinal /3 that 1s not a Mahlo cardinal we pm just pick a canonical name Qm n,A E V n,A for the trivial poset; i.e., at stage /3 where (3 is not Mahlo we don't do anything. step iteration" ? Now what exactly do we mean by "certain finite -31- pm Suppose we are in V n,>. and >. is inaccessible and GCL~). holds and ). +e = (>. + C)L for e ~ l. In the first two stages ( for n = 1 this will be done in one forcing) of Q 111 n,>. we add an object that is modulo coding of type mover V,,, (i.e., a subset of V 1;;+m-l) Em and then force that a certain statement <I> n holds about this object. The first poset will have size >. +(m-l) and will be <>. +(m-l) closed. < >. +(m-2) closed and < >. +(m-1) the first forcing will have size >. Baire and >. +(m-1) and <>. +m The second poset will be c.c. and of size >. +(m-1) +m (for n = 1 closed). Hence in particular after forcing with these posets, >. is still inaccessible, GCH ~). holds, and >. + e = f for e ~ l. Recall that in the definition of (). + e E: describability of >. we allow only parameters that are subsets of V).. Hence in the next (m - 1) steps we code down the object of type m on V). that we first added successively until we end up with code S). ~ >.. This goes as follows: It will turn out that the object that we added at the first step of stage can be coded by a subset ( "' +(m-l))L and "'+(m-2) the A). C >. +(m-1) . . +(m-1) Smee >. = = ('" +(m-2))L we can use a 1most d"1sjomt . r . 1 1orcing wit 1 < least almost disjoint family of size >. +(m-1) of constructable subsets of L ). +(m-2) . . +(m-2) +(m-2) _ . The forcmg 1s ). centered and <>. closed. Thus after we 2 do this forcing and obtain a code for A;. which is ~ >. +(m- ) we still have that >. is inaccessible and GCH~). holds and >. +e = (>. +ef for l!. ~ l. Thus we can proceed in this fashion until we end up with a code S). ~ >.. -32- Now in the last step of our iteration Qm we will force a club set C.,\ C .,\ such n,.,\ that Em C .,\ n {µ < .,\: µ inaccessible /\ V µ p= <I> n (the object coded by S .,\ Note that this forcing has size .,\ and for each µ n V p)} = 0. < .,\ there is a dense suborder that 1s <µ closed (it consists of all conditions whose top element ?_µ). Therefore we get the following: Q m has for each µ < .,\ a dense suborder that is < µ closed. n,.,\ One can prove for each inaccessible .,\ ~ "' by induction on a. For the successor step one has to use that for each o: < .,\ llpgi since ".,\ is inac" because JPm n,o: J < .,\ by induction hypothesis. From (1.3) we can deduce V .,\ ~ "' (.,\ Mahlo ⇒ P::\ is .:\ c.c) ' since {~ < .,\ Pg1 a ' = dirlim Pg11/} is stationary in .:\ by the Mahloness of .,\. Hence we TJ<A ' can conclude that for all Mahlo cardinals .,\ < "' -33- In order to show that for Mahlo A ~ K If---m- "A is inaccessible" p n,A we need to observe that at any intermediate stage the iteration factors in a nice way. Lemma 1.4. Let O < o: < K and P m denote the tail of the iteration n,o:+ 1 ,K+ 1 Ifµ denotes the least inaccessible E (o:+1,K+l) then "for each v < µ Pm has a dense suborder *pm n,o:+1,K+l n,o:+1,K+l that is <v closed." Proof. Let G be Pm generic and fix v < µ. We claim that in V[G]: n,o:+ 1 (1.5) If f3 E (o:,K+l] is a limit ordinal then Pm /3 is either a direct or an inverse n,o:+1, limit. Moreover if cf /3 < v then Pm /3 is an inverse limit. n,a+l, In order to prove (i.5) note that !Pm I < µ and that for /3 E (a+l,K+l) with n,a+l liminv r,</3 Pm (in V). n,r, Now we can use the same ideas as in [Baumgartner, 1983], Section 5. For 6 E [o:+1,K+l] we define *p m m V[G] = {f E P n,o:+1,6 :-'</(Edom f 11 m p n,o:+1,6 ".l)f n,a+l,( m dense suborder of Q "}. n,( "f(() is in the <v closed -34- The first half of (1.5) implies that *pm • is dense. The full claim (1.5) shows that n,a+ 1 ,u □ end of 1.4. *pm • is < v closed. n,a+l,u Given this lemma it is easy to see that for Mahlo .,\ ~ x:, lf---m- ".,\ is inaccessible." pn a ' This also shows that at each Mahlo stage .,\ ~ x:, the requirements for doing a finite step iteration Qm, are satisfied. Then it will follow n,A I ~ "there are no Pn E: indescribables <x:, ." Finally one can apply 1.4. to show by induction on a < x:, that I ~ GCH; hence we Pn,a obtain Preservation of the E: indescribability of x:,'. This follows from the fact that the iteration µ > x:, ~J:s inaccessible so that in particular Lemma 1.6. Let x:, be 11-p "x:, is E: E: P: P: can be defined inside any V µ where E V µ. We prove the following general indescribable and P be a poset with P E V x:, • Then indescribable." -35- Proof. Suppose G is P generic and~ is E: and A E (V[G,c]),c+l and, in V[G] V ,c F ~(A). Pick A E yP with (A)G = A and p E G with 0 (1.7) Plf-p "V,,, F ~(A)." Let µ be the least inaccessible <,c with P E V µ. pick Now for any inaccessible II E (p,1,,) A. E yP with 11 o* For each such II we can apply 11.1.2. and find A 11 E yP n V v+l with 0 * 0 Plf-p Av= Av. Then define o* Av. U X*G]f 11E(µ,1,,) 11 inaccessible Clearly o* o Plf-p A = A 0 and we have A* ~ V,,, and for each inaccessible II E (µ,1,,) o* (1.8) Plf-pA nvv =Ao* nvl/. (Here consider A* n Vv as an element of VP. Now (1.7) is E:(p,P,ic,A*) over v,,, since it is equivalent to -36- 3.At,[.At, transitive, .At, F ZF- , I..A1ol = IV i-+m-11 .At, IV i-+m-21 m o ~ ..A1o, .At, Jin-l correct for i., .At, F [Pl~ "Vii: F <l>(A*)"]]. To see this note that for any such .At, the Jim correctness of .At, inside V for ,- will n-1 imply that with any P-generic H because P E V ,_. By the E: ..A1o[H] will still be II:_ 1 indescribability of K in V this correct for K inside V[H] E: fact must reflect to some inaccessible A E (µ,i. ). So we get where we consider A* n V) as an element of vP. By applying (1.8) we obtain that in o* G = An V). Therefore in V[G] V[G], (A n V )) □ end of 1.6. i.e., <I> reflects. Preservation of the II: Indescribability of K. This is the difficult part of the proof of (1.2) and we are going to use the reformulation in I.1. Assume towards a contradiction that <I> 1s II: o pm and A E V n and for some condition p E P:1 we have 0 pjf---m "<l>(A) describes i.." pn By the reflection principle we can find some ordinal 8 > the least inaccessible above K -37- o m such that V 8 F [ZF- /\ p I ~ "<I>( A) describes 11:"]. Note that P n E V . 8 Pn Using standard arguments, one can construct a trans M of size 11: with M<K C M and an elementary embedding i: M --+ V MA EM with i(Mp) 8 with cpt i > 11: and some Mp E M and = p and i(MA) = A. Using more or less straightforward master condition arguments we will construct a V generic VG for P: and an M generic MG for M(P:) such that i lifts; i.e., i --+ M V --+ l and also p E VG. By applying 1.1. we can also find a trans N with IN I and N is Em n- 1 = IV 11:+m-l I and N IV11:+m-21 C N correct for K in V together with an elementary embedding j: M --+ N with cpt j = 11:. In order to finish the proof we have to come up with an N generic NG for N (Pm) such that N[N G] is Em n n-1 correct for 11: inside V[V G] and j lifts; i.e., j --+ M N. -38- Since p E VG we get in V[G] <I>(A G) describes ,-., . The E:_ 1 correctness of N[NG] for,-., inside V[V G] implies Then by elementarity of j and the fact that AG E M (since cpt j K) we get It will be the case that (M[MG]) <,-., ~ M[MG] inside V[V G]. Thus in V[V G] Therefore we get a contradiction. In order to find a generic NG with the properties above we use master condition arguments. At the last step of the last stage of the construction of NG where we add a certain club set ~ j(,-.,) we will see that the iteration as we have defined it does not allow us to pick a master condition. We are going to avoid this problem by adding at each Mahlo stage .,\ ~ ,-., of P: a .,\ + sequence (rather than just one) of objects of type (m-1) over V .,\ and then we make a E: fact true for half of them and its negation for the other half. Then we code all these objects down until we end up with a .,\ + sequence of codes that are each ~ .,\. Finally we add a.,\+ sequence (rather than just one) of closed sets ~ .,\ each of which avoids a certain set of inaccessibles. We shall see that with this modification we will be able to find a master condition in the very last step of the construction of NG. -39- The key point will be that in order to get a generic for the first step at stage 1,, m N (P:) we do not merely take the generic for the first step at stage 1,, in V (P:). Instead we choose a certain permutation of the sequence of generic objects at the first step of stage 1,, of V (P:). This permutation will ensure that for certain IMI = 1,, - many of the objects for which a E: fact holds in V[V G], a n: fact (its negation) will hold in N[N G] and this fact will allow us to pick a master condition in the very last step of the construction of NG. The most difficult part of the proof will be to show that N[N G] will still be Em correct inside V[V G] for n-1 permutation. 1,, m parameters from V 1,,+m after we do this -40- 2 2 SECTION 2. a- 1 / 1r 1 . 2.1. The Iteration Pi In this section we will write Pa instead of P 21 ,a . In Section 1 we have already outlined the general structure of this iteration and here we will restrict ourselves in exhibiting the 3 step iteration at stage ). ~ 1,, (where ). is Mahlo) that we use in order p describable in V ). + 1 2 1 to make ). E have seen in Section 1 that in V[G).] So assume G is P). generic over V = L. vVe .Xis inaccessible, (A +ef = .X +e for e> l and >.X GCH- holds. The forcing Q(l) that we use at the first step of stage .X will add a sequence (A'}':). < ). +) where for even 'Y < ). + A'}' is a pair consisting of a subset of.\+ and a club set ~,\ + that is disjoint from it and for each odd 'Y < .\ + A'}' is a subset of.\+. Q(l) will be a ). + product with <>. + support of posets that are each <.\ + closed and So Q(l) is<>.+ closed and has size>.+. Hence if (A'Y:'Y<.\+) is generic for Q(l) then in V[G).,A'Y] still). is inac, (>.+)e = p+C)L fore~ land have size .x+. >). GCH- holds. - - If we let A'Y ~ A'Y for odd 'Y and A'Y ~ the first component in the pair A'Y for even 'Y then a E~ fact is true about each A'Y where 'Y is even (namely, "i-\-y is not stationary") and a JI stationary"). Thus Q( 2 ) 2 1 fact is true about A'Y where 'Y is odd (namely "i-\-y is - ~ >. + a code C .\. Now in the next step Q( ) we will add for each A'Y 2 = TI 'Y<>.+ <>.support QA'Y where Q- is the forcing for coding A'Y ~ ). + by a set C >.. A'Y -41- For this let (T( :( < A+) denote the <L least constructible sequence of size ,\+of almost disjoint subsets of .X (note that ,\ + = (,\+fin V[G_x ,A,]). The conditions in are pairs (s,b) wheres~ A and b ~ .x+ and isl, lbl < A and QA "Y (s 1 ,b 1 ) ~ (s 2 ,b 2 ) iff s 1 2 s 2 , b 1 2 b 2 and Clearly QA "Y is <.X closed and .X centered (for this define (s 1 ,b 2 )-(s 2 ,b 2 ) iff s 1 = s 2 ). Moreover if S, is Q - A, generic then in V[G (EA, {=::;> S, ,\,A, ,S,] for all ( E ,\ +: n T( is unbounded in .X where S, ~ U {s: :lb(s,b) ES,}~,\. If we pick a generic (S,:, < .X +) for Q( ) then in V[G .X 2 1,, ,A, ,S,] for even , < + we created a E 2 fact in the parameter S, - ~ ,\: 1 (2.1) The set coded by S, is not stationary in ,\ + Note that for odd , < ,\ + A, is still stationary in V[G ,\,A, :S 1 ] since by a standard A system argument Q( ) has the property .X 2 we still have.Xis inaccessible, .X + + . Moreover in V[G, ,A, ,S , ] --+ --+ = (.X +/for€ ~ 1 and GCH~.X holds. In the final step of the 3 step iteration at stage ,\ we add a sequence (C,: 1 < A+) of club sets ~ ,\ via a product forcing Q( ) 3 each , < ,\ C, + n 2 El {µ < .X:µ inaccessible/\ V µ I= <I> (S, = f1 ,<,\+ <.Xsupport n V µ)} = 0. such that for -422 Here ~ L\ (S,) _ is the E 2 statement in (2.1). Obviously each Q' 1 has size A. Thus by (3) a standard ~ system argument Q( ) has the property A+. Furthermore for each a < A 3 Q( 3 ) has a dense, <a closed suborder. Hence in particular Q( 3 ) is <A Baire. So it is easy to see that for Mahlo A ~ 1,, II A is E P.X+l 2 1 describable. In fact we have for each Mahlo .X ~ 1,, II p ,,,+1 .X is E 2 1 describable. p . . S ect10n . 1, m . V smce as we saw m .x+ l t h e ta1·1 P .X + l ,1,, . + 1 1s. h"1ghl y B a1re. p 2.2. Preservation of the II~ Indescribability of 1,, in V 1,,+l Assume towards a contradiction that for some condition p * E P,,, + 1 and cfi 111 2 0 p IJ 1 and A E V we have 0 p*II P,,,+1 "~(A) describes 1,, ." Pick a 6> the least inaccessible greater than 1,, such that 0 "~(A) describes 1,,"]. Note P,,, + l E V 6 . -43- By standard arguments we can t:ind a transitive M with IMI = 1,, and M<"' ~ M and an elementary embedding i: M --+ V 8 with cpt i > 1,, such that for some MP, Now we have to find an M generic MG for Mp 1,,+l and a V generic VG for P 1,,+l such that p* E VG and i lifts: M[MG] --+ V5[V G] l M P,,,+1 M --+ l P,,,+1 V5. Construction of MG and VG. Since cpt i > 1,, and Mp,,, = P,,, ~ V ,,,we can take any V generic for P,,,, say G,,, with p*I,,, E G,,, and i will lift; i.e., M[G,,,] P,,, M P,,, --+ For the first step at stage 1,, of P:+l and P 1,,+l recall that Q(l) is <K + closed. Since IM[G,,,]I = 1,, any M[G,,,] generic for MQ(l) only has to meet 1,, dense sets. So in V[G,,,] we can pick a generic M1 1 for MQ(l) in the usual way. -44- Q(l) is also <1- + directed closed, hence there is a condition extending all i( q) M-+ A 1 . Any such condition in Q(l) is a master condition. for q in For the second and third step note that both Q( ) and Q( ) :1ave the 1,, + c.c.; 2 3 hence the pullback method works since cpt i = (1- +)M > 1-. Note that by the usual arguments M[MG]<'- ~ M[MG] inside V[V G]. By I.1. the JI~ indescribability of "' implies that m V INI L there 1s a trans N with = ,.+, N" ~ N (i.e., N is E~ correct for 1-) and an elementary embeddingj:lVI--+ N with cpt j = 1-. Now we have to come up with an N generic NG for Npj(K)+l such that N[N G]" ~ N[N G] inside V[V G] and such that j lifts; i.e., --+ j M --+ j N. Construction of N[N G]. First we find a NGj(1-) that 1s N Pj( 1-) generic over N. Note that P,.., C -45- and Np,,, NG Since P,,,. cpt j K, "( ) that is N[G,,,] generic for N[G,,,Jp K.,J K, it will therefore suffice to find "( ) ; then with NG.( ) = G,,, * NG '( ) J K, GJ)f h:,J le K.,J K, j will lift. Since P,,, is "' c.c. we get N[G,,,]"' ~ N[G,,,] inside V[G,,,]. Hence the poset N Q(l) that we use at the first step of stage 1,, in Npj(1,,) is the same as Q(l) which we use at the first step of stage "' in P 1,,+l. Now consider the <L least permutation II in the ground model V = L such that II: Even,,,+ --+ Even,,,+ - Even Recall that in V = L · M (1,,+) 1(1,, +)Ml = "'· Denote by (A 1 : 1 < 1,, +) the generic sequence for Q(l) of P ,,,+ 1 . Then define for the noncritical 1 < "'+ (i.e., those I with -1 and II( 1 ) both even or both odd) And fo~ the critical 1 <,,,+(i.e., 1 odd and II(,)< (1,,+)M even) Because II is in the ground model (N A 1 : 1 < "'+) is certainly N[G,,,] generic for Q(l)' Hence for each critical 1 < 1,, + - in V[G,,, ,A,]. N A. 1 is stationary in N[G,,, ,N"A ,] but nonstationary -46- By the <K- + closure of Q(l) N[G"', N ---+ Ar] "' ~ N[GK.,N Ar] inside ---+ N N+ V[G"' ,Ar]- Hence Q( 2 ) wants to add codes ~"' for each of the Ar C "' via almost disjoint forcing using the < L least constructible family (T ( : ( < "'+) of almost disjoint subsets of"'· Hence with Nsr 'M SII(r) the sequence (NSr:r<K-+) is certainly generic And by the "' + c.c. of Q( 2 ) N---+ N---+ ---+ ---+ N[G"' , Ar, S rJ inside V[G"' ,Ar ,S rJ (note again that II is the ground model). At the last step of stage "' of Npj(K-) we just take Ncr 'M CII(r) and by the same The C N PK-+lJ(K.) has from the viewpoint ofN[G"', suborder. Since INI tail N---+ N---+ N---+ + Ar, Sr, Cr] a<"' closed dense = "'+ in the usual way we can m V[G VJ pick a generic Now we handle stage j( K-) of N Pj( K-) + 1 . At the first step we note that the forcing we encounter is <j( K-) + directed closed; hence a straightforward master condition argument works for the first step of stage "' of MP K-+ 1 . -47- In the next step we proceed analogously since by the <j(i-) directed closure of the forcing at the second step of stage j(i-) of N Pj(i-)+l we can always find a condition extending all j(p) where pis a condition in the generic (MS,:,<(i-+)M) for the second step of stage i- in MP,_+ 1 . Now we consider the very last step where we add aj(i-)+ sequence of club sets. Before we finish the proof let us take a break and see what would happen if at stage 1., of P i-+l we had just added one subset of ,- + rather than ,- + In this many. construction denote the pair consisting of a subset of ,- + together with a club set ~ i- + disjoint from it that we add in the first step of stage ,- of MP,_+ 1 by A i'vI and the one in the first step of stage ,- of P 11: by A. Let MS ~ ,- be the code for lVI A and S ~ 11: be the code for A and Mc the club set that we add at the third step of stage 11: of Mp 11:+l. construction we In order to lift the embedding j at the very last step of this must find a club set c* ~ j(11:) of cardinality <j(i;,) 111 N[G11: j(M A)j(MS)] such that j(p) C c* for all conditions p "in" Mc. But for all such p p §- 11: and IPI < 11:; hence j(p) = p. Thus we must have K E c*. The problem is now that in order for c* to be a condition in the forcing at the third step of stage j ( i;,) is inaccessible and -48- E2 where <l> l (j(MS) n V 11:) says that the set C 11: + which is coded by j(MS) n V,;, is nonstationary in 11: +. To prove (2.2.) note that since gM ~ 11: and that since gM ~ 11:. But the set coded by S (namely, A) is nonstationary in N[G11:) and hence 111 We shall now see how the permutation II that we chose avoids this problem. We define a condition c* for the forcing at step 3 of stage j(11:) of N Pj(11:)+l by where (C~ :-y<11:+) is the generic for the last step of stage 11: of Mp11:+i · We have to show that c* is really a condition! -49- Notice that le*! = K < j(1,,) and that for each , < (1,, +)M c; subset of j(1,,) of cardinality <j(1,,). Now fix any , < (1,, +)M. We have to show that 17 (2.3) cJ(,) is a closed J( ,) 2 n {µ < j(,,:):µ inaccessible AVµ I= <I> 1 (J(· M-S)j(,) n V µ)} = 0 E2 where <I> 1 is the statement (2.1). Clearly we don't have to worry about the µ < · MJ( S,) K since j(MS)j(,) n Vµ n V µ = M-S 1 n V µ and since V µ+w is the same whether computed note that K · MJ( S\(,) n V,;: = M-S, = i( M-S,) = (i M-S\(,) = S, (i.e., the ,-th code that we added at step 2 of stage K of PK+ 1 ) . Recall that we defined NS rr :-- l ( ) 1 that rr- 1 [(,;: +)M] ~ Odd +. Hence the set coded by S,, i.e., A, = NA in N[G,,: ,NA,]. But then this set must also be S1 and II- 1 (Ai) , is stationary in K, stationary 111 NLi(G,,:),j(MA, ),j(Ms 'Y )] by some elementary chain condition and closure arguments. Thus we have shown (2.3). Finally it is clear that c* extends j(p) for all p in the generic M---+ C I and therefore c* is .a master condition for the very last step of the construction. arguments establish that N[NG]K ~ N[NG] inside V[V G]. Routine -50- SECTION ,a. u1{1 /1r1{1 (m?. 3). In this section we will always write Pa instead of Pm 1 ,a At stage . X ~ 1,, (where . X is Mahlo) we will do a ( m + 1 )-step iteration to guarantee that . X will be E~ p describable in V A+ 1 Suppose that in V[G ,x], where GA is P ,x generic we have: A is inac, (A+ ef A+e for e ?. l and GCH?.A holds. In the first step Q(l) of the (m-1) step iteration we force a sequence (A 1 : 1<..X +) where for each even 'Y < A+ A 1 is a pair consisting of a subset of . X +(m-l) and a club set <;; . X +(m-l) disjoint from it. For odd 1 < >. + A 1 will simply be a "new" subset of 'Y +(m-l). Hence Q(l) is . X + product (with full support) of posets that are each < A +(m-1) closed and have size . X Q(l) is <..X +(m-l) closed and has size A+(m-l)_ stationary for odd ")' < ,,;, + . Th us +(m-1) Note that A 1 <;; . X is +(m-1) and A 1 <;; A is not stationary for even 1 < (where A 1 is defined from A 1 as in the inaccessible and (A +ef +(m-1) ,c + 1ri/ui case). Moreover in V[G 1 ,A 1 ] .\ is still = . X +e for e ?. l and GCH?.A holds. +(m-1) In the next (m-1) steps we code each A 1 <;; A down until we end up with a_code that is a subset of ..X. m-k given a sequence (S 'Y At the k-th coding step (1 ~ k ~ m -1) we will be ·• 'Y <A+) where each C m-(k+l) = A- 1 ) and we want to code them by (S- 1 m-(k+l) (k l) <;; "'+m- + (define "'+o S-,,.,, . X +(m-k) (for : r < . X + ) where each " . Q (k+l) t h at d oes t l. . ="') . Th e -'1orcrng 11s 1s a -51- product of length A+ (with full support if k < m - 2, with support <A+ if k 2 and with support < A if k =m - = m - 1) where each factor is A+(m-(k+l)) centered and < A+(m-(k+l)) closed and has size A+(m-k)_ Thus Q(k+l) has the A+(m-k) property and is <A +(m-(k+l)) closed and has size A+(m-k). A is inaccessible, (A +ef coding: m-k code S C A r +(m-k) So throughout the A+e for e 2: 2 and GCH::2:A holds. Therefore to - m-(k+l) , +(m-(k+l)) by some Sr C " we can use almost disjoint forcing with the <L least constructible family of size A +(m-k) of subsets of A+(m-(k+l)). In the (m+l) the step at stage A we add a sequence (Cr: r club subsets of A such that for each r Cr n < 1,, + Em {µ<A:µ inaccessible AVµ F <P 1 (Sr Em where <P 1 (S < A+) of n V µ)} = 0 n V µ) says that the set C µ +(m-1) coded by s- n V µ C µ IS nonstationary. The forcing Q(m+l) that adds (Cr: r corresponding forcing in the II p "1,, < A+) 1s the analogue of the ui /1ri case. The proof that is JI~ indescribable" ,,,+1 is entirely analogous with the corresponding proof in the 1ri /ui case. -52- SECTION 1,. 2 2 ( The Generic Case). uaf1r 3 4.1. The Iteration P~. We restrict ourselves to describing what we are going to do at the stage A < 1,, where A is Mahlo in order to guarantee that 11 p2 3,A+l "A is E 2 describable." 3 In this section we are going to use PA instead of P 2 o , . Choose a term QA E V PA 3,A such that 0 I~ QA is a certain 4 step iteration if A is inac, A A+e = (A +e ) L for e ~ l and GCH >A - holds; 0 otherwise QA is the trivial poset. By "certain 4 step iteration" we mean the following: Suppose that GA 1s PA generic A+e for e ~ l and GCH~A holds. In the first step Q(l) we add a sequence (F 1 : 1 < A+) where each F 1 :2A + X IS Lipshitz function; i.e., each F I is really a function with domain LJ a 2a x 2a and a<A+ range contained in 2<A + and for X, Y ~ A+ one defines F,(X,Y) = LJ . a<A+ F 1 (X n a, Y n a). The poset Q(l) is a A+ product with <A+ support of copies of the forcing -53- PF where conditions in PF are functions f with dom fas a subtree of 2 <A+ x 2 <A+ of size < A+ I\ and for f, g E PF f ~ g iff f 2 g. The conditions for PF look like this dom f Clearly IQ(l)I = A+ and Q( 1) is <A+ closed. Hence in particular V[GA,(F 1 : 1 <A+)] A is still inaccessible, GCH~A holds, and (A +ef m = A+e for e ~ 1. In the next step, the forcing Q( ) which we will simply call Q from now on will make a 2 E~ statement true about the F I for I even and a ll~ statement true for the F I with 1 odd. The E; statement about F I will say 3X s; A+ '<:/Y s; A+ F 1 (X,Y) is nonstationary. The ll~ statement will be the negation '<:/X s; A+ 3Y s; A+ F ,(X,Y) stationary. -54- For this note that ,\ + where ffi = (,\ +f; hence any X ~ ,\ + has a canonical code ffi E V ,\+ 2 = {S: S E P(,\) n L /1. 3a(S is the <-a-th subset of,\ /1. a E X)} and any L ffi E V ,\+ 2 codes {a < ,\ + : the f a-th constructible subset of,\ is E ffi}. The poset Q will be a suborder of Fn(,\ ++ ,2,,\). At many coordinates a < ,\ ++ we will simply add a subset of,\+; at many other a < 1 ++ we will add a club subset of ,\ + that is disjoint from F ,(S 1 ,S 2 ) where (S 1 , s 2 ) is some pair of subsets of,\+ associated with a if certain conditions are satisfied. First we partition ,\ ++ into cofinal pieces C, A 1 ( 1 < ,\ +) and B 1 ( 1 < ,\ +) such that ,\ + ~ C. Then for each 1 < ,\ + we pick an enumeration ( r !:( E A 1 ) of nice Fn( ,\ ++ ,2,,\ +) names for subsets of ,\ + and for each 1 < ,\ + an enumeration ((o-~' 1 ,o-~' 1 ) : ( E 'B') of pairs of nice Fn(,\ ++,2,,\ +) names for subsets of,\+ such that for any nice Fn(,\ ++ ,2,,\ +) name T for a subset of,\+ and any 1 < ,\ + there are cofinally many ( with T ~ subsets of ,\ +. complete. = T and similarly for pairs of nice Fn( ,\ + + ,2,,\ + ) names for In the sequel we will call such enumerations of tupels of nice names Note that complete enumerations of length ,\ ++ always exist since Fn(,\ +_+ ,2,,\ +) has the ,\ ++ c.c. and size ,\ ++. We now define the coordinates <a of Q by induction on a ~ ,\ ++ for a =0 -55- if a ::; >. ++ is a limit then and if a E C or a E A 1 ( some 1 < >. +) then and if a E B I for some 1 < >. + then where for ( E A 1 and similarly a-;'~ {77,f): 3g[(77,g) E u~' I\ f::; g /\ f E Qa]} and when the formula 0 is short for 1 is odd /\ [[ ,3 ( E A 1 n a (f- 1( = a- a1,1 I\ r ( = a- a2, 1 ) /\ 1,, 2,, (8- a 1,, 2,, ,a-a ) Edom F 1 /\ f(a) kills F 1 (8- a ,a-a )] V f(a) = O] .V. 1,, 1,, 2,, 1,, 2,, 1 1 is even/\ [[r = a- o: /\(a-a ,a-a ) Edom F 1 /\ f(a) kills F,(a- a ,a-a )] V [,3( EA 1 n a(f-(1 = 8-o:1,, /\ r ( = a-a2,, ) /\ (a-a1,, ,a-o:2,, ) Edom F 1 /\ 1,, 2,, /\ f(o:) kills F,(a- a ,a- o: )] V f(a) = O]. -56- Here f( denotes the subset of A+ that we add at coordinate (. Since compatibility in Fn( A++ ,2,A +) coincides with compatibility in the suborder Q, we get that Q has the A++ c.c. Moreover Q is <A closed because of the cofinality requirement that we put into the definition of the forcing for adding (F 1 : 'Y < A+). closed since for each 1 < A+ II V[G A] Q(l) "VX,Y ~ A+ F 1 (X,Y) is stationary" and, as we shall see, Q makes "many" of these sets nonstationary. that Q is <A+ Baire. However Q is not <A+ Lemma 4.1.3. will show To prepare the proof of this we need some technical lemmas which will also be helpful later. It is easy to modify the definition of the forcing Q(l) so that rather than add Lipshitz functions F : 2A + x 1 2A + --+ 2A + where 1 < A+ we add a sequence ((F 1 ,H 1 ): 'Y < A+) of pairs of Lipshitz functions with F 1 ,H 1 : 2 such that for all X, Y ~ A+ F 1 (X,Y). A+ x 2 A+ --+ It is a A+ product with <A+ support of a posets whose conditions are pairs (f,h) where f e- PF A his a function A <lorn h = <lorn f A V(s,t) E <lorn h [3a < A+ [a > <lorn s A h(s,t) E 2a+l A f(s,t) E 2a+l = 1] A {( : h(s,t)(() = 1 = f(s,t)(()} = 0 A {(:h(s,t)(() A+ H 1 (X,Y) is a club subset of A+ which is disjoint from We denote the modified poset by Q'(l) . A h(s,t)(a) 2 = 1} is closed] A V(s,t), (s 1,t 1) E <lorn h[(s,t) extends (s 1,t 1 ) ⇒ h(s,t) extends h(s',t')]. -57- 1 If (f,h) E Q (l) then f E Q(l) and conversely for any f E Q(l) there are h with 1 1 (f,h) E Q (l). Moreover if D is dense in Q(l) then {(f,h) E Q (l): f E D} is dense in Q 1(l)° Thus if ((F,, H,):, < ,\ +) is Q 1(1) generic over V[G ,\] then (F,:, < ,\ +) is now define the following poset ( ( ~ ,\ + +) Lemma 4.1.1. For each a ~,\ ++ Qi¥ is <..\ + closed. conditions in Qi¥. By induction on ( ~ a we will construct qi( such that Q( qi( E dom(ql() = LJ 77 <,\ dom(q 77 1() We check only the case of a successor as ordinal ( + 1. If ( E C or ( E A' for some ,\ < ,\ + there is no problem. Now assume that ( E B' for some , < ,\ + and for some Then take q(() = LJ 11<J.. (€domq,, q77(() LJ sup top 11<J.. (€domq 11 q,,(();i!O q 17 ( (). -58- We get that qi((+ 1) E Q(+l since (in any model) if for some X, Y ~ ..\+ H,(X,Y) is defined, then it is disjoint from F,(X,Y) and closed. By the same argument qi(( + 1) It E Q(+l' qi(( + 1) ::; q 11 1(( + 1) for all 11 < ..\ and dom qi(( + 1) is immediately clear that = U dom q 11 1(( + 1). 11<..\ □ end of 4.1.1 Lemma 4.1.2. For each a ::; ..\ ++ Qi is dense in Q 0 • Proof. We use induction on a ::; ..\ ++. For a = 0 this is true since Q = {O} = Q6 . For a successor ordinal a + 1 0 we examine only the case where a E B' for some , < ..\ + and we are given q E Q 0 + 1 with q(a) # 0. Since in any model H,(X,Y) is always unbounded (if defined) we can pick an ordinal 8 <..\+with 8> top q(a)and a condition q*::; q with q* E Qi (by using that Qi is dense in Q 0 ) such that q* II -- V[G ..\ ,(F, ,H, )] Qa 1,, 8 E H,( & 0 2,, ,& a ). Hence q* U {(a,q(a) U {8})} is a condition in Q* below q. If a is a limit ordinal a+l and q E: Q 0 there are two possibilities: If cf( a) ~ ..\ + then dom q is bounded in a and we can by induction hypothesis find a condition q * E Qi below q. If cf( a) ::; ..\ then we pick a normal sequence ( ..\ 11 : 11 ::; /3) with sup ..\ 11 = a and ..\ /3 = a and /3 = cf( a) 11</3 ::; ..\. Now using induction on 11 ::; /3 we define a decreasing sequence ( q 11 : 11 ::; /3) with -59- By 4.1.1. each Q* >.TJ is <>. + closed so the construction works at limit ordinals D end of 4.1.2. TJ ~ /3. Clearly q/3 E Qit and extends q. Lemma 4.1.3. For any a ~ >. ++ Qa is <>. + Baire. 61 di,; T ( , -+ Suppose the lemma was false for some a ~ >. ++. Proof. u( in V(G >.] Q(l) Pick names -+ A1 , B1 , C, for the parameters that we need in the definition of Qa and fix a condition f E Q(l) with ( 4.1.4) f II V[G ). ] -+ 0 "Qa(defined from A I -+ O , B I -+ O o I -+· o 1, / ) • 1s not <>. , C, T ( , u ( + Baire." Q(l) Pick some h such that (f,h) E Q(l)" Now let ((F 1 ,H 1 ):, < >. +) be Q(l) generic over -+ -+ V[G>.] and extending (f,h). In V[G>.,(F,,H,)] Qa has a<>. + closed, dense suborder, namely Qit. So in particular in V(G>. ,F ,] Qa is <>. + Baire, contradicting (4.1.4). D end of 4.1.3. As a corollary we get that for any a ~ >. + + 1,, 2,, Therefore in the definition of Qa+ 1 we can omit the clause ( & a ,& a ) E <lorn F I in the formula 0. Next we want to see that forcing with Q makes a E 2 2 or II statement about 3 3 F I true depending on whether I is even or odd. We must first prove a technical fact which will be used again later. -60- Lemma 4.1.5. For any condition q E Q and any ordinal 8 < ,\ + there is a stronger condition q 1 E Q with 'v 1 < ,\ + 'v /3 E B 1 [q(/3) -:f. 0 => top q 1(/3) > 8]. Proof. Suppose this was false. o -o o Pick names C, B I , A I and C: 1 o'l, 1 o'2, 1 T ( , <J' ( , <J' ( m Q V[G ,\] (l) and a condition f E Q(l) with (4.1.6.) 0 0 V[G] ---+ -O ---+ . no q ' E Q ( C, O 2,"'f f II Q ,\ "there 1s A I ,B I , TO (I ,<J'O (1,'Y ,<J' ( ) (1) => top q 1(/3) > 8);" pick some ((F 1 ,H 1 ): 1 h with (f,h) a in the < ,\ +) be Q(h generic over V[G ,\]. (o:'f/:'T/ < X) ofdom q where IXI for,,, < X for 'f/ condition = 0 let q'T/ = 0. = ,\. modified poset Q(l). Now let Choose an increasing enumeration -61- < q 111 'r/11 1 < 1J. This 1s If 1J is a limit pick a condition qT/ E Q~T/ with qT/ possible since Q~T/ is <A+ closed. For successor 1J + l we examine only the case that a 11 E B I for some ; < A+ and q(a 11 ) =j:. 0. Similarly as in the successor case of the proof of 4.1.2., we can find 1 > 8 and a condition q* ~ qT/, qlaTJ+l in Q~TJ+l such that top q*(a 77 ) some ordinal 8 = 81• Define this to be qTJ+l. Once the sequence ( qT/ : 1J < A) has been defined one can find a condition q 1 E Q* with the property that we want by either using the <A+ closure + sup1J<5.a1J Q* + of or repeating the argument for the successor case m the inductive sup 7J<.>. a 11 construction of the sequence above depending on whether dom q has a last element or not. In particular q 1 E Q, so we get a contradiction with (4.1.6). □ end of 4.1.5. Next we want to see that after forcing with Q any F 1 (X,Y) 1s stationary ( for X, Y ~ A+) unless we kill it explicitly. To be more exact: Lemma 4.1.7. --+ --+ + Let G be a Q generic over V[GA ,F ,]. In V[GA,F 1 ,G) let X, Y ~ A and 10 < A+ and assume 'r//3 EB iO 1,,o G 2,,o G 'r/q E G[q(/3) =j:. 0 => ((a- /3 ) , (& /3 ) ) =j:. (X,Y)]. Then F 10 (X,Y) is stationary. 0 --+ 0 --+ 0 1 1 Pl. ck names C , A , B , definition of Q. r;., ~ ;' 1n V[G A]Q(l) 1or the paramet ers m the --+ --+· 0 .,, v .,, .c -62- Let o- 1 , o- 2 , o- E V[G Al Q(l)*Q --+ and (f ,q) E F 1 * G with I\ o- is club in A+." In order to finish the proof we have to find a condition (f,q) < (f ,q) and s 1 , s 2 E 2<A + and an ordinal a < A+ such that V[G Al 1 2 1 2 (f,q) liq *Q "(o- ,o- )extends (s ,s) /\ a E o-." (1) In order to come up with (f,q) and (s 1 ,s 2 ) and a we have to define a decreasing sequence ((f77 ,q 77 ): 1J < A) of conditions below (f ,q) and auxiliary sequences -63- + 'Y ++ and s i ' 'Y s 1. C_ .A + and at stage 'T/ where 8'T/'Y , a'T/ < A+ and T'T/ C - .A and b 'T/ C - A /3,'T/' 'T/ of the construction we have > sup <lorn 11'<11 (s,t) fdomf'Y, 11 'Yf u suppf, f',(s,t) U 'T/ sup(a 11'<11 'T/ I U 8 1) 'T/ 11 11'<11 o, n u <lorn q , =I= 0} u bo} T,,, = {,<A + : B f,,, 11 V[G.A]{ Q(l) o V, E T'T/ b~ B' 'TJ'<'TJ 'T/ n LJ <lorn q 1 ,,,, <'TJ 'T/ (i = 1, 2) V/3 E b 'Yo [3'TJ' < 'T/ q (/3) =/= 0 ⇒ (/,'Yo s2,,o) =/= (s 1 s2 )] 'T/ ,,,, /3,'T/ ' /3,'T/ 'T/' 'T/ V, E T'T/ V/3 E b~[3'T/ 1 < 'T/ q 1(/3) =/= 0 ⇒ top q'T/(/3) > 8,,,]. 'T/ We construct the sequences by induction on 'T/ < A. If we have arrived at stage 'T/ < A and all requirements hold at the earlier stages of the construction we proceed as follows: Since Q(l) * Q is <A closed there is a condition (f* ,q*) ~ (f,q) which extends all (f , ,q , ) for ,,,, < 'T/· 'T/ 'T/ (b~:, E T'T/) with LJ <lorn q , and Now pick f** ~ f* and T'T/ ~ 'T/ ,,,, <'T/ -64- - q 1 =fa 0} U {, = {, < .X + : Bo, n u dom T 17 f** II V[G .X ] { Q(l) Then pick ordinals 17 <11 n dom q 1 • ,,,, <11 17 LJ \/ 1 E T 17 bJ B' < A+ and 817 < A+ a 17 0 } 17 I and sets i, 'Y s/3 '17 ' s~ C .X + (for = 1,2) and a condition (f*** ,q**) :S: (f** ,q*) such that 1 E T 17 ,(3 E bJ ,i 8 17 > sup dom f**,'Y (s,t)Edomf** ' 'Y 1 E suppf** (s,t) U sup (a I U 8 1 ) ,,,, <11 17 17 oi,, rr/3 (f***,q**) 11 v[G.xJ Q (1)* Q <, n u17 =sf3,1l i,, ('1=1,2, (3 E b' ,,ET ) 77 77 in 017 , C (i = 1,2) = S17i \/ (3 E bJ [377 < 77 q 17 1((3) =fa O ⇒ (s/3', 17' ,s (3': ) =fa (s~ ,sij)]. ,., 0 1 1 0 2 0 Note that all this can be done since Q(l) * Q is <-X + Baire. Finally (using 4.1.5.) we pick (f17 ,q 17 ) :S: (f*** ,q**) such that This completes the definition of the sequences. Now let a ~ sup a 17 and pick a condition f E Q(l) that extends all f 17 for 11< .X 17 < A such that for all I E LJ n<.X ·, T 17 and all (3 E U b~ 11<>. -yeT 17 21 1 1 (s/3' ' ,s (3' ) E dom f where -65- si,, = fJ LJ C'.I)f 77<>. si,, (i = 1,2) and (s 1 ,s 2 ) E dom f 10 where si a;=f (J,77 1,, 2,,)( f ,( sf] , sf] .Ii LJ s~(i = 1, 2) and 77<>. sup 11<>. f3 f. dom q 11 Q11(/3);t0 Note that if 377 < >. q 77 (f3) =/= 0 then there is no conflict here. We also define q by dom q = LJ <lorn q 77 C'.I)f 77< >. LJ 77 <).. q 77 ((J) U { sup 11<>. q 11 (/3);t0 top q 77 ((J)} if fJ E LJ bJ and q 77 ({J) =/= 0 11<>. -yf.T 11 for some 77 < >. otherwise. " Then ( f,q) is a condition in Q(l) * Q below (f ,q) and (s 1 ,s 2 ) and a have the □ end of 4.1.7. properties that we want. Corollary 4.1.8. For odd 1 < >. + ---+ II V[G~,F,] VX ~ ;..+ 3Y ~ ;..+ F,(X,Y) is stationary. Proof. Let G be Q generic over V[G >. ,F 1 ] and X C >. +. _G X (note that (rr( E A 1 ) is complete). TO:' Pick some a E A I with We claim that F ,(X,Ga) 1s -66- stationary in V[G ,\ ,F 1 ,G] where Ga is the set ~,\ + that G adds at coordinate a. If q E G, then for all /3 E B' generic over V[G ,\ implies ( n a ( a}' )G -:p Ga since by the product lemma Ga is ,F, ,G n Qal• For all /3 E B' with /3 > a we get that q(,8) -=p 0 a}' ,a}') -:p u· l ,Ga) by the definition of Q ,8 + l. Hence by 4.1.7. □ end of 4.1.8. F ,(X,Ga) is stationary. Lemma 4.1.9. For even 1 < ,\ + --+ V[G,\,F ,] + + II Q 3X ~ ,\ VY ~ ,\ F ,(X,Y) is nonstationary. Proof 4.1.9. VY~ ,\ + --+ Let G be a Q generic over V[G,\ ,F ,]. --+ We claim that in V[G,\ ,F 1 ,G] F,(G' ,Y) is dead. Let Y ~ ,\+and pick /3 EB' with (o-1'')G = G' and (o-~'')G = Y. Since I is even, at coordinate ,8 we add a club subset of,\+ disjoint □ end of 4.1.9. from F,(G' ,Y). --+ Now let G be Q generic over V[G,\ ,F ,]. The next step in our 4-step iteration will add a code S, ~,\for each F,('Y < ,\+). Recall that 2 <-'+ is the same whether --+ computed in V[G ,\ ,F, ,G] or in V[G ,\]. But V[G ,\] is just L[G ,\] since we started out in V = L. Moreover G,\ ~ P,\ ~ L,\; hence 2< ,\+ ~ L +[G,\] and has order type,\ + ,\ under the canonical wellordering <L[G ,\]" Thus each F, has a code F, ~ ,\ + -67- with Fi E V[G,\,Fi]. Now let Q( ) be the,\+ product with<,\ support of the posets 3 (QF : i < ,\) where for each i < ,\ + the poset QF i adds a code Si C ,\ for the set i F,., C ,\ + via the <L least almost disjoint family of size ,\ + of constructible subsets of,\, I - Note that ,\ + - = (,\ +f and ,\ 1s inaccessible and GCH~,\ holds m V[G ,\,Fi ,G]. Thus as m the o-il1ri case each QF is ,\ centered and <,\ closed. Hence by a ~ i system argument Q( ) has the property ,\ + and is <,\ closed. Therefore in particular 3 Q( ) x Q( ) is ,\ + c.c. and does not add any new subsets of ,\ + all of whose initial 3 3 - - - segments are in V[G ,\,Fi ,G]. Thus in V[G ,\,Fi ,G,S i] we have: (4.1.10.) X, Y E A, .At, F ",\ + = (,\ +f A if F ~ ,\ + is the set coded by Si ~ ,\ via the < least constructible family of size ,\ + of almost disjoint subsets of,\ and if F is L the Lipshitz function with dom F F(X,Y) is not stationary"] for even i < ,\ + and = {(U ,V) E 2,\ + x 2,\ + : Va < ,\ + -68- VX ~ A+ 3Y ~ A+ V .Al, [A trans, .Al, F ZF-, IAI = IV A+ll, AA ~ A, (4.1.11.) X, YE A/\ AF "A+= (A+f /\Va< A+ X n a E L[GA]" . ⇒ . .Al, F " if F ~ A+ is the set coded by S, ~ A via the f least constructible family of size A+ of almost disjoint subsets of A and if F is the Lipshitz function with and rng F ~ {W E 2 A+ F using <L[GA] on 2<A + W n a E L[G A]} that is coded by : Va < A + then (X,Y) E <lorn F and F(X,Y) is stationary."] for odd , < A+ . Now the final step Q( ) in our 4-step iteration will be a A+ product with <A 4 support of posets (Q(4 ):, < A+) each of which adds a club set C, ~ A such that 2 C, n {µ<A:µ inaccessible Vµ F where~ L'23 denotes the E 2 3 3 ~E ( s,n Vµ, GA n Vµ, Anµ)}= 0 formula in (4.1.10). Note that for each, < A + IQ(4 )1 = A and fo~ each 6 < A, Q(4 ) has a dense suborder that is 6 closed. Therefore Q( 4 ) has the property A+ and for each 6 < A has a dense suborder that is 6 closed. So in particular Q( ) x Q( ) has the A+ c.c. and does not add any new subsets of A+ all of 4 4 --+--+ --+ --+--+ whose initial segments are in V[GA,F,,G,S,]. Hence in V[GA,F,,G,S,,C,] we still have (4.1.10.) and (4.1.11.). This completes the definition of the certain 4-step -69- iteration that we want to do at stage A. Clearly for even , < A+ 2 where <I>.!7 3 1s as in ( 4.1.10). The rest of the clauses in the definition of the iteration P IC+ 1 are as in Section 1. Note that as in Section 1: II Vo "the tail PA+l,1C+l has a< a closed dense suborder for each a<µ" PA*QA whereµ is the least inaccessible >A. Thus II V PIC+l "there are no E 2 indescribables <IC." 3 As a minor technical point one might wonder how we can uniformly (in A ~ IC) pick the parameters that one needs to define the second step of the four-step iteration at stage A. ---+ For this note that when we arrive at this step we are working in L[G A ,F 1 ] where ---+ F I is V[G A] genetic for the first step at stage A, < Thus we can simply pick the least family of parameters to define the poset at the second step. ---+ L[GA,F,] 4.2. Preservation of the 11~ Indescribability of IC in V p IC+ 1 The aim of this section is to prove "Pv1 "1C is 11~ indescribable." -70- Assume towards a contradiction <I>( A) is JI; and A E V p IC+ 1 is a name for a subset of VIC and p E P IC+l with 0 PII p "<I>(A) describes IC." IC+l We pick an ordinal 8> the least inaccessible above IC such that V 8 F "ZF- /\ P l ~ IC+l 0 <I>(A) describes IC." Note in particular P IC+ 1 find a transitive M with IMI V5 P 1C+l E V 8 . By using standard arguments we can = IC and M<IC C M and an elementary embedding i: M p and i( is JI: indescribable in V we can find transitive N with INI Mo A) o = A. Since IC = IC+ and NIC ~ N which is E~ correct for IC and an elementary embedding j: M --+ N with cpt j = IC. In order to finish the proof we have to come up with a V generic VG for P IC+ 1 with p E VG an M generic MG for Mp 1C+l and an N generic NG for Npj(1C)+l such that i lifts and j lifts and N[NG] is I:~ correct for IC inside V[V G]. Then we get a contradiction as outlined in Section 1. Constructing MG and VG. Note that P~ = PIC since M<IC ~ Min V. So we pick a V generic GIC for PIC with pj1C E GIC and i lifts, since clearly i(p) = p for p E PIC. -71- M In the next step we consider Q(l) * Q. Let (Da: a < 11:) E V 8 [G11:] be an enumeration of all sets E M[G11:] which are dense in MQ(l) * MQ. Below any condition (Mr°,Mq) that (Mf77 ,Mq 77 ) E D 77 (for 77 < 11:) and there is a condition (f,q) extending all (f77 ,q 77 ) in Q(l) * Q where f 77 = i(Mf77 ) and q 77 = i(Mq 77 ). The construction of this sequence takes place in V[ G 11:J but any initial piece of it is an element of M [G 11:J since this is < 1,, closed inside V[G11:] because P,,, is 11: c.c. At stage 77 of this construction we pick MT 77 MT77 = {, < ,,,+:M1P n u <lorn Mq '=I= 0} 1J 1<1J \:/-y E MT77 bJ = MiP 1J n LJ <lorn Mq 77' < 1J 1 1J -72- and /3 E bJ with dam Mf1 1(s,t) T/ u and Once the sequence ((Mfr, ,Mqr,): 'TJ < ,c) has been defined we use the elementarity of i:M[G,-]--+ v 8 [G,-] to see that there is a condition (f,q) below all the (f7J,q'TJ) for 'TJ < ,c. Let MF,* MG denote the filter generated by ((Mf7J,Mq'TJ):7J < ,c). Clearly MF 1 * MG is M[G,-] generic for MQ(l) * MQ. - Q(l) *_ Q with (f,q) E F 1 * G. Then i lifts; i.e., M Pick any V[G,-] generic F 1 * G for -73- For the last two steps of the 4-step iteration at stage 1,, where we code the Lipshitz functions by subsets of 1,, and then add the club sets ~ 1,, note that both posets are 1,, + c.c. Hence the pullback method works because cpt(i) = (1,, +)M > 1,,. So we have found an M generic MG for Mp 1,,+l and a V generic VG for P 1,,+l with M[MG] --+ i PM ,,,+1 M V8[VG] p K+l --+ 1 v8 . Construction of NG. Note that Np,,, j(p) = j(P,,,) n V,,, = P,,,, since P,,, ~ V,,, and cpt j = "'· In particular = p for all p E P,.,. Thus if G is any N[G,.,] generic for the tail Np K,J"() then j K, will lift; i.e. M[G,,,] --+ j Np j(1,,) P,,, M N[G,,,*G] --+ j N. We also want to choose G in such a way that N[G,., * G] remams E inside V[V G]. First we note 2 2 correct for 1,, -74- Lemma 4.2.1. N[G11:] is E~ correct for 11: in V[G11:]. Proof. Recall that P 11: C V 11: and is 11: c.c. The proof is very similar to the proof of D II.1.1. end of 4.2.1. The 11: c.c. of P 11: implies that N[G11:] is closed under 11: sequences inside V[G11:]- Thus N Q(l) (the poset at the first step of stage 11: of N Pj(11:)) equals Q(l) (the poset at the first step of stage 11: of P 11: + 1 ). In the ground model V = L we pick the < least L permutation II of 11: + such that 1:1 Even 11: + - Even ( 11: + ) M II: Even11: + --+ onto Odd 11: + ..!J Odd 11: + U Even (11: +)M . onto Now let NF, = F II(,) for,< 11: +. Clearly NF, is Q(l) generic over N[G11:l• Lemma 4.2.2. N[G.x ,NF,] is E~ correct for 11: inside V[G11: ,F ,]. Proof. Note that N[G11:, ~ F ,] = N[G11: ,F- ,] and that IQ(l)I = 11: + . Thus Q(l) can be coded by a subset of V 11:+l. Moreover Q(l) is <11: + closed; thus II Q(l) Now the proof of the lemma is a routine matter. V k+l = D end of 4.2.2. -75- The correctness argument for the next step involving the poset Q will require a lot more work. For this we need two more technical facts about Q. The first one will say that different choices of parameters all lead to isomorphic posets Q. We begin with a criterion which guarantees that we obtain a condition in Q, when we thin out certain coordinates of a given condition in Q. Definition 4.2.3. Fix a family of parameters to define the poset Q. A set S C 1,, ++ is said to be complete ( relative to these parameters) if for all 1 < 1,, + V( EA I n S V(17,h) E r ( (dom h ~ ( ⇒ dom h ~ S) V( E B 1 n S 'v'(17,h) E a-~ 1 (dom h ~ ( ⇒ dom h ~ S) (i = 1, 2) Definition 4.2.4. Given a fixed family of parameters and S ~ 1,, ++ define QS { q E Q : dom q ~ S) and for each ( < 1,, ++ and fof r < "'+ and ( E Ar 8 1} = {(17,h): 3f((17,f) E r ( /\ h ~ f /\ h E Q~)} and similarly for ( E Br and a-~ 1 (i = 1, 2). If it is clear from the context we will drop the letter S and simply write, for instance, r ( . -76- Lemma 4.2.5. Suppose S ~ 1,, Then for each ( ~ 1,, ++ is complete relative to a fixed family of parameters. ++ and all q E Q( qJS E Q( and Proof. We proceed by induction on (. claim of the lemma. The cases ( = 0 and ( a limit ordinal are clear. To prove the first claim for a successor ~ + 1 < 1,, + ( E dom q and ( E B' Note that the first claim implies the second + and a condition q E Q( + 1 we can assume n S for some 1 < "'+. Suppose towards a contradiction that qJS ~ Q~ +l. Then there is a condition q' E Q~ with q' ~ qJS and This is true since the completeness of S implies that for any H which is Q( generic over HnQS V[G,,,,F,] u·i)H =(fi) · ( for all T/ EA' n sn ( and similarly for 11,'(i = 1, 2). Moreover for TJ EA' n ( ((o-~'')H,(a-~'')H) = ((f-i)H,HT/) implies TJ ES. - If we define q" E Q( by q" J(S n () = q' q" I(( - S) = qj(( - S) then with the remarks above -77- □ end of 4.2.5. which contradicts q E Q( +l. two families of parameters and Q and Q be the corresponding posets. We will define a sequence of functions ( e( :( < K ++) such that 1/ E A r n ((B r n ( resp., C n ( resp.) ¢::::> e((TJ) E -r -r A (B resp., C resp.); let e 0 .?= 0 and for a limit ( < K ++ let e( = LJ eT/ • TJ<( If we arrive at a successor ( (for some r < K +) fix + 1 and ( ~ dom e( there are three cases: For ( E A 'Y the minimal 1/ E A:7 with 1/ ~ sup + rng e( and -78- note that ( ~ dom e() and let e( + 1 ( () minimal 77 E Br with 1J e(+l (()=77. = 77. For ( E Br (for some r < 11: +) fix the ~ sup+ rng e( and a'"~r - (a-~r t( (i = 1, 2) and let For ( EC fix the minimal TJ EC with Tf > sup+rng e( and let If ( ¢ rng e( U {77}, then again there are ( cases: -r (for some For ( E A . e :-1 r <,.+)fix the minimal e ~sup+ <lorn e( .u. ( + 1 with T~r = (i=",r) (, For ( E 13r (for some I < K +) fix the minimal e ~ sup+ <lorn e( .u. ( + 1 with a-:t . (-&-( 7 ) -1 e( (i = 1, 2) . For ( E C fix the minimal t, E C with t, ~ sup+ dame( .u. ( Note that all this is possible since the sequences of terms and pairs of terms are complete. Lemma 4.2.6. For each ( with 11: + ~ ( < K. ++ dom e( ~ K ++ is complete (rel. to the paramaters for Q) and rng e( ~ 11: ++ is complete (rel. to the parameters for -Q). Proof. This is immediate from the definition of the sequence (e(: ( < K. ++). D end of 4.2.6. - 79- Lemma 4.2.7. For any ( < "'++ e q ( E Q and rnge dome ( for all q E Q ( e- 1 dome _rnge( q ( E Q ( for all q E Q dome( _rnge( dome( Thus e( induces an isomorphism of Q with Q . Moreover, if H is Q generic and H V1<K + w v 1 <K = {qe( :q E H} 'r/11 E A I n dome( (rZ)H = c~z((v))H + wvll E B'i' n d om e( (_i,'i')H )H u 11 = (~i,1 u e((v) . Proof. The case ( = 0 is clear. Now we suppose are considering dome(+l q E Q . We can assume ( ~ + 1,, • a successor ( + 1 < "'++ and The worst case that can happen is that we have to add first ( to the domain of e( and then ( to the range of this function in order to get e( + 1 from e(: clearly dom e( U {e} is complete relative to the parameters of Q. dome( U {e} qj(dome( U {e}) E Q Hence by 4.2.5. -80- Proof of Claim 1- It suffices to show -, for some , < x: + and ( E <lorn q. Let -H( be -Q( generic with We can assume ( E B _ rng e ( _ _ Pick a Q generic H with H Then H = {f E Q G_Df <lorn e( _ _ n Q( = H( and (qjdom e() e( _ E H. e( dome( :f E H} is Q generic and qjdom e( E H. Thus we - get in V[Gx: ,F, ,H]: dome( U {e} because qj(dom e( U {0) E Q - This yields in V[Gx: ,F, ,HJ Since#~' ~ x: + x Q( this is equivalent to . □ end of proof of claim 1. Claim 1- q e( +l _rnge( +l E Q . -81- -'Y Proof of the Claim£· We can assume that 'f} E B We know already from claim 1 that q e(+l dome( Q e( :f E H H n Q _rnge( nQ + and q e(+l ('fJ) =/:- 0. Now let H be Q'f} generic with l7J E Q'f}. _rnge( By 4.2.6. for some 1 < 1,, rnge( Q lS generic. Then H ~ {f E dome( } is Q generic and qJdom e( E H. The completeness of <lorn e( U { (} relative to the parameters of Q yields qJ( dam e( U { (}) dome,u{(} -+ E Q . Thus in V[G,_ ,F 1 ,HJ Since o-~ 1 ~ K + x Q( this is equivalent to -+ - Therefore we obtain in V[G,. ,F 1 ,HJ -c 'f} )) • 0(H , 1 , ((.::...'Y)H rv : v E -A, n rng e ( ) , (.::...1,'Y)H <T 'fJ , c-2,'Y)H <T 'fJ , F 1 ,q The completeness of rng e( U {'fJ} relative to the parameter for Q yields □ end of proof of claim 2. _rnge(+l A similar argument shows that for q E Q -1 q e(+i d ome(+l E Q · -82- Finally it is immediate from the definition of e( + 1 that the the part of the lemma about the terms holds and in fact we have already used this in the proofs of the claims above. Now suppose ( is a limit ordinal <1,, qldom ev E Qdomev by 4.2.6. -Qrngev . ++ and let q E Q dome( For each v < ( Thus by induction hypothesis (qldom ev)ev E N ow one can use m . d uct1on . on v < 1,, ++ to s h ow t h at q e(I v E -Q v . At a successor v + 1 < 1,, ++ with v E B' for some; < "'+ and / ( (v) =/= 0 pick some l < ( with v Edom (qldom ee)ee ee) ee e( Iv, we get q Iv I ~ 0. that for q E Q Qv rnge( e/ q Then (qldom ee)eelv II Qv 0. Since qe(lv ~ (qldom e Hence q (Iv+ 1 E Qv+l · A similar argument shows dome( E Q The rest of the lemma is immediate for a limit ordinal(. D end of4.2.7. Corollary 4.2.8. Up to isomorphism there is only one 1,, ++ iteration Q in V[G,,, ,F ,] that uses (F 1 : ; < 1,, +), D end of 4.2.8. The second technical result about Q illustrates that for any coordinate ( < 1,, + + , if we consider the tail Q (,1,, + + of the poset Q inside V[G,,, ,F ,] Q(, then this looks pretty much like the original poset modulo a minor modification. -83- Before we can prove this we need to set up some notation. Suppose that in V[ G,. ,F 1 ] we pick a family of parameters to define a x: + + iteration Q. If 8 < x: + + -+ -+ and H 8 is Q 8 generic over V[G,. ,F ,], in V[G,. ,F 1 ,H 8 ], let: o -+ Pick a canonical name Qb,( E (V[G,. ,F ,] x: ++ Q8 for Qb,( . For each q E Q((8 < ( < o -+ Q8 ) pick a term qb,( E V[G,. ,F ,] with Lemma 4.2.9. For each ( with 8 ~ ( ~ x: ++ 0 defines an isomorphism of Q( with a dense suborder of Q 8 * Qb,(. □ end of 4.2.9. Next we associate with each nice Fn(x: ++,2,x: +)namer for a subset of x: + a canonical -+ name 8 r E V[G,. ,F ,] (4.2.10.) Q8 such that II Qb 8 r = {(77,h): 1J < x: +, h E Fn([8,x: ++),2,x: +) /\ -3f E f:lg E Fn (8,2,,-+)[(17,g-h) Er I\ f~ g]}. -84- Note that I ~ " 8 r is a nice Fn((8,x: ++),2,x: +) name for a subset of x: + ." 8 , Lemma 4.2.11. For any complete sequence (r(:( < x:++) of nice Fn(x:++,2,x:+) names for subsets of x: +. II Q "( 8 r (: ( < x: ++) is a complete sequence of nice Fn((8,x: ++),2,x: +) 8 names for subsets of x: + ." Proof. - - Let H be Q 8 generic over V(Gx: ,F ,] and in V(Gx: ,F 1 ,H] let Fn((8,x: ++),2,x: +) name for a subset of x: +. with 3-H = <7' <7' be a nice We pick q E H and 3- E V(Gx: ,F ,] Q 8 and "3- is a nice Fn((8,x: ++),2,x: +) name for a subset of x: + ." qll Q 8 Now define a nice Fn(x: ++ ,2,x: +) name for a subset of x: + T E V(Gx: ,F ,] via hl6 II Q8 (11,hl(6,x: ++)) E 3-}. From ( 4.2.10) we obtain qll Q6 6T = 3-. The completeness of ( T ( : ( < x: ++) in V(Gx: ,F ,] yields that there are arbitrarily large ( < x: ++ with r ( = r. Obviously we have for any such ( □ end of 4.2.11. -85- In the sequel we will not always distinguish between 6r (which is a name for a term) its and interpretation (which IS an element of 6 ++ 2 + (V[GIC ,F ,H])Fn([ ,IC ), ,1C )) unless there is reasonable danger of confusing these 1 two objects. We are now going to define what we mean by a modified 6, IC++ iteration. Suppose that m V[GIC,F 1 ] we have a partition of 6 < IC++ into A 1 ( 1 < IC+), B 1 ( 1 < IC+) and C with IC+ ~ C and for each ( E A 1 ( 1 < 11: +) and T/ E B 1 ( 1 < IC+) . Fn ( IC ++ ,2,IC ) names r (, I r,T/l,1 , r,T/2,1 1or C we h ave mce su b sets o f IC + . - Now let H be V[GIC ,F 1 ] generic for the iteration Q 8 defined from the parameters. -1 A (1 Suppose that in V[GIC ,F 1 ,H] we partition [6,IC ++) into cofinal pieces , - 1 1, 2, 1 < IC + ), -1 Band C and we have sequences (r(:( EA) and ((if( 1 ,if( ):( E B 1 ) that are, for each 1 < IC+, complete for Fn([6,1C ++),2,IC +). V[GIC ,F 1 ,H] we define the 1 1 (-B 1 : I - < IC +) , -C , (T ( : ( E A ,I and for limit a modified 6, IC++ iteration Working in Q((A 1 : 1 < IC+), 2 < IC +) , ((-<, 1( ' 1 ,<r - ( '')) ( E B1 )) by induction on a -86- Q 8 = {f E Fn([8,a),2,IC + ) : V /3 E [8,a) fJ(b,/3) E Q- 8' /3} ,a ~f for a E -, A or -C for some , < IC + : - +l = {f E Fn([8,a+l),2,IC + ):fJ[8,a) E Q, - } Q, u,a ~f u,a and for a E B' for , < IC+ Q.u,a +l ~f = {f E Fn([8,a+l),2,1C +) :fJ[8,a) E Q.u,a /\ fJ[8,a) 11 Q- 0} 8,a where the formula 0 says: ..2... 2a ,,) I\ f( a ) 1s · a con d"t· ..2... 2a '')] V f( a ) (..2...l,, 17 a ,17 1 10n ~1or k"ll" 1 1ng F , (..2...l,, 17 a ,17 = OJ .V. -, where for 'T/ E A and similarly for :F~'. By an analogous proof as in 4.1.3. one can show that modified 8, IC++ iterations are <1C + Baire. Moreover the analogue of 4.2.7. shows that up to isomorphism there is only one 8, IC++ iteration in V[GIC ,F, H] (that is modified by -87- (F 1 : 1 < 1,, +)) • F or any 1,, ++ 1terat1on . . Q .m V[G ,,, ,--.F 'Y ] d efime d f rom parameters H that is Q 8 generic over V[G,- ,F 1 ] there is a canonical 8, - V[G,- ,F 1 ,H] whose parameters arise from the parameters for Q. 1,, ++ iteration Q in For this recall that are complete in V[G,,, ,F 1 ,H] for Fn([8,,- ++),2,,- +). The following lemma shows that at any intermediate stage 8 < 1,, ++ Q factors in a nice way. - ,H] we have for each ( E [8,,- ++ ] Lemma 4.2.12. In V[G,,, ,F 1 Proof. We proceed by induction on 8 ~ ( ~ ,- ++. If ( If ( = 8 then note ~ ,- + + is a limit ordinal we distinguish two cases: If cf ( () ~ ,- + the claim follows from the induction hypothesis since all conditions have size ~'-, so we can assume cf(() ~ 1-. Clearly Qf( ~ Q8,(. Now we suppose q E Q8,(. Then we pick S ~ [8,() cofinal in ( with ISi ~ 1,,. For each v E S there is hv E H with hv U qlv E Qv. - 1 ] by the <1- + Baireness of Q 8 . Thus Note that the sequence (hv:v ES) E V[G,,,,F Vv E S hv E r. we can pick h E H with hi! Q 8 -88- Proof of the Claim. v Show by induction on v that for 8 ~ v ~ ( h-qjv E Qv. = 8 this is clear and also the case of v being a limit ordinal is immediate. If Now consider a successor v + 1. We can assume v E B' for some , < "'+ and v E <lorn q. Suppose towards a contradiction that we don't have h-qjv I~ 0. condition f E Qµ with f ~ h-qjv and fll Qv -, 0. Since hll Q 8 So there is a Let µ be the least ordinal >v in S. hµ E r and fj8 ~ h, we can find g E Q 8 extending both hµ and fj8. Now a contradiction since f ~ h-qjv. □ end of proof of claim The claim yields q E Qr,(. Finally consider the case of a successor ( + 1 < "'++. Note that by induction hypothesis Qr,( = Q8,(. We will need the following: Fact. _If K is Qr,( generic over V(GK, ,F, ,H] then for each , < "'+ and v E A, n [8,(] where <1> 8 is as in 4.2.9. and similarly for a-~' (v E B' n [8,(]). -89- t E Fn([8,,c ++),2,,c +) with t ~ h and (77,t) E ( -rZ)H. 8 Then pick f" E H and g E Fn(8,2,,c+) with -r'' ~ g and (77,g-t) E rZ. Choose -r'" E H such that f"'-h E Qv and let f' E H be a common extension of f"' and -r''. Now (77,-r'-h) E rZ since <I>- 1 [H*K] -r'-h E Qv and -r'-h ~ g-t. Clearly <1> 8 (-r'-h) EH* K. Thus 7J E (rZ) 8 r <I>-l[H*K] Conversely assume 77 E (rv) 8 ; then fix f E H and h E K with rh E Qv and □ end or the proof of the fact Now we proceed with the successor case and consider q E Qr,( +l. We pick h E H with h-q E Q( +l. We can assume ( E <lorn q and ( E Br for some r we obtain The fact yields that Hence q E Q«5,(+l · < ,c +. Then -90- Conversely if q E Q8 ,( +l we can assume ( E <lorn q and ( E B' for some 1 < IC+. 0 Now we pick h E H with h-ql( E Q( and hll Q.5 q E -+ V[G1C,F,] Q8 0 Q8,( +l, where Q8,( +l E -+ is a canonical name for the poset Q.5,(+l E V[G1C,F,,H] that we defined above. Now we have V[G "qi( II -+ F IC~ ,, 0 H] Q8,( -+ 0 where H is a canonical name E (V[GIC ,F ,]) 0 Q.5 0 for the Q 8 generic H and K is a Q 8 0 name for the canonical Q.5,( name for the Q.5,( generic. By applying the fact we get OH □ Thus h-q E Q(+l and therefore q E Q8,(+l · end of4.2.12 We are also going to use the following specialization of this: Suppose that in V[GIC ,F ,] we have defined a IC++ iterationQ such that for some 8 < IC++: (4.2.13.) v, < IC+ v, EA, n 8 supp r; n Even IC + ) M = 0 '> supp ( u~' n Even IC + ) M = 0 '> ( -91- -+ where for r E V[GIC ,F rl Fn(1C++,2,1C+) we define supp r ~ U{dom h:3u (u,h) Er}. A similar argument as m the proof of 4.2.5. shows that for each q +M b-Even ql(b - Even + M) E Q 0 (IC ) (IC ( o-(l,r )H -:/= Hr for any r E Even -+ The key point is that for any Q 0 generic H + M and ( E Br (IC ) n b since supp &(l,r ~ ( - Even (IC + )M. b-Even N ow suppose H .rs ~c Q . 0 (IC ) 0 ) +M b-Even Therefore Q E Q0 Q~u +M (IC ) . over generic -+ V[G1C,Frl- Then in V[G1C,Fr,Hl let where ( ~ 0 and h o q E Fn(b + (,2,IC +) is defined as follows: h o q(11) h o q(11) = q(b + e) if II is thee-th ordinal E Even (IC + ) M ~f = h(11) if ~f II E b - Even + M (IC ) be a canonical name for We let *Q + M b,b+(IC ) +( and for each q E Qb+( we pick a canonical name *q b-Even -+ E V[G1C ,F rl Qb +M (IC ) such that + M b,b+(IC ) +( -92- qlEven where for g E (11: + M ;:::ql[8,8 + () ) Fn(Even (11: + M, 2, 11: +) ) = *q and 8,8+ h M E (11: + )+( ]] Fn([8,8+(),2,11: +) we define g;:::h E Fn([8,8+(11: +)M + (), 2,11: +) by g;:::h (8 + v) ;ff g(e) where -.i1f eis the v-th element of Even (K + ) M and As in 4.2.9 we have that defines a dense embedding. - - Working inside V[G11: ,F 1 ,H] we are now going to define what we mean by a special modified 8, K ++ iteration *Q ++. This is very similar to a modified 8, 11: ++ 8,11: iteration except that at the first M(11: +) many coordinates ~8 we have to add subsets of 11: + such that: If I is the e-th even ordinal < (11: +)M then the set ~ 11: + that we add at coordinate 8 + e will be a witness for the E~ statement that we want to hold -93- about F1 . In analogy with + Fn(11: (4.2.10.) we will also associate with each -+ -+ + ,2,11: +) namer E V[G11: ,F 1 ] a canonical term nice Q8-Even(11: +)M r E V [G11: ,F ,] 8 6 such that * = {(17,q) ..17 < 11: + , q E Fn([8,11: ++ ),2,11: + ) /\ 8T llt--------:----8-Even + M Q (11: ) 8 clearly Ii-I---,----- "1r is a nice Fn([8,11: ++),2,11: +) name for a subset of 11: +,, Q 8-Even + M (11: ) u 8 and just as in 4.2.11., for any complete ( r (: ( sequence < 11: ++) of mce Fn(11:++,2,11:+) names for subsets of 11:+ II . 8 -Even + M Q (11: ) 8 "nr r: ( < 11: ++) is a complete sequence of nice Fn([8,11: ++),2,11: +) u '> names for subsets of 11: +,, 8-Even + M If we ~re in the special situation described in ( 4.2.13.) and H is Q 8 (11: ) generic over V[G11: ,F ,], then in V[G11: ,F 1 ,H] there 1s a natural special modified 8, 11: ++ iteration *Q that refers to (H': 1 E Even AI + M) and (((fh)H ,H 77 ): 77 E + - Even /'i, ( /'i, ) n 8, 1 < 11: +) and uses (F 1 :, < 11: +) and whose parameters arise from the -94- parameters of Q via the operation T -+ 'Jr above. The same ideas as m the case of modified iterations lead to the following factor lemma: (4.2.14.) For all ( E [0,11: ++] Once we are familiar with these facts it is rather easy to find a generic g for QN ( the poset at the second step of stage K in Pfc11:)+l) from the generic G for the poset Q that we use at the second step of stage K in PK+ 1 . In the ground model V II*(() = L let II* denote the following injection defined on K + + : = II(() if ( E Even +. K II*(() = ( if ( E K + + - Even +. K 1:1 K ++ - E ven . + M . Th en II * : K ++ --+ onto (11: ) II* induces-a map II*:Fn(11: ++ ,2,11: +) --+ Fn(11: ++ - Even (11: + M ,2,11: +); using ) this map we can associate with each nice Fn(K ++ ,2,11: +) name T for a subset of K + a nice Fn(11: ++ - Even (11: + M ,2,11: +y name TIT* for a subset of K + in the usual way. ) Recall that in N[G11: ,NF,] we have partitioned (11: ++)N into cofinal pieces Ne, (NA 1 : 1 < K +) and (NB 1 : 1 < K +) and we have complete sequences (N r;: E 1/ Fn((11: ++)N ,2,11:) names for subsets of K + from which we define the iteration (N Q(: ( -95- Now in V[GIC ,F 1 ] pick a partition of IC++ into cofinal pieces *C, (* A 1 : 1 < n (IC ++)N = NC and for I < IC+ NA 'Y = *A IT(,) IC+), (*B 'Y ,'Y < IC+) such that *c n N (1C ++) and NB 1 sequences (*rJ:,,., E = *BIT(,) n N (1C ++) and pick for each 1 < IC+ complete *A') and (*u~'',*u~''):'T/ E *B') of (pairs of) nice Fn(1C ++ ,2,IC +) names for subsets of IC+ such that for 1 < IC+ and 'T/ E NA 1 *r~( ,) supp supp *TT/IT(,) n Even * i,IT(,) <TT/ (IC + M = 0 and ) n Even + M = 0. (IC ) Thus, if (Q(: ( :::; IC++) denotes the IC++ iteration that is defined in V[GIC ,F ,] from these parameters and uses -F I we have for each ( with O :::; ( :::; N( IC ++ ) (-Even *Q ( + M (IC ) C _c *Q ( and By 4.2-.8. Q and *Qare isomorphic. Let G (coming from Gv) be the Q generic and G* the N(1C ++ )-Even + M pullback of G to *Q via an isomorphism of Q with *Q. Let g* ~ G* *Q (IC ) n -96- and g the pullback of g* to N Q via the map II*; i.e., g Clearly g is N Q generic. Now we have to show (4.2.15.) N[GK ,NF 1 ,g] is E~ correct for K inside V [GK ,F 1 ,G]. We begin with Lemma 4.2.16. Suppose that N F ZF- is transitive and N F ZF- and NK .c;;; N and N is E~ (n 2::: 0) correct for K inside V where for some S c;;; K for ( E A I and o'~ 1 = o-~ 1 (i = 1,2) for ( E B I for each 1 < K +. If Q E N and Q E V are the corresponding iterations defined from these parameters both using (Fi: r- < K +) and if G is Q generic over V, then N[G n Q] is E~ correct for K in Under the hypotheses it is clear that Q is an initial segment of Q V[G]. (i.e., Q on n. = Q ++ N). Therefore G n Q is N generic for Q. We proceed by induction (K ) -97- The case n = 0 is clear: .N"[G n Q]IC ~ .N"[G n Q] inside V[G] because Q and Q are both <IC+ Baire. Now we handle the case n + 1. Because of the induction hypothesis it is enough to consider <I>(A) in n!+1 and A E (.N"[G n QDIC+2 with .N"[G n Q] F "VIC F <I>(A)" and to show that V[G] F "VIC F <I>(A)." By the IC++ c.c. of Q in .N", we fix 8 < (IC ++).N" and a nice name A E Q8 for A and a condition q E Q8 n G with q I~ "VIC F <I>(A)." Then clearly Moreover, by the factor lemma 4.2.12. and by the analogue of 4.2.8. for modified 8, IC ++ 1't erat1ons . "for all modified 8,IC++ iterations that refer to ( G 1 : 1 E Even +) IC If- VIC F <l>(A)." The induction hypothesis applied within .N"[G V.Ab(.Ab trans, .Ab F ZF-, I.Abl n Q 8] yields in .N"[G n Q 8] = IV 1C+ll, .AblV ICI ~ .Ab, .Ab E~ correct for (G' : 1 E Even +) E .Ab, (((rJ)G ,G,,,):TJ EA I n 8, 1 < 1C+) E .Ab, IC A E .Ab, (F,:, < IC + ) E .Ab, .Ab F 8 < IC ++ .=>. IC, -98- .Ab F "for all modified 8 ,1,, + + iterations that refer to ( G' : , E Even +) K, II- V K, F <I>(A)"]. are all subsets of 1,, + can be coded by one subset of V i,;,+l. We can also express .Ab F 8 < i,;, ++ by picking, in if a wellorder of V i,;,+l of order type 8 and then requiring that this wellorder of (i.e., a subset of V i,;,+l) be in .Ab. This formula will be E~ in this parameter. For each 1 < i,;, + F I C L[S] where S ~ 1,,. Hence we can use the canonical wellorder < L[S] on 2 <K+ to code each F I by a subset of 1,, + • Then again these 1,, + subsets of 1,, + can be coded by one subset of V i,;,+l. formula which is II 2 n+l over V 1,, must hold m V[G Therefore the last formula is n Qc]• Together with another u application of 4.2.12. this yields: V[G] F "VI,, F <I>(A) ." We now return to the proof of (4.2.15): D end of 4.2.16. -99- We assume that <I>(A) is .ll~ U E~ and A E (N[G1C ,NF 1 ,g])IC+ 2 with and we have to show Pick a 8 < N (1C condition q E Q 8 ++ 0 N-+ ) and a mce name A E N[GIC, F ,] N Q8 °g A and a with A n g such that N-+ o N[GIC' F ,] I= "q I~ VIC I= <I>(A)." Q Lemma 4.2.16. together with the factor lemma 4.2.12. yields (4.2.17.) V[GIC ,NF 1 ,g] I= for all modified 8, IC++ iterations that refer to Now recall that V[G1C, N-+ F 1 ,g] -+ ,g *] , which . = V [GIC ,F we call V * from here on. 1 Moreover by (4.2.14.) in V* the tail *Q ++ of *Q is equal to a special modified 8,IC 8,IC ++ iteration that is modified by referring to ((g *,'Y:, E IC+ - Even * (((*fh)g ,g*' 17 ):17 E *A' (IC + M) and ) n 8, 1 < IC+)) and uses (F,:, < IC+). The correctness argument will be finished if we can show -100- (4.2.18.) V* F for all special modified 8, 1,, ++ iterations that refer to ( g *,1' : 1' E Even + - Even M If, * (((*r;)g ,g*T/):r, E *A 7 + ) and (1,, ) n 8, 1' <,,,+))and that use (F 7 :7 < ,,,+) If- "V F <I>(A)." If, The rest of the correctness argument will therefore be concerned with establishing that (4.2.17.) implies (4.2.18.). In the remainder of this section all modified 8, a iterations (where a E [8,1,, ++]) will be (NF 1': 1' < 1,, +) and all special modified 8, a iterations will be referring to (g *,1': 1' E ) and (((*r;)g * ,g*,T/):r, E *A 7 Even+ - Even M If, n 8, 1' <,,,+)and will use (1,,+) (F 1': 1' < ,,, +). The key point in proving that (4.2.17.) implies (4.2.18.) is the following back and forth property of modified and special modified 8, 1,, ++ iterations in V*: given a modified 8, 8 + 81 iteration Q8 8+ 8 ' 1 Suppose we are ( 81 < 1,, ++) that is defined from a -101- l---t----------------+----6 6 + (,c+)M 6 + (,c+)M + 61 1--------------+----------6 Bil(,) = i [B '] and ~f 1 Let *Q 6,6+(,c + M denote the special modified 6, 6 + (,c +)M + 61 iteration that ) +61 we define from these parameters. and Since all these terms have support disjoint from -102- Now suppose we "enlarge" the family of parameters for *Q have a partition of [c5, c5 + (x: +)M + c5 denote again by C, c5 ,c5 + ( K +M ) ; i.e., we + c51 1 + c5 2 ) where c5 2 < x: ++ into pieces that we A', B' (1 < x:+) and sequences('¥(:( EA') (1 < x:+) and =, 1 < + We denote the special modified c5, c5 + (x: + ) M + c5 1 -1,, ,u -2,, ( :(EB ) ( ((u ( x: ). + c5 2 iteration that we obtain from these parameters by *Q +M c5,c5+(x: ) + 81 + 82 . c5 c5 Note that c5 + c5 1 + M (x: + ) !l rng i 2 . Now define -C = U {c5 + c5 + (x: +M = i2 [C] ) } and 1 -103- with the "old" partition of [6, 6 + 61 ). We will now "expand" the old sequences (r ,. E -A')( , < sequences (-'Y T ( : .,. 1,, I: ( +) an d ((_l,, - 2( '') : .,.,. E -B')( , < ,.,~+) such that we u ( ,c; obtained from these parameters: and For 6 + 6 1 + M(,,,+) + 1 + (EB' for some 'Y <,,,+simply let For 6 + 61 + M(,,,+) + 1 + (EA' for some 1 <,,,+we have to look at two cases. If 1 is noncritical (i.e., either I and II('Y) are both even or both odd), then _, ::§:II(,) i2 T 6 +61 +(1,,+)M+l+( ~ (r 6+(1,,+)M+61 +() -104- and if; is critical (i.e., ; is odd and II(;) < (1- +)M even), let A 1 a maximal antichain 5;; where II(;) is thee-th even ordinal <(1- +)M and A 2 a maximal antichain 5;; { q E *Q . 8,8+(1-+)M+81 +(. qi~ ¥II(,) ¥- r8+e}. 8+(,-+)M+81 +( Assuming inductively that ( 4.2.19.) and ( 4.2.20.) hold for ( we pick such that for q E A 1 U A 2 where for q E A 1 (i.e., the canonical Q 8,8+81 +(1- +M ) +1 name for the set that we add at coordinate 8 + 81 + (1- +)M) and for q E A 2 -105- It takes a routine but lengthy argument to show that (4.2.19.) and (4.2.20.) hold throughout this construction: Suppose we have arrived at some coordinate (o + 1 and for all (::; ( 0 (4.2.19.) and (4.2.20.) for ( 0 hold. We can restrict ourselves to checking what happens if 8 + (i;; +)M + 8 1 + ( 0 E Bil(,) for a critical , < i;; +. By induction Then (4.2.20.) for ( 0 together in Q with the way m which we defined (re=( E A' n + M can "see" the set that we added at .coordinate 8 + 81 + 8,8+81 +(i;; ) +1+82 (i;; +)M in Q + M 8,8+81 +(i;; ) +1+82 yield: It cannot happen that we want to kill at coordinate 8 + (i;; +)M + 81 + ( 0 in *Q (at coordinate 8 + 81 + (i;; +)M + 1 + ( 0 in Q resp.) and save at cooordinate 8 + 8 1 + (i;; +)M + 1 + ( 0 in Q (at coordinate 8 + (i;; +)M + 8 This implies (4.2.20.) for ( 0 + 1. Suppose q E Q 1 + ( 0 in Q* resp.). Then one proves (4.2.19.) for ( 0 + 1 as follows: + M where we assume again that 8 + 81 + 8,8+8 1 +(i;; ) +1+( 0 +1 Let q 1 denote the unique element of Fn([8,8 + (i;; +)M + 81 + ( 0 + 1), 2, i;; +) so that -106- By the argument that we just used to establish ( 4.2.20.) it follows that Thus we get (4.2.19.) for ( 0 + 1. We can also go through a similar procedure if we start with a special modified 8, ismorphic had via the right a coordinate induced embedding define an i1 with the complete suborder properties. we can of extension id*_ Q8,8+(K+)M+61 This will work since the special modified iteration *Q + 6,8+(K )M+81 +1+82 does more -107- killing than the modified iteration Q 6,0+1+(11: +M ) . Using this back and forth +61 +62 property of modified and special modified iterations we now show that roughly speaking generic extensions of V* via modified and special modified iterations satisfy the same E§ statements (in parameters from (V*) 11:+ 2 ). Lemma 4.2.21. Suppose that in V* we are given a modified 6, 11: ++ iteration Q ++. 6,11: Let q be a condition in Q qll ++ with 6,11: "VII: F ~(A)." V* Q 6,11: ++ Q - o+o an d there is a witness E (v *) 6,6+61 for the Let o1 < 11: ++ such that q E Q 0 ' 1 E§ statement ~- We have seen how to define an initial piece *Q +M o,0+(11: ) +o 1 of a special modified 6, 11: ++ iteration which has a complete suborder isomorphic via some i 1 and with *Q + M 6,0+(11: ) +61 +62 which has the property that for any extension (6 2 < 11: ++) of it we can define a complete embedding i 2 into In this situation we have for any special modified 6, 11: ++ iteration *Q ++ that extends 6,11: il q V* II *Q u,11: ++ f;: "V "'~ Ir ~(A)." -108- There is also an analogue for this lemma where one starts out with an initial segment of a special modified 6, 1,, ++ iteration in V*. Proof. Suppose cI>(A) = 3X r/Y 'P(X,Y,A) where 'P is E~. Then pick 61 < 1,, ++ with 0 q E Q6 6 + 6 and such that there is a nice Q6 6 + 6 name for a subset of V K+l say X ' 1 • 1 with V* (4.2.22.) qJI Q C u,K Let i 1 · Q c c • o "V,,, FrlY 'P(X,Y,A)." ++ c - - *Q u,u+ul 6,6+ M (1,, + be a complete embedding such that we are m )+61 the situation described above. We claim: 0 "V K, F r/Y 'P(X for any extension *Q c u,K ++ of *Q cc+ u,u M i1 ("" ,,, ,Y,A)" + )+cu · 1 Suppose towards a contradiction that this fails for some extension *Q Then there is some 62 < 1,, ++ and a condition p E *Q *Q M 6 6+ + M 6,6+ (1,, ++. 6,1,, and a nice )+61 +62 + nam~ for a subset of V +l, say Y such that p ~ qil and (1,, )+6 1 +6 2 "' P II *Q V* 0 "V K, F -, ip(X i1 0 ,Y ,A)." 6,,,++ , Now let be an extension of and -109- in the situation described above; then (4.2.23.) 0 0 "V K, F -, <p(X,Y i2 ,A)" for any modified 6, 1,, ++ iteration Q ++ that extends 6,1,, This is true because <pis E Q 6,6+6 +(,,,+)M+1+6 . 1 2 2 0 i1 i2 0 and (X ) = X. 0 On the other hand clearly p there is an isomorphism of Q 6,1,, i2 ~ q. Thus ( 4.2.23.) contradicts ( 4.2.22) since + + with Q ++ that is the identity on Q6 6+6 • ' 1 □ end of 4.2.21. 6,1,, Given this lemma, the proof that (4.2.17.) implies (4.2.18.) is now very easy. suppose that <I>(A) in (4.2.17.) is E~. First Then (4.2.21.) yields (4.2.18.) smce up to isomorphism there- is only one special modified 6, 1,, ++ iteration in V*. If <I>(A) in (4.2.17.) is ll~, assume towards a contradiction that for some special modified 6, 1,, ++ iteration *Q there is a condition q with q II *- "V,,, F -, <I>(A)." Then by the version - Q of 4.2.21. that starts out with an initial piece of a special modified 6, "'++ iteration, we get that for some modified 6, 1,, ++ iteration Q and some condition p E Q Pl~ "V 1,, F-, <I>(A)" which contradicts (4.2.17.). Q Next we consider the third step of stage 1,, of N P j (,,,) . Recall that m -110- N[GIC, NF 1 ,g] we have for each 1 < IC+ a code NF 1 ~ IC+ for NF I by using that in N[GIC, N--+ <1C + <1C + F 1 ,g] 2 ~ L[G1C] which allows us to employ <qGIC] on 2 <1C+ --+ N--+ n L[GIC] is the same whether computed in V[G1C ,F, ,G] or N[GIC, F, ,g] since 2 But N--+ --+ N N[G1C, F 1 ,g] is closed under IC sequences in V[GIC ,F 1 ,G]. Thus F1 < IC + . - 1 ,G]). Hence QN _ (of N[GIC, ~ F 1 ,g]) agrees with QF (of V[GIC ,F F, II(,) In short the forcing at step 3 of stage IC in N Pj( IC) is just the forcing at step 3 of stage IC of P1C+l with its factors permuted by II. Thus with Ns, ~ Sil(,) (where (S,:, < 1C+) is the generic for the third step of stage IC of P 1C+ 1 ), clearly (NS,:, < IC+) is generic for the third step of stage IC of N Pj( IC) . Moreover the fact that the forcing at step 3 of stage IC of Npj(1C) has size IC+ makes it easy to show that N[G1C,NF,,g,Ns",] is E~ correct for IC in V[GIC ,F 1 ,G]',]. The IC+ c.c. implies that N[GIC ,NF 1 ,g, - - Ns ,] is closed under IC sequences in V[GIC ,F 1 ,G,S ,]. A similar argument shows that if ( e,:, < IC+) denotes the generic for the 3rd step of stage IC of P 1C+l that comes from Gv, then with Ne, = ell(,) the sequence (Ne, : 1 < IC+) is generic for the forcing at the third step of stage IC of N Pj( IC)° Since this forcing has size IC - -- V[GIC ,F, ,G,S ,,e ,] + N--+ Net N--+ 2 , N [G IC , F 1 ,g, S 1 , e 1 ] will be E correct for IC inside 2 and by the IC + c.c. N--+ Net N--+ N[G1C, F 1 ,g, S 1 , e,] will be closed under IC sequences in V[G V]. Recall that the tail Np 1C+l,j(1C) has a <µ closed dense suborder (whereµ is the -111- next inaccessible in N > x:). Since IN[Gx;,NF,,g,Ns,,Ne,]1 = II:+ we can in V[Gv] construct an H which is generic over N[Gx; ,NF I ,g, Ng ,,Ne,] for the tail in the usual = Gx; * NF I * g * Ng I * Ne I * H way. We know that j lifts with j(Gx;) M[Gx:] Px: M j j NLl(Gx;)] N pj(x:) N. Moreover NLl(Gx;)] is closed under 11: sequences and E~ correct for x: inside V[Gv] since the tail is highly Baire. Next we consider stage x: of Mp x:+l and stage j(11:) of Npj(11:)+l · Denote by the 4 steps of stage 11: of MP 11: + 1 that come from GM . Since the first three steps of stage j(x:) of Pflx:)+l are all <j(x:) directed closed, it is easy to find master conditions in these cases. The fact that INLl(Gx:)]I = 11: + allows us to construct generics for the first 3 steps of stage j(x:) of Pflx:)+l that contain these master conditions in the usual way, then j _lifts. M[Gx;, M--+ M l\,t;:;'" F ,, g, s ,ll - M N -112- To handle the last step of stage j(x:) of Pflx:)+l where we add a sequence of club sets ~ j( x:) that avoid a certain set of inaccessibles, we proceeed just as in the (11 / 71'1 case. Define c* by dom(c*) 'M {j(,): 1 < (x:+)M} and for 1 < (x:+)M let If we can verify that c* is a condition m the forcing at the last step of stage x: of N pj(x:)+1' we are done. For this it is enough to show that m NLi(Gx:)J(MF 1 ),j(Mg),.i(Ms 1 )] for each 1 < (x: +)M ( 4.2.24.) c;e,) n {µ < j( x:): µ inaccessible /\ E2 where cl>· 3 is the about the µ j( MS)j(,) E: < x:. statement (4.1.10.). As in the (11/71'1 case we don't have to worry For µ = K recall that j(x:) n X: = x:, j(Gx:) n V K = Gx; and n V,,, = j( M-S 1 ) n Vx: = M-S 1 = i( M-S1 ) = S,- (which is the 1 -th code that we add at the third step of stage "' of P +l). x: rr- 1 [(x: +)M] about S 1 ~ Odd,,,+. Recall also that S1 Thus in N[G,,,, NF 1 ,g] the n! = Ns rr- l (1) and statement (4.1.11.) is true = N-Srr-l(,). In the last two steps of stage,;, of N Pj(,;,) we do not add any new subsets of x: + all of whose initial statements are in N[Gx: ,NF 1 ,g], since both posets -113- have the "'+ property. Moreover the tail NP x: + 1 j (,..,) + 1 is highly Bai re in N[Gx;,NFr,g,Nsr,NcrJ· Thus we can conclude that then! fact (4.1.11.) holds about Sr = Ngrr-1( r) in NLl(G,..,)j(MF r )j(Mg)j(Ms r )] also; i.e., V x: I=· ct> V ,..,j(Gx:) n V,.., j("') n x:). Thus we have proved (4.2.24.) E2 3 ocMsr )n -114- SECTION g_. u~/1r~ (n ~ 2). 5.1. Definition of the Iteration P~. We are going to define 1,, + 1 stage iterations P~ by induction on n. iterations are analogues of the one that we used in the "generic" case These 0-5/ 1r5 and we will restrict ourselves to describing what must be changed. At stage .,\ ::; 1,, of the iteration P~, where .,\ is a Mahlo cardinal, we will again have a four-step iteration: step we will add a .,\ + sequence (Fr: r In the first < .,\ +) where each Fr is a Lipshitz function (2.,\ + )n-1 __. 2.,\ + In the second step we use a certain suborder of Fn( .,\ + + ,2,.,\ +) to make a E~ statement true about the Fr with r even and JI~ statement about the Fr with r odd. Then in the third step we code each Fr by a subset Sr ~ .,\ exactly as in case and finally in the 4th step we add a sequence (Cr: r u5/1r5 < .,\ +) where each Cr ~ .,\ is club and avoids the set of all inaccessibles µ < .,\ such that a certain E~ statement holds in V µ just as in the u5/1r5 case. In order to keep notation as simple as possible we will not give the full definition of a 1,, + + iteration Q that makes a E~ statement true about the Fr for even r and a JI~ statement about Fr for odd r- Instead we will work with one Lipshitz function -115- F: (2A + t- 1 ----+ 2A + and define an iteration ·Q 2 with En where the Xi range over subsets of A+ and Q E {3, 'v'} and i.p says that F(X 1 , ... ,Xn) is stationary or is nonstationary depending on whether n is even or odd, respectively. We will also define an iteration Q 2 such that nn with Q and i.p subject to the same conditions as above. In order to define Q 2 and Q 2 in both cases we first partition A++ into En lln cofinal pieces C and A (k) (1 ~ k ~ n - 1) with O E C. Then for each k with 1 < k < n - 1 we choose complete sequences of k-tuples of nice Fn( A++ ,2,A +) names for subsets of A+ and enumerate them along the coordinates in A(k\ i.e., ((r~l) , ... ,r~k)):( E A (k\ Then we define our iterations to be suborders of Fn( A++ ,2,A +) where at each coordinate ( E A++ - A (n-l) we simply add a new subset of A+ and for ( E A (n-l) we add a club set ~ A+ which is disjoint from F(f-~l) , ... ,f-~n-l)) if certain "killing conditions" are met. If these conditions are not satisfied we save F(r~l) , ... ,f-~n-l)); i.e., we force with the trivial poset {0}. -116- In order to describe these killing conditions we associate with each n ~ 2 a finite binary splitting graph for E! and a finite binary splitting graph for n! . The edges in these graphs will be labeled by integers. If some edge is labeled by say k (0 < k ~ n - Q 2), this corresponds to the situation that in V ( (where Q( is the iteration restricted to Coordl·nates < .,r) (T. .,~l) , ... ,T. ((k+l)) . (k) , GT/) 1or some T/ E A(k) n .,r w h ere =(.Tr,(l) , ... ,TT/ .c GT/ is the set that we add at coordinate T/· The label -k (0 < k < n - 1) corresponds .(1) to the failure of this situation. The labels O and -0 express whether T ( = G or not. 0 Q Now in order to determine whether we kill or save at coordinate ( (in V () we simply pick the path in the graph that disagreements of ( r~l) ,... ,r~n-l)) corresponds to the various agreements and check if it ends m a terminal mode that 1s labeled "kill" or "save." The graphs for n = 2 are very simple: .ll~ (kill) i.e., no edges. And for n .ll 2 ___J-- save 3 --:::-r--kill and = 3 we have 2 E3 ---9-- kill ~ 2___1---save -0 .ll -::-r- kill 3 -117for n ~ 3 we proceed by induction y···} 'Z ~--.} graph for JI~_ 2 where we add 2 to (subtract 2 from resp.) all positive labels including 0 (all negative labels including -0 resp.). graph for E~ _ 2 with all labels changed as above graph for E~ _ 2 with all labels changed as above graph for JI~ to illustrate what the graphs look like in practice we write them out up to n 2 fli(kil) 2)/1""'3 ,-1...... kil = 7. -118- As in the 1r~/ 0-5 case both Q 2 and Q 2 are <-X closed and .X + + c.c. Moreover an IIn En argument analogous to the one in the 1r~/ 0-5 case shows that all these iterations are <-X + Baire. Next we show that these iterations force indeed the II~ and E~ statements about F that we want. Note that lemma 4.1.7. can be proved about Q 2 and Q 2 by En IIn virtually the same idea. Lemma 5.1.1. Q 2 (Q 2 17 n IIn we want. Proof. We have to inspect two cases. Casel. nisodd,sayn=2l+1(€~1). 2 The IIU+l statement says: 2 2 resp.) force the II n (En resp.) statements (over V _x) that -119- 2 2 From the inductive definition it follows that the top path in the graph for rr £+l 1s labeled by the sequence 1, 2, ... , 2£ - 1 and ends in a save node. Now assume that G is Q 2 II generic over V[G,\ ,F] and work in V[G,\ ,F,G] if 2£+1 x 1 ~ ,\ + pick 11 1 E A (l) with ( f-½~))G = X 1 . . coordmate 11 1 ). For X 3 ~ ,\ (X 1 ,X 2 ,X 3 ) and let X 4 + now pick . 11 = G 773 . 3 EA Let X 2 (3) = G 77 (the set that G adds at . ( . (1) G . (2) G . (3) G) with (r ) ,(r ) ,(r ) 773 773 773 = Continue in this manner and define a tupel (X 1 , ... ,Xu)· Since the top path in the graph for JI~£+l is labeled 1, 3, ... , 2£ - 1 and ends in a save node, the analogue of lemma 4.1.7. for Q 2 II 2£+1 yields that F(X 1 , ... ,X 2 e) is stationary. 2 The E2£+l statement says: Again let G be Q 2 E generic over V[G,\,F] and work in V[G,\,F,G]. From the 2£+1 inductive definition- it follows that the top path in the graph for E~£+ sequence O, 2, ... , 2£ - 2 and ends in a killing node. Take x 1 2 . ((f-?))G , ... ,(f-~2£))G) Now for x 2 £ ~ ,\ is labeled by the = GO. For x2 ~ ,\ + pick 77 2 E A ( ) ((f-~i)G ,(f-~~)G) = (GO ,X 2 ) and let x 3 = G fashion and define a tupel (X 1 , ... ,X2£_ 1 ). 1 772 . Continue in this + find ( E A (2£) with . = x 1 , ... , x 2 £. Since the top path in the graph for E~£+l ends in a kill mode, we add the coordinate ( a club set ~,\ + which is disjoint from -120- Case i. n is even, say n = 2€ (€ ~ 1). □ end of 5.1.1. Here a similar argument as in case 1 works. Preservation of the .ll~ Indescribability of x:,. 0 p2 We assume towards a contradiction that there is a condition p E P~ and A E V n and cf> in .ll~ with 0 P I ~ "cf>(A) describes x:,." Pn Pick an ordinal 8 > the least inaccessible above x:, such that 0 V 8 I= ZF- /\ Pl~ "cf>(A) describes x:,." Pn Pick an elementary embedding i: M --+ V 8 with cpt i > x:, and M trans, IMI M<"' ~ M. By the .ll~ indescribability of x:, in V there is trans N with INI x:, and = x:,, N"' C N and N is E~-l correct for x:, and an elementary embedding j: M--+ N with cpt j x:,. By the same argument as in the a-§/ 1r§ case we can find a V generic VG for P~ and an M generic MG for Mp~ and that p E VG and i lifts. Now we have to come up with an N generic NG for Np~ such that j lifts and such that N(NG] is still E~-l correct for x:, in V(V G). The construction of NG is very similar to the construction in the a-~/ 1r~ case. Only the part where we have to find a generic for stage x:, of NP~ from a generic for stage x:, of VP~ deserves a detailed exposition. -121- Clearly the forcing that N[G,c] wants to do in the first step of stage 1,, of N Pii is the same as the one that V[G,,,] wants to do at the first step of stage 1,, of Pii, since N[G,,,] is closed under 1,, sequences inside V[G,,,]. Thus if (F-y: -y < 1,, +) are the 1,, + Lipshitz functions that we add at the first step of stage 1,, in V, then with NF "Y ~ F II( "Y) (NF-y:"Y <,,,+)is certainly generic over N[G,,,] for the forcing that N[G,,,] wants to do 2 N----,. 2 at the first step of stage 1,, of Pn and N[G,,,, F -y] is En-l correct for 1,, and closed ----,. under 1,, sequences in V[G,,, ,F -y]- Suppose that (Q(: ( < 1,, ++) denotes the 1,, ++ iteration that V[G,,, ,F -y] wants to use in order to make a Eii (llii resp.) statement true about F-y where -y is even (odd resp.) and (N Q: ( < (NF "Y: -y < 1,, 1,, 1,, ++) is the (1,, ++)N iteration that N[G,,, ,NF -y] wants to use for +). In the same way as in the o-~/11] case ++ ~ Even l·l we use the map II*:,,, ++ -=-+ . onto + M to define a 1,, ++ iteration *Q in V[G,,, ,F -y] with the property that ( K, ) II* induces an isomorphism of N Q with a complete suborder of *Q ++ N. Recall that ( K, for critical ''i < 1,, + *Q wants to make a :E~-l statement true about F II(-y) N Q wants to make ll~-l statement true about N F-y. rng II* ) = NF I and However from the fact that n Even + M = 0 , it follows that no term that appears in Q* at a coordinate ( K, ) <(1,,++)N can possibly "see" the witness for the :E~-l statement about FII(-y) (for critical 1 ) that * Q adds at coordinate II( -y). Now the key observation is that the edge in the graph for :Eii which is labeled -0 leads into a subgraph which is identical with the graph for llii. Therefore, if G denotes the V[G,,, ,F -y] generic for Q and G*, the generic -122- for *Q that is obtained from G (by applying the fact that Q and *Q are isomorphic since the analogue of 4.2.7. clearly holds in the of G* to the complete suborder of *Q o-~/1r~ case), and if g* is the restriction ++ N that is isomorphic to N Q, then g (the (K ) pullback of g* via the isomorphism induced by II*) is clearly N[G,,; ,NF,] generic for NQ. Now we claim (5.2.1.) 2 N[GIC, NF 1 ,g) is En-l correct for IC in V[GIC ,F 1 ,G]. Once we have proved this we can construct the rest of NG and carry out all the remaining correctness arguments exactly as in the 0-5/ 1r5 case. The Proof of (5.2.1.) . . We start out exactly as in the 2 o-5/1r5 case and let <I>(A) be a formula in E~-l U N-. II n-l and A E (N[GIC, F 1 ,g])IC+ 2 and assume that Pick an ordinal 6 < K condition q E g ++ o Q6 og and a mce name A E (N[GIC ,F ,]) with A A and a n Q 6 such that 0 "VIC F <I>(A)." Clearly the analogues of the factor lemmas 4.2.12. and ( 4.2.14.) can also be established for the a-~/ II~ case by using the exact same arguments as in the o-5/1r5 case and we have already remarked that the analogue of the isomorphism lemma 4.2.7. is also true in -123- the o-~/1r~ case. Hence we can apply the analogue of lemma 4.2.16. and obtain that in * --+ V ~ V[G1C,F,,g] = V[GIC, N--+F 1 ,g *]: for all modified 6, IC++ iterations that use NF 1 I~ VIC F lf>(A). In order to finish the proof it certainly suffices to show: for all special modified 6, IC++ iterations which use F 1 I~ "VIC F <I>(A)." It goes without saying that modified 6, IC++ iterations and special modified 6, IC++ iterations in V* are defined totally analogous as in the o-j/1rj case. Moreover, modified iterations always use (NF 1 : 1 < IC+) and special modified iterations use (F 1 : 1 < IC+). Recall that for "many" 1 < IC+ modified and special modified iterations, both make a E~ or a ll~ statement true about NF 1 = F II( 1 ) . However for the critical 1 (i.e., 1 odd and 1r( 1 ) < (1C +)M even) the modified iteration makes all~ statement true about NF 1 = F II( 1 ) and the special modified iteration makes a E~ statement true about F II( ) . Th us what is really going on here is the following: 1 We are working in a model ( call it simply V) with a Lipshitz function --+ 2 1 + . <I>(A) is a formula in ll~-l U E~-l and A E V 1C+ 2 such that for all ll~ iterations Qll. (5.2.2.) I ~ "VIC F <I>(A)" Q and we want to see that for all E~ iterations QE -124- (5.2.3.) I ~ "V /,; F ~(A)." Q In order to show this we use the (n - 1) back and forth property of E~/ lI~. By this we mean the following: For a given initial piece Qf1 of a lI~ iteration it is possible to define an initial Qf+ 61 of a E~ iteration and a complete embedding i1 that is an isomorphism of Qf1 with a complete suborder of Qf+ 61 . If we enlarge (where 62 < ,,; ++), then we can define an extension Qf + + 6 of Qf and a complete 1 2 2 1 embedding i2 that is an isomorphism of Qf+ 6 + 6 with a complete suborder of 1 2 Qf1 + 2 + 62 with the property that i2 o i1 = id Q6II. piece 1 This process can be repeated until we have defined embeddings i 1 , i 2 , ... , in-l and an initial segment qII of a II~ iteration and an initial QE of a E~ iteration such that i 1 , ... , in-l allow us to go back and forth n iterations in the way described above; i.e., ik+l o ik 1 times between these two = id for 1 $ k $ n - 2. Moreover we can go through a similar procedure if we start with an initial segment of a E~ iteration. Proof of the (n -1) Back and Fourth Property for E~/ II~ (n ~ 1). We first treat the case E~n+l/ II~n+l (n ~ 1). with an initial segment E Q 61 Fix n ~ 1. Suppose we start out (where 61 < ,,; ++) for a E~n+l iteration. Denote [0,6 1 ) -125- ( < 61 . Note that O ~ rng i 1 and for reasons that become apparent below we call O the new coordinate in ll,JI. Now define a JI~n+l iteration JI Ql+bi whose underlying partition of 11 JI is the partition induced by i 1 and where we do not associate a tupel of ' terms with 0. If no tupel of terms is assigned to coordinate ( E 11 E, then this is also ' true for 1 + ( E 11 JI . If a k-tu pel ( with k =I=- 1) of terms appears at coordinate ' ( E 11 E, then to coordinate 1 + ( E 11 JI we assign the tupel of terms each of which is ' ' the i 1 -shift of the corresponding term in the tupel that appears at ( E 11 E. If a single ' term T( is assigned to coordinate ( E ll,E, then we pick a canonical term the set that we add at the new coordinate in 11 JI if certain ' E altering coordinates hold in V Q( about f- ( ( T () il otherwise. We will explain in a moment what these altering conditions are and we are also going to show that in fact for each ( E 11 E ' i induces an isomorphism of E Q( with JI Qi!~-{O} 1 which is a complete suborder of JI Ql+( . Eq This shows in particular that V and the definition of T* makes sense. JIQl+( ( can be regarded as being contained in V -126- In the second step of the construction for E~n+lf JI~n+l assume we extend so that in particular i2 o i 1 = id 11,L' and i\ + 1 ~ rng i2 . E Q +2 + by choosing the partition of 12 ,E that is 81 82 Now we define an extension induced by i2 . We assign no tupel of terms to coordinate 81 + 1 which we call the new coordinate in 12 E. If a k tupel (k # 2) is assigned to coordinate ( E 12 JI, then the k- ' , tupel that consists of the i 2 shifts of the terms in this tupel will be assigned to coordinate i2 (() E Il,JI. If a pair (f-~l) ,f-?)) is associated with a coordinate ( E 12 ,JI, E then we associate with i ( () E 1 ,E the pair ( r * ,( f- ((2) ) i2 ) where r * E V Qi2W 2 2 E canonical term such that in V Qi (() 2 the set that we add at coordinate 8 1 + 1 if certain altering JIQ r* = conditions hold in V 1 (f-~ )/ 2 otherwise. ( about f-~l) is a -127- Again we have to check that for ( E 12 ,JI, i 2 induces an isomorphism of JI Q( with We continue in this fashion until we have defined Il,E, ... , I2 n- l,E and Il,.ll, ... , I2 n-l,JI and embeddings i 1 , ... , i 2 n-l. In the last step of the construction we will not introduce a new coordinate to define I 2 n,E from I 2 n,JI and we shift all terms at coordinates in I2 n,JI to get the terms for the corresponding coordinates in I 2 n,E. The schematic picture that one should have in mind when doing this construction looks like this: 1•1 ~ \/ I2 JI l1,11 l3,11 ' 13 11 1 3 10 11,..v 12,..v I3,..v i,f 't 1 2n-l,JI I2n,11 2n-1 12n-1,..v l2n,..v The numbers below the arrows indicate the arity of the tupels whose first term gets changed at this stage of the construction. The symbol o indicates that we have a new coordinate in the interval where it occurs. - We are now going to explain what the altering conditions are. Suppose we are at stage k ~ 2n-1 of the construction above and k is odd (even resp.) and the k-tupel (T?), ... , Tt)) is assigned to coordinate ( E Ik,E (( E Ik,JI resp.). Consider the graph for E~+ 2 (JI~+ 2 resp.). Among all its killing paths consider the direct killing paths, -128- i.e., those killing paths whose last edge is labeled with a non-negative integer. Now the altering condition for f-~l) 1s satisfied if one of the agreement scenarios prescribed by ,(1) the direct killing paths hold about ( r ( ,(k) , ... , r ( Eq ) m V IIq ( (in V ( resp.). Before we argue that the construction that we just described really works, let us explain what the constructions look like in the other cases: segment II Q E Q1+ 81 81 If we start with an initial of a II~n+l iteration where 81 < 1,, ++, we can define an initial segment of a E§n+l iteration where all terms are obtained by shifting the terms from II Q( so that they cannot see the E witness that we add at coordinate O of E Q 1 + . 81 1 In steps 2, 3, ... , 2n we proceed analogously as in the steps 1, 2, ... , 2n-1 of the construction II~n+l/ E~n+l where we start with an initial piece of a E~n+l iteration. Thus the schematic picture looks like this: 1•1 \ ;I 12 .L' 11,.L' ' Ia,.L' 10 11 12n-l,.L' i,f 2n-2 12,JI Ia JI ' 12n-l,JI \" 2n- 10 10 11,JI I2n,.L' I2n,11 Again the numbers below the arrows indicate the arity of the tupels whose first term gets changed if the altering condition is met where now the altering condition for even (odd resp.) stage k with k E {2, ... , 2n} is given by the direct killing paths in the graph for E~ +l (II~+l resp.). As before the symbols o indicate that there is a new coordinate in the interval where they appear. -129- The constructions for the H§n/ E§n case (n > 1) are totally analogous to the corresponding ones in the JI§n+l/ E§n+l case. Now we have to check that these constructions really work. Let us examine the E~n + 1 / H§n + 1 case where we start with an initial piece of a E§n + 1 iteration. Suppose we are at step k ~ 2n-1 of the construction with k being odd and ( E Ik E. ' For the construction to work we have to show (5.2.4.) Il,H U · · · U Ik H - { new coordinate E I k JI} c HQ_ ' Ik(() (5.2.5.) ' HQ. -C Ik(() ik induces an isomorphism of E Q( with HQ I 1 H U · .. U Ik H - { new coordinate E I k JI} . ' Ik(() ' ' where H Qik(() ( 17 Q( resp.) denotes the H§n+l (E§n+l resp.) iteration up to coordinate ik(() E Ik H (( E Ik E resp.). ' ' We show this by induction on ( E Ik E. Clearly we can restrict ourselves to a ' successor ordinal ( + 1 E Ik E where at coordinate ( we possibly add a set that kills ' • (1) F( T ( • (2n) , ••• ,T ( ). First we handle (5.2.5.). Note that V Eq( can be thought of as being JI contained in V Qik( ) ( in the sense that by induction hypothesis complete suborder of JI Q. lk(() E Q is isomorphic to a In order to prove (5.2.5.) it will therefore suffice to show the following two central facts. -130- (5.2.6.) We cannot be on a killing path for Il§n+l in V IIq. 'k(() and on a Eq saving path for E§n+l in V ( and Eq We cannot be on a killing path for E§n+l in V (5.2.7.) 2 V path for II 2 n + 1 in ( and on a saving II Qik(() Once these two central facts have been proven we consider the first claim (5.2.4.): For this it suffices to show that if q E JI Qik((+l), then q 1 which is obtained from q by dropping the new coordinate in Ik,JI is again a condition in II Qik((+l) There is a unique q 11 E Fn((+l,2,11:+) with (q /k 11 q E JIQik((+l) So assume = q 1• Ifwe can show that q 11 E E Q( + 1 , then we are done since we have already shown ( 5.2.5. ). But q 11 E 17 Q(+l follows easily from the first central fact. If we are at step k ~ 2 n - 2 of this construction where k is even, we proceed in an analogous manner. Finally at the last stage of this construction we do not have a new coordinate in 12 n,E and all terms get shifted in i 2 n where we go from I2 n,JI to I 2 n,E We have to show that i 2 n induces a complete embedding of II Q( into E Qi nW (for ( E I 2 n,JI ). 2 In order to prove this we use the first of the two central facts and obtain i 2 n ( q) is a condition in EQi n(() for all q E JI Q(. In order to show that each q E E Qi n(() has a 2 2 -131- i 2 n -reduction in II Q(, we proceed by the method used in the proof of 4.1.3. In order to show that the construction for II§n+l/ E§n+l' starting with an initial piece of a II§n+l iteration, and the constructions for II§n/ E§n work we have only to prove the analogues of the two central facts (5.2.6.) and (5.2.7.). Proof of the Two Central Facts That Establish the n 1 Back and Forth Property for 2 2 (n ~ 2). En/IIn We prove by induction on n ~ 2 that the two central facts hold throughout the constructions for E~/ II~. The key ingredient here is the inductive definition of the graphs for E~ and II~ which will be used all over the proof. We begin the induction by examining the two basic cases E§/ II§ and E~/ II~. If we are given an initial piece of a II§ iteration II Q 8 , then we can define an initial 1 piece of E§ iteration E Q + by shifting all the terms in II Q so that they cannot see 1 61 61 the E§ witness that we add a coordinate O in EQ1 + 61 . Clearly the two central facts hold in this case. If we start with an initial piece of a E§ iteration EQ61 and define an initial piece of a II 22 iteration II Q c by using the same parameters, then clearly E Q Ul ~ II Q 61 81 since the graph for II 22 has no saving paths at all. Now we examine the case where we start with an initial segment of a nj -132- II Q . In the first step we define an initial piece of a E§ iteration E Q1 +6'i iteration 01 by shifting all the terms from II Q so they cannot see the E§ witness at coordinate O in 01 17 Q + . The two central facts clearly hold at this step. 1 61 In the second step suppose EQ we are at coordinate ( E I 2 ,E and on a killing path for E§ in V either 0, or -0, -1. If we have O in V Eq ( so that we have . IIqi 2 W ( then there cannot be a 1 m V with a term that appears at a coordinate E Il,JJ since none of these terms can see the L'§ witness that we add at the new coordinate O E 11 E . Furthermore there cannot be a 1 ' IIq in V i 2 (() with a term that appears at a coordinate E 1 JI since when going from 2 12 E to 12 JI we change all 1 's in 12 ' ' ' ' L' because we have 0 in V Eq ' . Thus we have -1 IIq. . . V 1.e., we k"ll 1 1n 12 (() E . V If we h ave - O, - 1 1n Q' th en we clearly Now suppose we start with an initial piece of a E 2 iteration E Q c • We can argue IIq must have -1 1·n V IIq. 12 (() i2 (() ; 1.e., • • we k"ll. agam 1 m V 3 01 similarly as we did in the second step of the last case to see that if ( E 11 E and we kill ' EQ( at ( in V , then we also kill at i 1 ( () E I l,II in V IIQ Conversely if we kill at EQ i 1( () , 1.e., · . V we h ave - 1 , th en 1n · V 1· 1 ( .,;-) 1n IIQ. (() 11 ( - 0 clearly imp . 1·1es - 1 ; 1.e., . we k"ll 1 EQ at ( in V ( In the second step a similar argument shows that if we are on a killing -133- path for JI~ at a coordinate ( E 12 JI , then we are also on a killing path in E Q. , Now suppose n 12(() > 4 and we have already proven the two central facts for all constructions for E~/ JI~ with k < n. We will restrict ourselves to looking at an odd 2n + 1 (n ~ 2) and consider the case of E~n+l/JI~n+l where we start with an initial piece of a JI 2 2 n + 1 iteration. The arguments for the other cases are similar to the argument that we present here in detail. First we want to argue that the two central facts are satisfied through the first 2n - 2 stages of the construction. For this we make the following observation: The subgraph of the graph for E~n+l (JI§n+l resp.) which consists of all edges that are labeled by an integer of absolute value ~2n - 3 is identical with the graph for E§n-l (JI§n-l resp.) except that all nodes in the graph E§n_ 1 (JI§n-l resp.) of the form Q~ (Q E {V ,3}) have to be changed to Q~+ 2 and we must replace each save node by the graph for JI~ where the labels 1, -1 get replaced by 2n -1 and -(2n-1) resp. and each kill node must be replaced by the graph for E~ where the labels O, -0, 1, -1 get replaced by 2n - 2, -(2n-2), 2n - 1, -(2n-1) resp. If we now apply the induction hypothesis about E§n-l/ JI§n-l together with this observation, then we see that up to the first 2n - 2 stages of the construction for E§n+l/ JI§n+l we have the following: -134- Any time we are on a path in the subgraph of the graph for lI§n+l mentioned above that ends in "E§" we cannot be on a path in the subgraph of the graph for E§n + 1 that ends in 2 "II§" and similarly if we interchange 2 II2n+l and E2n+l. Then note L'§n+l/ that throughout the first II§n+l all the terms in 2n - Moreover a 2n - 2 stages of the construction for 2 and 2n - 1 tupels merely get shifted. E§ iteration clearly does more killing than a II§ iteration. Hence the two ,e;ntral facts hold throughout the first 2n - 2 stages of the construction for Now we consider the last two stages of the construction for E§n+l/II§n+l where we start with an initial piece of a II§n+l iteration. First we show that if we kill on the II§n+l side, we cannot save on the E~n+l side. Inspection of the graph for II§n + 1 tells us that there are two cases for killing paths: indirect killing; i.e., the last edge in the path is labeled -(2n-1) and direct killing; i.e., the last edge in the path is labeled 2n - 2. On th~ other hand there are two ways of saving in the graph for E§n+l: indirect saving;, i.e., the last two edges of the path are labeled -(2n-2), 2n - 1 and direct saving; i.e., the last two edges of the path are labeled 2n - 3, 2n - 1. It can never happen that we are on an indirect killing path for lI§n+l (i.e., -(2n-1)) -135- and on a saving path for E§n+l (i.e., 2n - 1) since at stage 2n of the construction for 2 . . . . 1 piece . . . E 22 n+l /II 22 n+l s t artmg WI"th an 1mt1a of a II 2 n+l iteration, a 2 n - 1 tupe1 gets altered only when we are on a direct killing path for E§n + 1 . It cannot happen that we are on a direct killing path for Il§n+l (i.e., ends in 2n - 2) and on an indirect saving path for E§n + 1 (i.e., the next-to-last edge is labeled -(2n-2)). This is so because at stage 2n - 1 of the construction for E§n+l/ Il§n+l (starting with an initial piece of a ll§n+l iteration) a 2n - 2 tupel gets altered only if we are on a direct killing paths in the graph of ll§n . However the direct killing paths in the graph for ll§n can all be extended to save paths or indirect killing paths in the 2 graph for n 2n + 1 . 2 Finally we consider direct killing in n 2 2 n+l and direct saving in E 2 n+l · We observe that the direct killing paths in ll§n+l are just all the killing paths in Il§n-l extended by one edge which is labeled 2n - 2 and all the direct saving paths in E§n + 1 are just all saving paths in E§n-l extended by one edge labeled 2n - 1. Now we can apply our induction hypothesis about the E§n-l/ ll§n-l construction and hence this constellation can never arise. Next we show that m the last two stages of the construction E§n+lf ll§n+l 2 ( starting with an initial piece of II 2 2 n + 1 iteration) we cannot kill on the E 2 n + 1 side and save on the Il§n+l side. -136- We have to check three cases here: Indirect killing path for E~n+l (i.e., ending in -(2n-1)) versus saving path in lI~n+l ( always ending in 2n - 1) cannot occur since the first term in a (2n - 1 )-tupel that gets altered at stage 2n of the construction for E~n+l/lI~n+l (starting with an initial piece of a lI§n+l iteration) will then denote the set at the new coordinate E I 2 n,1I . But no term at a coordinage E Il,lI U •• • U I 2 n,1I can "see" this set. Next we consider a direct killing path zn E§n+l (i.e., ending in 2n - 2) versus an indirect saving path in lI§n+l (i.e., ending in -(2n-2), 2n - 1). In this situation the 2n - 2 agreement m E§n+l had to occur with a (2n - 2)-tupel whose first term denotes the set that we add at the new coordinate I 2 n _ 1 E . Therefore the 2n - 1 ' agreement in lI~n+l had to occur at a coordinate E I 2n,1I. Then this must come from a 2n - 1 agreement in E~n + 1 at a coordinage E I2 n,E . However we assumed we were on a direct killing path m E~n+l. Thus any such 2n - 1 agreement would get destroyed at stage 2n of the construction for E§n+l/ lI§n+l when going from I 2 n,E to l2n 1I - a contradiction. ' Finally we consider the case of a direct killing path in E§n + 1 ( ending in 2n - 2) -137- versus a direct saving path in ll§n+l (i.e., ending in 2n - 3, 2n - 1). We prove the following: Claim: If we are on a direct killing path for E§n + 1 and on a direct saving path for ll§n + 1 , then there cannot be a 2n - 1 agreement on the ll§n + 1 side with a 2n - 1 tupel that appears at a coordinate E r1 .ll U · · · U r2 n .ll . ' ' The claim will give a contradiction to the fact that all direct saving paths for ll§n + 1 end in an edge that is labeled 2n - 1. Proof of the claim: First we note that the (2n - cannot occur with a (2n - 2) agreement on the E 2 2 n+l side 2) tupel that appears at a coordinate E I2 n E because in ' that case any (2n - 1) agreement on the E§n+l side had to occur at a coordinate E I 2 n,E . Since we are on a direct killing path for E~n + 1 , the first term in any 2n - 1 tupel that gives a 2n - 1 agreement on the E§n+l side will be altered when going from r2 n,E to I 2 n,.ll · This will result in -(2n - 1) on the .ll~n+l side - a contradiction. Now there are 2 possibilities for a direct killing path in E~n+l. If its next-tothe-last edge is labeled -(2n-3), then the first term m any 2n - 3 agreement on the side has to agree with the set that we add at new coordinate E I 2 n_ 2 n · ' From this it follows that any 2n coordinate E 2 agreement on the E~n+l side has to occur at a r2 n - l,E U I 2 n,E because none of the terms appearing at coordinates E Il,E U ·· · U I2 n- 2 ,E can see the set that we add at the new coordinate I 2 n- 2 ,.ll. By the remark at the beginning of the proof of the claim, the 2n - 2 agreement on the -138- L'§n+l side must therefore occur at a coordinate E I2 n-l,E. Now we observe that the direct killing paths in ll§n are labeled exactly as the direct saving paths in ll§n + 1 if we delete their last edge. Therefore the first term in any 2n - 2 tupel that gives a 2n - 2 agreement on the E 2 2 n+l side has to agree with the set that we add at the new coordinate E I2 n _ 1 E . This implies that any 2n - ' has to occur at a coordinate E I 2 n,E. 1 agreement on the E 22 n+l side But then we will end up with no 2n - 1 agreement on the ll§n+l since in the 2n-th step of the construction for L'§n+l/ ll§n+l ( starting with an initial piece of ll§n + 1 iteration) all these 2n - 1 agreements vanish - a contradiction. So we have shown that the direct killing path in E 2 2 n + 1 cannot end with -(2n-3), 2n 2. Thus it must end m 2n - 4, 2n - 2. Inspection of the graph for L'§n+l and L'§n shows that we are on a direct saving path for Inspection of the graph for ll§n+l and E§n in this case. ll§n shows that the direct saving paths in ll§n+l are obtained from the direct killing paths in ll§n by extending them with an edge labeled 2n - 1. We can assume by induction that: If we are on a direct killing path for ll§n and a direct saving path for L'§n , then there cannot be a 2n - 2 agreement on the E§n side with a 2n - 2 tupel that appears at a coordinate E Il,E U ·· · U I 2 n-l,E in the construction for ll~n iteration). E§n/ ll§n (starting with an initial piece of a -139- Th us any 2n - 2 agreement on the E§n + 1 side in the E§n + 1 / .ll §n + 1 construction has to occur at a coordinate E I 2 n E. Again the remark at the beginning of the proof of the ' □ end of proof of claim claim gives a contradiction. To show the two central facts for the E§n+l/ .ll§n+l construction (starting with an initial piece of E§n+l iteration) and the E§n/ .ll§n construction, we use the same ideas with the obvious modifications. The (n - 1) Back and Forth Property for E~/ .ll~ Implies (5.2.3.) (n ~ 2). The key point here is the following: Lemma 5.2.8.Suppose we have a E~ iteration Q 17 and formula <I>( ) in E~-l together with a condition q E Q 17 name A for a subset of V x:+l such that 0 q I ~ "V K F <I>(A)." Q If 8 < x: ++ is large enough so that q E Q 17 and 81 QE V 81 for the E~ statement <I> and if i1 : QE A E V 81 and there is a witness in Qf1 Qf+ 81 is a complete embedding as in -+ the first stage of the construction that establishes the n - 1 back and forth property for E~/ .ll~ starting with an initial piece of a E~ iteration, then we get for any .ll~ iteration -140- q,II that extends Qf+ 81 1 i1(q) 11-JJ "VK: F <I>(Ai )." Q We also have an analogous version that starts out with an initial piece of a JI~ iteration. Proof. This will be proved by induction on n ~ 2 and we write down only the proof of the first version of the lemma ( the proof of the second version is entirely analogous.) We begin with the case n = 2. Let <I>(A) _ 3X <p(X,A) where X ranges over V K+ 2 and <pis large enough such that q E QE and A E V 81 QE 81 E5. Now pick 81 < ++ K and there 1s a nice name XE V QE 81 with 0 0 q I ~ "V K: F <p(X,A)." Q Now let q,II be any II~ iteration that extends Qf; then 1 since <p is E5 and i1 : Qf1 Qf1 is a complete embedding. -+ The case n = 3 has already been demonstrated in the proof for o-~/ 11j in 4.2.21. 0 Now assume n ~ 4. Suppose <I>(A) and <p is E 2n_ 3 . We pick 8 1 0 = 3X VY <p(X,Y,A) where X, Y range over V K+ 2 < K: ++ large enough such that q E QE and A E QE 81 81 -141- QE and there is X E V 81 with 0 0 q I ~ VY <p(X,Y,A). Q (5.2.9) We assume towards a contradiction that there is some JI~ iteration QJI that extends Then there is 82 < K ++ and a condition q 1 E QJI 1+81 +82 with q' < i 1 ( q) and ~ 11 y E V Q 1 +61 +62 such that (5.2.11.) q f II _JI -, <p(XO i1 ,YO ,AO i1 ). Q ~E Recall that we can find an extension Q + + of Q E and a complete embedding 81 2 82 81 . ~JI 12: Q1+8 1 +8 2 -+ ~E Q8 +2+8 as in the second stage of the construction that 1 2 demonstrates the (n - 1) back and forth property for E~/ JI~ (starting with an initial piece of a E~ iteration). r o o i2 o 2 ~ E ~ E Claim. i 2 (q) II _E -, <p(X,Y ,A) for any En iteration Q extending Q 8 + 2 + 8 Q 1 2 Proof of the claim: Assume towards a contradiction that we have some E~ iteration -142- QE and 63 < , ;, ++ and a condition q 11 E Qf + 2 + 6 + 6 with q 11 ~ i 2 (q 1) such that 1 2 3 q " II _- E 0 0 i2 ,A 0 ) t.p ( X,Y Q -E Q61+2+62+63 r . . . h 2 an d t h ere 1s a witness m V 1or t e E n- 3 statement t.p. Now proceed as in the 3rd stage of the construction that establishes the (n - 1) back and forth property for E~/ .ll~ (starting with an initial piece of a E~ iteration) and ~.ll find an extension Q 1 + back and forth n - 61 + 62 + 2+ -_ll of Q 1 + 63 61 + 62 2 . Since t.p is En_ 3 and we can go -E 3 times between suitable extensions of Q and 61 +2+62+63 Qf+6 +6 +2+6 , we get by induction hypothesis: 1 2 3 For any .ll~ iteration Q.ll extending Q.ll 1+6 +6 +2+u3 £ 1 Now fix Q.ll as above. that is the identity on Qf+ 2 Recall that there is an isomorphism of 61 + 62 . Q.ll and Q.ll Thus i3 (q 11 ) ~ q 1 and (5.2.11.) and {5.2.12.) together are obviously a contradiction and the claim is proved. D end of proof of the claim. Next fix any E~ iteration QE extending Qf + 2 + 6 . From the claim we obtain 1 2 -143- f O 0 (5.2.13.) i 2 (q) II _E 3Y-, <p (X,Y,A). Q There is an isomorphism of QE with qE that is the identity on Qf1 . Then i2 ( q 1) :::; q and (5.2.9.) and (5.2.13.) give a contradiction. Hence our assumption (5.2.10.) was false and we get 0 i1 (q) II _II \:/Y <p cx\Y,Ai 1 ) Q and the first version of the lemma is proved. □ end of 5.2.8. It is now easy to obtain (5.2.3.) from (5.2.2.) by using this lemma: Assume that (5.2.2) holds. If cI>(A) E~-l then by the second version of the lemma we obtain (5.2.3). If cI>(A) is II~-l then we assume towards a contradiction that for some E~ iteration QE we have a condition q E QE with q I~ "V /'i, F -, cI>(A)." Q Then by the first version of the lemma we obtain a II~ iteration QII and a condition q 1 E QII such that which contradicts ( 5.2.2. ). -144- SECTION fi. o-W /1rg1(m2:'.:3, n2:'.:2). The main ideas for establishing the consistency of ug1 have already been developed in the > 1rg1 (m > 3, n > 2) ui/1ri case. We will write Pa rather than P~a in this section. Let us describe the (m + 2) step iteration that we use at stage A ( where A is Mahlo) in order to make A Eg1 p describable in V A+l Suppose that GA is PA generic over V = L and in V[G A] A is inaccessible and >A A+e = (A+e ) L for € 2:'.: 1 and GCHholds. In the first step we add a sequence (F -y: -y A+(m-1) < A+) where each F-y is a Lipshitz function (2 +(m-1) )n-l -+ 2A . Thus the forcing Q(l) is a A+ product (with full support) of copies of the forcing notion PF where conditions in Pp are functions f such that dom f is a subtree of (2< A+(m-1) t- 1 of size <A +( m -1) and and for f, g E PF we let f < g iff f 2 g. Clearly IQ(l)I , +(m-1) d Q " an (l) 1s -145- <-X+(m-l) closed. Hence if (F 1 : 1 < .x+) is Q(l) generic then in V[G,x,F,] we still have that ,\ is inaccessible,\ +e = (.\ +Ef fore 2 1 and GCH 2 ,\ holds. In the second step we will do an iteration Q( ) (that we call Q in the remainder 2 of this section) which will make a Eg-1 fact true about F I for I even and its negation about F I for I odd. . +m +(m-1) Q will be a certam suborder of Fn(,\ ,2,.\ ). We partition ,\ +m into ,\ + many pieces say (A,: 1 < ,\ +) and C with ,\ + C C each of which has size ,\ +m; then for each 1 < ,\ + we partition A1 into pieces (A~k): 1 $ k $ n - 1) each of which has size ,\ +m. Next for each k E {1, ... ,n - 1} we enumerate a complete sequence of k-tupels of nice Fn(,\ A~k). +m ,2,.\ +(m-1) ) names for a subset of ,\ +(m-1) along the coordinates in (Note that this is possible since Fn(.\ +m ,2,.\ +(m-l)) is ,\ +m c.c. and has size ,\ +m .) The poset Q will add a new subset of,\ +(m-l) at each coordinate in ,\ +m - LJ A~n-l) . At a coordinate a E A~n-l) (for some 1 < A+) Q will add a club set ,<,x+ ~,\ +(m-1) . (1) . (n-1) (1) (n-1) that is disjoint from F 1 (r 1 ,a ,... ,r 1 ,a ) (where (r 1 ,a , ... ,T1 ,a ) is the tupel that appears at coordinate a E A~n-l)) if certain killing conditions are met. If these killing conditions are not satisfied we just force with the trivial poset {O}; i.e., we • (1) • (n-1) save F 1 (r 1 ,a , ... ,r 1 ,a ). The killing conditions for a E A~n-l) where I is even (i.e., the killing conditions in Eg-1) are again given by the graph for .Eg-1 . Similarly the graph for ng-1 tells us -146- whether we kill at some a E A~n-l) where , is odd. Now the graphs for Eg1 (Hg1 resp.) look exactly like the graphs for Eii (Hii resp.) except that the nodes are labeled Ek and Hk instead of Ef and nf. Clearly Q is <,\ +(m- 2 ) closed (because of the cofinality restriction in the definition of conditions in Q(l)) and ,\ +m c.c. (since compatibility in Q agrees with compatibility in Fn(A +m ,2,,\ +(m-l\ An analogous proof as in the oj/1r~ case shows that Q is <,\ +(m-l) Baire. In particular this implies that for each , < ,\ + II V[G F ] ~ ' dom F, = (2 ,\+(m-1) )n - 1 . Moreover the analogue of 4.1.7. can be proved for Q; hence after forcing with Q - - explicitly killed it. Therefore if G is Q generic over V[G ,\ ,F,] we have in V[G ,\ ,F, ,G] for odd 1 < 1,, +: where Q = 3 (Q = 't/ resp.) and t/J says F ,(X 1 , ... ,Xn-l) is stationary (nonstationary resp.) in,\ +(m-l) for odd n (even n resp.). Clearly this is Hg1(F,). For even "f < 1,, + the negation of this statement will hold about F 1 , i.e., a For each "f < ,\ + we can find a code F, C ,\ This uses the fact that (2< +(m-1) for F "f in V[G ,\ ,F, ,G]. ,\ +(m-1) V[G ,F "f ,G] ) ,\ L[G,\] where G,\ C P,\ ~ L,\. Hence we can use the canonical wellordering <L[G,\] on -147- 2< ,\ +(m-1) to do this coding. The steps Q( 3 ), ... , Q( 3 +m- 2 ) will now code each F, ~ ,\ subset S, ~ ,\. This is done in exactly the same way as in the +(m-1) down to a uf (1rf proof. Finally in the last step we add a sequence (C,:, < ,\+)where each C, ~ ,\ is club and C, n {µ < ,\: µ inaccessible Em Here <l> n is the analogue of ( 4.1.10.) for EW. Now we can proceed as outlined in Section 1 and prove II p ,c+l "there are no EW indescribables ~ ,c, If, is nw indescribable, is EW indescribable." ,c The hard part of the proof of 11 P ,c+l 1 ",c is llW indescribable" is again to show (in the .• notation of Section 1) that N[G,c ,N F 1 ,g] is E~-l correct for ,c in V[G,c ,F 1 ,G] - where G,c is the V generic for P,c, F I is the generic for Q(l) of stage ,c of P ,c+l and G is the Q generic of stage ,c of P ,c+l and Np I is the Q(l) generic for stage ,c of Pfl,c) and g is the QN generic for stage ,c of Pj~ ,c). The strategy for this is the same as in the u~ / 71'"~ case; i.e., the key point is that EW / nw has the (n - 1) back and forth property which is proved by the same arguments as in the u~/ 71'"~ case. -148SECTION l- Oracles - The Final Word on Indescribability. In order to state the final theorem we need to introduce the notion of an oracle. An oracle is simply a subset of w that codes a function with domain {(m,n): m ~ 2, n ~ 1} that takes values in {0,1}. The final theorem is (ZFC) Assuming the existence of Eg1 indescribables for all m and n and p given any oracle GJ, there is a poset P GJ E L[GJ] such that GCH holds in (L[GJ]) GJ and Theorem 7.1. o-g1 < 1rg1 if GJ(m,n) = 0 o-g1 > 1rg1 if GJ(m,n) = 1. (7.2.) □ Before defining P GJ (for a given oracle function GJ) we make some observations about small forcing and indescribability. In 1.6. we have already seen that a forcing of size < 1,, cannot destroy the Eg1 indescribability of 1,,, indescribable cardinal 1,,, The same statement is true about a llg1 The proof for this is totally analogous to the Eg1 case. However the reformulation in 1.1. makes it possible to give an even easier proof. To complete the picture we show (cf. Corollary 7.8.) that no poset can create new Eg1 or llg1 indescribable cardinals (for any m, n ~ 1) that are larger than the cardinality of the forcing. First we prove: Lemma 7.3. (ZFC) Suppose-that 1,, is inaccessible and P is a notion of forcing with IPI < K. Let G be a P generic. Then, in V[G] for any X E V 1,,+l' (7.4.) X E V -¢::::::> X ~ V /1. Vs [s E V ⇒ X and for any$ E V 1,,+m (m ~ 2) n s E V] -149- g; e v <=} s; ~ v " vGJ [GJ E v " 1GJ1 s; "' . ⇒. g; (7.5.) n GJ E vJ. Heres ranges of V"' and GJ over V K+m (of V[G]). Proof. To prove the nontrivial direction of (7.4.) assume towards a contradiction that for some condition p* E G and some 0 X E yP we have 0 p* I~ "X f (V),,, /\ Vs [s E V => X 0 n s E V] /\ X ~ V." In V, pick a wellordering of V"' of order type "' and let sega: denote the segment of the first a:-many elements ( a: < "'). We can (in V) for each a: < "' pick Pa: s; p * and xa: E (V),,, with 0 Pa: ,~ X n sega: = Xa: . !Pl < IC implies that there is some p E P with Pa: = p for cofinally many a:. Then let X = u Xa: p If- X =X Pa:=P clearly 0 contradicting 0 - p If- X ~ v. To prove the nontrivial direction in (7.5.) we assume (without loss of generality) m and sup-pose towards a contradiction that for some p* E G and $ in yP 0 p* I~ "$ ~ (V),,,+1 /\ 'r/GJ [GJ E V 0 " 1GJ I s; K • ⇒. g; 0 n GJ E vJ " g; ~ v.,, =2 -150- 0 If for some p** 5 p* p** Ir iffil 5 K, then since IPI < "'we can find '!J" E (V)IC+2 with 0 0 l'!J"I $ "' and p** Ir '!I" 2 g;_ This clearly implies p** Ir g; E V, a contradiction. Thus we can assume 0 p* II- lffil ~ "'· Now we claim: 0 0 p* II- 39J s; $(l9JI = IC I\ \IZ[9J s; Z s; X ⇒ Z ~ V]]. Proof of the Claim: Consider B ~ r.o. (P) and let H be B generic over V with p* E H. Since IBI < "' we can find 9J E yB such that in V[H) l9JHI = IC and q;H s; g;H and implies Now suppose % E yB with q;H s; %H s; g;H; it follows that %H ~ V. Otherwise we 0 can pick Z EV with IIZ = ZII v B OH E Hand then we get for all X E 9J = IIZ = ZII B . IIZ s; $II B E H' v O O O n (V)/f,+1 -151- OH since for X E 9J n (V),.+1 we clearly have IIX E ZII = 1 because 9JOH ~ ZOH = z. V V But this contradicts (7.6). Hence iyH works and the claim is proved. □ end of the proof of the claim By the claim we can fix '11 E VP with 0 0 0 p* If- "9J ~ s; /\ l9JI = Let p** ~ p* and p 0 K I\ 'vZ [9J ~ 0 z ~ s; ⇒ z ~ VJ." f E vP such that ** IL fo. ' 1:1 gr onto ll• .K--+ Then define (in V): 0 9J 'M {X E (V),_+l: 3p ~ p** 3a < K Plf- X = f(a)}. Clearly l9JI = K and p**lf- '11 ~ i(f. Now (in V) wellorder 9J in order type K and for a < K denote by sega the segment of the first a element. Note that for a < K 0 p** If- s; n sega E v. Hence (in V) we can find for each a < K 0 Pa If- s; Pa ~ p** and 9Ja with n sega = 9Ja. Since IPI < K there must be some p ~ p** with p = Pa for cofinally many a. Then 0 p If- "$ n 9J = Pa=P u 9Ja E V" -152contradicting 0 n 9J ¢ v. p If- g; D end of 7.3. We use this lemma to show Lemma 7.7. (ZFC) If 1,,, P, Gare as in 7.3. then in V[G] for any$ EV 1,,+m (where m ~ 1) the formula "$ E V" is Eg1 ($,(V),,,) over V,,,. For m = 1 (7.4.) implies (s ranges over V ,,,) $ E V iff $ Clearly this is For m ~ ~ (V),,, /\ Vs [s E (V),,, ⇒ $ n s E (V),,,]. E! ($,(V),,,). 2 we proceed by induction on m. Suppose $ E V 1,,+m+l; then by (7.5.) (where~ ranges our V 1,,+m+l) Now, by induction hypothesis this is Eg1+l because any ~ ~ V 1,,+m of cardinality ~"' can obviously be coded by some element of V 1,,+m so that the whole formula is Eg1+l D end of 7.7. Remark. Of course lemma is not optimally phrased, but this version already allows us to prove: Corollary 7 .8. (ZFC) If 1,, is inaccessible and P a poset of size < 1,, and G is P generic, then for m, n ~ 1 ( 1,, is Eg1 (.llg1 resp.) indescribable) V[G] implies (1,, is Eg1 (.llffl resp.) indescribable)V. -153- Proof. If <I>(A), where A ~ (V)IC is EW (HW resp.) then by 7.7, in V[G) the formula (<I>(A))V is EW (A,(V)1C) (.llW(A,(V)IC) resp.). Then note that clearly (V)IC ~ VIC (in □ end of 7.8. V[G]). So we can use it as a parameter. We are now turning to the proof of 7.1. Suppose GJ is an oracle and we have Eg1 indescribables for all m, n. We know that in L[GJ) the following picture holds for m ~ 2, n ~ 1: (7.9) · .. < L[GJ) m L[GJ) m L[GJ) m L[GJ) m Un < 7rn < u n+ 1 < 7r n+ 1 < .. · · For the sake of completeness we give a proof of this fact. Proof of (7.9). Fix m ~ 2 and n ~ 1. We work in L[GJ). Let IC be the least .llg1 indescribable. The proof strategy is to find a .llg1 statement <I>(A,IC) with A ~ VIC such that VIC p <I>(A,IC) and any inaccessible A to which <I> reflects is Eg1 indescribable. <I>(A) can be found as follows: We know that IC being the least .llg1 indescribable is Eg1 describable. We fix some A ~ VIC and a Eg1 formula w(A) such that VIC p w(A) and 1l!(A) does not reflect to any inaccessible A < IC and such that the witness in the Eg1 formula W is least in the canonical wellordering <L[GJ) with property that it is a witness for a Eg1 formula ii,' in a parameter A 1 as above. We pick a sufficiently large finite fragment T of ZF + V = L[GJ) such that for any transitive model M of T with GJ E M we have that X E Mand Y <L[GJ) X imply Y E M. -154- Then we take <I>(A,IC) to be the formula 'v' .Al, [A transitive, .Al, FT, IAI = IV 1C+m-il, .Al, E~-l correct for IC, .Al, F "IC is not Eg1 indescribable" . ⇒ . .Al, F "VIC F 'li"(A)"]; <I> is clearly 1Ig1 over VIC and by the choice of T we get VIC F <I>(A,IC ). If A < IC 1s n VA ,A), then A must be Eg1 indescribable because we inaccessible and VA F <I>(A cannot have VA F 'li"(A n VA) by our choice of 'li"(A). Thus <I> has the properties that □ end of the proof of (7.9). we want .. Actually the proof that we just gave works for a large class of inner models. The key point is that the inner model under consideration ( or at least its truncation up to the first measurable) must have a certain "good" wellorder. We now resume the proof of 7.1. Working in L[<:f] we define form ~ 2 and n ~ 1 the poset P;1'n to be the trivial poset if <:f(m,n) = 0. If ~(m,n) = 1 then we use the exact same definition that we used for Pg1 ( with IC = L[<:f] 7rg1 ) except that we replace L by L['!f] and we do something only at Mahlo stages ~ L[<:f]ug1 . Then we let TI m~2,n~l -155- We must show that (7.2.) holds. So fix m' 2:'.: 2 and n' 2:'.: 1. Note that Pg: ~ P 1 x P 2 d p _ pm ',n ' d P m,n g: an an P 3 rr 2 ~ g: m<~' or , m=m An<n First assume that 'J(m',n') = 1. rr m>r;n' or , m=m /\n>n We know from Section 1 that for each a < L[<Jl u m' P has a <a closed, dense suborder. Hence P is < L['Jl um ' Baire. n'+l 3 3 n'+l Thus if G 3 is P 3 generic over L[<J], (L[<J,G 3 ])L[<Jl = (L['J])L['Jl , m un'+1 implies that in L[<J ,G 3 l L[<Jl,r!T\, is still n indescribables above L[<Jl1rrn,'. n m' n' of L[<Jl. with the Pg: ' , This m un'+1 nm,' indescribable and that there are many Em,' n n 3 It implies also that L[<J,G l's version of Thus if we denote by ,,_ P~}1' ,n' agrees ' the least E nm', indescribable > m' indescribable, ,,_ ' is E m', indescribable and there are no E m', II , n n n indescribables below L['Jl1rrn,'. n Clearly IP 1 1 < L[<Jl m' u , . n Hence by 7.8. for any G 1 that is P 1 generic over L[<J,G 3 ,G 2 l we obtain that m L[<J,G 3 ,G 2 ,G 1l there are no E:,' indescribables L[~] ,r m'] , and clearly we cannot have any E m' , indescribables below n n L[<J]urn,'. Also by IPil < L[<J]um' we get that L['J]1rrn,' is still n n' n ,,_, is still nm,' indescribable and n Em,n '. indescribable in L[<J,G 3 ,G 2 ,G 1l. This shows that for 'J(m',n') = 1 we -156have ' Now we assume that ':F(m',n') = 0. Then P':f ~ P 1 x P3. The <o-11} Baireness of n +1 P 3 implies I L[':f) m' - L[':f) a-,< m' L[':f] m' m' 1Tr=1T, I P 3 u,n n n n L[':f) m' u I together with the observation that no generic extension of L[':f] can n ' L[':f) ' have any .llll} indescribables < um yield that n n' Another factoring argument shows that for any cardinal µ we get 11~':f) GCH. ':f µ+ Hence -157BIBLIOGRAPHY (Baumgartner, 1983] Iterated Forcing, in Surveys in Set Theory, A.R.D. Mathias, ed., London Mathematical Society lecture notes, pp. 1-59, 89. [Dodd, 1982] The Core Model, London Mathematical Society, lecture notes, 61. [Drake, 1974] Set Theory, North Holland. [Hanf-Scott, 1961) Classifying inaccessible cardinals, Notices Amer. Math. Soc. 8, p. 445. [Jensen, 1967] Lectures at Bonn and at Oberwolfach. [Kunen, 1980] Set Theory, North Holland. (Levy, 1971) The sizes of the indescribable cardinals, in Axiomatic Set Theory, D. S. Scott, ed., Proc. Symp. Pure Math, 13 (1), Amer. Math. Soc., Providence, R.I., pp. 205-218. [Martin-Steel, 1988] Projective Determinacy, Proc. Natl. Acad. Sci. USA, 85, pp. 6587-6591. [Mitchell, 1979] Hypermeasurable cardinals, in Logic Colloquium '78, M. Boffa, D. Van Dalen & K. Mc Aloon, eds., North Holland, pp. 303-316. [Moschovakis, 1976) Indescribable cardinals in L, JSL 41, pp. 554-555. [Silver, 1971 J Unpublished notes on reverse Easton forcing. [Solovay-Tennenbaum, 1971) Iterated Cohen extensions and Souslin's problem, Ann. Math., 94, pp. 201-245. [Vaught, 1963] Indescribable cardinals, Notices Amer. Math. Soc, 10, p. 126.