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.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

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), University of Canterbury, 1967 MA, University of 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 hesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA December 1971 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis fo r scholarly purposes may be granted by the Head of my Department or by h i s representatives. It i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of The University of B r i t i s h Columbia Vancouver 8, Canada Date 1% Feb. 1971 Supervisor: Dr. A. Adler ABSTRACT In this thesis we study the mapping D /A^ /D, between ul 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 cardinality 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. We investigate the form of the sets a(D). It i s shown that i f a(D) has "gaps" then isomor-phisms arise between ultrapowers of different index sizes. In terms of o~(D) we prove new results on the properties of the set of homomorphic images of an u l t r a f i l t e r . Finally 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 establish necessary and sufficient conditions on D (i) for the cardinality of a to be raised in the passage to a,/D. ( i i ) for the confinality 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. The result (i) above is a case in point. - i i -TABLE OF CONTENTS Page Chapter 1. Introduction and Preliminaries 1 A. Introduction 1 B. Set Theoretic Notation 3 C. R e l a t i o n a l Structures 4 D. Saturated Structures 9 E. U l t r a f i l t e r s , Ultraproducts, Ultrapowers 10 F. Operations 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 of Ultrapowers 21 Chapter 2. Images of U l t r a f i l t e r s and Embeddings of Ultrapowers 26 A. Isomorphism of Ultrapowers 26 B. Images of U l t r a f i l t e r s , . 38 C. Ultrapowers as Ordered Sets 48 D. Shadow and C a r d i n a l i t y I 53 E. Categorical Formulation .. 55 Chapter 3. Reduction of Index Size 58 A. When i s onto 58 B. Transcendence degree of an Ultrapower 63 C. Ultrapowers that are Dir e c t Limits 67 D. A Hierarchy of Substructures 75 - i i i -- 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 Ul t r a f i l t e r s 102 ACKNOWLEDGEMENTS This thesis could not have reached i t s present form without many months of goading and guiding by my supervisor Dr. Andrew Adler nor without the e f f i c i e n t typing of Mrs. Edith Huang. Thanks also go to those who read my thesis i n i t s early stages and made many h e l p f u l suggestions. - v -CHAPTER 1 INTRODUCTION AND PRELIMINARIES A. Introduction Starting from a relat ional structure /A we can define, for each u l t r a f i l t e r D on an index set I, a new*relational structure /A^ /D called an ultrapower of /A. /A^ /D possesses the same f i rs t -order properties as Ik but is not in general isomorphic to /A. Most of the interest and attention given to ultrapowers has been directed to their application in 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 particular u l t ra -powers rather than on investigating general properties of ultrapowers. The acuteness of our ignorance in this latter area is emphasised by the many unresolved questions relating to the cardinality of ultrapowers. This present work represents a contribution to a "general theory" of ultrapowers whose preoccupation is with relating the form of the ultrapower /A^/D with the form of the u l t r a f i l t e r D used to define i t . To be more precise let us suppose that /A l i s t s among i t s relat ions, functions, and constants a l l the f in i tary relations and operations on i t s underlying set A and a l l members of A so that /A now carries as much structure as possible. Using this structure we define the natural notions of isomorphism between two ultrapowers A^/D and /A^/E and isomorphic embedding of /A^/E into /A^/D. Then we can ask - 2 -how c l o s e l y the isomorphism class of the ultrapower A /D determines the u l t r a f i l t e r D. For instance i s i t true that i f D and E are u l t r a f i l t e r s on I and /A1/]) = /A^/E then D = E ? If not, what r e l a t i o n does D bear to E ? Also how many isomorphism classes i s the set { /k1/^ : D an u l t r a f i l t e r on i} broken into? Of course the answer to. these and s i m i l a r questions w i l l depend on the si z e of |A|. For example i f A i s f i n i t e we have that Ik1/!) = Ik = /kT/E for a l l u l t r a f i l t ers D and E on I. Another kind of question i s (*) Given A, I and D what cardinals can be written i n the form  | j | , where J i s a set on which there resides a uniform  u l t r a f i l t e r E such that fk1/!) = /AJ/E ? In the remainder of t h i s chapter we w i l l f i x on our notation and c o l l e c t together some preliminary r e s u l t s known from the l i t e r a t u r e . In Chapter 2 we place a natural algebraic structure on the class of a l l u l t r a f i l t e r s . We show that i f we r e s t r i c t ourselves to u l t r a -f i l t e r s on a given set I and i f we take |A| s u f f i c i e n t l y large (3: |I|) that the algebra of ultrapowers of Z\ i s completely determined by t h i s algebra of u l t r a f i l t e r s up to an isomorphism of categories. We then c o l l e c t and prove r e s u l t s about t h i s algebra which f i n d an immediate a p p l i c a t i o n i n proving a s i z e r e s u l t (2.20) not previously derivable without the Generalized Continuum Hypothesis. Chapter 3 applies some of the ideas of Chapter 2 to give p a r t i a l answers to (*). Roughly speaking we investigate how "economi-c a l l y " an ultrapower can be obtained (up to isomorphism), i t being "wasteful" to employ too large an index set. This idea leads to an - 3 -interesting 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 results on the algebraic structure of an u l t r a f i l t e r D and on the relationship of th i s structure to the c a r d i n a l i t y of ultrapowers employing D. We define a notion of quasicompleteness for u l t r a f i l t e r s 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 notational apparatus of set theory without special comment. Our informal set theory may be thought of as Zermelo-Fraenkel set theory including the Axiom of Choice, although we w i l l refer to proper classes on occasion. The l e t t e r s GCH, respectively, LCH, attached to a result indicate that the result has been proved under the assumption of the Generalized Continuum Hypothesis, respectively, the Limit Cardinal 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 functions. Cardinals are taken to be i n i t i a l ordinals and we s p e c i f i c a l l y designated a , 3> Y> 5 and K to range over cardinals. 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 ordinals or cardinals at various places i n the thesis. We w i l l allow the expression to remain ambiguous, i t s interpretation to be suggested by the context. For example we can write both f e A y and n < A y = - 4 -In any event ordinal exponentiation is not intended. The symbol + is reserved for ordinal addition, but • always stands for cardinal multiplication. £ and II are used for i n f i n i t e cardinal sums, resp., products. For any set X S(X) = {Y : Y c x} S (X) = {Y : Y c X and |Y| < K} S (X) = {Y : Y c X and |X-Y| < K} We w i l l often think of functions as sequences and employ notation to B li suggest this. Thus i f f e A and <f> e X we may write f = <ffe : b e B> and cj> = «$>^ : r\ < u> where f^ = f(b) and <j)^  = <))(ri)- a + i - s the smallest cardinal greater than a . X ^ i s Z<X V : V < u>, the weak cardinal power. C. Relational Structures As implies in the Introduction we w i l l be taking a relational  structure to be an ordered 4-tuple /A = <A, R, F, C> where A is a set, R is a sequence <R^  : n < A> of finitary relations on A, F is a sequence <F^  : r| < u> of finitary operations on A, and C is a sequence <c : n < v> of members of A. A is called the n underlying set of /A. The (similarity) type of a relational structure A is a triple <0, T, v> where a e , T e 0)^ such that - 5 -(i) for a l l n < A, R c A a ( n ) ( i i ) for a l l n < y, : A T ( n ) + A ( i i i ) C has length V . /A i s said to be a f u l l structure on A i f the range of R includes a l l finitary relations on A, the range of F a l l finitary 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 is associated a first-order 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, L ^  has a a(n)-ary predicate symbol P^. (3) Function Symbols for each n < y, L has a T(n)-ary function symbol G . /iv n (4) Constant Symbols are elements of the set {d^ : n. < v } . (5) Logical Symbols = , A , " - i , and a, from which ->, v, and V are defined in the usual way. (In defining L ^  we have taken the type of A to be <a ,T ,v> where range (a) = X and range (T) = y. Unless another type is specified we w i l l always use these letters to refer to the type of a relational system under discussion). - 6 -The notions of formula and term of L j are defined by the standard induction on length of expression. Free v a r i a b l e , bound  v a r i a b l e , and sentence also have t h e i r standard meaning. The type of L ^  i s j u s t the type of /A. If /A' i s a structure of the same type as L ^ , (j) i s a formula of L and x e A , W we s h a l l say the sequence x s a t i s f i e s the formula (j) i n /A' and write lAx h cj) x for the usual notion of s a t i s f a c t i o n , i n which = i s to be interpreted as i d e n t i t y . ( c f . [4], p.56). I f cj) i s a sentence the p a r t i c u l a r sequence x i n the preceding i s immaterial and we can write /A' N <J> and say /A1 i s a model of cj) or cf) holds i n /A' . If £ i s a set of sentences then /A' i s a model of i f f /A' 1= cj) for a l l <J> e J> For each structure /A the theory T ^  i s defined as the theory with language L ^  and with axioms a l l sentences belonging to the set {cj) : IA 1= cj)} . In general T ^  i s not 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 structures of the same type <a ,T,v> i s a 1-1 map f : /A^ -> lA^ such that (a) for a l l n < A and any elements a^, a2> ...» a a ( n ) £ ^ < a i a a ( n ) > € R l n i f f < f ( a i } f ( a a ( n ) } > e R2n (b) for a l l n < y and elements a ^ * ^ a t ( n ) ' a 6 ^1 F l n ( a i ; . . . , a T ( n ) ) = a i f f F ^ ( f ^ ) , .. . , f (a T ( n ) ) ) = f(a) (c) for a l l n < v f ( c m ) = c2n - 7 -Throughout the rest of t h i s section Ik and IB are structures of type <a,T,v> and L = L .. = L m . /A IB If lk £ B we say that /A i s a substructure of IB and write fk c IB i f f the i n c l u s i o n map i : A -> B i s an embedding of /k into IB. It i s easy to see that t h i s i s the case i f f each r e l a t i o n and each function of (B r e s t r i c t s to the corresponding r e l a t i o n or function of /A and each constant of IB i s equal to the corresponding constant of Ik. An embedding i s said to be an isomorphism i f i t i s onto. I f there i s an isomorphism between Ik and IB we say that Ik and IB are isomorphic and write Ik = IB. If fk c (B and for every every formula 4>(v_,...,v ) of L and any a„,...,a e Awe have O n O n /A r= ((i(a n )...,a ) i f f IB 1= ()>(an,...,a ) u n u n we say that /A i s an elementary substructure of IB or that IB i s an elementary extension of /A and write /A < JB If for every sentence (J) of L we have that A. N $ i f f IB i= (f> then we say that i'k and [B are elementarily equivalent and write /A = IB. Notice that = i s an equivalence r e l a t i o n and that i s t r a n s i t i v e . An embedding h : /A ->• JB i s c a l l e d an elementary embedding i f f o r any formula <j) (VQ ,.. . , v ) of L and any aQ,...,a e A /A 1= <|>(a0 a n) i f f (B i= ^ (h(aQ) h ( a n ) ) . A f i r s t order theory T i s said to be model-complete i f whenever IB and € are models of the set of axioms of T and IB £ C then (B < C • - 8 -1.1 Theorem If /A is a f u l l structure then T ^  is 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 ,. . . ,vn) of L ^ and any members bQ,...,bn e B we have that iB t= <j>(bp,.. . jb^) i f f <E (= cj>(bQ,... ,b^) . We proceed by induction on the number of logical symbols in cf). It is easy to show that the result i s true i f cj) is an atomic formula or i f <j> is cj)^  or cj)^  A cj^  where the result holds for cj)^  and <f>2. Suppose that <f> = axijj(x,bQ,. . . ,b^) where for a l l b e B iB N i[)(b,b ,.. . ,bn) i f f C t= ^ (b,b Q,.. . ,b ) . Clearly i f IB 1= cj)(bQ,. . . ,bn) then C 1= <j)(bg,.. . jb^) . The converse w i l l f a i l only i f C f= cj>(b ,. . . ,b^) but there i s no b e B such that B h \j)(b ,b^,.. . ,b^) . Assume that this is the case. Let R(x,y) be a relation of Ik that well-orders A. Pick An+1 a e A, and define f e A such that f(a„ a ) i s the least element U n of A under R such that A t= tjj(f (ag,.. . ,a^) , aQ,...,an), or f(aQ,...,an) = a i f no such least element exists. Then as /A is f u l l f i s a function of /A, corresponding, say to a function symbol t. Now by assumption |B (= (t (b^, .. . jb^) jb^,. .. jb^) so that by the induction hypothesis C 1= ip(t(bQ,.. . ,b ) ,bg,.. . ,bn) . But for a l l CQ,...,c n eC» i f C f= <£(CQ, .. . ,c n) then t(cQ,...,c n) i s the R-least element of C such that <C *= ijj(t(c A,.. . ,c ),c~,...,c ). But u n u n this i s a contradiction. So there i s b e B such that iB t= ijj(b,bQ, • • • >bn) , IB i= a( x)ij)(x,b0 b Q) . // - 9 -In the following we denote the structure fk by <A,R 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 is an n-ary operation in range (F ,.) then F (a..,...,a ) eY. If X is a subset of A /A T| X n that generates i t s e l f then we can define a substructure H of A, the restriction of A to X as follows: i) H = X RlH,n = R A , n n x G ( n ) f o r 3 1 1 n K X ^ Vn = FA,nV<--> ^ r aim <y 1 V ) C f l = C/A H is denoted by A| v . A. D. Saturated Structures Recall that the type of fk is taken to be <a,T,V>. If X = <e^ : ^  < 0> is a sequence of elements of A we define a structure A°x to be the structure formed from A by attaching the sequence x after the sequence C ^  to form a new sequence of constants. Thus A°x is a structure of type <a,T,v+6>. (The sequences of relations and functions and the underlying set of /A are not changed.) For any structure IB of arbitrary type let f^-^ be the set of formulas of L. with at most VQ free. Take A £ j - ^ We shall say that A is satisfiable in B i f there is a b e B such that IB t= <f>(b) for a l l <$> e A and that A is f i n i t e l y satisfiable in B i f every f i n i t e subset of A - 10 -i s s a t i s f i a b l e i n tB. F i n a l l y we define A to be a-saturated i f , for a l l sequences X of elements of A having length less than a, any subset of i ^ o x that i s f i n i t e l y s a t i s f i a b l e i n Jk°X i s also s a t i s f i a b l e i n /A°X. The theory of saturated structures forms a large body of r e s u l t s , but we need only the following: 1.2 Theorem (a) I f /A and jB are a-saturated, elementarily equivalent, structures of the same type, and i f |A| = |B| = a , then lk and IB are isomorphic. (b) I f Ik i s an a-saturated structure of c a r d i n a l i t y a and IB H /A, where |B| < a , then tB can be elementarily embedded i n /k. Proof (a) See [4], p.224, Th. 3.1. (b) See [4], p.226, Th. 3.2. // E. U l t r a f i l t e r s , Ultraproducts, Ultrapowers A f i l t e r D on a set I i s a non-empty subset of S(I) such that (a) X, Y e D implies X n Y e D ; (b) X e D and Y = X implies Y e D . I f 0 / D, D i s c a l l e d a proper f i l t e r . A proper f i l t e r that i s included i n no other proper f i l t e r i s c a l l e d an u l t r a f i l t e r . A necessary and s u f f i c i e n t condition for a proper f i l t e r to be an u l t r a f i l t e r i s (c) X c I implies e i t h e r X e D o r l - X e D . For - 11 -For any i e I the set [i] = {X c i : i e X} i s an u l t r a f i l t e r on I. An u l t r a f i l t e r of t h i s form i s c a l l e d p r i n c i p a l . A family E c S(I) i s said to have the f i n i t e i n t e r s e c t i o n property (f i p ) i f any f i n i t e subfamily of E has non-void i n t e r s e c t i o n . 1.3 Theorem Any family E c S(I) having the f i p can be extended to an u l t r a f i l t e r on I. Proof A c l a s s i c a l and easy a p p l i c a t i o n of Zorn's Lemma. // 1.4 Theorem 2 I H 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 there are c l e a r l y only |I| p r i n c i p a l u l t r a f i l t e r s on I i t follows that "most" u l t r a f i l t e r s on I are non-principal. An u l t r a f i l t e r D can be regarded as a measure on the set of subsets of I i n the following way: For each X c I define y D ( x ) = 1 i f X e D 0 i f X i D then i t i s a consequence of (a), (b) and (c) that U D i s a f i n i t e l y - 12 -additive {0,l}-valued measure on I. This way of regarding D as a measure is a valuable aid to intuition 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 in 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 qualification "(mod D)". Consider, now, a sequence of relational 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 define the ultraproduct B = IT< IA^ : i £ I> / D 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 ~ D on B' as follows: i f a, b e B' set a ~ b i f f '{i e I : a. = b . } e D 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\~^ relation of A. where n. < A. Then i f 0(n) = n and a^/D, a^lVi, an/D e B we define R B,n s o t h a t <a1/D,...,an/D> e i f f {i : < a ±. ,. . . ,anl>eR. > n> e D. - 13 -c) Functions Let x(n) = m, then we define F m by tB,n J F i B , n ( a l / D " " ' a m / D ) = a / ° i f f { i : F i , n ( a l i a m i * = a i * e D ' ( n < 1-0 • d) Constants C-B.Tl " S / ° where g ( i ) = c. , (n < v ) . I t remains to v e r i f y that R , F and C _ are a l l w e l l -to p lt> defined 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 . If each factor /A^ Is the same, say /A^  = /A for a l l i e I, then we c a l l the r e s u l t i n g structure B an ultrapower of /A and write B = A I / D . The importance of ultrapowers and ultraproducts arises from the following "Fundamental Theorem": 1.5 Theorem (Los' Theorem) Let lA^ ( i e I ) be as above and l e t cj) be any formula of L = L _ and D any u l t r a f i l t e r on I . <CT,T,V> J Then Jl< IA. : i e I > / D t= <j> 1 x i f f { i e I : /A. f= cf>} e D l x. l where x = < I Q / D , f ^ / D , ...> i s any countable sequence of members of - 14 -: i e I>/D and x i = < f Q ( i ) , f - ^ i ) , . ..>. 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 y= 4> i f f /A. r= d) for almost a l l i e I. I ( i i ) /A = fk1/!). Proof Immediate from 1.5. // In fact we can strengthen part ( i i ) of 1.6. For let \ : A A^ /D be defined by setting l(a) = f /D where f : I -> A a a has constant value a. Then we claim that i i s an elementary embedding of fA into /A^ /D. For i f (J)(VQ,V^, . . . »vn) i s any formula of L and a^ a^ any elements of A we have by 1.5 that Ik1 I'D t= <J>(f /D, .. . , f /D) a A a 0 n i f f {i : /A t= <|>(f ( l ) , . . . , f (D)} e'D a„ a 0 n i f f {i : Ik F ^(a-,.. . ,a )} e D U n i f f Ik F (Ka,- . ,.. . ,a ) . u n l is called the canonical embedding of Ik in Ik I'D. We now discuss certain types of u l t r a f i l t e r s that are useful in the formation of ultrapowers. Let I be an arbitrary i n f i n i t e set. - 15 -A principal u l t r a f i l t e r on I is remarkable in that i t contains an element of cardinality 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 | . We have immediately: 1.7 Theorem An u l t r a f i l t e r on I is uniform i f f i t contains the f i l t e r S a (D, where a = |I| . II 1.8 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. // Principal u l t r a f i l t e r s are closed under arbitrary intersec-tions of their elements: in fact this property characterises principal 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 for a l l i i i e I but n{X : i e 1} = 0 I D. 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 is B-incomplete. If E is 8-complete for a l l B < y w e s aY E is ^ -complete, otherwise E i s y-incomplete. Thus i f | l | = a , every a-complete u l t r a f i l t e r on I i s principal. Every u l t r a f i l t e r is to-complete by definition. If | l | = a > 03 i t is 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 on I are famous problems in the history of set theory. The f i r s t , and most seminal, work on these questions is the paper of Ulam [12]. It is known that the answer to both questions is negative for a wide class of cardinals a that includes a l l cardinals commonly encountered in most branches of mathematics. We have the following result. 1.9 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 > c o . The hypothesis that such u l t r a f i l t e r s exist i s known as the axiom  of measurable cardinals. This area of set theory is s t i l l under active study. The word "measurable" here results 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 is co-complete. Measurable cardinals are those cardinals a which support co-complete non-principal ultra-f i l t e r s . Usually we work with CO-incomplete u l t r a f i l t e r s . There is an equivalent way of stating a-completeness that we w i l l sometimes use - 17 -1 . 1 0 Theorem D i s an a-complete u l t r a f i l t e r on I i f f for every c o l l e c t i o n {X^ : n < a'} of a' < a subsets of I, UCX^ : n <a1} e D implies X e D for some n_ < a'. n0 o Proof A routine a p p l i c a t i o n of de Morgan's laws. // Ultrapowers taken using complete u l t r a f i l t e r s do not y i e l d new structures: i n fac t we have the following r e s u l t . 1 . 1 1 Theorem If D i s a-complete and |A| < a then Ik^/D = Ik. Proof Under the hypotheses we w i l l show that a : Ik /k^/D i s onto. For suppose f/D e A^/D, and l e t X = { i e l : f ( i ) = f (i)=a}. 3. cL Then u{X : aeA} = I e D and so by 1 . 1 0 there i s a~ e A such that a J 0 X € D. Hence f ~ f and f/D € range ( i ) . // a 0 D a o We w i l l now define another kind of property an u l t r a f i l t e r can have which also stands i n a n t i t h e s i s to the property of being p r i n c i p a l . Let K be any c a r d i n a l . A family X £ s f o r m s a K-covering of I i f for each i e I |{X e x : i e X}| < K . An u l t r a f i l t e r D on a set I i s c a l l e d ( K , A ) - r e g u l a r i f there e x i s t s a K-covering ){ of I such that X £ D a n & ! x l = A - An - 18 -u l t r a f i l t e r i s c a l l e d simply regular i f i t i s (to, 11| )-regular. 1.12 Theorem Proof (i) I f |I| > a) there e x i s t s a regular u l t r a f i l t e r on I. ( i i ) I f | l | = OJ a l l non-principal u l t r a f i l t e r s on I are regular. ( i i i ) Any regular u l t r a f i l t e r i s uniform and to-incomplete. (i ) Let cj> : I -»• S ^ ( I ) be a 1-1 onto function, and set X ± = { j e l : iecKj)}-Then we claim that X = {x^  : i e l} has the f i p . For l e t {X. ,...,X. } be a f i n i t e subset of x. Then x ' x 1 n there e x i s t s i ^ e I such that 4>(1Q) = {i^»'»*»i n} and hence ±n e X. n ... n X. . So by 1.3 X extends O x - x J 1 n to an u l t r a f i l t e r F on I . F i n a l l y x i s an oo-covering as |{j : ieX }| = |<f>(i)| < O) . / ( i i ) As noted above a l l non-principal u l t r a f i l t e r s on a set of ca r d i n a l 03 are 03-complete. Let {X^ : n<0)} be a c o l l e c t i o n of members of D such that X=n{X : n < 0 3 > ^ D . Then i f Y = XnnX. n .. . n X - X n n 0 1 n i t i s clear that Y e D for a l l n < 0) and that n (Y^ : n < 03} i s an 0)-covering of I . / ( i i i ) I f D i s regular l e t {X^  : n < 111 } = x be an 03-covering of I by members of D. Then nlX^ : n < 03} = 0 I D - 19 -so that D is 03-incomplete. If D is not uniform let X e D be an element of the smallest cardinality. Then | X | = |x n X j < | l | for a l l n < |I|. But this implies there is x e X such that | { n : x e X ^ } | = | l | , a contradiction as x is an co-covering. // F. Operations on Ul t r a f i l t e r s We w i l l be employing various ways of constructing new ul t r a f i l t e r s from given u l t r a f i l t e r s in 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 restriction of D to X is 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| SO defined i s an ultra-f i l t e r . Note that any u l t r a f i l t e r can be restricted to a uniform u l t r a f i l t e r . (Take X to be a member of D having smallest cardinality.) 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 restrictions. - 2 0 -(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 i f f {j : X ^ e D} e E where X ^ = {i : <i,j> e X}. (3) Infinite Sum Suppose we have a family {i^ : A e A} of disjoint 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 i f f ' {A :,X n I^.e D^ } e E We write D = O u , : A e A}, hj A (4) Image If D is an u l t r a f i l t e r on I and f is 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 i f f f _ 1 ( X ) e D. We write E = f(D) in this situation. : Now we prove the following theorem about (2). 1.13 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 ~ TXT [ /A1/D]J/E = /A / DXE . Proof Let cj) : (A 1)^ A 1 ^ be the standard identification, i.e. (j>(<hj : j e J>) = k where k(i,j) = h^ ( i ) . Then xh./D : jeJ>/E = <hj/D : jeJ>/E - 21 -i f f {j : {i : h.(i) = h!(i)} e D} e E i f f {<i,j> : h (i) = h!(i)} e D x E i f f {<i,j> : k(i,j) = k'(i,j)} e D x E i f f ^ < h j : ^ £ J > ) / D x E = <K<hj : 3 e J>)/DXE So i f we define !j> : [A I/D] J/E -> A I x J/DxE by (j)(<h /D : jeJ>/E) = <j> (<h. : jeJ>)/DxE thenLcj) i s well-defined, 1-1, and clearly onto. i—* We can easily check that cj) preserves a binary relation R of R ^  by repeating the above argument with "R" in place of "=". The argument for general relations and functions is no more d i f f i c u l t . Thus we see that <j> is an isomorphism. // G. Cardinality of Ultrapowers We collect here some known results that w i l l be used in 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» a n < i a a n d 3 arbitrary. 1.14 Theorem (a) a < | ct1 /D | < aY (b) If D is uniform ly 1/!*! > Y (c) (i) I O V D I 6 < |(aV/D| ( i i ) |(aV/D| <- laVDl1^0! (d) If a is fi n i t e |aI/D| = a - 22 -(e) i f D is regular and a > co then | otX/D | = aY (f) If D is co-incomplete then i f a > OJ I^/DJ" = |otx/r>|" . Proof (a) i s t r i v i a l . (b) is proved by a diagonal argument. For complete proof see [4], p.132, Theorem 3.19. / (c) (i) Consider the map $ '.(oft)1 •> (a1) 3 given by <K<h± : i e I>) = k i f f k(n)(i) = h ±(n) 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 -»• (a1/!))6. Further i t is clear that $ and $ are onto. ($ i s also 1-1, but $ need not be.) Consequently | ( a W | s |(aV/D|. / (c) ( i i ) Consider the map * : (a 3) 1 - (a 1)^ given by "p(<lu : i e I>) = k where k is given by k(f) = g i f f g(i) = h ± ( f ( i ) for a l l i e I. ip induces a map : (aV/D -* (a-/B)&1/1) - 23 -such that "K < n ^ : i e I>/D) = k where k is given by k(f/D) = g/D i f f g(i) = h (f(i)) for almost a l l i in I (mod D). It is readily checked that the definitions given for k and ip do not depend on particular choices from equivalence classes. We now show that lp is 1-1: suppose that <ru : i £ I>/D 4 <h| : i £ I>/D then {i : h 4 h^} e D so there is an f e 6 * such that {i : h ± ( f ( i ) ) 4 h|(f(i))} e D hence i f k = •p(<hi : i £ I>/D) and k' = -|;(<h^  : 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 are co-complete. / (e) We prove a l i t t l e more: suppose D is (OJ,A)-regular and a > GO, then |aI/D| > a \ Then (e) follows when A = y« Let x = : n < A} be an co-covering of I by members of D. Let A± = (n : i e'X }, then A i is f i n i t e for a l l i e I. Let <A^  : n < c o > be a sequence of disjoint subsets of a such that IA I = a and let "b : a n -> A be 1-1 maps. 1 n 1 n n If f £ and {r\ ,. . . ,n } = A £ S (A) where J_ rC 03 < n 2 < ••• < i k w e set f*(A) = <f(n 1),...,f(n k)>. Now define 9 : •+ a} by (9f)(i) = \P|A j (f*(A.)) - 24 -Let 9 : a* -> a^/D be such that 9f = 0f / D . If f, g e and f 4 g then there i s n < A such that f(n) ^  g(n) hence i f i e X^, f*(A ±) 4 g*(A±) so that {i : 6f(i) 4 6g(i)} e D and 6f 4= 0g. Thus 0 is 1-1 and the conclusion follows. / (f) see [ 2 ] , p.130, Theorem 3.16. This result is also a corollary of 1.16. / Remark The result (b) is proved in Frayne, Morel, Scott [7]. (c)(i) is found in Keisler [11]. (c) ( i i ) is a result of A. Adler and appears in [3]. (e) is proved in Keisler [8], where a discussion of the history of the result i s given. 1.15 Corollary (g) 2 6 < | ( 2 3 ) I / D | < 2 l 0 l / D l . (h) i f | ( 2 3 ) I / D | > 2 3 then | 6 I / D | > g. Proof (g) Set a = 2 in (c) and apply (d). (h) follows from (g). // H. J. Keisler in [11] generalises the argument of 1.14(e) to prove the following result. - 25 -1.16 Theorem Let D be (K,X)-regular and let {X^  : n < A } c D b e a K-covering of I, then X K -\ll<a± : ieI>/D| < | < a i 1 : ieI>/D| where K. = | { n : i e X } | < K . // From this result can be derived ( c ) ( i ) , (e) and ( f ) . We shall refer to 1.16 as Keisler's Lemma. Later we w i l l indicate other consequences of this result. CHAPTER 2 IMAGES OF ULTRAFILTERS AND EMBEDDINGS OF ULTRAPOWERS A. Isomorphism of Ultrapowers In this chapter we shall 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 in Booth [5], where i t i s attributed to H. J . Keisler and M. E. Rudin. An u l t r a f i l t e r pair is an ordered pair <I,D> in 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 . If <I,D> and <J,E> are u l t r a f i l t e r pairs a map h : I -»• J is 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 - 1(X) e D. We then write h : <I,D> •+ <J,E>. If h is 1-1 onto in the above we shall say that h is 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 definition 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. It is proved in Sirota [15] that this i s an equivalent definition. We w i l l say that D and E are equivalent i f there are X e E, Y £ E such that DJ X = EJ y . We write E ss D. The relation is indeed an equivalence relation on the class of a l l u l t r a f i l t e r s . A l l principal 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 cardinality 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-tively such that |I| = |J| > 03 and there are X e E, Y e E such that D| = E| we can show D = Et We may assume |l-x| = |j-Y| = | l | . Let f : X -»- Y be a 1-1 onto map such that V e E[ i f f f - 1 ( V ) e D| and let g : I-X •> J-Y be any 1-1 onto map. Then i f we define h : I - > J b y h | x = f, b.| = g, i t is easy to check that h i s 1-1 onto and that Z e E i f f h _ 1(Z) e E and hence D = E. 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 in the class. One example is (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 in a w-class as each class contains u l t r a f i l t e r s of arbitrarily large cardinal, e.g. a l l expansions of a given u l t r a f i l t e r . 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 in D. Thus th(D) = min{|x| : X e D> . It is clear that a l l u l t r a f i l t e r s in a given s-class have the same thickness. The following theorem i s proved in Booth [5] for ultra-f i l t e r s on a countable set. H. J. Keisler, M. E. Rudin, and K. Kunen are given credit for independent proofs of the result. The proof we give here is a slight modification of Booth's. 2.1 Theorem Let <I,D> be an u l t r a f i l t e r pair 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 and Y ^ D , i . e . X u Y ^ D . Let f ^ denote the n-fold iterate of f. Then set (n) X n = {i : n is the least integer such that f (i) I X } (l<n<co). We have that u { X : 2 < n < 0)} = X , for, as < is a well-ordering, n each i £ I must belong to some X and X.. = I - X . If ° n 1 X , , = u{X_ , . : n < OJ} and X = u { X . ,„ : n < tu} then odd 2n+3 even 2n+2 X , , n X =0, X u X = X and X . = f _ 1 ( X ). So by odd even odd even odd even hypothesis X ,, e D i f f X e D , hence we must have X ,,, X I D J C odd even odd even and X )! D . If we define Y and Y , , in 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 ,,) is not a even odd (n) member of D . For each y e Y ' let = {f (y) : 1 < n < 0)} be the orbit of y under f. Then i t is easy to see that we can represent Y ' as a disjoint 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 1 under < ). Now let Y ' , , = {y : y is an odd member of i t s orbit} odd Y ' = {y : y is 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 < is a partial ordering on the s equivalence classes. - 29 -2.2 Theorem (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| Y = f (D| x ) , D| x, = g(E| Y ,) where X, X1 e D and Y, Y 1 e E. By part (a) we can assume that |x| = |X'| = th(D) and |Y| = |Y'| = th(E). As D|x and D| x , are equivalent u l t ra f i l te rs on sets of equal cardinality we have D| = D| , and s imilar ly E|Y = E| Y , and there exist 1-1 onto maps p : X' ->- X, q : Y -* Y' such that p(D|X,) = D| x and q(E| y) = E | y l . Then p[g(q[f(D| x)])] = D| x . So by 2.1 there i s X* e D, X* c X such that i f i e X*, p(g(q(f(i))) = i . But this implies is 1-1 and as Y = f(X ) eE we have f : Dj x * = E| *, so that D s s E. // The following theorem shows the relation between homo-morphisms of u l t ra f i l te rs and embeddings of ultra powers. 2.3 Theorem If h : <I,D> ->• <J,E> is a f i l t e r morphism then for any structure lk i f h ,^. : A J / E •* /k1/D i s defined by - 30 -h^A(g/E) = h°g/D ( 1 ) we have (a) h ^ i s an embedding (b) i f h i s 1-1 then h ^ i s an isomorphism. Proof that (a) To see that h ^ i s an embedding suppose Rn " :is an n-ary relation of 7k. Then i f • and R^' are the corresponding relations of lk. /D and /AJ/E respectively we have that <g1/E g n / E > £ T i f f {j : <g x(j) SnQ)> e Rn> e E i f f h - 1 ( { j : < g 1 ( j ) , . . . , g n ( j ) > £ E^}) e D = i f f {i : < g l(h(i)),...,g n(h(i))> e R } e D i f f <h#( g ; L/E) , . . . ,h #(g n/E)> e R^  . By similar arguments we can show that h ^ i s 1-1 and that functions and constants are preserved. (b) If h is 1-1 then every f e A^ " can be written as hog for some g e A^. Hence h^ i s onto, and hence an isomorphism. // (1) We employ the diagram convention for writing compositions of functions: I ^—f J A so h o g ( i ) = g(h(i)) f h°g - 31 -2.4 C o r o l l a r y (a) I f E < D then /AJ/E can be embedded i n /A1/!). (b) I f E « D then /AJ/E = /A^ "/D. Proof This c o r o l l a r y . f o l l o w s from 2.3 once we have proved that for any <I,D> i f X e D /AX/D|V s /kZ/T> . In fact i f we define a map <j> : A X/D| X - AX/D by cj)(f/D|x) = k/D, where k| x = f and k i s a r b i t r a r y on I-X, i t i s not hard to show that <}) i s an isomorphism. // We frequently drop the subscript " /A" from " h ^ " when there can be no confusion. We remark that the maps h ^ are always elementary embeddings. This i s c l e a r from 1.1 i n the case that /A i s a f u l l structure. For the general case note that any structure /A can be expanded to a f u l l structure /A' by addition of new r e l a t i o n s , functions, and constants. Then the argument of 2.3 shows that h ^ A = h ^ , i s an embedding of /A'^/E into /A'^/D, and hence i s an elementary embedding with respect to the language L ^ t - But the language L ^ i s contained i n l ^, so that h ^ i s an elementary embedding with respect to l . This r e s u l t can also be proved d i r e c t l y . /A To what extent are embeddings of the form h^ t y p i c a l among embeddings k : A^/E A^/D ? The following theorem shows - 32 -that i f /A is large enough and has enough relations and functions list e d then, indeed, a l l embeddings are of this form. 2.5 Theorem Suppose that k : /A^ /E ->• /A^ /D is an embedding. Then i f |A| > |J| and fk l i s t s a l l unary relations and unary functions of A then k can be written in the form h^ for some h : I -»• J. Proof Let f e A^ be a 1-1 function and let 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 h(i) = If 1 ( g ( i ) ) i f g(i) e f(J) otherwise # We claim that h(D) = E and that k = h (a) h(D) = E It suffices to prove that f(E) = g(D). Let Y be any subset of A and let P y be a corresponding predicate symbol of L j . Then /AJ/E j= P y(f/E) i f f /A1 /D *= Py(g/D) so {j : /A |= P y(f(j))} e E i f f {i : /A h PY(g(i))}..e D i.e. {j : f(j) e Y} e E i f f {i : g(i) e Y} e D i.e. f _ 1 ( Y ) e E i f f g - 1(Y) e D and hence f(E) = g(D). - 33 -(b) h # = k By part (a) h i s a f i l t e r morphism h : <I,D> <J,E> so by 2.3 : /A^/E •> /A^ /D i s an embedding. C l e a r l y we have it A h (f/E) = k(f/E) = g/D. If t e A i s any unary function of /A and t 1 , t0 are the corresponding functions of IA /E, A /D respec-t i v e l y we have h # ( t 1 ( f / D ) ) = t 2(g/D) k ( t 1 ( f / D ) ) = t 2(g/D) as k and h^ are homomorphisms. Thus h^ and k agree at a l l members of A^/E of the form t^ ( f / E ) for some unary function t ^ of /A^/E. But, i n f a c t , i f £/E i s any element of A^/E we can write SL = f°t A # for some t e A as f i s 1-1. Hence £/E = f o t/E = t 1 ( f / E ) . So h and k agree at a l l arguments i n t h e i r common domain A^/E. // Remarks (i) It i s important to observe i n connection with 2.5 that even i f the embedding k i s an isomorphism onto >h may s t i l l not be 1-1. (Or even "almost" 1-1.) ( i i ) We may c a l l a structure IA that has unary r e l a t i o n s for every subset of i t s underlying set A and unary operations for each function from A to A amongst i t s r e l a t i o n s and operations a f u l l unary structure on A. In p a r t i c u l a r 2.5 applies to a l l f u l l structures /A. - 34 -2.6 Corol l a r y Let A be a f u l l unary structure and l e t <I,D>, <J,E> be such that | j | < |A| then /A1/!) = /AJ/E i f f D ~ E. Proof 2.4(b) gives us h a l f the r e s u l t . The converse d i r e c t i o n follows from 2.5 and 2.2(b). // We can also make the observation that i f /A i s f u l l unary and |J| ^  |A| then any embedding of (A2/E into an ultrapower /A^ /D i s n e c e s s a r i l y elementary, and i s possible i f f E < D. This i s a consequence of 2.5, 2.4(a), and the fact that a l l the embeddings J h ^ are elementary. The following example shows that the c a r d i n a l i t y r e s t r i c t i o n i n 2.6 cannot be removed. 2.7 Theorem (GCH) Let /A be any structure on A. Then we can f i n d <I,D>, <J,E> (a) such that |I| = |J| = |A|+ /A1 IT) = /AJ/E E ^ D (b) such that |I| = |J| = |A|+ /AJ/E -< /A1/!) E i D. - 35 -Proof (Informal) Let K = |l|. K e i s l e r i n [9] and [10] has investigated a class 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 results that we s h a l l need about these u l t r a f i l t e r s are the following: 2K + (1) There are 2 K -good u l t r a f i l t e r s on I. (2) I f /A i s a structure 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 structure. (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 exist 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 A I l A l + + I f IA i s any structure on A then |L^| < 2 < 2 = K so that /A^ /D and /A^ /E are saturated structures of c a r d i n a l i t y K +. So fk1 I'D = f^/E by 1.2(a). (b) Let <I,D> be as i n (a). There are 2 u l t r a f i l t e r s 2K 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 /A1/!), by 1.2(b). // We mention the following consequence of 2.6 and 2.7: For any f u l l structure A we can find <I,D>, <J,E> such that AX/D = 7AJ/E but ( /AV/D r ( /A A) J/E A A where Ik i s a f u l l structure on A . I t i s l i k e l y that this can be proved without the assumption df the GCH. - 36 -Theorem 2.7, in contrast with earlier results, shows up a strong distinction 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 latter kind have a simple characterization. 2.8 Theorem (Adler) Let /A be a f u l l unary structure on A. Then /A^ /D is generated by a single element i f f A^/D = /A^ /E for some <J,E> with |J| < |A|. Proof. (a) <= We can assume |'I| ^  |A| . Let f : I ->• A be any 1-1 function. We claim that f/D generates A^/D. For let g/D be any member of A^/D. Then there is a function t : A A such that g = f°t. But as fk is f u l l unary there i s a function symbol t in L ^  corresponding to t. Then i f t^ i s the interpretation of _t in A^/D we have g/D = fot/D = t ^ f / D ) . Hence {f/D} is a set that generates A^/D. (b) => Given f/D e A^/D, consider the set {g/D : g/D = t 1(f/D) for some t e AA} = S (using the notation of part (a)). As lk is f u l l unary i t is easy to see that S is closed under the functions of F ^  and is hence the set generated by {f/D}. Now assume that f/D generates A^/D. Then - 37 -S = A^/D and each member of A^/D can be written i n the form t 1 ( f / D ) = f o t / D * A A for some t e A . Consider the embedding it A I f : /A /E -> /A /D where E = f(D). By d e f i n i t i o n ( c f . 2.3) the range of f ^ consists of a l l elements i n A^/D of form # A f (t/E) = fot/D for some t e A . # A ~ I So f i s i n fact onto and hence Ik /E = Ik /D. Remark In any ultrapower /A^ /D i f T i s a unary predicate symb of L ^ corresponding to X c A we have Ik1 ID »= T x ( f / D ) i f f X e f(D) i . e . f(D) i s the " u l t r a f i l t e r of pro p e r t i e s " of f/D. Thus i f | l | < |A| we see by the above that i f Ik i s f u l l unary, /A^ /D i s generated by f/D where f i s 1-1. In t h i s case D f(D) so that we can i n t e r p r e t D as being equivalent to the u l t r a f i l t e r of properties of a generating element. - 38 -B. Images of U l t r a f i l t e r s In t h i s section we c o l l e c t and prove r e s u l t s about u l t r a f i l t e r s and f i l t e r morphisms. In p a r t i c u l a r we study the c o l l e c t i o n of images of a given u l t r a f i l t e r . 2.9 D e f i n i t i o n s (a) a(D) d = f {th(E) : E < D} We c a l l a(D) the shadow of D. It i s the c o l l e c t i o n of cardinals a such that D has a uniform u l t r a f i l t e r on a as an image. (b) An u l t r a f i l t e r D i s a-descendingly incomplete (a-d.i.) i f there e x i s t s a sequence <X^  : n < a> of members of D such that n' < n < a implies , £ X^ and such that n"fX^ : n < a} = 0. Such a sequence we. w i l l c a l l an a-chain i n D. Descendingly incomplete u l t r a f i l t e r s were f i r s t studied by C. C. Chang i n [6]. A l l OJ-incomplete u l t r a f i l t e r s are c o - d . i . , i n fact an u l t r a f i l t e r D i s a-incomplete i f f D i s O J - d . i . for some 8 such that U) < 8 ^  Oi. Here the proof i n the " i f " d i r e c t i o n i s c l e a r . To see "only i f " suppose that D i s a-incomplete for some a > co. Then there i s a c o l l e c t i o n {X^ : n < a} £ D such that n{X^ : n < a} I D. Define sets Y i n d u c t i v e l y so that Y Q = X Q, = Y „ n x a n d Y, = n{Y : i] < A} i f A i s a l i m i t o r d i n a l , ryrl M i l A r) Let u be the least o r d i n a l such that Y^ i D. Then i t i s clear that u i s a l i m i t o r d i n a l £ a. So for some ca r d i n a l S such that - 39 -Ui < & < a there i s a sequence of ordinals <n^ : E, < g> that is cofinal with y. It is easy to see that <(Y -Y ) : £ < 8> is a 8-chain in rij- y D. 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 "in what way" D is incomplete. We also make the observation here that i f D is a-d.i. and 8 is cofinal with a then D is a-d.i. Thus D is 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 is 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 in f i n i t e cardinal. Then a e a(D) i f f D is a-d.i. Proof (i) Assume a e a(D). Then there is a pair <J,E> such that E < D and th(E) = a. We 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> is an a-chain in E. But then n <f "'"(X ) : 11 < a> is an a-chain in D, so that D is a-d.i. ( i i ) Assume D is a-d.i., and let <X^  : n < a> be an a-chain in D. 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 is uniform (i.e. th(E) = a) i f a is regular. Suppose that Y e a and |Y| < a. Then by regularity of a there is anil < a such that Y £ n_. But then - 40 -f x(Y) c f - 1 ^ ) £ i - x n + 1 so that f "*"(Y) i D and hence Y I 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 . i f f c f ( a ) £ a ( D ) . // Notice that (i) does not use the regularity of a so that for every a a e a ( D ) implies D is a - d . i . Also the proof of (i) shows that i f E is a uniform u l t r a f i l t e r on J then | j | e a(E) and E is |J|-d.i. For a l l < I , D > we have by definition 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 restraint c r ( D ) can be large. 2.12 Theorem For any set I there is 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 shall define a sequence < D ^ : n e On> of u l t r a f i l t e r s with the following properties: i) i s a uniform u l t r a f i l t e r on to^  i i ) n 1 ^ n implies D ^ , < - 41 -The construction i s by induction. Let DQ be any uniform 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 for 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 consider the u l t r a f i l t e r D ^ X F on ^ g x ^ . It is easy to see that i f E ^ then E < D ^ X F , S O i f we define D on o o ^ by = cj)(DgXF) where (j) : W g X o ) ^ -* o^ is 1-1 onto then = D^xF and satisfies (i) and ( i i ) (with n = X). Case 2. X is a limit ordinal. Let F be an u l t r a f i l t e r on X which extends the collection of sets {Cj. : £ < X} where C» = {n : E, < r\ < X}. Let D' be an u l t r a f i l t e r on 0)^ x {n} = I isomorphic to and consider the u l t r a f i l t e r D' = O D ' : r) < X} on u{l : n < X} = I'. We claim t T\ r) D < 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. <. for n < £ < X. For each such E, let f r : I_ I be such that f>-(Dl) = D' , and let f : I 1 -* I be such that f| = f r . (It is immaterial how f is defined on u{l' : 1, < n}.) Then f(D') = D', for i f X c I then £ n. ~ n f _ 1 ( X ) = u{f _ 1(X) : E, < X}. If X e D j then f^Cx) e D£ for a l l E, such that X] < E, < X so that f _ 1 ( X ) e D', and i f X i i t follows in the same way that f ^(X) i D'. A l l this is by definition of D' and the fact that C^ e F. - 42 -Now I' = to, and as n < X implies D < D' we have that 1 A n th(D') > OJ for a l l r\ < X, and so th(D') = OJ. . n A Finally we define to be an u l t r a f i l t e r isomorphic to D' on OJ^. It is clear that has the required properties. // If an u l t r a f i l t e r D is regular then D is a-d.i. for a l l a such that < a < | l | . This follows from lemma 2.2 of [12] which essentially observes that i f .X is regular and <X^  : ri<A> is a K-covering of I by elements of _D'where K < X, then"fSY^ y:-qf < A> is^a .A-chain in D where = u{X^ : n < £ < A}. This observation can be easily 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 is regular then a e a(D) for a l l regular a such that OJ < a < 111 . It is 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. In fact we have the following result. 2.13 Theorem Let D and E be any u l t r a f i l t e r s and 8 any cardinal. Then DxE is B-d.i. i f f either D or E is 8-d.i. Proof Suppose <X^  : n < 8> is a 8-chain in D: then <X^  x J : n < 8> is a 8 -chain in DxE. Similarly i f <Y^  : n < 8> i s a B"" c n ain in E then <I x Y : n < 8> is a 8-chain in DxE. - 43 -Conversely, suppose that <Z^  : n < B> is a 8-chain in DxE then for a l l n < U = {j : {i : <i,j> e Z } e D} e E. If U = n{U : n < 8 ) = 0 then we have that <U : n < 8> i n r) a 8-chain in E. Otherwise we have that for a l l j £ U = {i : <i,j> e Z^ } £ D (n < 3). Pick any j £ U, then <V^  : n < 8 > is clearly 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 <VJ : n < 8 > is a 8-chain in D. n By the same methods we can show that £<D. : i £ J> is E 3 8 - d . i . i f f either E is 8 - d . i . or D. is B-d.i. for almost a l l 3 j £ J (mod E) . We define the spread of an element f/D of an ultrapower AI/D by spread (f/D) = min{|range(f')| : f' ~ D f ) With this definition we can generalise 1.11. Note that the canonical embedding i : A—^A^/D is 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 | i f f 8 e 0(B). - 44 -Proof Suppose that f/D e A^D and spread (f/D) = 8. We can assume that |range(f)| = 8. Let E = f(D). Clearly th(E) < 8. If th(E) < 6 there is an X e E such that |X| < 6, f _ 1 (X ) e D. Pick X Q e X and define f ' : I -»• A by ff(i) i f i e f _ 1 (X ) f ( i ) = / ( J X Q otherwise Then f ~ Q f but |range(f')| < 8 a contradiction, so that th(E) = 8-Conversely suppose 8 e c(D). Then i f 8 < |A| we can find E on A and g : I 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. ( i i ) spread (g/D) > 8 for , as in 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 . Our result 2.12 shows that any set of the form { 8 : 8 = 1 or 0) < 8 ^ ot} can be so expressed. We also must require of any set S that is a shadow that a e S implies cf(a) e S. Another condition on shadows is 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 is regular, then D is K - d . i . - 45 -(b) If D is K - d . i . and y = cf(<) < K then either D is y-d.i. or for some 8 < K D is y-d.i. for a l l regular y such that 8 < y < K . Chang's proof of this result uses the G.C.H. but subsequent proofs of the result by Kunen and Prikry in [12] are free of this hypothesis. We w i l l now give the proof of Prikry that appeared in [12] of a result slightly stronger than Chang's Theorem. Firs t we need a combinatorial lemma from Ulam [17]. 2.15 Lemma Let X be any in f i n i t e cardinal. Then there is an array <A^  : a < X, n < X+> of subsets of X + with the following properties: (i) a 4 a' implies A^ j n A^, =0 ( i i ) n 4 n' implies A^ n A^ =0 ( i i i ) |X+ - {An : p < X}| < X P for every n < X+. Proof For every E, < X + let <a^ : p < £> be a sequence of distinct elements of X. Take A - {£ e X : a = a}, then i t i s clear that a TI (i) and ( i i ) are satisfied. To see that ( i i i ) holds notice that i f £ e X - u{Ap : p < X} then or is not defined, so that £ < n. Hence |X +-u{A n : p < X}|< |n| < X. // - 46 -We can regard t h i s array as a XxX matrix with set e n t r i e s . %+ > 1 - A Then each row and each column forms a pairwise d i s j o i n t + + c o l l e c t i o n of subsets of X , and the columns, i n f a c t , p a r t i t i o n X except for a set of c a r d i n a l i t y at most X . These and s i m i l a r arrays are c a l l e d Ulam matrices. 2.16 Theorem (Prikry) Suppose D i s X + - d . i . , then e i t h e r (i) D i s c f ( X ) - d . i . or ( i i ) there i s a regular c a r d i n a l a < X such that D i s ( a , X + ) - r e g u l a r . Proof Let <A^ : a < X , n < A + > be the Ulam matrix of 2.15. Set B n = u{A n : p < a} , a P We claim that S £ X + , 0 < X and |s| > \a\ implies (*) n{B^ : I e s} = 0 For suppose that T e ^{B^ : £ e S}. Then for each £ e S there i s r a p r < a such that T e A . - 47 -Since | s | > \a\ there are £, n e S such that £ 4 r\ and p r = p so that x e n A1"1 in contradiction to 2.15(H). Thus the claim (*) i s verified. + + Let D be X - d . i . , then since A e a(D) D has an image D' = f(D) on A + that is uniform. Since any a-chain or a-covering we may find in D' can be l i f t e d via f 1 to D we can start off by 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 + a l l i D (a < A). If Y = A + - u{A^ : p < A} = A + - U{BJJ : a < A} then Y I D as |Y| < A, If we set X = A + - (Y u BN) a a then <X : a < A> is a A-chain in D and hence D i s A-d.i. and a consequently cf(A)-d.i. Case II Case I f a i l s . Then for each n < A + there is a o"^  < A such that B1"1 e D. Then there i s a T c A + and a O < A such that |T| = A + and O = C for a l l n e T. Then by the claim (*) proved above <B^  : r) e T> is a |a| +-covering of A + by members of D. So D is (a,A +)-regular where - 48 -In view of the remarks following the result 2.12 on the construction of chains from coverings i t is clear that 2.16 implies Chang's Theorem. We w i l l be proving additional results on the form of shadows 0"(D) later in Chapter 4. C. The Ultrapower as an Ordered Set We consider now the situation in which the structure Ik has no operations or constants but merely a single binary relation RQ, where RQ is a linear ordering relation. We shall write < for RQ and <A, < ^  for Ik. The relation < on A induces a relation <' on A^/D given by f/D <* g/D i f f f ( i ) < g(i) for almost a l l i (mod D). We can see either directly or from Los' Theorem that <' is a linear ordering. If A is i n f i n i t e and < is a well-ordering of A i t is not hard to see that <' is a well-ordering i f f D i s oj-complete. This fact i s proved in [4], p. 134. The following theorem was suggested by ideas of Keisler [8], p.405, and shows the connection between <' and the descending in completeness properties of D. Chang quotes similar results of Keisler in his paper [6]. Recall that l : A A^/D is the canonical embedding. 2.17 Theorem Let A be well-ordered by < in type |A| = a. Then \(A) is confinal in A^/D (w.r.t. <') i f f D is not a-d.i. - 49 -Proof (a) Assume that \ (A) i s bounded i n A^/D by some element f/D. We w i l l show that D i s a-d.i. Let {a^ : n < a} be the elements of A as well-ordered by <. Then i (A) = (g^/D : n<a} where g^d) = a^ for a l l i e I, n < a . Now for a l l n < a we have g/D <* f/D. So = {i : a^ < f ( i ) } e D and i t i s clear that <X : n < a> i s an a-chain i n D. n (b) -»-. Suppose that <Y^ : n < a> i s a chain i n D. Define f : I ->• A so that f ( i ) = a ,, whenever n+i i e Y - Y . n n+1 I t i s easy to see that f/D i s an upper bound for \(A) i n A I/D. // We w i l l often drop some formality and regard r e s u l t s l i k e the above as pertaining to ultrapowers of ca r d i n a l s . Thus we w i l l say: "a i s c o n f i n a l i n a^/D i f f D i s not a - d . i . " (The embedding and orderings being understood.) Each member f/D of a^/D determines an i n i t i a l segment [f/D] = {g/Dec^/D : g/D<' f/D}. There i s a natural map of the ultraproduct II<n^ : ieI>/D into a^/D induced by the i n c l u s i o n map J_ : n<n i : i e I> + a 1 where n. = f ( I ) 1 - 50 -It i s easy to see that ^ i s well-defined, 1-1, and that i t s range i s [f/D]. Thus we can pass f r e e l y between ultraproducts and i n i t i a l segments of ultrapowers. Notice, though, that one i n i t i a l segment corresponds to many ( c l o s e l y related) ultraproducts. We now prove a s l i g h t l y less t r i v i a l r e s u l t which connects the r e g u l a r i t y properties of an u l t r a f i l t e r to the order properties of an ultrapower. 2.18 Theorem Let A be a regular c a r d i n a l , D a uniform u l t r a f i l t e r on A +. + A + • Then every set of ^ A elements of A /D i s bounded above 4-i n A /D i f f D i s (A,A )-regular. Proof We w i l l be using the Ulam matrix <A^ : a<A, n<A+> of 2.15 and the sets B^  of 2.16. We employ a case d i v i s i o n s l i g h t l y d i f f e r e n t from 2.16. Case (I) of 2.16 asserts that there e x i s t s a column, say the column of the Ulam matrix for which B^  i D for a l l a < A. In fact we w i l l assume for our Case I* that there e x i s t A"^  such columns, i . e . there i s a subset S £ A + such that |s| = A + and B^  I D for a l l n e S, O < A. We can s t i l l recover the conclusion of Case II from Case I I * = not Case I*. For i f (II*) applies there are at most A columns with the p e c u l i a r i t y described above. These can be deleted from the matrix to form a new matrix to which the argument of (II) applies. - 51. -+ X + (i) Assume that any set of X members of X /D is bounded above. If Case II* holds we can conclude as in 2.16 that D is (a +,X +)-regular for some a < X and so that D is (X,X )-regular. If Case I* holds there i s S £ X + such that |S| = X + and I D for a l l n e S and a l l a < X. We define functions {fc : E e S} £ X by fp i f i e (.0 i f i e X + - u{A^ p < X} P x + Let g/D be an upper bound in X /D for the set {f /D : £€S}. Then we have X ? = {i : 0 < fg(i) < g(i)} e D. E E' But i f p = fg(i) = f ^ i ( i ) > 0 then i e A^ n A^ and so £ = £'by 2.15(ii). Hence no two f's take the same positive value at i , for any i £ X +. Hence \{E_ : i e X ?} | < |g(i)| < X so that {Xg : E e S} is a X-covering of X + by members of D, and D is (X,X +)-regular. ( i i ) Assume that D i s (X,X )-regular and that + + X + {f^/D : ri <X } is any set of X elements of X /D. Let {X : n < X } be a X-c overing of X by members of D. - 52 -Define f f n ( i ) 1 e x n g n ( i ) = f 10 otherwise then ~p and as |{n : i e X^}| < A and A is regular we have that sup {g^U) : n < A + } exists, and is less than A. We denote this sup by g ( i ) . Then we can show easily that g/D is an upper bound for {g /D : n<A } = {fn/D : n<A+}. / / Remarks (A) We used the assumption that A was regular only in section ( i i ) of the proof. An inspection of this section shows that for a l l A we have the implications: (1) D is (cf ( A ) , A +)-regular implies-(2) Every subset of A'*1 /D of power < A + is bounded above in A /D implies (3) D is (A ,A + )-regular. (B) We have shown in 2.7 that i t may be true that / A A / D = / A A /E , where fk = < A , <^ and | A | = A , but that D ^  E. Notwithstanding this negative result we see by 2.18 that D and E have this much in common: D is (A ,A + )-regular i f f E i s . - 53 -D . Shadow and Cardinality, I Many cardinality questions can be settled when the shadow a ( D ) of an u l t r a f i l t e r D is known. For example i f D is an u l t r a f i l t e r on I and cf(y) e a ( D ) we have (*) I-C^/DI7 < | ( a ( Y ) ) I / D | . This follows from Keisler's Lemma (1.16) as follows: Let X = {X^  : n < y} be a y-chain in D . Then Y £ = Hn : i e X N > | < y for a l l i £ I, so that X is a y _covering and we may apply 1.16 with K = A = y. Thus Y . | a I / D | Y < |n<a 1 : i e I> / D | < | l l < a ^ : i £ I> / D | = | ( a ( Y V / D | as = sup {a^ : u < y} > a 1 for a l l i e I. So (*) holds. Putting y = w we see that (*) generalises 1.14 ( f ) . If G.C.H. holds we have the following consequence of (*): 2.19 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 I / D | > | A | - 54 -Proof ( i i ) cf(|A I/D|) > | A | (a) The GCH implies that a = a so that i f we take y = a i n (*) we have that |aI/D|a = | otX/D | But i t i s well-known from set theory that under GCH 3 a = 8 i f f a < cf(8) . So that we can conclude i i ) c f d A 1 / ! ) ! ) > | A | , from which i ) follows. // However we can prove a fragment of t h i s r e s u l t without the use of GCH by the following argument: 2.20 Theorem Let D be an u l t r a f i l t e r on I. Then | A | e cr(D) implies | A I / D | > | A | . Proof I f | A | e a ( D ) then D has a uniform image E on A. Suppose E = h ( D ) for some h : I -> A. But then hif : A A / E -> A I / D i s 1-1, and we know by 1.14(b) that | A A / E | > | A | . Consequently I A V D I > | A | . / / Later we s h a l l prove a converse to t h i s theorem i n the case where | A | i s regular. The proof of the converse given employs GCH. - 55 -E. Categorical Formulation Here we indicate briefly an interpretation of the main (1) The category PAIRS is 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 relational structure /A we have the category MODELS OF /k whose objects are a l l relational structures (B of the same type as fk and such that JB = /A,and whose morphisms are the elementary embeddings (J) : -> IB'2 • (3) The category ULTRAPOWERS of /k is 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 ,A : PAIRS ->- ULTRAPOWERS OF /A Ik such that i f <I,D> is an object of PAIRS then ideas of this chapter in terms of category theory. F /A(<I,D>) = /k1/!) and i f h e Horn (<I,D>, <J,E>) then = t i / A e Hom(/AJ/E, /A^/D). (4) Let 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. The functor ft ft F .. : PAIRS •> ULTRAPOWERS OF /A Ik is defined in the obvious manner. ft (5) For each set I, we define I-PAIRS and I-ULTRAPOWERS * OF A to be the f u l l subcategories of PAIRS and ULTRAFILTERS OF /A formed by looking only at ultra-f i l t e r s on the set I. Then these are small categories ft and i t can be shown that F ,, restricts to a functor-/A from I-PAIRS* to I-ULTRAPOWERS OF Ik that is an isomorphism of categories when | l | < |A| and fk is a f u l l unary structure. Note on Authorship in Chapter 2 Much of Section A is well-known, in particular 2.1 which appears in Booth [5]. Theorem 2.2 is also in [5], but here the generalisation to uncountable index sets is slightly less t r i v i a l . Theorem 2.5 is a joint result of A. Adler and the writer. Theorem 2.7 is 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 certainly been touched upon by some authors in the course of a proof. - 5 7 -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 in Chapters 3 and 4 where no explicit ascription is given, are due to the writer. CHAPTER 3 REDUCTION OF INDEX SIZE In Chapter 2 we have already noted a connection between the s t r u c t u r a l properties of ultrapowers A^/D and the c a r d i n a l i t y of the index set I. For example we have the theorem that i f A i s a f u l l structure A^/D i s generated by a sing l e element i f f AI/D £ A J/E for some <J,E> such that |J| < |A|. In f a c t , i f we examine the proof of t h i s r e s u l t , we see that t h i s isomorphism 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 that the induced embedding b/ : A J/E -*• A^/D turns out to be onto. In t h i s chapter we w i l l prove various r e s u l t s involving the construction of isomorphisms of t h i s kind. We w i l l show, roughly, that i f an ultrapower /A^ /D i s "small" compared with I then an isomorphic ultrapower A^/E e x i s t s with | j | < | l | . I f the u l t r a f i l t e r D i s uniform on I one might expect that t h i s s i t u a t i o n cannot a r i s e - however we w i l l show i n Chapter 4 that t h i s can happen i f | l | i s measurable. A. When h i s onto I f f i s a function with domain I we l e t be the equivalence r e l a t i o n on I given 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 equivalence r e l a t i o n II^ with the - 58 -- 59 -partition of I i f induces. Thus we speak of the partition [ f = (f : j e range(f)}, 3.1 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 ^  is onto. (b) for each f e A 1 there is an f' e A1 such that f ~ f and f is constant on each c e l l of TI, . D h (c) i f Ij = h ^(j) for each j e J and {i^ : n < a} is any partition of I (j £ J), where a ^  |A|, then there i s a sequence <n_. : j e J> such that u{l. J : j e j} e D. 3 Proof As range(h^) = {h°g/D : geA^} and a function from I to A is constant on each c e l l of TL^  i f f i t can be written as h°g for some geA'"" i t i s clear that (a) and (b) are equivalent. Now well-order A as {a^ : ri < |A|}. If (b) holds and ' {ij : n < a} (j e J) is a system of partitions as in (c), let f : I A be defined by f( i ) = a^ i f i e i l 1 We w i l l speak of the members of partitions' as cells. - 60 -for some j e J . Let f be a function constant on each c e l l of II, and such h that f ~ D f. For each j e J l e t K. = {i : f ( i ) = f ' ( i ) } n I.. P Then i t i s easy to see that either K. = 0 or K. = I? for some n. 2 3 3 E < a. I f K. = i A otherwise set n. = 0. Then 3 3 3 u{l..J : j . e J} a {i : f ( i ) = f ' ( i ) } e D and so (c) holds. This argument reverses without great d i f f i c u l t y to show that (c) implies (b). // 3.2 Theorem (A. Adler) Let /A^ /D = B be any ultrapower of A. Then there i s an image E = h(D) of D on the set J = A B such that h # : /AJ/E -*• A I /D i s an isomorphism. Proof Select a representative f^ from each ~ ^ - c l a s s b e B. Define a p a r t i t i o n II of I by set t i n g i l l i ' i f f f ^ ( i ) = f ^ ^ ' ^ ^ o r a ^ b £ B. Then IT has at most A c e l l s . In fac t II = IL where h h : I ->• A i s given by h( i ) ( b ) = f b ( i ) ( i e I, b e B) . If f £ A 1 then for some b e B (in fac t for b = f/D) we have f ~ f, . But f t i s c l e a r l y constant on the c e l l s of II, so the D b b J h r e s u l t follows by 3.1. // - 61 -The r e s u l t 3.2 t e l l s us that, up to isomorphism, an ultrapower IB of A can always be taken to have index s i z e l e s s than or equal to |A |. I f [Bj i s regular we can do better (with a l i t t l e help from the GCH). 3.3 Theorem (GCH) Let Ik1 IT) = B be an ultrapower of /A. I f |B| i s regular then there i s an image E = h(E) of D on a set J such that | j | ^  |B| and h^ : /A^/E -*• Ik^/T) i s an isomorphism. Proof ,B By 3.2 there i s an image E^ = h^(D) of D on = A such that h^ i s an isomorphism. (1) I f E^ i s not uniform we can fi n d J e E^ such that |J| £ |B| because the GCH and the fact that |B| > |A| imply that | j | = JA | = |B| . Then i f : J -> J i s any map that extends the i d e n t i t y on J we have h2 (V " E l l j -(2) Consider, now, the case that E^ i s uniform on J^. Then, by the observation following 2.11, we have that E^ i s |B| +-d.i., and hence by Chang's Theorem, that E 1 i s |B|-d.±-Let <X : n < |B|> be a IB|-chain i n E. and l e t <fF|/D : T)<|B|> be a well-ordering of A /E^. Select a e A. - 62 -For each n < | B | define ~ Q T by g n ( D = r f n ( i ) i f i e X n i f i e J, - X 1 n The partition II is defined by i l l i ' i f f g^Ci) = g^Ci') for a l l n < | B | . The subset X - X ,. of J . is 1 1 n n+1 1 broken up by II into at most \&^\ pieces. So |llj , the number of cells of I, is at most Z{|An| : n < | B | } but as |A| < | B | and by the GCH we have that |An| < | B | for a l l n < | B | . Hence |n| < | B | . So we can write II = II, where h„ : J. J is a h 2 2 1 function with range J such that | j | £ |BJ _ As each g is constant on each c e l l of TL we have 11 J 2 # J 1 by 3.1 that : IA /E ->- /A /E^ is an isomorphism where E = h2(E.^). In case (1) also i t is clear that h 2 is an isomorphism. ( c f . proof of 2.4.) In either case i f we take h = h^°h 2 we have E = h(D) and that h # = h*°h* : /AJ/E + /A1 /D is an isomorphism. // - 63 -B . Transcendence Degree of an Ultrapower We have three correlated scales for measuring the "size" of an ultrapower IB = / A V D : (a) the cardinality of B (b) the smallest number | j | such that there is an u l t r a f i l t e r E on J with / A ^ / E = B (c) the smallest cardinal number |x| where X generates I B . The results of section A concerned the relationship of (b) to (a). Hence we consider the relationship of (c) to (a). 3.4 Definition The degree of a relational structure IB is the smallest cardinal 8 such that there exists a set {b^ : n, < 8} which generates B. If B = A , where A is a f u l l structure, then there is a natural embedding of A into IB that sends an element a e A to the element of B with the same name. Thus we can regard B as an extension of A . If the degree of B is zero then i t isn't hard to see that the embedding is onto and hence |B is isomorphic to A . If the degree of B is one then IB can be generated from A with the adjunction of a single element. If a subset X of B generates X' in B, where IB = <B,R,F,C> and B = A , A being a f u l l structure, then X' consists of a l l elements of the form (b^,b2,...,b^) where F^ e range (F) and b^,b2j.--,bn € X u range(C). To see this notice that a l l such elements clearly belong to X' and that the set of a l l such elements is closed under the application of functions from range(F). This is because range(F .) - 64 -is closed under composition by the full-ness of A and hence as IB = A. we have that range (F ) = range(F) is closed under composition. More generally, with no assumptions on IB we can write X' as the set of a l l elements "Kb^ t>n), where b^,...,bn e range(C) u X and i> is a composition of members of range (F). It follows from these observations that i f X is 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 ) ) , and the set of f i n i t e sequences from X u range(C) has cardinality max(B,Y)- If IB = A and A is a f u l l structure then K = | A | , Y = | A | , so that we have 3.5 Theorem If IB i s of degree 8 and IB =..- A where A is a f u l l ft I I i A i A structure then 8 ^ |B| ^ max(3, | A | , c o ) . Consequently i f |B| > I A |, co then 8 = |B|. / / So, with large models of T ^ , degree coincides with cardinality. Generalising the proof of 3.2 we prove: or any structure with |L | = |AA| - 65 -3.6 Theorem Let lk be any structure and let (B = A^ /D have degree 8 • Then there i s an image E = h(D) of D on A such that h : lk /E -»- /A /D is an isomorphism. Proof (Outline) Let (f^/D : T) < 3} generate B. A partition II of I is defined by i l l i ' i f f f^ ( i ) = f n ( i ' ) for a l l n < 6. | TI | = |A^ | , 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 ( i ) , f n <D) ' l '2 n A n for some n ^ , r)^, . . . » r) < 8 and e A . These functions k are a l l constant on the cells of II, so the natural embedding # A g I h1t : /A /E -> /k/D is onto. // For the remainder of this section we w i l l assume that lk is 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 If |B has degree 8 < cf(|A j) then |A | = |A| and so by ~ A 3.6 IB = /A /E for some u l t r a f i l t e r E on A. But then by 2.8 we have 3*1. // - 66 -Note that GCH is not needed i f we replace cf(|A|) by cf*(|A j) where c f * ( K ) = min {a : K 0 1 > K } . 3.8 Corollary (GCH) If | A | i s regular then the ultrapower IB = /A1 /D has degree either 0, 1 or | B | . Proof (Outline) Let B have degree 8, where 8 < | B | . Then by 3.5 8 < |AA| and so by GCH B £ | A|. If B < |A| then 8 £ 1 by 3.7, so we can assume 8 = |A|. By 3.6 we can take |I| to be |AA| =|A|+. An argument which combines the techniques of 3.6 and 3.3 shows that iB = 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 possibility that B = | A | . / / Thus, under the GCH, an ultrapower B of A can have degree s t r i c t l y between 1 and | B | only i f | A | is singular and cf(|A|) S S < | A | . Whether this state of affairs can occur is an open question. - 67 -C. Ultrapowers that are Direct Limits Since so many cases are known of ultrapowers /A^/D where |A I/D| = | A 1 | , i t might be conjectured that i f the GCH holds and | A | < | A J / E | = y + then /A J/E = /A^D for some <I,D> such that | l | = y. That is "most" ultrapowers are isomorphic to an ultrapower of "proper" index size. We have come close to such a result in section A of this chapter, except that an application of 3.3 w i l l yield only a pair <K,F> such that A J/E = / / F and | K | = y+. In this section we w i l l show that i f y is regular then | A^/E| < y+ i f f /A^/E can be expressed as a direct limit of ultra-powers of index size y» over a well-ordered set of length y+. A partition II of the index set I of an ultrapower /A^/D determines an elementary substructure <E of /A*~/D where f/D e C i f f f ~ g, g being constant on each c e l l of II. We have used this fact to construct ispmerphisms and embeddings in Chapter 2 and in sections A and B of this chapter. More generally i f we have a set (P of partitions of I we can define a subset of A^/D by f/D e Qp i f f f ~p g where g is constant on the cells of some II e (p . 3.8 Lemma Let A be any structure, then the structure /A^/D]^ = Q is a substructure of /A1/D i f for every f i n i t e collection {II^jII^,.. . ,11^ } of partitions from (P there is a partition II e (p and a set D such that i f i , i ' e X then i H i ' implies 1 ^ 1 ' for a l l k, - 68 -Proof Assume that /P has the stated property. We w i l l show that Q^ p i s closed under the a p p l i c a t i o n of functions and constants of /A/D = ( A / D , R*, F*, C*). It i s easy to see that range (C*) c Q Now suppose that f^/D, r n / ^ e Q<p > where f ^ i s constant on each c e l l of 11^  e (y, and that F^ e range (F*) i s an n-ary function of A*/D. We have F*(f 1/D,...,f n/D) = g/D where g i s given by g ( i ) = .F^ ( f ^ d ) f n ( i ) ) ( i e I) , F^ being the function of /A corresponding to F . Let II and X have the properties of the statement of the lemma and define g' e A"*" by g'( i ) = i e X i i X where a^ i s a f i x e d element of A. Then g' i s constant on each c e l l of n-and g' ~ g so g/D = g'/D e Q // I f D i s an u l t r a f i l t e r on I we s h a l l c a l l a set (P of p a r t i t i o n s of I D-directed i f for every f i n i t e subset {Tl^,J[^, . . . ,Jl^} of (P there i s II e P and X e D such that i f i , i ' e X, then i l l i ' implies i n^i' for a l l k = l,2,...,n. Less formally we s h a l l say i n t h i s s i t u a t i o n that II r e f i n e s each 11^  almost everywhere. The substructures of ultrapowers given by D-directed sets of p a r t i t i o n s are p r e c i s e l y the structures that K e i s l e r [8] c a l l s l i m i t ultrapowers. K e i s l e r works with f i l t e r s of equivalence r e l a t i o n s - 69 -rather than with D-directed sets of partitions. We feel that presentation of limit ultrapowers by means of sets of partitions has the advantage of throwing attention on the natural embeddings of ultrapowers into limit ultrapowers. This is made explicit by the following lemma which relates to the situation we shall be interested in, namely, ultrapowers that are direct limits over a well-ordered set. The lemma has a functorial character which makes possible easy generalisations. 3.9 Lemma Let /A^ /D be an ultrapower of the structure /A. Suppose we have a sequence <II : n < y> of partitions of I such that (a) each function f e A 1 is ^ -equivalent 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 is a sequence of ultrapowers <A ^ /D^  : H < Y> and families of maps h : I -> I (r| < Y ) h , : I -* I , (n' < n < Y) nn n n' ' T I such that Hk /D is the direct limit of the sequence <lk ^ /D^  : H<Y > via the embeddings h* : /AIn/Dn AT/D A N D 1 , 1 h # , : Ik n'/D , •* IA n/D ( n ' < n < Y)-nn n - 70 -Proof Let the sets {i^} be chosen to index the partitions, thus let II = { a 1 ? : j e I } for a l l n < Y. The functions h : I I are defined by h (i) = j i f f i e a 1 ] and we take D = h (D) . We now define the functions h^ , : I I , n n nn n n By hypothesis IT refines IT , on a set X = X (n,n' ) belonging to D. We w i l l take h ,(i) = i ' i f nn a n n X c a?,' n X . - 1 This gives i ' uniquely from i so long as n X 4 0. But {i e I : a 1 ? n X = 0} I D as h r i 1 ( { i e l r i : cr?nX=0}) c I - X I D. So that h , has been defined for almost a l l i e I (mod D ). Define nn' n the remaining values of h , arbitrarily. nn It follows that the diagram - 71 -n' < n. < Y commutes on a set in D. From this i t is easy to see that h , = h i 0 h and that h „ = h , „ ° h ,• n' nn' n nn n n nn Finally let iB be any structure for which there exist embeddings k : A YD •* n n n < y such that k^, = h^^, o for a l l n1 < D < y. Then we define an embedding k : A/D + as follows: i f f/D e A/D then there is n < y so that f is ~ D~equivalent 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 11/D such that f/D = h (f /D ). n n n n n n We. set k(f/D) = k (f /D ). r r iy n This definition of k(f/D) is independent of which is chosen as i f f/D = h^,(f^,/D^,) where n1 < r\ then i t is easy to see that f/D = h* ,(f ,/D ,) and so n n nn n n - 72 -k ,(f ,/D ,) = h* , ° k (f ,/D ,) n n n nn n n n = k (h* ,(f ,/D ,)) n nn n n = k (f /D ) n n n l 2 Also k is 1-1 as i f f/D 4 f /D then for some n > Y there exist fVD , f2/D such that f i/D ^ f 2/D and f 1/D = h #(f 1/D ) n n n n n n n n n n n i = 1,2. Then k(fVD) = k (f*/D ) 4 k (f 2/D ) = k(f 2/D). n n n n n n A similar argument shows that k is an isomorphism. // If condition (a) of 3.9 is dropped the direct limit is obtained as a substructure of /A^ /D. In the result which now follows i t is important that the limit is taken over a well-ordered chain because i t is immediate from Adler [2] and can be deduced from Keisler [8] that any model of T , where fk is f u l l , is a direct limit of ultrapowers with index size < |A|. We shall say.in the situation of 3.9 that /A^ /D i s a chain-limit of the sequence of I ultrapowers < /A /^D^  : n > Y >- We speak of chain-limits of sets as well as chain-limits of structures. We can now state 3.10 Theorem (GCH) An ultrapower IB = /A^/D is a chain-limit of ultrapowers of index size < |B| i f either (1) |B| = Y+> where Y is regular - 73 -or (2) |B| is a limit cardinal > |A|. Proof (1) |B| = y +, Y regular. By 3.3 we can take | l | = y +. Let B be {f^/D : n < Y + } and define II for each 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 partitions of I such + * that i f £ < y then TI^ refines every partition in 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 partitions {H : n < £"} are already appro-priately 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 is uniform on I and hence D is y + - d . i . So by Chang's Theorem D i s y-d.i. Let <X^  : n < y> be a y-chain in D. Define an equivalence relation s on I as follows: (a) i f i and i ' belong to X - X ,, for some ri > y 6 n n+i then i E i ' i f f i n * * i ' for a l l n ' n ' such that n ' < n, n ' < <• (b) i f i and i ' belong to 1 - X g then i ss i ' . (c) in a l l other cases i s6 i ' . Now I = (1_xQ) U u{X -X ^ : n < y ) i s a disjoint decomposition of I and each X^ - X ^ is broken up by ss into < y'1"1' - 74 -c e l l s . As y i s regular and |ri] < Y w e have by'GCH that y'1"1' = Y« Hence s breaks up I into < y*Y = Y c e l l s and we can take II^ to be the p a r t i t i o n of I determined by ~. It i s clear that the sequence <TI^  : n < Y > thus defined s a t i s f i e s conditions (a) and (b) of 3.9. Hence by 3.9 (B i s I a d i r e c t l i m i t of a sequence </A /D : r\ < y > where 11 | = |II | < y. / (2) |B| a l i m i t c a r d i n a l > |A|. Define the p a r t i t i o n s <II^  : n < | B | > as i n part (1). Let II ^  be the common refinement of {IT.^  : n < £} for each E, < |B| . For any E, < |B| we have |n*| * |A^ | So as |A|< |B| we have by the GCH that |A^| < |B|, S O that |ll^{ < |B| for a l l E, < |B|. It i s easy to see that <IIg : E, < |B|> then s a t i s f i e s (a) and (b) of 3.9. // Notice that i f |A| < Y+ and (B i s the c h a i n - l i m i t of I + a sequence of ultrapowers < Ik /D : x\ < y > then we have that |B| < 2 Y ,Y + = 2 Y, so that we have proved 3.11 Theorem (GCH) Let |B = /A^/H and l e t y be a regular c a r d i n a l such that |A| < Y+- Then i t i s necessary and s u f f i c i e n t f o r |B| < Y+ that tB \ + i s a c h a i n - l i m i t of a sequence of ultrapowers < /A /D : r) < y > , where 11 | < Y for a l l r\ < y+. II Notice that i n a l l of the above we have not excluded the p o s s i b i l i t y that 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 /D for some r i n < Y and a l l n > ru. r] T|Q U U If we regard the least size of index | l | such that an ultrapower B of a structure Ik is 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 results of the last section we define a hierarchy of substructures of /A^ /D. In fact we w i l l work with arbitrary subsets of A^/D. 3.12 Definition Let Ik be any structure and let X be a subset of A^/D. We say that X is of level a i f a is the least cardinal such that there i s a partition IT of I into a cells 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 "level (X) = a". The level of a substructure of /AI/D is taken to be the level of i t s underlying set. // Note that (i) level ({f/D}) = spread(f/D). ( i i ) i f X is f i n i t e , level (X) < |A|. ( i i i ) i f lk(X) is the substructure of /A^ /D generated by X then the level of A(X) is the same as the level of X. - 76 -(iv) the level of A 1 /D is the least cardinal a such that D has an image E = h(D) on a for which h^ : /Aa/E -*• /A"*"/D is an isomorphism. In the rest of this section we assume that /A^ /D is presented with | l | already reduced in this way, i.e. that the level of AI/D is | l | . 3.13 Definition For a l l cardinals 8 ^  |I| we define = {X c AI/D : level (X) < 8} // 3.14 Theorem Proof Let B = AI/D. (a) For a l l in f i n i t e 3 ^  | l | , L^ is an ideal in S(B) (b) (GCH) i f D is y-d.i., where y is regular, then Ly + is y-complete. (a) It is 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 partitions of I. Then |lT^|, l l l ^ l < 8 and i f n^'H^ is the common refinement of It and n 2 i t is clear that |n «II2| = 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 «n2. - 77 -So each member of X^ u has a representative constant on each c e l l of II^'IL^. Thus X^ u e and hence L is an ideal. / p (b) Let (i) {X : n < Y} be a set of y members of L ,. n Y+ ( i i ) <Y^  : r) < y> be a y-chain in D. ( i i i ) {TI^  : n < y} be a set of y partitions of I into < y ce l l s , corresponding to the X^'s-We define a partition II of I as in the proof of 3.10, i.e. i f i , i ' e Y - Y ,, then n n+1 i n i ' i f f i n n , i ' for a i i n' < n . We have that |n| < s{YLNL : n < Y> = Y (employing the GCH). The partition 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 cells of II, so that u{X^ : r\ < y} e L^ + . // A theorem of Tarski [16] states that a ^-complete proper ideal L on a non-measurable set of cardinality 8 is either principal or admits a pairwise disjoint family {X , : n < 8) of non-members of L. If 111 = y + w e have by assumption that L^ + is a proper ideal. If y is regular we have that L is Y~ c o mpl e t e> from the above. Also from 3.3 and GCH we infer that - 78 -|A/D| = |B| > l e v e l (B) = | l | . If |B| = | l | , then L i s a Y + -complete proper i d e a l on a set of c a r d i n a l i t y y+. So by the r e s u l t of Tarski memtioned above L admits a pariwise d i s j o i n t family of non-members {X^ : n < y }. In t h i s s i t u a t i o n any embedding of the form h* : A J/E -»• A^D, where | j | ^  y, f a i l s to be onto i n a very strong way: i n fact the range of h^ can include none of the sets X^, n < y+, for to do so would contradict l e v e l ( X ) = v + i . e . X i L ,. n ' n Y+ 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 # / A : /AJ/E + /AI/D was an isomorphism 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 like 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 particular we shall obtain a partial converse to 2.20 and some results concerning ultrapowers /A^ /D with |A| < |A^ /D| < | l | . 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 this section h : <I,D> -> <J,E> is a fixed f i l t e r morphism. Recall that h^ : A^/E -»• A^ /D i s the injection 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) is onto i f f hj^j i s . ( i i ) If |A| > |I| then h* is onto i f f E ss D. ( i i i ) If h^ is onto and 8 < a then hf is onto. (iv) If D 56 E there is a cardinal OL > OJ such that hf n 8 is onto i f f 8 < ot^. Proof Parts (i) and ( i i i ) are simple consequences of 3.1. Part (iv) is a consequence of parts ( i i ) and ( i i i ) . We outline the proof of part ( i i ) . 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 is a set X e D such that h|^ is 1-1 and h(X) e E. Then by 2.3(b) we see that h^ is onto. Conversely i f h^ is onto, choose (for each j) partitions {i7? : n < IAI} of I. = h "^(1) such that each c e l l I1? is a singleton. 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 : j e j}.e D . The map which establishes D ss E is the map which sends j to the member of I. . JJ 4.2 Theorem If 8 € a(D) is such that |J| < 8 ^ U l then there is a - 81 -uniform u l t r a f i l t e r F on 3 and maps f : I ->- 8 , g : 8 J such that f(D) = F, g(F) = E and hf factors whence h^ i s onto i f f g^ and f ^ are onto. Proof As 8 e 0(D) there i s a p a r t i t i o n of I into 8 c e l l s that determines a uniform image F' of D on 8 . There i s also a p a r t i t i o n of I into |J| c e l l s that determine E as an image of D ( v i z : the p a r t i t i o n IL^ determined by h). Taking the common refinement of these two p a r t i t i o n s we obtain a p a r t i t i o n of I into 8 c e l l s that determines an u l t r a f i l t e r F on 6 such that E < F < D, and F' < F so that F i s uniform. Then there are obvious maps f : I 8 , g : 8 + J such that f(D) = F, G(F) = E and h = f°g. The rest of the theorem follows. // 4.3 Theorem Suppose h^ i s onto, and 8 < Y K a implies that Y ^ o(D). Then h* i s onto for a l l y < a. Proof Let IL^ = {I : j e j } , where I = h ^"(j),-be the p a r t i t i o n of I determined by h. Suppose f/D e u^/D where y < a. - 82 -Then by 2.14 and hypothesis we have that spread (f/D) < 8. ft So there i s f * ~ D f such that |range ( f * ) | < 8- Let range (F ) = V. Then by hypothesis and 4.1 we have that h^ i s onto. So by 3.1 there i s f ~ f * such that f' i s constant on each I. (1 e J ) . But then f 1 ~^ f and so by.3.1 again we have that f/D e range (h^)• 4.4 Theorem Let D be an u l t r a f i l t e r on I such that 8 < Y < a ? 28 implies y I a(D). Then i f 2 Z < a there i s an u l t r a f i l t e r E on 8 and a map k : I 8 such that E = k(D) and k^ i s onto for a l l Y < a. Proof F i r s t we claim (1) there i s an u l t r a f i l t e r E on 8 such that E < D and i f G i s any u l t r a f i l t e r on 8 such that G < D then G < E. For consider a l l u l t r a f i l t e r s on 8 that are images of D. 2$ 2 3 There are at most 2 of them and we can select < 2 p a r t i t i o n s of I into 8 pieces corresponding to these. The common refinement 2^ nnlK 923 of these 2 p a r t i t i o n s has at most 8 = 2 Z c e l l s , and hence determines an image E of D on 2^ such that each image of D on 8 i s an image of E'. However th(E') < Bj for otherwise there would be a uniform image of D on y where 8 < Y - 2 , contradicting Y i 0(D). So E' ss E where E i s an u l t r a f i l t e r on 8- C l e a r l y E s a t i s f i e s (1). Notice that (1) implies that E i s unique up to ss (and hence by e a r l i e r remarks, up to isomorphism) . - 8 3 -Select a map k : I -»• 8 such that E = k(D) . We claim ( 2 ) k^ is onto. Let k determine a partition II = {l_. : j e 8} of I. By 3 . 1 our claim ( 2 ) is verified i f we can show that for any refinement n* = {I n : j e 8, n < 8> of n, where I = u{i n : n < 8>, there exists a sequence <n_. : j e 8> e 8^ such that u {i J : j e 8) e D. * Now II* determines an image E of I on 8X8 such that TT.^(E ) = E where TT^ : 8X8 ^ 3 is the projection on the f i r s t factor. But I8 X8I = 8 so E is isomorphic to an u l t r a f i l t e r on 8 and hence by the universality property ( 1 ) of E there is a map : 8 8X8 such that ^ ( E ) = E . But then we have (TT^°I{J) ( E ) = E so by 2 . 1 * i there is X e E such that 1 T ^ ° ^ l x -*-s t n e identity on X. Then i f Y = T T ^ X ) , Y e E and X = (Y) = {>(j) : j e Y}. As O f ^ ) (j) = j for j e Y we have j) = <j ,ri > for some 8.. e 8 (j e Y) . Hence X £ ^ <J» rlj > : j e 3} where the n. are chosen arbi t r a r i l y i f j e 8 - Y. So t < j» rlj > : j e 8) e E and so u {I J : j e 8> e D * by definition of E . Thus ( 2 ) is verified. ( 3 ) k* is onto for a l l y < a. This follows from ( 2 ) and 4 . 3 . / / - 84 -B. Quaslcomplete U l t r a f i l t e r s We add some remarks on when the hypotheses of 4.4 are satisfied. If there is a regular cardinal YQ < | l | such that YQ i 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 satisfied i f we take 8 = YQ and a the least cardinal > YQ such that a e a(D), provided we accept the limit cardinal hypothesis. For o2B ( n +) then 2 Z = 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) for a l l Y - I 1 ! • The question has been posed (in Chang [6] for 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 in the case where | l | = y, the least measurable cardinal: the situation in general and in particular for I = OJ ,, remains unresolved. 1 1 OJ+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) for a l l y such that K < y < X, and simply K-quasicomplete i f D is (K, 111 )-quasicomplete.. We w i l l motivate these names a l i t t l e later, but for 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 earlier remarks we see that i f D is a uniform u l t r a f i l t e r on I and y is 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 this work Silver 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 -u l t r a f i l t e r s . Silver proves that i f D is an tu-incomplete inde-composible u l t r a f i l t e r on a strong limit cardinal X > to then there is a partition {I : n < to} of X such that I I D for a l l n n n < to and i f each I i s decomposed: I = u {i™ : m < to} (n < to) n n then there is a sequence <mn : n < to> such that m u {I : n < to} e D . n This result is a special case of 4.4. Another result mentioned by Silver in [14] is ascribed to Chang and Prikry. It states that i f GCH holds, and D is an indecomposible u l t r a f i l t e r on X then either X is inaccessible or cf(X) = to. We do not have available the proof of this result but in section E we w i l l prove a similar theorem in the more general setting of K-quasicomplete u l t r a f i l t e r s . Silver goes on in [14] to show that i f X i s a strongly inaccessible cardinal which supports an indecomposible u l t r a f i l t e r then A. has several "large cardinal" properties. In the other direction we w i l l show that i f u is the least measurable cardinal there exist K-quasicomplete u l t r a f i l t e r s on u for any K such that to ^  K < u. First we note the following result: 4.5 Lemma If Ik is a f u l l unary structure and /A^ /D = A^/E then for 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 is easy to show that for any structure IK with |K| < |A| we have ^/D = K J/E , (at least with respect to the unary relations). Let K be a set of cardinality 8 and suppose F = f(D) is a uniform image of D on K. Take K to be the structure which l i s t s precisely the unary relations of K, and let <J> : (K^ /D -* IK^ /E be an isomorphism. Then i f <j>(f/D) = g/E we claim F = g(E). For i f X is any subset of K and T is the corresponding predicate of L then A |K K^D F T x(f/D) i f f KJ/E 1= T x(g/E) i.e. {i : f ( i ) e X} e D i f f {j : g(j) e X} e E i.e. f _ 1(X) £ D i f f g _ 1(X) e E i.e. X £ f(D) i f f X £ g(E) So F = f(D) = g(E). Thus 8 £ cr(D) implies 8 e CJ(E), and the converse holds by symmetry. // As a corollary we have a converse to 4.4. 4.6 Corollary If E = h(D) is an image of D on 8 and h^ is 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 structures on ywe 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 cr(E). Hence i f y s a t i s f i e s 3 < y < a then y i o"(D) . // To construct a K-quasicomplete u l t r a f i l t e r on u we w i l l make use of the construction of Adler [1] for an co-incomplete non-regular u l t r a f i l t e r on y. Let E be any uniform u l t r a f i l t e r on K and l e t F be a u-complete uniform u l t r a f i l t e r on y. Take I = U X K , D = FxE. I f TT : I •> K i s the pro j e c t i o n we have IT(D) = E. Suppose A i s a f u l l structure on a set of c a r d i n a l i t y a < y. We claim that ir # : /AK/E + ^/D i s onto. Let I = {<n,j> : T| < y} for each j e K . By 3.1 we can show that TT^ i s onto i f we can prove that whenever we have decompositions I = { l n : TI < a} of each I. into a parts, then there i s a sequence <n. : j e K > J J such that u.{lj : j e K} e D. Assume that we are given such a sequence of decompositions and l e t X1] = {£ : <£,i> € I*?} then for each j e K we have J J y = u{xn : n < a} e F . - 88 -As F is a-complete i f follows that for each j e K there i s an r). < a such that X.J e F. But J J n. n. u{lj J : j e K} e D = F x E i f f {j : Xj e F} e E . Hence i f the sequence <n. : j e K > is chosen so that X. e F for a l l 1 e K we have that J n 1 u {I J : j € K} e D. So T T ^ is onto, and hence an isomorphism. As this 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 Cardinality II We w i l l prove here a converse to 2.20 under the assumption of the GCH and also some general results about |/D| where D is 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 let a < | l | be such that a = E{a : 8 < a}. Then a e a(D) i f f |aT/D| > a . Proof Note that any such a must be regular. The forward direc-tion of the result follows from 2.20. - 89 -Assume, now, that a e Cf(D). Then by 2.10 and Chang's Theorem we have that a , a , a' i 0"(D) , and hence by LCH that 9 a 2 a < y - 2 implies Y i O(D). 22<X , , (1) If 2 < |I| then by 4.4 there is an image E = h(D) of D on a such that h # : a a/E + a1/!) is a bisection. But 8 = th(E) < a as a I a(D) implies a i a(E), thus | otX/I>| = |aa/E| = |ae/E'| for some E' « E on 8• So |otX/D| < |a B| = a by hypothesis and 1.14(a). (2) If 1^ ~ t h e n W e m u s t h a v e t h ( D ) = 3' < a and by a similar argument |cxX/D | < |ot3 * | = a . // 4.8 Corollary (GCH) Let D be an u l t r a f i l t e r on I, and let a be a regular cardinal ^ 111. Then a £ a(D) i f f |otX/D 1 > a . - 90 -Proof If the GCH holds then for any regular cardinal a we R have a = £{a : 3 < a}. Certainly the LCH w i l l then hold so we may apply 4.7. // If a is singular the situation i s more complex and we summarize i t in 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 in section B. (|l| = u). Then D is tu-d.i. but, e.g., ui i 0(D). The same examples show that (3) cannot be reversed. Implication (2) presents some problems: Is GCH needed? Can (2) be reversed? These remain open questions. Of related interest to these problems and results is the following result which makes no use of the GCH. - 91 -4.9 Theorem If | otX/D | > a then either (1) D is cf(a)-d.i. or (2) there is a 3 < a such that |gI/D| > a. Proof Suppose that D is not cf(a)-d.i. Then by 2.17 X(a) is confinal in a^ /D where \ : a •+ a^ /D is the canonical embedding and a^ /D i s regarded as an ordered set. We take <' to be the order on a}/D. Define to be {f/D : f/D <' for each n < a. Then by our remarks following 2.17 we have that | c n l = In^ ol for a l l r\ < a. But and so aI/D = u{c^ : n < a} (t) |a/D| = sup{|8I/D| : 6 < a} Hence i f ICX^/DI > a there is a 8 < a such that IB^DI > a. // This theorem rather nicely f i l l s the gap in our under-standing l e f t by 4.8: i t t e l l s us that |aI/D| is greater than a i f f there is "good cause" for i t to be. - 92 -A bonus from the proof of the above r e s u l t i s the p r i n c i p l e (t) which holds whenever D i s not c f ( a ) - d . i . It i s an open question i n the theory of ultrapowers whether there e x i s t s a n o n - t r i v i a l ultrapower of singular c a r d i n a l i t y , i . e . an ultrapower a ^ / D where | a"*"/D | i s singular and greater than a. Using (t) we can envisage the following "scenario": that there e x i s t s an u l t r a f i l t e r D that i s not cf (ct)-d.i. and such that for some y, y < $ < a implies a < I B V D I < | a I / D | - Then by (t) 10£. X/ID | would have to be singular. By combining 4.9 with 1.15(h) we obtain 4.10 Theorem I f | ( 2 A ) I / D | > 2 a then e i t h e r D i s c f ( a ) - d . i . or there i s a 3 < a such that | 8 I / D | > a. Proof By 1.15(h) | ( 2 A ) I / D | > 2 a implies | o t X / D | > a. The r e s u l t then follows 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: both r e s u l t s can be proved without the GCH, but i f the GCH i s assumed then 4.10 implies Chang's Theorem. Por then we have by 4.8, | ( 2 A ) I / D | > 2 a i f f | ( a + ) I / D | > a + i f f D i s a + - d . i . Also i f 8 < a i s such that | 3 I / D | > a then we have for a l l regular - 93 -y such that 8 < y < a I Y V D I > I B 1 ^ ! > a > y so that l y 1 / 0 ! > Y and by 4.8 D is y-d.i. Chang's Theorem readily follows. // The above results relate only to the question of when |A^/D| > |A| for ultrapowers A V D . If we wish for more precise information on where jA*/D| f a l l s in the range of cardinals between |A| and |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 D. The following theorem shows us that even the "simplest" further question "When is |A"^ /D| > |A|+ ?" leads us to a new level of d i f f i c u l t y . 4.11 Theorem (GCH) Suppose |A| is regular and that [ l | > |A|. Then |A^/D| < |A|+ i f f A"*"/D is a chain-limit of a sequence I <A /^D^  : ri<|A| > 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 express this theorem in the following way: lA'/Dl < |A|+ - 94 -i f f there exist system of maps {h^ : n > |A|+} C A1 { h n n , : n < n < |A|+} C AA such that the diagrams h , (n' < n < |A|+) I + commute on a set in D, and i f = h (D) for a l l r\ < |A| then the diagrams commute on a set in and further i f g is any member of A there 1 1 + A exists an n > |A| and a t e A such that the diagram commutes on a set in D. - 95 -The question of whether such u l t r a f i l t e r s exist for 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 is 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. This assumption would imply that no ultrapower W ^ / D , where D is uniform on O J^ , is a chain-limit of a sequence <OJU )/D : X] < O J , > . M n 1 We shall close this section by proving a result which shows that i f D is a uniform u l t r a f i l t e r on I where | l | > | A | then either | A * / D | is "reasonably large" or we have some interesting pathological situations. 4.12 Theorem Let B = A^/D be any ultrapower of A, where D is Q uniform on I. Let 2 = | A |. Then either (l) 8 * | i | or (2) 6 " ^ cr(D) or (3) D has images on 8, D 2 uniform on 8 + and there exists h : 8 + + 8 such that h ( D ) = D and + // 8 8 the injection h : A / D ^ A / D 2 is onto. Proof By 3.2 there is a map k : I 8 such that k # : A3/E * A X /D is onto, where E = k ( D ) . Assume that 8 < | l | and 8 + e a ( D ) . Then there is a partition II' of I into 8 + pieces that determine a uniform image - 96 -of D or 6 . Let II be the common refinement of II' and II, . Then k |TT | = 3 + , B = B + and so JJ = II for a map g : I -> 8 + . By the construction of g there i s a map h : 8 + 8 we have k = g°h, h(g(D)) = E. Set g(D) = F , then because JJ refines 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 3 / E 8 A / F •> AX/D and as i s onto so are h^ and g^. The result follows i f we set / / I f we assume the GCH and | B | i s regular we can improve th i s result by using 3.3 instead of 3.2. We can then prove the above result with 8 = | B | instead of | A B | . Looking at 4.12 again we see that Conclusion (1) gives us a c a r d i n a l i t y r e s u l t , Conclusion (2) some completeness properties of the u l t r a f i l t e r , and Conclusion (3) isomorphism of ultrapowers of different index sizes. We venture a conjecture at this point. 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) \\\ < |I2I (2) 1 S uniform on 1^ (3) a < | l k | implies a e a(° k) f o r k = i> 2-Then I I /A 1/D1 £ A. VD 0 . // We may weaken this a l i t t l e by replacing (1) with (1'): | l 1 | < c f | l 2 | ) . Note that by 2.6 we have that 4.13 is a theorem i f |A| > | l J and also i f |I | < |A| < |I 9I we I I 1 ~ 2 can show that 4.13 holds. For i f /A /D^  ~ Ik /D2 where 11 | < |A| < |I 2I then by 4.5 we can conclude |A| i 0(0^). This conjecture, i f verified, would settle some interesting cardinality questions. For example consider the ultrapower OJ ^ / D where p < q < OJ P 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 q/D| =5 OJ _ . 1 p 1 p+1 But i f we assume GCH and 4.13 we can apply 4.12 with f^= B' / to conclude to I to q/D| > to 1 p ' q because 4.12(2) contradicts Chang's Theorem and 4.12(3) is ruled out - 98 -by 4.13. Conjecture 4.13 would be even more useful in 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) in the following section, but much s t i l l remains unknown in 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 simplicity of proof we shall employ the GCH in the proof of the next result. However, i t is sufficient to assume the LCH, or in part (2), that a is 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 let a be a limit cardinal < |I| such that a = sup(8 < a : 8 e 0"(D)}, (i-e., a is a limit point of a(D)) then (1) either a e a(D) or a + € cr(D) (2) i f cf ( a ) e a(D) then a e a ( D ) . Proof Let {a^ : n < 8) £ a(D) be such that a = supfo^ : n < 6}. For each n < 8 let n be a partition of I into a pieces that n n determines a uniform image D of D on a n n (1) The common refinement A{H^ : n < 8) of a l l these partitions determines an image D of D on a set - 99 -of c a r d i n a l II<a : ri < 3>. But B + n<a : n < 8> ^ a = a as c f ( a ) < f < a . Hence, by expansion i f necessary, we can take D + to be on a . As i t i s clear that D < D for a l l n < 8 we must n have th (D ) > a for a l l n < 8 • ft * + So th(D ) > a , hence th(D ) = a or a . / The r e s u l t i s t r i v i a l unless c f ( a ) < a and i t i s e a s i l y seen that we can take 8 = c f ( a ) . Let E be a uniform image of D on 8 determined, say, by a p a r t i t i o n {I : n < 8} of I. We construct a new p a r t i t i o n II of I as follows: i l l i ' i f f there e x i s t s n < 8 such that i , i ' e I and i l l g i ' for a l l £ < n . It i s easy to see that II r e f i n e s II£• on the set u{l : E < V < 8> = Y g . But as E i s uniform the sets Y ^ ( £ < 8) a l l belong to D, so II r e f i n e s each II^ almost everywhere. Now | IT | < Z<II<a r : E, < n> : n < 8> as each I i s broken up by II into at most Jl<at : '£ < n> pieces. - 100 -So | IT | < E<an'n' ' n < B > < Z<a + : 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 cardinality 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 + and let E be any u l t r a f i l t e r on R. Then i f + a a /D| = |a3/E| and | c f ( a ) a /Dl = |cf ( a) B/E| then we must have $ > a. Proof a By 1.14(b) we have |a /D| > a and so by 1.15(h), GCH a /D| > a . Thus |a 3| > |a3/E| > a which, with GCH, implies that 8 > cf(a). By 1.14(c)(ii) we have for any <I,F>, y, 6 that 1^ - 101 -4-In this inequality set y = a, 6 = c f ( a ) , I = a and F = D to obtain + so | ( a + ) a + / D | < | a a + / D | l c f ( a ) a /DI a + < | a a + / D | ' c f ( a ) a + / D l (*) If 6 < a then |a^/E| = | a a /D| = a + . By hypothesis |cf ( a ) p / E | = | c f ( a ) a / D| . Now 8 > cf(a) so |c f ( a ) 3 / E | < 63 = 8+ < a . Thus + I a , _ i cf(a) /D ^ , +.a + I a /D| 1 y 1 < (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 is a limit point of a(D). Proof Suppose to the contrary that there exists 8 < ot such that 8 < Y - a implies y i a(D). By Chang's Theorem we can take a to be a limit cardinal so that 2l =8 < a < a and 4.4 applies to show that h # : a 3/E -> a a /D is an isomorphism (w.r.t. any structure on a) for 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 restricts to a bijection h : AP/E -»• A /D . Thus |ae/E| = |aA+/D| and |cf(a) P/E| = |cf(a) a /D| and so by 4.5 8 > a, a contradiction. // We may prefer to express this theorem in the contrapositive: If a / a(D) then a + e a(D) i f f a is a limit point of cr(D). E. Further Results on Quasicomplete Ul t r a f i l t e r s An important and so yet not ful l y resolved question in the theory of u l t r a f i l t e r s i s the question of whether there exist u l t r a f i l t e r s D on sets I of "modest" cardinality such that y i a(D) for some regular cardinal y < | l | . As we observed in Section B the existence of such a y implies that D i s (y,X)-quasicomplete for some X > y, in fact D w i l l have a y-quasicomplete image on X. Equivalently we can ask for each K >.• oo which cardinals X > K + support K-quasicomplete u l t r a f i l t e r s . 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 result of Chang and Prlkry for indecomposable u l t r a f i l t e r s that we mentioned in 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 is inaccessible or cf(A) < K . Proof By 4.16 A. is a limit cardinal as i f X = 6 + for some then either 6 e a(D) or 6 is a limit point of 0"(D). But by hypothesis K < y < X implies y I a(D). Also as D is uniform on a set of cardinality A we have A e a(D) and hence cf(A) e 0"(D). But then we must have either cf(A) = A or cf(A) < K . / / Throughout the rest of this section D i s a K-quasicomplete u l t r a f i l t e r on a set I of cardinality A where 2l < X. By 4.4 this means that there i s a map h : I -»- K such that the injection h* : y K/E - y^D (E = h(D)) is onto for a l l y < A and hence induces isomorphisms /AK/E = AI/D for 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^  for a l l j £ J. We define a preordering on the subsets of I as follows: If X, Y £ I set X ^ Y i f f '{j : X n I, £ Y n I,} e E . - 104 -We are interested in the following statement: C(8) : i f {X^  : n < 8) Is a collection of 8 elements of D then there is an X e D such that X ^X for N n a i l n < 8. We shall show that i f A is a strong limit cardinal (and, i f LCH holds, i t always is) that C(8) holds for a l l 8 < A. This is the "completeness" property that motivates the name "quasicomplete". Suppose, then, that A i s a strong limit cardinal and that {X^  : n < 81 is a collection of 8 < Amembers of D. Define a partition II of I by i l l i 1 «-» for a l l n < 8 i e X n i f f i ' e X n Then II partitions I into at most 2 3 c e l l s . Suppose that II breaks up each I. so that 3 I. = u{l? : E < 23} . J 3 As 2 3 < A we have that h^ R is onto and so by 3.1 there is a sequence 2 <£j : j e J> £ ( 2 3 ) J such that u{l^J : j e j} £ D. Now take X = u{lj : 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. so that i f X n I. meets X n I. then 3 3 3 n j X n l . c X n I. so that 3 ~ n J - 105 -{ j : X n I . c X n I . } e E J ~ TI J and hence X ^ for a l l n < 8-Notice that we have, i n f a c t , shown that C(8) holds for a l l 8 such that 2 3 < X. Returning to the assumption that X i s a strong l i m i t c a r d i n a l we note that i f cf(X) < X (and hence < K) we also have C(X). For l e t X = u{a^ : £ < 8) where 8 < X and < X for a l l £ < 8 and l e t {X^ : n < X} be a c o l l e c t i o n of members of D. r Then as C(a^) holds there are sets X e D such that X ^ X^ for a l l n < dp (? < B) and as C(8) holds there i s a set X e D such that X < X^ for a l l 5 < 8 and i t follows e a s i l y that X < X^ for a l l n < X . We have shown that i f fk i s any structure such that |A| = a < X then the embedding h* : /AJ/E -WA^D A i s onto, and hence an isomorphism. On the other hand i f |A| = X then by 2.6 h ^ i s not onto as E g6 D and hence /A^ /E ¥ /A^ /D. However we have the following theorem which shows that the range of h ^ s t i l l froms a very comprehensive substructure of /AI/D. - 106 -4.18 Theorem Let /A be any structure of cardinality X. Then i f E is any set of formulas from ( c f . Chapter 1, Section D) such that |E| < X then £ i s satisfiable in /A1/D i f f £ is satisfiable already in h*A< /AJ/E) Proof Suppose E = {(J)^  : r| < 8) where 8 < X and that f/D e /A1 IU is such that /A1/!) 1= <|> (f/D) for a l l n < 8 . Let X, = {i £ I : /A 1= <f> ( f ( i ) ) } , then X. £ D for each n < 8 by Los' Theorem. As C(8) holds there is X £ D such that X for a l l n < 8. We define g £ A 1 as follows: i f 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 " i f X n I j = 4> pick a^ £ A and set g(i) = a^ for a l l i £ I . . ( l £ J ) . 3 Then g is 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|>n(g(i))} 3 Y^ where Y „ = u { l . : X n I . c X n I . } n X . Por i f i e Y^ ^ 3 3 ~ 3 n then g(i) = f ( i Q ) for some i Q e X n I where i £ 1^  - 107 -but then as i r t € X n I. 0 n 3 we have /A N d> (f(i„)) so that A * <|> (g(i)). But Y e D as n i - Y = h : X n I. c x n I.\) n X} = h _ 1(Z ) n X where Z e E . n n Hence {i : /A N cj>^(g(i))} e D so that ^/D = <|> (g/D) for a l l n < 8 , and g/D satisfies Z. As g/D e range (h^) = h*/A( /AJ/E) the theorem is proved. // In the case of singular strong limit cardinals X we have shown that C ( A ) holds and we can strengthen 4 . 1 8 to hold for sets of formulas Z with |z| = X. As an il l u s t r a t i o n of 4 . 1 8 we w i l l note a special case. Let a be a structure on the cardinal a that has the well-order < as one of i t s relations, and let B be an elementary extension of a. Then i f 6 is any element of a we w i l l say that B i s realised in B i f there is a b e B such that B = n < b < B for each n < g. Now regard A_ and A_^ /E as substructures of A^ /D by virtue of the embeddings i and h* respectively. If E = {(TI<VQ<B) : r)<B} i t i s easy to see that realising 8 and satisfying E are equivalent conditions on extensions of X. Then we have immediately - 108 -4.19 Corollary If 8 < A then 8 is realised in A^/D i f f 8 is already realised in A_ J/E. // Informally, 8 is realised in a /F i f f 8 is not confinal K K in 8_ /F(c a /F) . We can show after the manner of 2.17 that 8 is realised in a /F i f f F is 8-d.i. The result of 4.19 then would follow directly from the observation that a(D) = 0(E) u {A} . BIBLIOGRAPHY [1] A. Adler, C a r d i n a l i t i e s of Ultrapowers: An Example, Proc. Amer. Math. Soc. 28 (1971) pp. 311-312. [2] A. Adler, Representations of Models of F u l l Theories, to appear. [3] A. Adler and M. A. Jorgensen, Inequalities for the c a r d i n a l i t y of ultraproducts, to appear. [4] J . L. B e l l and A. B. Slomson, Models and Ultraproducts: An Introduction, North-Holland, Amsterdam (1969). [5] D. Booth, U l t r a f i l t e r s on a countable set, Annals of Math. Logic 2 (1970), pp. 1-24. [6] C. C. Chang, Descendingly 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. Morel, and D. Scott, Reduced d i r e c t products, Fund. Math. 51_ (1962), pp. 195-228. [8] H. J . K e i s l e r , Limit ultrapowers, Trans. Amer. Math. Soc. 107 (1963), pp. 382-408. [9] H. J . K e i s l e r , Good id e a l s i n f i e l d s of sets, Annals of Math. 7_9 (1964), pp. 338-459. [10] H. J . K e i s l e r , Ultrapowers and Saturated 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 of ultraproducts, B u l l . Amer. Math. Soc. 70 (1964), pp. 644-647. [12] K. Kunen and K. P r i k r y , On descendingly incomplete u l t r a f i l t e r s , to appear. - 109 -- 110 -[13] K. Prikry, On a problem of Gillman and Keisler, Annals of math, logic 2 (1970), pp. 179-187. [14] J. Silver, Indecomposable u l t r a f i l t e r s and 0^, talk at Tarski Symposium, Berkeley, Calif., June 23-30, 1971. [15] S. Sirota, On the problem of the classification of f i l t e r s , Sov. Math. Doklady 11 (1970) pp. 408-411. [16] A. Tarski, Ideale in vollstandigen Mengenkb'rpen I, Fund. Math. 32 (1939) pp. 45-63. [17] S. Ulam, Zur Masstheorie in 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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080477/manifest

Comment

Related Items