A BOOLEAN-VALUED APPROACH TO THE LEBESGUE MEASURE PROBLEM by WILLIAM /SANDBERG MAITLAND B_.Sc, University of B r i t i s h Columbia, 1973 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n 4 THE FACULTY OF GRADUATE STUDIES (Department of Mathematics •) We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA December, 1976 © William Sandberg Maitland, 1976 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced deg ree a t the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t ha t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Depar tment o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Depar tment o f Mathematics The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date January 15 , 1977. i Abstract We l e t : ZF = the Zermelo-Fraenkel axioms of set theory without the Axiom of Choice„(AC) . ZFC = ZF + AC . I = " There exists an inaccessible cardinal " . SV = " Every set of reals definable from a count able sequence of ordinals i s Lebesgue meas-urable ". DC = the Axiom of Dependent Choices. LM = " Every set of reals i s Lebesgue measurable In 1970, Solovay published a proof by forcing of the following r e l a t i v e consistency r e s u l t : Theorem If there exists a model M of ZFC + I, then there e x i s t extensions JMC [G] and DN of JMC such that: (a) JMC [G] |= ZFC + ¥ (b) 3N [= ZF + DC + LM . Boolean-valued techniques are used here to retrace Solovay's proof on a d i f f e r e n t foundation and prove the following r e s u l t : Theorem Let IK be a non-minimal standard t r a n s i t i v e model of ZFC + I. Then: I V (a) IK |= th e r e i s a model of ZFC + ¥ (b) IK |= th e r e i s a model of ZF + DC + LM . V Contents Abstract Acknowledgements Introduction 1 1 1 v i 1 Section 0 : Section 1 : Section 2 : Section 3 : Section 4 : Section 5 : Section 6 : Conclusion Bibliography Boolean-valued models and generic extensions 7 The Lebesgue Measure Problem and the Axiom of Choice 42 Some model theoretic properties of Lebesgue measure 4 7 The random reals 63 The Levy algebra 71 The model of Levy 91 The model of McAloon 103 114 116 v i Acknowledgements My sincere thanks go to Dr. Andrew Adler, not only for his suggestion of the topic of t h i s thesis and willingness to oversee the work, but e s p e c i a l l y for his encouragement and patience during the long course that has lead to i t s completion. His advice and insights have had a decisive influence on t h i s presentation of the topic. I wish also to acknowledge the support the Mathematics Department has given me. Special thanks are due to Mrs. Anne Rogers for her hard work and diligence i n typing the manuscript. I am grate f u l to Mr. Ralph Pudritz for his helpful com-ments on the manuscript, and to Mr. Peter Lomax and Ms. Miriam Silbermann for t h e i r help with tr a n s l a t i o n s . And l a s t l y , my acknowledgements go to the many who have shown f r i e n d l y concern and encouragements, not the least of whom i s Mr. Anatole Lebovich. 1 Introduction Under what hypothesis can we consistently assume that a l l sets of reals are Lebesgue measurable? This i s the essence of the Lebesgue measure problem. Here we present a recent set t h e o r e t i c a l investigation of t h i s problem due to Solovay. Lebesgue measure i s countably additive and t r a n s l a t i o n invariant. Under the hypothesis that the reals can be well-ordered, these two properties allowed early researchers ( e.g. V i t a l i , Bernstein ) to construct various sets of reals which are not Lebesgue measurable. Set functions with domain the powerset JP (3R ) of the r e a l s , which drop one of the above two constraints, have been the focus of some attention. But such would-be measures cannot compete with Lebesgue measure for i t s central role i n modern r e a l analysis. If we must accept the presence of non-measurable sets i n ordinary analysis, then i t would be useful to know how much t h e i r existence depends on the Axiom of Choice (AC). Solovay's research, published in 1970, shows that i t i s consistent with the Zermelo-Fraenkel axioms of set the-ory (ZF) and the P r i n c i p l e of Dependent Choices (DC) to assume that a l l sets of reals are Lebesgue measurable (LM), given the consistency of ZF+AC together with the statement (I) that a ( strongly ) inaccessible cardinal e x i s t s . This main theorem of Solovay indicates that i t i s impossible to prove the existence of non-measurable sets from the ZF 2 axioms with DC, provided that the theory ZF+AC+I i s con-si s t e n t . Hence the existence of non-measurable sets i s dependent on some form of AC which i s stronger than DC. To prove t h i s r e l a t i v e consistency r e s u l t , a model jN of ZF+DC+LM i s constructed from a model M of ZF+AC+I. Solovay's construction uses an unramified form of the forcing method, e s s e n t i a l l y due to Cohen. His main inn-ovation i s the use of Borel sets of po s i t i v e measure to replace Cohen's f i n i t e forcing conditions. Solovay has conjectured that the hypothesis regard-ing the consistency of I i s dispensable, though no proof has been forthcoming as yet. In 196 9, Sacks published an account of another Solovay r e s u l t , using ramified langua-ges and a measure theoretic forcing argument. He demon-strated that i f ZF i s consistent, then ZF+DC+ "there ex-i s t s a countably additive, t r a n s l a t i o n invariant extension of Lebesgue measure on jP'(3R)" i s consistent. The state-ment i n quotes i s weaker than LM, but i t s consistency re-quires no hypothesis regarding I. In 1965, Solovay and Scott, and independently Vopenka, noticed that forcing arguments could be translated into constructions involving so-called Boolean-valued models. Our presentation of Solovay's 1970 research begins with a resume of t h i s method of constructing a generic extension of a given ground model without forcing. A close examina-t i o n of [23] ( e.g. pp. 31 - 8, pp. 49 - 50 ) leaves no 3 doubt that Solovay's o r i g i n a l conception of his work on the Lebesgue measure problem was in terms of Boolean-valued models, rather than the c l a s s i c a l forcing arguments which predominate his f i n a l published account. The use of Boolean-valued methods provides a more natural and i n t u i -t i v e development of Solovay's ideas. In our i n i t i a l sec-t i o n , we have concentrated on those aspects of Boolean-valued models which have a d i r e c t bearing on Solovay's 1970 constructions, and have t r i e d to improve and complete some of the standard proofs i n t h i s area. In Section 3 we describe Solovay's notion of a random r e a l , which i s his main innovation mentioned above and the notion which motivated the Solovay-Scott development of Boolean-valued models. In t h i s , we have started with Solo-vay's d e f i n i t i o n , and translated his development into the language of Section 0. A d i f f e r e n t development ( based on D e f i n i t i o n 3.5 ) i n the same Boolean language can be found i n [9]. Lemma 3.8 establishes the equivalence of the two approaches. In t h i s exposition we have endeavored to combine the i n t u i t i v e c l a r i t y of the Boolean-valued approach with a rigorous foundational background. Two points are often glossed over i n presentations of t h i s type. It i s often not s p e c i f i e d whether the models involved are sets or classes. This lack of precision opens any treatment of definable sets to the p o s s i b i l i t y of set t h e o r e t i c a l para-4 doxes. To combat t h i s , we consider a l l our model construc-tions to take place within a model which i s a set, rather than within the "real world" of Solovay. The second s t i p -u l a t ion i s that our ground model i s countable. The reason-ing behind t h i s i s explained in Section 0. These two points ensure that our model constructions rest on an e x p l i c i t and correct foundation. The concluding sections describe the two main models of Solovay, whose o r i g i n he a t t r i b u t e s to Levy and McAloon. The l a t t e r model i s usually defined v i a the eight funda-mental Godel operations ( see [27] ), or by an extended form of the Reflection P r i n c i p l e ( see [15] ). Because of our adherence to models which are sets, we have been able to employ Godel-numbering to present a simpler construction needing much less background. The LeVy model i s construc-ted from an unpleasant Boolean algebra L which i s the sub-je c t of Section 4. We have f i l l e d i n some of the necces-sary technical work in t h i s LeVy algebra that i s avoided elsewhere. By a c l a s s i c a l algebraic argument, a theorem of Jensen ( [9], p. 76 ) i n d i r e c t l y implies that L i s homo-geneous. In our Lemmas 4.8 and 4.10 we have modified Jensen's theorem considerably, providing a d i r e c t proof of the homogeneity of L. Another often neglected point i s the problem of f i r s t -order d e f i n a b i l i t y of sets. In addressing t h i s topic, we have included relevant material here which i s usually only 5 alluded to. In Section 5, for example, we introduce the notion of uniform d e f i n a b i l i t y . This has other names in the l i t e r a t u r e ( e.g. " s p e c i f i a b i l i t y " , [4] ), but there seems to be no standard usage. In t h i s , we d i f f e r from Solovay's development which uses his M - J R - d e f i n a b i l i t y ( [23] p. 41 ). The somewhat informal use of d e f i n a b i l i t y i n Section 5 i s formalized i n Section 6. Here we show that the source of our d e f i n a b i l i t y problems i s Richard's paradox. While the McAloon model substantiates the main theorem of Solovay quoted above, the Levy model gives an equally in t e r e s t i n g secondary theorem of Solovay: If ZF+AC+I i s consistent, then i t i s consistent with ZF+AC to assume that every set of reals definable from a countable sequence of ordinals i s Lebesgue measurable. Using the formulas of set theory, we cannot e x p l i c i t l y define a non-measurable set without an uncountable sequence of ordinals. These notions are made precise i n Sections 5 and 6. Section 2 deals with some absoluteness properties of Lebesgue measure. For t h i s work we have selected a notion of absoluteness due to Shoenfield that i s naturally adap-ted to the model extension process. In most other respects, the development of t h i s section follows Solovay. We d i f f e r from the Solovay development by f i r s t establishing that the property of being a set of Lebesgue measure zero i s absolute. The main lemma of Solovay ( Lemma 1.6.4, p. 31, 6 [23] ) follows e a s i l y as our Corollary 2.25. Some prefatory remarks on the use of the Countable Axiom of Choice (AC^) i n analysis are included i n Section 1. Our aim here i s to emphasize that the r e a l impact of DC on ordinary analysis i s through AC^. Our set theoretic and model theoretic notation and nomenclature i s standard for the most part, being consis-tent with that of [1] and/or [14]. 7 Section 0 : Boolean-valued models and generic extensions Our approach to the proof of Solovay i s based on the concept of a Boolean-valued model of set theory. We st a r t here with a f a i r l y general treatment of t h i s subject, then in l a t e r sections select the l i n e of application that leads to the Solovay r e s u l t . To begin, we r e c a l l some background. As usual, ZF i s used to stand for the Zermelo-Fraenkel set theory, i . e . the c o l l e c t i o n of theorems that follow from the Zermelo-Fraenkel axioms ( less the Axiom of Choice ). ZFC denotes the f u l l c o l l e c t i o n of theorems following from ZF and the Axiom of Choice (AC). For t h i s section the terms "set theory" and ZFC w i l l be used synonymously. A model of set theory i s an ordered pair M = (M,E), where M i s a set and E i s a binary r e l a t i o n on M ( i . e . E c M2 ) which s a t i s f i e s a l l the axioms of set theory as the interpretation for ' e 1 . The symbolism DM j= <J), which says that 3MC s a t i s f i e s <j>, can be defined by induction on the complexity of cf) ( see [1] ) . M i s referred to as the universe or underlying set of M. In s t i p u l a t i n g that M i s a set rather than a class, we w i l l avoid the danger of set theoretic paradoxes which might otherwise impair the model construction process. However, many popular versions of the theorems we w i l l use assume M to be a clas s , and care must be taken when we meet such theorems. 8 D e f i n i t i o n 0.1 (a) A binary r e l a t i o n R i s well-founded i n a set H <= dom(R) i f there i s no se-quence fx ) cr H such that x n R x holds ^ n n+± n for each n e w . (b) A model M = (H,R) i s extensional i f for a l l x, y, and z i n H, ( zRx -H- zRy ) -> ( x =' y ) . (c) A model M = (H,R) i s standard i f R <= H 2 H e . (d) A model M = (H,R) i s t r a n s i t i v e i f H i s a t r a n s i t i v e set, i . e . for each x e H, x c: H . In 0.1 (c) above, we assume that there i s a "real world" of sets, and that e i s the natural membership re-l a t i o n . The statement that ZFC has a model implies the state-ment that ZFC i s consistent. The l a t t e r of these state-ments i s unprovable i n ZFC ( [3], p. 56 ). So i n order to proceed very f a r with the set t h e o r e t i c a l manipulation of the models defined above, i t becomes convenient and some-times necessary to add some new axiom to ZFC which asserts t h e i r existence. [3], p. 78 discusses t h i s . The following i s a r e l a t i v e l y strong form of model existence axiom, and w i l l be adequate for our purposes. Axiom A There i s a set H and a binary r e l a t i o n R well-9 founded on H, such that 3HE = tensional model of ZFC. (H,R) i s an ex-Any t r a n s i t i v e model i s extensional ( see [9], p. 21, and note that t h i s proof i s v a l i d for our d e f i n i t i o n of model ). For any model JHE = (H,R) s a t i s f y i n g Axiom A, the Mostowski Collapsing Theorem ( [9], p. 27 ) guarantees the existence of a unique standard, t r a n s i t i v e model IK = (K, K2iVc) which i s isomorphic to I I . To see that 3K i s t r u l y a model, we must keep i n mind that the isomorphic copy of a set i s also a set ( by the Axiom of Replacement ). This gives us the following more useful form of Axiom A. Axiom A' There i s a set K such that 3K = (K,K2Ae) i s a ( standard ) t r a n s i t i v e model of ZFC. By the Axiom of Regularity we know that K 2Ae i s well-founded ( [3], p. 54 ), and so the two statements A and A' are equivalent. Axiom A implies the existence of a minimal standard t r a n s i t i v e model JM0 of ZFC; one that i s countable and i s a submodel of a l l other standard t r a n s i t i v e models of ZFC ( [3], p. 83; [24], p. 197 ). M 0 has no standard proper submodels which are t r a n s i t i v e . Since M Q does not s a t i s -fy A,-Axiom A cannot be proved from the other axioms of ZFC ( [4], p. 110; c f . [26], p. 83 and [9], p. 37 ). The upward Lowenheim-Skolem Theorem c e r t a i n l y allows 10 us to pick K uncountable. We do t h i s to prevent JK = M 0 . From t h i s point we f i x t h i s JK , writing e for K 2 f i E . . A l l further models we w i l l consider are understood to s a t i s f y the condition that t h e i r universes belong to IK . Because K i s a set, the downward Lowenheim-Skolem Theorem allows us to construct, within ZFC, t r a n s i t i v e submodels of JK ( [3], p. 18, c.f. p. 79, where the problem of models with class universes i s discussed ). By a suitable argu-ment, one such model JM i s countable and has countable rank 1 ( [4], p. 110 ), hence M e K. We f i x JM = (M,M2Ae), and c a l l i t the ground model. By standardness and t r a n s i t i v i t y , ordinals i n IK and 3M are ordinals i n the r e a l sense. The class of ordinals i n IK turns out to be the least ordinal not i n JK ( [24], p. 197 ). We now turn to the topic of Boolean algebra, begin-ning with the d e f i n i t i o n . D e f i n i t i o n 0.2 B i s a Boolean algebra i f B = (B,•,+,-, 0,1) where B i s a set, • and + are binary operations on B, - i s a unary operation on B, and 0 and 1 are d i s t i n -guished constants i n B, a l l of which s a t i s f y : 1 T r a n s i t i v i t y guarantees the existence of a rank func-t i o n ( [3] , pp. 68-9 ). 11 (a) X + y = y + X , x . y = y • X • (b) X + ( y + z ) = ( x + y ) + z X • ( y • z ) = ( x . y ) • z • (c) ( X + y ) . z = ( x . z ) + ( y • ( X • y ) + z = ( X + z ) • ( y + (d) X + X = X r Y • y = y • (e) X + (--x) - 1 , x . (-x) = 0 • (f) - ( X + y ) = -x . -y - ( X • y ) = -x + -y • (g) - (-x) = X • We note that B i s p a r t i a l l y ordered by the r e l a t i o n : x >^ y i f f x = y + x . With t h i s p a r t i a l order, x + y corresponds with sup(x,y) = i n f [ u : u :>_ x, u >_ y ] , and x-y corresponds with in f (x,y) = sup [ u : u £ x, u <_ y ]. Generalizing t h i s notion, we write EA for sup (A) and IIA for i n f (A) , when A <= B. I t follows that EB = 1, and TIB = 0. It i s conven-ient to adopt the convention: Z0 = 0 and J10 = 1 . D e f i n i t i o n 0.3 (a) A Boolean algebra B i s complete i f for each A c B, EA and HA e x i s t , and EA s B and IIA e B. (b) A Boolean algebra B i s M-complete i f B e M, and for each A cr B: A e M implies EA e B and IIA e B. 12 There i s no problem regarding the existence of Boolean algebras i n models. Since any f i e l d of sets ( e.g. the power set JP (x) of x ) i s a Boolean algebra, each model abounds i n Boolean algebras. If B i s a Boolean algebra in M, then i t i s clear that B i s a Boolean algebra i n JK . We need not be concerned then, about losing Boolean alge-bras when we move from a given model to a more incl u s i v e model. However, i t i s quite conceivable that an incomplete Boolean algebra exists which i s complete i n a certain model THE simply because the A cr B for which LA / B do not belong to H. An JM-complete Boolean algebra i s therefore not necessarily a JK-complete Boolean algebra. For the remainder of t h i s section we w i l l consider B to be a fixed JMC-complete Boolean algebra. Without danger of confusion, we w i l l write B for both B and i t s under-l y i n g set B, and write JMC i n places where i t s universe M i s understood ( e . g . x e JMC ) . Two processes w i l l now be dealt with. The f i r s t i s B the construction of the Boolean-valued model JM from M and B. B The Boolean-valued model JMC e JK may be thought of as a generalization of the ground model JMC, where set theo-r e t i c statements may be evaluated for t h e i r "degree" of truth. More precisely, where c l a s s i c a l l o gic allows only two truth values, the Boolean-valued model JMC assigns as truth value a member of the complete ( i n JMC ) Boolean algebra B to each statement. This explains the name Boolean valued model. If B i s the two-elernent algebra de-noted {0,1} , the notion of Boolean-valued model reduces to g the c l a s s i c a l notion of model. We define JMC from within M, by induction on the ordinals less than Q-^-r the least ordinal not i n JMC. De f i n i t i o n 0.4 JMCB = {0} B B M = U JMC0 , i f a i s a l i m i t o r d i n a l . B ^ M a + ^ = { x : x i s a function, dom(x) c B JMC^ , rng(x) c B } M B = U JM B * a < 9 M g Notice that each element x of M must by induction g belong to for some least a. This a we may c a l l the g rank p (x) of that p a r t i c u l a r object i n JMC . Even though we are working within the ground model, g i t does not follow that JMC e JMC, and i n general t h i s i s fa l s e . There i s , however, a concrete way of envisioning g JMC as being inside JMC . This i s done v i a the following v B embedding functor : JMC —>- JMC , defined by t r a n s f i n i t e induction on p(x). V D e f i n i t i o n 0.5 (a) 0 = 0 v B (b) for each x e JMC, we have x e JMC , with dom(x) = { y : y e x }, and x(y) = 1 for each y e x. 14 Notice that p(y) < p(x) i f y e x, so that x i s indeed defined i n terms of elements of lower rank. The v-functor i l l u s t r a t e s each set x e M as a spe-v B c i a l i z e d c h a r a c t e r i s t i c function x e ML" . Because each V y e x i s also a set i n M, y i s also a c h a r a c t e r i s t i c func-V V t i o n of t h i s type, and so x becomes a composition of charac-t e r i s t i c functions on sets of c h a r a c t e r i s t i c functions. The rank p(x) serves to indicate how long t h i s process has gone on. It i s clear that other function-objects ex i s t i n M whose ranges include values other than 1. These of course have no pre-image by v among the sets of M, but they show that the M construction enables the handling of objects which may be s e t - l i k e to varying degrees. This presents us with the p o s s i b i l i t y of considering some of these ob-jects s e t - l i k e enough to combine with the sets of M, thus forming a new, more i n c l u s i v e model of ZFC. This i s the subject of the l a s t portion of t h i s section. It i s possible now to define a Boolean value ftfjCx^, .. ... ,xn) ] e B for each formula cf> of n free variables, and each x,, ... ,x e M . These Boolean values behave l i k e 1 n the conventional truth values of f i r s t order predicate c a l -culus, but since they belong to the M-complete Boolean algebra B, thay extend our notion of semantics beyond the usual d u a l i t y of truth (1) and f a l s i t y (0). The Boolean values I x e y ] and j x = y ] are defined for x, y e M by t r a n s f i n i t e induction on the lexicograph-i c a l ordering ( p(x), p(y) ) ( i . e . the ordering defined by: (a,3) > (S,y) i f f a > S or a = 6, 3 > Y )• D e f i n i t i o n 0.6 (a) [ x e y I = (b) II x = y I = z ( y ( z ) - i z = x ] ) , z e dom(y) n ( - x ( z ) + I z " £ y 1 ) z e dom(x) • n ( -y(z) + I z e x ] ) . z e dom(y) For a discussion of the form and e f f i c a c y of the above and similar d e f i n i t i o n s , see [17], pp. 41 - 4, and [25], pp. 121 - 2. Having defined H cj> J for cj) an atomic formula, we ex-tend the d e f i n i t i o n to include any set theoretic formula. D e f i n i t i o n 0.7 (a) (b) (c) (d) (e) I i * 1 = [ Cf> & ty ] I * v ty ]] II * - IP 1 I (vx)4> i| I * 1 1 cj) l-l ty I i (j) i + i ty i -I • 1 + I iM n B l <j>(x) ] x e M (f) I (ax)cf> ]] = Z B E cf)(x) TJ X £ M The M-completeness of B ensures that 0.6 (a), (b) and 0.7 (e), (f) are well-defined. The following i s a t r i v i a l but useful consequence of the above d e f i n i t i o n s . 16 Lemma 0.8 I a) J < I n> ] i f f [ <|> ->- u> ]] = 1 A series of lemmas now follows, which give several useful r e l a t i o n s concerning the Boolean values of some s p e c i f i c formulas. The proofs are straightforward, and are usually accomplished by t r a n s f i n i t e induction on ( p(x ) , p(y) ). A sample proof accompanies the f i r s t of these lemmas. Lemma 0.9 (a) I x = x ] = 1 . (b) x(y) < I y e x 1 (c) [ x = y J = il y = x ] . Proof: Suppose (a) to be true for any x s a t i s f y i n g p(x) < y . Let p(x) = y now. By d e f i n i t i o n : (i) [ x" = x 1 = II (-x(y) + I y e x I ) . y e dom(x) For each y e dom(x): ( i i ) E y e x ] = £ ( x (u) -I u = y 1 ) u e dom(x) > x(y) • ily = y ] = x(y) • 1, by hypothesis, as p(y) < y . Since x(y) i s defined only where y e dom(x), (b) follows. Substituting for [ y e x ] i n ( i ) , we have: K x = x ] 1 n (-x(z) + x(z) ) = 1 . z e dom(x) Therefore: x = x = 1 for p(x) = y . Calculating d i r e c t l y : ii 0 = 0 1 = 1 ( the Boolean infimum of the empty c o l l e c t i o n i s 1 ), so (a) follows by t r a n s f i n i t e induction. (c) i s v e r i f i e d d i r e c t l y from the d e f i n i t i o n . The next three interdependent statements are proved simultaneously by t r a n s f i n i t e induction on ( p(x ) , p(y) ) ( see [25], p. 123 ). Lemma 0.10 (a) | x = y l ' I x e z J ^ I y e z l (b) t x e z 1 • I z = y I < I x E y I . (c) I x = y ] • I y = z 1 < I x = z } . The lemma below follows by induction on the complexity of cj), using the fact that the previous lemma establishes the r e s u l t for atomic formulas. Lemma 0.11 I x = y 1 • II a> (x) II < I <j> (y) J . Lemma 0.12 (a) [[ ( ay e x)f(y) 1 = E (x(y)«tt o) (y) 11) y e dom(x) (b) I (Yy e x)tj>(y) 1 = n (x(y)-[ o) (y) ] ) y e dom(x) Proof: See Def i n i t i o n 0.13 [25], p. 125 . g Let x, , ... ,x e M . <b (x, , ... ,x ) 1 n 1 n i s said to be v a l i d i n M i f : [ Q) ( x l f ... ,x n) ] = 1 , in which case we write: g JMC (= <[) ( x 1 f ,x n) . 18 This notion of v a l i d i t y sets the stage for two of the most important re s u l t s of t h i s section. Theorem 0.14 Every axiom of f i r s t order predicate g calculus with i d e n t i t y i s v a l i d i n JMC . Those formulas obtained by rules of i n -ference of f i r s t order predicate c a l -g cuius from formulas v a l i d i n M , are g themselves v a l i d i n JM . g Theorem 0.15 Every axiom of ZFC i s v a l i d i n JMC . g Corollary 0.16 JME i s a model of ZFC ( i . e . every theo-g rem of ZFC i s v a l i d i n JMC ) . No proof w i l l be given here for 0.14 as the usual com-putational proof ( see [25], pp. 60, 124, and [17], pp. 36 - 51 ) i s unaffected by our d e f i n i t i o n of model. Theorem 0.15 i s also standard, but i t i s worthwhile to look at some aspects of i t s proof, p a r t i c u l a r l y those which surface as techniques i n l a t e r proofs. This sele c t i v e approach to 0.15 i s ca r r i e d out i n the next series of lem-mas . g g We define the Boolean-valued singleton {x} , for x e JMC , B B as follows: dom({x} ) = {x} ; {x} (x) = 1 . Hence B B B {x} e JMC , and for p (x) = a, we have p({x} ) =ot + 1. In B B general, {x} and {x} are d i s t i n c t , however I {x} = {x} 1 = 1 ( see Lemma 0.30 ). 19 Lemma 0.17 For each S c M , S e M, there i s a T e M such that I x e T H - 1 for each x e S. Proof: We take the Boolean sum of functions T = Z { x l B , i . e . dom(T) = S ; x e S T(x) = (x) (x) = 1 , for each x e S. From 0.9 (b) we have I x e T J =1, for a l l x e S. B B Note that T e M since p(T) = sup ((x) ), x e S which exists since S e M. The v e r i f i c a t i o n of 0.15 proceeds one axiom of ZFC at g a time. The M - v a l i d i t y of some of the axioms of ZFC i s a matter of a basic computation. Our previous lemmas re-duce the validations of the Axiom of Extensionality ( see [17], p. 50 for a proof that can be adapted to our founda-tions ), and the Axiom of Regularity ( [25], p. 89, [9], p. 56 ) to t h i s computational l e v e l . S l i g h t l y more sophisticated are those validations which are a consequence of 0.17. These include the v a l i d a -tions of the Axiom of Pairing and the Axiom of Unions, whose c l o s e l y related proofs ( [9], p. 55 ) are immediate. The next few lemmas also use the 0.17 strategy. A function F: 8 ^ . *-• B i s nondecreasing i f F(a) £ F ( 3 ) whenever a < 3 , and i s eventually constant i f there exists an ordinal y such that for a l l 3 > y, F ( 3 ) = F ( y ) . 20 Lemma 0.18 For each formula cf> of set theory, the function F (a ) = 1 £(}) (x)J X £ M a i s nondecreasing and eventually constant. Proof: For increasingly larger ordinals 3 , F (3) i s a Boolean supremum taken over increasingly g larger sets JMQ , hence F i s obviously non-» p decreasing. We define a function H: B *• 0__ by: H(a) = in f [ 3 : a < F (3) ] . Since B e M, an ordinal y exists which i s the supremum of the image of B by H. For each 3 > y , F (3) = F (y) . The fact that B i s a set i s c r u c i a l ; neither the Axiom of Replacement ( 0.19 ), nor the Axiom of Power Set ( 0.21 ), g nor the Maximum P r i n c i p l e ( 0.2 6 ) hold i n some 3M where B i s a proper class ( [25], p. 196 ). Lemma 0.19 For each formula o) of set theory: M B (=(Vx) (3y) (Vu e x) [ (3v)cj>(u,v) + ' (3v e y) cj) (u,v) ] Proof: Let x e ]MCB. The function F (3) = £ D Io>(ufv)l v e 3MC D p i s eventually,constant, by 0.18, for each u £ dom(x). This enables us to define the function: g(u) = i n f [ a : V3 > a , F (3) = F u ( a ) 1 f o r each u £ dom(x). We may write: 21 Z B.I<|>(u,v)] •= . 2 E <M.u,v).. 1. g (u) g Following 0.17, we l e t dom(y) = V.U ^ / } u e dom(x) g g = M , where v = sup g(u), and we set V u e dom(x) y(z) = 1 for a l l z e dom(y). For a chosen g g x e M , we have constructed a set y e M such that for each u e dom(x): I (3v)(J)(u,v) •*• (3v e y)c|)(u,v) ] E |[cHu,v)]] + E B |[(j)(u,v)] v e M v e - E g E(j)(u,v)U + £ . [<(>(ufv)]I V £ 3MC V e M . . g (u) B B Therefore, for each x e M there exists y £ M s a t i s f y i n g : | (Yu £ x) [ (3v)cf)(u,v) •* (3v £ y)cj)(u,v) ] 1 n [ -x(u) + n(av)(j)(u,v) ^ (av E y)<f»(u,v)j] u £ dom(x) n ( -x(u) + 1 ) = 1 . The r e s u l t u £ dom(x) now follows. The above lemma validates one form of the Axiom Schema of Replacement. It i s well known that the Axiom Schema of Separation i s a l o g i c a l consequence of the Replacement Axiom. We could i n f e r then, by way of 0.14, that the Axiom g of Separation also holds i n M . The following lemma i s a more useful statement of the v a l i d i t y of the Separation 22 Axiom. Its proof i s a basic c a l c u l a t i o n , so i n view of the above discussion we w i l l omit i t (. see [9] , p. 55 ) . Lemma 0.20 For each x e M and formula o>, there i s a set g y e ME s a t i s f y i n g : dom(y) = dom(x) , and: I ' (Vz e y) ( z e x & o>(z) ) I = 1 , II (V Z e x) ( <|>(z) -> z e y ) 1 • = 1 . The main application of the above lemma i s i n the next r e s u l t . g Lemma 0.21 M \= (Vx) (3y) (Vu) ( u cz x ->• u e y ) B B Proof: Let x, u e M . From 0.20, there exists v e M sa t i s f y i n g : dom(v) = dom(x) , I v = u A x ] =1. For each t edom(x) we have: [ t e v j = [ t e u l - i t E x ] , thus, I t E v l < I t e x l g Following 0.17, we define y e M as follows: dom(y) = {' z : dom(z) = dom(x), t e dom(x) I t E z l < I t e x l } , and y(z) = 1 for z e dom(y). We know that y ^ 0 when x ^ 0, since v e dom(y). Furthermore: I u c x l = I u c x l ' [ v = u ( l x I < I u = v l , so that: I u c x I < I I u = z I = I u e y 1 . z e dom(y) OH the other hand: 23 1 u e Y 1 = I tt z = u H z e dom(y) (i), = I I z = u M z c x l , z E dom(y) since z £ dom(y) implies I z c x 1 = 1 0.11 gives (i) < Z ttucxl=lucxl. z £ dom(y) B B Given any x E M , we have produced a y £ M s a t i s f y i n g I u c x 1 = |[ u e y I , for each g u £ M . The r e s u l t now follows. Lemma 0.21 establishes the v a l i d i t y of the Axiom of g Power Set i n 3MC . The Axiom of I n f i n i t y may be validated by various s t r a -tegies. Jech sketches a recursive construction of an i n -g f i n i t e set i n M ( [9], p. 56 ). Requiring s l i g h t l y more background i s Rosser's proof that A w i s i n f i n i t e 1 = 1 ( [17], p. 77 ). At t h i s point we quote a general theorem that y i e l d s the immediate v a l i d a t i o n of the Axiom of I n f i n -i t y , as well as that of the Null Set Axiom. (j)(x^, ••• ' x n ) ^ s a bounded formula of set theory i f each of the quantified variables of 4> are r e s t r i c t e d to one of the sets x^, . . . ,x n , e.g. (Vx £ a) (3y £ b) ( x e y ) . Theorem 0.22 If <b ( ) i s a bounded formula 1 n of set theory, then: 3MC |= ())(x1, ... ,x n) i f f M |= c M ^ , ... ,x_). Proof: This follows from our Corollary 4.14. For an elementary proof, see [25], p. 127 Corollary 0.23 (a) MCB (= (3x) (.x e co) & (Vx e co) (3y e o>) (x e y) (b) M B (= (Vx e 0) ( x ? x ) . The remaining lemmas of t h i s series culminate i n the v a l i d i t y proof of the f i n a l axiom of ZFC, namely the Axiom of Choice. D e f i n i t i o n 0.24 Let u e B and u f 0 . { u„: 6 e I } i s p a p a r t i t i o n of u i f £ u R = u , and B e l u y • u 6 = 0 for y it 5 ( I t= 0 M , I e M) . Lemma 0.2 5 Let ( u Q : B e I ) be a p a r t i t i o n of u e B, p u ^ 0. Let { t'g : B e l l e M B, and 1 <= Q m ' g I e M. Then there exists t e M such that: u Q < II t = t Q ]) for each g e l . P — p Proof: Letting a = sup P(t„) , we define t as follows: B e l p dom(t) = M a + 1 t(z) = £ u * t Q ( z ) Pel B B An immediate consequence i s that for each 3 e I g and each z e M a + 1 : u^'t^(z) = u^'t(z) This fact gives us two c a l c u l a t i o n s : Ci) Ug - ( -t(z) + IT z e t 6 1 ) > [u 3- -t(z) ] + [u e»t g(z) ] = [up» - t ( z ) ] + [ug» t(z)] ( i i ) Ug ' C-tgtzi + H z e t 1) ' > [ u g * ~ t g ( z ) ] + [u -t(z) ] = [ V - t 3 ( z ) ] + [ v t 3 ( z ) ] = u 6 . Employing (i) and ( i i ) , we conclude: ff t = t f l I- > u •[[ t = t e 1 p — P p > ufl- n u «(-t(z) + ttz e t f l I ) ~ 6 z £ 3MCB 3 3 n u • ( - t (z)+E z e t 1) z e dom(tg) p p g In s a t i s f y i n g the above lemma M i s said to be a com-plete Boolean-valued structure ( see [25], p. 62 ). The t i n Lemma 0.2 5 i s unique in the sense that i f t and t" both s a t i s f y the Lemma, then LI t = t 1 I = 1 The next lemma i s known as the Maximum P r i n c i p l e as g i t states that Boolean suprema i n JMC are i n fact maxima. Lemma 0.26 For each formula cj) (x) of set theory there exists t e 3MEB such that II (ax) cf> (x) J = II <f> (t) I Proof: Let u = C ( a x ) <f> (x) I = I Q I $ (x) 1 x £ M Without loss of generality, we assume u ^ 0 . It follows that for some t Q we have: u 0 = I cj)(t0) II > 0 . g The sequence { t g : 3 < a } < = M i s constructed inductively. If u- II -u > 0 , we may B Y < 3 pick t Q £ M such that: P o < u f i = I <M.t R) I < u* n -u , 6 B ~ Y < B by v i r t u e of the fact that AC holds i n ML, and that B £ ML. A second consequence of t h i s fact i s that B has a c a r d i n a l i t y i n ML-, which allows us to conclude that an ordinal a e ©__ exists ML such that E u R = u . By Lenvma 0.25 there BB< a i s a t e ML such that: u < I t e t D I , for p — p B < a . So u 3 = II t ='t p ! • [ (j)(tR) II < I tj»(t) 1, for each B < a ; and u = £ u D < I a) (t) I 3 < a 3 ~ £ E II aS (x) 1 = u . Hence u = I cf> (t) 1 . x £ M B D e f i n i t i o n 0.27 For x £ M , we write sup(x) for 1 x ^ 0 1 = E x(u) . u £ dom(x) Before entering into the v a l i d i t y proof of the Axiom of Choice, we must b r i e f l y review the property of function-B B hood i n M . By induction, we know that elements of M are functions i n M. What does a function i n ML" look l i k e from the point of view of M ? F i r s t , a function i s a special set of ordered pa i r s . But the pair (x,y) i s foreign B B to ML since i t has no domain i n MC or range i n B. Just as we have defined the Boolean-valued singleton ( p. 17 ), we may define Boolean-valued p a i r s . D e f i n i t i o n 0.28 For each x, y £ ML : (a) {x,y} B = {x,y} x {1} 27 B (b) ( x , y ) B = f {x} B,{x , y } ° } B B Notice that {x} = (x,x) The d e f i n i t i o n of a Boolean-valued function p a r a l l e l s the usual notion of functionhood. B i B Def i n i t i o n 0.29 g f e JM i s a Boolean-valued function i f g there e x i s t u,v e JM such that: (a) dom(f) <=• i ( x , y ) B : x £ u, y e v ) . (b) II (Yx e u) (ay e v) [ ( x , y ) B £ f ] 1 = 1 . B B (c) i f (x ,y) , (x , y*) £ dom(f), then: II ( x , y ) B e f I • [ ( x , y ' ) B e f I < I y. = y* 1 (d) f(w) £ B for each w £ dom(f) . g (a) and (d) above provide that f £ JM . II f i s a func-tion 1 = 1 i f f f s a t i s f i e s (b) and (c) . I f: u v I = 1 i f f f s a t i s f i e s (a) and (b). D e f i n i t i o n 0.29 i s thus equi-valent to the condition: II f i s a function & f : u - * - v l = l Lemma 0.30 (a) (b) (c) (d) I { x , y } B = {x,y} 1 = 1 II ( x , y ) B = (x,y) ] = 1 B tt (x,y) = ( x ' f y ' ) ] = [I ( x , Y r = II (x ,y) £ u 1 = II ( x , y ) B £ u j] . (x' , y ' ) B 11 Proof: (a) i s t r i v i a l when we interpret i t as: g I z £ {x,y} « ( z = x v z = y ) 1 = 1 . The others follow from (a) v i a the early lemmas, 28 Now i t i s possible to fr e e l y exchange (x,y) ( unnat-B B B ural i n M ) with (x,y) ( natural i n M ) i n express-ions l i k e (d) above. This w i l l be exploited i n the next proof, as ordinary pairs are less cumbersome to use than t h e i r Boolean counterparts. We r e c a l l that f i s a choice function for a nonempty set x , i f dom(f) = x , rng(f) cr x , and f(z) e z for each z e x , z ^ 0 . Lemma 0.31 3MCB (= (Yx) [ ( x ^ 0 ) •+ (3y) ( y i s a choice t i o n for x )] Proof: Let x e M . For each z e dom(x) we use the Axiom of Choice i n M and Lemma 0.26 to pick t e M B such that: sup(z) < tt t e z I . z — . z Let y £ M be defined: r B dom(y) = { (z,t) : z e dom (x) , t = t } , y( (z,t ;)B) = x(z) , for Z u. z e dom(x) . Then l e t <j>(x,y) be: (Vz)[ ( z e x & z ^ 0 ) - > - ( a t ) ( t e z & ( z , t ) B e y ) ] . Using Lemma 0.30 and others, we calculate: I *(x,y) II _> n [ -x(z) + ( -sup(z)+x(z) • Z E M B sup(z))] = 1 . Now we w i l l show II y i s a function B = 1 . Actually, only part (c) of D e f i n i t i o n 0.29 29 needs demonstration. Let g be the function i n M defined by: dom(g) = dom(x) ; g(z) = t , i. e . g i s the choice function on dom(x) described above. g i s extensional, i . e . (i) Vz e dom(x), I z = z 1 I < II g(z) = g ( z ' ) II . The v e r i f i c a t i o n of the above involves an elementary applicaton of 0.9 (b) and 0.11 . g For each z e dom(x) and t e M , we have: [ ( z , t ) B e y 1 = 1 y( (z« ,g(z') ) B ) - | ( z , t ) B = (z ' , g (z ')) B l D z*edom(x) = Z x ( z ' ) •[[ (z,t) = ( z ' ^ f z 1 ) ! (by 0.30) z 'e dom (x) = T. x ( z ' ) • Ez = z ' ]•[ t = g ( z ' ) 1 z 'e dom (x) < I x ( z ' ) - [ g ( z ) = g ( z ' ) ] - I[t = g ( z')l z'edom(x) ( by (i) above ) < E g(z) = t ] . Applying t h i s c a l c u l a t i o n , we conclude: I ( z , t ) B e yl • I ( z , f ) B e yl<Eg(z) = t l - E g ( z ) = t'l<tt = t ' l . g This v a l i d a t i o n of the Axiom of Choice i n M concludes our p a r t i a l proof of Theorem 0.15 . g Our attention now turns to Corollary 0.16 . Is M a model of ZFC, according to our convention on p.7 ? From the beginning we have de l i b e r a t e l y confounded the d i s t i n c t i o n g between M and i t s universe, by neglecting to invent a sep-arate symbol for the l a t t e r . Neither have we drawn attention B to the membership r e l a t i o n for M . Our unconventional 30 notion of v a l i d i t y tends to further obscure the matter. B B B IMC i s c l e a r l y a set i n IK : JMC0 E I ; i f M £ 1 , B B then IMC , , e IK ; i f M 0 e IK for each 3<a, where a i s a l i m i t ot+± p g ordinal i n IMC, then • 0 W ' 3MC„ e IK; and since 0 - _ _ . = Ord n M, 6<a S JMC 3 B B we have M = y M e IK a<9. IMC B B IMC has a membership r e l a t i o n e , which we may define: IMCB |= x e B y i f f Z y ( u ) i u = x ] = 1 , and t h i s u e dom(y) r e l a t i o n s a t i s f i e s ( v i a Theorems 0.14 and 0.15 ) the the-orems of set theory. Of course, we have been refering to B e as £ from the beginning, to simplify our notation. g This leads us to another problem: IMC (= x = y does g not necessarily imply x = y i n K , i . e . IMC has a d i f f e r e n t equality r e l a t i o n than IK . This i s e a s i l y resolved, i f we are w i l l i n g to further complicate our notion of model by relegating the symbol '=' to the status of a predicate con-stant. In t h i s case, IN = ( N , ^ ^ , ^ ) i s a model of set theory i f N i s a set, =^ i s a binary r e l a t i o n on N s a t i s -fying the axioms and inference rules of f i r s t order predi-cate calculus with i d e n t i t y , etc. , . This augmented notion of set theoretic model clears g up the problem. Both IMC and IMC are e a s i l y construed as models of t h i s sort: IMC = (M, = ,ep'M2) , IM B = (JMCB,=B, £ B) , g where IMC symbolizes both the model and i t s universe, and B B = and £ are defined recursively ( as i n 0.6 ). Following V t h i s convention, Theorem 0.22 t e l l s us that i s an embed-ding of M into M . In p a r t i c u l a r : (a) M B '{= x = B y i f f M (= x = y . B v B v Ob) M '(= x e y i f f M j= x e y g Our study of M , though not complete, i s s u f f i c i e n t for the comming use we are to put i t to. We w i l l come to g see the M construction as the intermediate stage of a g larger process. Moreover, the issue of whether M f i t s one of several f e a s i b l e notions of modelhood w i l l have e s s e n t i a l l y no impact on the work to come. The remainder of t h i s section deals with the extension g of the model M to a larger model that i s related to M , but that f i t s i n every way the c r i t e r i a of modelhood given on p. 7 . D e f i n i t i o n 0.32 (a) A subset G'of a Boolean algebra B i s an u l t r a f i l t e r i f : (i) 0 f. G . ( i i ) x, y e G implies x*y e G . ( i i i ) x e G, y >_ x implies y e G . (iv) Vx e B , x £ G o r - x £ G . (b) G c B i s an M-generic u l t r a f i l t e r i f , i n addition to the above, G s a t i s f i e s : (v) A cr G, A £ 3MC implies IIA £ G . G i s just a f i l t e r i f i t s a t i s f i e s (i) - ( i i i ) above. G i s a proper f i l t e r i f G ^ B. Condition (iv) i s equivalent to saying that G i s a maximal proper f i l t e r , i . e . one that i s not properly included i n any other proper f i l t e r . A useful equivalent to 0.32 i s the following. Lemma 0.33 An u l t r a f i l t e r G on B i s M-generic i f f for each p a r t i t i o n A of u e G such that A £ M, there exists b e B such that A fi G = {b} . Proof: Let A c B , A e M, then G i s M-generic i f f : (i) IIA £ G implies A j-£ G . We write: A 1 = { -a: a £ A } Since G i s an u l t r a f i l t e r , we have: IIA jzf G i f f -(IIA) e G i f f £A* e G S i m i l a r l y , A £ G i f f (3a £A)( a £ G ) i f f (3aeA)(-aeG) i f f (3aeA')( a e G) Hence (i) i s equivalent to: ( i i ) EA' e G implies (3aeA')( a e G) Given A 1, by simply taking the supremum of the a's which s a t i s f y ( i i ) , we arrive at a unique b eA' fi G , with no e s s e n t i a l change i n A'. D e f i n i t i o n 0.34 Let G be an M-generic u l t r a f i l t e r on B. By t r a n s f i n i t e induction on p(x), we define the interpretation functor i„ of M by G: (a) i G ( 0 ) = 0 . (b) i Q ( x ) =' { i G ( y ) : x(y) £ G } . We usually write ' i ' for i . , , dropping reference to G when i t i s understood. D e f i n i t i o n 0.35 M [G] = { i (x) : x e M B } i s c a l l e d the generic extension of 3MC by G, where G i s an ME-generic u l t r a f i l t e r on B. As seen below, the notation M[G] suggests ( as i n f i e l d theory ) what i t should. Theorem 0.36 M[G] i s the least model of ZFC exten-ding M and containing (G} The s i t u a t i o n i s summarized i n the commutative diagram below: inclusion G At t h i s point we w i l l only show part of 0.36, i . e . that M[G] i s a model of ZFC extending M and containing G as an element. This w i l l be done i n the next series of lemmas, ending with 0.40 . The minimality of ME [G] i s es-s e n t i a l l y a consequence of our Lemma 5.5 . [9], p. 59 gives another proof using absoluteness, which would be almost un-changed i n our system of models. Lemma 0.37 For each x e W, i (x) = x . V Proof: Induction on p(x) : i(0) = i(0) = 0 . i(x) ='.{ i(y) : x(y) e G } = { y : x(y) e G } , as p (y) < p(x) , = { y : y e x } , as x(y) = 1 £ G , g We define the canonical generic u l t r a f l i t e r G on MI : V V dom(G) = { x : x E B } ; G(x) = x , Vx £ B G belongs to M by d e f i n i t i o n . Lemma 0.38 G £ M[G] Proof: i(G) = { i (x) : G(x) £ G } = { i (x) : x £ G } = G . Suppose x £ M , x £ ML" [G] , and i (x) = x . Then we V say that x i s a name for x. For example, x i s a name for x. and G i s a name for G. Lemma 0.39 If x, y are names for x, y £ ME [G], respectively then: X £ y i f f [ [ x e y f l e G , and x = y i f f I x = y 1 £ G . Proof: (a) Given that x £ y, we show I x £ y I £ G. If x £ y, then there exists z Q £ dom(y) such 35 that y_(z0.)_ e G and i ( z 0 ) = x . Proceeding by t r a n s f i n i t e induction on ( p (x) , p (y) ), we assume by induction hypothesis that I z Q = x 1 eG, as p(z 0) p (y) . Hence y ( z 0 ) * l z Q = x 1 e Gf and since II x e y 1 > y (z Q) • I z Q = x 1 , we have that II x e y 1 E G . (b) For the converse of (a), see [9], p. 58 . (c) Given that x = y, we show II x = y I e G. Since i (y) = { i(z) : y(z) e G } = ( i ( z ) : x ( z ) e G ^ = i ( ^ ' we have: Vz e M B, y(z) e G i f f x(z) e G . Hence, for a l l z e dom(x): (i) ( x(z) £ G ).+ (-x(z) e G ) + (-x (z) +11 z e y l e G ) , ( i i ) ( x(z) e G ) -> ( i ( z ) e y ) ^ ( I z e y J e G ) ( as p(z) < p (x) ) + C-x(z) + [ z e y ] e G ) . Si m i l a r l y , for a l l z e dom(y): ( i i i ) (y(z) £ G ) -> (-y(z) + II z e x ]] e G ) , (iv) ( y(z) e G ) (-y(z) +11 z e x l e G ) . From the d e f i n i t i o n of II x = y H , (i) - (iv) above, and the genericity of G ( 0.32 ), i t follows that I x = y I e G. (d) The converse of (c). Given that fl x =' y TJ e G; for a l l z e dom (x) : x(z) e G implies _j z e y ]] e G, because G i s an u l t r a f i l t e r and -x(z) + [[ z e y JJ e G. So, i f x ( z ) e G ( i . e . i(z) e x ) then tt z e y 1 e G, and by induction hypothesis i ( z ) e y, as p(z) < p(x) . For the same reason, for a l l z e dom(y): y(z) e G ( i . e . i( z ) e y ) implies [[ z e x J e G, which by induction hypothesis implies i ( z ) e x, as p(z) < p (y) . We conclude that for a l l z e dom(x) u dom(y) such that x(z) e G and y(z) e G: i(z) e x i f f i(z) e y Hence, x = y . Lemma 0.40 If x^, ... ,x n e M are names for x^, ... ,x n e M [G] , and cj) i s a formula of set theory, then: M[G] H <$>{xir ... ,x n) i f f ff1(l)(x1, ... ,x n) H e G. Proof: This follows from the previous lemma by induc-ti o n on the complexity of cf> . 0.16 and 0.40 prove that M[G] i s a model of ZFC. 0.39 implies that M[G] i s standard, and i t i s not hard to show ( using 0.40 ) that M[G] i s t r a n s i t i v e . Because i Q i s defined by t r a n s f i n i t e induction over 0 e 3K , we have 37 i„ e IK, The Axiom of Replacement thus implies that M [G] e K . The other d e t a i l s of the diagram on p. 33 follow from 0.37 and 0.38 . Since 3K i s t r a n s i t i v e , our diagram seems to indicate that G e 3K . A l l along however, our t a c i t assumption has been that M-generic u l t r a f i l t e r s do e x i s t . To make such an assumption i s equivalent to adding a very strong axiom to ZFC. Martin's Axiom, which i s a weaker and more reason-able form of t h i s assumption, may be invoked for t h i s pur-pose ( see [13] ), but we would l i k e to avoid any further additions to our foundations. We s h a l l now show that the foundations l a i d at the beginning of t h i s section are enough to provide the existence of an M-generic u l t r a f i l t e r G i n 3K . An u l t r a f i l t e r H a i s said to be p r i n c i p a l i f i t i s of the form { b e B : b > a }. Suppose that H i s M-generic. — c l Then 0.33 implies that there are no p a r t i t i o n s of a e B i n M. Within M, a i s an atom, or minimal non-zero member of B ( even i f B i s i n r e a l i t y nonatomic, i . e . having no atoms ). A sim i l a r argument shows that i f an M-generic u l t r a f i l t e r G belongs to M, then TIG i s an atom of B. Since we do not r e s t r i c t our attention to Boolean algebras having atoms i n the sequel, we cannot rule out the p o s s i b i l i t y that each M-generic u l t r a f i l t e r G on B i s non-principal and that G £ M. G, i f i t exists at a l l , may be highly non-constructive . 38 D e f i n i t i o n 0.41 Let F be a family of subsets of a Boolean algebra B. A f i l t e r U on B i s F-complete i f for each E e F such that HE e B: E cr TJ implies HE e U . There i s an obvious redundancy i n the above d e f i n i t i o n i f B i s complete. Two elements a, b e B are compatible i f a*b ^ 0 . A pairwise compatible subset of B i s one whose members are compatible with each other. It i s apparent that f i l t e r s are pairwise compatible, and that each subset of a pairwise compatible set i s pairwise compatible. Below, we have a t r i v i a l extension lemma which w i l l be helpful i n construc-ting and extending pairwise compatible sets. Lemma 0.42 If H c B i s pairwise compatible, then for each b e B, either H U {b} or H U {-b} i s pairwise compatible. If H i s a pairwise compatible subset of B, then we can enlarge i t to the following f i l t e r : J = { z e B : z > II a, , a , e H l . k < n By maximalization, we may further extend J to an u l t r a f i l -ter. This i s expressed i n the well-known U l t r a f i l t e r Theorem below. Theorem 0.43 Each pairwise compatible subset of B i s contained i n some u l t r a f i l t e r on B. Since the above theorem follows from AC, i t holds i n IK , and u l t r a f i l t e r s are p l e n t i f u l in IK . The d i f f i c u l t y of the existence problem we are considering must l i e i n the property of genericity. Theorem 0.44 Given a countable family F of subsets of a Boolean algebra B, and an F-com-plete f i l t e r G Q on B, there exists an F-complete u l t r a f i l t e r G on B extend-ing G 0 . Proof: Let F* = { A £ F : - n A £ G0 } . Since F i s countable, we may enumerate F* = { A D, ... ,A , ... } , and define P n n II (A ) . By d e f i n i t i o n , P ^ 0 , for n n each n. F* has the following property: Vn, Va e G D , a-p n ? 0 , since a«p =0 implies a < -p , but ^n — cn -P i G< ,Q . Because of t h i s , we know that H D = G oy'{p 0} i s pairwise compat-i b l e . Having defined H^ and assuming that i t i s pairwise compatible, we use 0.42 to define H ,, as H U (p } t i f n+1 n *n th i s i s pairwise compatible; or HfiU i ~ P n ^ otherwise. H = y H i s thus a pairwise n n compatible set containing G Q . We ex-tend H to an u l t r a f i l t e r G by way of 0.43, 40 G i s c l e a r l y G--complete. Theorem 0.44 i s an extended form of the Rasiowa-Sikorski Lemma ( c f . [25], p. 29 et seq. ). While the usual form of t h i s r e s u l t i s s u f f i c i e n t for our present purpose, we w i l l need the stronger hypothesis of 0.4 4 in Section 4. It may seem natural to release F from the coun t a b i l i t y re-s t r i c t i o n , but t h i s cannot be done without making further r e s t r i c t i o n s on B ( e.g. Martin's Axiom [9], p. 99 ). I t now becomes apparent just why we have picked a countable ground model M. Corollary 0.45 If M <=• IK i s a countable model of ZFC, and B i s a complete Boolean algebra i n M, then M-generic u l t r a f i l t e r s on B exi s t i n IK . M Proof: G i s M-generic i f f G i s IP (B)-complete. Since M nP (B) i s countable, Theorem 0.44 y i e l d s the r e s u l t . This concludes our study of M and M[G] as abstract objects. In the sequel we w i l l work with p a r t i c u l a r ex-amples of these constructions, and v i r t u a l l y a l l of the material i n t h i s section w i l l f i n d application. By now we are acquainted with the use of a generic u l t -r a f i l t e r as a type of decision process capable of evaluating any set theoretic statement regarding i t s v a l i d i t y i n M [G]„ . In practice, many of, the properties of M{GJ w i l l be demon-strated by Boolean-valued calculations involving generic u l t r a f i l t e r s . We w i l l also f i n d i n the sequel that generic u l t r a f i l t e r s can be used to r e f l e c t a number of algebraic and a n a l y t i c a l notions. They can be used i n certain s i t u -ations to provide d i r e c t answers to purely non-logical problems. 42 Section 1 : The Lebesgue Measure Problem and the Axiom of Choice The Axioms of Pairing, Unions, and I n f i n i t y ensure that a l l standard t r a n s i t i v e models of ZF contain the set of natural numbers w ( see [24],p.129 ). Well-known methods ( e.g. Dedekind cuts ) of generating the r a t i o n a l and r e a l numbers are e a s i l y duplicated i n these models ( see [16],p.271 ), however the set of Dedekind cuts gen-erated from to may vary from model to model. It i s possible thus to express statements of r e a l analysis as formulas i n ZF. As the concept of Lebesgue measure i s definable in t h i s context, we may view the Lebesgue Measure Problem from the vantage point of ZF by asking whether models of ZF e x i s t which s a t i s f y the statement: LM A l l sets of reals are Lebesgue measureable. In the event that a model IE does exi s t such that IE |= LM , we immediately conclude that IE ^ AC , for AC-*--] LM . For an analyst, our model 3E might be unattractive as there i s no guarantee that certain basic prerequisites of analysis hold on IE . Not only are the non-constructive p r i n c i p l e s , such as the Hahn-Banach Theorem, derived from some form of AC, but so are some commonplace facts l i k e the re g u l a r i t y of (. countable unions of countable sets are countable ) . Moreover, the presence of AC in some ( possibly weaker ) form i s necessary to provide acceptable properties for 43 Lebesgue measure in JE , There are two main characterizations of the basic top-o l o g i c a l notions of metric spaces: (a) e - < 5 c r i t e r i a . (b) sequential l i m i t c r i t e r i a . The d e f i n i t i o n s of a l i m i t point and the closure of a set, as well as continuity of functions have obvious versions i n (a) and (b). If our model under discussion s a t i s f i e s the Heine-Borel Theorem ( which may not be the case; see 1.2 ), then versions in (a) and (b) e x i s t for the d e f i n i -t i o n of compactness of a set. Using AC we can prove the equivalence of both versions of a l l the d e f i n i t i o n s men-tioned above. What happens i f our model does not s a t i s f y AC ? Proposition 1.1 For each of the following notions there i s a model of ZF not s a t i s f y i n g AC i n which versions (a) and (b) of said no-t i o n are not equivalent. (i) l i m i t point of a set. ( i i ) closure of a set. ( i i i ) continuity of a function. (iv) compactness of a set. Proposition 1.2 For each of the following statements there i s a model of ZF not s a t i s f y i n g AC i n which said statement holds: Ci) co^ i s singular. ( i i ) the set of reals IR i s the union of countably many countable sets. ( i i i ) there i s an i n f i n i t e set of reals having no countable subset. (iv) there i s a subspace of the reals which i s not separable. (v) the Heine-Borel Theorem i s f a l s e . See [10], pp. 141 - 4 for a demonstration of the above r e s u l t s . As far as the needs of the analysis and topology of the reals are concerned, the appropriate weakening of AC i s the following statement, known as the Countable Axiom of Choice. AC^ Every countable c o l l e c t i o n of nonempty sets has a choice function. If IE |= ZF + AC^ then versions (a) and (b) of each of (i) - (iv) i n Proposition 1.1 are equivalent i n IE . . Also, none of the statements (i) - (v) i n Proposition 1.2 can hold i n any model of AC^ . In fact, we have the following r e s u l t . Proposition 1.3 If IE f= ZF + AC^ then each of the f o l l -owing statements must hold i n IE : (a) the Heine-Borel Theorem ("h)_ every subspace of a separable metric space i s separable. (c) Lebesgue measure exists and i s count-tably additive. (d) the family of F i r s t Category sets i s countable additive. Proof: See [10], p. 21 - 2, p. 29 . The Baire Category Theorem does not depend at a l l on AC. AC^ does not imply the f u l l strength of the general Hahn-Banach Theorem; the McAloon model of Section 6 v e r i f i e s t h i s ( see [23], pp. 2 - 3 ). However, AC^ e a s i l y y i e l d s the Hahn-Banach Theorem for separable Banach spaces. Since the family of Borel sets w i l l have a special significance i n l a t e r constructions, i t i s worthwhile to examine the r e l a t i o n i t has with AC. There are two usual d e f i n i t i o n s for t h i s family, IB . D e f i n i t i o n 1.4 (a) IB i s the smallest a-algebra of sets of reals containing the open sets, (b) IB i s the c o l l e c t i o n of sets hyper-arithmetic i n some re a l ( see [21], p. 179 ); or, by a theorem of Souslin: IB i s the c o l l e c t i o n of A. sets i n the Projective Hierarchy ( see [21], p. 185, c f . [11], v . l , p. 453, et seq. ). As (b) i s the type of d e f i n i t i o n we w i l l r e l y on, we • need AC at l e a s t , i n order to show tha t IB i s c l o s e d under co • countable unions (. we must p i c k a code f o r each of count-ably many Bore l sets ). Without AC, (a) and (b) above are not g e n e r a l l y e q u i v a l e n t ; however AC^ i s strong enough to guarantee the equivalence of (a) and (b), and show ( see [10], P. 22 ): (i) IB = u IB a where B 0 the open * a<coi s e t s , and IB i s the set of a l l count-ex . able unions' of elements of u IB and Y<a t h e i r complements. ( i i ) IB cr. IB ' , Ya<oJi . , a a+1 I t i s evident that AC^ i s a necessary and p o s s i b l y adequate form of AC as f a r as elementary a n a l y s i s and top-ology are concerned. The question now remains as to whe-ther models of ZF e x i s t which s a t i s f y both LM and AC oo Solovay has shown that under a c e r t a i n hypothesis the con-s t r u c t i o n of a model of ZF s a t i s f y i n g LM + AC^ i s p o s s i b l e , using the techniques of - Section 0 . Solovay's con-s t r u c t i o n i s the subject of the sequel. 47 Section 2 : Some Model Theoretic Properties of Lebesgue Measure We s h a l l define some types of set theoretic formula from two syntactic hierarchies and develop some of t h e i r model theoretic properties. Our f i r s t source of notation i s Kleene's a n a l y t i c a l hierarchy ( see [21], p. 173 et seq. ). S t r i c t l y speaking, t h i s i s a c l a s s i f i c a t i o n i n recursion theory of formulas of second-order arithmetic. There i s a natural t r a n s l a t i o n of these formulas into the f i r s t - o r d e r language of set theory, however. De f i n i t i o n 2.1 A formula of set theory <j> i s IT i i f : cj> «-»- ( Vx l f ... ,x n e oow )ty , where ty i s a formula whose only quantifiers are of the form Vy e w , or ay e oo . The following i s a syntactic c l a s s i f i c a t i o n of the formulas of ZF, known as the Levy hierarchy ( see [12] ). D e f i n i t i o n 2.2 (a) A formula i s E Q = n o i f i t i s bounded ( see p. 21 ). (b) ty i s £ n + 1 i f cj) = 3xty where ty i s n . n (c) cj) i s n i f cj) = Yxip where ty i s E . n (d) cj> i s Z* F, resp. II^ F i f ZF |- ty «-*• ty where ty i s E , resp. II r n n 48 ZF (e) o) i s A , resp. A i f d> i s both n n Y £ and II , resp. A and II n n ' c n n Let IE , IF be standard models of ZF with universes E, F respectively. It i s obvious that IE i s a submodel ( see [1] , p. 21 ) of IF i f E cr F . For such standard models s a t i s f y i n g t h i s condition we write IE cr IF Let cj> be a formula of ZF. An assignment f of a) i n IE i s a mapping of the free variables of a> into E; we write 4>[f] for the sub-s t i t u t i o n of f (x) for each free variable x occuring i n tf>. We now define the fundamental model theoretic concept of t h i s section, the notion of absoluteness between stan-dard t r a n s i t i v e models of ZF. There are many notions of absoluteness i n the l i t e r a t u r e . Unlike the absoluteness of Goedel ( see [7] ) or of Cohen ( see [3] ), the d e f i n i -t i o n we use ( due to Shoenfield; see [4], pp. 85, 106 ) does not employ r e l a t i v i z a t i o n of formulas to t r a n s i t i v e classes. D e f i n i t i o n 2.3 Let IE , IF be standard t r a n s i t i v e models of ZF, and l e t IE cr IF (a) A formula <j> i s absolute between IE and IF i f f for a l l assignments f of a) i n IE : IE cf>[f] i f f IF f= <j)[f] • (b) A term t i s absolute between IE and IF i f f the formula ( x = t ) i s absolute between IE and IF , and x does not occur in t. Cc) An operation D i s absolute between 3E and IF i f f the term D (u) i s absolute between IE and IF for each u e dom(D) . For the following sequence of lemmas l e t IE , IF be standard t r a n s i t i v e models of ZF, and IE c r IF . Lemma 2.4 (a) Atomic formulas are absolute be-tween IE and IF . (b) If ty and ty are absolute between IE and IF then so are ~] ty , tyvty. Proof: (a) and (b) follow from the d e f i n i t i o n s of submodel and (= , respectively. If every formula i s absolute between IE and IF , then IF i s obviously an elementary extension of IE ( see [1] , p. 82 ). Since the models we w i l l b u i l d are not elementary extensions of the ground model, the problem of determining whether a formula i s absolute i n t h i s context i s n o n - t r i v i a l . Our purpose i s served by a p a r t i a l solution to the problem. Lemma 2.5 (a) Bounded ( £ 0 ) formulas are absolute between IE and IF . ZF (b) formulas are absolute between IE and IF . „ 5Q Proof; (a)_ Either by induction on complexity C [1.1, p. 478 ), or by way of Skolem functions C [4], p. 87 ). (_b) If cf)(x,y) i s absolute between IE and IF , then ax <f>(x,y) i s preserved under extension from IE to IF , by def-i n i t i o n of f= . ZF Hence £^ formulas are preserved under -the above extension ( i . e . they hold in IF i f they hold i n IE ) . Sim i l a r l y , Vx <Mx,y) i s preserved under r e s t r i c t i o n from IF to IE . Hence ZF II ^ formulas are preserved under the above r e s t r i c t i o n ( i . e . they hold i n IE i f they hold i n IF ) . It follows from (a) above and Lemma ZF 2.4 that formulas are absolute between IE and IF . Most of the fundamental concepts of set theory are ex-ZF pressible as A^ formulas, terms, and operators. These i n -clude: x cz y ; {x,y} ; (x,y) ; (x i s an ordinal) ; (suc-cessor of x) ; 0 , 1 , 2 , ... ; (x e co) ; (x = co) ; the ordinal arithmetic operations ; rank of x ; functionhood ; range(x) ; domain(x) ; union(x) ( see [4], p. 81, et seq. ), These concepts are therefore absolute between IE and IF . There are two notable exceptions: neither IP (co) nor 51 { JX ; rank Cxi . = Qt } are preserved under extensions. Since ZF both notions are 11^ , we cannot expect the higher orders of the Levy hierarchy to add much to our knowledge of ab-solutness. Lemma 2.5 seems to be the best possible r e s u l t of i t s type; fortunately i t i s enough for our needs. The following r e s u l t due to Mostowski and Shoenfield ( see [20] ) establishes an important connection between the analytic hierarchy and absoluteness. Theorem 2.6 In any t r a n s i t i v e model of ZF: f o r -ZF mulas are equivalent to A^ formulas. Proof: See. [4] , .p. 160.. Corollary 2.7 formulas are absolute between 3E and JF . The assumption i s now made that IE (= AC^ . Borel sets have a central role i n the construction ahead. It i s imperative that we have some method of naming and r e f e r i n g to Borel sets within the language of set theory. The method we use i s that of Godel -numbering or 'coding 1 the 2^° Borel sets with number theoretic functions. Of the many possible recursive coding procedures the following, due to Solovay, i s simple and adequate. Let {r^} be an arithmetic enumeration of Q ( the r a t -ionals \. Let J be the following pairing function: JCa,b) = 2 a(2b + 1) . It i s e a s i l y v e r i f i e d that J i s one-to-one from .to2 onto tos.'{-Q} , and i s recursive. D e f i n i t i o n 2.8 (a) a codes [r.,r.] i f : a(0) = 0 (mod 3) , a(l) = i a(2) = j (b) Suppose ou codes B. , i = 0, 1, ... then a codes \ XJ B. i f : i 1 a(0) = 1 (mod 3) and a( J(a,b) ) = a (b) . a (c) Suppose 3 codes B, a(0) = 2 (mod 3), and a(n+l) = 3 (n) , then a codes 3R^ B ( the complement of B ) . (d) a codes B only as required by the above cases. Lemma 2.9 The following holds i n IE : (a) Every set coded by a e ai U i s Borel. (b) Every Borel set i s coded by some a e O J W . (c) If a codes A and a codes B, then A = B . Each code gives a sequential 'recipe' for a Borel set. If a Borel set A with code a i s used i n the construction of a Borel set B then the r e s u l t i n g code 3 for B w i l l con-t a i n a as a subsequence. The correspondence between Borel sets and t h e i r codes i s c l e a r l y not one-to-rone. 53 The recursive d e f i n i t i o n of the codes ensures that they are definable by a set theoretic statement. We w i l l continue to use recursiveness for t h i s purpose. If a codes a Borel set B we w i l l use the notation B a for B. I f , furthermore a e 3E , and B e 3E then we write B IE a for B. Let {s n} be a non-repetitive recursive enumeration of the f i n i t e sequences of p o s i t i v e integers s a t i s f y i n g : (a) = ( ) . n 7 (b) If s i s an i n i t i a l segment of s •, then m n m _< n . For n > 0, s n i s nonempty and has length k, say. Let be the i n i t i a l segment of s n having length k-1. Let the f i n a l segment of s be n, „. Then n*<n and s = s ^ (n,) l. n n n' Solovay (in [23]) constructs a code-generating function $(a,n) such that i f a i s a code, then for each new $(a,n) i s a code. D e f i n i t i o n 2:10 $(a,n)(i) = (a) a (i) ; n = 0 . (b) 0 ; n > 0 , *(a,n*)(0) = 0 (mod 3) . (c) $ (a,n*) ( J ( n k , i ) ) ; n» 0 , $(a,n*)(0) = 1 (mod 3) . (d) $ (a,n*) (i+1) ; n > 0 , (e) $(a,n*)(0) = 2 (mod 3) . The purpose of t h i s function i s to 'decode' a , y i e l d -denotes the concatenation of f i n i t e sequences, 54 ing the codes of the component Bor e l sets from which B^ may be constructed. Let 3 e O J w . We def i n e 3 e coW v i a the f i n i t e sequence s^, > = ( 3(0), ... , 3 ( n - l ) ) . The p v n) f o l l o w i n g Lemmas are due to Solovay. Lemma 2.11 Define cj^Ca) as (V3eoja)) (Sneco) [$ ( a , 3 (n) ) = 0] . Then: IE \= <t>^ (a) •«->• ( a codes a Bo r e l set ) . I f a codes a Bore l set and x e IR , d e f i n e : 'l ; x e B, Y ( i ) = $(a,i) 0 ; otherwise The previous lemma guarantees the existence of B^ ^ a ^ Lemma 2.12 There i s an a r i t h m e t i c formula ( see [22], p. 160 ) cf>4(a,3,x) such that cj>4(a,3,x) •«-*- 3=Y Lemma 2.13 Let x e IR . There are formulas ^ ( o ^ x ) . <^^(a,x) such t h a t : (a) IE \= cj>2(a,x) +*• ( a codes a Bo r e l set and x e B ) . a (b) IE |= ((^(a/x) -<-»• ( a codes a Bo r e l set and x t Ba ) . Proof: (a) Define fy^ ( a/ x) a s t n e f o l l o w i n g : (V3ew W) (aS4 (a , 3,x) + 3(0) = 1 ) & ^ ( a ) . o>2(a,x) i f f y(0) = 1 , by Lemma 10, and Y(0) = i f f x e B, , i f f x e B , as $(a,0) = a . <M a, 0) a (b) Define <^^(a,x) as: (Vecooa)) (. * 4 (a ,3,x) + 3(0) =0 ) & <t>± Ca) . <i>3 (a,x) i f f yCO). = 0 , by Lemma 10, and yCO) = 0 i f f x ft B, , i f f x £ B . • <S> (a, 0) a Both of the above formulas are . Corollary 2.14 There are formulas cf)^(a,3) and <j)g(ot,3) such that: (a) 3E h * 5 ( a , 3 ) ^ ( B a c= B g ) . (b) IE h * 6(a , 3 ) ++ ( B a = B g ) . Proof: Define cj>_(a,3) as <}>, (a) & <(>_ ( 3 ) & (Vx £ ]R) ( $ (a,x) v <|> (3,x) ) . Define <j)g(a,3) as <j>(..(a,3) & $^(8,a) . Quantifying over the reals i s permissible in the d e f i n i t i o n of <f>_(a,3) . We could o code each r e a l by i t s binary expansion, thus ensuring that <J),-(a,3) i s 11^ . If cj) (x) i s Ilj , and a i s a code belonging to 1 c F then tj)(a) i s absolute between IE and IF . A f f i x i n g subscripts and superscripts ( e.g. IR^ ) to emphasize that the construction of a defined term i s car-r i e d out within a s p e c i f i e d model, we summarize the above res u l t s i n the following theorem. From now on we make the additional assumption that IF \= AC^ . Theorem 2:15 For a, 3 e (w 1 0)^ and x£-3R_, the following notions are equivalent i n IE to formulas absolute between IE and IF : (a) a codes a Borel set. (b) o; codes a Borel set and x e B (c) a,6 code Borel sets and B c B„ . (d) a,g code Borel sets and B = B„ . a a p We may define a one-to-one map # by: #Ba = B^ . Theorem 2;15 indicates that # maps the Borel sets i n IE onto a subfamily of the Borel sets i n IF , which we c a l l the Borel sets r a t i o n a l over IE, . IF D e f i n i t i o n 2 •16 (a) BelF i s r a t i o n a l over IE i f B - B for some code a e (co^) _ . (b) If {B^} i s a sequence of Borel sets i n IF , {B^} i s r a t i o n a l over IE i f there i s a sequence {ou} i n IE of codes i n IF IE such that B. = B , for each l e co . 1 (X£ -Solovay points out a redundancy i n 2.16(b), namely that i f the belong to IE , then by AC^ the sequence of these codes automatically belongs to IE . From Theorem 2.15 we conclude: Corollary 2.17 : For Be JT r a t i o n a l over IE , B = #(BniR._ ) # i s natural i n that the following diagram commutes for Borel sets i n E j 1 \ / "2 IK where #1 and #2 are defined as above, but between JE and IK , and IF and E , respectively. D e f i n i t i o n 2.18 cf)(x,Ba) i s #-absolute i f for a l l assign-ments f i n IE : IE h *[f] (B a) i f f IF |= * t f ] (#Ba) . ( S i m i l a r l y for terms and operations. ) Lemma 2.19 (a) Boolean set operations are #-absolute. (b) I n f i n i t e Boolean set operations are #-absolute. (c) Let A,B be Borel sets i n IE , then A c B and A = B are #-absolute r e l a t i o n s . Proof: By Boolean set operations, we mean those on the f i e l d of sets of r e a l s . Let {B^} be a sequence of Borel sets in IE with codes a. , then y de-I fined by: y(0) = 2 (mod 3); y ( l ) =1 (mod 3); y(J(i,0)+l) = 2 (mod 3); y ( J ( i , j ) + l ) = a ± ( j - l ) , for j > 1; i s a code for both ClB. i n IE , and (?I#B. i n IF . By d e f i n i t i o n : # O B . = 0#B. , i i J l i i . i and (b) follows for the case of i n f i n i t e i n t e r -section. Codes for complementation and i n f i n i t e unions are covered i n D e f i n i t i o n 2.8 (b) - (c). 58 Thus (bl. (a) follows from (b). Theorem 2.15 Ccl - Cdl imply Cc) . Of the numerous topological notions that are #-absolute, the two most basic are a l l we need here. Lemma 2.20 (a) ( B i s open ) i s #-absolute. (b) ( B i s closed ) i s #-absolute. Proof: Let {[r. ,r. ]} comprise the closed r a t i o n a l -1k Dk K endpoint i n t e r v a l s containing B. Define y as: Y(0) =2 (mod 3); Y (1) = 1 (mod 3) ; Y(J(k,0)+l) = 2 (mod 3); Y(J(k,l)+l) = 0 (mod 3); Y(J(k,2)+l) = i k ; Y(J(k,3)+l) = j k ; then Y codes the closure of B. B i s closed i f B = B = B^ . (b) follows from Lemma 2.19 . B i s open i f IRxB i s closed. (a) follows from (b) . With si m i l a r arguments ( [23], p. 30 ) we can show that the int e r v a l s are r a t i o n a l over IE . Lemma 2.21 Let a, b e^R.^, then #(a,b) = (a,b); #[a,b] = [a,b]; #{a} = {a} . We now have a l l the tools necessary to explore Lebesgue measure i n t h i s model theoretic setting. Our concept of Lebesgue measure y i s that of an outer measure r OO 0 0 •, y*(E) = i n f { E_(b - a ) : U . (a ,b ) => E , b > a } 1 n=0 n n n=0 n n n n J r e s t r i c t e d to the a-algebra of measurable s e t s . Lemma 2.22 I f IE |= AC then f o r each Lebesgue measurable s e t E i n IE there are s e t s G a n d N such t h a t IE f= E = G-N & y*(N) Proof: We take E measurable t o mean t h a t f o r each E > 0 th e r e i s an open s e t 0 and a c l o s e d s e t F such t h a t F c E c 0 ,and y * ( 0 ^ F ) < e .. £ £ £ E £ By AC we may p i c k such a p a i r (0, , , F., , ) J oo x/n 1/n f o r each n £ oo . L e t G = n 0, . . Then de-n 1/n f i n e N = G-E . V n e oo, y* (N) < ^ ^ / y \ Y \ / r ? < 1/n . We now look a t v a r i o u s cases o f #-absoluteness f o r Lebesgue measure. Lemma 2.23 Let B be a ^ - s e t i n IE , then y E (B) = y ^ (#B) . Pro o f : The e q u a l i t y we wish to prove i s expressed i n a 3K , so our p o i n t o f view i s t h a t o f the diagram f o l l o w i n g C o r o l l a r y 2.17 . (a) Suppose B = y (a »t>m) , then from Lemmas m=l m 2.19, 2.20, 2.21, the d e f i n i t i o n o f Lebesgue measure, and the n a t u r a l i t y of #, n u (B) = £, (b - a ) i s #-absolute, and H m=l •m m y E (B) = mw (#B) i n IK . (b) L e t B be any open s e t . Enumerate the s e t s 60 of form i n (a) above: { A n} . Then: V (B) = sup { M (A n) : A n cr. B. } n i s sup of a countable c o l l e c t i o n of #-absolute r e a l s , hence i t i s #-absolute. Cc) L e t B e . We need only l o o k at the r e p r e s e c t a t i o n : B = n 0 ; 0 , , <= 0 . By ^ n n n+1 n a well-known p r o p e r t y o f u : y(B) = i n f y(0 ) n which i s #-absolute. The r e s u l t f o l l o w s . The next theorem i s the main r e s u l t o f t h i s s e c t i o n . Theorem 2.24 L e t a code a B o r e l s e t , then ( y(B a)=0 ) i s #-absolute. Pro o f : Our s t r a t e g y i s r e m i n i s c e n t o f Lemma 2.5. (a) ( y ( B a ) = 0 ) i s p r e s e r v e d under the e x t e n s i o n IE• -»• IF . F o r 3 e to" l e t 3 ^ ( 3 ) h o l d i f f ( 3 codes a 3 ^ - s e t ). From Lemmas 2.19(b) and 2.20(a), we i n -f e r t h a t ^ (3) i s (#-)absolute. From Lemma 2.23: ( ^ ( 3 ) & y(B ) ' = ' 0 ) i s #-absolute. Using Lemmas 2.4 and 2.19(c) we see t h a t i f ( y(B ) = 0 ) 33 e to W( ^ 6 ( B ) & B a c= B g & y(B ) = 0 ) holds i n IE , then by d e f i n i t i o n o f |=, i t h o lds i n IF . Thus Va e uit, : IE TR TP ) JE ( B a ). . 0 -> v w (B.^ ) = 0 , i f a i s a code. (b) ( y (JB^) = 0 ) i s p r e s e r v e d under the r e s t r i c t i o n IF -»- IE . For 3 £ to W l e t y ^ B ) h o l d i f f ( 6 codes a c l o s e d s e t ). Lemma 2.20 s a y s / ^ 3 ) i s (#-) ab-s o l u t e . Since /(B) + ^ ( P " ) * Lemma 2.23 i m p l i e s t h a t (/(B) & V(Bg) = 0 ) i s #-absolute. I f ( V(B a) = 0 ) V0ea>u( (/(B) & B B c B a) -*• y ( B B ) = 0 ) holds i n 3F then by d e f i n i t i o n o f f=, i t holds inJE . Thus Y a e ooW; y ^ ( B ^ ) = 0 y ^ (hf ) = 0 , i f a i s a code. The f o l l o w i n g lemma of Solovay i s a consequence o f the above theorem. C o r o l l a r y 2.25 (a) L e t B be a B o r e l s e t i n IE , then: ^JE ( B ) = yTP ( # B ) ' (b) L e t B be a B o r e l s e t i n JF r a t i o n a l over IE , then: ^IF ( B ) = ^IE ( B n ] R I E ) ' Pro o f : (a) Consider B as a measurable s e t ; by Lemma 2.22 B = G^N, where G i s and 62 N i s n u l l (. measure zero ) . Mote t h a t i n t h i s case N must be B o r e l a l s o . Mw (#B) = Mw (#G) - y-pdN). ( b y 2.19 ) = y E (G) - 0 (. by 2.23, 2.24 ) = y E (B) -(b) follov/s from (a) and C o r o l l a r y 2.17 . The proof above might l e a d us to c o n j e c t u r e t h a t the r e s u l t h o l d s f o r B measurable. Our p r e s e n t development o f f e r s no ground f o r t h i s c l a i m , and the reason i t doesn't underscores the whole r a t i o n a l e o f t h i s s e c t i o n . Because the codes range over the s e t to w, we may express u n i v e r s a l 1 statements about B o r e l s e t s as IT^ formulas. Even i f we c o u l d apply codes to the measurable s e t s , t h e i r c a r d i n a l i t y 2*° would be too l a r g e ( 2 ) f o r t h i s treatment. In such a case we have no i n f o r m a t i o n r e g a r d i n g a b s o l u t e n e s s , even f o r simple formulas. 3 63 Section 3 ; The Random Reals We assume the existence of a standard t r a n s i t i v e ground model M of ZFC which i s a submodel of IK countable i n IK . A l l our subsequent model constructions w i l l be b u i l t from IMC. Let IR denote the r e a l numbers of IK , and B denote the a-algebra of Borel sets of reals i n IMC. Let N denote the CT-ideal of Lebesgue measure zero sets i n IMC. D e f i n i t i o n 3.1 B* = IB /N i s the quotient algebra of equivalent classes of Borel sets [A] such that B e [A] ( B = A (mod N ) ) i f f y (A A B) =0 ( A i s symmetric d i f f -erence ) . Proposition 3.2 B* i s a complete Boolean algebra s a t i s -fying the countable chain condition. Proof: See [8], p. 67 . This proof involves AC, but M |= AC, thus B* i s IMC-complete. IR __ = IR H IMC i s countable, so most reals f a l l outside IMC i t . A large portion of these extraneous reals have a spe-c i a l property which i s instrumental i n the construction of our generic extensions of IMC. D e f i n i t i o n 3.3 IR * i s the set of those reals belonging to no measure zero Borel set which i s r a t i o n a l oyer IE . For x e I * , we say that the r e a l number x i s random over JE . Since JM i s fixed we w i l l write IR * as IR *, and IMC c a l l the elements of IR * random r e a l s . While i t i s clear that there are no random reals i n IMC C y({x}) = 0 ), the existence of random reals i s immediate: Lemma 3.4 IR * i s a Borel set having measure zero comp-lement. Proof: As IMC i s countable we may enumerate the Borel sets of measure zero, r a t i o n a l over M. Their union i s a Borel set of measure zero and equals IR ^ JR * . Of course IR * i s not r a t i o n a l over IMC, and since Q £ JM, each random r e a l i s i r r a t i o n a l . Solovay ( [23], pp. 4, 33 ) remarks that the random reals are characterized by. '.random1 binary expansions: for large n, any block of 2n consecutive entries i n the expansion contain approxi-mately n zeros and n ones. D e f i n i t i o n 3.5 Let G be an JM-generic u l t r a f i l t e r on B*: x G = { r : r £ Q , [ (r,°°) ] £ G } . It i s easy to show that x p i s a (left) Dedekind cut, G and as such can be i d e n t i f i e d with the r e a l : sup x^ . x^ t e l l s us a great deal about the structure of G. We define a. complexity function A mapping the codes into the ordinals. D e f i n i t i o n 3.6 fa) If a code Y e toW s a t i s f i e s Y CO)- = 0 (mod 3), define ACy) = .0 . (b) If Y(0) = 1 (mod 3), l e t Y iCj) = y ( J ( i , j ) ) and define XCY) = supUCYi) + 1) • i Cc) If YCO) = 2 (mod 3), define A(y) = MB) + 1, where 6(n) = YCn+1) S t r i c t l y speaking, the proof below i s a t r a n s f i n i t e induction on A M = A f \3MC, which maps (to ) M into 9 but we omit the extra notation. Lemma 3.7 Suppose B i s a Borel set i n IMC and G i s an M-generic u l t r a f i l t e r on B*, then: x G E #B i f f [B] e G . Proof: We set IE = IMC, IF = IK , and define # as i n the l a s t section. Let B = B^ where y e (toW) M . (a) Suppose y(0) = 0 (mod 3), then By = [ r y ( l ) ' r y ( 2 ) ] = # [ r Y ( D ' T y ( 2 ) ] = # B y ' x„ e #B -«-»• r . . < x < r . . -«-»• G y y CI) G Y ( 2 ) [ rY ( l ) ' to) £ G & ( r Y ( 2 ) ' °°) 1 G ^ [ B Y ] £ G (b) Suppose y(0) = 1 ( m o d 3) ' then B = UB Y i Y i and #B = y#B by Lemma 2.19. By induction Y j_ Yj_ hypothesis and f i l t e r properties; xr e #BV . xr e • U #B *+ a i t x r £ #B . \ s* T G i Y i : « Ti 3i ( [B J £ G ) ( as A (Yi) < A (y) ) r i • . [B ] £ G C as l[Ey f' = [B J ) i 1 (c) Suppose y(0) = 2 (mod 3), then B v = 3R B 0 , where 3 (n) = y(n+l) . Y p xn £ #B, ^ x . i #BQ ( by Lemma 2.19 ) G Y G p -H. [B g] / G ( as X(3) < A(y) ) -<-*- = L B y] e G ( as G i s an u l t r a -f i l t e r ) . The r e s u l t follows by t r a n s f i n i t e induction on complexity of codes. ( An argument simi l a r to that of Lemma 2.9 proves that every code has a complexity. ) We can use Lemma 3.7 to estab l i s h a natural b i j e c -t i o n between the generic u l t r a f i l t e r s and the random reals Lemma 3.8 x £ 3R* i f f x = x. for some generic u l t r a f i l -—— ter G . Proof: (a) Let x e M* . Define G = {[B] : x e #B} Let A,B e JB ; i f A = B (mod N) then x e #A -«->• x e #B R, as y ( A A B ) = 0 and y (#A A #B) = 0 ( Lemma 2.19 and Theorem 2.24 ) Thus: IBJ £ G -«-> YA e IB], x e #A . . . . (1) By. Theorem 2.24: [01 £ Gv . . ... (2) If [A], [B] e G x then x e #A, x e #B, and x e #A n.#B = #(. A n.B ) by Lemma 2.19 . Thus: [Ah B] = [A] • [B] e G . ... (3) Let [A] £ G and [A] < [B], then by (1): VC e [B] , x e C and so [B] e G . (4) (2) — (4) imply that G i s a proper f i l t e r . X G i s obviously maximal, and i s thus an u l t r a -x J ' f i l t e r . Let S B*, S e M , IS e G . Since B* obeys X the countable chain condition, there i s a M> countable c o l l e c t i o n of Borel sets: { A , ... ,A , ... } s M such that [A ] £ S, for each i £ co, and: I[A ] = ES h. Y . x Y r ( see [8], p. 61 ). Let y (0) = 1 (mod 3), y ( J ( i , j ) ) = Y ± ( j ) then A = u A and [A ] ' i ^ i ' £ G . Hence x £ #A by Lemma 3.7 . Lemma x 2.19 implies #A = U# A , so Hi ( x £ #Ay ) i i i and [A ] £ G H S ( Lemma 3.7 ). This estab-yL x lis h e s the genericity of G „. Note that even X though |M| = , the countable chain con-d i t i o n i s required. 68 Lemma 3.7 now gives: x = x_. , where G = G G x (b) Conversely, l e t x = x_, for some generic G u l t r a f i l t e r G on B*. For each Borel set B Y r a t i o n a l over M and s a t i s f y i n g JJ (B ) = 0, Theo-rem 2.24 implies i i M ( B ™ ) = 0 , and so [B^] £ G. It follows from Lemma 3.7 that x £ B • Y Corollary 3.9 For each x e l * , G = { [B] : x e #B } ——•—~~~~———— ——— i s an M-generic u l t r a f i l t e r on B*. These res u l t s give us some notation and terminology: (a) Each x e 3R * has an associated generic u l t r a f i l -ter G on B*. x (b) Each generic u l t r a f i l t e r G on B* has an associated random r e a l X„ . De f i n i t i o n 3.10 For x e 3K , l e t M fx] be the least tran-s i t i v e submodel of IK extending M and containing {x} , i f t h i s exists; M[x] = IK otherwise. We w i l l only use the above notation where i t i s well defined, primarily by the r e s u l t below. Lemma 3.11 For every x e IR*, M [x] = M [G ] . Proof: M [ G ] i s the least t r a n s i t i v e submodel of IK x extending M and containing {G1} ( see proof [9] , p. 56 v i a absoluteness^ or Lemma 4.8 for d i r e c t proof of a stronger r e s u l t )_. e IMCJG .] , by De f i n i t i o n 3.5 .. If I ? M i s a t r a n s i t i v e submodel of IK ( hence IN i s standard ) , and x e IN , then G e IN by Corollary 3.9, and so M[G ] c ]N , i . e . X x e „ M [ G ] <= IN IMC D e f i n i t i o n 3.12 For a given generic u l t r a f i l t e r G on B*, B* define X£e IMC as: dom(xG). = { r : r e Q, [(r,~)]eG; } ^ ( r ) = [(r,°°)] B* X~ i s c a l l e d the canonical random r e a l i n M x^ , —(j —(j names x G , i . e . i G (x^J = x G . For G understood, x = x^ , . We r e c a l l t h i s restatement of Lemma 3.8 of Section 0. Lemma 3.13 For each formula <j) and y e IR *: IMC [y] |= cf> (y) i f f I <f»(x) J e G . This r e s u l t holds with parameters i n IMC by making the substitution cj)g(y) = <J>(y,P~) r P e IMC. This gives: IT M [ y ] h *(Yf?) i f f II *(x,f) ] ] e G y , y e I R * , p e I M C . Theorem 3.14 For each formula cj), the set E = { y e IR : IMC [y] ( = <J) (y) } i s Lebesgue measurable. Proof: Let E' = { y e I R * : I M C [ y ] f = cf> (y) } . 70. By Lemma. 3,4, E' = E (modN ). Then by Lemma 3.13: y e E' <-> l t y ( x ) J eG^ . Let y e •«»-. code the Borel B such ' JM Y that: [B^ .] = I ty (x) I . Then for a l l y e JR*: y £ E' [B ] £ G y £ #B Y Y Y Therefore: E' = #B^ (modN ) , E = #B^ (modN ) , and E i s Lebesgue measurable. The above theorem e a s i l y generalizes by adding para-meters i n JM, and i t i s th i s form of Theorem 3.14 that finds application i n Section 5., 71 Section 4 : The Levy Algebra Every Boolean algebra i s a p a r t i a l l y ordered set, but seldom does a p a r t i a l l y ordered set have the necessary struc-ture to make i t a Boolean algebra, much less a complete Boolean algebra. Fortunately, a standard technique exists which transforms any given p a r t i a l l y ordered set into a complete Boolean algebra. If P i s a p a r t i a l l y ordered set we write RO(P) for the regular open algebra of P. This i s obtained by imposing the order topology on P ( with basic open sets [p] = { q : q <_ p } ). The elements of RO(P) are those open sets U which are regular ( i . e . U = U° ). RO(P) i s a complete Boolean algebra. Complete d e t a i l s are to be found in [8] ( p. 25 ) and/or [25] ( pp. 1 4 - 1 7 ). As usual, c f ( a ) denotes the c o f i n a l i t y of an ordinal a . D e f i n i t i o n 4.1 Suppose M |= K i s a cardinal & cf (K) = to. P i s defined by: M (= p e P «-»- ( 3n e to ) ( p:n-H< ) , and i s p a r t i a l l y ordered by: P ^ q ^ q ^ P -For each cardinal K, P i s simply a c o l l e c t i o n of f i -nite functions i n M with range i n K. The ordering of P i s reverse of the usual inclusion ordering. The p a r t i a l l y ordered set P gives us a complete Boo-K • lean algebra L =• RO(P ), c a l l e d a Collapsing algebra K K 1 C the reason for t h i s name: for any generic u l t r a f i l t e r G 72 on L f the function UG maps oo onto K, and so K "collap-IS ses" onto oo and i s countable i n M [G] . See [23] , p. 8 ) . For the present we s h a l l assume there i s a (_ strongly ) inaccessible "cardinal X. The ramifications of t h i s assump-tio n are discussed i n the next section. The family { P : cf (K) = oo, K < A } forms a normal l i m i t i n g system ( see [25], p. 193 ). It follows that the associated family { L : cf (K) =oo, K < A } i s an example of a d i r e c t system of complete Boolean algebras. An exhaustive development of t h i s topic i s found i n [25], pp. 183 - 195 . De f i n i t i o n 4.2 A Boolean algebra B s a t i s f i e s the K-chain condition i f each p a r t i t i o n of unity i n B has c a r d i n a l i t y less than K. In the case where K = oo, we say that B s a t i s f i e s the countable chain condition. Two members a, b of a Boolean algebra ( or p a r t i a l l y ordered set ) B are said to be compatible i f there exists a nonzero c e B such that c _< a and c _< b, otherwise they are said to be incompatible. Since a p a r t i t i o n of unity i s a maximal family of pairwise incompatible elements of B, the K-chain condition implies that no family of p a i r -wise incompatible elements of B has c a r d i n a l i t y K, or greater. A p a r t i a l l y ordered set s a t i s f i e s the K-chain condition i f i t contains no s t r i c t l y descending chain ( to-t a l l y ordered set ) of c a r d i n a l i t y K . The proposition below gathers together a number of technical r e s u l t s , mainly from the above reference, which support the work of t h i s section. We quote them without t h e i r lengthy but straightforward proofs, some of which derive from the work of Engelking and Karlowicz [5]. Proposition 4 . 3 (a) For each K < A such that cf (K) = co, P = ,UP K a<\ a (b) P = UP s a t i s f i e s the. A-chain K<A K condition. (c) L = AJlv s a t i s f i e s the A-chain condition. (d) L = RO(P) . (e) For each K < A, L i s a complete subalgebra of L. (f) |L'| < A , for each K < A . The Boolean algebra L defined above w i l l be referred to as the Levy algebra. The significance of Proposition 4 . 3 l i e s mainly i n two f a c t s . From (c) we have that L s a t i s f i e s the A-chain condition. This fact w i l l have app-l i c a t i o n s to situations i n both t h i s and the next section. From (c), (e), and (f) on one hand, and (d) on the other, we have two d i s t i n c t representations of L. The f i r s t rep-resentation would normally be improper. In general, we cannot say that the union of a family of complete Boolean algebras w i l l be a Boolean algebra, complete or otherwise. 74 Takeuti and Zaring use Proposition 4.3(a) and the fact that the collapsing algebras form a d i r e c t system to show that t h i s union i s equal to the d i r e c t l i m i t , or sum, of the L . The usual method of defining the sum of a family of Boolean algebras, and taking the completion of thi s sum, i s thus circumvented. Takeuti and Zaring show further that L thus defined i s isomorphic to RO(P), giving us a second representation ( within isomorphism ) of L. Our next r e s u l t takes a closer look at the structure of L by way of t h i s second representation. Lemma 4.4 (a) P i s the c o l l e c t i o n of f i n i t e sets of t r i -ples p = { ( a i , n i , 3 i ) } i < k s a t i s f y i n g : (i) n. eoj, 3 • < a. < A . l I l ( i i ) ( a , n , B Q ) , ( o ^ n ^ ) £ P + 3 Q = • (b) Suppose S e= L\{o} and |s| < A . For each K < A there i s a c o l l e c t i o n { e L : 3 < K } of pairwise incompatible elements such that: Ys e S, Y 3 < K, a B«s ^ 0 . Proof: (a) i s an obvious formal renaming of the ele-ments of P. The proof of (b) i s a straight-forward c a l c u l a t i o n using (a) ( see [9], p. 76 ) Many of the i n t r i n s i c properties of L are obtained by looking at P, s p e c i f i c a l l y the representation given i n (a) in the lemma above. This habit of ca l c u l a t i n g i n P rather than L carr i e s r i g h t over to some of the res u l t s concerning 75 M.k and M;J.GJ i n the next section, and mirrors the method-ology of c l a s s i c a l forcing to some extent. In preparation for these calculations we w i l l introduce at t h i s point some indispensable tools. D e f i n i t i o n 4.5 Let P be a p a r t i a l l y ordered set and S c P . S i s dense i n P i f : Vp e P, as e S, s £ p . If G i s any f i l t e r on L ( o r any other regular open algebra ), i t i s not d i f f i c u l t to induce' a related f i l t e r G' on the p a r t i a l l y ordered set P. Of course, we must de-scribe G' on P i n an order language rather than a Boolean language. We say that G* i s a f i l t e r on P i f : (a) the members of G1 are pairwise compatible. (b) x e G', y _> x y £ G1.. Complementation and the existence of 0 must not be taken for granted i n P; that i s why we are forced to simplify the notion of f i l t e r from the o r i g i n a l Boolean algebraic case. D e f i n i t i o n 4.6 G' i s an M-generic f i l t e r on P i f f for each dense set S c P, S £ M, we have S f\G1 ? 0 . G' c P above i s also c a l l e d a generic set of forcing conditions i n the l i t e r a t u r e . We w i l l not delve into the method of inducing a gen-e r i c f i l t e r GV on P, given a generic u l t r a f i l t e r G on L, or that of inducing G from G1 on the other hand. The l i t -erature contains ample treatment of t h i s (. see [25] , pp. 25 - 32, es p e c i a l l y p. 30; see also [9], pp. 48 - 52 )„and we s h a l l never need to appeal to the mechanics of i t . Suffice i t to say that RO induces a one-to-one correspon-dence between the generic u l t r a f i l t e r s of L and the generic f i l t e r s of P. Why have we defined L, and what' properties does i t have that simpler, more fa m i l i a r algebras do not? We have already mentioned that by i t s d e f i n i t i o n , L s a t i s f i e s the A-chain condition, and that t h i s fact i s very useful i n both t h i s section and the next. L has however, a very strong and unusual property having c r i t i c a l impact on Solo-vay 's application of random reals to the measure problem. It i s to t h i s property of homogeneity that the duration of t h i s section i s devoted. A l l of the p r i o r r e s u l t s we have c i t e d are e a s i l y ac-cessible i n the l i t e r a t u r e , and so we have quoted them with-out proof. The proof that L i s homogeneous i s not well re-presented elsewhere, so i t deserves a detailed treatment here. Suppose A i s a complete subalgebra of L, and g i s an automorphism on A. We say that g l i f t s from A to L i f there i s an automorphism g 1 of L whose r e s t r i c t i o n to A i s g. 77 g 1 i s c a l l e d an extension of g. I t i s by no means clear what conditions we might impose on A to ensure the l i f t i n g of each g e Aut CA) . Letting Aut(A) denote the set of automorphisms on A, we say that a complete subalgebra A of L has the l i f t i n g property i f each g e Aut(A) l i f t s . D e f i n i t i o n 4.7 L i s homogenous i f each complete sub-algebra A of L s a t i s f y i n g |A| < X has the l i f t i n g property. The term "homogeneous" has various meanings i n the l i t e r a t u r e . For our purposes, the strong notion of homo-geneity we use i s necessary. Let us f i r s t review some e a s i l y obtainable information. L i s complete, as i t i s a regular open algebra. A Hahn-Banach type extension argument can be employed to show that complete Boolean algebras are i n j e c t i v e - ( see [8], pp..132 -143 ), i . e . they s a t i s f y the commutative diagram below for any Boolean algebras A and B: B where e i s any monomorphism, and h i s any homomorphism. Having fixed a l l of the above p a r t i c u l a r s , i n j e c t i v i t y 78 simply means that a homomorphism f exists which completes the diagram. One of the main consequences of i n j e c t i v i t y i s the fact that homomorphisms on subalgebras into L extend to homomorphisms on L. This follows d i r e c t l y from the d i a -gram by l e t t i n g B = L, and e be the incl u s i o n map. We know then, that an automorphism on a subalgebra A of L extends to some homomorphism on L. Using a Hahn-Banach type argument, we can show that embeddings ( complete mono-morphisms ) of subalgebras extend to embeddings of L. Un-i v e r s a l techniques show us then, that automorphisms on any subalgebra extend to embeddings of L into L. To show that L i s homogeneous however, we must use properties s p e c i f i c to L. The path we w i l l take involves a novel use of Boolean-valued techniques. Though we are confronted with a non-l o g i c a l problem concerning L, we w i l l f i n d that much alge-braic information about L i s r e f l e c t e d i n ]MCL. We r e c a l l that DMC i s our t r a n s i t i v e ground model of ZFC. Lemma 4.8 Let A be a subalgebra of L, and h be an auto-morphism on A. In 3MCL there i s an u l t r a f i l t e r G, on A such that for each a £ A: h h(a) = [[ a e G, B . n Proof: G i s the canonical u l t r a f i l t e r on M L. Since G(l) = A C D =1, we have: M h AH.G f p. and the Maximal P r i n c i p l e (/Lemma 0.26 )_ de-fines G such that: 3MCL (= G a = AflG . XT. Likewise, we use the Maximal P r i n c i p l e to de-fine G, on A: h M L \= a e G, h(a) v e G, . h A An elementary c a l c u l a t i o n y i e l d s : I a E G A 1 = a , for each a e A . So we have: I a e G h ] = I h(a) v e G A B = h(a) . From t h i s , and the fact that h i s a monomorph-ism, simple calculations give: (a) I 0 £ G h JJ = 1 , (b) a' <_ b implies [ a e ] < I b £ G h 1 , (c) I (a-b) v e G h 1 = [[ a e G h & b e G h JJ , (d) \ (-a) v e G h J J = - | I a £ G h J ] . We conclude: L i ^ IMC h G, i s an u l t r a f i l t e r on A. „ h We refer to G, as the u l t r a f i l t e r on A associated with h h. This lemma i s understated i n the sense that h could just as well have been an embedding of A into L. Even so, we have not extracted a l l the information about G^ that i s re f l e c t e d in h. Corollary 4 . 9 IMCL f= G h i s (IP(A) ) v-complete. 80 Proof: h i s complete. The main work within L i s car r i e d out by the follow-ing r e s u l t , which i s our modified version of a theorem due to Jensen ( see [9], pp. 7 5 - 7 6 ). To prepare for i t , we mention the following items that are necessary i n the proof: (a) A subalgebra of a Boolean algebra i s said to be regular i f suprema ( and infima ) of subsets common to both algebras correspond to the same value i n each algebra. It i s e a s i l y v e r i f i e d that complete subal-gebras of complete Boolean algebras are regular. (b) The f a c t that A = [* ] , which i s proved i n the next section ( Corollary 5.2 ) using no information dependent on Lemma 4.10 . Lemma 4.10 Let A, B be complete subalgebras of L having c a r d i n a l i t y less than A , and l e t A be a com-plete subalgebra of B. Each automorphism on A l i f t s to be an automorphism on B. Proof: Let h be an automorphism on A, and be i t s associated u l t r a f i l t e r on A. Using the Max-imal P r i n c i p l e again, we induce a f i l t e r G* on B: M L \= (YxeB) ( xeG* ++ (3y £A) (y<x & Y e G h ) )• In M L, G* i s the f i l t e r on B generated by the pairwise compatible set G^. For each b e B, 81 we define; b* = '£.{ a e A : a < b } , where the supremum i s taken i n A, which i s com-plete. Obviously, b* e A and b* _< b . Using completeness of h and Corollary 4.9,for each b e B: II b e G* ]] = I (b*) " e G h ]J = h(b*) (1) , For each E cr B, [TIE]* = II { b* : b e E }, and so we have by (1): I E c= G* B = E { b* : b e E } v e G h ]] = II (TIE) e G h JJ = II (TIE) " e G* JJ (2) This gives: M L |= G* i s a (IP (B) ) "-complete f i l t e r on B. Since X i s inaccessible, Theorem 0.44 and item (b) preceding t h i s lemma allow us to extend G* to an u l t r a f i l t e r G': jM L h e i s a (IP (B) ) "-complete u l t r a -f i l t e r on B and G' => G* . A mapping g may now be defined for each b e B: g(b) = I b E G' 1 . The following Boolean suprema, evaluated i n th e i r respective algebras, are equal: [[ b e G' I ( B ) = II b e G' ]] ( L ) , as B i s a regular subalgebra of L. Hence g maps B i n t c B . 82 Using the fact that G' i s an u l t r a f i l t e r and that i s i n f e c t i v e , we have for each a, b e B: g(-a) = t[ (-a) - e G' J = I a £ G' JJ = - 1 a e G'.'l = -g(a) , g(a«b) = [[ (a«b) v e G1 ]] = [[ a e G1 & b e G1 ]] = g (a) »g (b) . Thus g i s a homomorphism. Si m i l a r l y , we can use (JP (B) ) "-completeness of G' i n M L to show that g i s a complete homomorphism. For each a e A, we have: g(a) = [ [ a £ G I J = [[ a e ] = h(a) , so g i s an extension of h. There are many u l t r a f i l t e r s G1 for which the above calculations hold. We w i l l select one of these which ensures the i n j e c t i v i t y of g. By Lemma 4.4(b), there i s a pairwise incompa-t i b l e family { a^ £ L : b £ B, b ^ O } such a, *c 4 0 for each a, , and each c £ A where c 4 0. b b By Lemma 0.25, there exists t e M such that a^ <_ [t t = b D / for each b e B where b 0. We pick t 1 £ 3MCL such that: I ( t 1 £ B) & ( t 1 = -t) I = 1 , i . e . t 1 i s the complement of t i n B. Now we define G' as before, but with the added proviso: [ II t' ft G* I < I t £ G' I . This amounts to generating G' from E = G*U{t} i f E i s pairwise compatible, i . e . 83 M L h ( G' i s a (IP (B)) v-complete u l t r a f i l t e r on B ) & ( G* c= G' ) & ( t' £ G* -> t e G' ) . Let b e B, and b ^ 0 . g(b) = lb £ G'l > lb = tUvttt e GM >. lib = t l - I f £ G*J >_ Vo = tj'[[-(b) £ G*IJ = Eb = tU • I (-b)v £ G*] a b • -((-b)*) . Since -b < 1; (-b) * < 1, - ( ( - b ) * ) ^ 0, and so g(b) •£ 0, by d e f i n i t i o n of a^. Thus ker(g) = 0 and g i s i n j e c t i v e . Since B i s i n j e c t i v e , the diagram indicates that each monomorphism on B ( such as g ) has a r e t r a c t i o n f, i . e . an epimorphism f such that f°g i s the i d e n t i t y map on B. If f i s a re-tr a c t i o n for g, then f i s complete, and the kernel of f i s a complete Boolean i d e a l . Id-eals of th i s type must necessarily be p r i n c i -pal , i . e . there i s an element u e B such that ker(f) = [u] = { v : v j< u } . If rng(g) ^ B, then u ^ 0 and u £ rng(g) . Define: E = { t £ B : [ [ t £ G ' ] ] ^ u } . Since dom(E) = { t : t £ E } , and E ( t ) =1 for each t £ E , a simple c a l c u l a t i o n y i e l d s : V V [ E <r G'l = II [ t E G'l = u , b y d e f i n i t i o n of t £ E of E and k e r ( f ) . But (2) above implies: u = [ [ E c G'J = I ( I I E ) V £ G'JJ = g ( I I E ) , 84 i . e . u e rng(g). We conclude that ker(f) = 1 0 ] , and rng(g) = B . Theorem 4.11 L i s homogeneous, Proof: Suppose A i s a complete subalgebra of L, and that |A| < X . Then A c: L , where: K = sup i n f { y < X : a e l 1 }, aeA Y We show that A i s a complete subalgebra of L . Let E <= A. We use superscripts to denote the Boolean operations of var-ious subalgebras. A i s a subalgebra of L, and P i s a base for the topology of L, so: E ( A ) E = Z ( D E { P . P ; £ P F P < A } aeE = £ ( L ) Z { p : p e P , p < a} . aeE K Since P i s a base for L , the above K K equals £ k E . Now we w i l l show that for each a e A , -a^ L^ e L . P may be represented as the following truncation of P: P K = '{ PK : P e P } where: p = { (a,n ,3) e p : a < i < } . IC Then L = {EX : X <= P } . Recalling K IC Lemma 4.4(a), we see that i t i s possible for p, q e P to be incompatible, due to 85 the f u n c t i o n a l i t y constraint ( i i ) . If p and q are incompatible, where p e P, q e P ; then p and q are also incom-pat i b l e . Let a e A, a = EX where X <= P , and -a ^ = EY, Y «= p. For each q e X and p £ Y, p*q - 0; and so p *q = 0 . I C Therefore: - a ( L ) = E p £ L . peY A i s thus a complete subalgebra of L. If h e Aut(A), Lemma 4.10 extends h to an automorphism h E Aut(L ). By trans-I C f i n i t e induction, we use Lemma 4.10 to define h £ Aut(L ) for each y > <: h = h K By Lemma 4.10, i f h^ £ Aut(L^), h ,, = h £ Aut(L ,,) Y+l Y Y+l h = U' h R , i f Y i s a l i m i t 6<Y P o r d i n a l . Note that for y < X a l i m i t o r d i n a l , h Y i s an embedding and rng(h ) = U L R = L , Y 3<Y Y hence h £ Aut (L ) . Y Y h.. = U h i s likewise an embedding, and • y<X Y rng(h^) = L . Thus h^ £ Aut(L), and we have produced the required l i f t i n g of h. 86 We close t h i s section with an application of Theorem 4.11 to a d e f i n a b i l i t y problem to be encountered l a t e r . F i r s t we w i l l look at a natural method of extending auto-morphisms of L to automorphisms of M L. Given g e Aut(L), we may induce an automorphism g* on by t r a n s f i n i t e induction on rank p . Let g*(0) = 0 . Suppose g* i s defined for each y e M L such that p(y) < p (x) , given an x e 3MCL. In p a r t i c u l a r , g* (y) i s defined for each y e dom(x). We define: dom(g*(x)) = g*(dom(x)) , [g*(x) ] (g*(y)) = g(x(y)) for each g*(y) e dom(g*(x)) . g* thus defined i s a b i j e c t i v e map of 3MCL onto JMEL, and g* (x) = x for each x e Mc. Lemma 4.12 Let x, y e M L, and g e Aut(L) . Then: g( Ix = yl ) = I g*(x) = g*(y) I and g( ttx e yl ) = [[ g* (x) e g* (y) 1 Proof: The two equations are proved by a simultaneous t r a n s f i n i t e induction on ( p(x), p(y) ). Ass-ume both equations are true for any z e IMLL s a t i s f y i n g p(z) < p(y) or p (z) < p(x) Then: gC Ix e yl ) = g[ I y(z)-[[z=xl ] zedom(y) = t g(y(z).) -g([[z = x] ) zedora(y) = £ Ig*(y)J (g*(.z))«Ig*(z) = g*(x)J zedom(y) = llg*(x) e g*(y)] . A similar c a l c u l a t i o n holds for the other equa-t i o n , establishing the inductive step for z sa-t i s f y i n g p(z) = p (y) • The generalization below follows from Lemma 4.12 by i n -duction on the complexity of cj). For s i m p l i c i t y , we drop parentheses where convenient. j ] Corollary 4.13 Let cj) be a formula with n free variables For each x, , ... ,x e ]MCL: 1 n glty(xir ... , x n ) l = [[cj)(g*x1, ... ,g*x n)] It i s apparent that i f cj) i s a sentence ( i . e . having no free variables ) , then I<f>] i s a fixed point for any g e Aut(L). Hence [[cj)]] i s either 0 or 1. The same reasoning gives us a 0-1 law ( see [19], p. 408, and [25], p. 171 ) for formulas whose variables range over JM. Corollary 4.14 Let cj) be a formula with n free variables For each x,, ... ,x e M : 1 n [[cj)(x1, ... fx n)I e {0,1} . Proof: For each b e L^{0,l}, we may use Theorem 4.11 to construct g, e Aut(L) such that 88 g^(b) f b . For example, define the automorphism e on the subalgebra {0,b,-b,l} by e(b) = -b , and l i f t e to g^ on L. Let b = I cb ( X l, ... ,x U . If b £ {0,l}, Corollary 4.13 implies: V V b = [[0 (g*x l f . . . ,g£x n ) I = gbf[<{> 0 ^ , ... /X n)I ^ b . Hence b e {o,l} . It i s possible to prove Theorem 0.22 from the above, since bounded formulas are of t h i s type, and t h e i r Boolean values are non-zero when they are v a l i d i n M. In the next section, we define L t as the complete sub-algebra of L generated by rng(t), where t e 3MC L. Lemma 4.15 If |rng(t)| < A, then |Lfc| < A . Proof: Since P corresponds to the basic open sets i n the topology of L, P i s dense i n L. Using the A-chain condition, we can thus fi n d for each a e L, a subset S cr P such that |S I < A, and a 1 a 1 a = ES . Let S = U{ S : a e rng(t) } . Since | S^ | < A, there i s a K < A such that S cr P . L = RO(P ) and S c L , so L c L , and K K K t K l L t l 1 l L J <- X ' 89 A generalized form of Corollary 4.14 now follows, Theorem 4.16 Let t e M be such that dom(t) c { x e M • } , and | rng (t). | < X . Then; x K<Kt')I £ L t • Proof: For each u £ L f c l e t Lt(.u) be the sub-algebra of L generated by L t u{u} , i . e . L t(u) = { (a«u) + (b--u) : a, b £ L t } . Define the following automorphism on L t(u) e( a*u + b*-u ) = (b*u) + (a*-u) e(a) = a, for each a £ L t , but e(u) = -u By Theorem 4.11, e l i f t s to g u £ Aut(L) . For each u ft L, there exists g £ Aut(L) t ^u such that g (a) = a , for a e L. , and ^u t g (u) ^ u . For each such u, g*(t) = t, ^u ^u by d e f i n i t i o n of dom(t). Hence g u(k) = b, where b = [[cj> (t) U - Since u = b yi e l d s a contradiction, we conclude that b £ L, . A l l of the constructions i n t h i s section were carried out within M, and so our many uses of AC i n various forms have been proper. In spite of the forbidding number of technical results i n t h i s section, only two of them have any application i n the sequel. These are: Proposition 4.3 (c), used i n some c a r d i n a l i t y calculations, and Theorem 4.16 90. above, which i s our s o l e a p p l i c a t i o n of the homogeneity 91 Section 5 : The Model Of Levy In previous sections we have imposed a number of plau-s i b l e r e s t r i c t i o n s on the ground model ZMC. To begin t h i s section, we add one more r e s t r i c t i o n to the l i s t : namely that M s a t i s f y the following axiom. Axiom I There exists an inaccessible cardinal. The above statement i s much stronger than the axiom A we used i n section 0 to j u s t i f y the existence of IK . Tar-ski [26] shows that a model of ZFC can be constructed i f there exists an inaccessible cardinal ( see also [14], pp. 159-63; [4], p. 109-10 ). Similar arguments show that such a model may not be a model of I ( e.g. [4], p. 110; [9], p. 37 ). Hence model existence axioms such as A cannot r imply I. The assumption M |= I i s , i n d i r e c t l y , an added con-s t r a i n t on our assumptions regarding IK . Though axiom A i n i t s present form i s not s u f f i c i e n t to provide such a IK , we s h a l l bypass t h i s problem for the present. Taking M to be the ground model containing an inac-cessible X , we may construct within M the Levy algebra L of Section 4. We f i x an M-generic u l t r a f i l t e r G on L, and i n the course of t h i s section construct the following 'tower' of generic extensions: 92 Since M \= AC, each generic extension also s a t i s f i e s AC, and therefore ~| LM as w e l l . However, the r e s u l t s of the l a s t section w i l l provide that a large family of sets of r e a l s i n IMC [G] are Lebesgue measurable. To begin, we check the behaviour of cardinals with re-spect to the above tower. Lemma 5.1 Let IE be. a model of ZFC, B be a Boolean alge-bra i n IE , s a t i s f y i n g the countable chain con-d i t i o n i n IE , and l e t H be an IE -generic u l t r a -f i l t e r on B. Then: $ = ( K i s a cardinal ) i s absolute between IE and IE [H] . Proof: F i n i t e cardinals are absolute, so we assume K _> . Suppose IE =^ $ , and. IE [H] |= ~~| $ .. Then there e x i s t s a Boolean-valued function f e IE such that for 6 < K b = [• dom(f) =6 & rng(f) = < Tj ? 0 . Since we have not defined the Boolean-valued notions of dom(f), or r n g ( f ) , we w i l l assume f s a t i s f i e s D e f i n i t i o n 0.29 and define: 93 b = n Z I. (g,y) B e f J • H , .E tt.(a,Y)B e f- H a<6 ' Y < K y < K a<6 ft 0 . . V " B We l e t b ( a , 3 ) = b • [[(a, 3) e f J '. Two facts emerge: (a) From D e f i n i t i o n 0.29(c) and Theorem 0.22, v v 6 fi y• + b ( a , B ) *b (a,Y) < b • EB = YI = 0 , as f i s a Boolean-valued function. (b) Since b ft 0, V3 < < , 3 Y > 3 , 3 a ( b ( a , Y ) f^ 0 ) . From (b) we have: |{ 3 <-K : 3 a , b ( a , 3 ) 0 }| = K . Since 6 < K, 3 a 0 such that: | { 3 < K : b ( a Q , 3 ) ^ 0 } | = K . By (a), { b ( a D , 3 ) : 3 < < } i s a set of p a i r -wise incompatible elements of B having cardin-a l i t y K . This v i o l a t e s the countable chain condition. $ i s therefore preserved under the extension IE -*• IE [H] . A routine argument shows that $ i s preserved under r e s t r i c t i o n . The c o r o l l a r y below r e c a l l s some terminology from Sec-tio n 4. P i s the c o l l e c t i o n of f i n i t e sets of t r i p l e s p = • { (a i,n i, B i n i < k s a t i s f y i n g : (a) n. eco, 3- < a. < A I I l (b) ( a,n , 3 0 ) / . C a,n , 3 1 ) e p 3 Q = 3]_ • P i s p a r t i a l l y ordered by p. < q i f f p => q. L - RO(P) . I f G is. an JMC-generic u l t r a f i l t e r on L, l e t G' be i t s i n -duced JMC-generic f i l t e r on P. We t h i n k of p e P as a func-t i o n having f i n i t e domain <= ^ .xoo, wit h p.[ (a^,n^)] = 3j_ < ou. C o r o l l a r y 5.2 JM [G] Proof: Le t 6 = to and K = A i n the proof o f the preceeding lemma. Using the f a c t t h a t L obeys the A-chain c o n d i t i o n , we i n f e r JMC r G1 ^: > (^^ . For each a < A, we de-f i n e : f a = { (n,3) : { (a,n,3) }" e G'} . From (b) above, each f i s a f u n c t i o n a i n M [G] , and f : to ->• a . For a / 0, Yn £ to, n e dom(f a) : Let A Q = { h e P : (a,n) e dom(h) } . Since a > 0, A D i s dense i n P. By gen-e r i c i t y t here i s an h £ G ' n A Q such t h a t 33, h[(a,n)] = 3 . Then {(a,n,8)} e G ' , as G ' i s a f i l t e r . n £ d o m ( f a ) . Y3 < a, 3 e r n g ( f ): Let A 1 = { h £ P : 3n £ to, h[(a,n)] = 3 } A^ i s dense i n P. The r e f o r e t h e r e i s an h e G 1 r\A 1 such t h a t h[(a,n)] = 8, so {(a,n,8)} e G 1 and 3 e rngCf^) . We conclude t h a t f o r a l l a < A, f maps to onto a. Thus A <_ ) JMC [G] 95 . Def i n i t i o n 5,3 Let s e M.[G] , s «= IMC, and s e M L be a name for s. L i s the complete sub-algebra of L generated by rng (s_) . Lemma 5.4 For each x e M, and s e IMC [GJ , Ix e sj e L g , where s_ names s. Proof: Let A be a complete subalgebra of L containing A v {0 rng (s_) . For each x e M , x e I M C a s x e M ' and {0,1} i s a subalgebra of A. Since dom (s_) L ^ c M s, [[z = x] e A for each z e dom (s_) . Thus: Ix e s] = E s(z)-IIz = x I ] £ A , z e dom (s_) by completeness of A. Our attention turns now to the f i r s t extension of the tower. The role of t h i s extension concerns the d e f i n a b i l -i t y of those sets of reals i n IMC [G] we wish to be Lebesgue measurable. We say that a set E i s definable ( i n IMC [G] ) from s £ IMC [G] , i f there i s a formula <f> having free v a r i a -bles only x, s, such that E = { x : IMC [G] |= cf>(x,s) } . For the rest of t h i s section, our in t e r e s t w i l l focus on those sets of reals i n IMC [G] definable from a sequence of ordinals. Thus s e M[G] i s a function with domain co, ranging over , the ordinals of IMC ( IMC and IMC [GJ have the same ordinals; see [25], p. 128 ) . In Section 3 we found a connection between the generic u l t r a f i l t e r s over B* and the random r e a l s . The next r e s u l t gives us a general connection between the generic u l t r a -f i l t e r s induced by G on L and the extensions ML Isj . Lemma 5.5 Let s e name s e M[G] . Then: 1 * 1 . 8 1 = M [G A j . ] Proof t Since G i s an M-generic u l t r a f i l t e r on L, G C\ L i n h e r i t s a l l the properties necessary' to make i t an M-generic u l t r a f i l t e r on L . M [ G n L A ] i s therefore a true generic exten-sion. Since for a l l x e M : M [G] [= x e s i f f I x e s I e G i f f [ x £ s ] e G Pi L, i f f we haves Let U s I f , and s e W . For each a e 0, defines <j> (s rb) ( 3 x e dom (s) ) ( b = s (x) & b e G ) o — — <hp (b) ( a i s even ordi n a l ) & a M [G H L ] h x e s s s e M [G 0 L J ( by 0.40 ) ( by 5.4 ) ( by 0.40 ), we (. S 6<a ) C 3 c e A g.) ( b = -c & c £ G ) .{. a i s odd ordin a l ). & C. a r e u A Q) ( b = s r & b e G ) 3<a 3 (s,s,b) ( i (s) - s ) & [ * c (s,b) - C aa E 0 m ) ( a < W + & ( <J>° (b) v <|>* (b) ) ] . These formulas re f e r to the following sets: A G = rng(s) , A = f-c : c e U AD} ; for a even, A a =• {EF : r <= U^,} ; for a odd. Let G a = GQA a . Since L e IMC c UN , and G D cr L, the separation axiom implies G 0 E l . If a > 0 i s even, G a = { b : <J>° (b) }, and i f a i s odd, G a = |• b : <f>^ "(b) } . So i f G R e IN for each 6 < a, then G e IN . a We conclude that GHL = { b : ^(s,s_,b) } U G e IN , and that M [GHL ] i s the <• - a -least model of ZFC extending IMC and containing {s}. ->-We say that b = b(p) e IE i s uniformly JE -definable i n p i f there i s a formula § with free variables among p, x, ->- -¥ such that for any set of values p Q of the parameters p: b(p 0) = { x : IE \= (J> (p 0 ,x) } . It i s usually not convenient to mention a l l the parameters i n p, p a r t i c u l a r l y those which are always fixed. In the co r o l l a r y below, we make no reference to such parameters as L or G for t h i s reason. Where no parameters are needed, 98 we w i l l drop the a,dverb " u n i f o r m l y " . C o r o l l a r y 5.6 GO.I' i s u n i f o r m l y M [s] - d e f i n a b l e i n g s, s» Our f i r s t diagram l e f t out an unusual a r c h i t e c t u r a l de-t a i l o f tower. The second e x t e n s i o n i s r e a l l y a s i m u l t a n -eous g e n e r i c e x t e n s i o n , r e v e a l e d below: As we s h a l l see, the upper e x t e n s i o n apparatus i s a a n a t u r a l r e p e t i t i o n of the f i r s t e x t e n s i o n , u s i n g the r e a l nunber y i n the p l a c e o f s. The lower e x t e n s i o n uses the r e s u l t s of S e c t i o n 3, on the h y p o t h e s i s t h a t y i s "almost always" a random r e a l . Roughly speaking, d e f i n a b i l i t y a s-pec t s are handled by the upper e x t e n s i o n and measure t h e -o r e t i c a spects are handled by the lower e x t e n s i o n . How do we know t h a t these e x t e n s i o n s agree? Lemmas 3.7 and 5.5 ensure t h i s . The s p e c i f i c p r o p e r t i e s o f s may now be used t o our advantage. Lemma 5,7 I f s i s a countable sequence of ordinals i n JMC [G] , i t has a name" s_ e JMCL such that; |rng(s)| < X . Proof: By Lemma 0.40, we pick s_ so that to v .. I s_ e C. Q M flu) 1 e G, where u i s some set in JM. For each n e oo, K = | { a : I (n ,ap e s ] ] ^ 0 } | < X , since L obeys the X-chain condition. By re-gu l a r i t y of X we have: | rng (s) | <_ lim ic < X . Corollary 5.8 With s_ as above, | L | < X . Proof: By Lemma 4.15 . The next lemma i s the culmination of a l l our work on the Levy algebra L and i t s associated model M [G]. The existence of X and the r e s u l t i n g homogeneity of L are cru-c i a l factors i n i t s proof. The lemma introduces a reduc-tio n i n the d e f i n a b i l i t y of sets of reals i n M[G] that places them within reach of the upper second extension of the tower. Lemma 5.9 Let E be a set of reals i n M[G] which i s de-finable from a countable sequence of ordinals s e M[G]. E i s uniformly JM [s] [y]-definable in s, s, for each y e E. 100 Proof: We represent y e E by i t s Dedekind cut. There i s a formula <J> whose only free variables are s, y, such that the following are equivalent: (a) y e E , (b) M [ G ] (= <Ky,s) , (c) ( ay e M L) (Icf) (y,s)]] e G & dom (y) = { r : r e Q } & rng(y) c L & (Yr e Q) ( r e •w y(r) £ G )) . By Lemma 5.7, we may pick s_ so that | rng (s_) | < X . For y e E we may pick a name y e M L so that |rng(y)| < X ( as a Dedekind cut, y i s definable from a countable sequence of o r d i -nals ). We define L to be the complete sub s,y algebra of L generated by rng (s_) U rng (y) . Corollary 5.8 provides that |L | < X . s_, y We note that y (r) £ G y (r) e GAL J_\ j_y s,y From Theorem 4.16, [[())(y,£)ll e G ^ I(J)(y,£)]] £ G n L . This i s the p r i n c i p a l use of the s,y * homogeneity of L. By Lemma 5.5, we have M [ G f l L ] = M[s][y] . From Corollary 5.6, we obtain: y E E i f f M [ s ] [y] h ay 4>' ( Y / Y / S f S ) . We have used the upper second extension to e f f e c t a reduction i n the c r i t e r i o n of membership i n E, from IMCfG] to M i s ] ly] . We w i l l apply the tools of Section 3 to t h i s 101 reduced c r i t e r i o n by way of the lower extension and obtain the f i r s t main theorem of Solovay. Lemma 5.9. renders E i n the parametric form of Theorem 3.14 .. The only fact we need check i s whether or not M[s] i s an appropriate ground model from the standpoint of Sec-tion 3. 3MC[s] can, i n fact, be shown to be countable ( by induction on rank, as i n [22], p. 36 1 ) . Instead, we w i l l use a more s p e c i f i c argument about cardinals that re-estab-lish e s Lemma 3..4 for the lower second extension. Theorem 5.10 Let E be a set of reals i n M[G] which i s M[G]-definable from a countable se-quence of ordinals s e JM [G]. E i s Lebesgue measurable. Proof: Each subset t of to i n M[s] has a name t e M £ with dom(t) = { h : n e ca } , and so determines a function f ^ : u ) -»- L t s_ defined by: V f (n) = II n e t I ( see 5.4 ) . Note that f. e M, . f^ = f -»-t t u Vn: II n e t J = I n e u 1 • — * I t = u 1 = 1 —> M [s] (= t = u . Thus the number of subsets of co i n M[s] cannot exceed the number of functions i n M from to into L . Using the inac-s_ c e s s i b i l i t y of X i n M and Corollary 5.2: 102 2 * 0 ) M [ s ] < A = ( ) IMC [G] The c a r d i n a l i t y of the family of Borel codes i n IMC [si i s countable i n M [G] , so there can only be countably many Borel sets of measure zero i n IMC [G] which are r a t i o n a l over M [ s ] . Lemma 3.4 and Theorem 3.14 y i e l d the r e s u l t . 103 Section 6 ; The Model of McAloon We cannot expect any generic extension of a ground mo-del of ZFC to be a model of ZF + LM. However, the Levy model i s an example of a generic extension which comes very close to s a t i s f y i n g LM, i n that a certain large family of sets of reals are Lebesgue measurable. This fact suggests a new approach. Can we f i n d a suitable submodel of M[G] whose sets of reals f a l l within the above family? In t h i s section we follow the McAloon-Solovay construction of one such i n t e r n a l model 1 c M[G]. A l l the work of t h i s sec-t i o n i s c a r r i e d out within M [G]. If ]N |= LM, the problems of Section 1 regarding the needs of analysis and measure theory become pertinent. The model 3N which we construct w i l l s a t i s f y the axiom below, known as the P r i n c i p l e of Dependent Choices: DC : If R i s a binary r e l a t i o n on a nonempty set A such that for every x e A there exists y e A so that xRy, then there i s a sequence {x^} of elements i n A s a t i s f y i n g : ( Vn e to ) ( x Rx , ) . n n+1 It i s e a s i l y shown that DC implies AC^ ( see [1.0] , p. 23 )_, and so the r e a l analysis of ET i s "normal". It i s also true that AC implies DC ( see proof of Theorem 6.12 I. As an i n t e r e s t i n g aside, our construction of UN 1Q4 w i l l establish; two independence re s u l t s previously shown by other methods: CD; The Axiom of Choice i s independent of the other axioms of ZF ( Cohen, [2] ) . C2) AC i s independent of DC (. Feferman, [6] ). D e f i n a b i l i t y i s the central concept i n our construc-ti o n of 3N . Our ultimate i n t e r e s t i s with a family of sets which are the values of abstraction terms having spe-c i a l parameters. These notions are subject to hidden d i f -f i c u l t i e s of which mention i s now made. We f i r s t look at the simplest type of d e f i n a b i l i t y . A set x i s definable without parameters ( we write: Dwp(x) ) i f : x = { y : <j) (y) } , where cj> i s some formula with one free variable. For the class of such sets we write: DWP. Our previous uses of d e f i n a b i l i t y have.been informal i n the sense that no formula cf>0 of ZF has been exhibited for which: <j>0 (x) -«->• Dwp (x) . In general, the following version of Richard's paradox prevents t h i s . Proposition 6 .1 ~| Dwp (DWP) . Proof: Since DWP i s countable for the f i r s t or-der language of set theory, undefinable ordinals e x i s t . If <j> (x) has only x free, note that y = { a : Y3 < a, <f) C3). } i s the least ordinal not definable by cf). 1Q5 We ha,ye Dwp Cy)_ f but ~] ty (jy 1, Thus, no formula having one free variable can "define" 3E DWP. Let DWP be the class- of sets IE-definable without HE parameters, i . e . Dwp (x) x = { y : 3E \= ty iy) } . Because we are working with models having set-universes, the next r e s u l t i s true. 3E Proposition 6.2 (a) Dwp Ca) i f f there i s a formula ty (x) with free variable x only, such that: HE (= Yx ( ty (x) «-> x = a ) . (b) Dwp (DWP^ ) . 3E Proof: (a) Let a e DWP . Then there i s a formula ty such that a = {y : J£ \= ty (y) }. Define tyQ(y,x) ( y e x -«-»- ty(y) ) . Then HE f= Yx ( Yy (tya (y ,x) ) <-+ x = a ) . Conversely, suppose there i s a formula ty (x) , with only x free, and 3E \= Yx(iMx) x = a) . Then a = {y : 3E |= Yx ty0 (y,*•)}, where: <j>o ( Y f X ) ( y e x +-+ ty ix) ) . (b) We arithmetize the set theory of ]E , and apply Godel numbers r<jfi to each formula cj) ( [24], pp. 175 - 95 ) . Since 3E has a set as universe, there 106 i s a A^ F formula (.. I25J , p. 193; c f . I4J , p. 9.1 ) : Sat (a, IE ,a) <-> a ~ 1 cf)"1 & IE f= 4> (a) . From (a) we haves Dwp (a) ++ IE \= ¥x(. i|»tx) x = a ) S a t ( a 0 , I E ,a) , where a 0 = rVx ( i|» (x) -> x = a i s dependent on a, and IE i s f i x e d . Next, we look a t the c l a s s o f s e t s which are the v a l u e s o f a b s t r a c t i o n terms whose o n l y parameters are o r d i n a l s . T h i s c l a s s i s known i n the l i t e r a t u r e as the o r d i n a l - d e f i n -a b l e s e t s , denoted OD. Because o f P r o p o s i t i o n 6.1, the d e f i n a b i l i t y of t h i s c l a s s w i t h i n ZF must be shown w i t h an extended form of the r e f l e c t i o n p r i n c i p l e ( [ 1 5 ] f p. 273 ). Sin c e we are working w i t h i n 3ML [G] which has a s e t as u n i -v e r s e , we can use the s i m p l e r d e v i c e o f P r o p o s i t i o n 6.2(b). We f i r s t a r i t h m e t i z e the formulas of ZF, a s s i g n i n g them g unique Godel numbers as i n [24] , pp. 175 - 95. We l e t %| denoce the s e t of Godel numbers of formulas of ZF. ^ may be thought of as a countable s e t of o r d i n a l s i n M [ G ] . Our analogue to OD must i n c l u d e an a d d i t i o n a l parameter, namely a countable sequence of o r d i n a l s , so we g i v e i t a d i f f e r e n t symbol. D e f i n i t i o n 6.3 x e OD' M[G] h (3r<!>' 107 (aa 9 • • '°n E Q M ) ( V Y ) C Y C * t, a. OD' i s the family of sets ordinal-definable i n M[G] from a sequence of ordinals. For each set of reals E e OD', Theorem 5.10 asserts that E i s Lebesgue measurable. Neither OD nor OD' are necessarily t r a n s i t i v e , as ele-ments of OD ( resp. OD' ) sets may not be OD ( resp. OD' ). OD does contain, however, a t r a n s i t i v e submodel known i n the l i t e r a t u r e as the family of he r e d i t a r i l y ordinal-def i n -able sets ( HOD ). The sets of HOD and a l l t h e i r ancestors v i a the membership r e l a t i o n are HOD. The t r a n s i t i v e closure TC(x) of a set x i s the least set containing x that i s t r a n s i t i v e . Existence of TC(x) presents no problem: Proposition 6.4 Let IE be a standard t r a n s i t i v e model of ZF. Vx e IE , TC (x) e IE Proof: Let the sequence (x } be defined: X 0 X, X n+1 = U x By standardness n and t r a n s i t i v i t y , along with the axioms of I n f i n i t y and ReplacementJ {x } e IE By the axiom of Regularity, u x = TC (x). . n n By the axiom of Unions, TC (x) e IE . These conditions are es s e n t i a l ; see [4], p. I l l 108 Just as, QD< js pur analogue to OD, our d e f i n i t i o n of UN i s analogous to that of HOD = { x e OD : TC (x) e OD } . D e f i n i t i o n 6.5 3N = f x e OD' ; TC (x) e OD' } . Lemma 6.6 1 = { x e OD' : x c I } Proof: By 6.4, TC(x) = {x} U { TC(.y) : y e x } , so x e EI i f f x e OD' & (Vy e x) (y e EJ ) . Corollary 6. 7 EI i s t r a n s i t i v e . Despite the close d e f i n i t i o n a l analogy between the class HOD and the set EI , there i s one important d i f f e r -ence. HOD s a t i s f i e s AC ( see [15], p. 276 ), but we s h a l l see that EI does not. The Myhill-Scott proof for HOD |= ZF adapts e a s i l y to EI . Theorem 6.8 EI |= ZF . Proof: (a) Since EI i s t r a n s i t i v e , the follow-ing hold ( see [9], pp. 21, 23 ): (i) EI i s extensional. ( i i ) (Xfy)1* = (x,y) . , • • • , EI ( i n ) u x = u x (iv) HP M (x) = 3P (x) H EI . These v e r i f y the axioms of Extensional-i t y , Pairs, Unions, and Powerset i n EI . Cb) EI i s standard and e n.EJ2 i s well-109 founded, so the axiom of Regularity holds i n IN , Cc) 0 e IN and to e IN , so the axioms of Null set and I n f i n i t y hold in IN . Cd) The axiom schema of Separation holds i n IN : (i) If x i s definable from parameters b^, ... ,b n which are i n OD', then x e OD'. This i s obvious from 6.3; the ordinal parameters for each b^ parametrize x, and the ordinal sequence parameters t ^ for each b^ can be amal-gamated into a single ordinal sequence parameter t for x, i n which the t ^ ap-pear as subsequences: = o 1 ^ t(k) = .t ± C j ) ; k = 2^3-0 ; otherwise ( i i ) Let f be a formula and l e t a,b, , ... ,b e IN cr OD' . Then: 1 n c = { x e a : IN \= cf>(x,b^, . . . r^>n) } e OD' from (i) . c e IN by Lemma 6.6 . (e) The axiom schema of Replacement holds i n IN : Suppose: (i) f = { (x,y) e IN2 : IN [= i>(x,y,b1 , . . . ,b ) V where b, , ... ,b j_ n J 1 n 110. E I c OD' . ( i i ) JN |= f i s a f u n c t i o n . Then f o r a e JN , c = {y : JN f= (Vx e a )c|)(x,y,b 1 ). . ...,bn)'} belongs t o OD' , as i n the argument f o r (d). T h e r e f o r e c E I by Lemma 6.6 . From P r o p o s i t i o n 6 .2(b) and D e f i n i t i o n s 6.3 and 6.5,. we see t h a t Dwp(JN). The f o l l o w i n g u n i f o r m i t y r e s u l t p r e -sents t h i s f a c t i n a more s i g n i f i c a n t and u s e f u l form. Lemma 6.9 There i s a formula cj>0 f r e e i n s, y o n l y , such t h a t : 1 I— -u- r- TNT I I c c ^n, JM [G] h x e U (3s e W 0 W ) (Vy) ( 4> 0(s fy) y • = x ) . Proof : L e t : 6 0 ( s , y ) e«})(aa 1, ... , a n e 0 M ) (Vz) ([z e y +-* <J)(z,s,a 1 # ... /« n)] & <J>0(y)) » » where <j>0 (y) -*->- TC(y) cr OD', which i s f r e e i n y o n l y ( when f u l l y w r i t t e n out i n ZF u s i n g 6.3 and 6.4 ). For any x e IN , Lemma 6.9 t e l l s us t h a t x i s u n i q u e l y determined by a sequence s e ^Q-^- • The next lemma ex-p l o i t s t h i s to show t h a t a l a r g e f a m i l y of mathematical o b j e c t s o f JM [G] e x i s t i n JN . I l l Lemma 6.10, Let h:u •> JN and h e M [G] , then h e JN . Proof: Working i n M [ G ] , we def i n e an o r d i n a l y (x) as the l e a s t o r d i n a l a such that there i s an s:co -> a such t h a t x i s the unique y s a t i s f y i n g <)>o(s,y) (. Lemma 6.9 ). Let y = sup Y(.h(n)). Using AC, we define a n we 11-ordering L o n { s : S:OJ->Y } • Let s :&) Y be the l e a s t of these s such t h a t n ' h(n) i s the unique y s a t i s f y i n g 4> 0(s,y). We amalgamate the sequences s n i n t o a s i n g l e se-quence g:w -> 0 M : g(k) = / \ i ~m_n s (n) ; k = 2 3 m ; otherwise h i s d e f i n a b l e from {s } v i a the w e l l - o r d e r i n g . n y = h(n) (Vs < s n) ( H K (s,y) ) & * Q ( s R , y ) , and {s n} i s c l e a r l y d e f i n a b l e from g. Thus, h e OD1. Since co e 3N and the axiom of P a i r s holds i n I , h c B by d e f i n i t i o n . h e 3N by Lemma 6.6 C o r o l l a r y 6.11 (a) IR M [ G ] e M . The above techniques are a l l we need to prove the l a s t two main theorems. Theorem 6.12 112 IN ^ DC Proof; Let A, R e I s a t i s f y the hypothesis of DC. Suppose {x^}^ £ n i s a f i n i t e se-quence of elements of A such that x.Rx.,, , Vi < n . Since M [G] |= AC, l l + l ' we may pick x , , e A such that x Rx ,. J ^ n+1 n n+1 for any value of n. By induction, there i s a map h:co -> A such that h(n) = x n . From Lemma 6.10, h e I . Theorem 6.13 I h LM . Proof: By Corollary 6.11, each r e a l i n M[G] belongs to IN , each closed i n t e r v a l with r a t i o n a l end-points i n IMC[G] belongs to IN , and each Borel code i n IMC [G] belongs to IN . Thus IMC [G] and IN have the same IN Borel sets. Let E cr IR , E e IN , then by d e f i n i t i o n of IN and Theorem 5.10 and Lemma 2.22, IMC [G] |= <J) (E) , where: cf>(E) +-> (3G (3N) ( y (N) = 0 & E = G^ -N ) . From Theorem 2.24 and the above: IN |= cj)(E) , i . e . , E i s Lebesgue measurable i n IN. From the assumption that there exists a model M e l 113 such, that M j= ZFC + I r we have arrived through these l a s t two sections at a model I e I s a t i s f y i n g 3N (= ZF + DC + LM . 114 Conclusion To summarize the development of the past seven sections, we w i l l present the main results i n the form of a theorem. Theorem Let IK be a non-minimal 1 standard t r a n s i t i v e model of ZFC + I . Then: (a) IK (= there i s a model of ZFC + " Every set of reals definable from a countable seq-uence of ordinals i s Lebesgue measurable " (b) IK f= there i s a model of ZF + DC + LM . We note that for IE = ( E ^ f t e ) , where E i s a set, and (j) a sentence, the statements IE |= <j> ', and IE |= ZF, are ex-ZF pressible as A x -formulas ( [4], pp. 94, 96, 97 ). Hence the statements " there exists a model of ... " are abbrev-iation s of formulas i n the language of set theory. Our point of view i s c l e a r l y d i f f e r e n t from that of Solovay [23]. His model construction takes place within the i n t u i t i v e but ambiguous "real world" of set theory, while our constructions are r e l a t i v i z e d to a fixed model IK of set theory. For t h i s reason, Solovay's construction appears i n the form of a model extension. Our actual con-stuction takes the same form of model extension, but our models M, M [G] , and IN are inte r n a l models with respect to IK . This explains the format of our main theorem above. Theorems 0.36, 5.10, and 6.8, 6.12, 6.13 provide the i . e . IK i s not the least such model. See pp. 9 - 1 0 . 115 main v e r i f i c a t i o n of t h i s theorem, except for the found-ation a l aspects to which we now return. Axiom A, which worked so well as a foundation for Sec-tions 0 - 3 , proved not to be powerful enough ( p.91 ) to ensure the existence of an inaccessible i n the ground model. Even the adoption of the much stronger Axiom I as a part of our metatheory would f a i l to do t h i s . Perhaps the best com-promise would be to introduce an axiom that guarantees the existence of at least two inaccessibles. Standard techniques ( e.g. [4], p.110 ) then produce a set K such that IK \= I . Now, supposing that K does e x i s t such that IK \= I, we must s t i l l produce a countable ground model M s a t i s f y i n g I and belonging to IK . A standard modification of the Lowenheim-Skolem-Tarski technique exists by which we can constuct a countable elem-entary submodel belonging to IK , ( IK i s non-minimal ) , which we outline ( see [12], c.f. [4] ). F i r s t we take the c l o -sure of {0} under a set of Skolem functions for IK and Mostowski-collapse t h i s to a t r a n s i t i v e set M. M w i l l be a countable elementary submodel of IK , thus M (= I. By a theorem of Levy ( [4], p.104 ) M i s h e r e d i t a r i l y countable ( |TC(M)| < O)I ) which implies that M has countable rank-( [4] , p. 103 ) . Hence M c { x e l : rank(x) < to i} e IK . The power set axiom then t e l l s us that M e l . This completes the proof of our theorem. 116 Bibliography C. C. Chang and J. H. Kei s l e r , [1] Model Theory , ( North-Holland, Amsterdam, 1973 ). P. J. Cohen, [2] Independence res u l t s i n set theory, i n : J . W. Addison, L. Henkin, and A. Tarski, eds., The Theory of Models, ( North-Holland, Amsterdam, 1965 ) 39 - 54. [3] Set Theory and the Continuum Hypothesis, ( Ben-jamin, New York, 1966 ). F. R. Drake, [4] Set Theory: An Introduction to Large Cardinals, ( North-Holland, Amsterdam, 1974 ). R. Engelking and M. Karlowicz, [5] Some theorems of set theory, Fund. Math. 57 ( 1965 ) 225 - 285. S. Feferman, [6] Independence of the axiom of choice from the ax-iom of dependent choices, J. Symb. Logic 29 ( 1964 ) 226., K. Godel, [7] The Consistency of the Continuum Hypothesis, Ann. Math. Studies 3_ ( Princeton Univ. Press, Princeton, N. J . , 1940; 7 pr i n t i n g 1966 ). 117 P. R. Halmos, [8] Lectures on Boolean Algebras, ( 196 3, rpt. Springer, 1974 ). T. J. Jech, [9] Lectures i n Set Theory with P a r t i c u l a r Emphasis On' the Method of Forcing, Lecture Notes i n Math-ematics, 217 , ( Springer, B e r l i n , 1971 ). [10] The Axiom of Choice, ( North-Holland, Amsterdam, 1973 ). K. Kuratowski, [11] Topology, 2 v o l . , trans, from French by J. Jawor-owski, New ed., rev. and augm., ( Academic Press, New York, 1966 ). A. Levy, [12] A hierarchy of formulas in set theory, Mem. Amer. Math. Soc. 57 ( 1965 ). D. A. Martin and R. M. Solovay, [13] Internal Cohen Extensions, Ann. Math. Logic 2_ ( 1970 ) 143 - 178. J. D. Monk, [14] Introduction to Set Theory, ( McGraw-Hill, New York, 1969 ). J. R. Myhill and D. S. Scott, [15] Ordinal D e f i n a b i l i t y , i n : D. S. Scott ed., Axiomatic Set Theory, Proc. Symp. Pure Math. 1_3 ( 1 )( Amer. Math. S o c , Providence, R. I., 1971 ) 271 - 278. W. V. Quine, [16] Mathematical Logic, ( Harvard Univ. Press, Cam-bridge, Mass., 1951 ). J. B. Rosser, [17] Simplified Independence Proofs: Boolean Valued Models of Set Theory, ( Academic Press, New York, 1969 ) . W. Rudin, nci [18] P r i n c i p l e s of Mathematical Analysis. 2 ed., ( McGraw-Hill, New York, 1964 ). G. E. Sacks, [19] Measure theoretic uniformity i n recursion theory and set theory, Trans. Amer. Math. Soc. 142 ( 1969 ) 381 - 420. J. R. Shoenfield, [20] The problem of p r e d i c a t i v i t y , i n : Essays on the Foundations of Mathematics, ( Magnes Press, Jerusalem, 1961 ) 132 - 142. [21] Mathematical Logic, (Addison Wesley, Reading, Mass., ]967 ). [22] Unramified forcing, i n : D. S. Scott, ed., Axiomatic Set Theory, Proc. Symp. Pure Math. 13 119 ( 1 )( Amer. Math. Soc., Providence, R. I., 1971 ) 357 - 381. R. M. Solovay, [2 3] A model of set theory i n which every set of reals i s Lebesgue measurable, Ann, of Math. 92 (1970 ) 1 - 56. G'. Takeuti and W. M. Zaring, [24] Introduction to Axiomatic Set Theory. ( Springer, B e r l i n , 1971 ). [25] Axiomatic Set Theory, ( Springer, B e r l i n , 1973 ). A. Tarski, [26] Uber unerreichbare Kardinalzahlen, Fund. Math. 30^ ( 1938 ) 68 - 89. P. V&penka and B. Balcar, [27] Generator classes i n set theory, Z_. Math. Logik Grundl. Math. 13 ( 1967 ) 95 - 98.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Boolean-valued approach to the Lebesgue measure problem
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Boolean-valued approach to the Lebesgue measure problem Sandberg Maitland, William 1977
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Boolean-valued approach to the Lebesgue measure problem |
Creator |
Sandberg Maitland, William |
Publisher | University of British Columbia |
Date Issued | 1977 |
Description | We let: ZF = the Zermelo-Fraenkel axioms of set theory without the Axiom of Choice„(AC) . ZFC = ZF + AC . I = " There exists an inaccessible cardinal " . ψ = " Every set of reals definable from a count able sequence of ordinals is Lebesgue measurable ". DC = the Axiom of Dependent Choices. LM = " Every set of reals is Lebesgue measurable In 1970, Solovay published a proof by forcing of the following relative consistency result: Theorem If there exists a model M of ZFC + I, then there exist extensions M [G] and N of M such that: (a) M [G] |= ZFC + ψ. (b) N I= ZF + DC + LM . Boolean-valued techniques are used here to retrace Solovay's proof on a different foundation and prove the following result: Theorem Let IK be a non-minimal standard transitive model of ZFC + I. Then: (a) IK |= there is a model of ZFC + ψ (b) IK |= there is a model of ZF + DC + LM . |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-02-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080111 |
URI | http://hdl.handle.net/2429/20657 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1977_A6_7 S25.pdf [ 4.88MB ]
- Metadata
- JSON: 831-1.0080111.json
- JSON-LD: 831-1.0080111-ld.json
- RDF/XML (Pretty): 831-1.0080111-rdf.xml
- RDF/JSON: 831-1.0080111-rdf.json
- Turtle: 831-1.0080111-turtle.txt
- N-Triples: 831-1.0080111-rdf-ntriples.txt
- Original Record: 831-1.0080111-source.json
- Full Text
- 831-1.0080111-fulltext.txt
- Citation
- 831-1.0080111.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080111/manifest