US SOME SIZE AND STRUCTURE THEOREMS FOR ULTRAPOWERS by MURRAY ALLAN JORGENSEN BSc(Hons), U n i v e r s i t y o f C a n t e r b u r y , 1967 MA, U n i v e r s i t y o f B r i t i s h Columbia, 1970 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n the Department of Mathematics We accept t h i s t h e s i s as conforming t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA December 1971 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the the University of B r i t i s h Columbia, I agree that 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 study. I f u r t h e r agree 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 copying of t h i s t h e s i s f o r s c h o l a r l y purposes may by h i s r e p r e s e n t a t i v e s . be granted by permission. Department of The U n i v e r s i t y o f B r i t i s h Vancouver 8, Canada Date 1% Feb. 1971 Department or I t i s understood t h a t copying or of 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 written the Head of my Columbia s h a l l not be publication allowed without my Supervisor: Dr. A. Adler ABSTRACT In this thesis we study the mapping D /A^/D, between u l t r a f i l t e r s and models, given by the ultrapower construction. Under this mapping homomorphisms of ultrapowers induce elementary embeddings of ultrapowers. Using these embeddings we investigate the dependence of the structure of an ultrapower /A^/D on the c a r d i n a l i t y of the index set I. With each u l t r a f i l t e r D we associate a set of cardinals a(D) which we term the shadow of D. the sets a(D). We investigate the form of It i s shown that i f a(D) has "gaps" then isomor- phisms arise between ultrapowers of d i f f e r e n t index s i z e s . In terms of o~(D) we prove new r e s u l t s on the properties of the set of homomorphic images of an u l t r a f i l t e r . F i n a l l y we introduce a new class of "quasicomplete" u l t r a f i l t e r s and prove several results about ultrapowers constructed using these. Two results which can be mentioned here are the following: Let a be a regular cardinal. We e s t a b l i s h necessary and s u f f i c i e n t conditions on D (i) for the c a r d i n a l i t y of a to be raised i n the passage to a,/D. (ii) for the c o n f i n a l i t y of a,/D (regarded as an ordered set) to be greater than a . + Some of the results of this thesis depend on assumption of the Generalised Continuum Hypothesis. i s a case i n point. - ii - The result ( i ) above TABLE OF CONTENTS Page Chapter 1. I n t r o d u c t i o n and P r e l i m i n a r i e s 1 A. Introduction 1 B. Set T h e o r e t i c N o t a t i o n 3 C. Relational Structures 4 D. Saturated Structures 9 E. U l t r a f i l t e r s , U l t r a p r o d u c t s , Ultrapowers 10 F. O p e r a t i o n s on U l t r a f i l t e r s 19 G. C a r d i n a l i t y o f Ultrapowers 21 Chapter 2. Images o f U l t r a f i l t e r s and Embeddings o f Ultrapowers 26 A. Isomorphism o f Ultrapowers 26 B. Images o f U l t r a f i l t e r s C. U l t r a p o w e r s as Ordered Sets 48 D. Shadow and C a r d i n a l i t y I 53 E. C a t e g o r i c a l Formulation Chapter 3. R e d u c t i o n o f Index S i z e 58 A. When 58 B. Transcendence C. Ultrapowers t h a t are D i r e c t L i m i t s 67 D. A Hierarchy of Substructures 75 , i s onto degree o f an Ultrapower - i i i- . .. 38 55 63 - iv - Page Chapter 4. Induced Isomorphisms and the Shadow 79 A. Three Algebraic Theorems 79 B. Quasicomplete U l t r a f i l t e r s 84 C. Shadow and Cardinality II 88 D. Further Results on the Shadow 98 E. Further Results on Quasicomplete U l t r a f i l t e r s 102 ACKNOWLEDGEMENTS T h i s t h e s i s c o u l d n o t have reached w i t h o u t many months o f goading Dr. Andrew A d l e r n o r w i t h o u t Mrs. E d i t h Huang. i t s present form and g u i d i n g by my s u p e r v i s o r the e f f i c i e n t typing of Thanks a l s o go t o those who read my t h e s i s i n i t s e a r l y stages and made many h e l p f u l - v - suggestions. CHAPTER 1 INTRODUCTION AND PRELIMINARIES A. Introduction Starting from a r e l a t i o n a l structure each u l t r a f i l t e r D on an index set I, c a l l e d an ultrapower of properties as /A. /A we can define, for a new*relational structure /A^/D /A^/D possesses the same f i r s t - o r d e r Ik but i s not in general isomorphic to /A. Most of the interest and attention given to ultrapowers has been directed to their application i n model theory for constructing, from a given model of an axiom system, a new model of the same axioms with certain desired properties. Hence emphasis has been on building p a r t i c u l a r powers rather than on investigating general properties of ultra- ultrapowers. The acuteness of our ignorance i n this l a t t e r area i s emphasised by the many unresolved questions r e l a t i n g to the c a r d i n a l i t y of ultrapowers. This present work represents a contribution to a "general theory" of ultrapowers whose preoccupation i s with r e l a t i n g the form of the ultrapower /A^/D with the form of the u l t r a f i l t e r To be more precise l e t us suppose that D used to define /A l i s t s among i t s r e l a t i o n s , functions, and constants a l l the f i n i t a r y relations and operations on i t s underlying set A and a l l members of A so that carries as much structure as p o s s i b l e . /A now Using this structure we define the natural notions of isomorphism between two ultrapowers /A^/E and isomorphic embedding of it. /A^/E into /A^/D. A^/D and Then we can ask - 2 - how c l o s e l y t h e isomorphism c l a s s o f the u l t r a p o w e r the u l t r a f i l t e r D. For instance u l t r a f i l t e r s on I and /A /]) = 1 A /D determines i s i t t r u e that i f D and E a r e /A^/E then D = E ? I f not, what relation does D b e a r t o E ? A l s o how many isomorphism c l a s s e s i s t h e s e t { /k /^ : D an u l t r a f i l t e r on i } 1 broken i n t o ? Of course t h e answer to. these and s i m i l a r q u e s t i o n s will depend on the s i z e o f |A|. F o r example i f A i s f i n i t e we have t h a t Ik /!) 1 = Ik = /k /E f o r a l l u l t r a f i l t e r s D and E on I . T Another k i n d o f q u e s t i o n i s (*) Given |j|, A, I and D what c a r d i n a l s can be w r i t t e n i n the form where J i s a s e t on which t h e r e u l t r a f i l t e r E such t h a t fk /!) 1 = r e s i d e s a uniform /A /E ? J In the remainder o f t h i s chapter we w i l l and c o l l e c t together some p r e l i m i n a r y In Chapter 2 we p l a c e all ultrafilters. r e s u l t s known from the l i t e r a t u r e . a n a t u r a l a l g e b r a i c s t r u c t u r e on t h e c l a s s o f We show t h a t i f we r e s t r i c t o u r s e l v e s f i l t e r s on a g i v e n t h a t the a l g e b r a f i x on our n o t a t i o n s e t I and i f we take to u l t r a - |A| s u f f i c i e n t l y l a r g e (3: |I|) o f u l t r a p o w e r s o f Z\ i s c o m p l e t e l y determined by t h i s algebra o f u l t r a f i l t e r s up t o an isomorphism o f c a t e g o r i e s . collect and prove r e s u l t s about t h i s a l g e b r a which f i n d an immediate a p p l i c a t i o n i n proving w i t h o u t the G e n e r a l i z e d a s i z e r e s u l t (2.20) n o t p r e v i o u s l y We then derivable Continuum H y p o t h e s i s . Chapter 3 a p p l i e s some o f the i d e a s o f Chapter 2 t o g i v e p a r t i a l answers to (*). Roughly speaking we i n v e s t i g a t e how "economic a l l y " an u l t r a p o w e r can be o b t a i n e d "wasteful" (up t o isomorphism), i t being t o employ too l a r g e an index s e t . T h i s i d e a l e a d s t o an - 3 - i n t e r e s t i n g c l a s s i f i c a t i o n of the substructures of an ultrapower. F i n a l l y i n Chapter 4 we present new r e s u l t s on the a l g e b r a i c structure of an u l t r a f i l t e r D and on the r e l a t i o n s h i p of t h i s structure to the c a r d i n a l i t y of ultrapowers employing D. of quasicompleteness for u l t r a f i l t e r s We define a notion that helps to express some of these r e s u l t s . B. Set-Theoretic Notation We w i l l use standard n o t a t i o n a l apparatus of set theory without s p e c i a l comment. Our informal set theory may be thought of as Zermelo-Fraenkel set theory i n c l u d i n g the Axiom of Choice, although we w i l l r e f e r to proper classes on occasion. The l e t t e r s GCH, r e s p e c t i v e l y , LCH, attached to a r e s u l t i n d i c a t e that the r e s u l t has been proved under the assumption of the Generalized Continuum Hypothesis, r e s p e c t i v e l y , the Limit C a r d i n a l Hypothesis. Ordinals are denoted by small Greek l e t t e r s although we sometimes employ these l e t t e r s to represent f u n c t i o n s . Cardinals are taken to be i n i t i a l o r d i n a l s and we s p e c i f i c a l l y designated a , 3> Y> 5 and K to range over c a r d i n a l s . This w i l l not i n h i b i t us from declaring other l e t t e r s to be o r d i n a l s or c a r d i n a l s at various places i n the t h e s i s . We w i l l allow the expression to remain ambiguous, i t s i n t e r p r e t a t i o n to be suggested by the context. For example we can w r i t e both f e A y and n < A y = - 4 - In any event ordinal exponentiation i s not intended. i s reserved for ordinal addition, but The symbol + • always stands for cardinal £ and II are used for i n f i n i t e cardinal sums, resp., multiplication. products. For any set X S(X) = {Y : Y c x} S (X) = {Y : Y c X and |Y| S (X) = {Y : Y c X and |X-Y| < K} < K} We w i l l often think of functions as sequences and employ notation to B suggest t h i s . and <f> e X Thus i f f e A f = <f fe li than a . C. X^ i s Z<X V : V < u>, write cj> = «$>^ : r\ < u> : b e B> and where f^ = f(b) and <j)^ = <))(ri)- we may a + i- s the smallest cardinal greater the weak cardinal power. Relational Structures As implies i n the Introduction we w i l l be taking a r e l a t i o n a l structure to be an ordered /A = <A, 4-tuple R, F, C> where A i s a set, R i s a sequence <R^ on A, F i s a sequence <F^ : n < A> of f i n i t a r y r e l a t i o n s : r| < u> of f i n i t a r y operations on A, : n < v> of members of A. C i s a sequence <c and A i s c a l l e d the n underlying set of /A. A i s a t r i p l e <0, T, v> The ( s i m i l a r i t y ) type of a r e l a t i o n a l structure where a e , T e 0)^ such that - 5 - (i) for a l l n < A, (ii) f o r a l l n < y, R c A : A a ( n ) T ( n ) + A C has length V . (iii) /A i s said to be a f u l l structure on A i f the range of R includes a l l f i n i t a r y r e l a t i o n s on A, the range of F a l l f i n i t a r y operations on A, and the range of C a l l members of A. With every structure Ik (or s t r i c t l y with every type <a,T,v>) there i s associated a f i r s t - o r d e r language L ^ (or L < c r ^ ^ ) > defined as follows: (1) Individual Variables are elements of the countable set {v : n < w}. n (2) Predicate Symbols for each n > X , (3) L ^ has a a(n)-ary predicate symbol P^. Function Symbols for each n < y, has a T(n)-ary function symbol G . L /iv (4) n Constant Symbols are elements of the set {d^ : n. < v } . (5) Logical = , A," i, - Symbols and a, from which ->, v, and V are defined i n the usual way. of (In defining L ^ we have taken the type A to be < a , T , v > where range (a) = X and range (T) = y. Unless another type i s s p e c i f i e d we w i l l always use these l e t t e r s to r e f e r to the type of a r e l a t i o n a l system under discussion). - 6 - The n o t i o n s o f formula and term o f L j a r e d e f i n e d by t h e standard i n d u c t i o n on l e n g t h o f e x p r e s s i o n . v a r i a b l e , and sentence of L ^ i s j u s t Free v a r i a b l e , bound a l s o have t h e i r s t a n d a r d meaning. the type o f /A. The type I f /A' i s a s t r u c t u r e o f the same type as L ^ , (j) i s a formula o f L and x e A we s h a l l say the , W sequence x s a t i s f i e s the formula (j) i n /A' and w r i t e lA h x x cj) f o r the u s u a l n o t i o n o f s a t i s f a c t i o n , i n which = i s t o be i n t e r p r e t e d as i d e n t i t y . I f cj) i s a sentence ( c f . [ 4 ] , p.56). the p a r t i c u l a r /A' sequence x i n the p r e c e d i n g i s i m m a t e r i a l and we can w r i t e and say /A i s a model o f cj) o r cf) h o l d s i n /A' . I f £ i s a set of 1 sentences then /A' i s a model o f N <J> 1= cj) f o r a l l <J> e J> i f f /A' For each s t r u c t u r e /A the theory T ^ i s d e f i n e d as the theory w i t h language L ^ and w i t h axioms a l l sentences {cj) : IA 1= belonging t o the s e t cj)} . In g e n e r a l T ^ i s n o t r e c u r s i v e l y axiomatisable. An embedding f : lA^ -> IA^ between two r e l a t i o n a l s t r u c t u r e s of the same type <a,T,v> i s a 1-1 map f : /A^ -> lA^ such t h a t (a) f o r a l l n < A and any elements a^, a2> ...» < (b) i a a(n) > € R l n i f f < f ( a i } f o r a l l n < y and elements a ^ * ^ F (c) a l n (a ;...,a i for a l l n < v f ( c m ) = c 2n T ( n ) f ( a a ( n ) a t(n)' } a a ( > a ) = a i f f F ^ ( f ^ ) , .. . , f (a ) £ n e 6 T ( n ) R ^ 2n ^1 ) ) =f(a) - 7 - Ik and Throughout the r e s t o f t h i s s e c t i o n IB a r e s t r u c t u r e s o f type <a,T,v> and L = L .. = L . m /A IB I f lk £ B we say t h a t fk c /A i s a s u b s t r u c t u r e o f IB and w r i t e IB i f f the i n c l u s i o n map i : A -> B i s an embedding o f /k i n t o IB. I t i s easy to see t h a t t h i s i s the case i f f each r e l a t i o n and each f u n c t i o n o f (B r e s t r i c t s t o the c o r r e s p o n d i n g r e l a t i o n o r f u n c t i o n of /A and each constant o f IB i s e q u a l t o t h e c o r r e s p o n d i n g constant of Ik. An embedding i s s a i d t o be an isomorphism I f t h e r e i s an isomorphism between i f i t i s onto. Ik and IB we say t h a t Ik and IB a r e i s o m o r p h i c and w r i t e Ik = IB. I f fk c (B and f o r every every 4>(v_,...,v ) o f L and any a„,...,a e A w e have O n O n /A r= ( ( i ( a . . . , a ) n) u we say t h a t elementary i f f IB 1= ()>(a ,...,a ) n u n /A i s an elementary formula n s u b s t r u c t u r e o f IB o r t h a t IB i s an e x t e n s i o n o f /A and w r i t e /A < JB I f f o r every sentence (J) o f L we have t h a t say t h a t A. N $ i f f IB i= (f> then we i'k and [B a r e e l e m e n t a r i l y e q u i v a l e n t and w r i t e N o t i c e t h a t = i s an e q u i v a l e n c e r e l a t i o n and t h a t An embedding h : /A ->• JB i s c a l l e d an elementary any formula <j) (VQ ,.. . , v ) o f L and any aQ,...,a /A A first whenever then 1= <|>(a 0 a ) n /A = IB. i s transitive. embedding i f f o r e A i f f (B i= ^(h(a ) Q h(a )). o r d e r t h e o r y T i s s a i d to be model-complete i f IB and € are models o f the s e t o f axioms o f T and (B < C • n IB £ C - 1.1 8 - Theorem If /A i s a f u l l structure then T ^ i s model-complete. Proof: (After Adler [2]). Let (B and <E be models of T ^ such that iB c £ . We wish to show that for any formula <j> (VQ ,. . . ,v ) of L ^ n iB t= <j>(bp,.. . jb^) i f f and any members bQ,...,b e B we have that n <E (= cj>(bQ,... ,b^) . symbols i n cf). We proceed by induction on the number of l o g i c a l It i s easy to show that the result i s true i f cj) i s an atomic formula or i f <> j is cj)^ and cj)^ or cj)^ A cj^ where the result holds for <f>2. Suppose that < > f = axijj(x,bQ,. . . ,b^) where for a l l b e B N i[)(b,b ,.. . ,b ) i f f C t= ^(b,b ,.. . ,b ) . iB n then Q Clearly i f IB 1= cj)(b ,. . . ,b ) Q n The converse w i l l f a i l only i f C f= cj>(b ,. . . ,b^) C 1= <j)(bg,.. . jb^) . but there i s no b e B such that h \j)(b ,b^,.. B . ,b^) . Assume that t h i s Let R(x,y) be a r e l a t i o n of Ik that well-orders A. Pick n+1 a e A, and define f e A such that f(a„ a ) i s the least element U n i s the case. A A of A under R such that t= tjj(f (ag,.. . ,a^) , aQ,...,a ), or f(aQ,...,a ) n = a i f no such least element e x i s t s . of /A, corresponding, by the induction hypothesis n eC» i f C |B (= C 1= 0 ip(t(bQ,.. . ,b ) ,bg,.. . ,b ) . n n this i s a contradiction. i= a( x)ij)(x,b (t (b^, .. . jb^) jb^,. .. jb^) so that But for f= <£(CQ, .. . ,c ) then t(cQ,...,c ) i s the R-least element of C such that IB Then as /A i s f u l l f i s a function say to a function symbol t . Now by assumption a l l CQ,...,c n b ). Q <C n *= i j j ( t ( c , . . . ,c ),c~,...,c ). But u n u n A So there i s b e B such that iB t= ijj(b,bQ, • • • >b ) , n // - 9- fk by <A,R In the following we denote the structure If X, Y £ A we say that X generates Y i f Y i s the smallest subset of A such that X u range(C ^) £ Y and i f a^,a^,...e Y and operation i n range (F ,.) then F (a..,...,a ) eY. /A T| X i s an n-ary I f X i s a subset of A n that generates i t s e l f then we can define a substructure H of A, the r e s t r i c t i o n of A to X as follows: i) H =X R ^ lH,n = R A, n x G ( n ) f V n A,nV<--> C r 3 1 1 n K X ^ r aim <y =F 1 V ) o n f l /A = H i s denoted by A | C v . A. D. Saturated Structures Recall that the type of fk i s taken to be <a,T,V>. I f X = <e^ : ^ < 0> i s a sequence of elements of A we define a structure A°x to be the structure formed from a f t e r the sequence A°x A by attaching the sequence x C ^ to form a new sequence of constants. i s a structure of type <a,T,v+6>. Thus (The sequences of r e l a t i o n s and functions and the underlying set of /A are not changed.) For any structure of formulas of L . IB of a r b i t r a r y type l e t f^-^ be the set with at most V Q free. Take A £ j - ^ We s h a l l say that A i s s a t i s f i a b l e i n B i f there i s a b e B such that IB t= <f>(b) for a l l <$> e A and that A i s f i n i t e l y s a t i s f i a b l e i n B i f every f i n i t e subset of A - 10 is satisfiable in tB. F i n a l l y we X of elements of The results, 1.2 A to be a - s a t u r a t e d i f , f o r a l l sequences l e n g t h l e s s than a, any satisfiable theory but we define A having that i s f i n i t e l y - in subset Jk°X i s a l s o s a t i s f i a b l e of i ^ o x in /A°X. of s a t u r a t e d s t r u c t u r e s forms a l a r g e body o f need o n l y the following: Theorem (a) If /A and jB are a - s a t u r a t e d , elementarily s t r u c t u r e s o f the same type, and then (b) If lk and IB are IB H /A, embedded i n = |B| = a, isomorphic. Ik i s an a - s a t u r a t e d and i f |A| equivalent, where |B| s t r u c t u r e of c a r d i n a l i t y < a, then tB can be a elementarily /k. Proof E. (a) See [ 4 ] , p.224, Th. (b) See [ 4 ] , p.226, Th. U l t r a f i l t e r s , Ultraproducts, 3.1. 3.2. // Ultrapowers A f i l t e r D on a set I i s a non-empty subset that YeD. is (a) X, Y e D i m p l i e s X n Y e D ; I f 0 / D, D i s c a l l e d ultrafilter is sufficient (c) X e D and Y = X a proper f i l t e r . i n c l u d e d i n no o t h e r p r o p e r f i l t e r n e c e s s a r y and (b) o f S(I) i s called such implies A proper f i l t e r an u l t r a f i l t e r . c o n d i t i o n f o r a proper f i l t e r to be X c I implies either X e D o r l - X e D . that A an For - 11 - For any i e I the s e t [ i ] = {X c i i s an u l t r a f i l t e r on I . : i X} e An u l t r a f i l t e r o f t h i s form i s c a l l e d A f a m i l y E c S ( I ) i s s a i d to have the f i n i t e (fip) 1.3 i n t e r s e c t i o n property s u b f a m i l y of E has non-void i f any f i n i t e principal. intersection. Theorem Any f a m i l y E c S ( I ) h a v i n g the f i p can be extended to an ultrafilter on I . Proof A classical 1.4 and easy a p p l i c a t i o n o f Zorn's Lemma. // Theorem 2 IH There are 2 d i s t i n c t u l t r a f a l t e r s on an i n f i n i t e set I. Proof See [ 4 ] , p.108, Theorem 1.5. As t h e r e are c l e a r l y o n l y it f o l l o w s t h a t "most" u l t r a f i l t e r s // |I| p r i n c i p a l u l t r a f i l t e r s on I on I a r e n o n - p r i n c i p a l . An u l t r a f i l t e r D can be regarded as a measure on the s e t of s u b s e t s o f I i n the f o l l o w i n g For way: each X c I d e f i n e y (x) D 1 i f X e D 0 if X = i D then i t i s a consequence o f ( a ) , (b) and (c) t h a t U D is a finitely - 12 - additive {0,l}-valued measure on I. This way of regarding D as a measure i s a valuable aid to i n t u i t i o n as i t makes available analogies with measure theory. In this s p i r i t , i f we have a proposition P concerning the members i of I we w i l l say "P(i) holds for almost a l l i i n I (mod D)" so long as {i e I : P ( i ) holds} e D . If the context makes the meaning clear we w i l l drop the q u a l i f i c a t i o n "(mod D)". Consider, now, a sequence of r e l a t i o n a l structures < /A^ : i e I> each of type <a,T,v>,and an u l t r a f i l t e r D on I. We B = IT< IA^ : i £ I> / D define the ultraproduct of the sequence </A. : i e I> modulo D as follows: 1 a) Underlying set Let B' be the set IHA^ : i e I>. Define an equivalence relation ~ on B' as follows: D a ~ b D i f a, b e B' set i f f ' { i e I : a. = b . } e D x i i . e . a = b almost everywhere. Then we write a/D for the equivalence class of a under ~^ and take B to be the quotient set {b/D : beB'} of B' under ~ . b) Relations Take R. to be the r\~^ r e l a t i o n of A. where n. < A. Then i f 0(n) = n and a^/D, a^lVi, B,n R so n t h a t <a /D,...,a /D> e 1 a /D e B we define n i f f {i : < . ,. . . ,a > R. > e D. a± nl e >n - 13 - c) Functions L e t x ( n ) = m, then we F iB,n ( a l define F ""' m / D a m tB,n by J = /° / D ) a iff {i d) i , -B.Tl " where defined F a l i S / a m i * = i * a e D ' ( n < 1-0 • ° g ( i ) = c. remains (n < v ) . , to v e r i f y t h a t R to , F p and C _ a r e a l l w e l l - lt> by ( b ) , (c) and (d).. But t h i s i s an easy c a l c u l a t i o n . I f each f a c t o r then we c a l l /A^ Is the same, say /A^ = the r e s u l t i n g s t r u c t u r e B = The the f o l l o w i n g 1.5 ( n Constants C It : A / D I importance /A f o r a l l i e I , B an u l t r a p o w e r o f /A and w r i t e . o f u l t r a p o w e r s and u l t r a p r o d u c t s arises from "Fundamental Theorem": Theorem (Los' Theorem) Let lA^ ( i e I ) be as above and l e t cj) be any formula o f _ and D any u l t r a f i l t e r L = L <CT,T,V> on I . J Then Jl< IA. 1 : i e : /A. l I > / D t= < j > x iff {i e where x = < I Q / D , f ^ / D , I f= x. l cf>} e D ...> i s any c o u n t a b l e sequence o f members o f - 14 - : i e I>/D and x = <f (i), f-^i), i Q . ..>. Proof See [4], p.90, Theorem 2.1. 1.6 // Corollary (i) i f (J) i s a sentence of L IT< k : i e I>/D ± /A. r= d) for almost a l l i e I. iff (ii) y= 4> I /A = fk /!). 1 Proof Immediate from 1.5. // In fact we can strengthen part ( i i ) of 1.6. \ :A A^/D be defined by has constant value a. fA into of a^ /A^/D. setting l(a) = f /D where f : I -> A a a Then we claim that i i s an elementary embedding For i f (J)(VQ,V^, . . . »v ) i s any formula of L and n a^ any elements of A we have by 1.5 that Ik I'D 1 t= <J>(f /D, .. . , f /D) a a 0 n A iff { i : /A t= <|>(f ( l ) , . . . , f ( D ) } e'D a„ a 0 n iff { i : Ik F iff l For l e t Ik ^(a-,.. . ,a )} e D U n F (Ka,-.,.. . ,a ) . u n i s c a l l e d the canonical embedding of Ik i n Ik I'D. We now discuss certain types of u l t r a f i l t e r s i n the formation of ultrapowers. that are useful Let I be an a r b i t r a r y i n f i n i t e set. - 15 - A p r i n c i p a l u l t r a f i l t e r on I i s remarkable i n that i t contains an element of c a r d i n a l i t y 1. By way of contrast we c a l l an u l t r a f i l t e r D on I uniform i f for any X e D we have |X| = | l | . 1.7 We have immediately: Theorem An u l t r a f i l t e r on I i s uniform i f f i t contains the f i l t e r S (D, a 1.8 where a = |I| . II Corollary Uniform u l t r a f i l t e r s exist on sets of arbitrary cardinality. Proof By 1.3 and 1.7. // P r i n c i p a l u l t r a f i l t e r s are closed under arbitrary intersec- tions of t h e i r elements: i n fact this property characterises p r i n c i p a l u l t r a f i l t e r s among a l l proper u l t r a f i l t e r s . For i f D i s a non-principal u l t r a f i l t e r on a set I and we take X. = I - {i} then X. e D f o r a l l i i i e I but : i e 1} = 0 I D. n{X We c a l l an u l t r a f i l t e r E g-complete i f every intersection of 8 members of E belongs to E, otherwise E i s B-incomplete. for a l l B < y Thus i f | l | w e s a Y E i s ^-complete, I f E i s 8-complete otherwise E i s y-incomplete. = a , every a-complete u l t r a f i l t e r on I i s p r i n c i p a l . Every u l t r a f i l t e r i s to-complete by d e f i n i t i o n . If | l | = a > 03 i t i s natural to ask i f there are any cT-complete non-principal u l t r a f i l t e r s on I. This question and the related question of whether there exist - 16 - any co-complete non-principal u l t r a f i l t e r s in the history of set theory. on I are famous problems The f i r s t , and most seminal, work on these questions i s the paper of Ulam [12]. It i s known that the answer to both questions i s negative for a wide class of cardinals a that includes a l l cardinals commonly encountered of mathematics. 1.9 i n most branches We have the following r e s u l t . Theorem There exists an a and an co-complete non-principal u l t r a f i l t e r on a i f f there exists a 3 > w and a ^-complete non-principal u l t r a f i l t e r on 3 • Proof [4], p.112, Theorem 1.11. // Thus i f we can find an co-complete non-principal u l t r a f i l t e r we can find an a-complete non-principal u l t r a f i l t e r on some a > co. The hypothesis that such u l t r a f i l t e r s of measurable cardinals. active study. exist i s known as the axiom This area of set theory i s s t i l l under The word "measurable" here r e s u l t s from thinking of an u l t r a f i l t e r D as the {0,l}-valued measure u ^ , which turns out to be countably additive i f f D i s co-complete. Measurable cardinals are those cardinals a which support co-complete non-principal u l t r a filters. Usually we work with CO-incomplete There i s an equivalent way w i l l sometimes use ultrafilters. of stating a-completeness that we - 1.10 17 - Theorem D i s an a-complete u l t r a f i l t e r {X^ : n < a'} o f a' < a subsets e D f o r some n_ X n of I, U on I i f f f o r every C^ X : <a } n collection e D implies 1 < a'. o 0 Proof A r o u t i n e a p p l i c a t i o n o f de Morgan's laws. Ultrapowers taken // u s i n g complete u l t r a f i l t e r s do n o t y i e l d new s t r u c t u r e s : i n f a c t we have the f o l l o w i n g r e s u l t . 1.11 Theorem I f D i s a-complete and |A| < a then Ik^/D = Ik. Proof Under the hypotheses we w i l l onto. show t h a t a : Ik F o r suppose f/D e A^/D, and l e t X /k^/D i s = {iel : f(i)=f 3. Then u{X X a € D. a (i)=a}. cL : aeA} = I e D and so by 1 . 1 0 t h e r e i s a~ e A such t h a t 0 J Hence f ~ f D a 0 and f/D € range (i). // o We w i l l now d e f i n e another k i n d o f p r o p e r t y an u l t r a f i l t e r can have which a l s o stands i n a n t i t h e s i s to the p r o p e r t y o f b e i n g principal. Let K-covering K be any c a r d i n a l . A family X £ s f o r m a s o f I i f f o r each i e I |{X e x An : i e X}| < K . (K,A)-regulari f u l t r a f i l t e r D on a s e t I i s c a l l e d there e x i s t s a K-covering ){ o f I such t h a t X £ D a n & !xl = A - An - 18 - ultrafilter 1.12 i s called simply regular i f i t i s (to, 11| ) - r e g u l a r . Theorem (i) (ii) I f | I | > a) t h e r e If | l | e x i s t s a r e g u l a r u l t r a f i l t e r on I . = OJ a l l n o n - p r i n c i p a l u l t r a f i l t e r s on I a r e regular. (iii) Any r e g u l a r u l t r a f i l t e r i s u n i f o r m and to-incomplete. Proof (i) L e t cj> : I -»• S ^ ( I ) be a 1-1 onto f u n c t i o n , and s e t X ± = { j e l : iecKj)}- Then we c l a i m t h a t X = {x^ : i e l } has the f i p . For let {X. ,...,X. } be a f i n i t e subset o f x. Then x ' x 1 n t h e r e e x i s t s i ^ e I such t h a t 4>(1Q) {i^»'»*»i } = n and hence ± e X. O x n 1 n ... n X. . x n to an u l t r a f i l t e r F on I . So by 1.3 X extends J F i n a l l y x i s an oo-covering as |{j (ii) : i e X }| = |<f>(i)| < O) . / As noted above a l l n o n - p r i n c i p a l u l t r a f i l t e r s set o f c a r d i n a l 03 are 03-complete. on a L e t {X^ : n<0)} be a c o l l e c t i o n o f members o f D such t h a t X=n{X it n :n<03>^D. i s c l e a r that Y n Then i f Y = XnnX. n .. . n X n 0 1 n e D f o r a l l n < 0) and t h a t (Y^ : n < 03} i s an 0)-covering (iii) -X I f D i s r e g u l a r l e t {X^ of I by members o f D. of I . / : n < 111 } = x be an 03-covering Then nlX^ : n < 03} = 0 I D - 19 - so that D i s 03-incomplete. I f D i s not uniform l e t X e D be an element of the smallest c a r d i n a l i t y . Then |X| = |x n for a l l n < | I | . < |l| X j But this implies there i s x e X such that |{n =| l | , : x e X^}| a contradiction as x i s an co-covering. F. // Operations on U l t r a f i l t e r s We w i l l be employing various ways of constructing new ultrafilters from given u l t r a f i l t e r s i n this thesis. We describe them here. (1) Restriction Given an u l t r a f i l t e r D on I and a member X of D , the r e s t r i c t i o n of D to X i s an u l t r a f i l t e r D|^ on X given by D| v = {Y n X : Y e D } . A It i s easy to check that D| filter. SO defined i s an u l t r a - Note that any u l t r a f i l t e r can be r e s t r i c t e d to a uniform u l t r a f i l t e r . (Take X to be a member of D having smallest c a r d i n a l i t y . ) Conversely i f we have an u l t r a f i l t e r E on a subset J of I we can expand E uniquely to an u l t r a f i l t e r D on I by setting D = {X c I : X n J e E} Thus D can be recovered from any of i t s r e s t r i c t i o n s . - 20 - (2) Product Given u l t r a f i l t e r s D on I, E on J we define an ultra- f i l t e r D x E on I x J by X e D x E where (3) X^ Infinite i f f {j : X ^ e D} e E = {i : <i,j> e X}. Sum Suppose we have a family { i ^ : A e A} of d i s j o i n t sets with u l t r a f i l t e r s on 1^ and E on A. Then we can define an u l t r a f i l t e r D on u{'I^ : A e A} by X e D (4) i f f ' {A :,X n I^.e D^} e E We write D = O u , : A e A}, hj A Image If D i s an u l t r a f i l t e r on I and f i s a map from I into J we can define an u l t r a f i l t e r E on J by X e E iff f ( X ) e D. _ 1 We write E = f(D) i n this s i t u a t i o n . Now 1.13 : we prove the following theorem about (2). Theorem Let D be an u l t r a f i l t e r on I, E an u l t r a f i l t e r on J, and /A any structure. Then T T ~ [ /A /D] /E = 1 J /A TXT / DXE . Proof Let cj) : ( A ) ^ 1 (j>(<hj : j e J>) = k A where xh./D 1 ^ be the standard i d e n t i f i c a t i o n , i . e . k ( i , j ) = h^ ( i ) . Then : jeJ>/E = <hj/D : jeJ>/E - 21 - iff {j : { i : h . ( i ) = h!(i)} e D} e E iff {<i,j> : h (i) = h!(i)} e D x E iff {<i,j> : k ( i , j ) = k ' ( i , j ) } e D x E iff ^ < h j : ^ £ J > )/ D x E <K j = <h : 3 J>)/DXE e So i f we define !j> : [A /D] /E -> A I (j)(<h /D : jeJ>/E) = <j> (<h. J IxJ /DxE by : jeJ>)/DxE then cj) i s well-defined, 1-1, L and c l e a r l y onto. i—* We can e a s i l y check that cj) preserves a binary r e l a t i o n R of R ^ by repeating the above argument with "R" i n place of "=". The argument for general relations and functions i s no more d i f f i c u l t . Thus we see that <j> i s an isomorphism. G. // C a r d i n a l i t y of Ultrapowers We c o l l e c t here some known r e s u l t s that w i l l be used i n the following chapters. In this section we w i l l take D to be an u l t r a f i l t e r on a set I of cardinal y - » w 1.14 a n < i a a n d 3 arbitrary. Theorem (a) a< (b) I f D i s uniform ly /!*! > Y (c) 1 <a Y 1 (i) I O V D I (ii) (d) | ct /D | 6 < |(aV/D| |(aV/D| <- laVDl ^ ! If a i s f i n i t e 1 |a/D| = a I 0 - 22 - (e) i f D i s regular and a > co | ot/D | = a X then Y If D i s co-incomplete then i f a > OJ (f) I^/DJ" = |ot/r>|" . x Proof (a) is trivial. (b) i s proved by a diagonal argument. For complete proof see [4], p.132, Theorem 3.19. / (c) ( i ) Consider the map $ '.(oft) <K<h ± : i e I>) = k 1 i f f k(n)(i) = h (n) ± •> (a ) 1 3 given by for a l l n < 3 . Notice that i f <h. : i<I> ~ <h! : i e I> and $(<h! : iel>) = k' l D I I then k(n) ~ D k'(n) for a l l n < 8. So $ induces a map $ : (aV/D -»• (a /!)) . 1 6 Further i t i s clear that $ and $ are onto. also 1-1, but $ need not be.) |(aW| Consequently s |(aV/D|. (c) ( i i ) Consider the map * : (a ) 3 (a )^ 1 1 given by "p(<lu : i e I>) = k where k i s given by k ( f ) = g iff g(i) = h ( f ( i ) ± for a l l i e I. ip induces a map : (aV/D -* ($ i s (a-/B) &1/1) / - 23 - such that "K ^ <n : i e I>/D) = k where k i s given by k(f/D) = g/D i f f g ( i ) = h ( f ( i ) ) for almost a l l i i n I (mod D). It i s readily checked that the d e f i n i t i o n s given for k and ip do not depend on p a r t i c u l a r choices from equivalence classes. We now show that lp i s 1-1: suppose that <ru : i £ I>/D 4 <h| : i £ I>/D then 4 h^} e D {i : h so there i s an f e 6 * such that {i : h ( f ( i ) ) 4 h | ( f ( i ) ) } ± hence i f k = •p(<h : i £ I>/D) e D and k' = -|;(<h^ : i i e I>/D) then k(f/D) 4 k'(f/D) and so k 4 k'. (d) follows from 1.11 as a l l u l t r a f i l t e r s (e) We prove a l i t t l e more: suppose D i s (OJ,A)-regular and a > GO, then |a /D| > a \ x Let <A^ IA 1 n Let A ± : n < A} be an c o - c o v e r i n g of I by members = = (n : i e'X }, then A i i s f i n i t e for a l l i e I. : n < c o > be a sequence of d i s j o i n t subsets of a such that 1 I = a and l e t "b : a n -> A n If f £ n be 1-1 maps. and {r\ ,. . . ,n } = A £ S (A) where J_ < n 2 < ••• < i w k e define 9 : 03 rC set f*(A) Now are co-complete. / Then (e) follows when A = y« I of D. / = <f(n ),...,f(n )>. 1 k •+ a} by (9f)(i) = \P |A j (f*(A.)) Let - 24 - Let 9 : a* -> a^/D be such that 9f = 0 f / D . I f f , g e then there i s n < A such that f(n) ^ g(n) and f 4 g hence i f i e X^, f * ( A ) 4 g*(A ) ± ± so that {i : 6 f ( i ) 4 6g(i)} e D and 6f 4= 0g. Thus 0 i s 1-1 and the conclusion follows. (f) see [ 2 ] , p.130, Theorem 3.16. / This result i s also a c o r o l l a r y of 1.16. / Remark The result (b) i s proved i n Frayne, Morel, Scott [7]. ( c ) ( i ) i s found i n K e i s l e r [11]. ( c ) ( i i ) i s a result of A. Adler and appears i n [3]. (e) i s proved i n K e i s l e r [8], where a discussion of the h i s t o r y of the result i s given. 1.15 Corollary < |(2 ) /D| < 2 l (g) 2 (h) i f |(2 ) /D| > 2 (g) Set a = 2 i n (c) and apply (d). (h) follows from (g). 6 3 3 I I 3 0 l / D l . then | 6 / D | > g. I Proof H. J . K e i s l e r i n [11] generalises the argument of 1.14(e) to prove the following r e s u l t . // - 1.16 25 - Theorem Let D be (K,X)-regular and l e t {X^ : n < A } c D b e a K-covering of I, then \ll<a ± : ieI>/D| X < | < a K i 1 : ieI>/D| where K. = | { n : i e X } | < K . // From this result can be derived ( c ) ( i ) , s h a l l refer to 1.16 as Keisler's Lemma. other consequences of this r e s u l t . (e) and ( f ) . We Later we w i l l indicate CHAPTER 2 IMAGES OF ULTRAFILTERS AND EMBEDDINGS OF ULTRAPOWERS A. Isomorphism of Ultrapowers In this chapter we s h a l l explore a natural notion of homomorphism between u l t r a f i l t e r s . We w i l l be using this notion of homomorphism to describe various embeddings and isomorphisms of ultrapowers. In the case of u l t r a f i l t e r s on countable sets this concept has been studied extensively i n Booth [5], where i t i s attributed to H. J . K e i s l e r and M. E. Rudin. An u l t r a f i l t e r pair i s an ordered p a i r <I,D> i n which the second component i s an u l t r a f i l t e r on the f i r s t . I f <I,D> and <J,E> are u l t r a f i l t e r pairs a map h : I -»• J i s said to be a f i l t e r morphism i f E = h(D) i . e . X e E i f f h ( X ) e D. -1 h : <I,D> •+ <J,E>. We then write I f h i s 1-1 onto i n the above we s h a l l say that h i s a f i l t e r isomorphism and that the u l t r a f i l t e r s D and E are isomorphic (written D ~ E). An alternate d e f i n i t i o n of isomorphism of two u l t r a f i l t e r s would be to say that D = E i f there exists a map (j) : D E with an inverse and preserving u and n. Sirota [15] that this i s an equivalent I t i s proved i n definition. We w i l l say that D and E are equivalent i f there are X e E, Y £ E such that D J = E J . X i s indeed an equivalence y We write E ss D. The r e l a t i o n r e l a t i o n on the class of a l l u l t r a f i l t e r s . A l l p r i n c i p a l u l t r a f i l t e r s form one class under equivalence. If D and E are u l t r a f i l t e r s on sets of the same c a r d i n a l i t y then D = E - 26 - - 27 - i f f D x E. For i f D and E are u l t r a f i l t e r s on sets I and J respec- t i v e l y such that |I| = |J| > 03 and there are X e E, that D| we can show D = Et = E| Let f : X -»- Y be a 1-1 onto map We may assume |l-x| = |j-Y| = such that V e E[ and l e t g : I-X •> J-Y be any 1-1 onto map. h : I->Jbyh| x = f, b.| Y e E such |l|. i f f f ( V ) e D| - 1 Then i f we define = g, i t i s easy to check that h i s 1-1 onto and that Z e E i f f h ( Z ) e E and hence D = E. _ 1 Many properties of u l t r a f i l t e r s apply to a l l u l t r a f i l t e r s in a si-class i f they apply to any i n the c l a s s . One example i s (K , A.)-regularity. In contrast the property of being uniform never applies to a l l u l t r a f i l t e r s i n a w-class as each class contains u l t r a f i l t e r s of a r b i t r a r i l y a l l expansions of a given u l t r a f i l t e r . large cardinal, e.g. However we can define the thickness th(D) of an u l t r a f i l t e r D to be the smallest cardinal of a set i n D. Thus th(D) = min{|x| : X e D> . It i s clear that a l l u l t r a f i l t e r s i n a given s-class have the same thickness. The following theorem i s proved i n Booth [5] for u l t r a - f i l t e r s on a countable set. H. J . K e i s l e r , M. E. Rudin, and K. Kunen are given credit for independent proofs of the r e s u l t . The proof we give here i s a s l i g h t modification of Booth's. 2.1 Theorem Let <I,D> be an u l t r a f i l t e r p a i r and f : I -»• I a function such that f(D) = D then {i : f ( i ) = i} e D. - 28 - Proof Let < be an arbitrary well-ordering of I and set X = { i : f ( i ) < i} and Y = { i : f ( i ) > i } . We w i l l show X I D Y ^ D , i . e . X u Y ^ D . and Let f ^ denote the n-fold i t e r a t e of f. Then set (n) X = { i : n i s the least integer such that f ( i ) I X } (l<n<co). We have that u { X : 2 < n < 0)} = X , f o r , as < i s a well-ordering, n n each i £ I must belong to some X and X.. = I - X . I f ° n 1 X , , = u { X _ , . : n < OJ} and X = u { X . ,„ : n < tu} then odd 2n+3 even 2n+2 X ,, n X odd even =0, X odd u X even = X and X . = f odd _ 1 ( X even ). So by hypothesis X , , e D i f f X e D , hence we must have X , , , X I D odd even odd even J C and X )! D . I f we define Y and Y , , i n the corresponding way even odd we cannot prove Y = Y u Y ,. but we can prove Y u Y ,, i D . even odd even odd If now remains to prove that Y ' = Y - ( Y u Y ,,) i s not a even odd (n) member of D . For each y e Y ' l e t = {f (y) : 1 < n < 0)} be the orbit of y under f . Then i t i s easy to see that we can represent Y' as a d i s j o i n t union of orbits u{C. : y e Z} for some Z c Y ' . (Remember that f(y) > y for a l l y e Y ' , the f i r s t member of Z chosen would be the least member of Y under < ). Now l e t Y ' , , = {y : y i s an odd member of i t s orbit} odd 1 Y' = {y : y i s an even member of i t s orbit} even and argue as before to conclude Y ' I D . Now we define E < D i f there exist Y e E, X e E and f : X -»- Y such that E| = f (D | ). The next result shows that < i s a p a r t i a l ordering on the s equivalence classes. // - 29 - Theorem 2.2 (a) i f E < D and D' ~ D, E* « E then E* < D'. (b) E < D and D < E implies E & D. (c) E < D and F < E implies F < D. Proof (a) and (c) are easy. (b) suppose E| and Y, Y 1 e E. Y = f(D| ), x D| , = g ( E | , ) where X, X x As D| x and D | , are equivalent x on sets of equal c a r d i n a l i t y we have D| Y 1 eD By part (a) we can assume that |x| = |X'| = th(D) and |Y| = |Y'| = th(E). E| Y = D| , and s i m i l a r l y = E | , and there exist 1-1 onto maps p : X' ->- X, Y such that p(D| ,) = D| X and q(E| ) = E | . x y p[g(q[f(D| )])] = D| x y l q : Y -* Y' Then . x So by 2.1 there i s X* e D, p(g(q(f(i))) = i . ultrafilters X* c X such that i f i e X*, But this implies i s 1-1 and as Y = f(X ) eE we have f : D j * = E| * , so that D ss E. x The following theorem shows the r e l a t i o n between homomorphisms of u l t r a f i l t e r s and embeddings of u l t r a powers. 2.3 Theorem If h : <I,D> > - • <J,E> i s a f i l t e r morphism then for any structure lk i f h^,. : A /E J •* /k /D i s defined by 1 // - 30 - h^ (g/E) = h ° g / D ( 1 ) A we have (a) h ^ i s an embedding (b) i f h i s 1-1 then h ^ i s an isomorphism. Proof (a) To see that h ^ i s an embedding suppose that R " i s an n-ary r e l a t i o n of 7k. : n Then i f • and R^' are the corresponding r e l a t i o n s of lk. /D and /A /E J respectively we have that <g /E g /E>£T 1 iff iff = iff iff n S Q)> {j : <g (j) h ({j - 1 e R> e E n x n : < g ( j ) , . . . , g ( j ) > £ E^}) e D 1 n {i : < (h(i)),...,g (h(i))> e R } e D gl n <h ( /E) , . . . ,h (g /E)> e R^ . # # g;L n By s i m i l a r arguments we can show that h ^ i s 1-1 and that functions and constants are preserved. (b) I f h i s 1-1 then every f e A^" can be written as hog for some g e A^. (1) Hence h^ i s onto, and hence an isomorphism. We employ the diagram convention for writing compositions of functions: I ^—f J h°g A f so h o g ( i ) = g(h(i)) // - 31 2.4 - Corollary (a) I f E < D then /A /E can be (b) I f E « D then /A /E = J J embedded i n /A /!). 1 /A^"/D. Proof T h i s c o r o l l a r y . f o l l o w s from 2.3 for any once we have proved t h a t <I,D> i f X e D /A /D| s X In f a c t i f we V define a /k /T> . Z map <>j : A / D | - X by cj)(f/D| ) = k/D, X where k | x A /D X = f and x k i s a r b i t r a r y on I-X, i t is not hard to show t h a t <}) i s an isomorphism. We there f r e q u e n t l y drop the s u b s c r i p t " /A" can be no confusion. elementary embeddings. is a full /A can be structure. is A We For the g e n e r a l expanded to a f u l l = h^, structure constants. i s an embedding of /A' by i s contained embedding w i t h r e s p e c t to l . always i n the case t h a t new Then the argument of 2.3 /A'^/D, and i s an shows hence to the language L ^ t - so t h a t h ^ /A structure a d d i t i o n of /A'^/E i n t o i n l ^, when are case note t h a t any an elementary embedding w i t h r e s p e c t the language L ^ from " h ^ " remark t h a t the maps h ^ T h i s i s c l e a r from 1.1 r e l a t i o n s , f u n c t i o n s , and that h ^ // But elementary T h i s r e s u l t can a l s o be proved directly. /A To what extent among embeddings k : A^/E are embeddings of the A^/D ? The form h^ typical f o l l o w i n g theorem shows - 32 - that i f /A i s large enough and has enough r e l a t i o n s and functions l i s t e d then, indeed, a l l embeddings are of this form. 2.5 Theorem Suppose that k : /A^/E ->• /A^/D i s an embedding. Then i f |A| > |J| and fk l i s t s a l l unary r e l a t i o n s and unary functions of A then k can be written i n the form h^ for some h : I -»• J . Proof Let f e A^ be a 1-1 function and l e t g e A* be any function such that k(f/E) = g/D. Pick a fixed j . e J and define h : I — > J by If ( g ( i ) ) i f g(i) e f(J) 1 h(i) = otherwise We claim that h(D) = E and that k = h (a) # h(D) = E It s u f f i c e s to prove that f(E) = g(D). of A and l e t P Then so y /A /E J be a corresponding predicate symbol of L j . j= P ( f / E ) i f f /A /D 1 y *= P (g/D) y {j : /A |= P ( f ( j ) ) } e E y iff {i : /A h P (g(i))}..e D Y i.e. {j : f ( j ) e Y} e E i.e. f (Y) e E and hence Let Y be any subset _ 1 i f f {i : g ( i ) e Y} e D i f f g (Y) e D f(E) = g(D). - 1 - 33 - (b) h # = k By p a r t by 2.3 h it (a) h i s a f i l t e r morphism h : <I,D> : /A^/E •> /A^/D i s an embedding. ( f / E ) = k ( f / E ) = g/D. and t , t 1 0 If t e A A <J,E> so C l e a r l y we have i s any unary f u n c t i o n o f a r e the c o r r e s p o n d i n g f u n c t i o n s o f IA /E, A /A /D r e s p e c - t i v e l y we have h ( t ( f / D ) ) = t (g/D) # 1 2 k ( t ( f / D ) ) = t (g/D) 1 2 as k and h ^ a r e homomorphisms. of A^/E o f the form t ^ ( f / E ) f o r some unary f u n c t i o n t ^ o f /A^/E. But, i n f a c t , for Thus h ^ and k agree a t a l l members some t e A i f £/E i s any element o f A^/E we can w r i t e SL = f°t A as f i s 1-1. and k agree a t a l l arguments Hence £/E = f o t / E = t (f/E). 1 # So h i n t h e i r common domain A^/E. // Remarks (i) I t i s important t o observe i n c o n n e c t i o n w i t h 2.5 t h a t even i f t h e embedding k i s an isomorphism may s t i l l n o t be 1-1. (ii) We may c a l l for a structure onto h > (Or even "almost" 1-1.) IA t h a t has unary r e l a t i o n s every subset o f i t s u n d e r l y i n g s e t A and unary o p e r a t i o n s f o r each f u n c t i o n from A t o A amongst its r e l a t i o n s and o p e r a t i o n s a f u l l on A. /A. unary structure I n p a r t i c u l a r 2.5 a p p l i e s t o a l l f u l l structures - 34 - 2.6 Corollary Let A be a f u l l be such t h a t unary s t r u c t u r e and l e t <I,D>, <J,E> | j | < |A| then /A /!) = 1 /A /E J i f f D ~ E. Proof 2.4(b) g i v e s us h a l f t h e r e s u l t . The converse d i r e c t i o n f o l l o w s from 2.5 and 2.2(b). // We can a l s o make t h e o b s e r v a t i o n and t h a t i f /A i s f u l l |J| ^ |A| then any embedding o f (A /E i n t o an u l t r a p o w e r 2 i s n e c e s s a r i l y elementary, and i s p o s s i b l e i f f E < D. unary /A^/D This i s a consequence o f 2.5, 2.4(a), and t h e f a c t t h a t a l l t h e embeddings J h ^ are elementary. The f o l l o w i n g example shows t h a t the c a r d i n a l i t y r e s t r i c t i o n in 2.6 cannot be removed. 2.7 Theorem (GCH) Let /A be any s t r u c t u r e on A. Then we can f i n d <I,D>, <J,E> (a) such t h a t | I | = |J| = |A| + /A IT) = /A /E J 1 E ^ D (b) such t h a t | I | = | J | = |A| + /A /E -< /A /!) J E i D. 1 - 35 - Proof (Informal) Let K = | l | . K e i s l e r i n [9] and [10] has i n v e s t i g a t e d a c l a s s of u l t r a f i l t e r s on I which he terms the K^-good u l t r a f i l t e r s . The two r e s u l t s that we s h a l l need about these u l t r a f i l t e r s are the f o l l o w i n g : (1) 2 There are 2 (2) If + K -good u l t r a f i l t e r s on I . K /A i s a s t r u c t u r e with |L-^J < K and D i s a K -good u l t r a f i l t e r on I then /A^/D i s a K -saturated s t r u c t u r e . + (a) As there are only 2 functions from I to I each K u l t r a f i l t e r on I i s equivalent to at most 2 other u l t r a f i l t e r s on I . So by (1) there e x i s t K -good u l t r a f i l t e r s D and E on I such that D 56 E. I AI lAl + I f IA i s any s t r u c t u r e on A then | L ^ | < 2 < 2 =K + + so that /A^/D and /A^/E are of c a r d i n a l i t y K . + (b) saturated structures So fk I'D = f^/E by 1.2(a). 1 Let <I,D> be as i n ( a ) . There are 2 2 ultrafilters K F on I such that F < D, but 2 u l t r a f i l t e r s on I . Let E be any u l t r a f i l t e r on I such that E j£ D. Then l/A^/El < K + and hence /A^/E can be elementarily embedded i n /A /!), by 1.2(b). // 1 We mention the f o l l o w i n g consequence of 2.6 and 2.7: For any f u l l s t r u c t u r e A /D X A we can f i n d <I,D>, <J,E> such that = 7A /E J but ( /AV/D r ( /A ) /E A J A A where Ik i s a f u l l s t r u c t u r e on A . I t i s l i k e l y that t h i s can be proved without the assumption df the GCH. - 36 - Theorem 2.7, i n contrast with e a r l i e r r e s u l t s , shows up a strong d i s t i n c t i o n between ultrapowers with index set larger than the base A, and those with index size < |A|. We note next a result which shows that ultrapowers of this l a t t e r kind have a simple characterization. 2.8 Theorem (Adler) Let /A be a f u l l unary structure on A. generated by a single element i f f A^/D = Then /A^/D i s /A^/E for some <J,E> with |J| < |A|. Proof. (a) <= We can assume |'I| ^ |A| . any 1-1 function. A^/D. We claim that f/D generates For l e t g/D be any member of A^/D. there i s a function t : A But as Let f : I ->• A be Then A such that g = f°t. fk i s f u l l unary there i s a function symbol t i n L ^ corresponding to t . Then i f t ^ i s the interpretation of _t i n A^/D we have g/D = fot/D = t ^ f / D ) . Hence {f/D} i s a set that generates (b) => A^/D. Given f/D e A^/D, consider the set {g/D : g/D = t ( f / D ) for some t e A } = S A 1 (using the notation of part (a)). As lk i s f u l l unary i t i s easy to see that S i s closed under the functions of F ^ and i s hence the set generated by {f/D}. Now assume that f/D generates A^/D. Then - 37 - S = A^/D the and each member o f A^/D can be w r i t t e n i n form t (f/D) = 1 * A fot/D A some t e A . for C o n s i d e r the embedding it I A f : /A /E -> where E = f ( D ) . /A /D By d e f i n i t i o n ( c f . 2.3) of f ^ c o n s i s t s o f a l l elements i n A^/D f # the range o f form A ( t / E ) = f o t / D f o r some t e A . So f # i s i n f a c t onto and hence A ~ Ik /E = Ik I /D. Remark In any u l t r a p o w e r of L ^ c o r r e s p o n d i n g to X c A we Ik ID 1 i.e. |l| /A^/D iff x Thus i f see by the above t h a t i f Ik i s f u l l unary, In t h i s case D can i n t e r p r e t D as b e i n g e q u i v a l e n t properties of a generating symb X e f(D) o f p r o p e r t i e s " o f f/D. g e n e r a t e d by f/D where f i s 1-1. we i s a unary p r e d i c a t e have »= T ( f / D ) f(D) i s the " u l t r a f i l t e r < |A| we if T element. /A^/D is f(D) so t h a t to the u l t r a f i l t e r of - 38 - B. Images o f Ultrafilters In t h i s s e c t i o n we c o l l e c t ultrafilters and f i l t e r morphisms. and prove r e s u l t s about In p a r t i c u l a r we study the c o l l e c t i o n o f images o f a g i v e n u l t r a f i l t e r . 2.9 Definitions (a) a(D) = d f {th(E) : E < D} We c a l l a(D) the shadow o f D. I t i s the c o l l e c t i o n o f c a r d i n a l s a such t h a t D has a u n i f o r m ultrafilter on a as an image. (b) An u l t r a f i l t e r D i s a-descendingly incomplete if t h e r e e x i s t s a sequence <X^ : n < a> o f members of D such t h a t n' < n < a i m p l i e s such t h a t "fX^ : n < a} = 0. n (a-d.i.) , £ X^ and Such a sequence we. w i l l c a l l an a-chain i n D. D e s c e n d i n g l y incomplete u l t r a f i l t e r s by C. C. Chang i n [ 6 ] . A l l OJ-incomplete u l t r a f i l t e r s i n f a c t an u l t r a f i l t e r D i s a-incomplete some 8 such t h a t U) < 8 ^ O i . is clear. To see " o n l y n{X^ : n < a} I D. = „ M Y ryrl n x a i n l d i f " suppose Define sets Y Y, = n{Y A o r d i n a l £ a. are c o - d . i . , i f f D i s OJ-d.i. for t h a t D i s a-incomplete f o r {X^ : n < a} £ D such t h a t i n d u c t i v e l y so t h a t Y : i] < A} i f A i s a l i m i t r) L e t u be the l e a s t o r d i n a l such t h a t Y^ i D. u i s a limit studied Here t h e p r o o f i n the " i f " d i r e c t i o n Then t h e r e i s a c o l l e c t i o n some a > co. were f i r s t Q = X , Q ordinal, Then i t i s c l e a r t h a t So f o r some c a r d i n a l S such t h a t - 39 - Ui < & < a there i s a sequence of ordinals <n^ with y. It i s easy to see that <(Y rij- D. : E, < g> that i s c o f i n a l -Y ) : £ < 8> i s a 8-chain i n y Thus i f an u l t r a f i l t e r D i s a-incomplete a knowledge of what chains exist t e l l s us something about " i n what way" D i s incomplete. We also make the observation here that i f D i s a - d . i . and 8 i s c o f i n a l with a then D i s a - d . i . Thus D i s a - d . i . i f f D is cf(a)-d.i. The next theorem shows the connection between the shadow a(D) of D and the set of cardinals a for which D i s a-d.i. 2.10 Theorem Let D be an u l t r a f i l t e r on I, and a a regular cardinal. Then a e a(D) infinite i f f D is a-d.i. Proof (i) Assume a e a(D). Then there i s a p a i r such that E < D and th(E) = a. We <J,E> can assume that | j | = a and that E = f(D) for some f : I -> J . Well-order J so that J = {i : n < a} and take X to be the set {jg. : V < £ < a} Then <X : n < a> i s an a-chain i n E. But then n <f "'"(X ) : 11 < a> i s an a-chain i n D, so that D i s a-d.i. (ii) Assume D i s a-d.i., and l e t <X^ in D. : n < a> be an a-chain Define f : I -* a by taking f ( i ) to be the least ordinal £ such that i I X^. Let E = f(D). We claim that E i s uniform ( i . e . th(E) = a) i f a i s regular. Suppose that Y e a and |Y| < a. Then by r e g u l a r i t y of a there i s a n i l < a such that Y £ n_. But then - 40 - f (Y) x so that f c f- ^) £ i - x "*"(Y) i D and hence 1 n + 1 YI E. Hence E i s uniform, and thus a e a(D). 2.11 // Corollary For a l l a , a l l D , D is a-d.i. iff cf(a) £ a ( D ) . // Notice that ( i ) does not use the r e g u l a r i t y of a so that for every a a e a ( D ) implies D i s a - d . i . Also the proof of ( i ) shows that i f E i s a uniform u l t r a f i l t e r on J then | j | e a(E) E is and |J|-d.i. For a l l < I , D > we have by d e f i n i t i o n that a ( D ) £ {a : a ^ |I|}, Of course i f 1 < n < to then n I a ( D ) as there are no uniform u l t r a f i l t e r s on f i n i t e sets with more than one element. Apart from this r e s t r a i n t c r ( D ) can be large. 2.12 Theorem For any set I there i s an u l t r a f i l t e r D such that to < a < | l | implies a e a ( D ) . Proof We s h a l l define a sequence < D ^ : n e On> with the following properties: i s a uniform u l t r a f i l t e r on to^ i) ii) n 1 ^ n implies D^,< of ultrafilters - 41 - Let DQ be any uniform The construction i s by induction. u l t r a f i l t e r on o o and suppose that the u l t r a f i l t e r s D have been n constructed f o r a l l n < X. Case 1. X = 6+1 Let F be any uniform u l t r a f i l t e r on OJ^ and the u l t r a f i l t e r D ^ X F then E < D ^ X F , (j) : WgXo)^ on ^g ^. x S O i f we define D -* o^ i s 1-1 onto then ( i i ) (with n = consider I t i s easy to see that i f E ^ on o o ^ by = cj)(DgXF) where = D^xF and s a t i s f i e s ( i ) and X). Case 2. X i s a limit ordinal. Let F be an u l t r a f i l t e r on X which extends the c o l l e c t i o n of sets {Cj. : £ < X} where u l t r a f i l t e r on 0)^ x {n} = I u l t r a f i l t e r D' = O D ' t D C» = {n : E, < r\ < X}. isomorphic to : r) < X} on u{l T\ Let D' be an and consider the : n < X} = I'. We claim r) < D' for a l l n < X. For suppose n < X,. then D < D^. for a l l E, < X such that ? > n. So by 2.2(a) we have Dg. <. E, l e t f r : I_ be such that f| u{l' : 1, < n}.) I For each such be such that f>-(Dl) = D' , and l e t f : I = f . r 1 -* I (It i s immaterial how f i s defined on Then f(D') = D', £ for i f X c I n. f ( X ) = u { f ( X ) : E, < X}. _ 1 for n < £ < X. _1 then ~ n If X e D j then f ^ C x ) e D£ E, such that X] < E, < X so that f ( X ) e D', and i f X i _ 1 i n the same way that f ^(X) i D'. and the fact that C^ e F. for a l l i t follows A l l this i s by d e f i n i t i o n of D' - 42 - Now th(D') > OJ I' 1 = to, and as n < X implies D < D' we have that A n for a l l r\ < X, and so th(D') = OJ. . n A F i n a l l y we define D' on OJ^. I t i s clear that to be an u l t r a f i l t e r isomorphic to has the required properties. // If an u l t r a f i l t e r D i s regular then D i s a - d . i . for a l l a such < a < |l|. that This follows from lemma 2.2 of [12] which e s s e n t i a l l y : ri<A> i s a K-covering of I by observes that i f .X i s regular and <X^ elements of _D'where K < X, = then" SY^ y:-q < A> i s ^ a . A - c h a i n i n D where f f u{X^ : n < £ < A}. This observation can be e a s i l y checked by the reader. Note that this does not render 2.12 t r i v i a l as i t merely proves that i f D i s regular then a e a(D) for a l l regular a such that OJ < a < 111 . It i s possible to relate the descending incompleteness of a product u l t r a f i l t e r to the descending incompleteness of i t s factors. 2.13 In fact we have the following r e s u l t . Theorem Let D and E be any u l t r a f i l t e r s and 8 any c a r d i n a l . Then DxE i s B-d.i. i f f either D or E i s 8-d.i. Proof Suppose <X^ i s a 8 chain i n DxE. - <I x Y : n < 8> i s a 8-chain i n D: then <X^ x J : n < 8> S i m i l a r l y i f <Y^ : n < 8> i s a 8-chain i n DxE. : n < 8> i s a B " " cna i n i n E then - 43 - Conversely, suppose that <Z^ : n < B> i s a 8-chain i n DxE then for a l l n < U = {j : If U = n{U { i : <i,j> e Z } e D} e E. : n < 8 ) = 0 then we have that <U n a 8-chain i n E. Otherwise we have that for a l l j £ U = { i : <i,j> e Z^} £ D : n < 8> i r) (n < 3 ) . Pick any j £ U, then <V^ : n < 8 > i s c l e a r l y decreasing and i f i £ n{V^ : n < 8 } then <i,j> £ n{Z^ : n < 8 ) = 0. This contradiction shows that n {V^ : n < 8 ) = 0 and hence that : n < 8 > i s a 8-chain i n D. <V n J By the same methods we can show that £ < D . : i £ J> i s E 3 i f f either E i s 8 - d . i . or D. i s B - d . i . for almost a l l 8-d.i. 3 j £ J (mod E) . We define the spread of an element f/D of an ultrapower A /D by I spread (f/D) = min{|range(f')| : f' ~ f ) D With this d e f i n i t i o n we can generalise 1.11. Note that the canonical embedding i : A—^A^/D i s onto i f f each element of A"*"/D has spread 1. 2.14 Theorem The ultrapower A ^ " / D contains an element of spread 8 ^ | A | iff 8 e 0(B). - 44 - Proof Suppose that f/D e A ^ D and spread (f/D) = 8. assume that |range(f)| = 8. Let E = f(D). Clearly th(E) < 8. If th(E) < 6 there i s an X e E such that |X| < 6, Pick X Q e X and define f ' f(i) Then f ~ Q f ( X ) e D. _ 1 : I -»• A by ff(i) = / (JXQ if i e f (X) _ 1 otherwise f but |range(f')| < 8 a c o n t r a d i c t i o n , so that th(E) = 8Then i f 8 < |A| we can find Conversely suppose 8 e c(D). E on A and g : I We can A such that E = g(D) and th(E) = 8. We claim that spread (g/D) = 8 *. (i) spread (g/D) > 8 as i f g* ~ D g and |range(g*)| < 8 then g*(D) = g(D) = E and so th(E) < 8. (ii) spread (g/D) > 8 f o r , as i n the f i r s t part of the proof, we can find g ' ~ D g with |range(g')| ^ 8 - // It i s natural to ask what sets of cardinals can be expressed as shadows of u l t r a f i l t e r s . the form {8:8=1 or Our result 2.12 shows that any set of 0) < 8 ^ ot} can be so expressed. We also must require of any set S that i s a shadow that a e S implies cf(a) e S. Another condition on shadows i s a consequence of the following result of Chang [6]. Chang's Theorem Let D be any u l t r a f i l t e r . (a) If D i s K - d . i . + and K i s regular, then D i s K - d . i . - 45 - I f D i s K - d . i . and y = cf(<) < K then either D (b) i s y - d . i . or f o r some 8 < K D is y-d.i. for a l l regular y such that 8 < y < K . Chang's proof of this r e s u l t uses the G.C.H. but subsequent proofs of the result by Kunen and Prikry i n [12] are free of this hypothesis. We w i l l now give the proof of Prikry that appeared in [12] of a r e s u l t s l i g h t l y stronger than Chang's Theorem. F i r s t we need a combinatorial 2.15 lemma from Ulam [17]. Lemma Let X be any i n f i n i t e cardinal. <A^ : a < X, of subsets of X (i) (ii) (iii) + Then there i s an array n < X> + with the following properties: a 4 a' implies A^j n A^, = 0 n 4 n' implies A^ n A^ |X + =0 {A : p < X}| < X P n for every n < X . + Proof For every E, < X elements of X. + l e t <a^ : p < £> be a sequence of d i s t i n c t Take A - {£ e X a (i) and ( i i ) are s a t i s f i e d . :a = a}, then i t i s clear that TI To see that ( i i i ) holds notice that i f £ e X - u{Ap : p < X} then or i s not defined, so that £ < n. Hence |X -u{A + n : p < X}|< |n| < X. // - 46 We - t h i s a r r a y as a XxX can r e g a r d % m a t r i x w i t h set e n t r i e s . > + 1 - Then each row and c o l l e c t i o n of subsets of X + each column forms a p a i r w i s e , and 2.16 Theorem disjoint the columns, i n f a c t , p a r t i t i o n X except f o r a set of c a r d i n a l i t y at most X . a r r a y s are c a l l e d Ulam A These and similar matrices. (Prikry) Suppose D i s X - d . i . , then e i t h e r + D is cf(X)-d.i. (i) or (ii) there i s a r e g u l a r c a r d i n a l a < X such t h a t (a,X )-regular. D is + Proof Let Set B n a = u{A We (*) n P : a < X, <A^ : p < n < A > + c l a i m that S £ X , 0 < X and + n{B^ : I e < a such t h a t T e A s} 2.15. . |s| > \a\ implies = 0 : £ e S}. r r the Ulam m a t r i x of a}, For suppose t h a t T e ^{B^ a p be Then f o r each £ e S t h e r e is + - 47 - Since | s | > \a\ there are £, n e S such that £ 4 r\ and p r = p so that x e n A" i n contradiction to 2.15(H). 1 1 Thus the claim (*) i s v e r i f i e d . + + Let D be X - d . i . , then since A e a(D) D' = f(D) on A + that i s uniform. D has an image Since any a-chain or a-covering we may find i n D' can be l i f t e d v i a f to D we can start o f f by 1 assuming that D i s a uniform u l t r a f i l t e r on A . There are two cases + Case I For some n < A Y= A all + - u{A^ : p < A} = A + i D (a < A). - U{BJJ : a < A} + If Y I D as |Y| < A, then If we set X = A a + - (Y u B ) N a then <X : a < A> i s a A-chain i n D and hence D i s A-d.i. and a consequently c f ( A ) - d . i . Case II Case I f a i l s . such that B" 11 |T| = A + and O e D. Then for each n < A Then there i s a T c A + + there i s a o"^ < A and a O < A such that = C for a l l n e T. Then by the claim (*) proved above <B^ : r) e |a| -covering of A + + by members of D. T> is a So D i s (a,A )-regular where + - 48 - In view of the remarks following the r e s u l t 2.12 construction of chains from coverings i t i s clear that 2.16 Chang's Theorem. on the implies We w i l l be proving a d d i t i o n a l r e s u l t s on the form of shadows 0"(D) l a t e r i n Chapter 4. C. The Ultrapower as an Ordered Set We consider now the s i t u a t i o n i n which the structure Ik has no operations or constants but merely a single binary r e l a t i o n RQ, where RQ i s a linear ordering r e l a t i o n . R Q and <A, < ^ for <' on A^/D Ik. We s h a l l write < for The r e l a t i o n < on A induces a r e l a t i o n given by f/D <* g/D We i f f f ( i ) < g ( i ) for almost a l l i (mod D). can see e i t h e r d i r e c t l y or from Los' Theorem that <' i s a l i n e a r ordering. I f A i s i n f i n i t e and < i s a well-ordering of A i t i s not hard to see that <' i s a well-ordering i f f D i s oj-complete. This fact i s proved i n [4], p. 134. The following theorem was suggested by ideas of K e i s l e r [8], p.405, and shows the connection between <' and the descending i n completeness properties of D. K e i s l e r i n h i s paper [6]. Chang quotes s i m i l a r r e s u l t s of Recall that l : A A^/D i s the canonical embedding. 2.17 Theorem Let A be well-ordered by < i n type |A| = a. i s c o n f i n a l i n A^/D (w.r.t. <') i f f D i s not a - d . i . Then \(A) - 49 - Proof (a) Assume t h a t \ (A) i s bounded i n A^/D by some We w i l l show t h a t D i s a - d . i . element f/D. {a^ : n < a} <. Then i (A) = (g^/D : n<a} i g/D be the elements o f A as w e l l - o r d e r e d n < a. e I, Let Now where g ^ d ) for a l l n < a by = a^ f o r a l l we have <* f/D. = { i : a^ < f ( i ) } e D and i t i s c l e a r t h a t So : n < a> i s an a - c h a i n i n D. <X n (b) -»-. Define i : n < a> Suppose t h a t <Y^ e Y n i s a c h a i n i n D. f : I ->• A so t h a t f ( i ) = a ,, whenever n+i - Y . n+1 I t i s easy t o see t h a t f/D i s an upper bound f o r \(A) i n A /D. // I We w i l l o f t e n drop some f o r m a l i t y and regard the above as p e r t a i n i n g to u l t r a p o w e r s o f c a r d i n a l s . say: "a i s c o n f i n a l i n a^/D orderings i f f D i s not a - d . i . " [f/D] will (The embedding and determines an i n i t i a l = {g/Dec^/D : g/D<' There i s a n a t u r a l map where n. = f ( I ) : n<n i : i e I> + segment f/D}. o f the u l t r a p r o d u c t II<n^ : ieI>/D induced by the i n c l u s i o n map J_ 1 Thus we being understood.) Each member f/D o f a^/D i n t o a^/D results like a 1 - 50 It i s easy to see its range i s [ f / D ] . and initial initial that ^ Thus we - i s well-defined, 1-1, can pass f r e e l y between segments of u l t r a p o w e r s . Notice, now the r e g u l a r i t y prove a s l i g h t l y though, t h a t less t r i v i a l p r o p e r t i e s of an u l t r a f i l t e r of an ultrapower. 2.18 Theorem L e t A be a regular cardinal, that ultraproducts segment corresponds to many ( c l o s e l y r e l a t e d ) We and one ultraproducts. r e s u l t which connects to the order properties D a uniform u l t r a f i l t e r on A. + Then e v e r y s e t of ^ A + A • + elements o f A /D i s bounded above 4- in A /D i f f D i s (A,A )-regular. Proof We 2.15 and w i l l be u s i n g the s e t s B^ different from of 2.16. the a < A. B^ a<A, n<A > of + employ a case d i v i s i o n asserts that there e x i s t s column of the Ulam m a t r i x f o r which B^ In f a c t we will I D for a l l n We can Case I I * = not slightly e still Case I * . a column, i D for a l l assume f o r our Case I * t h a t t h e r e A"^ such columns, i . e . there and We : 2.16. Case (I) of 2.16 say the Ulam m a t r i x <A^ S, i s a subset S £ A such t h a t + exist |s| = A + O < A. recover the c o n c l u s i o n of Case I I from For i f ( I I * ) a p p l i e s t h e r e A columns w i t h the p e c u l i a r i t y d e s c r i b e d from the m a t r i x to form a new above. are at most These can be m a t r i x to which the argument of deleted (II) a p p l i e s . - 51. - + (i) Assume that any set of X bounded above. members of X X + /D i s I f Case I I * holds we can conclude as i n 2.16 that D i s ( a , X ) - r e g u l a r for some a < X + + and so that D i s (X,X )-regular. there i s S £ X such that |S| = X + a l l n e S and a l l a < X. {f c I f Case I* holds : E e S} £ X I D for and + We define functions by fp if ie (.0 if i e X - u{A^ + x + Let g/D be an upper bound i n X p < X} P /D for the set {f /D : £€S}. Then we have X = { i : 0 < f g ( i ) < g(i)} e D. ? E But i f p = f g ( i ) = f ^ i ( i ) > 0 so £ = £'by 2 . 1 5 ( i i ) . E' then i e A^ n A^ and Hence no two f's take the same p o s i t i v e value at i , f o r any i £ X . + Hence \{E_ : i e X } | < | g ( i ) | < X ? so that {Xg : E e S} i s a X-covering of X + by members of D, and D i s (X,X )-regular. + (ii) Assume that D i s (X,X )-regular and that + + {f^/D : ri X } i s any set of X < Let {X of D. elements of X : n < X } be a X-c overing of X X + /D. by members - 52 - Define f n f g (i) n ( i ) 1 =f 10 then e x n otherwise and as |{n : i e X^}| < A and A i s regular we have that ~p sup {g^U) : n < A } + e x i s t s , and i s less than A . We denote t h i s sup by g ( i ) . Then we can show e a s i l y that g/D i s an upper bound f o r {g /D : n<A } = {f /D : n<A }. // + n Remarks (A) We used the assumption that A was regular only i n section ( i i ) of the proof. An inspection of this section shows that for a l l A we have the implications: (1) D i s (cf(A),A )-regular + implies(2) Every subset of A'* /D of power < A i s bounded 1 + above i n A /D implies (3) (B) D is (A,A )-regular. + We have shown i n 2.7 that i t may be true that /A where /D = A fk = < A , /A A /E , < ^ and | A | = A , but that D ^ E. Notwithstanding this negative result we see by 2.18 that D and E have t h i s much i n common: D i s (A,A )-regular + iffE is. - 53 - D. Shadow and C a r d i n a l i t y , I Many c a r d i n a l i t y questions a ( D ) of an u l t r a f i l t e r D i s known. can be s e t t l e d when the shadow For example i f D i s an u l t r a f i l t e r on I and cf(y) e a ( D ) we have (*) I-C^/DI 7 < | ( a ( Y ) ) I / D | . This follows from K e i s l e r ' s Lemma (1.16) as follows: Let X = {X^ : n < y} be a y-chain i n D . Y = £ Hn Then : i e X >| <y N for a l l i £ I, so that X i s a y covering _ and we may apply 1.16 with K = A = y. Thus Y. |a /D| I as Y < |n<a < |ll<a^ = |(a V/D| : i 1 e I> / D| : i £ I> / D | ( Y = sup {a^ : u < y} > a 1 f o r a l l i e I. So (*) holds. Putting y = w we see that (*) generalises 1.14 ( f ) . I f G.C.H. holds we have the following consequence 2.19 of (*): Theorem (GCH) Let D be an u l t r a f i l t e r on I such that c f ( a ) £ a ( D ) . Then i f |A| = a we have (i) | A / D | I > |A| - 54 - (ii) cf(|A /D|) I >| A | Proof (a) The GCH i m p l i e s t h a t a in = a so t h a t i f we take y = a (*) we have t h a t |a /D| I = | ot /D | a X But i t i s well-known from s e t t h e o r y t h a t under GCH 3 = 8 a i f f a < cf(8) . So t h a t we can conclude ii) cfdA /!)!) 1 > | A | , from which i ) f o l l o w s . However we can prove a fragment of this result // without the use o f GCH by the f o l l o w i n g argument: 2.20 Theorem L e t D be an u l t r a f i l t e r |A /D| I on I . Then | A | e cr(D) i m p l i e s > | A | . Proof If | A | e a ( D ) then D has a u n i f o r m image E on A. E = h ( D ) f o r some h : I -> A. h if : A /E A -> But then A /D I i s 1-1, and we know by 1.14(b) t h a t I A V D I > Suppose | A A / E | > |A|. Consequently | A | . / / L a t e r we s h a l l prove a converse t o t h i s theorem i n the case where | A | i s regular. The p r o o f o f the converse g i v e n employs GCH. - 55 - E. Categorical Formulation Here we indicate b r i e f l y an interpretation of the main ideas of this chapter i n terms of category theory. (1) The category PAIRS i s the category with objects a l l u l t r a f i l t e r pairs <I,D> and morphisms the f i l t e r morphisms f : <I,D> -> <J,E>, i . e . maps f : I -»• J such that f(D) = E. (2) For any r e l a t i o n a l structure /A we have the category MODELS OF /k whose objects are a l l r e l a t i o n a l structures (B of the same type as fk and such that JB = /A,and whose morphisms are the elementary -> IB'2 • embeddings (J) : (3) The category ULTRAPOWERS of /k i s the f u l l subcategory of MODELS OF /A determined by the ultrapowers of Ik. For each /k we have a contravarient functor F , : PAIRS ->- ULTRAPOWERS OF /A Ik A such that i f <I,D> i s an object of PAIRS then F (<I,D>) = /k /!) 1 /A and i f h e Horn (<I,D>, <J,E>) = ti (4) Let then e Hom(/A /E, /A^/D). J / A PAIRS* be the category with the same objects as PAIRS but where the morphisms are given by h/D £ Hom*(<I,D>,<J,E>) i f f h £ Hom(<I,D>,<J,E>) - 56 - i.e. the morphisms are equivalence classes of the morphisms of PAIRS. ft ft F .. : PAIRS Ik The functor •> ULTRAPOWERS OF /A is defined i n the obvious manner. (5) For each set I, we define I-PAIRS ft and I-ULTRAPOWERS * OF A to be the f u l l subcategories of PAIRS and ULTRAFILTERS OF /A formed by looking only at u l t r a filters on the set I. Then these are small categories ft and i t can be shown that F ,, r e s t r i c t s to a functor/A from I-PAIRS* to I-ULTRAPOWERS OF Ik that i s an isomorphism of categories when | l | < |A| and fk i s a f u l l unary structure. Note on Authorship i n Chapter 2 Much of Section A i s well-known, i n p a r t i c u l a r 2.1 which appears i n Booth [5]. Theorem 2.2 i s also i n [5], but here the generalisation to uncountable index sets i s s l i g h t l y less trivial. Theorem 2.5 i s a j o i n t result of A. Adler and the writer. Theorem 2.7 i s a result of the writer and disproves an unpublished conjecture of A. Adler. The remaining results of Section A are largely "housekeeping". As far as the writer can ascertain the notions of "shadow" and "spread" are new, although similar ideas have c e r t a i n l y been touched upon by some authors i n the course of a proof. - 57 - Apart from the results of Chang, Ulam, and Prikry, the results of Section B are the writer's, as are the results 2.18 and 2.20 of Sections C and D. A l l results i n Chapters 3 and 4 where no e x p l i c i t i s given, are due to the writer. ascription CHAPTER 3 REDUCTION OF INDEX SIZE In Chapter 2 we have a l r e a d y noted a c o n n e c t i o n between the s t r u c t u r a l of p r o p e r t i e s of ultrapowers the index s e t I . a f u l l structure A /D I £ A /E J A^/D and the c a r d i n a l i t y F o r example we have t h e theorem that i f A i s A^/D i s generated by a s i n g l e f o r some <J,E> such t h a t element i f f | J | < |A|. In f a c t , i f we examine the p r o o f o f t h i s r e s u l t , we see t h a t t h i s arises i n a p a r t i c u l a r way: We have a morphism h : <I,D> ->• <J,E> such t h a t the induced embedding b/ : A / E -*• A^/D J onto. I n t h i s c h a p t e r we w i l l prove v a r i o u s r e s u l t s the c o n s t r u c t i o n o f isomorphisms o f t h i s k i n d . r o u g h l y , t h a t i f an u l t r a p o w e r then an i s o m o r p h i c ultrapower isomorphism t u r n s out t o be involving We w i l l /A^/D i s " s m a l l " compared w i t h I A^/E e x i s t s w i t h |j|< |l|. the u l t r a f i l t e r D i s u n i f o r m on I one might expect t h a t situation cannot a r i s e - however we w i l l t h i s can happen i f | l | A. When h show, show i n Chapter If this 4 that i s measurable. i s onto If f i s a f u n c t i o n w i t h domain I we l e t be t h e e q u i v a l e n c e r e l a t i o n on I g i v e n by < i , i ' > e II ^ i f f U l ^ i ' i f f f(i) = f ( i ' ) . We i d e n t i f y the e q u i v a l e n c e r e l a t i o n I I ^ w i t h the - 58 - - 59 - p a r t i t i o n of I i f induces. [ f = (f 3.1 Thus we speak of the p a r t i t i o n : j e range(f)}, Lemma (A. Adler) Let h : <I,D> <J,E> be a f i l t e r morphism. The following are equivalent conditions on /A: (a) h ^ i s onto. (b) for each f e A f ~ f D (c) and f there i s an f' e A 1 1 such that i s constant on each c e l l of TI, . h i f Ij = h ^ ( j ) for each j e J and { i ^ : n < a} i s any p a r t i t i o n of I (j £ J ) , where a ^ |A|, then there i s a sequence <n_. : j e J> such that u{l. 3 J : j e j} e D. Proof As range(h^) = {h°g/D : geA^} and a function from I to A i s constant on each c e l l of TL^ i f f i t can be written as h°g f o r some geA'"" i t i s clear that (a) and (b) are equivalent. Now well-order A as {a^ : ri < |A|}. ' { i j : n < a} I f (b) holds and (j e J) i s a system of p a r t i t i o n s as i n (c), l e t f : I f ( i ) = a^ if i e il A be defined by 1 We w i l l speak of the members of partitions' as c e l l s . - 60 - f o r some j e J . Let that f ~ D f f. be a f u n c t i o n c o n s t a n t on each c e l l o f II, and such h F o r each j e J l e t K. = { i : f ( i ) = f ' ( i ) } n I . . P Then i t i s easy t o see t h a t e i t h e r K. = 0 o r K. = I ? f o r some n. 3 3 I f K. = i A o t h e r w i s e s e t n. = 0. Then 2 E < a. 3 3 u{l.. and J so (c) h o l d s . 3 : j . e J} a { i : f ( i ) = f ' ( i ) } e D T h i s argument r e v e r s e s without great difficulty to show t h a t (c) i m p l i e s ( b ) . 3.2 Theorem // (A. A d l e r ) Let /A^/D = B be any u l t r a p o w e r an image E = h(D) o f D on the s e t J = A of A. Then t h e r e i s such t h a t h B : /A /E -*• A / D # J I i s an isomorphism. Proof S e l e c t a r e p r e s e n t a t i v e f ^ from each ~ ^ - c l a s s b e B. D e f i n e a p a r t i t i o n II o f I by s e t t i n g b £ B. h Then IT has a t most : I ->• A A b 1 f ~ f, . D b result cells. i f f f^(i) = f^^'^ ^ o r a ^ I n f a c t II = IL where h i s g i v e n by h(i)(b) = f ( i ) If f £ A illi' ( i e I, then f o r some b e B ( i n f a c t b e B) . f o r b = f/D) we have But f i s c l e a r l y constant on the c e l l s o f II, so t h e b h t f o l l o w s by 3.1. J // - 61 - The r e s u l t 3.2 t e l l s us t h a t , up t o isomorphism, an IB of ultrapower A can always be taken t o have index s i z e than o r e q u a l t o |A |. l i t t l e help 3.3 (with a from the GCH). Theorem (GCH) Let then there and I f [Bj i s r e g u l a r we can do b e t t e r less Ik IT) = B be an u l t r a p o w e r o f /A. 1 i s an image E = h(E) h ^ : /A^/E -*• I f |B| i s r e g u l a r o f D on a s e t J such t h a t | j | ^ |B| Ik^/T) i s an isomorphism. Proof By 3.2 there ,B i s an image E^ = h^(D) o f D on = A such t h a t h ^ i s an isomorphism. (1) I f E^ i s n o t uniform we can f i n d J e E^ such t h a t |J| £ |B| because the GCH and the f a c t t h a t imply t h a t | j | = JA | = |B| . Then i f |B| > |A| : J -> J i s any map t h a t extends the i d e n t i t y on J we have h (2) 2 V " ( E llj- C o n s i d e r , now, the case t h a t E ^ i s u n i f o r m on Then, by the o b s e r v a t i o n J^. f o l l o w i n g 2.11, we have t h a t E ^ i s |B| -d.i., and hence by Chang's Theorem, + that E Let i s |B|-d.±: n < |B|> be a IB|-chain i n E. and l e t <X <f /D F| 1 : T)<|B|> S e l e c t a e A. be a w e l l - o r d e r i n g of A /E^. - 62 - each n < | B | define For r ~ f (i) n g (D = n T Q by if i e X if i e J, - X 1 n n The p a r t i t i o n II i s defined by i l l i ' i f f g^Ci) = g^Ci') for a l l n < | B | . 1 1 The subset X - X ,. of J . i s n n+1 1 broken up by II into at most \&^\ pieces. the So |llj , number of c e l l s of I , i s at most Z{|A | : n < | B | } n as |A| < | B | and by the GCH we have that but |A | < | B | for a l l n < | B | . n So we can write II = II, h 2 Hence |n| < | B | . where h„ : J. 2 1 J is a function with range J such that | j | £ |BJ _ As each g i s constant on each c e l l of TL we have J 2 # J 1 by 3.1 that : IA /E ->- /A /E^ i s an isomorphism 11 where E = h (E.^). 2 In case (1) also i t i s clear that h of 2.4.) 2 i s an isomorphism. In either case i f we take h = h^°h 2 ( c f . proof we have E = h(D) and that h i s an isomorphism. # = h*°h* : /A /E + /A /D J 1 // - 63 B. - Transcendence Degree of an Ultrapower We have three correlated scales for measuring the " s i z e " IB = / A V D : of an ultrapower (a) the c a r d i n a l i t y of B (b) the smallest number | j | such that there i s an u l t r a f i l t e r E on J with /A^/E = B IB. to 3.4 (c) the smallest cardinal number |x| where X generates The results of section A concerned the relationship of (b) (a). Hence we consider the relationship of (c) to (a). Definition IB i s the smallest The degree of a r e l a t i o n a l structure cardinal 8 such that there exists a set {b^ : n, < 8} which generates B. If B = A , where A i s a f u l l structure, then there i s a natural embedding of the element of an extension of A into IB that sends an element a e A B with the same name. A . I f the degree of Thus we can regard the B i s one then B as B i s zero then i t isn't hard to see that the embedding i s onto and hence If the degree of to |B i s isomorphic to A . IB can be generated from A with adjunction of a single element. If a subset X of B generates X' i n IB = <B,R,F,C> and B = A , B, where A being a f u l l structure, then X' consists of a l l elements of the form F^ e range (F) and b^,b2j.--,b n (b^,b2,...,b^) where € X u range(C). To see this notice that a l l such elements c l e a r l y belong to X' and that the set of a l l such elements i s closed under the application of functions from range(F). This i s because range(F .) - 64 - i s closed under composition by the full-ness of A and hence as IB = A. we have that range (F ) = range(F) i s closed under composition. More generally, with no assumptions of a l l elements "Kb^ on IB we can write X' as the set t> ), where b^,...,b e range(C) u X n n and i> i s a composition of members of range (F). It follows from these observations that i f X i s a generating set for B and |x| = 3 then 8 < |B| < max(K,oo,8,Y) where K = |range(F)|, y = |range(C)J. For the set of compositions of members of range(F) has cardinality max(K,0)), has c a r d i n a l i t y then 3.5 K = | A | , and the set of f i n i t e sequences from X u range(C) max(B,Y)Y |A| = If IB = A and A i s a f u l l structure , so that we have Theorem If structure ft IB i s of degree 8 and i I I IB =..- A where i A then 8 ^ |B| ^ max(3, | A | , c o ) . A is a full then 8 = |B|. // So, with large models of T ^ , degree coincides with cardinality. A Consequently i f |B| > I A |, co Generalising the proof of 3.2 we prove: or any structure with |L | = |A | A - 65 - 3.6 Theorem Let lk be any structure and l e t (B = Then there i s an image E = h(D) of D on A A^/D have degree 8 • such that h : lk /E -»- /A /D i s an isomorphism. Proof (Outline) Let (f^/D : T) < 3} generate B. A p a r t i t i o n II of I i s defined by illi' | TI | = |A^| , i f f f^(i) = f ( i ' ) n for a l l n < 6. so II determines an image E = h(D) of D on A^. Each member of B can be expressed as k/D where for a l l i e I k ( i ) = <Mf (i), f 'l (i), '2 f n n <D) A e A . These functions k are n for some n ^ , r)^, . . . » r) < 8 and a l l constant on the c e l l s of II, so the natural embedding h # 1t A I : /A /E -> /k/D i s onto. g For // the remainder of this section we w i l l assume that lk i s a f u l l unary structure, with |A| > OJ. 3.7 Corollary (GCH) An ultrapower £ B = /A^/D either has degree < 1 or degree cf(|A|). Proof ~ 3.6 If A |B has degree 8 < cf(|A j) then |A | = |A| and so by IB = /A /E for some u l t r a f i l t e r E on A. 3*1. But then by 2.8 we have // - 66 - Note that GCH i s not needed i f we replace cf(|A|) by cf*(|A j) where cf*(K) 3.8 Corollary If = min {a : K 0 1 > K} . (GCH) | A | i s regular then the ultrapower IB = /A /D has 1 degree e i t h e r 0, 1 or | B | . Proof (Outline) Let 8 < |A | A B have degree and so by GCH can assume 8 so we = B £ |A|. |A|. 8, where 8 < | B | . Then by I f B < |A| then 8 £ 1 by By 3.6 we can take |I| to be An argument which combines the techniques of 3.6 iB = 3.5 and 3.3 3.7, |A | A =|A| . + shows that k /E for some u l t r a f i l t e r E on A. But, by 2.8, this implies that 8 ^ 1 , contradicting the p o s s i b i l i t y that B = | A | . Thus, under the GCH, degree cf(|A|) s t r i c t l y between 1 and // an ultrapower B of A can have | B | only i f | A | i s singular and S S < | A | . Whether this state of a f f a i r s can occur i s an open question. - 67 - C. Ultrapowers that are Direct Limits Since so many cases are known of ultrapowers |A /D| = | A | , 1 I /A^/D where i t might be conjectured that i f the GCH holds and |A| < |A /E| = y J + then / A / E = / A ^ D for some <I,D> such that | l | J = y. That i s "most" ultrapowers are isomorphic to an ultrapower of "proper" index s i z e . We have come close to such a result i n section A of t h i s chapter, except that an application of 3.3 w i l l y i e l d only a pair <K,F> such that A /E = / / F and | K | = y . J + In this section we w i l l show that i f y i s regular then |A^/E| < y + i f f /A^/E can be expressed as a direct l i m i t of u l t r a - powers of index size y» over a well-ordered set of length y . + A p a r t i t i o n II of the index set I of an ultrapower /A^/D determines an elementary substructure <E of /A*~/D where f/D e C iff f ~ g, g being constant on each c e l l of II. We have used t h i s fact to construct ispmerphisms and embeddings i n Chapter 2 and in sections A and B of this chapter. More generally i f we have a set (P of p a r t i t i o n s of I we can define a subset of A^/D by f/D e Qp i f f f ~p g where g i s constant on the c e l l s of some II e (p . 3.8 Lemma Let A be any structure, then the structure i s a substructure of /A /D i f for every f i n i t e 1 {II^jII^,.. . ,11^} of p a r t i t i o n s and a set from (P implies 1^1' =Q collection there i s a p a r t i t i o n II e (p D such that i f i , i ' e X then iHi' /A^/D]^ for a l l k, - 68 - Proof Assume t h a t /P Q^p = (A/D, R*, F*, C*). suppose t h a t f^/D, each c e l l of 11^ e (y, of the s t a t e d p r o p e r t y . i s c l o s e d under the a p p l i c a t i o n of f u n c t i o n s /A/D Now has A*/D. We I t i s easy to see r n and /^ e constants of t h a t range (C*) t h a t F^ e range (F*) i s an n-ary c Q on function have 1 n g/D where g i s g i v e n by g ( i ) = .F^ ( f ^ d ) the f u n c t i o n of f (i)) n /A c o r r e s p o n d i n g to F . g'(i) i e X i i X = where a^ i s a f i x e d element of A. of n-and g' ~ g so g/D = g'/D t h e r e i s II e P implies in^i' being on each c e l l e Q // s h a l l c a l l a s e t (P of i f f o r every f i n i t e subset {Tl^,J[^, . . . and X e D such t h a t i f i , i ' e X, for a l l k = Less f o r m a l l y we F^ d e f i n e g' e A"*" by Then g' i s constant I f D i s an u l t r a f i l t e r on I we p a r t i t i o n s of I D-directed ( i e I) , L e t II and X have the p r o p e r t i e s of the statement of the lemma and illi' and w i l l show t h a t Q<p > where f ^ i s constant F*(f /D,...,f /D) = of (P We ,Jl^} then l,2,...,n. s h a l l say i n t h i s s i t u a t i o n t h a t II r e f i n e s each 11^ almost everywhere. The substructures of ultrapowers g i v e n by D - d i r e c t e d o f p a r t i t i o n s are p r e c i s e l y the s t r u c t u r e s t h a t K e i s l e r [8] limit ultrapowers. K e i s l e r works w i t h f i l t e r s of e q u i v a l e n c e sets calls relations - 69 - rather than with D-directed sets of p a r t i t i o n s . We f e e l that presentation of l i m i t ultrapowers by means of sets of p a r t i t i o n s has the advantage of throwing attention on the natural embeddings of ultrapowers into l i m i t ultrapowers. This i s made e x p l i c i t by the following lemma which relates to the s i t u a t i o n we s h a l l be interested i n , namely, ultrapowers that are d i r e c t l i m i t s over a well-ordered set. The lemma has a f u n c t o r i a l character which makes possible easy generalisations. 3.9 Lemma Let /A^/D be an ultrapower of the structure we have a sequence <II (a) /A. Suppose : n < y> of p a r t i t i o n s of I such that each function f e A i s ^-equivalent 1 to a function g constant on each c e l l of some TI . (b) i f n' < n then II refines II , almost everywhere. I Then there i s a sequence of ultrapowers <A ^/D^ H < Y> : and families of maps h h nn : I -> I (r| < , : I -* I , n n' (n' < n < Y) Y) ' I T such that Hk /D i s the d i r e c t l i m i t of the sequence <lk ^/D^ : H<Y v i a the embeddings A N h* : /A /D h , : Ik '/D A /D In T n 1 D # nn n , 1 , •* IA /D n n ( ' n < n < Y)- > - 70 - Proof Let the sets {i^} be chosen to index the p a r t i t i o n s , thus l e t II = { a ? : j e I } for a l l n < Y. 1 The functions h : I I are defined by h (i) = j and we take D = h (D) . We now n i e a ] iff 1 define the functions h^ , : I n By hypothesis IT We w i l l take h I , n nn refines IT , on a set X = X ( n , n ' ) belonging n to D. ,(i) = i ' i f nn a n X c a?,' n X 1 n . This gives i ' uniquely from i so long as n X 4 0. But : a ? n X = 0} I D {i e I 1 as h So that h 1 r i ({iel r i : cr?nX=0}) c I - X I , has been defined for almost a l l i e I D. (mod D ). n nn' the remaining values of h , arbitrarily. nn It follows that the diagram Define - 71 - n' < n. < Y commutes on a set i n D. i h , = h n' h 0 nn' From this i t i s easy to see that and that h „ = h , „ ° h nn n ,• nn n n F i n a l l y l e t iB be any structure for which there exist embeddings : A k YD n n < y •* n for a l l n such that k^, = h^^, o < D < y. 1 Then we define an embedding k : A/D + as follows: if f/D e A/D then there i s n < y so that f i s ~ ~equivalent D to a function constant on the classes of II . Thus f/D e range (h/) Jl and there exists a unique f /D e Ik /D such that f/D = h (f /D ). 11 n n n n n n We. set k(f/D) = k (f /D ). r r iy n This d e f i n i t i o n of k(f/D) i s independent of which chosen as i f f/D = h^,(f^,/D^,) where n 1 that f / D n = h* , ( f ,/D n nn n ,) and so n is < r\ then i t i s easy to see - 72 k ,(f ,/D ,) = h* , ° k (f ,/D n n n nn ,) n n n = k (h* ,(f ,/D n n nn ,)) n = k (f /D ) n n i = 1,2. n 2 l exist f V D n , f /D such that f /D ^ f /D and f /D = h ( f / D ) Also k i s 1-1 as i f f / D 4 f /D then for some n > Y there 2 n i n n 2 n n 1 n n # 1 n n n Then k ( f V D ) = k (f*/D ) 4 k (f /D ) = k ( f / D ) . 2 n n n n 2 n n A s i m i l a r argument shows that k i s an isomorphism. If condition (a) of 3.9 obtained as a substructure of i s dropped the d i r e c t l i m i t i s /A^/D. In the r e s u l t which now i t i s important that the l i m i t i s taken over a well-ordered because i t i s immediate from Adler [2] K e i s l e r [8] that any model of T that /A^/D follows chain and can be deduced from , where fk i s f u l l , i s a d i r e c t l i m i t of ultrapowers with index size < |A|. s i t u a t i o n of 3.9 // We s h a l l say.in the i s a chain-limit of the sequence of I ultrapowers < /A ^/D^ n > Y - : > W e speak of chain-limits of sets as well as chain-limits of structures. We 3.10 Theorem can now state (GCH) An ultrapower of index size < |B| (1) |B| IB = /A^/D i s a chain-limit of ultrapowers i f either = Y> + where Y i s regular - 73 - or (2) |B| i s a l i m i t cardinal > (1) |B| = y , Y regular. |A|. Proof + By 3.3 we can take | l | and define II for each n < y + = y . Let B be {f^/D : n < Y } + + by i II i ' i f f f (i) = f ( i ) . 1 * We + w i l l construct a sequence <TI^ : n < y > of p a r t i t i o n s of I such + that i f £ < y * then TI^ refines every p a r t i t i o n i n the set {II : X] <O u {n* : n < E] on some member of D, and such that for a l l n < y , |n | < y. • r * Suppose the p a r t i t i o n s {H : n < £"} are already appro- p r i a t e l y defined, we w i l l show how to define IIg.. As E, < y we have \E.\ < y and we can re-order the set ft ftft {11^ : n < E) u {11^ : n < O as {TI^ : n < K} where K = \E\ < y. + Without loss of generality D i s uniform on I and hence D i s y - d . i . + So by Chang's Theorem D i s y - d . i . Let <X^ : n < y> be a y-chain i n D. Define an equivalence r e l a t i o n s on I as follows: (a) i f i and i ' belong to X - X ,, for some ri > y n n+i 6 then i E i' i f f in**i' for a l l n ' n' such that n ' < n, n ' < <• (b) i f i and i ' belong to (c) i n a l l other cases i s6 i ' . 1 - X Now I = (1 Q) U u{X -X _x decomposition of I and each X^ - X ^ : n < g then i ss i ' . y ) i s a disjoint ^ i s broken up by ss into < y' " ' 1 1 - 74 - cells. As y i s |ri] < Y r e g u l a r and Hence s breaks up I i n t o < y*Y w have by'GCH t h a t y' " ' = Y« e 1 Y c e l l s and we = 1 can take II^ t o be the p a r t i t i o n of I determined by ~. defined s a t i s f i e s conditions (a) and I a d i r e c t l i m i t o f a sequence (2) |B| a limit </A : n < Y > thus <TI^ I t i s c l e a r t h a t the sequence (b) o f 3.9. : r\ < y /D Hence by 3.9 > where 11 | = (B i s |II | < y. |A|. cardinal > D e f i n e the p a r t i t i o n s <II^ : n < | B | > as i n p a r t ( 1 ) . L e t II ^ be the common r e f i n e m e n t of {IT.^ : n < £} f o r each E, < |B| . For any E, < |B| |n*| * So as |A|< |B| |B| |ll^{ < we have by the GCH (a) and 2 , 3.11 Theorem (GCH) Let B | = Y, |A| + < Y- Y |A^| S O that /D < Y + (B i s the c h a i n - l i m i t o f and + : x\ < y > then we have t h a t so t h a t we have proved /A^/H and l e t y be a r e g u l a r c a r d i n a l such t h a t f o r |B| < Y + \ i s a c h a i n - l i m i t of a sequence where 11 | < Y |B|> // Then i t i s n e c e s s a r y and s u f f i c i e n t + < |B|, (b) of 3.9. o f u l t r a p o w e r s < Ik |B| < 2 Y = that I t i s easy to see t h a t <IIg : E, < N o t i c e t h a t i f |A| I a sequence have |A^| f o r a l l E, < |B|. then s a t i s f i e s we of ultrapowers < /A t h a t tB + /D : r) < y > f o r a l l r\ < y . II + N o t i c e t h a t i n a l l o f the above we have not excluded the possibility t h a t the d i r e c t l i m i t s a r e . t r i v i a l i n the sense , that / - 75 - Ik /D = /A r] /D T|Q f o r some r i < Y U n and a l l n > r u . U If we regard the least size of index ultrapower |l| such that an B of a structure Ik i s isomorphic to Ik. /D for some u l t r a f i l t e r D on I as a measure of the "complexity" of B then 3.10 represents certain ultrapowers as chain-limits of "simpler" ultrapowers. D. A Hierarchy of Substructures In order to generalise the r e s u l t s of the l a s t section we define a hierarchy of substructures of /A^/D. In fact we w i l l work with a r b i t r a r y subsets of A^/D. 3.12 Definition Let Ik be any structure and l e t X be a subset of A^/D. We say that X i s of l e v e l a i f a i s the least cardinal such that there i s a p a r t i t i o n IT of I into a c e l l s such that each element f/D of X has a representative f' ~ f that i s constant on each c e l l of It. We write " l e v e l (X) = a". The l e v e l of a substructure of /A /D i s taken to be the l e v e l of i t s underlying set. I // Note that (i) (ii) (iii) l e v e l ({f/D}) = spread(f/D). i f X i s f i n i t e , l e v e l (X) < |A|. i f lk(X) i s the substructure of /A^/D generated by X then the l e v e l of A(X) i s the same as the l e v e l of X. - 76 - (iv) the l e v e l of A /D i s the least cardinal a such that 1 D has an image E = h(D) on a h^ : for which /A /E -*• /A"*"/D i s an isomorphism. a of this section we assume that with | l | In the rest /A^/D i s presented already reduced i n t h i s way, i . e . that the l e v e l of A /D i s | l | . I 3.13 Definition For a l l cardinals 8 ^ |I| we define = {X c A /D : l e v e l (X) < 8} // I 3.14 Theorem Let B = A /D. I (a) For a l l i n f i n i t e 3 ^ | l | , (b) (GCH) i f D i s y - d . i . , where y i s regular, then Ly + L^ i s an i d e a l i n S(B) i s y-complete. Proof (a) I t i s clear that X e L^ and Y c X implies Y e L^. Suppose that X^, X^ e L^ and that II ^ and TT^ are the corresponding p a r t i t i o n s of I. Then |lT^|, l l l ^ l of It and n < 8 and i f n^'H^ i s the common refinement 2 i t i s clear that |n «II | = 2 IlLj'lirJ < 8- Each element f/D of X^ (k = 1,2) has a representative constant on each c e l l of II, and hence on each c e l l of k n «n . 2 - 77 - So each member of X^ u has a representative constant on each c e l l of II^'IL^. and hence L Thus X^ u e i s an i d e a l . / p (b) Let (i) : n < Y} be a set of y members of L ,. {X Y+ n (ii) (iii) <Y^ : r) < y> be a y-chain i n D. {TI^ : n < y} be a set of y p a r t i t i o n s of I into < y c e l l s , corresponding to the X^'sWe define a p a r t i t i o n II of I as i n the proof of 3.10, i.e. i f i ,i 'e Y - Y ,, then n+1 i f f i n , i ' for a i i n' < n . n ini' n We have that |n| < s{Y LNL : n < Y> = Y (employing the GCH). The p a r t i t i o n II refines each II on Y ,, £ D. so that * n n+i each member of X has a representative constant on n every c e l l of II. Thus each member of u{X^ : n < has a representative constant on the c e l l s of II, so that u{X^ : r\ < y} e L^ + . // A theorem of Tarski [16] states that a ^-complete proper i d e a l L on a non-measurable set of c a r d i n a l i t y 8 i s either p r i n c i p a l or admits a pairwise d i s j o i n t family {X , : n < 8) of non-members of L. If 111 = y + w e have by assumption that L ^ i s a proper + is Y~ ideal. I f y i s regular we have that L above. Also from 3.3 and GCH we i n f e r that c o m pl e t e > from the - 78 - |A/D| If |B| = |l|, = |B| then L cardinality y. > level i s a Y complete +- So by the r e s u l t + (B) = |l| . p r o p e r i d e a l on a s e t o f of T a r s k i memtioned above L admits a p a r i w i s e d i s j o i n t f a m i l y of non-members {X^ In t h i s s i t u a t i o n any embedding o f the form h* : A / E J where | j | ^ y, f a i l s to be onto i n a v e r y s t r o n g way: contradict level ( X ) = v n }. -»• A ^ D , range o f h^ can i n c l u d e none o f the s e t s X^, would : n < y + ' i.e. X n < y, + i L ,. n Y+ i n fact the f o r to do so CHAPTER 4 INDUCED ISOMORPHISMS AND THE SHADOW In Chapter 3 we presented theorems where we constructed images <J,E> of an u l t r a f i l t e r pair <I,D> such that the embedding h was an isomorphism # : /A /E + J / A /A /D I and where | j | depended on [A^/D|. We prove now results connecting the nature of the shadow a(D) of D with the problem of when embeddings l i k e h ^ are onto. These results w i l l allow us to pass from results on a(D) to results on |A^/D| and vice-versa. In p a r t i c u l a r we s h a l l obtain a p a r t i a l converse to 2.20 and some results concerning ultrapowers |A| < |A^/D| < | l | . /A^/D with We w i l l also investigate a related notion of quasicompleteness for u l t r a f i l t e r s . A. Three Algebraic Theorems Throughout f i l t e r morphism. t h i s section h : <I,D> -> <J,E> i s a fixed Recall that h^ : A^/E -»• A^/D i s the i n j e c t i o n defined by h^Cg/E) = h°g/D. As we have said above we are interested in when these maps h^ are onto. Some easy f i r s t results are given in the following lemma. - 79 - - 80 - 4.1 Lemma (i) (ii) (iii) (iv) i s onto i f f hj^j i s . If |A| > |I| then h* i s onto i f f E ss D. If h^ i s onto and 8 < a then hf i s onto. If D 56 E there i s a cardinal OL > OJ such that hf 8 n i s onto i f f 8 < ot^. Proof Parts ( i ) and ( i i i ) are simple consequences of 3.1. Part (iv) i s a consequence the proof of part of parts ( i i ) and ( i i i ) . We outline (ii). Suppose E ss D, then we that h(D) ss D. Employing 2.1 we have by an argument similar to that of the proof of 2.2(b) that there i s a set X e D such that h|^ i s 1-1 and h(X) e E. Then by 2.3(b) we see that h^ i s onto. Conversely i f h^ i s onto, choose (for each j ) p a r t i t i o n s {i ? : n < IAI} of I. = h ^"(1) such that each c e l l I ? i s a singleton. 7 1 1 1 1 (We can do this as | I_. | < |I| ^ |A| .) Now we employ 3.1 to conclude the existence of a sequence <rij : j e J> such that u { l j : j e j}.e D J . The map which establishes D ss E i s the map which sends j to the member of I. . 4.2 JJ Theorem If 8 € a(D) i s such that |J| < 8 ^ U l then there i s a - 81 - u n i f o r m u l t r a f i l t e r F on 3 and maps f : I ->- 8 , t h a t f ( D ) = F, g : 8 J such g ( F ) = E and h f f a c t o r s whence h ^ i s onto i f f g ^ and f ^ a r e onto. Proof As 8 e 0(D) t h e r e i s a p a r t i t i o n o f I i n t o 8 c e l l s t h a t determines a u n i f o r m image F' o f D on 8 . There i s a l s o a p a r t i t i o n o f I i n t o | J | c e l l s t h a t determine E as an image o f D ( v i z : the p a r t i t i o n IL^ determined by h ) . Taking the common refinement o f these two p a r t i t i o n s we o b t a i n a p a r t i t i o n o f I into 8 c e l l s t h a t determines an u l t r a f i l t e r F on 6 such E < F < D, and F' < F so t h a t F i s u n i f o r m . obvious maps f : I and h = f°g. 4.3 8, that Then t h e r e a r e g : 8 + J such t h a t f(D) = F, G(F) = E The r e s t o f t h e theorem f o l l o w s . // Theorem Suppose h ^ i s onto, and 8 < Y K a implies that Y ^ o(D). Then h * i s onto f o r a l l y < a. Proof L e t IL^ = {I : j e j } , where I p a r t i t i o n o f I determined by h. = h ^"(j),-be the Suppose f/D e u^/D where y < a . - 82 Then by 2.14 So t h e r e and i s f* ~ h y p o t h e s i s we D there But is f ~ then f 4.4 4.1 f and we ft L e t range (F ) = have t h a t h ^ i s onto. so by.3.1 again we 8. So by on each I. an u l t r a f i l t e r ?2 implies y 8 and I a(D). a map k Then i f 2 (1 e J ) . have t h a t f/D e range ( h ^ ) • : I on I such t h a t 8 < Y < a 8 < a there Z 8 such t h a t E = k(D) i s an u l t r a f i l t e r E and k^ on i s onto f o r a l l a. Proof First (1) and we claim there i f G i s any i s an u l t r a f i l t e r E on 8 such t h a t E < D u l t r a f i l t e r on For c o n s i d e r There are at most 2 of I i n t o 8 p i e c e s of these 2 2^ 2$ of them and we can determines an image E n nlK at most 8 of D on 2^ E. on 8 t h a t are images of select < 2 c o r r e s p o n d i n g to t h e s e . p a r t i t i o n s has on 8 i s an image of 8 such t h a t G < D then G < a l l ultrafilters The 9 Z partitions cells, and E'. However t h ( E ' ) < Bj f o r o t h e r w i s e t h e r e would be Y i 0(D). satisfies Notice that on 8- Clearly E (1) i m p l i e s t h a t E i s unique up ss (and hence by e a r l i e r remarks, up a , contradicting So E' ss E where E i s an u l t r a f i l t e r (1). hence such t h a t each image of D u n i f o r m image of D on y where 8 < Y - 2 D. 3 common refinement 23 = 2 2 to isomorphism) . V. 3.1 Theorem L e t D be Y < (f/D) < |range ( f * ) | < 8- f * such t h a t f ' i s constant ~^ 1 have t h a t spread f such t h a t Then by h y p o t h e s i s and - to - 83 - Select a map k : I -»• 8 such that E = k(D) . We claim (2) k^ i s onto. Let k determine a p a r t i t i o n II = {l_. : j e 8} of I. By 3 . 1 our claim ( 2 ) i s v e r i f i e d i f we can show that f o r any refinement n* = { I : j e 8, n < 8> of n, where I n = u { i : n < 8>, there n exists a sequence <n_. : j e 8> e 8^ such that : j e 8) e D. u {i J * Now II* determines an image E of I on 8 8 such that X TT.^(E ) = E where TT^ : 8 8 ^ 3 i s the projection on the f i r s t X But I8 8I = 8 so E i s isomorphic to an u l t r a f i l t e r on 8 and hence X ( 1 ) of E there i s a map by the u n i v e r s a l i t y property such that = E . But then we have (TT^°I{J) ( E ) = E * i there i s X e E such that ^ ° ^ l x -*i d e n t i t y on X. ^(E) st 1 T = TT^X), Y Y e E factor. and X = (Y) = n e {>(j) : j e Y}. j ) = <j ,ri > f o r some 8.. e 8 for j e Y we have As :8 88 so by 2.1 X Then i f Of^) (j) = (j e Y) . Hence X £ ^ J» lj < r > : j e 3} where the n. are chosen a r b i t r a r i l y i f j e 8 - Y. t j» lj < r > : j e 8) e E So and so u {I J : j e 8> e D * by d e f i n i t i o n of E . Thus ( 2 ) i s v e r i f i e d . (3) k* i s onto f o r a l l y < a. This follows from ( 2 ) and 4 . 3 . // j - 84 - B. Quaslcomplete Ultrafilters We add some remarks on when the hypotheses of 4.4 are satisfied. YQ i I f there i s a regular cardinal YQ < | l | such that o(D) then i t follows from Chang's Theorem that YQ> YQ > I|[ YQ 5 etc. i o(D). Then the hypotheses of 4.4 w i l l be s a t i s f i e d i f we take 8 = YQ and a the least cardinal > YQ such that a e a(D), provided we accept the l i m i t o2B then 2 Z cardinal hypothesis. For ( ) n+ = 8 for some n (3 ^ n < OJ) • We have already exhibited u l t r a f i l t e r s D on I such that y e cr(D) f o r a l l Y - I ! • 1 question has been posed The (in Chang [6] f o r the case that | l | = ^^j) as to whether there exist uniform u l t r a f i l t e r s D on I such that there i s a regular y .< | l | such that y i o~(D). We w i l l construct an example of such an u l t r a f i l t e r i n the case where | l | = y, the least measurable cardinal: the s i t u a t i o n i n general and i n p a r t i c u l a r f o r I = OJ ,, remains unresolved. OJ+1 1 1 We w i l l c a l l a uniform u l t r a f i l t e r D on a set I (K,X)-quasicomplete i f K + < X and y I o(D) f o r a l l y such that K < y < X, and simply K-quasicomplete i f D i s (K, 111 )-quasicomplete.. We w i l l motivate these names a l i t t l e l a t e r , but f o r the meantime note that these quasicomplete u l t r a f i l t e r s lack certain kinds of incompleteness. From our e a r l i e r remarks we see that i f D i s a uniform u l t r a f i l t e r on I and y i s a regular cardinal i 0"(D) then D i s (y,X)-quasicomplete, where X i s the least cardinal > y such that X e o(D). Independently of t h i s work S i l v e r et a l . [14] have studied OJ-quasicomplete u l t r a f i l t e r s , which they c a l l indecomposible - 85 - ultrafilters. S i l v e r proves that i f D i s an tu-incomplete composible u l t r a f i l t e r on a strong l i m i t inde- cardinal X > to then there i s a p a r t i t i o n {I : n < to} of X such that I I D f o r a l l n n n < to and i f each I i s decomposed: I n = u {i™ : m < to} n then there i s a sequence <m n m u {I n (n < to) : n < to> such that : n < to} e D . This r e s u l t i s a s p e c i a l case of 4.4. Another r e s u l t mentioned by S i l v e r i n [14] i s ascribed to Chang and P r i k r y . I t states that i f GCH holds, and D i s an indecomposible u l t r a f i l t e r on X then e i t h e r X i s inaccessible or cf(X) = to. We do not have available the proof of this r e s u l t but i n section E we w i l l prove a s i m i l a r theorem i n the more general s e t t i n g of K-quasicomplete u l t r a f i l t e r s . S i l v e r goes on i n [14] to show that i f X i s a strongly inaccessible cardinal which supports an indecomposible then A. has several "large c a r d i n a l " properties. ultrafilter In the other d i r e c t i o n we w i l l show that i f u i s the least measurable there exist K-quasicomplete u l t r a f i l t e r s to ^ K < u. 4.5 cardinal on u f o r any K such that F i r s t we note the following r e s u l t : Lemma If Ik i s a f u l l unary structure and /A^/D = A^/E then f o r a l l cardinals 3 < | A | we have 8 e a(D) i f f 6 e a(E) . - 86 - Proof Given the hypotheses, i t i s easy to show that for any structure IK with |K| < |A| we have ^/D = K /E J , (at least with respect to the unary r e l a t i o n s ) . Let K be a set of c a r d i n a l i t y 8 and suppose F = f(D) i s a uniform image of D on K. Take K to be the structure which l i s t s p r e c i s e l y the unary r e l a t i o n s of K, and l e t <J> : (K^/D -* IK^/E be an isomorphism. Then i f <j>(f/D) = g/E we claim F = g(E). of K and T A For i f X i s any subset i s the corresponding predicate of L K^D F T (f/D) x iff K /E J |K then 1= T (g/E) x i.e. {i : f ( i ) e X} e D iff {j : g ( j ) e X} e E i.e. f (X) £ D iff g (X) e E i.e. X £ f(D) iff X £ g(E) So F = f(D) = g(E). _ 1 _1 Thus 8 £ cr(D) implies 8 e CJ(E), and the converse holds by symmetry. // As a c o r o l l a r y we have a converse to 4.4. 4.6 Corollary I f E = h(D) i s an image of D on 8 and h^ i s onto for a l l y such that y < a then y i a(D) for a l l y such that 6 < Y < a. Proof As the embeddings h^, induce isomorphisms of f u l l on ywe structures have from 4.5 that i f y < ct then y e a(D) i f f y £ a(E). - 87 - But y > 3 implies Y I then y i cr(E). Hence i f y s a t i s f i e s 3 < y < a o"(D) . // a K - q u a s i c o m p l e t e u l t r a f i l t e r on u we To c o n s t r u c t make use o f the c o n s t r u c t i o n o f A d l e r non-regular u l t r a f i l t e r on [1] f o r an will co-incomplete y. L e t E be any u n i f o r m u l t r a f i l t e r on K and l e t F be a u-complete I f TT : I •> K i s the p r o j e c t i o n we have IT(D) Suppose a < y. We claim A is a full D = FxE. = E. s t r u c t u r e on a s e t o f c a r d i n a l i t y that ir is Take I = U X K , uniform u l t r a f i l t e r on y. : # /A /E + ^/D K onto. Let can show t h a t I : T| < y} = {<n,j> TT^ i s onto i f we f o r each j e K . By 3.1 can prove t h a t whenever we we have decompositions I = {l n : TI < a} of each I . i n t o a p a r t s , then t h e r e i s a sequence <n. J J such : j e K> that u.{lj Assume t h a t we and l e t X ] = {£ J 1 : j e K} e D. are g i v e n such a sequence of : <£,i> € I*?} then f o r each j e K we J y = u{xn : n < a} e F . decompositions have - 88 - As F i s a-complete i f follows that for each j e K there i s an r). < a J such that X. J e F. J But n. u{lj : j e K} e D = F x E J n. i f f {j : Xj e F} e E . Hence i f the sequence <n. : j e K > i s chosen so that X. J e F for a l l 1 e K we have that n u {I J 1 : j € K} e D. So T T ^ i s onto, and hence an isomorphism. As t h i s argument holds for a l l a < y we have by 4.6 that a i a(D) for a l l a such that K < a < y, so that D i s K-quasicomplete. C. Shadow and C a r d i n a l i t y II We w i l l prove here a converse to 2.20 under the assumption of the GCH and also some general r e s u l t s about | / D | where D i s a uniform u l t r a f i l t e r on I. 4.7 Theorem (LCH) Let D be an u l t r a f i l t e r on I and l e t a < | l | that a = E{a : 8 < a}. a e a(D) be such Then iff |a /D| > a . T Proof Note that any such a must be regular. tion of the r e s u l t follows from 2.20. The forward d i r e c - - 89 - Assume, now, that a e Cf(D). Theorem we have that a , a Then by 2.10 and Chang's i 0"(D) , and hence by , a' LCH that 9 a 2 a < y - 2 2 (1) Y i O(D). implies , , 2<X If 2 < |I| then by 4.4 there i s an image E = h(D) of D on a such that h # a : a / E + a /!) 1 is a bisection. But 8 = th(E) < a as a I a(D) implies a i a(E), thus | ot/I>| = |a /E| = |a /E'| X a e for some E' « E on 8• So |ot /D| < |a | = a X B by hypothesis and 1.14(a). (2) I f 1^ ~ t h e n W e m u s t h a v e t h ( ) D = 3' < a and by a s i m i l a r argument |cx/D | < |ot * | = a . X 4.8 3 Corollary (GCH) Let D be an u l t r a f i l t e r on I, and l e t a be a regular cardinal ^ 111. Then a £ a(D) i f f |ot /D 1 > a . X // - 90 - Proof If the GCH holds then for any regular cardinal a have a = £{a R : 3 < a}. we Certainly the LCH w i l l then hold so we may apply 4.7. // If a i s singular the s i t u a t i o n i s more complex and we summarize i t i n the following diagram of implications The implication (1) cannot be reversed, for we may have cf(a) ^ | l | < a. Less t r i v i a l l y look at an to-quasicomplete u l t r a f i l t e r D on I as constructed i n section B. Then D i s tu-d.i. but, e.g., ui i 0(D). (|l| = u). The same examples show that (3) cannot be reversed. Implication (2) presents some problems: Can Is GCH needed? (2) be reversed? These remain open questions. Of related interest to these problems and results i s the following result which makes no use of the GCH. - 91 - 4.9 Theorem If | ot /D | > a X then either (1) D i s c f ( a ) - d . i . or (2) there i s a 3 < a such that |g /D| > a. I Proof Suppose that D i s not c f ( a ) - d . i . where \ : a •+ a^/D i s confinal i n a^/D and a^/D order on i s regarded as an ordered set. Then by 2.17 X(a) i s the canonical embedding We take <' to be the a}/D. Define to be {f/D : f/D <' for each n < a. Then by our remarks following 2.17 we have that | c l = In^ol n for a l l r\ < a. But a /D I and = u{c^ : n < a} so |a/D| = sup{|8 /D| : 6 < a} (t) I Hence i f ICX^/DI > a there i s a IB^DI > a. 8 < a such that // This theorem rather n i c e l y f i l l s the gap i n our understanding l e f t by 4.8: i t t e l l s us that |a /D| i s greater than a i f f there i s "good cause" for i t to be. I - 92 - A bonus from the p r o o f o f the above r e s u l t i s the principle (t) which h o l d s whenever D i s not c f ( a ) - d . i . I t i s an open q u e s t i o n i n the t h e o r y o f u l t r a p o w e r s whether t h e r e e x i s t s a n o n - t r i v i a l ultrapower o f s i n g u l a r c a r d i n a l i t y , i . e . an ultrapower a ^ / D where and g r e a t e r than a. Using | a"*"/D | i s s i n g u l a r (t) we can e n v i s a g e the f o l l o w i n g " s c e n a r i o " : t h a t t h e r e e x i s t s an u l t r a f i l t e r D t h a t i s not c f ( c t ) - d . i . and such t h a t f o r some y , a < I B V D < |a I I | - /D y < $ < a (t) Then by 10£. /ID X implies | would have to be singular. By combining 4.10 Theorem If is a 4.9 w i t h 1.15(h) we o b t a i n 3 <a | ( 2 A ) I / D | such t h a t 2 > then e i t h e r a |8 /D| I D i s c f ( a ) - d . i . or there a. > Proof By 1.15(h) | ( 2 A ) I / D | > 2 implies a |ot /D| X > a. The r e s u l t then f o l l o w s by 4.9. // The r e s u l t 4.10 bears an i n t e r e s t i n g r e l a t i o n s h i p to Chang's Theorem: b o t h r e s u l t s can be proved w i t h o u t the GCH, but if the GCH i s assumed then 4.10 i m p l i e s Chang's Theorem. Por then we have by 4.8, | ( 2 A ) I / D | > 2 a i f f A l s o i f 8 < a i s such t h a t | ( a + ) I / D | > a + i f f D is a -d.i. + | 3 / D | > a then we have f o r a l l r e g u l a r I - 93 - y such that 8 < y < a IYVDI so that l y / ! 1 > I B 1 > Y and by 0 ^ ! > 4.8 a > y D i s y-d.i. Chang's Theorem r e a d i l y follows. // The above results relate only to the question when |A^/D| > |A| for ultrapowers A V D . precise information between |A| and of I f we wish for more on where jA*/D| f a l l s i n the range of cardinals |A^| we find that we have to study much more d i f f i c u l t questions about the structure of the u l t r a f i l t e r The following theorem shows us that even the further question l e v e l of 4.11 "When i s |A"^/D| > |A| + ?" <A ^/D^ Theorem leads us to a new (GCH) |A^/D| < |A| + : "simplest" difficulty. Suppose |A| i s regular and that Then I D. ri<|A| > [l| > |A|. i f f A"*"/D i s a chain-limit of a sequence of ultrapowers with index size 11 | ^ |A| . Proof Apply 3.11 with y = |A|. In terms of the u l t r a f i l t e r D we may theorem i n the following way: lA'/Dl < |A| + // express this - 94 - iff there exist system of maps {h^ : n {h , n n > |A| } A + : n <n C 1 < |A| } A + C A such that the diagrams (n' < n h + , commute on a set i n D, and i f the < |A| ) I+ = h (D) for a l l r\ < |A| then diagrams commute on a set i n 1 1 + exists an n > |A| and further i f g i s any member of A A and a t e A such that the diagram commutes on a set i n D. there - 95 - The question of whether such u l t r a f i l t e r s exist f o r various | A | and | l | seems to be quite d i f f i c u l t . The result of Prikry [13] shows that i t i s consistent to assume that a l l uniform u l t r a f i l t e r s on O J ^ are regular. no ultrapower W ^ / D , of a sequence M <OJ /D U) This assumption would imply that where D i s uniform on OJ^ , i s a chain-limit n X] < : OJ, > . 1 We s h a l l close this section by proving a result which shows that i f D i s a uniform u l t r a f i l t e r on I where | l | then either |A*/D| > |A| i s "reasonably large" or we have some interesting pathological s i t u a t i o n s . 4.12 Theorem Let be any ultrapower of A, where D i s B = A^/D Q uniform on I. Let 2 = | A |. (l) 8 * |i| or (2) 6"^ or (3) D has images Then either cr(D) exists h : 8 on 8, D + + 8 the i n j e c t i o n h 2 uniform on 8 + such that h ( D ) = D + 8 // : A 8/ D ^ A and there and / D i s onto. 2 Proof By 3.2 there i s a map k : I k # : A /E * 3 8 such that A /D X i s onto, where E = k ( D ) . Assume that 8 < | l | p a r t i t i o n II' of I into 8 + and 8 + e a(D). Then there i s a pieces that determine a uniform image - 96 - of D or 6 . Let II be the common refinement of II' |TT | = 3 B = B + , and so + JJ = II f o r a map construction of g there i s a map h : 8 k = g°h, g : I -> and II, . k Then By the 8+. 8 we have + h(g(D)) = E. Set g(D) = F , then because JJ r e f i n e s J J ' and J J ' determines g a uniform image on 8 + we have that F i s uniform on 8 + We have embeddings A and as 3 / E A 8 •> /F A /D X i s onto so are h^ and g^. The r e s u l t follows i f we set // I f we assume the GCH and | B | i s regular we can improve t h i s r e s u l t by using 3.3 instead of 3.2. We can then prove the above r e s u l t with 8 = | B | instead of | A | . B Looking at 4.12 again we see that Conclusion us a c a r d i n a l i t y r e s u l t , Conclusion of the u l t r a f i l t e r , and Conclusion (1) gives (2) some completeness properties (3) isomorphism of ultrapowers of d i f f e r e n t index s i z e s . We venture a conjecture at t h i s p o i n t . 4.13 Conjecture Let A be a f u l l structure on a set /A and l e t <I^,D^>. k = 1,2 be such that - 97 - (1) \\\ < |I I 2 (2) (3) uniform on 1^ 1 S a < |l | implies a e ( ° ) a k Then f o r k I /A /D I A. V D £ 1 1 k = i> 2 . 0 // We may weaken this a l i t t l e by replacing (1) with (1'): |l | 1 < cf|l |). Note that by 2.6 we have that 4.13 2 i s a theorem i f |A| > | l J and also i f |I | < |A| < |I I we I I 1 ~ 2 9 can show that 4.13 holds. For i f /A /D^ ~ Ik /D where 11 | < |A| < |I I then by 4.5 we can conclude |A| i 0(0^). 2 2 This conjecture, i f v e r i f i e d , would s e t t l e some interesting c a r d i n a l i t y questions. For example consider the ultrapower OJ ^ / D P where p < q < OJ and D i s uniform on OJ . q By Chang's Theorem we know that a(D) 3 {a : OJ < a < OJ } q so that by 2.20 we have OJ |0J 1 /D| q p 1 =5 OJ _ p+1 . But i f we assume GCH and 4.13 we can apply 4.12 with f^= B' / to conclude to I to /D| > to q 1 p ' q because 4.12(2) contradicts Chang's Theorem and 4.12(3) i s ruled out - 98 - by 4.13. Conjecture 4.13 would be even more useful i n conjunction with further results on the shadow o"(D) of an u l t r a f i l t e r D . We prove more about 0"(D) i n the following section, but much s t i l l remains unknown i n this area. D. Further Results on the Shadow We prove here two additional results about the form of sets of cardinals a ( D ) , adding to the information that Chang's Theorem gives us. For s i m p l i c i t y of proof we s h a l l employ the GCH i n the proof of the next r e s u l t . However, i t i s s u f f i c i e n t to assume the LCH, or i n part (2), that a i s a strong limit cardinal. 4.14 Theorem (GCH) Let D be an u l t r a f i l t e r on I and l e t a be a l i m i t cardinal < |I| such that a = sup(8 < a : 8 e 0"(D)}, ( i - e . , a i s a l i m i t point of a(D)) then (1) either a e a(D) or a (2) i f c f ( a ) e a(D) then a e a ( D ) . + € cr(D) Proof Let {a^ : n < 8) £ a(D) be such that a = supfo^ : n < 6}. For each n < 8 l e t n be a p a r t i t i o n of I into a n determines a uniform image D n (1) of D on a pieces that n n The common refinement A{H^ : n < 8) of a l l these p a r t i t i o n s determines an image D of D on a set - 99 - of c a r d i n a l II<a : ri < 3 > . But : n < 8> ^ a n<a Hence, by expansion B + = a as c f ( a ) < f < a . i f n e c e s s a r y , we can take D + to be on a . As i t i s c l e a r t h a t D n < D f o r a l l n < 8 we must have for a l l n < 8 • (D ) > a th ft So th(D ) > a , * hence th(D ) = a o r a + . / r e s u l t i s t r i v i a l u n l e s s c f ( a ) < a and i t i s e a s i l y The seen t h a t we can take 8 = c f ( a ) . image o f D on 8 determined, : n < 8} {I of I. L e t E be a u n i f o r m s a y , by a p a r t i t i o n We c o n s t r u c t a new p a r t i t i o n II o f I as f o l l o w s : illi' and i f f t h e r e e x i s t s n < 8 such t h a t i , i ' e I for a l l £ < n . illgi' I t i s easy to see t h a t II r e f i n e s II£• on the s e t u{l : E < V < 8> = Y g . But as E i s u n i f o r m the s e t s Y ^ ( £ < 8) to D, so II r e f i n e s each II^ almost a l l belong everywhere. Now | IT | < Z<II<a as each I Jl<a t r : E, < n> i s broken : '£ < n> pieces. : n < 8> up by II i n t o a t most - 100 - So | IT | < E<a ' ' ' n < B > n < Z<a n : n < 8> = a , + n and we can take II to determine an image D of D on a. By construction of II, < D for a l l n < 6- Hence th(D) = a and a e a(D). // Our next theorem on a(D) depends on a c a r d i n a l i t y result of Andrew Adler, which we state as a lemma: 4.15 Lemma (GCH) (A. Adler) Let D be a uniform u l t r a f i l t e r on a u l t r a f i l t e r on R. and l e t E be any Then i f a + a /D| = |a /E| 3 |cf(a) and + a /Dl = | c f ( a ) / E | B then we must have $ > a. Proof By 1.14(b) we have |a a /D| > a . a /D| > a and so by 1.15(h), GCH Thus |a | > |a /E| > a 3 3 which, with GCH, implies that 8 > c f ( a ) . for any <I,F>, y, 6 that ^1 By 1.14(c)(ii) we have - 101 - 4I = a and F = D to In this inequality set y = a , 6 = c f ( a ) , obtain + |(a ) /D| < | a + a + /D|l a + c f ( a ) a I /D so a < |a + a + /D|' c f ( a ) a + / D If 6 < a then |a^/E| = | a /D| p a / D| . (*) = a . By hypothesis a |cf(a) /E| = | c f ( a ) l + Now 8 > c f ( a ) |cf(a) /E| < 6 3 = 8 3 + so < a . Thus + I a Ia ,_i /D| cf(a) 1 /D y 1 ^ , +.a + < (a ) = a which contradicts (*). Hence 8 s a. 4.16 // Theorem (GCH) Let D be an u l t r a f i l t e r on I, then i f a + e a(D) either (1) a e a(D) or (2) a i s a l i m i t point of a(D). Proof Suppose to the contrary that there exists 8 < ot 8 < Y - a implies y i a(D). such that By Chang's Theorem we can take a to be a l i m i t cardinal so that 2 =8 l < a < a and 4.4 applies to show that h # : a / E -> a 3 a /D i s an isomorphism (w.r.t. any structure on a) f o r some h : a"*" •> 8 - 102 - and where E = h(D). But i f A i s a subset of a of power cf(a) then h^ preserves the corresponding unary predicate and so r e s t r i c t s to a b i j e c t i o n h /D . : A /E -»• A P Thus |a /E| = e and |a /D| A+ |cf(a) /E| = |cf(a) P a /D| and so by 4.5 8 > a, a contradiction. // We may prefer to express t h i s theorem i n the contrapositive: If a / E. a(D) then a + e a(D) Further Results on Quasicomplete i f f a i s a l i m i t point of cr(D). Ultrafilters An important and so yet not f u l l y resolved question i n the theory of u l t r a f i l t e r s i s the question of whether there e x i s t u l t r a f i l t e r s D on sets I of "modest" c a r d i n a l i t y such that y i ( D ) a for some regular cardinal y < | l | . As we observed i n Section B the existence of such a y implies that D i s (y,X)-quasicomplete for some X > y, i n fact D w i l l have a y-quasicomplete image Equivalently we can ask f o r each K >.• oo which cardinals on X. X > K + support K-quasicomplete ultrafilters. We already know from Section B that we can take X = y, the f i r s t measurable cardinal. We also have the following theorem, which generalises - 103 - the r e s u l t of Chang and Prlkry for indecomposable ultrafilters that we mentioned i n Section B. 4.17 Theorem (GCH) If D i s a K-quasicomplete u l t r a f i l t e r on a set of cardinal A > K + then either X i s inaccessible or cf(A) < K . Proof By 4.16 A. i s a l i m i t cardinal as i f X = 6 + then either 6 e a(D) or 6 i s a l i m i t point of 0"(D). for some But by hypothesis K < y < X implies y I a(D). Also as D i s uniform on a set of c a r d i n a l i t y A we have A e a(D) and hence cf(A) e 0"(D). cf(A) = A or cf(A) < But then we must have either K. / / Throughout the rest of t h i s section D i s a K-quasicomplete u l t r a f i l t e r on a set I of c a r d i n a l i t y A where 2 l < X. By 4.4 this means that there i s a map h : I -»- K such that the i n j e c t i o n h* : y / E - y ^ D K (E = h(D)) i s onto for a l l y < A and hence induces isomorphisms /A /E K = A /D I f o r a l l structures /A such that |A| = y < A. For uniformity of notation we w i l l take K = J and set h "*"(j) = 1^ f o r a l l j £ J . We define a preordering on the subsets of I as follows: If X, Y £ I X^Y set i f f '{j : X n I, £ Y n I,} e E . - 104 - We are interested i n the following statement: C(8) : i f {X^ : n < 8) Is a c o l l e c t i o n of 8 elements of D then there i s an X e D such that X ^ X N n < 8. ail for n We s h a l l show that i f A i s a strong l i m i t cardinal (and, i f LCH holds, i t always i s ) that C(8) holds f o r a l l 8 < A. This i s the "completeness" property that motivates the name "quasicomplete". Suppose, then, that A i s a strong l i m i t cardinal and that {X^ : n < 81 i s a c o l l e c t i o n of 8 < Amembers of D. II Define a p a r t i t i o n of I by illi «-» f o r a l l n < 8 1 i eX n iff i 'e X n Then II p a r t i t i o n s I into at most 2 3 cells. Suppose that II breaks up each I. so that 3 I. = u{l? : E < 2 } 3 J As 2 <£j 3 we have that h ^ i s onto and so by 3.1 there i s a sequence 2 : j e J> £ ( 2 ) such that 3 < A . R 3 J u{l^J Now take X = u{lj : j e j} £ D. : j £ j} then i t i s clear that {j : X n I. meets X n I.} £ E 3 H 3 but X n I. = I. 3 X n l . c X 3 ~ 3 n n I. J so that i f X n I. meets X 3 so that n n I. then j - 105 - { j : X n I . c X n I . } e E J and hence X ^ for a l l n < Notice all t h a t we 8 such t h a t 2 < 3 TI ~ J 8- have, i n f a c t , shown t h a t C(8) holds for X. R e t u r n i n g to the assumption t h a t X i s a s t r o n g note t h a t i f c f ( X ) < X c a r d i n a l we C(X). For l e t X = u{a^ £ < 8 and l e t {X^ (and hence < K ) we : £ < 8) where 8 < X and : n < X} be limit a l s o have < X for a l l a c o l l e c t i o n of members o f D. r Then as C(a^) holds there X ^ and as C(8) i t follows e a s i l y |A| h* range o f of /A/D. I for a l l n < X . A fk i s any s t r u c t u r e such t h a t embedding : /A/E J -WA^D hence an isomorphism. then by 2.6 h ^ However we 5 < 8 have shown t h a t i f = a < X then the i s onto, and for a l l that X < X^ We (? < B) i s a set X e D such t h a t X < X^ and n < dp for a l l X^ holds there e D such t h a t are s e t s X i s not onto as On E g6 D the other hand i f |A| and hence /A^/E ¥ /A^/D. have the f o l l o w i n g theorem which shows t h a t h ^ still froms a very comprehensive the substructure = X - 106 - 4.18 Theorem Let /A be any structure of c a r d i n a l i t y X. any set of formulas from Then i f E i s ( c f . Chapter 1, Section D) such that |E| < X then £ i s s a t i s f i a b l e i n /A /D i f f £ i s s a t i s f i a b l e 1 already i n h* < /A /E) J A Proof Suppose E = {(J)^ : r| < 8) where 8 < X and that f/D e /A IU i s such that 1 /A /!) 1 Let for a l l n < 8 . 1= <|> (f/D) X , = {i £ I : /A 1= <> f ( f ( i ) ) } , then X. £ D for each n < 8 by Los' Theorem. holds there i s X £ D such that As C(8) for a l l n < 8. X We define g £ A 1 as follows: X n I . 4 4> pick i _ e X n I . and define g ( i ) = f (i^.) J 0 j ° 0 for a l l i £ I. 3 " if i f X n I j = 4> i £ I . . ( l £ pick a^ £ A and set g ( i ) = a^ f o r a l l J) . 3 Then g i s constant on each I j so that by 3.1, g/D £ range ( h ^ ) . But for each n < 8 we have that {i : /A 1= c|> (g(i))} 3 Y^ : X n I. c X 3 ~ where Y„ then g ( i ) = f ( i ) for some ^ = u { l . 3 Q n n I . } n X . 3 i Q e X n I Por i f i e Y^ n where i £ 1^ 107 - but then as i r t 0 - € X n I. n 3 we have /A N d> (f(i„)) so that A But Y e D n - Y = h * <|> ( g ( i ) ) . as : X n I. cx = h (Z ) n X i n I.\) n X} where _ 1 n Hence {i : /A Z e E . n N cj>^(g(i))} e D so that a l l n < 8 , and g/D s a t i s f i e s Z. As ^/D = <|> (g/D) f o r g/D e range ( h ^ ) = h* ( /A /E) J /A the theorem i s proved. // In the case of singular strong l i m i t cardinals X we have shown that C ( A ) holds and we can strengthen 4 . 1 8 to hold f o r sets of formulas Z with |z| = X. As an i l l u s t r a t i o n of 4 . 1 8 we w i l l note a s p e c i a l case. Let a be a structure on the cardinal a that has the well-order < as one of i t s r e l a t i o n s , and l e t B be an elementary extension of a. Then i f 6 i s any element of a we w i l l say that B i s r e a l i s e d in i f there i s a b e B such that B B = n < b < B for each n < g. Now regard A_ and A_^/E as substructures of the embeddings i and h* respectively. of A^/D by v i r t u e I f E = {(TI VQ<B) : r)<B} < i t i s easy to see that r e a l i s i n g 8 and s a t i s f y i n g E are equivalent conditions on extensions of X. Then we have immediately - 108 - 4.19 Corollary If 8 < A then 8 i s realised i n A^/D i f f 8 i s already realised i n A_ /E. // J Informally, 8 i s r e a l i s e d i n a /F i f f 8 i s not confinal K K i n 8_ /F(c a /F) . We can show after the manner of 2.17 that 8 i s realised i n a /F i f f F i s 8-d.i. The result of 4.19 then would follow d i r e c t l y from the observation that a(D) = 0(E) u {A} . BIBLIOGRAPHY [1] A. A d l e r , C a r d i n a l i t i e s of U l t r a p o w e r s : An Example, P r o c . Amer. Math. Soc. 28 (1971) pp. 311-312. [2] A. A d l e r , R e p r e s e n t a t i o n s o f Models o f F u l l T h e o r i e s , t o appear. [3] A. A d l e r and M. A. Jorgensen, I n e q u a l i t i e s f o r the c a r d i n a l i t y of u l t r a p r o d u c t s , t o appear. [4] J . L. B e l l and A. B. Slomson, Models and U l t r a p r o d u c t s : An I n t r o d u c t i o n , N o r t h - H o l l a n d , Amsterdam [5] D. Booth, (1969). U l t r a f i l t e r s on a countable s e t , Annals o f Math. L o g i c 2 (1970), pp. 1-24. [6] C. C. Chang, D e s c e n d i n g l y incomplete u l t r a f i l t e r s , Trans. Amer. Math. Soc. 126 (1967), pp. 108-118. [7] T. Frayne, A. M o r e l , and D. S c o t t , Reduced d i r e c t p r o d u c t s , Fund. Math. 51_ (1962), pp. 195-228. [8] H. J . K e i s l e r , L i m i t u l t r a p o w e r s , T r a n s . Amer. Math. Soc. 107 (1963), pp. 382-408. [9] H. J . K e i s l e r , Good i d e a l s i n f i e l d s o f s e t s , Annals of Math. 7_9 (1964), pp. 338-459. [10] H. J . K e i s l e r , Ultrapowers and S a t u r a t e d Models, Indeg. Math., 26 pp. 178-186. [11] H. J . K e i s l e r , On c a r d i n a l i t i e s o f u l t r a p r o d u c t s , B u l l . Amer. Math. Soc. 70 (1964), pp. 644-647. [12] K. Kunen and K. P r i k r y , On d e s c e n d i n g l y incomplete to appear. - 109 - ultrafilters, - 110 - [13] K. Prikry, On a problem of Gillman and K e i s l e r , Annals of math, l o g i c 2 (1970), pp. 179-187. [14] J . S i l v e r , Indecomposable u l t r a f i l t e r s and 0^, talk at Tarski Symposium, Berkeley, C a l i f . , June 23-30, 1971. [15] S. Sirota, On the problem of the c l a s s i f i c a t i o n of f i l t e r s , Sov. [16] Math. Doklady 11 (1970) pp. 408-411. A. Tarski, Ideale i n vollstandigen Mengenkb'rpen I, Fund. Math. 32 (1939) pp. 45-63. [17] S. Ulam, Zur Masstheorie i n der allgemeinen Mengenlehre, Fund. Math. 16 (1930), pp. 140-150.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some size and structure theorems for ultrapowers
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some size and structure theorems for ultrapowers Jorgensen, Murray Allan 1971
pdf
Page Metadata
Item Metadata
Title | Some size and structure theorems for ultrapowers |
Creator |
Jorgensen, Murray Allan |
Publisher | University of British Columbia |
Date Issued | 1971 |
Description | In this thesis we study the mapping D → A[sup I]/D, between ultrafilters and models, given by the ultrapower construction. Under this mapping homomorphisms of ultrapowers induce elementary embeddings of ultrapowers. Using these embeddings we investigate the dependence of the structure of an ultrapower A[sup I]/D on the cardinality of the index set I. With each ultrafilter D we associate a set of cardinals a(D) which we term the shadow of D. We investigate the form of the sets a(D). It is shown that if σ(D) has "gaps" then isomorphisms arise between ultrapowers of different index sizes. In terms of σ(D) we prove new results on the properties of the set of homomorphic images of an ultrafilter. Finally we introduce a new class of "quasicomplete" ultrafilters and prove several results about ultrapowers constructed using these. Two results which can be mentioned here are the following: Let α be a regular cardinal. We establish necessary and sufficient conditions on D (i) for the cardinality of α to be raised in the passage to α[sup I]/D. (ii) for the confinality of α[sup I]/D (regarded as an ordered set) to be greater than α⁺. Some of the results of this thesis depend on assumption of the Generalised Continuum Hypothesis. The result (i) above is a case in point. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-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.0080477 |
URI | http://hdl.handle.net/2429/32660 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1972_A1 J67.pdf [ 4.34MB ]
- Metadata
- JSON: 831-1.0080477.json
- JSON-LD: 831-1.0080477-ld.json
- RDF/XML (Pretty): 831-1.0080477-rdf.xml
- RDF/JSON: 831-1.0080477-rdf.json
- Turtle: 831-1.0080477-turtle.txt
- N-Triples: 831-1.0080477-rdf-ntriples.txt
- Original Record: 831-1.0080477-source.json
- Full Text
- 831-1.0080477-fulltext.txt
- Citation
- 831-1.0080477.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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080477/manifest