UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Some size and structure theorems for ultrapowers Jorgensen, Murray Allan 1971

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items