ABSTRACT MODEL THEORY by Craig Graham Fraser B.A. , Carleton U n i v e r s i t y , 1974-A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS. FOR THE DEGREE OF MASTER OF ARTS In the Department of Mathematics We accept t h i s thesis as conforming to the required standard THE UNIVERSITY. OF BRITISH. COLUMBIA August, 1976 (c) Craig Graham Fraser, 1976 In presenting th i s thesis in pa r t i a l fu l f i lment of the requirements fo an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree.that the L ibrary shal l make it f ree ly ava i l ab le for reference and study. I further agree that permission for extensive copying of th is thesis for scho lar ly purposes may be granted by the Head of my Department or by his representat ives. It is understood that copying or pub l i ca t ion of th is thes is for f inanc ia l gain sha l l not be allowed without my written permission. Department of h * T H F t l A T ZC S The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Abstract We define a notion of l o g i c that provides a general framework for the study of extensions of f i r s t - o r d e r predicate calculus. The concept of p a r t i a l isomorphism and i t s r e l a t i o n to i n f i n i t a r y l o g i c s are examined. Results on the d e f i n a b i l i t y of ordinals e s t a b l i s h the s e t t i n g for our proof of Lindstrom's Theorem: this theorem gives conditions that characterize f i r s t - o r d e r l o g i c . We then consider the analogues to the general case of the compactness and Lowenheim properties. For a wide cla s s of l o g i c s i t i s shown that i n t e r e s t i n g connections e x i s t between the analogues of these properties. i i i Table of Contents Page Introduction iv Chapter One: The Barwise Notion of a Logic 1 1.1 Some preliminaries and basic definitions 1 1.2 The main notion 5 Chapter Two: Partial Isomorphisms and Scott Sentences 11 Chapter Threes : Definability of structures and Lindstrom's .• _ ^ 17 Theorem 3.1 Definability of structures 17 3.2 Lindstrom's Theorem 24 Chapter Four: Hanf Numbers and Well-ordering Numbers 31 4.1 Definitions and prelMmnaf dies 31 4.2 Existence theorems 36 4.3 Relationship of Hanf and well-ordering numbers 38 Bibliography 50 i v INTRODUCTION In the l a s t two decades l o g i c i a n s have done considerable research on l o g i c s that extend the f i r s t - o r d e r predicate calculus. B e l l and Slomson, fo r instance, devote the l a s t two chapters of t h e i r textbook "Models and Ultraproducts" to the study of such extensions. The motivation for looking at these extensions stems from a desire to avoid c e r t a i n shortcomings of f i r s t - o r d e r l o g i c ; i n p a r t i c u l a r , as i s well known, f i r s t - o r d e r l o g i c i s d e f i c i e n t i n expressing many useful mathematical notions. Any good introduction to the f i r s t - o r d e r predicate l o g i c w i l l l i s t the following properties that t h i s l o g i c possesses: (i ) Compactness property, ( i i ) Lowenheim-Skolem property. A natural question a r i s e s : under what conditions does an extension also s a t i s f y these properties? The answer i s perhaps s u r p r i s i n g : any l o g i c possessing the above properties must be equivalent to f i r s t - o r d e r l o g i c . This i s a r e s u l t of the Scandinavian l o g i c i a n P. Lindstrom£l2[] . Besides being i n t e r e s t i n g i n i t s e l f , Lindstrom's r e s u l t has stimulated the growth of a f i e l d of research, abstract model theory, which attempts to construct a model theoryffor general extensions of f i r s t - o r d e r l o g i c . Among the many extensions of f i r s t - o r d e r calculus there are two l o g i c s which have been the subject of e s p e c i a l l y close study. One, pioneered by T a r s k i , i s obtained by allowing the formation of i n f i n i t e l y long sentences. The other, due to Mostowski, involves the use of generalized q u a n t i f i e r s . V Because these l o g i c s are proper extensions of f i r s t - o r d e r l o g i c Lindstrom's r e s u l t ensures the f a i l u r e of e i t h e r the compactness or the Lowenheim property. I t turns out, however, that analogues of these properties e x i s t f o r the above extensions. In addition,.reduction techniques of Fuhrken ,[9] and Lopez-Escobar [13] can be used to show c e r t a i n i n t e r e s t i n g connections between the analogues of these properties. The purpose of t h i s thesis i s threefold. F i r s t , a general notion of l o g i c i s established that i s adequate f o r formulating r e s u l t s i n a wide framework, (Chapter One). Second, the machinery necessary to prove Lindstrom's r e s u l t i s developed, (Chapters Two and Three). Third, the analogues of the compactness and Lowenheim properties are examined i n the general s e t t i n g , (Chapter Four). Our d e f i n i t i o n of a general l o g i c and the proof of Lindstrom's r e s u l t i s based on the treatment of Jon Barwise i n [ l ] . The material on general compactness and Lowenheim properties has i t s source i n Flum 8 . In our presentation we have modified, reorganized and supplemented the material with examples and connecting l i n k s . Thus we condense Barwise's notion of a l o g i c while emphasizing c e r t a i n assumptions which prove to be very important. Complete proofs and r e s u l t s from the l i t e r a t u r e have been supplied i n places. The constructions i n the proofs of Chapter Three are given e x p l i c i t l y (for example, Theorems 3.1.9 and 3.2.3). The complete proof given of Theorem 4.3.1 provides the j u s t i f i c a t i o n f o r the remark that follows that theorem. What were o r i g i n a l l y exercises and statements are also given,proof (Lemmas 4.3.4,4.3.5). Lastly,, the existence of the w e l l -ordering number of ^-(Qa) i s nowhere e x p l i c i t l y expressed i n the l i t e r a t u r e but f a l l s out n a t u r a l l y from:iFuhrken"s reduction technique. v i I t i s hoped that this, thesis w i l l be accessible to anyone f a m i l i a r with f i r s t - o r d e r l o g i c . The rudiments of cardinal.and o r d i n a l arithmetic are assumed; the material that i s needed here may be found i n Chapter 0 of the above mentioned book of' B e l l and-Slomson. F i n a l l y ; the terms 'set' and 'class' are understood i n the sense of the Godel-Bernays system of set theory, a set being a cl a s s which i s a member of another class.(see Mendelson [l4] f o r more d e t a i l s ) . v i i Acknowledgement Ilwish to thank my supervisor Dr. A. Adler for the suggestion of the topic and his patient reading during the preparation of this thesis. My appreciation i s also extended to Dr. E. Belluce for reading this thesis. Finally, I would like to thank the National Research Council of Canada for their financial support during the last two years. CHAPTER ONE THE BARWISE NOTION OF A LOGIC In t h i s section we present the bare e s s e n t i a l s of Barwise's treatment of l o g i c s . We have,ffbr example, dispensed with his c a t e g o r i c a l approach which, while i n t e r e s t i n g , doesn't seem to be e s s e n t i a l . 1.1 Some Preliminaries and Basic D e f i n i t i o n s D e f i n i t i o n 1.1.1: AAlanguage L i s a c o l l e c t i o n of r e l a t i o n , function,and constant symbols. L w i l l always contain the symbol V , a unary r e l a t i o n symbol which denotes the domain of the u n i v e r s a l q u a n t i f i e r . The use of V , although i t i s a somewhat a r t i f i c i a l constraint, proves to be t e c h n i c a l l y convenient. D e f i n i t i o n 1.1.2: A p a r t i a l structure M for L i s a function M with domain £ L such that: (i ) M = i s a set, c a l l e d the universe of M . ( i i ) I f Ree L i s a n-ary r e l a t i o n symbol then R^ c M n . ( i i i ) I f f e L i s a n-ary function symbol then f ^ i s a p a r t i a l function from M n to M . (iv) I f c e L i s a constant symbol and c^ i s defined then c^ e M . M M If i n ( i i i ) and (iv) each f and each c i s defined t o t a l l y then M i s an L-structure. An L-structure w i l l sometimes be displayed as follows: M = < M, R^, R_2,..,, f_ l 5 f_ 2,..., a x , a 2,... > , where M i s the universe of M , R^ i s the i n t e r p r e t a t i o n of R^, f_^ i s the in t e r p r e t a t i o n of f , , etc. . 2> Definition 1.1.3 : Two partial structures M and W for a language L are isomorphic i f there is a bijective mapping from the universe of M to the universe of W which preserves i n a natural sense the relations and functions. We write M - W to indicate that M is isomorphic to W. An expansion of a language L is any language K with L c K. An L-structure M i s a reduct of a K-structure W, and W is an expansion of M, i f M is W N , the restriction of M to the language L. Every language L hassa set of terms associated with i t , defined inductively as follows: i f c is a constant term of L then c is a term; i f t,, t are terms and f is a n-ary function symbol then f(t..,...,t ) is I n J J I n M a term. Given a structure M for L every term t of L denotes an element t 8l M (the universe of M ) . If c is a constant symbol t^ is just c^ and i f t is f ( t - , . . . , t ) then t = f ( t , ; . . . , t ) where t,, t are already assumed i n 1 n 1 n (inductively) to have been defined. We now introduce the important concept of an interpretation( morphism) Definition 1.1.4 : Let r > 0 be an integer. Let L, K be languages. An r-term interpretation or morphism a of L into K consists of r terms t^, t of K and a mapping a from L into Kasatisfying : (i) If R e L is an n-ary relation symbol then R is an (n-H- r)-ary relation symbol. Cfc ( i i ) If f e L is an(n-ary function symbol then f is an (n + r)-ary function symbol. ( i i i ) If a(x) = V then x = V . We thus have that V " is a (1 + r) -ary relation symbol, usually 3 denoted by U or V. A 0-term i n t e r p r e t a t i o n a such that a( \f ) = \J i s c a l l e d a simple morphism. Now morphisms on languages induce operations on the corresponding structures. Let a : L •> K be an r-morphism and l e t M = < M,..., a^,..., a^ > be a t y p i c a l K-structure, where i s the i n t e r p r e t a t i o n i n M of t'^. We wish to p u l l Maback to a structure M f o r L. The universe of M i s N = { a e M : (a, a ^ ..., a^) e U^, U = a( V ) } The i n t e r p r e t a t i o n of an n-ary r e l a t i o n symbol R e L i s given by (b, , .... b ) e R i f f b b e N and (b , , b , a,, a ) I n l n I n i r e ( R a ) M : The i n t e r p r e t a t i o n of an n-ary function symbol f e L s i s i t h e r e s t r i c t i o n of f_ to N n where 1 r f (b , b ) = (f°') M(b 1, b , a , a ) —a,,...,a 1 n 1 n l r 1 r Since N may not be closed under the functions f , M i s only a 1 r p a r t i a l L-structure. In many cases, however, M 01 will be an L-structure and M i s then said to be a - i n v e r t i b l e . There are two important examples of the above which are used repeatedly i n future proofs. Example 1.1.5 : Let L be a language and V a unary r e l a t i o n symbol not i n L and l e t K * L(V). (L(V) i s the language obtained from L by adjoining the symbol Vi) Let a : L K be the i n t e r p r e t a t i o n which sends V to V but leaves the other symbols of L unchanged. A t y p i c a l K-structure has the form (M,V) where M i s an L-structure. The structure (M,V) i s a - i n v e r t i b l e i f f the set V i s closed under the various functions of M, i n which case 4 JVf"a i s j u s t the usual r e l a t i v i z a t i o n of M to the set V, M a== Example 1.1.6: Given a language L and a c o l l e c t i o n of L-structures { M. |: i e I •! i t i s possible to code t h i s set of structures into a s i n g l e model f o r an expanded language K of L. For example, l e t L = { R } where R i s a binary r e l a t i o n symbol and l e t K = { R', V, c } where R' i s 3-ary, W i s binary and c i s a constant symbol. Let a : L -> K be the 1-morphism which sends V to V and R to R'. The term of a i s j u s t c. From the set of L-structures { M : i e I } we form,the K-structure M =? < M, V, R' > the indexed union of the , by defining M = I U . M.M. where M. = \/ ^ i , n e l i i v ' < a, i > e V i f i e I and a e M. , — 1 M < a", i > e¥R' i f i e I and < a, b > e R i *.' The i n t e r p r e t a t i o n of the constant symbol was d e l i b e r a t e l y l e f t unspecified; i f we denote by ( M, j ) the indexed union i n which c receives the i n t e r p r e t a t i o n j then M_. = ( M, j ) , i . e . i t i s possible to recover each of the structures M. from the indexed union M. J One more preliminary d e f i n i t i o n i s needed. D e f i n i t i o n 1.1.7 : By a c o l l e c t i o n C of languages we w i l l always mean a c o l l e c t i o n which s a t i s f i e s the following two conditions: (i) I f L and K are i n C then L QKK i s i n G , ( i i ) I f L i s i n C and K i s obtained from L by adding ( f i n i t e l y ) many r e l a t i o n , function or constant symbols to L then K i s i n C. 5 1.2. The Main Notion D e f i n i t i o n 1.2.1 : A l o g i c L* on a c o l l e c t i o n C of languages consists of two,components, a syntax and a semantics. The syntax of L* assigns to each L i n C a cl a s s L* of sentences. The elements of L* are c a l l e d L*-sentences. The syntax s a t i s f i e s the following two properties: (i) I f L £ K then L * £ K * . ( i i ) (Occurrence Property) : For every L*-sentence <j> there i s a smallest (under inclusion) language L. i n C such that 9 e L* . 9 9 For each morphism a from L to K, the syntax also induces a map ao from L to K . I f 9 i s an L -sentence, a (9) w i l l be denoted by <j> . The semantics of L* i s a r e l a t i o n such that i f M 1== 9 then M i s an L-structure for some L i n C and 9 e L*. The semantics s a t i s f i e s : ( i i i ) (iiiT):o-.("1J*s6mo.rphismrErpperty)f:.' I f Mi!==cj>' and Mhs.M'then Nl=<f>. M^=(() i s read as "M i s a model of 9". The syntax and semantics of L* f i t together according to the f i n a l property: (Iv) (Translation Property): For every L*-sentence 9, every morphism a : L^ -> K and every K-structure M j M F= 9 i f f M i s a - i n v e r t i b l e and M ^=9. The next two examples provide some motivation f o r the requirement of the t r a n s l a t i o n property. Example 1.2.2: Let 9 be an L*-sentence and l e t K be any language such that L = L, £ K . If a : L1 ->• K i s the natural embedding map and M i s a K-structure 9 9 then M i s j u s t the L-reduct of M, i . e . M == M | S L « The t r a n s l a t i o n property asserts that M F= 9 i f f 9. So the t r a n s l a t i o n property implies that JL* has the above 'reduct property'. Exanple 1.2.3: Let 9 be an L*-sentence and l e t L = L^ be the set of symbols occuring i n <j>. Let V be a unary r e l a t i o n symbol not i n A> ( i . e i not i n L , ) , <P and l e t a : L -* L(V) be the r e l a t i v i z a t i o n defined i n Example 1.1.5. We V a write <j> f o r <j> . The t r a n s l a t i o n property asserts that the L(V)-structure ( M, V ) |= <}> i f f V i s closed under the functions of M and M ( V ) | = 4 . V cf> i s c a l l e d the r e l a t i v i z a t i o n of <J> to V, and the t r a n s l a t i o n property implies that our l o g i c has t h i s r e l a t i v i z a t i o n property. In the following we s t i p u l a t e a few a d d i t i o n a l assumptions on a l o g i c . These assumptions are not a necessary part of a l o g i c but are designed to ensure that any l o g i c under consideration extends the c l a s s i c a l f i r s t -order predicate calculus. Observe f i r s t - that any language L gives r i s e to a set of atomic sentences. I f and are terms of L then t^ = -X. i s an atomic sentence of L. ('=' denotes equality and i s treated here as a l o g i c a l symbol; i t doesn't occur i n the language L.) If R i s an n-ary r e l a t i o n symbol and t, , .... t are terms then R ( t . , . . . , t ) i s an atomic sentence of L. 1' ' n v 1 n Let L* be a l o g i c on the c o l l e c t i o n C of languages. We formulate three assumptions which we require L* to s a t i s f y : Assumption 1 : L* contains a l l atomic sentences. This means that: (i) i f t^ = i s an atomic sentence of L then i t i s an element of L*, and for each L-structure M ' 1 .'. 2 ji 1 Zl . n ( i i ) i f R ( t . , . . . , t ) i s an atomic sentence of L then i t i s an i n element of L*, and f o r each L-structure M Mt= R(t. t ) i f f ( t f , . . . , t M ) e R M . i n i n Assumption 2 : L* contains conjunction and negation. Suppose L i s a language of C and <j> and are any sentences of L*. Conjunction: There i s a sentence x of L * such that i f M i s any L-structure then M (=x i f f W t= <J> and M f=- 1(1 The sentence X w i l l be denoted by 4> A * Negation: There i s a sentence x °f L such that i f M i s any L-structure then M x i f f n ° t M |=- <(>. x w i l l be denoted by (^j> . Assumption 3 : L* i s closed under e x i s t e n t i a l q u a n t i f i c a t i o n . Again l e t L be any language i n C and l e t if be a sentence of L* which may or ma/not contain the constant symbol c. Then there i s a sentence %fof• *L such that i f M i s any L-structure: M t= x i f f there i s some constant a e M such that ( M, a ) F=- <J> \ ( M, a ) i s the L-structure d i f f e r i n g at most from M i n that c receives the i n t e r p r e t a t i o n a i n the universe of M. ) The sentence x w i l l be denoted by 3 x < H ( x ) . For our purposes then a l o g i c L* as defined e a r l i e r s a t i s f i e s the four properties of the d e f i n i t i o n and the three assumptions given above. Ad d i t i o n a l r e s t r i c t i o n s might be introduced. For instance, Barwise proposes a tentativee d e f i n i t i o n f o r f i n i t a r y s y n t a c t i c operations. This d e f i n i t i o n , however, i s extremely general and may be too weak to be u s e f u l ; we w i l l not look at i t further. At t h i s point i t i s i n t e r e s t i n g to look at some examples of l o g i c s that are covered i n the Barwise set-up. Example 1.2.4 : L R . - t h e c l a s s i c a l f i r s t S o r d e r predicate c a l c u l u s . i5(j)u) Syntax: Given any language L the set L = L i s formed i n d u c t i v e l y as follows: (i ) L contains a l l atomic sentences (see page ) ami ( i i ) I f d>, Tb e L then A A * e L 0)0) 0)0) ( i i i ) I f <|> e L then d^> E L 0)0) (DO) (iv) If d> E L then 3x<J> (x) e L , 0 ) 0 ) 0)0) L i s sometimes referred to as the set of well-formed sentences. 0)0) Semantics: . Given an L-structure M we i n d u c t i v e l y define the r e l a t i o n M fc= <j> (A a sentence of L_ ) as follows: 0)0) ( i ) I f <j) i s an atomic sentence the r e l a t i o n M ^ <|> is exactly as given, i n the statement of assumption 1 above ( i i ) r ; Mf= <f)/\i|) i f f M(=(|> and MJ= ^ ( i i i ) JVH==^ (() i f f notM^^' (iv) I f (f> i s a sentence which may or may not contain the constant symbol c then Mf= 3X(f>(x) i f f there i s some a £ M such that ( M, a )|=(j)(c) where c receives the i n t e r p r e t a t i o n a i n ( M, a ) (We wrote <(>(c) for tj) to i n d i c a t e the s p e c i a l r o l e of the constant symbol c. ) Note: In our formulation of a l o g i c we have avoided the usual concept of a free v a r i a b l e . This i s because a free i n d i v i d u a l v a r i a b l e of a language can be i d e n t i f i e d with a constant symbol of a larger language. More p r e c i s e l y , given a language L form the language L'^c) by adjoining the constant symbol c to L. I f M i s an L-structure we are free to i n t e r p r e t c a r b i t r a r i l y in the universe of M to get an L ( c ) - s t r u c t u r e ( M, a ). In t h i s manner, c can be thought of as a free v a r i a b l e of L. And s i m i l a r remarks apply i n the case of (higher-order) l o g i c s which allow r e l a t i o n or predicate v a r i a b l e s . Example 1.2.5 : - second-order l o g i c . Informally, t h i s i s an extension o f f c l a s s i c a l f i r s t - o r d e r l o g i c i n which q u a n t i f i c a t i o n over predicate variables i s allowed. Syntax: We add a new l o g i c a l symbol E (the membership r e l a t i o n ) to i • New atomic sentences t e U are allowed, where t i s a term and U is a * unary relation symbol. If L is a language L is obtained from L by adding the following formation rule to the syntax of L .: 0)0) (v) If <j> e',!.*• then H X * e L * . Semantics : e is interpreted in any L-structure M as set-membership. Add the following semantic rule to L : 0)0) (v) If <j> i s any sentence of L * which may or may not contain the unary relation symbol U then M|= 3X<j> i f f there i s some U C M such that ( M, U )^=<j>(U). Here ( M, IJ ) is the structure differing at most from M in that U receives the interpretation U; we write <j>(U) for (> to indicate the special role of the symbol U. Example 1.2.6 : * - ( Q A ) ~ logics with the quantifier Q ^ . These logics are obtained from L by adding the quantifier Q , where a i i s an ordinal. They 0)0) J b n are but one example of the many different logics that result from employing generalized quantifiers. Syntax: Add the following rule to the syntax of (v) If (f> e L * then Q x<|>(x) £ L * . Semantics: Add the following rule to the semantics of L : 0)0) •k (v) If (j) (c) i s a sentence of L then M|=Qax<))(x) i f f cardinality ( {aeM : . ( M, a ) |= <j> (c) } ) >_ o) ~ . (w i s the a cardinal in the sequence of i n f i n i t e cardinals) Intuitively, Q^xKx) holds in. M i f there are oi objects a such that ( M, a )|==<(>(G)»-' One important specific example i s L ( Q Q ) : in this logic, M |= QQX<))(X) i f f there are i n f i n i t e l y many a e M such that ( M, a ) ( = <t>(c) 10 I n f i n i t a r y l o g i c s are important extensions of the predicate calculus and have been the object of close study i n recent years. The next l o g i c s we w i l l consider are examples of these i n f i n i t a r y l o g i c s ; they w i l l be examined i n greater d e t a i l i n Chapter I I . Example 1.2.7 : L - l o g i c with i n f i n i t e conjunctions and di s j u n c t i o n s . Syntax: Add the following r u l e to the syntax of L : 0)0) ft (v) I f $ i s a set of sentences of L then A $ and V $ are sentences of L*. Semantics: Add the following r u l e to the semantics of L : 0)0) (v) M {=• /\$ i f f M |= 9 f o r a l l 9 e $ and M (=• V $ i f f M fc= <|>f f or some 9 e $ . Example 1.2.8: L , where a i s an i n f i n i t e c a r d i n a l . This l o g i c has the C 0CU) sfme^yn^ajPand semantics as L except f o r the following r e s t r i c t i o n : the set $ of the previous example must have c a r d i n a l i t y l e s s than a. Thus f o r a = U j we get the l o g i c ^ i n which only the countable conjunction and di s j u n c t i o n of sets of sentences i s allowed. 11 CHAPTER TWO PARTIAL ISOMORPHISMS AND SCOTT SENTENCES In t h i s chapter we give some d e f i n i t i o n s and state some r e s u l t s from the i n f i n i t a r y l o g i c s described at the end of the l a s t chapter. A more d e t a i l e d account including proofs of the r e s u l t s may be found i n [2 J . Let M be an L-structure. A p a r t i a l substructure MQ of M i s a subset M^ of S-hecuniverse of M together with the r e s t r i c t i o n s of the r e l a t i o n s and functions to MQ (so some of the functions may be p a r t i a l ) . Given L-structures M and W, a p a r t i a l morphism from M to W i s j u s t an isomorphism F : MQ - WQ f o r p a r t i a l substructures of M and W re s p e c t i v e l y . D e f i n i t i o n 2.1 : Let I be a set of p a r t i a l morphisms from M to M. We say I has the back and f o r t h property i f for every F e I and a e M (resp-e c t i v e l y b e N) there i s a G e I with F£-G and a e domain(G) (respectively b e range(G)). I f there e x i s t s a set I with the, back and f o r t h property then M Z a n d W are said to be p a r t i a l l y isomorphic written I : M = hi or simply M - W. P Example 2.2 : Let M = < M, <^ > and W = < N, <^ > be dense l i n e a r orderings without endpoints. For example M and M could be the r e a l s and the r a t i o n a l s r e s p e c t i v e l y with the natural ordering. Let the set I consist of a l l maps f such that f i s an isomorphism from a f i n i t e subordering of M onto a f i n i t e subordering of W. Then i t i s straightforward to check that I has the back and f o r t h property and so I : M W. 12 The notion of p a r t i a l isomorphism can be viewed as a 'weak' form of isomorphism. The next r e s u l t shows that i n c e r t a i n cases the two notions are equivalent. Tfeorem 2.3 : I f M and W are countable L-structures then M - W i f f there e x i s t s a set I such that I : M - W. P Proof; If f : M - W l e t I = { f } and c l e a r l y I : M - W. T ° prove the converse we give a s p e c i a l case which i s a c t u a l l y a c l a s s i c a l r e s u l t . , The general case i s then proved i n a s i m i l a r manner. The s p e c i a l case i s where M, W and I are as given i n Example 2.2 above with the added s t i p u l a t i o n that M and W are countable. Since M and N are both countable l e t M = { a^,a^,a^,... } and N = { b^jb^jb^*... }• The set I i s used to construct an isomorphism f from M = < M, <^ > onto W = < N, <^ >. In f a c t a sequence f . ^ . f n — £ „ ?r. •. i s constructed such that f = f ±s the desired 1 2 3 n n isomorphism. Let f^ = { <a^,b^> } be the function i n I which maps a^ to b^. We now proceed i n d u c t i v e l y : f„ = some function g e l with f„ ,^Zg and a e domain(g) 2n Zn— 1 n f, f „ ,. = some function g e l with f„ 9^ .g and b e range(g) . /.'.zn+i zn n Then f = U f has domain a l l of M, range a l l of N and preserves the n n , . M W „ c . r e l a t i o n s < , < . Hence f i s an isomorphism. R e c a l l the d e f i n i t i o n of L rgiveh i n Example 1.2.7. Two L-structures M and W are said to be L ^ - e l e m e n t a r i l y equivalent , written M = W, i f the same set of L -sentences hold i n both structures. The L °°a> following theorem i s fundamental i n that i t provides a connection between 13 the algebraic concept of p a r t i a l isomorphism and the l o g i c a l concept of L^-elementary equivalence. Theorem 2.4 : Given L-structures M and W the following are equivalent: (i ) M =. W °°U) ( i i ) There i s an I : M = M P One e f f e c t of t h i s theorem i s to make cl e a r the t r a n s i t i v i t y of the r e l a t i o n - because of the f a i r l y obvious t r a n s i t i v i t y of L -p °°U> elementary equivalence. Later r e s u l t s require a refinement of the above theorem. To t h i s end a precise measure of the complexity of an L^-sentence i s needed. The next d e f i n i t i o n gives one such measure. D e f i n i t i o n 2.5 : Let d) be an L ^sentence. The q u a n t i f i e r rank of d>, — 00(0 written qr ( d ) ) , i s defined i n d u c t i v e l y as follows: (i ) I f <j> i s an atomic sentence i n which no function symbols occur then qr(d)) = 0. ( i i ) Suppose <j> i s an atomic sentence of the form t^ = t ^ i n which function symbols occur. Let n be the number of occurrences of ::.or.yfunction symbols„ in': t^ or t^. Then qr(<j>) = n-1. ( i i i ) Suppose <j> i s an atomic sentence of the form R(t^,...,t^) i n which function symbols occur. Let n be the number of occurrences of function symbols i n any of the t ^ . Then qr(cj)) = n . (iv) qrOH>) = qr(rf)), q r ( V x < K x ) ) = qr( 3x<j>(x)) = qr(<J)(c)), q r ( / \ $ ) = q r ( \ / $ ) = sup {qr(<()) : d> e $ } . If a i s an o r d i n a l we write M =^ a W to indicate.that the 14 same set of sentences of q u a n t i f i e r rank _< a hold i n both M and M. Theorem 2.6 : Given L-structures M and N and an o r d i n a l a the following are equivalent: (i ) M -E l W • . ( i i ) There i s a sequence I n 3 I D . .. D i -D . . .31 where, f o r U I p ot each g < a, I i s a non-empty set of p a r t i a l morphisms — p between M and W such that i f 3+1 < a and F e I then f o r — p+i each a e M (resp. b e N) there i s a G e I with F G and p a e domain(G) (resp. b e range(G)). The sequence { 1^ ^ g < a gives an approximation to a p a r t i a l isomorphism i n the case where M =,a W although not ne c e s s a r i l y M =.. W . °°u) °°OJ Let L be a language and 9 a sentence of L*. Ln the subsequent d e f i n i t i o n the following notation i s u s e d : ^ <Kx) denotes the sentence it of L such that f o r any L-structure M M fc= 3 x<j> (£) i f f ( M, a )[= 9(c) where a i s the i n t e r p r e t a t i o n of c i n III . Also, i f the l o g i c i s L then L denotes the set L of sentences of L. D e f i n i t i o n 2.7 : Let L be a language. For each o r d i n a l a, each L-structure M and each sequence d = a. a - e Mwe define a sentence a a,u N e I n (M,a) L(c,,...,c ) . T h i s - i s ^ c a l l e d a Scott Sentence. The d e f i n i t i o n proceeds 1 n r by induction on a: a(M a) = ^ : ^ i s a n atomic or negated atomic sentence of L(c^ c qr(ijO. = O sand (M,a1,...,'a } 1 n a+1 For any a, ^ i s the conjunction of the following sentences: 15 a C(M,a) c beM—' xn+l (M,a.,...,a ,b).Sc 1 n n+1 V N / 0 1 <- C n + 1 ,i V x n + i beM a(M,a.,...,a ,b)Sc _,,' 1 ii n+1 -Far., l i c i t erdineiv > , - X a For l i m i t ordinals X, a,,, „ N i s the conjunction , a,,. * . We write ' (M,a) J a<\ (M,a) a^j f o r ^ when a i s the empty sequence. Informally, the Scott sentence a^ ^ gathers up a l l the information about (M,a.) that i s contained i n those sentences of q u a n t i f i e r rank <_ a which hold i n (M,a). The next theorem makes t h i s remark more precise. Theorem 2.8 : Let M and W be L-structures and l e t a = a,,...,a 1 n b = b^,...,b be sequences i n M and N re s p e c t i v e l y . Then ( N,6)F= o ° M j a ) i f f (M,a) =^a (N,b) . °°U) A s p e c i a l case of t h i s theorem i s when ri = 0 and d,b are the empty sequences. In t h i s case N F i f f M W ~. Hence Theorem 2.8 gives a nice c r i t e r i o n i n terms of Scott sentences for L -elementary equivalence. Ddiinition 2.9 : The sequence of beth cardinals i s defined as follows: ~1 = 0 I = 2~-^a -^0 ' — l a + l L = sup. I i f M s a l i m i t o r d i n a l . 3 a<B a JJWe w i l l be p a r t i c u l a r l y interested iri those cardinals a for which | = a . One important example of t h i s type of c a r d i n a l i s oi. We c a l l cardinals such that ~] = a f i x e d point beth c a r d i n a l s . 16 The l a s t theorem of t h i s chapter provides a d d i t i o n a l information about Scott sentences i n the case where c a r d i n a l i t y ( L ) _< K f o r some f i x e d point beth c a r d i n a l K. The theorem i s also c r u c i a l i n the proof of the main r e s u l t of Chapter Three. Theorem 2.10 : Suppose K i s a c a r d i n a l such that K = and L i s a —'K ' language with c a r d i n a l i t y ( L ) <_ K . Then for each a < K and each p o s i t i v e integer n: (i ) I f M i s any L-structure the sentence a°lu N i s i n L(c,,...,c ) J (M,a) 1' n KO) ( i i ) There are l e s s than K sentences of the form a ^ ^ as M ranges over a l l L-structures. 17 CHAPTER THREE DEFINABILITY OF STRUCTURES AND LINDSTROMSS THEOREM 3.1 D e f i n a b i l i t y of Structures In t h i s section we e s t a b l i s h some r e s u l t s on the d e f i n a b i l i t y of structures and, i n p a r t i c u l a r ^ the d e f i n a b i l i t y of ordinals i n a l o g i c . These r e s u l t s are important because the d e f i n a b i l i t y of ordinals gives some measure of the 'strength' of a l o g i c . This becomes more clear i n the material of 3.2 where the r e s u l t s are needed i n some of. the key proofs. Throughout t h i s section L* i s a logicapn a c o l l e c t i o n Coof languages. D e f i n i t i o n 3.1.1 : Structures M and W are s i m i l a r i f domaim'(iM) = domain(W) = L. If K i s a cla s s of s i m i l a r structures f o r a language L then K'As L*-definable i f there i s a sentence d> e L such that M e K i f f M \p= <b. So i f L == L 0)0) then K i s L*-definable i f f K i s an elementary class ( i . e l the cla s s of models of some f i r s t - o r d e r sentence.) We now give the notion of Z { - d e f i n a b i l i t y . This i s the notion of d e f i n a b i l i t y which w i l l be used most often. D e f i n i t i o n 3.1.2 : Let K be a cla s s of L-structures. K i s sa i d to be Z{-definable i f ( i ) there i s a language K and a 0-morphism a : L -> K which i s the i d e n i t y on L except possibly that a(\/ ) + V and ( i i ) there i s a sentence <j> i n K* such that each model M of d) i s a - i n v e r t i b l e and K = {M"a=* M t= <p> The following remarks should help c l a r i f y w h a t i i t means f o r a set 18 of structures K of a language L to be Z{-definable. Suppose L i s contained i n a l arger language K and l e t K(V) be the language obtained from K by adjoining the new unary r e l a t i o n symbol V.toWe denote a t y p i c a l K(V)-structure by ( M, V ) where Miis a K-structure and V i s the i n t e r p r e t a t i o n of V i n the universe of M. Let <f> be a sentence of K(V)* with the following property: i f ( M, V ) |=. rf> then (M(V)j>|\ L i s a f u l l L-structure. ( ( M ( V ) ) f i s the structure obtained by f i r s t r e l a t i v i z i n g M to V to get a ( p a r t i a l ) K-structure and then taking the reduct of t h i s structure to the language L. ) Then a c l a s s K of Ljsliructures i s £{-definable i f f there e x i s t a K, V and a sentence <)> as above such that K consists of a l l and only those structures of the form (M ( V ))(v for (M, V)|=d). C l e a r l y any definable c l a s s i s z{-definable. Also, the c l a s s of reducts of a definable c l a s s w i l l be Z^-definable. D e f i n i t i o n 3.1.3:(i^A structure M i s definable (Z{-definable) i n L* i f K = { hi : hi i s s i m i l a r to M and W - M } i s definable (z{-definable) . (i i < ) l ^ (cTa^sa'sAtof-fordinalss i s definable (Z{-definable) i f the cl a s s of structures K ={{ M : M - < a, < > for some a eAA} i s definable ( z j-definable). Theorem 3.1.4 : The following are equivalent: (I) The c o l l e c t i o n of f i n i t e sets i s Z{-definable i n L*. ( i i ) < to, < > i s Z{-definable i n L*. ( i i i ) There i s a c l a s s of ordinals A Z{-definable i n L* which contains an i n f i n i t e o r d i n a l . Proof: ( (i)' implies ( i i ) ): Let tj) be the Z { - d e f i n i t i o n of the c o l l e c t i o n K of 19 f i n i t e sets. We suppose 9 i s a sentence of the language L = L^. Thus a W unary r e l a t i o n symbol occurs i n 9 and the f i n i t e set M e K i f f M = U for some W such that W t= 9. We may, by the isomorphism property of D e f i n i t i o n 1.2.1, assume that M i s an i n i t i a l segment of the integers. For each n < co there i s an 9 with II/' 1 1'!' >_ n. I f the language L = { \/ , U, R^,..., f^,...} then consider the language K = {\f , V, U', Rj,..., f j , . . . } and the 1-morphism with constant d e K such that V I > v u 1 * u' Rj 1 > R^ ... etc. We write <j>'(d) f o r 9 . We take the indexed union W of { W : n < co } to io n form a K-stfucture (see Examplell.1.6). The universe of W w i l l be the 00 set U N n U co. Expand K to the language = K(W, :<•) where III i s a unary and < a binary r e l a t i o n symbol. Let be the conjunction of the following two K* sentences: " < i s an i n f i n i t e l i n e a r ordering of W " V x [ W ( x ) * 3y(9'(y) A Vz(z < x + D ' ( z , y ) ) i | . We show two things: (a) that has a model and (b) i f ( M, W, <) i s a model of i\i then < W, < > - < co, < > (a) Consider the structure ( W , co* < ) for K(W, <) (here < i n ( Ws, co, <)) CO CO A^y? Jvn i s the natural ordering on co) . I f a e 55 'thenritafiollowsLthaC a_e U f o r < -somein.! Let n be the i n t e r p r e t a t i o n of y i n hi . C l e a r l y i f b < a then co Wnn W b e U , i . e . (U') w(b9n)'.sholds?.reTherefbrestheesentence IJJ holds i n ( Wu,.u, < )• (b) Let ( W, W,_-< ) be a model of \\>. To show <JW, -< > = < co, < > i t i s only necessary to show that each a e W has a f i n i t e number of predecessors. If • b e W i s such "that ( W, b ) ^ 9 '(d) then a l l the predecessors of a are i n X = { z : <z, b> e (U')^ }. But then M = ( W, b ) ~ a i s a model 20 of <f> with = X and so X i s f i n i t e . This f i n i s h e s i((i) implies ( i i ) ) . ( ( i i ) implies ( i i i ) ) 1 : This i s t r i v i a l . Let A = { oi } and the r e s u l t follows from the d e f i n i t i o n s . ( ( i i i ) implies ( i ) ) : Let A be a c l a s s of ordinals E{-definable i n L* and l e t i> be the z{-def ini'tioniof A. So \p contains the unary W and the binary < and M j ^ ij; implies < W^ , <^ > i s well-ordered. Add a unary r e l a t i o n symbol to the language L = L^ to form L^.(U) and and l e t <f> e L^(U)* be the conjunction of if) and \/x(U(x) -> W(x)) \/xyy(U(x)Ay < x ->UU(y)) Vx[u(x)/\3y(y < x) ->3y(y < xA\/z<v(y <zz <xx)))] Then a set M i s f i n i t e i f f M = for some hi <j> so <J> i s an z { - d e f i n i t i o n of the c o l l e c t i o n of f i n i t e sets. This theorem t e l l s us that < o), < > i s not Ej-definable i n L 1 0)0) If i t were then there would be an L sentence <j> containing the unary symbol U that I^-defines the c o l l e c t i o n of f i n i t e sets. Let d> be the sentence: J- n /\u l^)l\...l\w(%)) Then the set of sentences { <f> ? n ? o) } would have no model even though every f i n i t e subset has a model. And t h i s contradicts the w e l l known compactness property of L 0)0) In many of the other examples of l o g i c s given i n Chapter One < o) < > i s definable hence E{-definable. Example 3.1.5 : L — s e c o n d order l o g i c . Consider the following sentences: (i) " < i s a t o t a l ordering" ( i i ) V X 3 y V x ( y e X A x e X - > y ^ x ) ( i i i ) V x 3 y ( x < y) 2 1 ( i ) , ( i i ) and ( i i i ) say i n t u i t i v e l y that < i s a we l l ordering with no largest element. (iv) Vx[3y(y < x) -> 3y(y < x /\Vz^(y < z <xx))J (iv) says i n t u i t i v e l y that each element has an immediate predecessor i n the ordering <• Let <j> be the conjunction of these four sentences. Then < A,<<>>=is a smddel of 9 i f f < A, < > - < co, < > so 9 i s the L d e f i n i t i o n of < co, < >. Example 3.1.6 : ^-(QQ) ~ l o g i c with the q u a n t i f i e r ' there e x i s t s i n f i n i t e l y many'. Let 9 be the conjunction of the sentences: " < i s a t o t a l ordering", Vx(^Qgy(y < x ) ) , Q Q X ( X = X ) • Then < A, < > i s a model of 9 i f f A i s i n f i n i t e , < well orders A and there are only f i n i t e l y many predecessors of any a e A. Consequently < A, < > i s isomorphic to < co, < > and 9 i s the 4(QQ) d e f i n i t i o n of < co, < >. Example 3.1.7 : For the d e f i n a b i l i t y of < < > i n the l o g i c L see 4.1. c u^ co D e f i n i t i o n 3.1.8 : An o r d i n a l a i s L*-accessible i f a e A for some clas s A of ordinals that i s E^-definable i n L*. In L the definable and accessible ordinals coincide: they are coco j u s t the f i n i t e o r d i n a l s . C l e a r l y every f i n i t e o r d i n a l i s definable and therefore accessible. By the previous theorem i f an i n f i n i t e o r d i n a l were L - a c c e s s i b l e then < co, < > would be Y,}-definable: t h i s , as was noted coco 1 ' above, i s not the case. The following theorem i s an important r e s u l t f o r obtaining new L*-accessible o r d i n a l s . Theorem 3.1.9.: Let A be a clas s of ordinals which i s EJ-definable i n L*. Then (i) the cla s s of ordinals A' = { a : a < 3 f o r some 3 eAA}. i s 22 E^-definable i n L*. ( i i ) i f A i s a set and g = sup{ a :aa e A} then g i s L*-accessible. Proof of (i ) : Let a) be the E { - d e f i n i t i o n ofAA. Thus <f> contains a unary symbol U and a binary symbol <. a e A i f f < a, < > ^ ( U^, <^ ) for some W such that Wt=<}>. Let U', <' be new unary and binary r e l a t i o n symbols res p e c t i v e l y and l e t ^ e L (U',<') be the conjunction of the following two sentences: V x ( U ' ( x ) •> U ( x ) ) " <' i s the reduction of < to U' " M M Then i f y _< a f o r some a e A then § y, < > - !( U' , < ) f o r some M such that M |= . ( M i s obtained by modifying the above structure N.) Proof of ( i i ) : Because A i s a set g = sup{a: a e A} i s indeed an o r d i n a l . By part ( i ) we may assume that A = g = { a : a < g } . Let <|> be the £*-definition of A (as i n part ( i ) ). If L = ( V , U, <,...} l e t K = { W,V, U', R,...} <P and l e t a : L, -> K be a 1-morphism with constant d such that 9 I > v u D i >u' < I » R ...etc. Ct Write <<f>'(d) for (j> . Expand K to form the language K(W, -4 ) (where W i s unary and binary). Let 6 be the conjunction of the following two K(W, •< ) sentences: " ^ i s a l i n e a r ordering of W " Vx[w(x) + 3y(<f>(y) A Vz(z < x + R(z,x, y)))] As i n the proof of the previous theorem we must show two things: (a) M 9 implies i W^ , j- i s well-ordered and (b) There e x i s t s a M|=. 0 such that i , J- - < g, < > . (a) Suppose M = ( N , W^, ) where H i s an K-structure. Assume that Mt= 90and < ifT^, ^ § i s not well ordered. Then there e x i s t s an i n f i n i t e 23 descending chain a-j^V a ^ ' '' where each a^ e W^-. Let a be the i n t e r p r e t a t i o n of y i n W such that 9(a) and b'^a-J implies R^Cb.a^a). This implies b < a^ i n W . L e t t i n g b = a^, a^,...etc. we get a chain a^ > a^ > a^ > ... i n N . Since < w e l l orders W t h i s i s a co n t r a d i c t i o n . M MM Hence < W , ^ > i s well ordered. (b) We must f i n d M such that M|= 6 and < W^ , -^'> - < 3, < >.ZFbr each a < 3 there i s an W such that W <j> and < U^ a, -c^01 > - <aa, < > . Let a a 1 W be the indexed union of the { W : a £ .3 }. Then ( W , 3, < ) i s a model P Ot p of 9. For i f a e 3 '('i.e. a < 3) l e t a+1 be the i n t e r p r e t a t i o n of y i n W_. p Then y < a implies y < a i n W + j so that R^(Y,a,a+l) . We close t h i s section with some d e f i n i t i o n s and examples. D e f i n i t i o n 3.1.101-!: The l o g i c L* i s bounded (respectively bounded by 3) i f every zj-definable class Afof. ordinals i s bounded '(respectively bounded Byb 3) . Note: bounded here means s t r i c t l y bounded. D e f i n i t i o n 3.1.11 : If the l o g i c L* i s bounded by some 3 then wo(L*), the w e l l ordering number of L*, i s the l e a s t such 3. Example 3.1.12 : As was noted e a r l i e r the only csets of ordinals z j-definable i n L must consist of f i n i t e l y many f i n i t e o r d i n a l s . Hence L i s 0)0) 0)0) bounded by 00; i n f a c t , wo(Lo)O)*) = o> . 0)0) eExample 3.1.13 : The l o g i c I? (second-order l o g i c ) i s not bounded and therefore wo(L^) i s not defined. This i s because the cla s s A of a l l ordinals i s definable hence Z^-definable by the sentence <f> which i s the conjunction of: " < i s a t o t a l l i n e a r ordering " V x - [ y J y ^ x y e e x r A V x ( x e x •+ y •_< ) ) 24 3.2 Lindstrom's Theorem The main r e s u l t of t h i s section i s Lindstrom's Theorem. This theorem outlines conditions that characterize f i r s t - o r d e r , l o g i c i n the sense that any l o g i c that s a t i s f i e s these condition must be equivalent to f i r s t -order l o g i c (the meaning of 'equivalent' w i l l be made p r e c i s e ) . A c t u a l l y a more general r e s u l t i s established that s p e c i f i e s conditions which char-a c t e r i z e l o g i c s i n terms of the hierarchy L , where K i s a c e r t a i n type of i n f i n i t e c a r d i n a l . Let L* be a l o g i c on a c o l l e c t i o n C of languages. In t h i s section we s t i p u l a t e another assumption that a l o g i c w i l l be required to s a t i s f y i n a d d i t i o n to those givai i n Chapter One: Assumption 4 : Let <|> be any L* sentence. Then the set L^ i s f i n i t e -only a f i n i t e number of symbols occur i n d>. The motivation for Assumption 4 w i l l become apparent i n the proofs of the r e s u l t s of t h i s s e c t i n . Let L* be a logicaon C and l e t L be a language o f C. I f M and W are two L-structurestthen M and W are said to beeelementarily equivalent with respect to L*, written M =^ W, i f the same set of L* sentences i s true i n both structures. D e f i n i t i o n 3.2.1 : The l o g i c L* has the Karp proprty i f f o r a l l languages L i n C, and a l l L-structures M and N , i f M = M then M = M i . e . p a r t i a l P * isomorphism implies elementary equivalence.(see Chapter Two f o r an account of p a r t i a l isomorphisms). / Ddiinition 3.2.2 : The l o g i c L* has the Lowenheim property i f every L*-sentence a) which has a model has a model of power <_ . 25 Theorem 3.2.3 : If L* has the Lowenheim property then i t also has the Karp property. Proof: Suppose L* doesn't have the Karp property and l e t L be a language with structures M „ and M, such that M . - M, but f o r some <b e L* 0 1 0 p 1 MQ (= 9 and M j t = ^9 We assume L = L, and hence i s f i n i t e (by Assumption 4). Enrich L to form <P the language K = L(U,W,E,p) where U and W are unary r e l a t i o n symbols, E i s a binary r e l a t i o n symbol and p i s a binary (pairing) function symbol. We write <x,y> for p(x,y) and <x,,...,x ,x f o r p(<x,,...x >,x , ..) . J 1 n n+1 r 1 n n+1 Let iji e L(U,W,E,p)* be the conjunction of the following sentences: (1) 9 U and (S>) W (see Example 1.2.3) (2) Vxyu [E(x,y) AU(u) -> ]w(W(w) A E(<x,u>,<y,w>))]. (3) Vxyw [E(x,y) A W(w) -»• 3u(U(u) A E(<x,u>,<y.w>))] . (4) For each n-ary r e l a t i o n symbol R the sentence: Vxj_.• -x^.--y n [E(<X X,.. '\ > > < y l >• • -y^) n + .^^(x.) «-> W(y±)) A R(xlS...xn) R(ylf...yn)] . (5) For each n-ary function symbol f the sentence: V x r . . x n y r . .y n [ E ( < x l S . - ., V V l ^ l ' " ' * 'Wn+l^ n+1 .AdKx.) - w(y.)) Af(x i s...,xn) = x n + 1 -> H y 7 J - y ^ Note that because L J i s f i n i t e only f i n i t e l y many sentences a r i s e i n (4) and (5). Thus by our assumptions on the l o g i c L* the conjunction ^ i s indeed an L*-sentence. We show that IJJ has a model W. The universe of W w i l l be the set: N = MQ(J ^ where MQ i s the universe of MQ and i s the universe of . 26 Let p be any i n j e c t i v e map from N N into N and l e t U = MQ, W . W M . • W Define E as follows: E (<x, ,. .. ,x >, <y_ ,. .. ,y •>). i f f x.,...,x et:U , J L . n l n i n y y e and there i s a p a r t i a l morphism from M- to M, such that ^ 1 n 0 1 W x, I >y,> • x I »y . Define R as follows: 1' 1 n 1 n R^(x..,... ,x ) holds i f f x,,...,x e M„ and R^0( x ,...,x ) or I n 1 n U I n Mi x l 5 . . . , x n e and R 1 ( 2 ^ , . . . . x ^ ) . W Define f as follows: i f x, .... ,x e M» then f^(x, ,. . .x ) = f ^ ( x , ,.. . ,x ) 1 n 0 1 n I n i f x. x e M, then f^(x,,...,x ) = f ^ i ( x , x ) I n 1 I n 1 n otherwise define f a r b i t r a r i l y . Since MQ = ;viM^ sentences (2)-(5) i n the conjunction of \p hold i n W. And because 'MQ|=9 and M^ |= ^9 ip W i s indeed a model of ip. Assume now that the l o g i c L* has the Lowenheim property. Then there e x i s t s a model, WQ f o r ip of c a r d i n a l i t y _< J ^ 0 • l e t a : L -> L(U,W.E,p) be the 0-morphism which i s the i d e n i t y except that a(V) = U. Let g : L L(U,W,E,p) be the a 0-morphism which i s the i d e n i t y except that a(V) = W. Then W~a i s a — 3 countable model of 9 and WQ i s a countable model of ^9. Moreover•, _ the c o n j . u n c £ i o n - o f r . ( 2 ) ^ : ( 5 ) x i n v ; t h e 7 f o r m a * i o n o f to e n s u r e ^ . t h a t i N x s ' : s t f N , . ,T 0 p 1 By the c l a s s i c a l r e s u l t given i n Chapter Two (Theorem 2.3 ) p a r t i a l l y isomorphic countable structures are isomorphic. Hence WQ - . Since WQ b= 9 and W.^ |= H t h i s i s a cont r a d i c t i o n . Thus L* does have the Karp property. This r e s u l t t e l l s us that a large c l a s s of l o g i c s have the Karp property. For instance, i t i s w e l l known that L s a t i s f i e s the Lowenheim 0)0) property and i t i s shown i n [4] that L ( Q Q ) (see Example 1.2.6) does also. By the above theorem both these l o g i c s have the Karp property. The converse of t h i s theorem i s f a l s e : as was noted i n Chapter Two L has the Karp °°o) property; however, i t doesn't s a t i s f y the Lowenheim property. The next d e f i n i t i o n gives a p a r t i a l ordering on the cla s s of a l l l o g i c s . D e f i n i t i o n 3.2.4 : Given l o g i c s L*aand L# on the same c o l l e c t i o n C of languages we say that L# i s as strong as L* and write L# >_ L* i f for every L*-sentence 9 there is. a /.^-sentence ij; such that: (i ) Q_ , i . e . , every symbol occurring i n d) occurs i n <j>. ( i i ) Mh=* d> i f f M br# ib for a l l L -structures M. 9 We say L# i s stronger than L*, and write L# > L* , i f L# _> L* but not L* > W . If L* > L# and L# _> L* we write L* = L# and say that L* and L# are equivalent. The assumptions l i s t e d i n Chapter One ensure that L < L* for wio — a l l l o g i c s L*. Also, i t i s c l e a r that L < L for a l l i n f i n i t e c ardinals acu — °°u) ai The following theorem contains the key r e s u l t of t h i s chapter. It provides a more precise measure of the strength of c e r t a i n l o g i c s . Theorem 3.2.5 : Let K be a c a r d i n a l such that K = | . (For the d e f i n i t i o n of 3 see Chapter Two.) If L has the Karp property and wo(L*) j< K then '•fi the l o g i c L i s as strong as L*. KOJ Proof: Assume i s not as strong as L* and suppose L* has the Karp property. We show that K i s L*-accessible; t h i s contradicts the condition wo(L*) < K . Because L i s as not as strong as L* there i s an L*-sentence — KOJ <i) which does not have the same models as any sentence of L . ' KO) Claim: For each a < K there are L -structures M, W with M hi, M\=.*^$ KO) and hi !=*'">(()•. 28 V e r i f i c a t i o n : suppose the claim were f a l s e . Then there would be some a < K such that M =.a W, M k=* 9 implies f/l=* 9 for a l l L -structures L 9 KU) M and W. By Theorem 2.8 M E^a W i f f W]=a^j (here |= denotes the semantic KU) i m p l i c a t i o n r e l a t i o n with respect to the l o g i c !„,,). Hence we would have °°U) W|=a^, M>=*99 implies W M 9 for a l l L^-structures M, N. Consider the sentence V { oj^ j : M t = * 9 }. By Theorem 2.10 i t i s a sentence of L ( t h i s i s where the assumption K = ~| • i s used). I f W i s a model of KU) K ^ K t h i s sentence then M t= a?, f o r some L - s t r u c t u r e M such that M l=* 9. By M 9 the above comment thisggives Wt==* 9. S i m i l a r l y , i f W |= * 9 then (since N|=ojJ ) W|= V( ajjj : M l=* 9 }. Thus i f the above claim were f a l s e <b would have the same models as \J{ a?, : M \=* 9 }, a sentence of L , • M KU) and t h i s contradicts our assumption on 9. This establishes the claim. Using Theorem 2.6 we can rephrase the claim as follows: For each a < K there are L,structures M and W such that 9 (i ) Mr=5 9, Wt=* «u9 ( i i ) There i s a sequence 1^ 51^=? • • • 21^2 • • • 2 I'a where',-for each 3 < a, I i s a nonempty set of pi'Somof.pbismslb,eitweenW£p.artial p substructures of M and W. This sequence has the following property: (*) i f g+1 < a and F e I , then f o r each a e M (respectively b e N) there i s a G e l . with F E G and a e domain(G) (respectively b e range(G)). p We now proceed with the proof. The technique resembles that used i n proving the previous theorem. Let K be the language obtained from by adding 9 the following new symbols: U, WQ , W.-J,, ( a l l unary), < (binary), p (a binary p a i r i n g function symbol),and E a 3-ary r e l a t i o n symbol. We construct a sentence \> of K* such, that: ( i ) i f Wt=* i|> then < U^, i s a well-ordering 29 and ( i i ) for each a < K there i s a model N 1=^ * <f> with < U^, <^ > of order type a. I t w i l l then follow from Theorem 3.1.9 of the previous section that K i s L*-accessible. ipeis the conjunction of the following sentences: (1) 9w 0 a n d QH)Ui (2) " < i s a l i n e a r ordering of U " (3) " p i s a pa i r i n g function " (4) " i f E(c,x,y) and c' < c then f o r every a e WQ there i s a b e and for every b e W^ there is. an a e WQ. such that E(c',<x,a>,<y,b>). (5) For each n-ary r e l a t i o n symbol R: 1 1 i f E(b,<x^,...,x >,<y^,...,y >) n and U(b) then A^Wn^) / ^ ( y ^ ) and R ^ , . . . ^ ) R ( y i , . . . , y n ) " (6) Similar to (5) except for function symbols f. The notaMemG£x..y.;>.v.yX' S-.cis.'-thi - same.-, as twas used iiidfche pr.oof-of Theorem . . . I n • 3.2.3 . Our assumptions on a l o g i c ensure that \p i s indeed an L*-sentence. Now for each a < K using condition (*) above i t i s easy to construct a model hi of such that hi l =* ijj and < U^,<^ > - < a, < > (condition (*) i s used i n s a t i s f y i n g (4),(5) and (6)). The construction of hi i s s i m i l a r to the construction given in.Theorem 3.2.3. We need only show that hi (=* hi hi implies that < U , < > i s a we l l ordering. Suppose there was some W X C u with no le a s t element. Using X we can define a set I of p a r t i a l morphismsffrom hl^& to,,;W^l^ . I consists of a l l p a r t i a l morphisms F such that for some b e X, F i s given by: hi >y^,...,xn| )y.^ where E (b,<x^,. . . ,x >,<y^,. .. ,y >) . Because X has no le a s t element. I has the back and f o r t h property. Hence and are p a r t i a l l y isomorphic, I : hl^1^ ~ p ^ W ^ • S i n c e L* n a s t n e Karp property t h i s gives W ( W o ) W ( W1 } . But W ( V F=* <f> and W ( W l } r = * H , 30 W W t h i s a c o n t r a d i c t i o n . Thus < U , < > i s well-ordered. We have shown that K i s L*-accessible and t h i s completes the proof. If we l e t K = GO i n the above theorem we obtain Lindstrom's Theorem which i s a c t u a l l y a c o r o l l a r y to the above r e s u l t . Theorem 3.2.6 (Lindstrom)c.:T Let L* be a l o g i c on a c o l l e c t i o n C of languages. If L* has the Lowenheim property and e i t h e r of the properties stated below, then L* = L LOU) (a) (Upward Lowenheim-Skolem) : If a sentence 9 '.of L* has an i n f i n i t e model then i t lias an uncountable model. (b) (Countable Compactness) : If T i s a countable set of sentences of ft f b r f o r any.nLCinnS andeif-revery.ifinitessubsetTofaT hasoaeihodel then modeT.has a model. Proof: . Observe f i r s t that because of our assumptions on a l o g i c L*, L* i s always stronger than L . Also, since L*mhas the Lowenheim property by Theorem 3.2.4 i t has the Karp property. We show that conditions (a) or (b) imply that wo(L*) <_ GO ; by the previous theorem t h i s gives L, > L* . coco — I t was shown i n an argument i n section 3.1 that the E ^ - d e f i n a b i l i t y of < co, < > dunkls*. makes countable compactness f a i l . So (b) implies wo (!'*) < co. As sume now that (a) holds and suppose < coi < > i s Z,-definable by an L*-sentence 9 containing the unary U and binary <. Let ip be an L*-sentence which says that f i s an i n j e c t i v e function with range contained In U. C l e a r l y the conjunction of 9 and UJ have only countable models and t h i s contradicts (a) . Hence < co, < > i s not Y.\-definable i n L*. 31 CHAPTER FOUR HANF NUMBERS AND WELL-ORDERING NUMBERS-In t h i s chapter we continue our i n v e s t i g a t i o n of general l o g i c s . We w i l l examine the analogues i n the general s e t t i n g of the f a m i l i a r compactness and Lowenheim-Skolem theorems of the f i r s t - o r d e r predicate calculus. We assume that a l o g i c L* on a c o l l e c t i o n C of languages i s as defined i n Chapter One; hence a l o g i c s a t i s f i e s the four properties and three assumptions given there. We w i l l , however, not require that a l o g i c s a t i s f y Assumption Four s t i p u l a t e d at the beginning of Chapter Three. That i s , we drop the requirement that an L*-sentence 9 must contain only f i n i t e l y many symbols. 4.1 D e f i n i t i o n s and Preliminaries The f i r s t d e f i n i t i o n of t h i s section gives a generalization of the Upward Lowenheim-Skolem property. D e f i n i t i o n 4.1.1 : The Hanf number of a l o g i c , w r itten h(L*), i s the le a s t c a r d i n a l a such that i f an L*-sentence 9 has a model of c a r d i n a l i t y _> a then i t has a r b i t r a r i l y large models. More generally, h.(L*) i s the le a s t a such that i f a set E of L*-sentences with c a r d i n a l i t y ( E ) j< 'X has a model of c a r d i n a l i t y _> a then E l has a r b i t r a r i l y large models. Note that i n general the Hanf number of a l o g i c need not ex i s t ( a l l a t e r example shows this) -*. C l e a r l y h, (JL ) = co for a l l cardinals A: A coco • " 32 t h i s i s the content of the Upward Lowenheim-Skolem theorem for L toto R e c a l l the d e f i n i t i o n of wo(L*) given i n 3.1.11. wo(L*), i f i t e x i s t s , i s the l e a s t o r d i n a l t, which i s an upper bound for any cl a s s A of ordinals zj-definable i n L*. wo(L*) i s also c a l l e d the well-ordering number of the l o g i c L*. The next d e f i n i t i o n provides a gene r a l i z a t i o n of the well-ordering number to sets of sentences. D e f i n i t i o n 4.1.2 : Let X be a c a r d i n a l . Suppose t, i s an ordinal.cwith the following property: If Z i i s any set of <_ X L -sentences containing the binary r e l a t i o n symbol £ and M i s a model i n which <^ well-orders i t s f i e l d i n order-type >^ £, then Z has a model W i n which <^ i s not well-ordered. Then wo((L*), i f i t e x i s t s , i s the l e a s t o r d i n a l ? with t h i s property. A In the case X = 1 t h i s d e f i n i t i o n i s equivalent to our o r i g i n a l d e f i n i t i o n , i . e . wo^(L ) = wo(L*). In t h i s chapter we w i l l f i n d i t convenient to work with t h i s new d e f i n i t i o n of the well-ordering number of a l o g i c . In Chapter Three the compactness property of L was used to show that wo(L^) = co. Iii f a c t , the well-orderingnnumberoofaallggic i s c l o s e l y connected with compactness properties. Some evidence for t h i s i s provided by the next theorem.. Theorem 4.1.3 : Let L* be a l o g i c on a c o l l e c t i o n C of languages and l e t L be a countable language i n C. Then the following are equivalent: (i ) (Countable Compactness) If each f i n i t e subset of a countable set E of L -sentences has a model, then Z has a model. ( i i ) (wo((L*) _< to) Assume L contains the binary symbol ^ and l e t 33 ft X be a countable set of L -sentences- Suppose that f o r each p o s i t i v e integer n, Z has a model M such that <^ well-orders i t s f i e l d i n W order-type >_ n. Then Z has a model W such that < i s not a w e l l -ordering. ffirodf; ( (i ) implies ( i i ) ): Consider the set X(J { c n + 1 < c n : n e co }. By compactness and the assumptions i n ( i i ) t h i s set has a model M. The M M give an i n f i n i t e descending chain i n M so < i s not a well-ordering. ( ( i i ) implies (i) ): Let A 0 , 4l5... be countably many L*-sentences and suppose that for a l l n, {<f>0, • • • »* } has a model. Let U and < be new unary and binary r e l a t i o n symbols re s p e c t i v e l y . Let Z be the set of sentences of L(U,<)* consisting of the following: "U i s f closed" f o r each function symbol f i n L " I f the f i e l d of < has more than n elements then A ^ " " for each p o s i t i v e n integer n . Far each n, i f M i s a model of { A . , . . . , * we can construct a model M of v n—1 n Z. The universe of M w i l l be MU {0,1,... ,n-l}'. The f i e l d of < i n M n n w i l l be {0,1,...,n-l} with the natural well-ordering. By ( i i ) there i s a model W of Z i n which <^ . i s not well-ordered. Thus the f i e l d of <^ i s i n f i n i t e and so W i s a model of A ^ for a l l n. Taking the U-reduct of n W we get a model of { d ) 0 , A , . . . } . Our aim l a t e r r i n t h i s chapter w i l l be to examine what r e l a t i o n s h i p e x i s t s between the Hanf and well-ordering numbers of a l o g i c L . The Upward Lowenheim-Skolem theorem for L ^ i s u s a l l y proved using compactness. We w i l l discover that the s i z e of the Hanf number of many general l o g i c s i s determined by t h e i r well-ordering numbers. Indeed, our r e s u l t s may be 34 viewed as a welcome extension of f i r s t - o r d e r model theory i f the following two 'equations' are accepted: Hanf number = generalization of Upward Lowenheim-Skolem property . well-ordering number = general i z a t i o n of compactness property. We w i l l focus our attention on the l o g i c s L + and L(Q ) KTOJ a introduced i n Examples 1.2.8,1.2.6. (If K i s any ca r d i n a l then K + denotes the next l a r g e s t c a r d i n a l , eg. co+ = tOj)) A small digression i s necessary to provide f o r future reference c e r t a i n r e s u l t s about these l o g i c s . The next two theorems are Downward Lowenheim-Skolem r e s u l t s f o r the l o g i c s L + and L(Q proofs of the theorems may be found i n < w a [ l l ] and [4 ] . Theorem 4.1.4 : (Downward Lowenheim-Skolem Theorem for L + ) Assume KMO that M i s a model of the L + -sentence d>. Let M„ d M and suppose |MQ| + K < p < [MI. Then there i s a structure W such that WCM, NJ=d>, M Q C N and |N| = y. Theorem 4.1.5 : (Downward Lowenheim-Skolem Theorem for L(Q )) Let K = to . " a a Assume M i s a model of the set Z of 1(0 )-sentences where III < K. Let a 11 — MQ M and suppose |MQ| +• K .<_ u <_ |M| . Then there i s a structure W such that WCM, W.J=Z, M Q ^ N and |N| = y. We now show that well-orderings of the form < t,, < > are definable i n i + f o r any o r d i n a l t, < K +. Suppose L i s a language containing only the binary r e l a t i o n symbol < and the constant symbol c. For each t, < K + we define sentences d> (c) and il) of L ± such that : t, t, K'IO -35 (i) For a l l L-structures M and a l l a e M (M,a) |= • (c) i f f < {b:b e M, b < M a}, < M > ( i i ) For a l l L-structures M, M(= ip^ i f f H'M - < C, < >• The d e f i n i t i o n of <j>^ (c) proceeds by recursion. Suppose ^ ( c ) has been defined f o r a l l ri < ?• Then <l)^(c) i s the sentence l ^ A ^ y X y < c A^Cy))] A [Vy(y <xe V ^ y ) ) ] The sentences u) are then defined i n terms of the <f> ( c ) : C n A straightforward induction argument shows that ( i ) and ( i i ) above hold. The sentences t e l l us immediately that WO(L,K-)_^) >^ K +. They also show that the Hanf number and well-ordering numbers need not e x i s t f o r a given general l o g i c . More s p e c i f i c a l l y , since UJ isaan -sentence f o r a l l ordinals t i t i s c l e a r thatth(£ ), wd(L ) are both undefined. . °°U) °°U) We close out t h i s section with some observations which w i l l be us e f u l l a t e r . ( i ) There i s a sentence cj>0 of 1^ +^ which only has models of c a r d i n a l i t y K. ( i i ) I f K = a)^ then there i s a sentence ^ of ^ ^ a ^ having only models of c a r d i n a l i t y K. To v e r i f y ( i ) take <j> to be the sentence ip defined above. For ( i i ) take U K <J>0 to be the conjunction of the following £(Q^)-sentences: "<< i s a t o t a l ordering " Q x(x = x) a-Vx^Q^y(y < x) These sentences also serve to show that K ( L + ) > K +, h(l(Q ) > K +. K a) — a — 36 4.2 Existence Theorems The main r e s u l t of t h i s section employs an argument of Hanf ( [ lo]) to show that the Hanf number of a large c l a s s of l o g i c s e x i s t s , ft Assume L i s a l o g i c on a c o l l e c t i o n C of languages. Let L ft be a language i n C and suppose that L , the cla s s of sentences of L, i s a set. For each Z £E L* with |z| <_ X (X accafdinal) define K by: 0 i f Z has a r b i t r a r i l y large models KZ = sup{ |M| : M {= Z } otherwise. Let K = sup{ <t : Z£E L , |Z| <_ X }T Because L i s a set, an a p p l i c a t i o n of the set theor e t i c axiom of replacement shows that i s a c a r d i n a l . The A-Hanf number of the l o g i c L*, i f i t e x i s t s , w i l l equal sup{ : L a language i n C }. A We now prove that f o r many l o g i c s t h i s supremum does i n f a c t e x i s t . ft Theorem 4.2.1 (Hanf) : Assume that a l o g i c L on a c o l l e c t i o n C of languages s a t i s f i e s the following properties: ( i ) The number of symbols occuring inaany t*-sentence i s bounded. i . e . , there i s a c a r d i n a l u such that f o r each L*-sentence d> IL^I < p. 9 — ( i i ) L i s a set for a i l h L i n C. Then h((L*) e x i s t s f o r a a l l X. A Proof: We construct a language K N such that K\ < K^8 for each L i n C. U A : A (We are assuming the c a r d i n a l X i s f i x e d ) . I n t u i t i v e l y KQ w i l l contain within i t a copy of each of the languages L. More p r e c i s e l y , f o r each p o s i t i v e integer n the set contains y X n-ary predicate symbols and 37 y X n-ary function symbols. Assume now L i s any language i n C. I f E i s a set of _< X L -sentences we show that K _< K 0 . Let a be a 0-morphism from L to K Q such that a : V I ' V. Define E a = { a) a : a) e S }. If M i s any model of I i t i s easy to construct from M a K^-structure W such that: (a) W~a = M and (b) W1= z " . By (a) |M| = |N|. Because K* i s a set, K^O e x i s t s and |M| = IN| <_ icfo . Hence K < K^O and so i t follows A A L A L j. * i i Kn that K = sup{ KT' : E £ L , | E | < X } < K u . Since t h i s i s true for any A L A language L i n C, h (JL*) = sup{ : L i n C } e x i s t s . A A Example 4.2.2 : (Application to L . , L(Q )))Assume that the l o g i c s L + and L(Q ) are defined on a c o l l e c t i o n C of languages and assume that a L + , L„ are sets f o r each L i n C (L + ,L„ denote L f o r the l o g i c s KTU) Q K GO Q a a L + , L(Q ) r e s p e c t i v e l y ) . I f <k> and i> are sentences of L + aand 1(0 ) K co a KCO a resp e c t i v e l y i t i s c l e a r that cardinality({symbols occuring i n 9}) < K + cardinality({ fsymbols occuring i n < co. This these l o g i c s s a t i s f y the hypotheses of the above theorem and h (L(Q ) ) , A 06 h,(L + ) e x i s t f o r a l l X. X K CO Remark: We noted e a r l i e r that the Hanf number of L doesn't e x i s t . °°co The above theorem might suggest that the reason f o r t h i s i s that an L <»C0 can contain a r b i t r a r i l y many symbols. This, however, i s quite misleading. Let L*^ be the l o g i c obtained from L by adding the requirement that only f i n i t e l y many symbols occur i n each sentence of L . Then a l l of the °°co sentences \b. defined i n the l a s t section belong to L*„; consequently h(L* ) £ & °°to °°co i s undefined. The f a i l u r e of the existence of the Hanf number of .L and, °°a) 38 and L* i s a c t u a l l y an outcome of the following: given a language L the class L ^ of sentences of L i s not a set. No general method s i m i l a r to the above theorem i s a v a i l a b l e for determining whether wo(L*) exists-andaeachiclogic-must be investigated i n d i v i d u a l l y . Lopez-Escobar shows i n 13 that wo,(L ) ex i s t s f or a l l A aco cardinals A and a. The existence of wo((L(Q )) w i l l be a d i r e c t c o r o l l a r y A Ct of the reduction given i n Example 4.3.7 of the next section. We assume i n the future therefore that wo,(L + ) and wo,(L(Q )) both e x i s t . A KJTCOU) X a 4.3 Relationship of Hanf and Well-ordering Numbers In Chapter Two the beth cardinals were defined i n terms of ca r d i n a l exponentiation. An extension of t h i s idea gives r i s e to the generalized beth c a r d i n a l s . For each c a r d i n a l K and o r d i n a l t, the general 3K i i s defined by recursion as follows: l o = K' 3c " n.<?(2 n ) ' If K = 0 we get the usual beth c a r d i n a l s : 3^ = 3J|" Generalized beth cardinals are of i n t e r e s t to us here because they provide a connecting: l i n k between the Hanf and wellSordering numbers of many l o g i c s . That i s , for many l o g i c s L* the following r e l a t i o n holds: h,(L*) = ~ l K . For A -IWO^(L ) example,ssinee wo (L ) = h., (L ) = to, we get the r e l a t i o n A COCO A COCO CO h.(L ) = co = ' J = 1 ., A coco ^co -"wo, (L ) X LCOCO The next theorem provides a p a r t i a l r e s u l t i n t h i s d i r e c t i o n f or more 39 general l o g i c s . Theorem 4.3.1 Let A and K be cardinals with 1 <_ A <_ K and K i n f i n i t e . Assume that the l o g i c L* s a t i s f i e s the following properties: ( i ) wo AL*) e x i s t s . A ( i i ) There i s an L*-sentence 9 Q that has only models of power K. ( i i i ) Let E be any set of <_ X L*-sentences of some language L. I f the L-structure M {= E and M Q £ M then there i s an L-structure W such that: Nfr=E, NCM, M Q £ : N and | N | <_ |MQ(|! +KK. (This condition i s a Downward Lowenheim-Skolem property.) Then h (£?;) > JK . A — -*wo (L ) A 3?;poof: An easy argument shows that wo (L*) i s a l i m i t o r d i n a l . Hence i t A i s s u f f i c i e n t to show that for each L, < wo (L*) there i s a set E of < X A many L*-sentences that has a model of power ^ but not a r b i t r a r i l y large . models. Since £ < wo (L*) there i s a language L containing the binary A ft symbol < and a set E of _< X L -sentences such that: (i ) M |= E for some L-structure M i n which <^ well-orders i t s f i e l d i n order-type £. ( i i ) I f M F= £ then <^ well-orders i t s f i e l d i n order-type l e s s than wo (L A Let K be the language obtained from L by adjoining Uhand V (unary r e l a t i o n s ) , E (binary r e l a t i o n ) , and g (unary f u n c t i o n ) . The set E w i l l consist of the following K -sentences: v 9 for 9 e E Vx(V(g(x))A " g(x) E field(<) ") VxVy(Eyx -> g(y) < g(x)) Vx(U(x) -> "g(x) i s the f i r s t element of <") 40 Vx Vy(^U(x) A MJ'(y) A Vz(Ezx Ezy) -> x = y) We now show two things: (a) Mt= E implies |MJ _< (/.*)" ^ p a r t i c u l a r , X E doesn't have a r b i t r a r i l y models, (b) E has a model of power 3^-(a) I f Mt= E then M t= | V for a l l <f> e E. In the subset V M of M, < M w e l l -orders i t s f i e l d i n order-type n. < wo (L*)-. We assume n i s a l i m i t o r d i n a l ; the proof of (a) i n the case where n i s not a l i m i t o r d i n a l i s e s s e n t i a l l y the same. Let X. = and for 0 < g < n l e t X n ==P( U nX ). (For any set A (J g a<g a P(A) denotes the power-set of A). Set X = - U x . C l e a r l y cardinality(X)i g<n g i s equal to J . To prove (a) we define an i n j e c t i v e map f from M to X. M < 1 < " I The d e f i n i t i o n of f foraa e M 1 — MT] — -»wo (L ) A proceeds by induction on g^(a). I f g^(a) = 0 ( i . e . a e l / S f(a) = a. Assume M M M M f has been defined for a l l b such that g (b) < g < n. If g (a) = g then M f(a) = (f(b) : E ba} e X . The l a s t sentence included i n E ensures that f g i s i n j e c t i v e and t h i s proves (a). i I K (b) We construct a model M of E with |M| = ] . Let M^ be a model of E i n Mi which < i well-orders i t s f i e l d i n order-type £. As i n (a) we suppose t, i s a l i m i t o r d i n a l ; the other case i s treated s i m i l a r l y . Using hypothesis ( i i i ) we may assume that |£| j£ | | <_ |£| + K. By hypothesis ( i i ) there i s a model M2 of <j>0 with |M§J,±= KK- Let V M = Mx and U M = M 2 - Define X Q = U^ and i f g < z define X„ = P(LJ„X ) . Set X = V x „ . We assume that Mi i s embedded g a<g a' g<£ g 1 i n X so that MjS. X ( t h i s i s possible since | Mj_ |. _<_" | C | + < £ j x | ) . . The universe of M i s then M = X. If a e M l e t g be the l e a s t o r d i n a l such that a e X . g M M M Then define g (a) = g. Define E by E ab i f f g(a) < g(b). The structure M so constructed i s a model of E and |MI = This proves (b). 41 Remark: Let L* be a l o g i c f o r which h (L*) e x i s t s and assume L* i s bounded "N A (see D e f i n i t i o n 3.1.10). If L* s a t i s f i e s properties ( i i ) and ( i i i ) of Theorem 4.3.1 then the above proof can e a s i l y be adapted to show that wo (L*) e x i s t s A f o r each A <_ K. Evxample 4.3.2: (Application to L + , L(Q ) where K = to ) The r e s u l t s at <Tto a • a the end of section 4.1 show that the l o g i c s L + and L(Q ) s a t i s f y the hypotheses of the above theorem. Hence for each A <_ K h. (L + ) > -|K + h (L(Q )) > n K r l f n ,N . A K»V W OA^ K+UP ~ Jwo <L(Qa')) As mentioned e a r l i e r , we wish to obtain r e s u l t s of the form h(L*) = " 1 K st*\' ^ o r l o g i c s s a t i s f y i n g the hypotheses of the above theorem wo \ L ) • we need only show i n e q u a l i t i e s of the form h(L*) < ~T The l o gxcs — WO\L ) introduced i n the next d e f i n i t i o n , fl-logics, are designed for t h i s purpose, fi-logics are an invention of the l o g i c i a n Flum and our treatment of them i s taken from [ 8 ^ . (Note: we have a l t e r e d Flum's notation; he c a l l s fi-logics M-logics)) E s s e n t i a l l y an fi-logic i s j u s t L with semantic r e s t r i c t i o n s ' toco on the class of allowable structures. We w i l l see that L . and 1(0 ) can KVJO a be reduced i n some sense to these ft-logics; the r e s u l t s holding f or the l a t t e r can then be applied to the former. We assume throughout that a l l l o g i c s belong to some c o l l e c t i o n C of languages. Definition 4.3.3: Let L^ be a language and Q a class of L^-structures. Let U be a unary r e l a t i o n symbol not i n L^, Given any language L, an L-structure M i s said to an fi-model i f the following two conditions hold: (i ) L Q U (U> £ L. ( i i ) Let a : L n -* L be the i d e n t i t y map except that a : V l » U. Then 42 M i s a - i n v e r t i b l e and M = W for some W i n fi. Condition ( i i ) says simply that the L^-reduct of / i s a f u l l L^-structure isomorphic to some structure i n fi, i . e . each fi-model contains within i t a r e l a t i v i z e d reduct which l i e s i n Q. The fi-logic L(ft) i s then defined as follows. I f L i s any language the set of sentences of L, written L^, i s given by: <f> i f L Q U { U } £ L L L i f L . U - { U } £ L coco 0 For each L-structure M and L^-sentence <(>tthe r e l a t i o n fc=^ i s given by: M p= <j> i f f M i s an fi-model and M p= <ji . Ob Here fc= denotes the semantic entailment r e l a t i o n inubheafirst-order l o g i c L ( t h i s makes sense since any sentence of L„ i s f i r s t - o r d e r ) . coco Q, Observe that L(fi) i s not a l o g i c as defined i n Chapter One. For example, the r e l a t i v i z a t i o n property given i n Example 1.2.3 f a i l s . This, however, should cause no alarm: the ft-logics can be viewed as devices f o r e s t a b l i s h i n g r e s u l t s about more f a m i l i a r , genuine, l o g i c s . Lemma 4.3.4: Assume that a l l structures i n have the same i n f i n i t e c a r d i n a l i t y K . Then (a) V x U ( x ) has only fi-models of power K. (b) If E has an ft-model arid | E | _< K then E has an fi-model of power K. (c) wo^(L(ft)) e x i s t s f o r a a l l cardinals. A. Proof: (a) i f M i s an fi-model then = K. Thus M V x U ( x ) implies ————— Juj that |M| = 1^ 1 —Km •'• (b) Let M be an Q-model of E . Using the Downward Lowenheim-Skolem theorem 43 for L , take an elementary substructure W of M such that U ^ £ N and 0)0) | N | = K. W w i l l be an fi-model of E oflpower K. (c) By choosing the ca r d i n a l y large enough and taking a s u f f i c i e n t l y r i c h language i t i s possible to f i n d an L -sentence 9 such that U0) ,(U) M F = L 9 i f f (JIT ' ) f ^ - W for some W e Q Now suppose wo (L ( f t ) ) doesn't e x i s t . For each o r d i n a l c there w i l l be some A set E of < X L(Q)-sentences such that E has only ^-models M with <^ w e l l -M ordered and one with < i n order-type C. Form the L -sentence : ^ UO) 6 ' = ( A z ) A <>. Then the sentences 6 imply that wo(L ) doesn't e x i s t and t h i s i s a C F . yo/ contra d i c t i o n . Hence wo^(L(fi)) e x i s t s . A For the remainder of t h i s chapter i t i s assumed that each structure i n 0. has the same i n f i n i t e c a r d i n a l i t y K. Lemma 4.3.5: For each X < K, K, (L(f i )) >-~] , i , ^ w - A — —|wo.(,L(.fi;j A Proof: We modify the proof of Theorem 4.3.1 making changes necessitated by the f a i l u r e of the r e l a t i v i z a t i o n property f o r L(fi). Let the set E be as i n that proof and l e t V, E and g be new symbols. The set E consists of the following KL -sentences of L(V,E,g): 0)0) Vx(U(x) + V(x)) v For each 9 e E the f i r s t - o r d e r r e l a t i v i z a t i o n of 9 to V, <j> Vx(V(g(x))A"g(x) esfield.(<:):!!). el<r -. c f Vx(U(x) -»• "g(x) i s t h e l f irst?elemento<5f <") VxVy(Eyx -> g(y); < g(x)) VxVy(MJ(x)A ^U(y) A Vz(Ezx <-+ Ezy) -* x== y) 44 Applying the previous lemma, the res t of the proof proceeds i n a s i m i l a r fashion to the proof of 4.3.1. The next very important theorem provides the raison d'etre f o r fi-logics. Theorem 4.3.6: For each X < K h, (L(fi)) = ~1 /i^w • ~ X -"wo, (.HSJ)) A Proof: This theorem i s quite deep and the proof i s rather complicated. Since we are mainly interested i n app l i c a t i o n s of t h i s r e s u l t we give a very b r i e f sketch proof. D e t a i l s may be found i n [8j ;By Lemma 4.3.5 i t i s only necessary to show that h (L(ft)) < A 1~]K // /^ w • So l e t E be a set of < X < K sentences with an fi-model M of power _> ^ ] w o (L(fi))' t' i e ^ e a ^ s t o construct a r b i t r a r i l y large models of Z. . From the fi-model M a set-th e o r e t i c p a r t i t i o n r e s u l t of Erdos and Rado and the well-ordering number of i-(ft) are used to construct an fi-model W of £ containing an i n f i n i t e set X of elements i n d i s c e r n i b l e with respect to U. This means that any two f i n i t e sequences in-Xssa'tisfysthe same formulas with parameters i n U. An fi-model S of E of a r b i t r a r i l y large c a r d i n a l i t y i s then formed by throwing into the universe of I y > |N| new elements which behave as the elements i n X. The next two examples are applications of Theorem 4.3.6 to the l o g i c s L(Q ) and L + . In each case a reduction i s defined which allows a- KTCU us to transfer the r e s u l t s f o r ^ - l o g i c s to the above l o g i c s . Example 4.3.7: (Application to L(Q ) ) . Assume that K = to.. Let L„ = {<} a a 0 and l e t 0, consist of a l l the models of the sentence if) defined at the end of K 45 4.1. Thus the structure M = < M, < > e Q, i f f (i) |M| = K. ( i i ) < i s a l i n e a r ordering of M. ( i i i ) I f a e M then the set {b : b < a} of predecessors of a has c a r d i n a l i t y < K. F i x the unary r e l a t i o n symbol U. With LQ, Q. and U thus s p e c i f i e d we get an fi-logic L(Q). In the following discussion i t i s assumed that L QU { U } £: L for any language L under consideration. This assumption can always be j u s t i f i e d by expanding L ( i f necessary) to include L Q L H U } . Suppose L i s a language and 9 i s a sentence of L . Form the a language K by adjoining the r e l a t i o n symbols V (unary) and F (ternary) so that K = L(V,F). Let a : L K be the 0-morphism which i s the i d e n t i t y except that V I—*V. We f i n d a sentence i of L such that: coco (*) Models of 9 = {M~ a : M *= $} That i s , an L-structure W t r==f f() x 9 i f f W i s of the form ( M ^ ) p f o r some K-structure Miw'ith' M ( = 99. Result (*) thus gives the desired reduction of the i(Q a)-sentence 9 to the L(fi)-sentence $• F i r s t we o u t l i n e the idea behind t h i s reduction. We wish to replace a sentence of the form Q xd>(x) by the f i r s t - o r d e r sentence: a "There i s a 1-1 map from a subset of {x : V(x) and <fi(x) holds} onto the set U." 'v'Q^ tKx) i s replaced by the f i r s t - o r d e r sentence: "There i s a 1-1 map from {x : V(x) and cf>(x) holds} onto a proper i n i t i a l segment of U." The 1-1 maps referred to belong i n a c o l l e c t i o n which i s indexed using the ternary r e l a t i o n F. That i s , f o r each x an i n j e c t i v e map g^ from a subset 46 of V to U is given such that: g (y) = z i f f <x, y, z> e F. The precise details are now provided. To each sentence UJ of ^-(Qa) is associated by recursion a sentence \b* of L as follows: coco (i) = ifj i f 41 is atomic. ( i i ) CMJO* = 'V'Oli*), (^I v * 2 ) * = * * V*2 • ( i i i ) (3xij,(x))* = Bx(V(x)A^*). (iv) (Qa?n|>(x))* = 3yVz3x(V(x)A A^yxz). If the sentence is first-order then ( i ) - ( i i i ) ensure that \p* is just the relativization of i> to V. (iv) says that there is a map indexed by F from a subset of the set defined by ty* in V onto U. Given a sentence <f> of L we now define a f i n i t e set Z of f i r s t -ex order sentences. Z consists of the following sentences: (i) 9 * ( i i ) The sentence "F is an indexed collection of 1-1 maps from a subset of V into U" ( i i i ) For each sub'formula of a) of the form Q^XIJJ(X) the universal closure of 3y{ Vz 3 X [ ^ J * A V(x) A F(y,x,z)] V 3wVx 3z[^* A V(x) -*• z < w A F(y,x,z)]} This sentence says that among the maps indexed by F there i s one that either (a) maps a subset of the set defined by ty* i n V onto U, or (b) taaps mapssthedsetndef'ined by ^ * in V onto a proper i n i t i a l segment of U. (iv) Vx(U(x) V V(x)) Note that Z is f i n i t e . Let <f> be the conjunction of the sentences in Z . Then J i s a sentence of K . Fuhrken proves i n [9] that W <j> coco Q i f f ( W ^ ) f L ^"^(Q ) $ a n d hence establishes result (*) . Remark: The reduction result((*) confirms (among other things) the existence 47 of wo (L(Q )) v i a the existence of the well-ordering number of L(ft). A c t u a l l y we have more. Claim: For a l l X h,(L(ft)) = h, (1(Q )) and wo, (L($*•)) = wo, (L(Q ) ) . A A a A A a Since ft i s j u s t the set of a l l models of the L(Q )-sentence U; i t i s cl e a r a K that h, (L(ft)) < h,(L(Q )) and wo,(L(ft)) < wo,(L(Q ) ) . The above described A A O t A A O C reduction applied to any set of <_ X l(Q a)-sentences shows the reverse i n e q u a l i t i e s . We are f i n a l l y i n a p o s i t i o n to apply Theorem 4.3.6. Using t h i s theorem f o r each A <_ K from the above claim we get: \<L<V - \^l»~XoAum - XoAua » • A A a In p a r t i c u l a r , taking X = 1, i f the i(Q a)-sentence 9 has a model of c a r d i n a l i t y K — ^woClCQ )) t h e n * n a s a r b i t r a r i l y large models. Example 4.3.8: (Application to L^+^). Let L Q = { c : t, < K } and l e t ft = { (K, (?) ) } . ft consists of one structure with universe K (where K i s conceived as the set of a l l ordinals l e s s than K). I f 9 . i s the 1 + -0 K CO sentence • A ^ ( c = c ) A V x V ( x = c ) then M t = , 9 „ i f f K 00 W - (K, (?) ) f o r any L - s t r u c t u r e W. With ft and L n s p e c i f i e d we get an ft-logic L(ft). As i n the previous example i t i s assumed that for any language L under consideration, L Q U { U } S E S L . Suppose now that L i s a language and 9 i s a sentence of L | <+ t J« We f i n d a languge K containing the unary r e l a t i o n symbol V and with L Q \ J { U } S K which has the following property: (*) Let a : L ->• K be the 0-morphism which i s the i d e n t i t y except that V I—»V. Then there i s a set of < K sentences of K — coco 48 such t h a t : Models of <j> = {M 0 1: M i s an ft-model and M F 2 2^ Z } . (*) says t h a t an L - s t r u c t u r e W r^, 9 i f f W i s o f the form ( M ^ ) f f o r some M w i t h M ?. R e s u l t (*) thus g i v e s t h e d e s i r e d r e d u c t i o n o f the L + - s e n t e n c e A to the s e t Z of L ( f t ) - s e n t e n c e s . KT0) — The i d e a b e h i n d the r e d u c t i o n i s to r e p l a c e a d i s j u n c t i o n o f _< £sfQ.mu<la§aby. an e x i s t e n t i a l q u a n t i f i c a t i o n o v e r t h e s e t U. F i r s t , to each s e n t e n c e it o f L . we a s s o c i a t e by r e c u r s i o n an L - s e n t e n c e i f > * : K+0) 0)0) ( i ) i f ) * = if) i f if) i s atom i c . ( i i ) ( M O * = (ipj_V V * = * i * V * 2* • ( i i i ) ( 3 x < / » * = lx (v(x) A **). The purpose o f ( i ) - ( i i i ) i s t o r e l a t i v i z e if) to the s e t V. Suppose now t h a t UJ(X) i s a f o r m u l a of jtheafdr-itfn V&if,i . ( x ^ e w i t h l l b f r e e varia^'le7.- i l(The g e n e r a l i z a t i o n t o n f r e e v a r i a b l e s i s s t r a i g h t f o r w a r d ; we c o n s i d e r f o r m u l a s w i t h f i n i t e l y many f r e e v a r i a b l e s because we w i l l o n l y be d e a l i n g w i t h subformulas o f sentences o f L K + W - ) L e t be a new b i n a r y r e l a t i o n symbol. Then ( i f)(x))* i s : ( i v ) 3y(U(y) A P ^ y x ) . F o r if)-as i n ( i v ) l e t be the s e t = (Vx(P^c^x -w- i f ) * ( x ) ) : <;<<}. Gi v e n a sen t e n c e A o f L + l e t K be the language c o n s i s t i n g o f K V O ) (a) L l H v } and (b) a l l t h e p r e d i c a t e s P^ f o r any su b f o r m u l a if) o f <j> which i s an i n f i n i t e d i s j u n c t i o n . Then £ i s the f o l l o w i n g s e t o f se n t e n c e s of K : 0)0) { A * } U Lpl U{ Vx(V(x) V U ( x ) ) } where t h e m i d d l e u n i o n i s t a k e n o v e r a l l subformulas if) of A which a r e i n f i n i t e d i s j u n c t i o n s . C l e a r l y | Z | <_ K and an i n d u c t i o n argument shows t h a t an ft-model M |= Z i f f (M^) f j^j A . 06 I tl L i K+0) T h i s e s t a b l i s h e s r e s u l t (ft). R e s u l t (*) and the f a c t t h a t ft i s t h e s e t o f models o f the L , -KT0) 49 sentence <|>0 prove the following two e q u a l i t i e s : h ( W = hK(L<^>> W ° ( W = W O K d ( f i ) ) . Applying Theorem 4.3.6 we then get: h(L . ) = h (L(n» = n K = 1 K „ v K+CO K -"wo (L(ft)) -Jwo(L , ) K KVOJ noted e a r l i e r that wo We noted e a r l i e r that wo(L + ) > K +. Thus K + wo(L _i_ ) = wo(L + ). A small argument shows from t h i s : "~| K,, N = i ,, . Hence we obtain the -•wo(L + ) -^wo(L . ) f i n a l r e s u l t h(L • ) = _ J which i s an Upward Lowenheim-Skolem r e s u l t K+GJ wo(L . N f o r the l o g i c L + 50 BIBLIOGRAPHY 1) Barwise, J . : "Axioms for abstract model theory", Annals of Mathematical Logic 7 (1974), pp. 221-265. 2) Barwise, J . : "Back and f o r t h through i n f i n i t a r y l o g i c " , i n : M. Morley, ed., Studies i n Model Theory, MAA (1973), pp. 5-34. 3) Barwise, J . and Kunen, K.: "Hanf number for fragments of L ", I s r a e l °°co — ; Journal of Mathematics"10 (1971), pp. 306-320. 4) B e l l , J.L. and Slomson, A.B.: Models and Ultraproducts, North Holland, Amsterdam,(1969). 5) Chang, C C . and K e i s l e r , H.J.: Model Theory, North Holland, Amsterdam, (1974). 6) Enderton. H.B.: A Mathematical Introduction to Logic, New York and London, (1972). 7) Feferman, S.: "Two notes on abstract model theory.II. Properties in v a r i a n t on the range of definable r e l a t i o n s between structures", Fundamenta Mathematicae 82 (1974), pp. 153-164. 8) Flum,,J.: " F i r s t - o r d e r l o g i c and i t s extensions", i n Lecture Notes i n Mathematics 499, Logic Conference K i e l 1974, Springer-Verlag, Heidelberg, (1975). 9) Fuhrken, G.: "Skolem-type normal forms for F i r s t - o r d e r l o g i c with generalized q u a n t i f i e r s " , Fundamenta Mathematicae 54 (1964), pp. 291-302. 10) Hanf, W.: "Models of languages with i n f i n i t e l y long expressions" International Congress f o r Logic, Abstracts of contributed papers, 24_ (1960), Stanford, C a l i f o r n i a . Tl)sKeisler.JH:J.: Model Theory for I n f i n i t a r y Logic, Noth Holland, Amsterdam, (1971) 12) Lindstrom, P.: "On extensions of elementary l o g i c " , Theoria 35 (1969), pp. 1-rll. 13) ;2EopezsEseobar^ Fundamenta Mathematicae 59 (1965), pp. 13-21. 51 14) Mendelson, E.: Introduction to Mathematical Logic, Van Nostrand, Princeton,,(1964). 15) Mostowski, A.: "Craig's i n t e r p o l a t i o n theorem i n some extended systems of l o g i c " , i n : Van Roostelaar and Staal eds., Logic Methadology and Philosophy of Science I I I , North Holland, Amsterdam, (1968), pp. 87-104. 16) Morley, M.: "The Hanf number of co-logic", Journal of Symbolic Logic 32 (1967), pp. 437. 17) Vaught, R.L.: "The Lowenheim-Skolem Theorem", i n : Proceedings of 1964 International Congress on Logic, Methadology and Philosophy Science, North Holland, Amsterdam (1965), pp. 81-89.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Abstract model theory
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Abstract model theory Fraser, Craig Graham 1976
pdf
Page Metadata
Item Metadata
Title | Abstract model theory |
Creator |
Fraser, Craig Graham |
Date Issued | 1976 |
Description | We define a notion of logic that provides a general framework for the study of extensions of first-order predicate calculus. The concept of partial isomorphism and its relation to infinitary logics are examined. Results on the definability of ordinals establish the setting for our proof of Lindstrom's Theorem: this theorem gives conditions that characterize first-order logic. We then consider the analogues to the general case of the compactness and Lowenheim properties. For a wide class of logics it is shown that interesting connections exist between the analogues of these properties. |
Subject |
Model theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-02-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0080107 |
URI | http://hdl.handle.net/2429/19873 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1976_A8 F73.pdf [ 2.94MB ]
- Metadata
- JSON: 831-1.0080107.json
- JSON-LD: 831-1.0080107-ld.json
- RDF/XML (Pretty): 831-1.0080107-rdf.xml
- RDF/JSON: 831-1.0080107-rdf.json
- Turtle: 831-1.0080107-turtle.txt
- N-Triples: 831-1.0080107-rdf-ntriples.txt
- Original Record: 831-1.0080107-source.json
- Full Text
- 831-1.0080107-fulltext.txt
- Citation
- 831-1.0080107.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080107/manifest