Open Collections

SOME THEORY OF BOOLEAN V A L U E D MODELS b y • - A n t h o n y C o l l i n s K l u g B . S c , U n i v e r s i t y o f C a l i f o r n i a , R i v e r s i d e , 1 9 7 1 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T OF THE REQUIREMENTS FOR THE D E G R E E OF MASTER OF S C I E N C E i n t h e D e p a r t m e n t o f M a t h e m a t i c s We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE U N I V E R S I T Y OF B R I T I S H C O L U M B I A A u g u s t , 1 9 7 4 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an advanced d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head o f my Depar tment o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Depar tment o f Krffr " W v v N t ^ T ' C S The U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r 8, Canada Date *1 1 *^7 A b s t r a c t B o o l e a n v a l u e d s t r u c t u r e s a r e d e f i n e d a n d some o f t h e i r p r o p e r t i e s a r e s t u d i e d . C o m p l e t e n e s s a n d c o m p a c t n e s s t h e o r e m s a r e p r o v e d a n d L o w e n h e i m - S k o l e m t h e o r e m s a r e l o o k e d a t . I t i s s e e n t h a t f o r a n y c o n s i s t e n t t h e o r y T a n d c a r d i n a l n u m b e r K T t h e r e i s a m o d e l N o f T ( a " u n i v e r s a l " m o d e l ) s u c h t h a t f o r a n y m o d e l M o f T w i t h M <, K , M c a n b e w r i t t e n a s a q u o t i e n t o f N . A t h e o r y T i s s h o w n t o b e o p e n i f a n d o n l y i f g i v e n s t r u c t u r e s M c N , i f N i s a m o d e l o f T , t h e n M i s a m o d e l o f T , T i s s h o w n t o b e e x i s t e n t i a l i f a n d o n l y i f t h e u n i o n o f e v e r y c h a i n o f m o d e l s o f T i s a m o d e l o f T. T h e p r e f i x p r o b l e m a n d o b s t r u c t i o n s t o e l e m e n t a r y e x t e n s i o n s a r e e x a m i n e d . V a r i o u s f o r m s o f c o m p l e t e n e s s a r e c o m p a r e d a n d , f i n a l l y , a n e x a m p l e i s g i v e n w h e r e B o o l e a n v a l u e d m o d e l s a r e u s e d t o p r o v e a t h e o r e m o f M a t h e m a t i c s ( H i l b e r t ' s 1 7 - t h P r o b l e m ) w i t h o u t u s i n g t h e A x i o m o f C h o i c e . T h r o u g h o u t , i t i s s e e n t h a t g o o d B o o l e a n v a l u e d s t r u c t u r e s ( f o r a l l 41 E ( 3 V j ) < ( ) ] ^ = I(Ji,a]^ f o r s o m e a e U^) b e h a v e v e r y m u c h l i k e r e l a t i o n a l s t r u c t u r e s a n d m u c h o f t h e t h e o r y d e p e n d s u p o n t h e i r e x i s t e n c e . i i i • V ' ' ' . \ . A c k n o w l e d g e m e n t I w i s h t o . t h a n k D r . A . A d l e r f o r h i s m a n y i d e a s a n d s u g g e s t i o n s p u t f o r t h d u r i n g t h e p r e p a r a t i o n o f t h i s t h e s i s . I am a l s o t h a n k f u l f o r t h e c a r e f u l r e a d i n g g i v e n t h i s t h e s i s b y D r . T . C r a m e r . F i n a l l y , I am p l e a s e d t o a c k n o w l e d g e t h e f i n a n c i a l s u p p o r t g i v e n me b y t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a M a t h e m a t i c s D e p a r t m e n t . C o n t e n t s I n t r o d u c t i o n C h a p t e r 1 F i r s t O r d e r T h e o r i e s a n d B o o l e a n A l g e b r a s 1.1 F i r s t O r d e r T h e o r i e s 1.2 B o o l e a n A l g e b r a s C h a p t e r 2 R e l a t i o n a l a n d B o o l e a n V a l u e d S t r u c t u r e s 2.1 R e l a t i o n a l S t r u c t u r e s 2.2 B o o l e a n V a l u e d S t r u c t u r e s C h a p t e r 3 B a s i c T h e o r e m s 3.1 H e n k i n T h e o r i e s a n d L i n d e n b a u m A l g e b r a s 3.2 T h e C o m p l e t e n e s s T h e o r e m 3.3 T h e C o m p a c t n e s s T h e o r e m C h a p t e r 4 T h e L o ' w e n h e i m - S k o l e m T h e o r e m s 4.. 1 . The..Downward L o w e n h e i m - S k o l e m The.o.rem 4.2 A T r i v i a l U p w a r d L o w e n h e i m - S k o l e m T h e o r e m 4.3 T h e T h e o r e m s f o r S t r u c t u r e s w i t h S t r i c t E q u a l i t y 4.4 U n i v e r s a l M o d e l s o f a T h e o r y C h a p t e r 5 C h a r a c t e r i z a t i o n T h e o r e m s 5.1 T h e M o d e l E x t e n s i o n T h e o r e m a n d O t h e r Lemmas 5.2 O p e n T h e o r i e s a n d E x i s t e n t i a l T h e o r i e s C h a p t e r 6 A d d i t i o n a l T h e o r e m s 6.1 T h e P r e f i x P r o b l e m 6.2 O b s t r u c t i o n s t o E l e m e n t a r y E x t e n s i o n s 6.3 C o m p l e t e n e s s a n d M o d e l C o m p l e t e n e s s . 6.4 H i l b e r t ' s 1 7 - t h P r o b l e m B i b l i o g r a p h y Introduction Although Boolean valued models are often considered to be modern creations, the idea of assigning to sentences truth values other than True and False can be traced back to the beginnings of Mathematical Logic. George Boole made$ allusions»to-truth„ values), other than-True and False and so did Freg'e and Pierce. But i t was the work of Lukasiewicz in the 1920's which can be called the foundation of Boolean valued model theory. He was the f i r s t to precisely define many-valued logics and, with remarkable foresight, he recognized their application to independence proofs. After the work of Lukasiewicz, a number of other workers i n the next decade developed and elaborated upon his ideas. Some of the people involved were Tarski, Lindenbaum, Brouwer, Mostowski, McKinsey and Stone. In particular, i t was seen that there should be a structure on the set of. truth values reflecting the structure of the theory under consideration. Thus instead of having subsets of [0,1] as truth values, algebraic structures were used. T a r s k i [ 2 0 ] described the use of logi c a l matrices which were sets on which were defined operations corresponding to the propositional connectives v t A» ~» "**" • Sentences were interpreted as functions on the matrix. Using this method, Tarski was able to characterize the set of provable formulas of Propositional Calculus topologically and algebraically. When attention shifted to Predicate Calculus, the idea of logical matrices was naturally extended and models were defined i n which formulas were Interpreted as functions from, the,underlying, set,of. the model to soma algebraic object. The original paper was by Mostowski[9] who proved the independence of a certain formula from the axioms of Intuitionistic Logic. Since the theory here was Intuitionistic Logic, the model's truth set was a (complete) l a t t i c e . In 1950 Rasiowa and Sikorski[10l gave the f i r s t proof of.the Completeness Theorem (for countable f i r s t order theories) which used Boolean valued models. They f i r s t constructed a model using the Lindenbaum algebra of the theory as the set of truth values. Then by taking a quotient of the Lindenbaum algebra by an u l t r a f i l t e r they obtained a c l a s s i c a l model. Later, i n their book, The Mathematics of Metama.theinatics.Lli], Rasiowa .and Sikorski used Boolean .valued..models and other algebraic and topological techniques for proving theorems of Metamathematics. While Boolean valued models up to this time had proven to be interesting devices i n the-algebraization of logic, they began to arouse the attention of a wider audience i n connection with Paul Cohen's forcing method. In 1963 Cohen[2,3] used the new method of forcing to prove the independence of the Continuum Hypothesis from the-.: axioms, of set theory. Although forcing was quite correct and elegant, i t could only be understood by a nonspecialist after much time and effort. However, in 1965 R.M. Solovay discovered that Cohen's forcing conditions could be viewed as, a way of assigning Boolean values to formulas. By translating the;forcing conditions into conditions on the Boolean algebra, the forcing method could be avoided altogether. In 1966 Dana Scott[16] applied this idea and proved the independence of the Continuum Hypothesis using only a Boolean valued model. Aside from the purely mathematical aspect of this proof, Scott's paper was important because i t was easy to understand. More recently, J.B. Rosser has also used Boolean valued models to simplify independence proofs[14]. It would be a mistake, though, to think that forcing and the method of Boolean valued models are competing techniques, there being a school of forcing and a school of Boolean methods. On the contrary, the two methods have been merged and the present practice i s to use forcing .conditions -to construct Boolean valued models with certain predetermined properties (see J e c h [ 8 ] , for example). Despite the exposure Boolean valued models have had i n the past decade, they are s t i l l not understood by many people. Often, i t i s because Boolean valued models are thought of as models with generalized truth values and even philosophers find the notion of generalized truth value d i f f i c u l t to understand. Whereas this i s a perfectly vali d interpretation, i t w i l l be seen i n this thesis that an equally v a l i d , but more comprehensible alternative i s to view a Boolean valued model as a sort of "premodel", that i s , only some sentences are declared true or false. Certain "premodels", namely the canonical ones, are actually a bridge between syntax and semantics. Another reason that Boolean valued models have seemed a b i t mysterious i s that the model-theoretic b a c k g r o u n d b e h i n d t h e i r u s e i n independence proofs i s usually assumed known and i s not e x p l i c i t l y given. This deficiency has.begun to be corrected-with papers by Rutkowski[l5], Szczerba[18] and Ressayre[12]. This thesis i s intended to be an introduction to the basic model-theoretic properties of Boolean valued models. Also, as many theorems as possible w i l l be proven without using the Axiom of Choice or the U l t r a f l i t e r Theorem. There are many theorems of algebra and analysis whose proofs use either the Axiom of Choice or the U l t r a f l i t e r Theorem. We give one example i n which a Boolean valued version of the theorem of Artin on real-closed f i e l d s , while weaker than the standard version, i s s t i l l sufficient to prove one of the corollaries of the original theorem, namely Hilbert's seventeenth problem. While we are unable to present anymore results here, the outlook i s favourable for at least some other cases. Chapter 1 F i r s t Order Theories and Boolean Algebras In this chapter a l l the basic definitions and theorems, of f i r s t order theories and of Boolean algbras w i l l be given. As a rule, the theorems w i l l not be proved. The results are a l l standard, though, and the proofs may be found i n the appropriate standard text. For example, Shoenfield[17] and B e l l and Slomson[l] provide proofs for theorems on f i r s t order theories. Also, Halmos[5] and B e l l and Slomson develop a l l that i s needed concerning Boolean algebras. Section 1 F i r s t Order Theories A f i r s t order language, £ contains the following sets of symbols: (1) a countable set of variables {VQ,V^,V2,»••}, (2) for each nonnegative integer n, a set P Q of n-ary predicate  symbols, the letter P w i l l denote an arbitrary element of P n, (3) the equality predicate =, which is an element of , (4) for each positive integer n , a set P n of n-ary function symbols, the letter f w i l l denote an arbitrary element of F n , (5) a set C of constant symbols, the letter c w i l l denote an arbitrary element of C, (6) the symbols ~, v, 3, ~ i s negation, V is disjunction. 3 i s the existential quantifier, (7) brackets, parentheses, commas, etc. ; Note that these sets are assumed to be disjoint and i t i s possible that any except i s empty. The language L also contains the set T of terms, defined inductively as follows: (1) variables and constant symbols are terms, (2) i f f-e'F and t l t • • • , t n e Tt then f (t1,».»-» ,t Q) c T . Lastly, L contains the set F of formulas, also defined inductively: (1) i f P e P n and t 1,««»,t n e T , then P(ti,«*»,tn) i s an atomic formula and atomic formulas are i n F , (2) i f $ and y are formulas, then so are ~$ and (<})V\|i), ( 3 ) i f $ i s a formula, then so i s (avj)^i for any j = 0 , 1 , 2 , " ' , It i s useful and customary to introduce defined symbols i n the following way: ( 1 ) write <J> A . f ° r ~(~<f> v ~ 1J0 » A i s c o n j u n c t i o n , (2) .write • <j> —>.ijj f o r ~<|>- v ip , ' ( 3 ) write <j> ip • for (<{>-»- ij)). A - » - ( { , ) , (4) w rite (VVj)^ for ~ ( 3 V j ) ~ ^ , V i s the universal quantifier. The letters \|), 6, a, x» 5 w i l l be names for elements of F . An occurrence of V j i n $ i s bound i f this occurrence i s i n a part of $ of the form (Svj)^ , otherwise the occurrence i s free. We say V j i s bound i n $ i f V j has a bound occurrence i n <f> . Similarly, V j i s free i n $ i f i t has a free occurrence i n $ . Note that a variable may be both bound and free i n a formula. For terms t and s , the symbol tj[s] denotes the term obtained from t by replacing each occurrence of V j in t by s . If T i s a sequence (tQ,tj_,•••'•) of terms, then t[x] denotes the term obtained from t by simultaneously replacing each occurrence of v^ by t j for j = 0,.1,2«»» . The term t[t] i s called an instance of t . If $ i s a formula and t i s a term, we say that . t i s free for V j i n cj> i f for each variable v^ occurring i n t , no part of $ of the form (Sv^iji contains an occurrence of v^ which i s free i n $ . If t i s free for V j i n <J> , then • j t t l denotes the formula obtained from <j) by replacing each free occurrence of v^ by t . If T i s a sequence ( t ^ t ^ * * * ) of terms such that each t^ i s free for v^ j i n $ i then f [r] denotes the formula obtained from $ by simultaneously replacing each free occurrence of V j by t j for j = 0,1,2,»»» . We c a l l an instance of <f> . We w i l l write <{>[t] for «|>j [t] when no confusion can arise. The l o g i c a l axioms of L are a distinguished set of formulas of L . Let 4>i 4*» X be any formulas. Then the following formulas are logical axioms (we omit parentheses when no confusion results); (1) 4> -> 4) , (2) U x>] —• [(• x)l » (3) ( ~ * ~ij>) • «i $) , (4) ( M *) ^  * i (5) ($ A ^j) <|i , (6) ( X - M ) [(X --*;*).-*• (X U v <p))] , ( 7 ) * ($ v ^ ) , (8) ij) - »• (* v 4,) , (9) (• x) - * • [ ( * -*• X) ((* M) X)] . (10) f j t t J C 3*^)* where j = 0,1,2,.«. and t i s free for i n <}> , . (11) (Vv^X^ tp) ( vVj)ip) where j = 0,1,2,.«. and $ contains no free occurrence of , (12) (VVJKVJ = V j ) for j = 0,1,2,••• , (13) (Vvj)(Vv k) ( ( V j = vfc) A x —• X 1) where v f c i s free for V j i n X Bnd. x' results from x by replacing some, but not necessarily . a l l , free .occurrences of v.^  by v^ ., (14) C Y v j ) C Y v k ) ( ( v J , - S v1t) "*"-^-5 ' j ^ k 1 * f o r ^ t e r m c ' Axioms (1) through (9) are called propositional axioms. Axioms (10) and (11) are, respectively, substitution and V-introduction axioms. We c a l l (12) to (14) equality axioms. Next we define the rules of inference. There are two of them: (1) for any formulas <j> and ip , ip i s an immediate consequence of $ and <p —»• ip , (2) for any formula 0 and any variable v^ , (Wj)9 i s an immediate consequence of 8 • It should be noted that this choice of axioms and inference rules i s not at a l l unique. There are many equivalent formulations. Ours follows,Bell and Slomson, most closely. We can now define what we mean by a f i r s t order theory. A f i r s t order theory T , called simply a theory, consists of three things: (1) a f i r s t order language L(T) , called L when T i s understood (2) a set of axioms, the logical axioms of L and other, nonlogical axioms, (3) the inference rules for L . A theory i s completely specified by giving i t s language and nonlogical axioms. In the future, when we refer to the axioms of a theory, we w i l l mean i t s nonlogical axioms. The theorems of a theory 2* are defined inductively as follows: .(1) . Che .logical .and. nonlogical axioms of T are theorems,, (2) the immediate consequences of theorems are theorems. If a i s a theorem of T , we w i l l write T h a . The theory with no nonlogical axioms w i l l be called predicate calculus and we w i l l write 1- cr when a i s a theorem of predicate calculus. If I? i s a set of formulas, T[D] w i l l denote the theory obtained from T by adding the formulas of D as new nonlogical axioms. We w i l l now l i s t some theorems about f i r s t order theories: Theorem 1 (Tautology Theorem, special cases)* Let ij>, x be any formulas. Then (1) i f 2* h $ and T I- <J> -*• i|> , then T h > , 10 (2) If T V $ tp , then T V <J> i f and only i f 2" I- tp , (3) i f ? r- • * and 2" r ip X , then T h • •* X i (4) i f T V $•*-*• and 2* }- ip •«->• x » then T V $•*-+• x , (5) 21 h $ A ip i f and only i f 2" K <J> and 2* I- tp , (6) T V <j> ^ i f and only i f T F <f> ip and T V if -+ 4> , (7) 2* r <}> —*• tp i f and only i f 2" h ~tp , (8) 2* f- ($ A » « . A (|>n) -•• ip . i f and only i f 2* f- ^  (*2 ( t ) n —• t p ) « . « ) . ^ e o r e a 2 (Substitution Rule). If f > 8 and e' i s an instance of 6 t then T V 6 * . Theorem 3 (Substitution Theorem). For any terms ti*"' *tn ' (1) 2- j- e[t l t««»,t n] -*• (a V l)...(av n)e , (2) T V (Vv.)...(Vv„)e -^-0[t,,-..,t ] . The formula 6* i s the closure of 8 i f 0' i s obtained from 0 by universally quantifying a l l free variables of 8 . We say 0 i s closed i f i t contains no free variables. 8 i s open i f i t i s quantifier free. Closed formulas are also called sentences. Theorem 4 (Closure Theorem). If 8' is the closure of 0 , then TV 0 i f and only i f T V 0' . 11 Theorem 5 (Deduction Theorem). If . $ i s closed, then for any , T \- <f> —• t|i i f and only i f T[4>] J- ij> . In, general, i f ^x'*"*^,n a r e closed, then T \- A » . . A * ) & i f and only ;if rU.,-r M ,»i] I- ^  • Theorem 6 (Theorem on Constants) Let 2" be obtained from T by adding new-constants*-to* L (but? no new-axioms). Then-for any formula X of L and new constants c^,«»«,cn , T V x I f and only i f T1' V xtc^»*•*»cnl» A formula tj/' i s a variant of i f if/' i s obtained from by replacing parts (a^j)9 of \|» by (av )^ (9j [v^]) where v^ i s not free i n 6 . Theorem 7 (Variant Theorem). If i s a variant of ij» , then A formula of the form (Qv. ) e , ,(Qv. )9 , where Q i s either 1 J n 3 or V and 9 i s open, i s said to be i n prenex form. 9 i s called the matrix of the formula. Theorem 8 (Prenex Form Theorem). For every formula a , there i s a formula ar i n prenex form such that T V o o * . A language L ' i s an extension of a language L i f (2) F'o F and n n (3) C1 a C. A theory 2" i s an extension of T i f 1,(2") extends L ( T ) and every theorem of T i s a theorem of f . An extension T* of T i s a conservative extension of T i f every formula of L(2") which i s a theorem of T% i s also a theorem of T . The theories 2 1 and T%  a r e equivalent i f each i s an extension of the other, that i s i f they have the same language and the same theorems. Theorem 9 (Reduction Theorem). Let D - be a set of formulas of L . For any formula <(> , T[D] F 4 i f and only i f T |- (iii, A . . « A y ) -y «j, , where i 1 ^ * * " t^xi a r e c l ° 8 u r e 3 °f formulas of D . A theory T i s inconsistent i f every formula of L i s a theorem of J . Otherwise T i s consistent. Theorem 10 (Reduction Theorem for Consistency).If D i s a (nonempty) set of formulas, then T[D] i s inconsistent i f and only i f T V ~8, v«»«v ~8 . where 8 ,•••,8 are closures of formulas of D . I n ' 1 * * n Corollary 1 1 . Let o' be the closure of a . Then 2* Y a i f and only i f 2 ,[~a'] i s inconsistent. T h e o r e m 1 2 ( C o n j u n c t i v e F o r m T h e o r e m ) * L e t D b e a s e t o f f o r m u l a s a n d l e t a be a formula b u i l t up from formulas of D using v , A and ... There i s a formula x such that T \- a •*-*• x where x h a s the form X, A » « » A X_ and each x.r has the form ~8„ v»»»v ~0 v A v«««v A 1 ^ i i 1 m 1 k with 8 4 , ^  i n 5 . 1 3 A t h e o r y T i s s a i d t o b e f i n i t e i f t h e n o n l o g i c a l a x i o m s o f T a r e f i n i t e i n n u m b e r t A t h e o r y T i s a s u b t h e o r y o f a t h e o r y T' i f t h e n o n l o g i c a l a x i o m s o f T a r e a l s o n o n l o g i c a l a x i o m s o f Tr T h e o r e m 13 ( F i n i t e n e s s T h e o r e m A ) . A t h e o r y T i s " c o n s i s t e n t i f a n d o n l y i f e v e r y f i n i t e s u b t h e o r y o f T i s c o n s i s t e n t . T h e o r e m 14 ( F i n i t e n e s s T h e o r e m ..B) , A f o r m u l a <(>..,is a t h e o r e m o f T i f a n d o n l y i f ef> i s a t h e o r e m o f s o m e f i n i t e s u b t h e o r y o f T « S e c t i o n 2 B o o l e a n A l g e b r a s A B o o l e a n a l g e b r a i s a s e t B t o g e t h e r w i t h t w o d i s t i n g u i s h e d e l e m e n t s 0 a n d 1 , t w o b i n a r y o p e r a t i o n s v a n d A , a n d a u n a r y o p e r a t i o n ' s a t i s f y i n g t h e c o n d i t i o n s b e l o w f o r a n y p , q , r £ B : ( 1 ) 0' = 1 1' = 0 , ( 2 ) p A 0 = 0 p V 1 = 1 , ( 3 ) p A 1 = p P V 0 = p , ( 4 ) p A p » = 0 p V p ' = 1 , ( 5 ) P " = P , ( 6 ) p A p = p p V p = p „ ( 7 ) ( p A q ) ' = p« v q ' ( p v q)» = p« * q ' » ( 8 ) p A q = q A p p V q = q V p ( 9 ) ( p A q ) A r ;= p A ( Q A R ) ( p V q ) v r = P v ( q v r ) , ( 1 0 ) p A ( q v r ) = ( p A q ) v ( P A r ) p V ( q A r ) = ( p V q ) A ( p v r ) . This l i s t of axioms i s informative but not minimal. One example of a minimal set i s (3) , (4), (8) and (10). In the next section the operations i n a Boolean algebra w i l l be related to the propositional connectives of section 1. If this relation i s to be meaningful, the Boolean operation A should be definable from v and * . But i t is immediate from (-5) and (7) that p A q = (p' v q')« . Also, we define new operations —*• and •«-»• by (p —• q) = P' v q and (p q) = (p -»• q) A (q p) To correctly refer to a Boolean algebra, one should give & 4-tuple (B,0,v,') . However, as i s often done i n Mathematics, the Boolean algebra w i l l usually be referred to simply as B , i t s underlying set, when this causes no confusion. There i s a canonical par t i a l order on the Boolean algebra B which i s given by p £ q i f p A q = p , or equivalently, p £ q i f p V q = q . Now one may ask,about supremums and infimums of subsets of B with respect to this p a r t i a l order. Any f i n i t e set ai»***» a n ^ a a both a supfemum, which i s Just a^ v.»»v , and an infimum, given by a^ A » » « A a Q . Infinite sets may have neither, just one, or both. If {a^ : iel} c B has a supremum, i t i s denoted by sup{a^ : iel} , and i f i t has an infimum, i t i s written inf{a^ : iel} . The notation i s sometimes V(a i : i e l ) and : i d } which i s meant to i l l u s t r a t e the fact that sups and infs can be considered to be the operations v and A applied to an i n f i n i t e number of arguments. We say B i s complete i f a l l supremums (and infimums) exist. Subalgebras are defined i n the usual way. In addition to axioms (1) through (10),, the following facts w i l l be useful: (1) p <i q i f and only i f p' a q* , (2) p £ q i f and only i f (p —• q) = 1 , (3) i f p = 1 and (p q) = 1 , then q = 1 , (4) (sup p^)' = inf p^ and (inf p^)' = sup p£ , where i t i s understood that i f the term on one side of either equation exists, the term on the other side exists and both are equal, (5) p v inf q^ = i ^ f ( p v q^) and p A sup - sup (p A q^) , with the same interpretation as above, (6) . p A « » » A =. 1 i f .and only i f each p^ = 1 , (7) If A i s a subalgebra of B and [ p ^ c A , then 8 i P A p i 2 S i P B p i m d ^ A p l l n f B P i * w h e r e t h e subscripts indicate with respect to which algebra the bound i s taken; i n this case, there i s no relation between the existence of terms on either side of the inequalities, (8) i f c B 2 c»»» i s a chain of Boolean algebras, then the union U B^ i s also a Boolean algebra, ( 9 ) i f {B i : iel} i s a family of Boolean algebras, the Cartesian product n B^ i s also a Boolean algebra; i f p,q e n B^ , then p £ q i f and only i f p^ S q^' for a l l i e l .' A f i l t e r F i n a Boolean algebra B i s a n o n e m p t y s u b s e t o f B s u c h t h a t ( 1 ) . i f p e F and q e B , then p v q g F , ( 2 ) i f p e F and q e F , then p A q e F . Condition ( 1 ) i s equivalent to the following condition: ( 1 ' ) i f p e F and p £ q , then q e F . Thus 1 i s always an element of F . Every Boolean algebra B contains two uninteresting f i l t e r s : the t r i v i a l f i l t e r 1 and the improper f i l t e r B . A f i l t e r F i s nontrivial i f "S'~* 1 ; i t i s proper i f F * B . A homomorphism g from a Boolean algebra A to a Boolean algebra B (where we give the respective operations i n each algebra the same name and use 0 , 1 for the distinguished elements of both algebras) i s a function from A to B such that for a l l p,q e A g(p') = g(p)' and g(p V q) = g(p) V g(q) . From this i t immediately follows that g ( 0 ) = 0 , g(l) = 1 and g(p) * g(q) for a l l p * q . The s h e l l of any homomorphism g , that i s , the set {peA : g(p)=l} i s always a proper f i l t e r . Conversely, given a proper f i l t e r F , there i s a homomorphism whose she l l i s F . The image of this homomorphism i s called the-quotient of A by F , written A/F , The hotaomorphism g i s said to be complete i f for every subset { a ^ c A with a supremum a , the set {g(a ±)} c B has a supremum which equals g(a) . A f i l t e r F i s said to be complete i f i t s induced hotaomorphism A —> A/F i s complete. A very important class of f i l t e r s are the u l t r a f l i t e r s . A proper f i l t e r F i s ah u l t r a f l i t e r i f any of the following equivalent conditions are f u l f i l l e d : (1) F i s not properly contained In any other proper f i l t e r , that i s , i f for some f i l t e r G , F c G , then F = G or G = B (2) f o r a l l p £ B , either p e F or p' e F (but not both), (3) B/F = {0,1} where (0,1} is the t r i v i a l Boolean algebra. The existence of u l t r a f i l t e r s i s given by the following theorem: Theorem 15 ( U l t r a f l i t e r Theorem). Every proper f i l t e r may be extended to an u l t r a f i l t e r . Proof. Let F be a proper f i l t e r i n B and l e t S be the set of a l l proper f i l t e r s i n B extending F . 5 i s not empty since F e S . Let D 1 c c « " be a chain i n S and set D = U D ± . We want to show that D i s a f i l t e r . If x,y e D and z £ B , then for some j , x e D. and y £ D so x A y £ D c D and x v z e D <= D . Since 0 i for a l l i , 0 i D . Thus D i s a proper f i l t e r and an upper bound for the chain i n S . By Zorn's Lemma, S contains a maximal element, that i s , an u l t r a f i l t e r . From this proof we see that the Axiom of Choice implies the U l t r a f i l t e r Theorem. The converse, though, i s not true: the U l t r a f i l t e r Theorem,: taken as an axiom (along with the other axioms of Zermelo-Fraenkel set theory), does not imply the Axiom of Choice[7], A subset A of a Boolean algebra B i s said to have the f i n i t e  intersection property i f the infimum of every f i n i t e subset of A is nonzero. The importance of sets with the f i n i t e intersection property i s that they can be extended to proper f i l t e r s i n B. Thus i f A has the f i n i t e intersection property, there i s an u l t r a f i l t e r i n B containing 19 Chapter 2 Relational and Boolean Valued Structures Section 1 . 1 gave some syntactical properties of f i r s t order theories. The keywords relating to these properties were "theorem", "provable" and "consistent". However, we w i l l also want to study semantics so we must define the terms "true", "false" and "valid". The usual way to do this i s with relational structures. A description of these objects i s given i n section 1 of this chapter. The more general Boolean valued structures w i l l be defined in section 2 . Section 1 Relational Structures Given a language L , a relational structure M for £ i s a nonempty set , the underlying set of M , together with the following: ( 1 ) for each P e P , an n-ary relation P.. on U„ with n ' ' v M M the restriction that =^ i s the identity relation, ( 2 ) for each f e F , a function f : u" -*• U,. , (3) for each c e C , an element c^ £ . Although we are ultimately only interested in the truth value of sentences, i t i s advantageous, for example, i n proofs by .induction, to also define truth values of formulas. Since a formula $ may contain free variables, we need to assign an element'of to each free variable i n cj> . We do this by specifying a valuation a i n M which i s just a sequence (a^ .a^ .,••••.) of elements-of . In the future, 3 = (b^,b^,»*») w i l l also denote a valuation. Let us f i r s t define what we mean by the value [ t ] ^ of the term t i n M with respect to a . This i s done by induction: (1) [ V j ] ^ = a for any j = 0,1,2 (2) [c]M = c„ for any c £ C (note that [c] i s independent of a M a (3) i f f e F and the values of the terms t.,,»»»,t have n x n been defined, then [f ( t ^ - . . = V [ t l ] a ' * " ' ^ n 1 ^ ' Now we define when a formula * i s true i n -M with respect to a and we write Af,a p * or M p *[a] i n this case: (1) i f P e P an'd t.,•••, t are terms, then M,a P 'P'Ct- • • ,t ) i f and only i f ( [ t ^ J , • • •, [ t j * ) e P^ , (2) 'AT,a 1= ~<j> i f and only i f not M,a {= * , (3) Af,a t= * v ^  i f and only i f Af,ct * or Af,ct t= i|» , (4) i f x e , we let a(jlx) be the valuation which i s the same as a except for having x i n the j-th place, then Af,a N(3vj)«}> i f and only i f for some x e , M,a(j lx) p * . From (2), (4) and the definition of the universal quantifier, we see that M.a P (Vv^H i f and only i f for a l l x , Af,o(j |x) P t> . It i s also easy to see that i f a and B are valuations such that i f V j occurs free i n * , then = bj , then Mta, P * If and only i f Af,8 1= * . In other words, whether or not Mtct P * depends only on the elements of a which correspond to free variables of cj> . Thus we are allowed, when convenient, to write Aft3 $ [a k , • • • ,a n] i n place of M k <j>[a] when the free variables of $ are among ' vk»** * » vn * ^ * s a 8 e n t e n c e » w e m a y write M ¥ Q> without referring to any valuation at a l l . We say a formula <{> i s valid i n M i f Af,a i= $ for a l l valuations In a . We may write Af t= 4* when <j> i s valid i n M . Now l e t T be a theory over L . A relational structure Af i s a model of T i f for every axiom x of T , M x • A formula x i s valid i n T i f for every model M of T , M x • The relations between being consistent and having a model and between being v a l i d and being provable are given by the two forms of the Completeness Theorem: Theorem 1 (Completeness Theorem A). A theory T i s consistent If and only i f T has a model. Theorem 2 (Completeness Theorem B). A formula $ i s va l i d i n a theory T i f and only i f ; > $ i s provable i n T . The Compactness Theorem, which may be thought of as the semantic counterpart of the finiteness theorem, i s also an important theorem i n the theory of relational models: Theorem 3 (Compactness Theorem A). A theory T has a model i f and only i f every f i n i t e subtheory of 2" has a model. 2 2 Theorem 4 (Compactness Theorem B). A formula $ is v a l i d i n T i f and .only i f <J> i s valid in some f i n i t e subtheory .of T . The l o g i c a l relations among these statements and the U l t r a f i l t e r Theorem, which i s used i n their proof, is given by the next theorem, whose proof, of course, does not use the Axiom of Choice or the U l t r a f i l t e r Theorem: Theorem 5, The following four statements are equivalent: (1) T i s consistent i f and only i f T has a model, (2) T has a model i f and only i f every f i n i t e subtheory of T has a model, (3) every Boolean algebra contains an u l t r a f i l t e r , (4) every proper f i l t e r i n a Boolean algebra may be extended to an u l t r a f i l t e r . Any one of these statements implies the following statement: (5) a formula $ i s valid i n T I f and only i f $ i s provable i n T ; and this statement implies the one following: (6) <{. i s valid i n T i f and only i f <j> i s valid in some f i n i t e subtheory of T . If one examines the proof of the Completeness Theorem A given i n B e l l and Slomson, one sees that the u l t r a f i l t e r whose existence i s given by the U l t r a f i l t e r Theorem i s used to decide which sentences w i l l be true .and which w i l l be false i n the model. It^seems plausible, then, that i f we were to relax the requirement that sentences must be either true or false i n a relational structure, we might be able to avoid the U l t r a f i l t e r Theorem i n proving completeness and compactness (of course, we would obtain different completeness and.compactness theorems). In the next section we define structures which do relax this condition. A third important pair of theorems are the LBwenheim-Skolem 'ta. theorems which deal with cardinalities of models. The cardinality M  of a structure M i s the cardinality of i t s underlying set U^ . cca The cardinality L of a language L i s the cardinality of the set rjat of symbols of L . The cardinality T of a theory T i s the cardinality of the language of J" , Theorem 6 (Downward Lowenheim-Skolem Theorem). If T has an sat i n f i n i t e model, then I has a model of cardinality T . Theorem 7 (Upward LbVenheim-Skolem Theorem). If T has an i n f i n i t e model, then T has a model of any cardinality ^ T . The l o g i c a l relations among these theorems and the Axiom of Choice which i s used i n their proof i s given by the following theorem: 24 Theorem 8. The following are equivalent: (1) the Upward Lowenheim-Skolem Theorem, (2) the Downward Lowenheim-Skolem Theorem, (3) the Axiom of Choice. Section 2 Boolean Valued Structures Before we define what a Boolean valued structure i s , l e t us take another look at the d e f i n i t i o n of a r e l a t i o n a l structure. To every n-ary predicate symbol P , a r e l a t i o n a l structure M assigns a r e l a t i o n c . We may view t h i s r e l a t i o n as a function P^ : —»• {0,1} , where {0,1} i s the minimal Boolean algebra, by agreeing that VM^*1*"' * xr? = 1 i f and only i f (x^,• • • ,x n) e ?M . We may extend t h i s new point of view to formulas by defining a tr u t h function I , ] ^ with values i n {0,1} by setting 18 , a ] ^ = 1 i f and only i f Af,a !»• 8 . Thus we may say that a l l sentences have truth value 0 or 1 i n Af . Considering our stated desire to relax t h i s r e s t r i c t i o n on the possible t r u t h values of sentences, i t i s natural to seek a generalization of r e l a t i o n a l structures by replacing {0,1} by other Boolean algebras. Thus our f i r s t step would be to assign a function : UJJ —*• B to every P e P Q where B i s some Boolean algebra determined by the structure. Whereas the function i , ] and the r e l a t i o n -can both "equally w e l l express the notion of v a l i d i t y f o r r e l a t i o n a l structures, we must rely almost entirely on the B-valued function I , ] (yet to be defined) with Boolean valued structures since there w i l l be more than the two p o s s i b i l i t i e s M.a p $ or Af,a P ~<j> that occur for relational structures. There are certain properties which the function assigned to the equality predicate should have. Since an element x e really i s equal to i t s e l f , we should have (x =y x) = 1 . However, we do not require that i f x * y , that (x =^ y) = 0 . In fact, we may even have (x H y) = 1 for distinct x,y e U '. For relational structures, the substitution axioms for equality were automatically satisfied. Because =^ , for M a Boolean valued structure, i s not s t r i c t equality, we must place conditions on i t and the functions , so that these axioms are s a t i s f i e d . Roughly speaking, these conditions should say that the value P.,(»• • , x , • ) should equal the value !"..(••• »y» •) to the degree to which x and y are equal. Also, the degree to which f^(» • • ,x, • • •) equals f^(»••,y,•••) should be at least the degree to which x equals y . If we carry over the definition of p to the function II , 1 for a relational structure M , we find th-att ( 1 ) IPO*,—,t n> . a]„ = P^CCt^. — .LtjJ) , ( 3 ) (2) (4) T h e o p e r a t i o n s v , ~ a n d s u p . a r e d e f i n e d b y V 0 1 0 1 { 0 } { 1 } { 0 , 1 } 0 0 1 1 0 s u p 0 1 1 1 1 1 I t s e e m s r e a s o n a b l e , t h e n , t o d e f i n e 1 , 1 ^ , f o r - a B o o l e a n v a l u e d s t r u c t u r e M , i n f o r m a l l y t h e same w a y . P u t t i n g a l l t h i s t o g e t h e r w e a r r i v e a t t h e f o l l o w i n g d e f i n i t i o n o f a B o o l e a n v a l u e d s t r u c t u r e : A B o o l e a n v a l u e d s t r u c t u r e M f o r t h e l a n g u a g e L i s a n o n e m p t y s e t t o g e t h e r w i t h t h e f o l l o w i n g : ( 1 ) a B o o l e a n a l g e b r a B ^ w i t h e n o u g h s u p r e m u m s ( t h i s w i l l b e e x p l a i n e d b e l o w ) , ( 2 ) f o r e v e r y f e F , a f u n c t i o n f ^ : —>- , ( 3 ) f o r e v e r y P e P , a f u n c t i o n P ^ : —> B ^ s u c h t h a t f o r a l l a , , • • • , a ,b e U„, , 1 ' n M ( a ) ( b = M b ) = 1 , ( b ) P A f ( a i » * " » V ' ' ' V A C a i aM b ) S V a l ' " , » b ' * , * ' a n ) ' ( c ) i a t = M b ) ^ [ f M ( a 1 , ' - - , a i , - « - , a n ) H M f ^ . ' - . b . ' - . a ^ l , ( 4 ) f o r e v e r y c e C , a n e l e m e n t c ^ e . N o t e t h a t ( 3 a ) a n d ( 3 b ) i m p l y t h a t ( a 5^ b ) = ( b = M a ) f o r a l l a,b e M T h e v a l u e o f a t e r m t i n M w i t h r e s p e c t t o a i s d e f i n e d a s f o r r e l a t i o n a l s t r u c t u r e s . . T h e t r u t h f u n c t i o n . C , 1^ f o r t h e B o o l e a n v a l u e d s t r u c t u r e M , a c c o r d i n g t o t h e r e m a r k s a b o v e , s h o u l d b e d e f i n e d b y i n d u c t i o n a s f o l l o w s ( 1 ) i f P e P a n d t t a r e t e r m s , t h e n n 1 n ( 2 ) f o r a n y f o r m u l a s 9 a n d a , l~d.a]„ = H e , a ] ' M M a n d E6 v a , a ] ^ = 16,al^ v tta.al^ , i n w o r d s , t h e " v a l u e o f t h e n e g a t i o n o f 9 i s t h e c o m p l e m e n t o f t h e v a l u e o f 0 -and t h e v a l u e o f t h e d i s j u n c t i o n . 6 V a o f 9 a n d a i s t h e j o i n o f t h e v a l u e s o f 9 a n d o f a , ( 3 ) f o r a n y v a r i a b l e v ^ a n d f o r m u l a <j> , l ( a v j ) * , a l w = s u p ( E $ , a ( j l x ) l M : x e i y . T h a t h a s e n o u g h s u p r e m u m s s i m p l y m e a n s t h a t t h e a b o v e s u p r e m u m e x i s t s f o r a n y $ a n d a . B^. w i l l h a v e e n o u g h s u p r e m u m s i f , f o r e x a m p l e , i t i s c o m p l e t e , b u t t h i s c o n d i t i o n i s m u c h s t r o n g e r t h a n n e c e s s a r y . I f i t i s c l e a r f r o m t h e c o n t e x t w h i c h s t r u c t u r e M i s b e i n g r e f e r r e d t o , . w e w i l l o m i t t h e s u b s c r i p t s f r o m H , 1^ a n d B ^ a n d t h e M s u p e r s c r i p t f r o m [ t ] • L o o k i n g b a c k a g a i n a t r e l a t i o n a l s t r u c t u r e s , w e s e e t h a t |[(3v H , a l = 1 i f a n d o n l y i f f o r s o m e x e , I i j ) , a ( j | x ) l = 1 . T h e c o r r e s p o n d i n g p r o p e r t y f o r B o o l e a n v a l u e d s t r u c t u r e s w o u l d b e : ( g ) g i v e n a n y Vj ,, a n d a , t h e r e i s a n x e U M s u c h t h a t • • II(aVj)i)),al = It* ( j l x ) l • I n o t h e r w o r d s , t h e s u p r e m u m s u p { | [ ^ , a ( j l x ) I : x e U ^ } i s a c t u a l l y a maximum. We w i l l s a y t h a t a s t r u c t u r e ( f r o m n o w o n , " s t r u c t u r e " w i l l mean " B o o l e a n v a l u e d s t r u c t u r e " ) M i s a g o o d s t r u c t u r e i f s a t i s f i e s t h e a b o v e p r o p e r t y ( g ) w h i c h i s s o m e t i m e s c a l l e d - t h e M a x i m u m P r i n c i p l e [ 1 2 ] . C l e a r l y , t h e s e t o f e l e m e n t s o f B o f t h e f o r m I<j>,a] " f o r s o m e f o r m u l a <}> a n d v a l u a t i o n a i s a s u b a l g e b r a o f B w h i c h h a s e n o u g h s u p r e r o u m s . S i n c e t h e e l e m e n t s o u t s i d e t h i s , s u b a l g e b r a p l a y n o p a r t i n t h e w o r k i n g s o f t h e s t r u c t u r e , we w i l l a l w a y s a s s u m e t h a t B c o i n c i d e s w i t h t h i s s u b a l g e b r a . T h e f i r s t t w o t h e o r e m s o f t h i s s e c t i o n r e c o r d s o m e e l e m e n t a r y f a c t s a b o u t t h e f u n c t i o n E , ] : T h e o r e m 1. F o r a n y v , 6 a n d a , I C V V j ) 0 , a ] = i n f {(16 ,a ( j I x ) ] : x e U ^ } a n d t h i s i n f i m u m " e q u a l s [['0 fa('j l y ) 1 " f o r -some y e'"U^ l " f 'M " i s g o o d . P r o o f . U s e t h e d e f i n i t i o n o f V a n d t h e p r o p e r t y i n f a . = ( s u p a ! ) ' f o r a n y s u b s e t { a . } c B f o r w h i c h , t h e b o u n d s e x i s t . . i 1 i 1 1 . T h e o r e m 2. G i v e n a f o r m u l a <j> a n d v a l u a t i o n s a , 3 s u c h t h a t i f V j i s f r e e i n <j> , t h e n a ^ = b ^ , t h e n II<j>,a ! = [[<}>,g]. P r o o f . O n e f i r s t s h o w s t h a t f o r a n y t e r m t s u c h t h a t i f v ^ o c c u r s i n t . , a ^ = b j , t h e n [ t ] a = [ t ] g . T h e n i n d u c t i o n i s u s e d o n t h e l e n g t h o f <j> . C o r o l l a r y 3. I f § i s a s e n t e n c e , t h e n E<J),a] = EIJ'JB] f o r a l l v a l u a t i o n s a , .3 . I n v i e w o f t h i s c o r o l l a r y , w e w i l l w r i t e s i m p l y [I<j>] w h e n <j> i s a s e n t e n c e . A l s o , i f t h e f r e e v a r i a b l e s o f <j> a r e a mong v i » * * * » v n » we may u n a m b i g u o u s l y w r i t e II<J>;a , • • • , a ^ ] f o r a n y a^, • • ' e . We c a n , i f we w i s h , d e f i n e t h e r e l a t i o n P w i t h r e s p e c t t o B o o l e a n v a l u e d s t r u c t u r e s b y w r i t i n g M, a p tjj o r MP ip[a] w h e n Hip,a] = 1 , a n d a l s o M p i|) i f M,a P tp f o r a l l a . T h e p r o p e r t i e s p h a s w i t h r e s p e c t t o r e l a t i o n a l s t r u c t u r e s d o n o t a l l c a r r y o v e r t o B o o l e a n v a l u e d s t r u c t u r e s . I n p a r t i c u l a r , w e may h a v e M,a p <j> v b u t n e i t h e r Mta p <j> n o r M,a P i|» . A l s o , a l t h o u g h M,a p ~<j> i m p l i e s n o t M.a p $ , i t i s n o t t r u e t h a t n o t M.a p <j) i m p l i e s Mta P' ~<{> . T h e s e t w o f a c t s a r e i m m e d i a t e c o n s e q u e n c e s o f t h e f a c t t h a t t r u t h v a l u e s o t h e r t h a n 0 ( f a l s e ) a n d 1 ( t r u e ) a r e a l l o w e d . G i v e n a t h e o r y T a n d a s t r u c t u r e M f o r t h e l a n g u a g e o f . T , M i s s a i d t o b e a m o d e l o f T i f f o r e v e r y a x i o m $ o f T , M P <J> . G i v e n t w o s t r u c t u r e s M.N w e s a y t h a t M i s a s u b s t r u c t u r e o f N , o r 2V i s a n e x t e n s i o n o f M , w r i t t e n M c N , i f t h e f o l l o w i n g h o l d ( 1 ) U M c , ( 2 ) B ^ c B ^ ( a s a l g e b r a s ) , ( 3 ) f o r a l l P e , ?M = P ^ l u J , ( 4 ) f o r a l l f £ F n , f ^ = f ^ l u j , ( 5 ) f o r a l l c e C , cM = cN . . I f s o m e t i m e s h a p p e n s t h a t we d o n ' t h a v e a c t u a l s u b s e t s i n ( 1 ) a n d ( 2 ) b u t i n s t e a d a n i n j e c t i o n i : U „ a n d a m o n o m o r p h i s m g : B ^ —»-F o r ( 3 ) , ( 4 ) a n d (.5) we h a v e , r e s p e c t i v e l y : C3') f o r a l l P e , g ° P ^ = P ? / ° i n , (4») f o r a l l f. e F n i o f ^ = ' f f f o i n . , ( 5 ' ) - f o r a l l c e C , c ^ = i C c ^ ) . H o w e v e r , i f we i d e n t i f y w i t h i ( U ^ ) , w i t h g ( B ^ ) , e a c h P ^ w i t h P ^ | i n ( u ] J ) , e a c h f ^ w i t h . f ^ I i . n (IJJjjp a n d / e a c h c ^ w i t h i ( c ^ ) , t h e n w e c a n t r a n s f o r m s u b s t r u c t u r e s a c c o r d i n g t o t h i s s e c o n d d e f i n i t i o n i n t o s u b s t r u c t u r e s a c c o r d i n g t o t h e f i r s t d e f i n i t i o n w i t h o u t e s s e n t i a l l y c h a n g i n g a n y t h i n g . W i t h o u t e x p l i c i t l y m e n t i o n i n g i t , t h i s i s w h a t we s h a l l d o i n t h e f u t u r e . Now s u p p o s e M c N t I f a i s a v a l u a t i o n i n Af a n d cf> i s a f o r m u l a , i t i s n a t u r a l t o a s k h ow t h e v a l u e s I<f>,a]^  a n d I<j>,a]^  a r e r e l a t e d . I t i s e a s y t o s e e b y i n d u c t i o n t h a t i f <f> i s q u a n t i f i e r f r e e , t h e n II<j),a]^ = I<t>,a]^ . I f Af i s g o o d a n d <f> i s e x i s t e n t i a l ( t h e p r e n e x f o r m o f -<f> c o n t a i n s o n l y e x i s t e n t i a l q u a n t i f i e r s ) , t h e n ll<}>»a]^ ^ [ [ < ( > , > T h i s i s a n e a s y c o r o l l a r y o f a t h e o r e m o f C h a p t e r 3 , S i m i l a r l y , i f Af i s g o o d a n d <)> i s u n i v e r s a l ( t h e p r e n e x f o r m o f <}> c o n t a i n s o n l y u n i v e r s a l q u a n t i f i e r s ) , t h e n I<J>,a]^  S [ < j ) , a ] ^ • I n g e n e r a l , n o t h i n g c a n b e s a i d w h e n t h e . p r e n e x f o r m o f <j> c o n t a i n s b o t h u n i v e r s a l a n d e x i s t e n t i a l q u a n t i f i e r s . T h e r e a r e s t r u c t u r e s Af c N f o r w h i c h s o m e t h i n g v e r y s i m p l e a n d s t r o n g may b e s a i d c o n c e r n i n g t h e v a l u e s H({>,a3^ a n d l^>,aj^ . We s a y t h a t Af i s a n e l e m e n t a r y s u b s t r u c t u r e o f N, o r N i s a n e l e m e n t a r y e x t e n s i o n o f M , w r i t t e n Af < iV , i f : ( 1 ) M c N , ( 2 ) f o r a l l <j> a n d v a l u a t i o n s a i n M , Ucf>,a]^ = I<f>,a]^ . F o r g o o d s t r u c t u r e s t h i s m e a n s t h a t f o r a n y s u p r e m u m i n o f t h e f o r m sup{[I<j>,a(j l x ) ] ^ : x e U ^ } t h e r e i s among t h e e l e m e n t s d e w h i c h , r e a l i z e , t h e s u p r e m u m (([<(>,a ( j I d ) ] ^ = sup{I<f> , a ( j |x) : x e l l ^ } ) , a t l e a s J t o n e w h i c h i s a n e l e m e n t o f . L.W. S z c z e r b a [ 1 8 ] h a s g i v e n f i v e v a r i a t i o n s o f t h e d e f i n i t i o n o f e l e m e n t a r y s u b s t r u c t u r e a n d h a s s t u d i e d t h e i r p r o p e r t i e s a n d t h e i r i n t e r r e l a t i o n s . F o r o u r p u r p o s e s , t h e d e f i n i t i o n g i v e n a b o v e , w h i c h g e n e r a l i z e s t h e n o t i o n o f e l e m e n t a r y s u b s t r u c t u r e f o r r e l a t i o n a l s t r u c t u r e s , i s s u f f i c i e n t . T h e p r o o f s o f a n u m b e r o f t h e o r e m s i n l a t e r c h a p t e r s u s e g o o d s t r u c t u r e s i n a n e s s e n t i a l w a y . I f w o u l d b e o f v a l u e , t h e n , t o k n o w w h e n a g i v e n s t r u c t u r e c o u l d b e e x t e n d e d t o a g o o d s t r u c t u r e w i t h o u t c h a n g i n g t o o many o f t h e p r o p e r t i e s o f t h e s t r u c t u r e . T h e n e x t t h e o r e m s a y s t h i s c a n a l w a y s b e d o n e . T h e o r e m 4. F o r a n y s t r u c t u r e M t h e r e i s a g o o d s t r u c t u r e N s u c h t h a t M < N , t h a t i s , e v e r y s t r u c t u r e h a s a g o o d e l e m e n t a r y e x t e n s i o n . P r o o f . We w i l l p r o v e t h i s t h e o r e m i n C h a p t e r 5 w h e n we w i l l h a v e m o r e m a c h i n e r y a t h a n d , R u t k o w s k i [ 1 5 ] g i v e s a c o m p l e t e l y d i f f e r e n t p r o o f f r o m w h a t we s h a l l p r e s e n t . F r o m a s t r u c t u r e M i t i s p o s s i b l e t o c o n s t r u c t new B o o l e a n v a l u e d s t r u c t u r e s w h i c h may p r o p e r l y b e c a l l e d q u o t i e n t s o f M . T o f o r m a q u o t i e n t M o f M we n e e d a p r o p e r f i l t e r F o n B ^ a n d a n e q u i v a l e n c e r e l a t i o n ^ o n . I n o r d e r t h a t M b e w e l l d e f i n e d , F a n d 'v* m u s t h a v e c e r t a i n p r o p e r t i e s . T h e y a r e : ( 1 ) f o r a l l . P e P„ ., f e F• a n d a , , ? " , a ,b-,*'»,b g "U,. • n » n 1' * n ' 1* ' n M s u c h t h a t a , M ) , , • • •, a ^-b we h a v e 1 1 ' ' n n ( a ) [ P ^ ( a i , . . . , a n ) ^ . P w ( b ; L , . . . , b n ) ] g F , ( b ) f M ( a i , - . - , a n ) * f ^ b ^ . . . ^ ) , • ( 2 ) F p r e s e r v e s s u p r e m u m s o f t h e f o r m sup{(I<j>,a(j | x ) ] ^ : x e U ^ } , t h i s w i l l b e t r u e i f , f o r e x a m p l e , F i s c o m p l e t e o r i f M i s a _good s t r u c t u r e . When t h e s e c o n d i t i o n s a r e f u l f i l l e d , we d e f i n e M b y : ( 1 ) = U^/^ ( t h e s e t o f e q u i v a l e n c e c l a s s e s o f u n d e r ^) ( 3 ) i f P g , f g F a n d a ^ , * * * , a n e w i t h r e s p e c t i v e r e p r e s e n t a t i v e s r , * , , , r € U„. , t h e n 1 n M ( a ) P w ( a 1 ( —.a nX = P ^ , • • • , 0 / F , ( b ) f r } ( a 1 , " , , a ) = f , , ( r , , * * * , r ) ~ ( t h e e q u i v a l e n c e c l M L ' n M L n o f f M ( r . , • • • • , r ) ) , M 1 n ( 4 ) i f c 6 C , t h e n c ^ = c ^ . I t i s a n e a s y m a t t e r t o c h e c k t h a t =^ s a t i s f i e s t h e n e c e s s a r y a s s c o n d i t i o n s a n d t h a t E , l r , i s d e f i n e d (B-, h a s e n o u g h s u p r e m u m s ) . M M A l s o , f o r a n y v a l u a t i o n a i n M , l^,a"-J^ - tt cf) ,aH^/F . Now s u p p o s e M' i s t h e q u o t i e n t o f M b y F a n d ^ a n d s u p p o s e a ^ b . T h e n a . a n d b a r e e q u a l i n M s o ( a ~ =^ b ~ ) = 1 . B u t t h e r e may b e d i s t i n c t c l a s s e s c , d e s u c h t h a t ( c Hj^ d ) = 1 . B u t i f ^ i s t h e l a r g e s t p o s s i b l e . e q u i v a l e n c e - r e l a t i o n , i . e . , o n e s u c h t h a t a ^ b i f a n d o n l y i f ( a = M b ) e F , t h e n we w i l l h a v e ( c d ) " = 1 i f a n d o n l y i f c = d e . M o r e o v e r , i f F i s a n u l t r a f i l t e r a n d ^. i s t h e l a r g e s t p o s s i b l e , t h e n M i s a r e l a t i o n a l s t r u c t u r e . C h a p t e r 3 B a s i c T h e o r e m s T h e r e a r e t w o t h e o r e m s w h i c h a r e b a s i c t o t h e t h e o r y o f B o o l e a n v a l u e d s t r u c t u r e s j u s t a s t h e i r c o u n t e r p a r t s a r e b a s i c t o t h e t h e o r y o f r e l a t i o n a l s t r u c t u r e s . T h e s e a r e , o f c o u r s e , t h e c o m p l e t e n e s s a n d c o m p a c t n e s s t h e o r e m s . I n t h i s c h a p t e r t h e s e ^ t h e o r e m s a r e - p r o v e d , a n d i n t h e p r o c e s s we a l s o p r o v e t h e c o u n t e r p a r t o f L o s ' s t h e o r e m . S e c t i o n 1 H e n k i n T h e o r i e s a n d L i n d e n b a u m A l g e b r a s T h e d i f f i c u l t p a r t o f t h e C o m p l e t e n e s s T h e o r e m i s , g i v e n a c o n s i s t e n t t h e o r y T , t o c o n s t r u c t a m o d e l o f t h a t t h e o r y , T h e o n l y c o n c r e t e o b j e c t s we h a v e t o w o r k w i t h a r e t h e s y m b o l s o f t h e l a n g u a g e L o f T, s o t h e m o d e l , c a l l e d a H e n k i n m o d e l , m u s t b e b u i l t f r o m t h e s e o b j e c t s . T h e v a r i a b l e f r e e t e r m s o f L i t s e l f w o u l d b e a l o g i c a l c h o i c e f o r t h e u n d e r l y i n g s e t o f a m o d e l o f T . T h e p r o b l e m w i t h t h i s c h o i c e i s t h a t T may h a v e a n a x i o m o f t h e f o r m ( 3 V Q ) 8 b u t t h e r e may b e n o v a r i a b l e f r e e t e r m t s u c h t h a t TV 8 [ t ] . T h i s w o u l d m a k e i t h a r d t o a s s e r t t h a t ( 3 V Q ) 6 w a s t r u e i n t h e m o d e l . We o v e r c o m e t h i s , d i f f i c u l t y b y a d d i n g e n o u g h n e w a x i o m s a n d c o n s t a n t s t o T , A t h e o r y T H i s a H e n k i n t h e o r y i f f o r e v e r y c l o s e d f o r m u l a ( 3 y . ) 8 o f TJJ , t h e r e i s a c o n s t a n t s y m b o l c s u c h t h a t T r ( a v ^ e e [ c ] . ^ G i v e n a t h e o r y T- a H e n k i n t h e o r y T e x t e n d i n g T. i s c o n s t r u c t e d H •as f o l l o w s : We f i r s t d e f i n e t h e s p e c i a l c o n s t a n t s o f l e v e l n b y i n d u c t i o n o n n , T h e s p e c i a l c o n s t a n t s o f l e v e l 0 a r e j u s t t h e c o n s t a n t s y m b o l s o f L . Now s u p p o s e t h e s p e c i a l c o n s t a n t s o f l e v e l n h a v e b e e n c o n s t r u c t e d a n d s u p p o s e (avj ) x i s a c l o s e d f o r m u l a f o r m e d f r o m t h e c o n s t a n t s o f l e v e l n o r l e s s a n d t h e s y m b o l s o f L , w h e r e we a s s u m e t h a t a t l e a s t o n e c o n s t a n t o f l e v e l n a p p e a r s i n x • T h e n t h e s y m b o l c o n s i s t i n g o f t h e l e t t e r c w i t h s u b s c r i p t (3Vj)x i s a s p e c i a l c o n s t a n t o f l e v e l n+1 L e t Z/JJ b e t h e l a n g u a g e o b t a i n e d f r o m L b y a d d i n g - t h e s p e c i a l c o n s t a n t s o f a l l l e v e l s . T o e v e r y c l o s e d f o r m u l a (av.)x o f L t h e r e J H i s a s s o c i a t e d a u n i q u e s p e c i a l c o n s t a n t whoSs l e v e l i s o n e g r e a t e r t h a n t h e m a x i m u m l e v e l o f s p e c i a l c o n s t a n t s o c c u r r i n g i n x • i r c i s t h e s p e c i a l c o n s t a n t f o r (3v_.)x , (3v^)x x[c] i s t h e s p e c i a l a x i o m f o r We l e t 2^ b e t h e t h e o r y w i t h l a n g u a g e w h o s e a x i o m s a r e t h o s e o f T p l u s a l l s p e c i a l a x i o m s . C l e a r l y , 2V, i s a H e n k i n t h e o r y a n d 2" ti H e x t e n d s T , We m u s t b e s u r e , t h o u g h , t h a t t h e " i m p o r t a n t " t h e o r e m s o f 2" a r e s t i l l j u s t t h e t h e o r e m s o f T . T h e f o l l o w i n g t h e o r e m H a s s u r e s u s o f t h i s . T h e o r e m 1. T i s a c o n s e r v a t i v e e x t e n s i o n o f T . H T h e p r o o f o f t h i s t h e o r e m may b e f o u n d i n S h o e n f i e l d [ 1 7 ] . B e s i d e s a n u n d e r l y i n g s e t t h e o t h e r c o n c r e t e o b j e c t we m u s t b u i l d f r o m s y n t a c t i c a l m a t e r i a l s f o r o u r m o d e l i s a B o o l e a n a l g e b r a . I t t u r n s o u t t h a t a v e r y n a t u r a l o n e i s c l o s e a t h a n d . We a s s u m e t h a t • 21 i s a c o n s i s t e n t H e n k i n t h e o r y . L e t CF b e t h e s e t o f c l o s e d f o r m u l a s o f . We d e f i n e a n e q u i v a l e n c e r e l a t i o n = o n CF b y p u t t i n g <f> - IJJ i f a n d o n l y i f T \- ip . -We t h e n l e t H I cj> I b e t h e e q u i v a l e n c e c l a s s o f <j> e CF u n d e r = , a n d we s e t L = { I <j> I : <j>eCF} , | cf> | v = | < f ) V ^ | , | ij, | ' - \~$ | a n d 1 = U e C F .: 2,Rl-<j>} • T h e o r e m 2. L e t T„ a n d L b e a s a b o v e . T h e n L i s a B o o l e a n a l g e b r a . I n p a r t i c u l a r , v a n d ' a r e w e l l d e f i n e d a n d 1 i s a n e q u i v a l e n c e c l a s s . L i s c a l l e d t h e L i n d e n b a u m a l g e b r a o f 2" . T h e t h e o r e m i s p r o v e d i n B e l l a n d S l o m s o n f l ] . T h e p r o o f b a s i c a l l y i s j u s t a r i g o r o u s s t a t e m e n t o f t h e s i m i l a r i t y b e t w e e n t h e p r o p o s i t i o n a l a x i o m s f o r L a n d t h e H a x i o m s f o r a B o o l e a n a l g e b r a . T h e f a c t t h a t T„ I s a H e n k i n t h e o r y i s n o t n e e d e d t o s h o w t h a t L i s a B o o l e a n a l g e b r a , t h a t i s , a n y c o n s i s t e n t t h e o r y h a s a L i n d e n b a u m a l g e b r a . H o w e v e r , b e c a u s e T„ i s a H e n k i n t h e o r y , L h a s t h e f o l l o w i n g a d d i t i o n a l p r o p e r t y : T h e o r e m 3. F o r e v e r y c l o s e d f o r m u l a (3v^)c|> , |(3v^)<f>| = s u p { | < J > [ t ] l : teCT} a n d f o r s o m e c e• CT - v a r i a b l e f r e e t e r m s o f L n w e h a v e U [ c ] l = l ( 3 v J ) ( j ) | , P r o o f . B y t h e s u b s t i t u t i o n a x i o m , T h <j>[tl —*• (3v.)<{> f o r a l l H j t e CT , h e n c e I Cav^> <f> I i s a n u p p e r , b o u n d o f {|<p[tj | : teCT) . B u t i s a H e n k i n t h e o r y , s o f o r s o m e c o n s t a n t c , T^, h (av.)<f> ~* <{)[c] . S o f o r t h i s c , l(av.)<|>| = l<J)[c]l . S i n c e H 3 3 c e C T , | ( a V j ) < f i | m u s t b e t h e l e a s t u p p e r b o u n d . S e c t i o n 2 T h e C o m p l e t e n e s s T h e o r e m T h e n o t i o n o f v a l i d i t y w i t h r e s p e c t t o B o o l e a n v a l u e d s t r u c t u r e s i s f o r m a l l y t h e same a s w i t h r e s p e c t t o r e l a t i o n a l s t r u c t u r e s . N a m e l y , a f o r m u l a a i s v a l i d i n t h e t h e o r y ,T i f f o r e v e r y ( B o o l e a n v a l u e d ) m o d e l Af ..of T , we h a v e M t a . T h e f i r s t s t e p i n p r o v i n g t h e C o m p l e t e n e s s T h e o r e m i s t o s h o w t h a t a l l t h e o r e m s a r e v a l i d : T h e o r e m 1. E v e r y t h e o r e m o f P r e d i c a t e C a l c u l u s i s v a l i d i n a l l s t r u c t u r e s ( f o r L). P r o o f . L e t M b e a n y s t r u c t u r e f o r L a n d a a n y v a l u a t i o n i n Af We m u s t s h o w t h a t |- <}> i m p l i e s I c ( ) , a ] ^ = 1 < T h i s i s p r o v e d b y i n d u c t i o n o n t h e l e n g t h o f t h e p r o o f o f <j> < T h a t t h e p r o p o s i t i o n a l a x i o m s h a v e v a l u e 1 f o l l o w s i m m e d i a t e l y f r o m t h e p r o p e r t i e s o f B o o l e a n a l g e b r a s . F o r e x a m p l e , i f <j> i s 6 (ip 0) , t h e n l e -*• (ip e),a3 = lle,al (lip,a] tte.al)' = tte.a]* v (^,al' v 118,a]) = ( l 0 , a ] ' v iQ.al) v dip,a] = 1 v Hip,a]' = 1 . T h e v e r i f i c a t i o n f o r t h e o t h e r p r o p o s i t i o n a l a x i o m s i s a n a l o g o u s . T h e a x i o m s f o r e q u a l i t y h a v e v a l u e 1 p r e c i s e l y b e c a u s e o f t h e c o n d i t i o n s o n t h e f u n c t i o n =^ . F o r t h e s u b s t i t u t i o n a x i o m , l e t t b e a t e r m f r e e f o r v ^ i n i> . T h e n [t|»[t],a] =• I I * , a ( j I [ t ] a > ] ^ s u p { ^ , a ( j | x ) ] : xeU^> = [ I ( a v j ) > , a ] , s i n c e [ t ] a e -U^ . T h u s tt^t't] -*• ( a v )|fc,a]' = E ^ [ t ] , - a ] I -(av>i> , a l = 1 N e x t , l e t u s s h o w t h a t t h e V - i n t r o d u c t i o n a x i o m h a s v a l u e 1 , So l e t <J> b e a f o r m u l a i n w h i c h t h e v a r i a b l e v.. i n n o t f r e e . T h e n l x ) ] = I<J>,a] f o r a n y x £ a n d we h a v e tt(VVj)(<i> -> 4>) , a ] = inf{K<t> -*• * , a ( j l x ) ] : x e U ^ } = i n f (U , a ] 1 v M,a ( j |x) ] : x e U ^ J • = N>,alTv . i n f { [ * t o ( j | x ) I : x e U ^ } = 14>,a]' v II (Vv.. )4< ,a] = I<f>ta] [ ( W ^ ) ^ , a l ! = !<{>-> ( V v )<|»,a] ' T h u s [ ( W j X * ('i* ( V v ) * ) , a ] = 1 . T h e i n d u c t i o n s t e p s h o w s t h a t t h e i n f e r e n c e r u l e s , w h i c h b u i l d u p l o n g e r p r o o f s f r o m s h o r t e r o n e s , p r e s e r v e s a t i s f a c t i o n * F o r m o d u s p o n e n s , i f I- <{> a n d |- 4> —> ij> , t h e n b y t h e i n d u c t i o n h y p o t h e s i s I<j>,a] = 1 a n d HtaJ -+ I ^ , a ] l = l<f> tp,a] = 1 . F r o m t h i s we c a n c o n c l u d e t h a t 11^,al = 1 . O u r o t h e r i n f e r e n c e r u l e i s g e n e r a l i z a t i o n . S u p p o s e V $ . B y t h e i n d u c t i o n h y p o t h e s i s E<j>,&3 = 1 f o r a l l v a l u a t i o n s 3 « I n p a r t i c u l a r , H , a ( j l x ) J . = 1 f o r a l l x e . H e n c e I ( V v H ,aJ = i n f ( E * , a ( j l x ) ] : x e U > .= 1 . .We n e x t g e n e r a l i z e t h i s t h e o r e m t o n o n e m p t y t h e o r i e s . .The r e s u l t i s s o m e t i m e s c a l l e d t h e V a l i d i t y T h e o r e m . T h e o r e m 2. E v e r y t h e o r e m o f a t h e o r y T i s v a l i d i n T » P r o o f . L e t ^  b e a t h e o r e m o f T ; l e t M b e a n y m o d e l o f T a n d a n y v a l u a t i o n i n Af . B y t h e , r e d u c t i o n - t h e o r e m . t h e r e * , a r e . f o r m u l a s ip 1, ,",ip w h i c h a r e t h e c l o s u r e s o f a x i o m s o f T , s u c h t h a t I n ip A««»A ]\> —>- 4> i s a t h e o r e m o f P r e d i c a t e C a l c u l u s . B y t h e p r e v i o u s 1 n t h e o r e m , HT{J^  A«««A ip^  — * <J>,a] = 1 . B u t • Af • i s a m o d e l o f T s o Hijj^  A«««A tp ,a] = 1 . T h e r e f o r e we o b t a i n H4>ta] = 1 . Th e c o r o l l a r y f o l l o w i n g c a n b e p r o v e n w i t h o u t u s e o f T h e o r e m 4 b u t t h e V a l i d i t y T h e o r e m a l l o w s f o r a m o r e s i m p l e i n d u c t i o n . T h e c o r o l l a r y s t a t e s t h a t t h e p r o p e r t y g i v e n i n s t a t e m e n t ( g ) i n t h e d e f i n i t i o n o f I , c a n b e e x t e n d e d t o a n y n u m b e r o f q u a n t i f i e r s . C o r o l l a r y 3. L e t * b e a f o r m u l a o f L w i t h f r e e v a r i a b l e s v , , • • • • v a n d b o u n d v a r i a b l e s v - i » " * , v . . T h e r e i s a q u a n t i f i e r ' 1* ' n n + l ' ' n+m f r e e f o r m u l a 9 s u c h t h a t f o r a n y g o o d s t r u c t u r e Af a n d e l e m e n t s a . , • • • • a e U.. t h e r e a r e e l e m e n t s a . i » " * , a . e U.. w i t h 1 * * n . Af n + l ' ' n+m Af H ; a 1 , . . . , a n ] M = Ml*!,'" ,*n+JM-P r o o f . L e t 9 b e t h e m a t r i x o f t h e p r e n e x f o r m o f <f> . I f <j> a l r e a d y h a s n o q u a n t i f i e r s , t h e n 9 i s <j) a n d w e a r e d o n e . S u p p o s e t h e t h e o r e m i s t r u e f o r f o r m u l a s w i t h m-1 q u a n t i f i e r s . T h e p r e n e x f o r m o f <{> i s ( Q ^ m ) *" * ^ i v i ^ ® ( w h e r e t h e v a r i a b l e s a r e r e l a b e l e d i f n e c e s s a r y ) a n d <j> -*->- CC^v ) • • • (Q_^v_^) 9 1 S a t h e o r e m o f P r e d i c a t e C a l c u l u s . T h u s f o r a n y s t r u c t u r e Af a n d e l e m e n t s a ^ , « « ' , a n e , H*;a l t • • * , a ] = I ( Q m v m ) • • • ( Q 1 v 1 ) e ; a l f • * • ,a n ] l . B e c a u s e M_ i s a g o o d s t r u c t u r e , t h e r e i s a n a e U,, s u c h t h a t 1 ( 0 v ) • • • ( Q - v . ) 8 ; a , , • • •, n+m M Tn m 1 1 1 = [ I ( Q m _ i v m _ l ) * * * ( Q i v l > e ; a 1 » * * , » a n ' a n + m ] l ' B y t h e i n d u c t l o n h y p o t h e s i s t h e r e a r e e l e m e n t s a ,,,*••»a i m , -e U s u c h t h a t J V n + l n+nv-1 Af I^lVl)'"({!lvl)e'al»,,,'an'aJ = ^ V ^ W • P u t t l n 8 a l l t h i s t o g e t h e r we h a v e II<j>;a , • • • , a n ] J a l » * " » a n + m ^ * Now s u p p o s e T i s a c o n s i s t e n t t h e o r y w i t h l a n g u a g e L . We d e f i n a c a n o n i c a l s t r u c t u r e M f o r T i n t h e f o l l o w i n g m a n n e r : ( 1 ) t h e u n i v e r s e IT o f Af i s t h e s e t o f a l l v a r i a b l e f r e e Af t e r m s o f , t h e H e n k i n l a n g u a g e o f L , ( 2 ) b e c a u s e T i s c o n s i s t e n t , i t s H e n k i n t h e o r y i s a l s o c o n s i s t e n t ; t h e r e f o r e t h e L i n d e n b a u m a l g e b r a L o f ' T„ e x i s t s ; l e t B, = L , H M _ ( 3 ) f o r P e P a n d a..,««',a e U M l e t n l xi M P^(a^,•••,a^) = l P ( a ^ , * ' * , a ) l ; t h i s m a k e s s e n s e b e c a u t h e e l e m e n t s o f U a r e t e r m s i n L „ , M H ( 4 ) f o r f ~e~F a n d a , . • • • . a e U„. d e f i n e n 1 n M f f a , , * " ^ ) = f ( a . , » , # t a ) ; t h i s , t o o , m a k e s s e n s e Af x n 1 n s i n c e f ( a , • • • j a ) i s a v a r i a b l e f r e e t e r m o f L I n H a n d i s t h e r e f o r e a n e l e m e n t o f U,. , • Af s e 41 ( 5 ) f o r a l l c e C ( c o n s t a n t s o f L), l e t c ^ = c ; t h e c o n s t a n t s o f L a r e a l s o v a r i a b l e f r e e t e r m s o f L , s o H c.. i s w e l l d e f i n e d . M A t t h i s p o i n t , i t s h o u l d b e c l e a r w h y t h e s y m b o l = f o r t h e e q u a l i t y p r e d i c a t e i s d i s t i n c t f r o m t h e s y m b o l = f o r s e t - t h e o r e t i c e q u a l i t y . Of c o u r s e , t h a t M i s a c t u a l l y a s t r u c t u r e - r e q u i r e s p r o o f a n d t h e n e x t t h e o r e m g i v e s t h i s p r o o f , i . e . , i t p r o v e s t h a t h a s t h e n e c e s s a r y p r o p e r t i e s a n d t h a t B h a s e n o u g h s u p r e m u m s . I n a d d i t i o n , Af Af i s s h o w n t o b e a g o o d s t r u c t u r e w h i c h t u r n s o u t t o b e e s s e n t i a l f o r f u t u r e t h e o r e m s . T h e o r e m 4. L e t T a n d Af b e a s a b o v e . T h e n ( 1 ) W i s a g o o d s t r u c t u r e f o r L , Af ( 2 ) [ t ] = t [ a ] f o r a l l t e r m s t o f L a n d v a l u a t i o n s a i n Af , a ( 3 ) [ [ ( j ) , a ] ^ = l c j>[a]| f o r a l l f o r m u l a s <j> o f L a n d v a l u a t i o n s a i n Af . N o t e t h a t o n t h e l e f t - h a n d s i d e s o f ( 2 ) a n d ( 3 ) a i s c o n s i d e r e d a s a s e q u e n c e i n , w h i l e o n t h e r i g h t - h a n d s i d e s a i s a s e q u e n c e o f t e r m s o f L^. P r o o f . T o s e e t h a t ( 2 ) h o l d s , i t i s o n l y n e c e s s a r y t o r e c a l l t h e d e f i n i t i o n s o f t h e v a l u e o f a t e r m i n a s t r u c t u r e a n d o f i n s t a n c e s o f t e r m s . T h a t t h e e q u a l i t y f u n c t i o n =• , s a t i s f i e s t h e n e c e s s a r y c o n d i t i o n s Af i s j u s t a r e s t a t e m e n t o f t h e a x i o m s f o r e q u a l i t y i n t e r m s o f t h e L i n d e n b a u m a l g e b r a o f T. We c o m p l e t e t h e p r o o f o f ( 1 ) , i . e . , s h o w t h a t B ^ h a s e n o u g h s u p r e m u m s a n d a l s o a t t h e . s a m e t i m e v e r i f y ( 3 ) b y a n i n d u c t i o n o n t h e l e n g t h o f t h e f o r m u l a <j> . T o p r o v e t h i s f o r a t o m i c f o r m u l a s , l e t P e P a n d ' t - , * * * ^ r ' n 1 n b e t e r m s . T h e n E P ( t . • • • , t ) , a ] = P ( [ t ] , • • • , [ t l ) = l P ( t . [ a ] , • • •, t [ a ] ) I = | P ( t t ) [ a ] I . Now s u p p o s e t h a t f o r 1 n I n f o r m u l a s 0 a n d ip , . [ [8,a] and. (Lip-, a] a r e . d e f i n e d a n d e q u a l 10 [a] I a n d | i p [ a ] | r e s p e c t i v e l y . T h e n [10 v ^,otII = 1 0 ,a] V flip,all = I 8 . [ a ] | v ! ^ [ a ] l = 1(6 v i p ) [ a ] | a n d l l ~ 0,a] = tt0,a]' = | 0 [ a ] | ' =' | ~ 0 [ a ] | L a s t l y , l e t u s a s s u m e i t h a s b e e n s h o w n t h a t l l 0,Bl = |6[B]I f o r a l l v a l u a t i o n s 6 . I n p a r t i c u l a r , E 0 , a ( j i x ) ] = | 8 [ a ( j | x ) ] | f o r a l l x e U . We k n o w f r o m s e c t i o n 1 t h a t s u p { | 0 [ a ( j l x ) ] I : x e u \ ^ e x i s t s i n B M a n d e q u a l s I ( ( g v ) 8 ) [ a ] I . A l s o , s i n c e T i s a H e n k i n t h e o r y , t h e r e i s a c o n s t a n t d o f L s u c h t h a t l ( a v . ) 0 [ a ] | H 3 = I 6 [ a ( j | d ) ] l , i . e . , t h e r e i s a n e l e m e n t d e s u c h t h a t II(av ) 0 , a ] = I 8 , a ( j | d ) ] . T h e o r e m 5. L e t T b e a c o n s i s t e n t t h e o r y . T h e c a n o n i c a l s t r u c t u r e Af i s a m o d e l o f T , I f Af t= <f> , f o r a n y c l o s e d f o r m u l a <p o f T , t h e n T l - f . P r o o f . L e t ip b e a n a x i o m o f T . T h e n J F f , h e n c e T (- ip . H s o f o r e v e r y s e q u e n c e a o f v a r i a b l e f r e e t e r m s ( e v e r y v a l u a t i o n a I n Af) TV i p [ a ] a l s o . H e n c e l i p , a ] = lip [ a ] 1 = 1 . I f , c o n v e r s e l y , H. M Af t= ip a n d ip I s c l o s e d , t h e n T V ip s i n c e l i p I = l i p ] = 1 .• B e c a u s e H T i s a c o n s e r v a t i v e e x t e n s i o n o f T , T h ip . T h u s we may h e n c e f o r t h c a l l M t h e . c a n o n i c a l m o d e l of T * W i t h j u s t a l i t t l e m o r e w o r k we c a n e x p r e s s t h e s e r e s u l t s i n a m o r e f a m i l i a r f o r m : T h e o r e m 6 ( C o m p l e t e n e s s T h e o r e m A ) . A t h e o r y T i s c o n s i s t e n t i f a n d o n l y i f T h a s a m o d e l . P r o o f < I f T i s c o n s i s t e n t , i t h a s a ( g o o d ) m o d e l b y T h e o r e m 8. S u p p o s e T i s n o t c o n s i s t e n t b u t t h a t T h a s a m o d e l M . P i c k i n g a c l o s e d f o r m u l a <f> , we h p v e T j- * A ~* . B y t h e V a l i d i t y T h e o r e m , I * A ~<j>]| = 1 . B u t [[(j) A ~<j>] = [<j>] A H * ] 1 = 0 , a c o n t r a d i c t i o n . T h e o r e m 7 ( C o m p l e t e n e s s . T h e o r e m B ) . F o r a n y t h e o r y T a n d f o r m u l a * , T h <f> i f a n d o n l y i f * i s v a l i d i n T • P r o o f . I f T \- 4> t h e n * i s v a l i d i n . T b y t h e V a l i d i t y T h e o r e m , S u p p o s e * i s n o t a t h e o r e m o f T . T h e n T [ ~ a ] i s c o n s i s t e n t ( b y T h e o r e m 1 . 1 . 1 1 ) w h e r e a i s t h e c l o s u r e o f * , B y T h e o r e m . 9 , T [ ~ a ] h a s a g o o d m o d e l M . B y C o r o l l a r y 1.6 t h e r e i s a v a l u a t i o n a i n Af s u c h t h a t I * , a ] = l a ] - ff~a]' = 1' = 0 . T h e r e f o r e , * i s n o t v a l i d i n M , b u t Af I s a m o d e l o f T s o <j> i s n o t v a l i d i n T . I n s u m m a r y , b y n o t d e m a n d i n g t h a t r e a l i z a t i o n s o f L a s s i g n t h e e x t r e m e v a l u e s T r u e o r F a l s e t o e v e r y s e n t e n c e , w e h a v e b e e n a b l e t o p r o v e a c o m p l e t e n e s s t h e o r e m v e r y e a s i l y w i t h o u t u s e o f t h e U l t r a f i l t e r T h e o r e m o r t h e A x i o m o f . C h o i c e . A s a c o r o l l a r y , we.may p r o v e t h e C o m p l e t e n e s s T h e o r e m f o r r e l a t i o n a l s t r u c t u r e s : 44 T h e o r e m 8. A t h e o r y T i s c o n s i s t e n t i f a n d o n l y i f T h a s a r e l a t i o n a l m o d e l . P r o o f . I f T h a s a r e l a t i o n a l m o d e l , we a l r e a d y k n o w t h a t T i s c o n s i s t e n t . S o s u p p o s e T i s c o n s i s t e n t < B y T h e o r e m '6, T h a s a g o o d B o o l e a n v a l u e d m o d e l M . B y t h e U l t r a f i l t e r T h e o r e m , t h e r e i s a n u l t r a f i l t e r F o n B , L e t ^  b e t h e e q u i v a l e n c e r e l a t i o n M-d e f i n e d o n t>y s e t t i n g a ^  b i f a n d o n l y i f ( a =^ b ) e F , We h a v e s e e n i n s e c t i o n 2,2 t h a t M , t h e q u o t i e n t o f M b y F a n d ^  , i s a r e l a t i o n a l s t r u c t u r e . I f x 1 S a n y a x i o m o f T w i t h f r e e v a r i a b l e s a mong v , , " ' v a n d i f a-.,»»',a e U- w i t h r e s p e c t i v e r e p r e s e n t a t i v e s I n 1 ' ' n M r1 ' " ' ' x n 6 U M » t h e n I x ; a i , * " ' a n % = [ I x ; r 1 , - " , r n l w / F = 1/F = 1 , T h u s M i s a r e l a t i o n a l m o d e l o f 21 * P r o v i n g t h e C o m p l e t e n e s s T h e o r e m f o r r e l a t i o n a l s t r u c t u r e s v i a t h e C o m p l e t e n e s s T h e o r e m f o r B o o l e a n v a l u e d s t r u c t u r e s may b e l o o k e d u p o n a s a f a c t o r i z a t i o n o f t h e p r o o f i n t o a c o n s t r u c t i v e s t e p a n d a n o n c o n s t r u c t i v e s t e p : w e f i r s t c o n s t r u c t t h e B o o l e a n v a l u e d m o d e l a n d t h e n w e t a k e a q u o t i e n t b y a n u l t r a f i l t e r t o a r r i v e a t a r e l a t i o n a l m o d e l . T h e o r e m 8 a l s o i l l u s t r a t e s h o w B o o l e a n v a l u e d m o d e l s may b e t h o u g h t o f a s " p r e - m o d e l s " , A s a c o r o l l a r y , w h i c h w i l l b e u s e f u l l a t e r , w e t e l l w h e n t w o t h e o r i e s a r e e q u i v a l e n t . T h e o r e m 9. Two t h e o r i e s a n d w i t h t h e s a m e l a n g u a g e a r e e q u i v a l e n t i f a n d o n l y i f t h e y h a v e t h e same m o d e l s . P r o o f . S u p p o s e T- a n d T „ a r e e q u i v a l e n t a n d l e t M, b e a m o d e l o f , I f x i s a n a x i o m o f , x i s a t h e o r e m .of . H e n c e M >r x s o M i s a l s o a m o d e l o f • B y s y m m e t r y , - e v e r y m o d e l o f i s a m o d e l o f T . Now s u p p o s e a n d h a v e t h e s a m e m o d e l s a n d l e t x b e a t h e o r e m o f 2"2 • T h e n x * s v a l i d i n e v e r y m o d e l o f w h i c h m e a n s X f s v a l i d i n e v e r y m o d e l o f T' . H e n c e x i . s a t h e o r e m o f . S i m i l a r l y , e v e r y t h e o r e m o f i s a t h e o r e m o f T^ * S e c t i o n 3 T h e C o m p a c t n e s s T h e o r e m T h e C o m p a c t n e s s T h e o r e m c a n b e p r o v e d a s a s t r a i g h t f o r w a r d c o n s e q u e n c e o f t h e C o m p l e t e n e s s T h e o r e m a n d t h e F i n i t e n e s s T h e o r e m : T h e o r e m 1. A t h e o r y T h a s a m o d e l i f a n d o n l y i f e v e r y - f i n i t e s u b t h e o r y o f T h a s a m o d e l . P r o o f . I f T h a s a m o d e l M , t h e n M i s a m o d e l o f e v e r y f i n i t e s u b t h e o r y o f T . S u p p o s e e v e r y f i n i t e s u b t h e o r y o f T h a s a m o d e l . B y t h e C o m p l e t e n e s s T h e o r e m , e v e r y f i n i t e s u b t h e o r y o f T i s c o n s i s t e n t , s o b y t h e F i n i t e n e s s T h e o r e m , T i s c o n s i s t e n t . H e n c e , b y t h e C o m p l e t e n e s s T h e o r e m , T h a s a m o d e l . T h e r e i s , o f c o u r s e , a b s o l u t e l y n o t h i n g w r o n g w i t h t h i s p r o o f , b u t we h a v e r e a l l y n o t u s e d t h e m o d e l s o f t h e f i n i t e s u b t h e o r i e s o f T a t a l l i n g e t t i n g a m o d e l f o r T b e y o n d u s i n g t h e m t o s h o w t h a t e a c h f i n i t e s u b t h e o r y w a s c o n s i s t e n t . I t w o u l d b e m o r e s a t i s f y i n g i f w e c o u l d c o n s t r u c t a m o d e l o f T f r o m m o d e l s o f t h e f i n i t e s u b t h e o r i e s o f T b y a l g e b r a i c m e a n s a l o n e . One s u c h c o n s t r u c t i o n we e x c l u d e f o r r e a s o n o f i t b e i n g a n " e a s y w a y o u t " : f o r e a c h m o d e l t a k e a q u o t i e n t b y a n u l t r a f i l t e r , o b t a i n i n g a r e l a t i o n a l m o d e l o f e a c h f i n i t e s u b t h e o r y o f T , Now c o n s t r u c t t h e a p p r o p r i a t e u l t r a p r o d u c t o f t h e s e m o d e l s a s d o n e i n B e l l a r i d S l o m s o n t o o b t a i n a r e l a t i o n a l m o d e l o f T * I d e a l l y , w e w o u l d l i k e t o a l g e b r a i c a l l y p r o v e t h e C o m p a c t n e s s T h e o r e m a s s t a t e d i n t h e a b o v e t h e o r e m a n d w i t h o u t u s i n g t h e U l t r a f i l t e r T h e o r e m o r t h e A x i o m o f C h o i c e , U n f o r t u n a t e l y , o u r a l g e b r a i c c o n s t r u c t i o n w i l l a p p l y o n l y t o g o o d s t r u c t u r e s a n d i n g e n e r a l , we w i l l n e e d t h e A x i o m o f C h o i c e t o p r o v e t h a t t h i s c o n s t r u c t i o n h a s t h e d e s i r e d p r o p e r t i e s T h e c o n s t r u c t i o n i s a B o o l e a n v a l u e d a n a l o g o f t h e u l t r a p r o d u c t c o n s t r u c t i o n , L e t . { A f ^ : i e l } b e a n o n e m p t y f a m i l y o f g o o d s t r u c t u r e s f o r L a n d l e t F b e a p r o p e r f i l t e r o n I , T h e r e d u c e d p r o d u c t Af o f t h e f a m i l y {Af^ : i e l } b y F i s t h e g o o d s t r u c t u r e f o r w h i c h : ( 1 ) U ^ = 5 U i * w ^ e r e u i = UAf * A^f i S n o n e m P t v k v t h e A x i o m o f C h o i c e b u t AC i s n ' t n e e d e d i f L c o n t a i n s a n y c o n s t a n t s y m b o l s s i n c e i f c e C , t h e n { c . : i e l } e U,„ , w h e r e c . = c -i Af i ^ ( 2 ) d e f i n e a r e l a t i o n ^ o n II B , w h e r e B = B . b y s e t t i n g i i Af± b % c i f a n d o n l y i f { i e l : b.'u: } e F ; r o u g h l y s p e a k i n g , t h i s s a y s t h a t b e q u a l s . c a t " a l m o s t a l l c o o r d i n a t e s " s i n c e F m a y b e t h o u g h t o f a s t h e " l a r g e " s u b s e t s o f I , t h e n t h e s e t E = { b e l ^ : b ^ l } i s a p r o p e r f i l t e r o n II B.^ • l e t B = ( n B ) / E ; n o t e t h a t b / E = c / E M 1 i f a n d o n l y i f ( b / E ) ( c / E ) = 1 i f a n d o n l y i f ( b c ) / E = 1 i f a n d o n l y i f ( b -«-> c ) £ E i f a n d o n l y i f { i e l : (b-*-*c) =1} e F i f a n d o n l y i f { i e l : . ( b ^ c ) =1} . e F i f a n d o n l y i f { i e l : b ^ c ^ } e F i f a n d o n l y i f b a. c ; t h u s w e may w r i t e b ~ f o r b / E ; n o t e a l s o t h a t b ~ < c ~ i f a n d o n l y i f { i e l : b ^ S c ^ } e F , ( 3 ) i f P e ? n a n d a ^ , « , , , a n e , t h e n V v - ' V = ^ i i ' — ' W : i e I } • w h e r e p i = \ -( 4 ) i f f e F^ a n d a ^ » " " » a n € ^ » t n e n V V * ' ^ = { f i < a l i » " ' . * a n i ) : i e I > » W h e r e f i = \ ' ( 5 ) i f c e c? , t h e n c ^ = { c : i e l } , N a t u r a l l y , w e m u s t p r o v e t h a t M r e a l l y i s a g o o d s t r u c t u r e * T h i s i s d o n e i n t h e n e x t t h e o r e m w h e r e i t i s a l s o s h o w n how t h e t r u t h f u n c t i o n II , ]y i s r e l a t e d t o t h e t r u t h f u n c t i o n s I , ] ^ o f t h e A/^'s. T h i s r e l a t i o n i s t h e B o o l e a n v a l u e d a n a l o g o f L o s ' s T h e o r e m . T h e o r em 2. L e t {Af^ : i e l } , F a n d M b e a s a b o v e . T h e n Af i s a g o o d s t r u c t u r e f o r L a n d f o r a n y v a l u a t i o n a = ( a ^ , a 2 f • • • ) i n Af a n d a n y . f o r m u l a * , (l) I I * , a ] ^ = { I * , a ( i ) l £ : i e l } * " , w h e r e a ( i ) i s t h e v a l u a t i o n i n d e f i n e d b y a ^ ^ j = a j i ' P r o o f . T h e e q u a l i t y function = s a t i s f i e s the necessary conditions ' M since, f o r example, I f P e P and a»,««»,a e U,, , then at each n 1' ' n M * coordinate I , P ^ C a ^ , • • • ,a^ ±* • • » a n i ) A (a = ± b ± ) 5 P i ( a l i ' , " » V " * , a n i ) S ° F M ( a ^ ' " ' a y " ' ' a r ?  A ( a j B M b ) < P M(a 1,.-.,b,...,a n) . T o prove that has enough supremums„ that"these supremums are maximums and that (£) holds, we use induction on the length of cj> . .Af F i r s t note that f o r any term t , the i - t h component of [ t ] a £ I s the value of t i n Af. with respect to a ( i ) , that i s [t] - . e U. « Now f o r atomic formulas we have [ [ P ( t ^ , • • • , t n ) ,a = V ^ a . ' - W = { P l « t 1 ] a ( 1 ) , . . . , [ t n ] o ( l ) ) : i e l } ~ = { t t P ( t 1 , * * * , t n ) , a ( i ) l i : i e l } ~ . I f we have already shown that (l) holds f o r 6 and 1(1 , i t i s an easy matter to show that I t holds f o r 8 v a n d ~8 . Now suppose that (£) i s true f o r the formula 6 and a l l valuations 3 i n M , i n p a r t i c u l a r f o r the valuations a(j|x) , x e « N o t e that a ( j | x ) ( i ) = a C i X j I x ^ f o r a l l i e l . We must show that (£) holds f o r (av^)6 and that I ( av^)9,a]^ = H 8 , a ( j I d ) ] ^ f o r some d e , S i n c e each 'Af I s good, there i s , by the A x i o m of C h o i c e , an element d e such that 118 ,ct(i) Cj I d±) ] ± = I (3v.. ) 8 ,a (i ) 1± f o r a l l i e l . F o r each x , the set o f i such that 18 ,a(j |x) ( i ) ] ^ = He , a ( i ) (j Ix.^) ] < H 8 , a ( i ) ( j I d J ] i s I which i s i n F . H e n c e , Re.aCj l x ) ] w i i Af £ { i e , a ( i ) ( j l d ± ) ] : i e l } ~ f o r a l l x e U t f « B u t { H e . a C D C j I d ^ ^ : i e l } " = {[8 ,'a(j Id) ( i ) J± : i e l } ~ = He ,a(j I'd) 'is • a n e l e m e n t o f t h e s e t {[I 8 , a ( i I x ) l , : xgU,.} a n d t h e r e f o r e m u s t b e i t s M M . s u p r e m u m . .Thus . .[[ ( 3 v •) 8..,a] = I-8,a(j I d ) = {[16 , a ( i ) ( j I d ± ) 1 ± : i e . I } ~ = {[(avj)e,aCi)l t : iel}~ . L a s t l y , w e n o t e t h a t t h e f u n c t i o n U , m a p s o n t o B s i n c e e a c h f u n c t i o n I , ]L m a p s o n t o B^ « T r y i n g t o d e f i n e a r e d u c e d p r o d u c t f o r s t r u c t u r e s w h i c h , a r e r i ' " t n e c e s s a r i l y g o o d w o u l d l e a d u s t o t h e p r o b l e m o f s h o w i n g t h a t s u p { l e , a ( j l x ) I w : x e U ^ } = { s u p { I 6 , a ( i ) ( j [ x ± ) 1 ± : x ± e U > : i e l } " . T h i s a m o u n t s t o s h o w i n g t h a t t h e f i l t e r E p r e s e r v e s c e r t a i n s u p r e m u m s o r , e q u i v a l e n t l y , t h a t t h e f i l t e r F c o n t a i n s t h e m e e t o f a n i n f i n i t e n u m b e r o f e l e m e n t s o f F . I n g e n e r a l , t h i s i s n o t p o s s i b l e . W i t h t h i s t h e o r e m we „are a b l e _to..,prpve a w e a k e n e d f o r m o f t h e C o m p a c t n e s s T h e o r e m s o l e l y b y a l g e b r a i c m e a n s : T h e o r e m 3 ( C o m p a c t n e s s Theorem)« A t h e o r y T h a s a g o o d m o d e l i f a n d o n l y i f e v e r y f i n i t e s u b t h e o r y o f T h a s a g o o d m o d e l * P r o o f . I f T h a s a g o o d m o d e l M , t h e n Af i s a g o o d m o d e l o f e v e r y f i n i t e s u b t h e o r y o f T . Now s u p p o s e e v e r y f i n i t e s u b t h e o r y S o f T h a s a g o o d m o d e l Af ., We l e t I b e t h e s e t o f a l l f i n i t e s u b t h e o r i e s o f T . F r o m t h e f a m i l y {M : Sel} we w i l l c o n s t r u c t a r e d u c e d p r o d u c t w h i c h i s a m o d e l o f T . T o g e t a f i l t e r o n I f i r s t l e t S* = { 5 ' e l : S<=-S'} f o r e a c h S e l s o t h a t S c I . T h e s e t {S : Sel} h a s t h e f i n i t e * * r * -, i n t e r s e c t i o n p r o p e r t y s i n c e f o r a n y 5 l f » « * f S e {S : Sel} , S u « » » u ' S £ I a n d S, w-u S e 5, n«««n 5 . T h u s t h e f i l t e r F 1 n 1 ' ' n . 1 n g e n e r a t e d b y { 5 : S e l } i s p r o p e r a n d t h e r e d u c e d p r o d u c t M o f {Mg : Sel} b y F i s a g o o d s t r u c t u r e f o r L . We c l a i m M i s a m o d e l o f 2* . L e t '* b e a n a x i o m o f T : T h e t h e o r y S w h o s e o n l y n o n l o g i c a l a x i o m i s ,<j> i s i n I a n d M„ p <j> . S i n c e e v e r y 5' => S a l s o . p r o v e s o * <f> , 5 c { 5 e i : A?5*=<|>} , T h e r e f o r e { S e l : Ay=<|>} e F , i . e . , {5£l : f o r a l l v a l u a t i o n s 6 i n M I I ( j ) ,3(5)3^=1} £ F . S i n c e f o r e v e r y v a l u a t i o n a i n M , {Sel : H<j»,a(5)] =1} => { S e l : |[A,B(S)]=1} , we h a v e {Sel : H * , a ( 5 ) ]^=1} £ F f o r a l l a , T h u s I I<j) fa] w = { I < j ) , a ( 5 ) ] 5 : S e l } ~ = 1 a n d s o M p * , T h e r e f o r e Af . i s a g o o d m o d e l o f T . W i t h a m i n o r m o d i f i c a t i o n i t i s p o s s i b l e t o p r o v e t h e C o m p a c t n e s s T h e o r e m w i t h o u t u s i n g t h e A x i o m o f C h o i c e * We m a k e m o r e u s e o f t h e m o d e l s o f t h e f i n i t e s u b t h e o r i e s t h a n w a s d o n e i n T h e o r e m 1 , b u t n o t a s m u c h a s i n T h e o r e m 3. T h e o r e m 4, A t h e o r y T h a s a ( g o o d ) m o d e l i f a n d o n l y i f e v e r y f i n i t e s u b t h e o r y o f T h a s a m o d e l * . P r o o f . I f T h a s a m o d e l Af , t h e n Af i s a m o d e l o f e v e r y f i n i t e s u b t h e o r y o f T . Now s u p p o s e e v e r y f i n i t e s u b t h e o r y S o f T h a s a m o d e l M . B y T h e o r e m 2 . 2 . 4 t h e r e a r e g o o d s t r u c t u r e s N s u c h t h a t Mg ^  Ng. f ° r e v e r y S e l . L e t N b e t h e r e d u c e d p r o d u c t o f t h e f a m i l y {Nq : Sel}. J u s t a s i n T h e o r e m 3 we may s h o w t h a t If i s a m o d e l o f T . B u t now N i s t h e r e d u c e d p r o d u c t o f c a n o n i c a l s t r u c t u r e s a n d t h i s m e a n s t h a t t h e A x i o m o f C h o i c e i s n o t n e e d e d i n T h e o r e m 2 o r i n t h e d e f i n i t i o n o f N . F o r , f o r e x a m p l e , e a c h U c c o n t a i n s a s p e c i a l c o n s t a n t c c o r r e s p o n d i n g t o t h e f o r m u l a ( 3 V Q ) ( V Q H v ) a n d s o { c ^ , : Sel} I s i n . A l s o , i n s h o w i n g t h a t I (av^) 4>,a]^ = .{H<f),a(5)]^ : Sel}~ , we may c h o o s e d c t o b e t h e s p e c i a l c o n s t a n t f o r ( ( 3 v . ) <f>) [ a (£) ] " ( t h i s i s a s e n t e n c e o f L(Ng) w h i c h w i l l b e d e f i n e d i n C h a p t e r 5 ) . T h e n w e may c o n s t r u c t t h e s e q u e n c e { d : Sel] e U w i t h o u t u s i n g t h e A x i o m o f C h o i c e . We c l o s e t h i s s e c t i o n w i t h a c o m p a r i s o n o f t h e B o o l e a n v a l u e d r e d u c e d p r o d u c t w i t h t h e r e l a t i o n a l r e d u c e d p r o d u c t w h e n t h e s t r u c t u r e s a r e r e l a t i o n a l . L e t {Af^ : i e l } b e a f a m i l y o f r e l a t i o n a l s t r u c t u r e s a n d l e t F b e a p r o p e r f i l t e r o n I . T h e r e l a t i o n a l r e d u c e d p r o d u c t [ 4 ] Af o f iM : i e l } b y F h a s a s u n d e r l y i n g s e t , t h e p r o d u c t II U K. . X x r e d u c e d b y F , t h a t i s , U = ( I I U . ) / - w h e r e b - c i f a n d o n l y i f K X { i e l : b.^=c^} e F . I f M i s t h e B o o l e a n v a l u e d r e d u c e d p r o d u c t o f {M^ : i e l } b y F , t h e n we h a v e t h e f o l l o w i n g t h e o r e m : T h e o r e m 5. F o r a n y f o r m u l a <J> a n d a n y v a l u a t i o n a i n M , Af,a \F (f> i f a n d o n l y i f M ,a t= <j> , w h e r e a = (a~,a~,«««) . R . 1 Z . P r o o f . ••Af.'o t= 4> i f f 1 = l<\>,a] = { l l * , a ( i ) ] . : i e l } ~ i f f M 1 { i e l : tt4),a(i)] =1} e F i f f { i e l : Af. ,aCi)f=4>> e F i f f W D,a~ {= $ . i 1 R C o r o l l a r y 6, I f F i s a n u l t r a f i l t e r , t h e n "M a n d ~M a r e -2. R e l e m e n t a r i l y e q u i v a l e n t ( i n t h e r e l a t i o n a l s e n s e ) . I n v i e w o f t h i s c o r o l l a r y , we m a y c o n s i d e r t h e u l t r a p r o d u c t o f r e l a t i o n a l s t r u c t u r e s t o b e t h e q u o t i e n t b y a n u l t r a f i l t e r o f t h e B o o l e a n v a l u e d p r o d u c t s t r u c t u r e : , I n t h e u s u a l c o n s t r u c t i o n , t h e u n d e r l y i n g s e t i n r e d u c e d , w h i l e i n t h e c o n s t r u c t i o n g i v e n h e r e t h e B o o l e a n a l g e b r a i s r e d u c e d . 5 3 C h a p t e r 4 T h e • L o v e n h e i m - S k o l e m T h e o r e m s I n a B o o l e a n v a l u e d s t r u c t u r e M w h i c h i s n o t g o o d , a s t r a n g e t h i n g may h a p p e n . A l t h o u g h a s e n t e n c e ( 3 V Q ) O m a y b e t r u e ( h a v e v a l u e 1 ) i n M ,. t h e r e m a y b e no. a e. U . s u c h t h a t d a , a ] = 1 . . T h i s . n e v e r o c c u r s ..in g o o d B o o l e a n . v a l u e d as.tru.c.tur.es . . s i n c e ,.there„,is . a l w a y s a n e l e m e n t a e U s u c h t h a t I ( 3 v n ) a ] = [ a , a ] « I n t h i s r e s p e c t , M U g o o d B o o l e a n v a l u e d s t r u c t u r e s b e h a v e j u s t l i k e r e l a t i o n a l s t r u c t u r e s . A s a r e s u l t o f t h i s s i m i l a r i t y , t h e p r o o f o f t h e D o w n w a r d L o w e n h e i m -S k o l e m T h e o r e m f o r g o o d B o o l e a n v a l u e d s t r u c t u r e s i s e s s e n t i a l l y t h e s a m e a s t h a t f o r r e l a t i o n a l s t r u c t u r e s . T h i s p r o o f i s g i v e n i n s e c t i o n 1 o f t h i s c h a p t e r . T h e c a s e . o f t h e U p w a r d L o w e n h e i m - S k o l e m T h e o r e m i s q u i t e d i f f e r e n t . B e c a u s e we d o n o t h a v e t h e e q u a l i t y p r e d i c a t e i n t e r p r e t e d a s s t r i c t e q u a l i t y i n o u r s t r u c t u r e s , e l e m e n t a r y e x t e n s i o n s a r e t r i v i a l t o c o n s t r u c t , a n d c o n s e q u e n t l y , t h e U p w a r d L B w e n h e i m - S k o l e m T h e o r e m I s o f n o v a l u e , T h e r e a r e t w o q u e s t i o n s , t h e n , w h i c h s h o u l d b e a n s w e r e d : C a n w e p r o v e t h e D o w n w a r d L o w e n h e i m - S k o l e m T h e o r e m f o r s t r u c t u r e s w h i c h a r e n o t n e c e s s a r i l y g o o d ? C a n we f o r m u l a t e a n d p r o v e a m e a n i n g f u l U p w a r d L o w e n h e i m - S k o l e m T h e o r e m ? B o t h q u e s t i o n s h a v e a f f i r m a t i v e a n s w e r s a n d we s k e t c h t h e p r o o f s i n s e c t i o n 3 . I n t h e l a s t s e c t i o n we p r o v e a t h e o r e m w h i c h m a y b e t h o u g h t o f a s a n o t h e r v e r s i o n o f t h e U p w a r d L o w e n h e i m - S k o l e m T h e o r e m , a l t h o u g h i t s i n t e n d e d i n t e r p r e t a t i o n i s a s a t h e o r e m o n " u n i v e r s a l " o r " f r e e " : m o d e l s . S e c t i o n 1 T h e D o w n w a r d L»wenheim-Skolem. T h e o r e m T h e D o w n w a r d L b w e n h e i m - S k o l e m T h e o r e m f o r g o o d B o o l e a n v a l u e d s t r u c t u r e s w i l l c o n t a i n t h e t h e o r e m f o r r e l a t i o n a l s t r u c t u r e s a s a s p e c i a l c a s e . S i n c e t h e D o w n w a r d L b w e n h e i m - S k o l e m T h e o r e m f o r r e l a t i o n a l s t r u c t u r e s * i s s , known*... t c % he*, e q u i v a l e n t * to.*. t h e * Axiom.: o f * .Choice.,, t h i s ? a x i o m m u s t a p p e a r s o m e w h e r e i n o u r p r o o f . We a r e t h e r e f o r e f r e e t o u s e a n y f o r m o f t h e A x i o m o f C h o i c e a n d a n y p a r t o f t h e u s u a l t h e o r y o f c a r d i n a l n u m b e r s . R e c a l l t h a t t h e c a r d i n a l i t y o f t h e l a n g u a g e - L i s t h e c a r d i n a l i t y o f t h e s e t o f s y m b o l s o f L , S i n c e t h e r e a r e c o u n t a b l y m a n y v a r i a b l e s , t h i s c a r d i n a l i t y w i l l b e r^Q u n l e s s ; some s e t C,P^,F^,P-^,F2,"' i s u n c o u n t a b l e , i n w h i c h c a s e L w i l l b e t h e s u p r e m u m o f C%P^t'i,^P .F.^t "* F o r m u l a s o f L a r e f i n i t e s t r i n g s o f s y m b o l s o f L , h e n c e t h e c a r d i n a l i t y o f t h e s e t o f f o r m u l a s o f L i s L , A s w i t h r e l a t i o n a l s t r u c t u r e s , . t h e c a r d i n a l i t y o f a B o o l e a n v a l u e d s t r u c t u r e M, M , i s d e f i n e d t o b e j u s t U , T h e D o w n w a r d L o w e n h e i m - S k o l e m T h e o r e m f o r g o o d s t r u c t u r e s w i l l a p p e a r a s a c o r o l l a r y o f t h e f o l l o w i n g t h e o r e m o n t h e e x i s t e n c e o f e l e m e n t a r y s u b s t r u c t u r e s . T h e o r e m 1. L e t N b e a n i n f i n i t e g o o d s t r u c t u r e w i t h l a n g u a g e L s u c h t h a t L.< N , T h e n f o r a n y c a r d i n a l u b e t w e e n ' L a n d N , t h e r e i s a n e l e m e n t a r y g o o d s u b s t r u c t u r e M o f N w i t h c a r d i n a l i t y u , P r o o f . We w i l l c o n s t r u c t a n e l e m e n t a r y s u b s t r u c t u r e Af w h o s e u n d e r l y i n g s e t i s t h e u n i o n o f a n a s c e n d i n g s e q u e n c e o f s u b s e t s UQ C <=••• o f , e a c h o f c a r d i n a l i t y u « F o r c h o o s e a n y s u b s e t o f h a v i n g c a r d i n a l i t y u w h i c h c o n t a i n s a l l t h e d i s t i n g u i s h e d e l e m e n t s o f N , i . e . , a l l e l e m e n t s o f t h e f o r m c ^ f o r s o m e c e C . • T h i s . c h o i c e i s , , p o s s i b l e ? s i . n c e y-> L .« A s a n ; i n d u c t i o n . * h y p o t h e s i s , s u p p o s e u\ c U. c«.«c TJ, h a v e b e e n d e f i n e d . We c o n s t r u c t U, . a s v v 0 1 k k + 1 f o l l o w s : F o r e a c h f o r m u l a A w i t h f r e e v a r i a b l e s v „ , * * * , v a n d e a c h O n s e q u e n c e a , . • • • , a e U, t h e r e i s a n o n e m p t y s e t D c IT s u c h t h a t 1 n k N E (3VQ)<(>;a^, • • • »an3^ - ^ » ^ » a i » " " » a n ^ ^ o r a-"-l d e D . " L e t E b e a s e t c o n t a i n i n g o n e e l e m e n t f r o m e a c h o f t h e s e s e t s D , W h i c h p a r t i c u l a r d e D w e p u t i n E i s i m m a t e r i a l u n l e s s <$> h a s t h e f o r m VQ "= f ( v - j _ , • • • , v n ) f o r s o m e f e F^ . T h e n a n y b e s u c h t h a t [ b =jy f ^ ( a i » ' * * » a n ) ] = 1 w i l l b e i n D b u t we i n s i s t t h a t % ( a i » * ' * > a n ) i t s e l f b e . t h e e l e m e n t we p u t i n E . T h i s w i l l b e n e c e s s a r y i n o r d e r t o s h o w t h a t Af i s a s u b s t r u c t u r e o f N . T h e c a r d i n a l i t y o f t h e s e t o f f o r m u l a s o f L i s L a n d t h e c a r d i n a l i t y o f t h e s e t o f f i n i t e s e q u e n c e s a ^ » * * * » a n ^ s u » s o = ^'^ - ^'^ ~ V ' Now s e t U, , = U. u E . T h e n U. = y , B y i n d u c t i o n , we h a v e t h e d e s i r e d k+.l k k + 1 s e q u e n c e c •<=••• a n d we l e t U = Uu*^  w h i c h h a s c a r d i n a l i t y u « T o m a k e U I n t o a s u b s t r u c t u r e Af o f N w e r e s t r i c t t h e f u n c t i o n s • Af o f 217 t o U , N a m e l y , Af i s t h e s t r u c t u r e s u c h t h a t : Af ( 1 ) i s a s d e f i n e d , .n ( 2 ) f o r a l l P c P f l , P ^ = P ^ , ( 3 ) f o r a l l f e F , f , = f , J u " , t h i s m a p s u", t o U f o r . n ' M. N M M M . i f a 1 , . . . , a n e U k , t h e n f ^ , ; . . ^ ) = f f f ( a ^ ... f a n ) e U f c + 1 a s w e h a v e s p e c i f i e d , ( 4 ) f o r a l l c e C , c^.= c^,£ U Q c , ( 5 ) B ^ i s t h e s u b a l g e b r a o f B ^ g e n e r a t e d b y t h e r a n g e s of,. a l l , , t h f e f u n c t i p n S i P^.. . We m u s t s h o w t h a t M i s r e a l l y a g o o d s t r u c t u r e a n d t h a t ( e ) I<J>,a]^  = II*ta]^ f o r a l l f o r m u l a s A a n d v a l u a t i o n s a i n M • T h e e q u a l i t y f u n c t i o n =^ s a t i s f i e s t h e n e c e s s a r y c o n d i t i o n s b e c a u s e i t i s t h e r e s t r i c t i o n o f 5 t o U w . T o s h o w t h a t B w h a s N M M e n o u g h s u p r e m u m s , t h a t t h e s e s u p r e m u m s a r e a c t u a l l y m a x i m u m s a n d t h a t ( e ) h o l d s , i n d u c t i o n i s u s e d o n t h e l e n g t h -of <j> • I t i s n o t h a r d t o s h o w t h a t "(e) h o l d s when. A. i s a t p m l c , -and - g i v e n t h a t i t h o l d s f o r 9 a n d 6 , i t i s e a s y t o s h o w i t h o l d s f o r 9 v a a n d ~8 . Now s u p p o s e ( e ) h o l d s f o r 9. We may. s u p p o s e t h a t t h e f r e e v a r i a b l e s o f 9 a r e v n , « « * , v a n d w i t h o u t l o s s o f g e n e r a l i t y , we may q u a n t i f y n v Q . T h e n - 1 1 ( 3 ^ ) 9 , 0 1 ] =. [[ ( 3 v Q ) 9 j a . ^ • • • . a ^ ] ^ . L e t k b e t h e l e a s t i n t e g e r s u c h t h a t a ,'«»ja e TT , T h e n f o r s o m e d e U , II ( a v ) 9 ; a . , • •• , a ]„7 =..[[6;-d,a1,,»»«,a ]„and b y t h e i n d u c t i o n h y p o t h e s i s , u 1 n N I n N I 9 ; d , a 1 , * « » , a = [ [ 6 ; d , a . J w . Now f o r e a c h x e U „ , ' 1 ' n N 1 n M M I l 9 ; x , a 1 , " « , a n ] w = 1 9 j . * , ^ , • • • . a ^ ^ [ l 9 ; d , a l t • • • ,\iN = U;-d,&19y 9&nlM s o . : - [ [ 6 : d . a , , • • • , a J,. i s a n u p p e r b o u n d f o r t h e s e t I ti M {[[9 ; x , a - p • • • , a Q ] ^ : x e U ^ } b u t s i n c e d i t s e l f i s o n e o f t h e s e x ' s , i t i s t h e l e a s t u p p e r b o u n d . T h u s [I , ] i s d e f i n e d , f o r ( 3 v Q ) e a n d [ ( a v ( ) ) G ; a 1 , . - . , a n ] w . = G e ^ . a ^ • • - . a ^ = [ 6 j d ^ , • • • = I ( a v n ) 0 ; a , , • • • , a ]„ . So Af i s a g o o d e l e m e n t a r y s u b s t r u c t u r e o f N U 1 n N o f c a r d i n a l i t y y . •. Ifc?..i-s.-.worjfchwh-ii 'ei t-o?no:fce^t'hat3i--wfi»consteEU\efe-ed^.an'i! eitem.enfeariy-s u b s t r u c t u r e Af o f N e x a c t l y a c c o r d i n g t o t h e r e m a r k m a d e a f t e r t h e d e f i n i t i o n o f e l e m e n t a r y s u b s t r u c t u r e : We m a d e s u r e t h a t f o r e v e r y s u p r e m u m o f t h e f o r m s u p { U<j> ,a ( j I x ) J : x e U .} t h e r e w a s a t l e a s t o n e N N e l e m e n t i n U w h i c h r e a l i z e d t h i s supremum;. Af ;.The,orem v2.:\(Downward . ^ w ^ n h e i m s S k o ^ e ^ ^ h ^ o g e B ) - . - - X e t IT b e a ,t h e o r , y . . w i t h . . l a n g u a g e .L .and . s u p p o s e .T h a s .a ..good . m o d e l // ' w i t h N > L . T h e n f o r a n y c a r d i n a l y b e t w e e n L .and ,N , t h e r e i s a g o o d s u b s t r u c t u r e Af o f N o f c a r d i n a l y w h i c h I s a m o d e l o f T . P r o o f . B y t h e p r e v i o u s t h e o r e m , t h e r e i s a n e l e m e n t a r y g o o d s u b s t r u c t u r e Af o f N s u c h t h a t Af = y . F o r a n y a x i o m iji o f f a n d a n y v a l u a t i o n a i n Af., | [ i p , a ] ] ^ = [ [ i p , a ] ^ = 1 , h e n c e Af i s a m o d e l o f T • S e c t i o n 2 -A T r i v i a l U p w a r d m w e n h e i m ^ S k b l e m . .Theor.em T h e i n t e r p r e t a t i o n o f t h e e q u a l i t y p r e d i c a t e i n B o o l e a n v a l u e d s t r u c t u r e s a s we h a v e d e f i n e d t h e m n e e d n o t b e s t r i c t e q u a l i t y . T h a t i s , g i v e n a s t r u c t u r e Af a n d a n e l e m e n t a e U ^ , t h e r e m a y b e many d i s t i n c t e l e m e n t s b e U w s u c h t h a t ( a = M b ) = 1 . W i t h t h i s o b s e r v a t i o n i n m i n d , i t i s n o p r o b l e m a t a l l t o c o n s t r u c t e l e m e n t a r y e x t e n s i o n s o f Af w i t h a n y d e s i r e d c a r d i n a l i t y K > W, S p e c i f i c a l l y , l e t < b e a n y c a r d i n a l s u c h t h a t . K > Af , T o g e t . a n e l e m e n t a r y e x t e n s i o n N o f y w i t h c a r d i n a l i t y K , we s i m p l y a d d K c o p i e s o f s o m e a r b i t r a r y e l e m e n t a 0 £ A^f ' ^ u s l e t A b e a n y s e t w i t h c a r d i n a l K . We d e f i n e N a s . f o l l o w s : ( 1 ) U^-.= A u , w h e r e • t h i s i s a d i s j o i n t u n i o n , n o t e = K , <2> *N = BM > ( 3 ) i f P e a n d a . ^ * " ^ e , t h e n p ^ ( a i » * * * » a n ) = ' Pj/ ai»* w h e r e a j = a . i f a . e U , i 1 I M ~ ao i f a i 6 A » ( 4 ) i f - f e F^ a r i d a . ^ * *"• » a n "£ " u w , t h e n ' f j / C a l f • , a ^ ) = f ^ ( a . [ , • • ;wher.e ;the .al''s,,ar.'e;;.as rahov.e, ( 5 ) i f c e C , cN = cM . F r o m ( 3 ) a n d ( 4 ) we s e e t h a t e l e m e n t s o f A, b e h a v e e x a c t l y l i k e a ^ . I n p a r t i c u l a r , ( a =^ a g ) = 1 f o r a l l a-e A . I t i s n o w a s i m p l e m a t t e r t o s h o w t h a t N i s a s t r u c t u r e a n d t h a t M < N . Now g i v e n a n y t h e o r y T w i t h a n i n f i n i t e m o d e l Af a n d g i v e n a n y c a r d i n a l < S Af ,. c o n s t r u c t N a s . a b o v e . T h e n N = K t N e x t e n d s Af a n d N i s a m o d e l o f T . S e c t i o n 3 T h e T h e o r e m s f o r S t r u c t u r e s w i t h S t r i c t E q u a l i t y We w i l l c a l l a s t r u c t u r e M s u c h t h a t f o r a l l a,b e U , Af ( a = M b ) = 0 i f a * b = 1 i f a = b a s t r o n g s t - r u c t u r - e - . I n - other*-word-s^, t h e * e q u a l i t y - p r e d i c a t e * ' i s i L i n t e r p r e t e d a s s t r i c t e q u a l i t y i n a s t r o n g s t r u c t u r e . F o r t h e s e s t r u c t u r e s - t h e c o n s t r u c t i o n o f t h e p r e c e d i n g s e c t i o n i s n o t p o s s i b l e . One w o u l d a s k , t h e n , i f a n U p w a r d L o V e n h e i m - S k o l e m t h e o r e m h o l d s f o r s t r o n g s t r u c t u r e s . T h e a n s w e r i s y e s w h i c h f o l l o w s i m m e d i a t e l y f r o m t h e n e x t t h e o r e m . ...Theorem 1. I f A f i s a s t r o n g s t r u c t u r e f o r L of i n f i n i t e c a r d i n a l i t y u a n d i f K ^ max.{y.,L.} t, t h e n . t h e r e : is-'a : :;,stjcoing\;'e^l.ementary e x t e n s i o n N o f Af o f c a r d i n a l K . P r o o f . I n t h e p r o o f g i v e n b y L.W. S z c z e r b a [ 1 8 ] , t h e B o o l e a n v a l u e d s t r u c t u r e Af i s a s s o c i a t e d . w i t h a c e r t a i n r e l a t i o n a l s t r u c t u r e Af ' . I n p a r t , A f ' c o n s i s t s o f t h e f o l l o w i n g : U „ , c o n t a i n s U , , B,, M M M a n d t h e f o r m u l a s , o f L . F o r e a c h f u n c t i o n P ^ : U ^ —>• B ^ t h e r e i s a f u n c t i o n f ^ , : U*^ —*• U^, w h i c h a g r e e s w i t h P ^ o n U ^ . Now u s i n g s o m e . t h e o r e m s o f r e l a t i o n a l s t r u c t u r e s , a n e l e m e n t a r y e x t e n s i o n N* o f A f ' w i t h c a r d i n a l i t y K i s c o n s t r u c t e d . T o N1 i s a s s o c i a t e d a s t r o n g B o o l e a n v a l u e d s t r u c t u r e N a n d N h a s c a r d i n a l < a n d i s a n e l e m e n t a r y e x t e n s i o n o f Af . T h e s a m e t e c h n i q u e w i l l a l s o w o r k t o p r o v e a D o w n w a r d L B w e n h e i m -S k o l e m t h e o r e m : 6 0 = 3 s w T h e o r e m 2. I f /I/ i s a s t r o n g s t r u c t u r e f o r L s u c h t h a t /I/ > L , t h e n f o r a n y c a r d i n a l y b e t w e e n L a n d N t h e r e i s a s t r o n g e l e m e n t a r y s u b s t r u c t u r e M o f N w i t h M - y « We now h a v e t h e t h e o r e m f o r g o o d s t r u c t u r e s a n d f o r s t r o n g ; s t r u c t u r e s . I f * t u r n s . - o u t t h a t t h e r e i s n o p r o b l e m i n g o i n g f r o m ( n o t n e c e s s a r i l y s t r o n g ) s t r u c t u r e s t o s t r o n g s t r u c t u r e s a n d t h e n b a c k a g a i n a n d w e c a n t h e r e f o r e u s e t h e l a s t t h e o r e m t o p r o v e t h e D o w n w a r d L O w e n h e i m -S k o l e m T h e o r e m f o r g e n e r a l B o o l e a n v a l u e d s t r u c t u r e s . T h e o r e m 3. I f N i s a n y s t r u c t u r e f o r L s u c h t h a t N £ L , t h e n f o r a n y c a r d i n a l y b e t w e e n L a n d N t h e r e i s a n e l e m e n t a r y s u b s t r u c t u r e M o f N w i t h M - y , P r o o f . L e t L1 b e t h e l a n g u a g e w h i c h i s i d e n t i c a l t o L e x c e p t f o r h a v i n g =' a s i t s e q u a l i t y p r e d i c a t e ( L ' s t i l l h a s t h e b i n a r y p r e d i c a t e = ) . We l e t N1 b e t h e s t r o n g s t r u c t u r e f o r L1 o b t a i n e d f r o m N b y s e t t i n g t o b e t h e i d e n t i t y f u n c t i o n o f . B y T h e o r e m 2, N* h a s a s t r o n g e l e m e n t a r y s u b s t r u c t u r e M1 o f c a r d i n a l i t y y , B y d r o p p i n g t h e f u n c t i o n , we o b t a i n a s t r u c t u r e M f o r L s u c h . t h a t M < N - a n d M. = \i . 6 1 S e c t i o n 4 U n i v e r s a l M o d e l s o f a T h e o r y O n e may s e e f r o m t h e d e f i n i t i o n o f t h e c a n o n i c a l m o d e l Af o f a t h e o r y T t h a t Af i s a s e m a n t i c a l s t r u c t u r e , i n t h e B o o l e a n v a l u e d s e n s e , i n v e s t e d w i t h m u c h o f t h e s y n t a c t i c a l i n f o r m a t i o n a b o u t T « S i n c e e v e r y m o d e l o f T , whether.., r e l a t i o n a l o r : E p p l e a n v a l u e d , • c o n t a i n s some d a t a o n 2" , s u c h a s " t h e s e s e n t e n c e s a r e c o n s i s t e n t w i t h T ..." o r " t h e s e s t a t e m e n t s a r e n o t p r o v a b l e f r o m T ..." , i t s h o u l d n o t b e s u r p r i s i n g t h a t e v e r y m o d e l o f T i s a q u o t i e n t o f t h e c a n o n i c a l s t r u c t u r e s u i t a b l y m o d i f i e d . T h e m o d i f i c a t i o n c o n s i s t s o f a d d i n g t h e p r o p e r n u m b e r o f " f r e e " e l e m e n t s t o t h e u n d e r l y i n g s e t o f Af . T h e m a i n p r o p e r t y o f t h e s e u n i v e r s a l m o d e l s , i s g i v e n ' m o r e e x a c t l y - i n - t h e f o l l o w i n g - t h e o r e m : T h e o r e m 1. L e t T b e a c o n s i s t e n t t h e o r y a n d l e t K b e a n y c a r d i n a l . T h e r e i s a m o d e l N o f T w i t h t h e p r o p e r t y t h a t f o r e v e r y m o d e l M o f T o f c a r d i n a l i t y £ K t h e r e i s a q u o t i e n t N o f /If s u c h t h a t Af * N ... P r o o f . L e t D b e a s e t w i t h c a r d i n a l i t y K a n d l e t L ' b e t h e l a n g u a g e L o f T w i t h D a d d e d a s new c o n s t a n t s y m b o l s . .We l e t 2" b e t h e . t h e o r y w i t h l a n g u a g e L* w h o s e n o n l o g i c a l a x i o m s a r e t h o s e o f T . B y T h e o r e m 1 . 1 . 6 , 2" i s a c o n s e r v a t i v e e x t e n s i o n o f T , s o 2" i s a l s o c o n s i s t e n t . T h u s 2" h a s a c a n o n i c a l m o d e l a n d w e l e t N b e t h i s m o d e l r e s t r i c t e d t o L , i . e . , we f o r g e t a b o u t t h e d i s t i n g u i s h e d e l e m e n t s c o r r e s p o n d i n g t o D . N o t e t h a t N i s a m o d e l o f T . T o s e e t h a t N h a s t h e p r o p e r t y c l a i m e d , s u p p o s e Af i s a m o d e l o f T w i t h M < K . T h e r e i s t h e n a n o n t o f u n c t i o n j : D —* U '. Af A We w i l l m a k e Af i n t o a m o d e l -Af o f T' , t h e H e n k i n t h e o r y o f T1 . H T h e c o n s t a n t s o f L' a r e C u Z? u H . w h e r e H i s t h e s e t o f s p e c i a l H ' H e n k i n c o n s t a n t s . F o r c e C , c ^ i s a l r e a d y d e f i n e d . I f c e D , -'set - c ^ ~ j ( c ) . Now e a c h s p e c i a l c o n s t a n t ? ' b e l o n g s t o , - a c e r t a i n - l e v e l o f KH . T h e s p e c i a l c o n s t a n t s o f l e v e l 0 a r e j u s t t h e e l e m e n t s o f C.u D a n d w e .have a l r e a d y d e f i n e d t h e e l e m e n t s o f U , c o r r e s p o n d i n g Af t o t h e s e c o n s t a n t s . " S u p p o s e t h e d i s t i n g u i s h e d e l e m e n t s o f f o r a l l s p e c i a l c o n s t a n t s o f l e v e l n o r l e s s h a v e b e e n d e f i n e d . I f c ; i s a s p e c i a l c o n s t a n t o f l e v e l n + l , c c o r r e s p o n d s t o a s e n t e n c e ( 3 v ^ . ) * o f I V w h e r e a l l t h e s p e c i a l c o n s t a n t s o c c u r r i n g i n <j> a r e o f l e v e l n o r l e s s . ; L e t c b e some e l e m e n t Of U,, s u c h " t h a t Af Af I ( a v . . ) * J ^ = I * , c ] ^ . N o t e t h a t t h i s d e f i n i t i o n r e q u i r e s t h e A x i o m o f C h o i c e . •; T h e n o n l o g i c a l a x i o m s o f T' a r e t h e n o n l o g i c a l a x i o m s o f T p l u s H * t h e s p e c i a l H e n k i n a x i o m s . M s a t i s f i e s t h e n o n l o g i c a l a x i o m s o f T * b e c a u s e Af d o e s , a n d Af s a t i s f i e s t h e s p e c i a l H e n k i n a x i o m s b y * , c o n s t r u c t i o n . T h u s Af i s a m o d e l o f 2" . H To d e f i n e t h e f i l t e r , l e t 9 b e a s e n t e n c e o f £ ' . T h e n l e t H 19| e F i f a n d o n l y i f C 9 ] ^ = 1 . F i s w e l l d e f i n e d , f o r i f Af * 19 | = , t h e n h 9 > a n d t h e r e f o r e 119 $}Mie = 1 . -T h i s m e a n s 1 8 ] = W,^ s o H03__ = 1 i f a n d o n l y i f UI,,. =' 1 . Af* M* Af* M* A s i m i l a r p r o c e d u r e s h o w s t h a t t h i s d o e s d e f i n e a f i l t e r , w h i c h , c l e a r l y i s p r o p e r . We w i l l h a v e a n i s o m o r p h i s m g : B ^ / F —+ BM b y d e f i n i n g JM g(iei/F)--= del Af* ' g i s w e l l d e f i n e d a r i d o n e - t o - o n e b e c a u s e 6-1 / F = l i p l . / F i f a n d o n l y i f 6 1/F l ^ l / F i f a n d o n l y , i f ip I e F i f and only i f H.6 *3 i f and only i f II9] W * = W^*. • g i s onto because the term 'M* ,A f * e v a l u a t i o n - map. [ ] f r o m U , •the>va.r^ia;ble-'free 1<feer.mS' o f -i s o n t o . L a s t l y , g i s o b v i o u s l y a h o m o m o r p h i s m . t o t . t 1 ] T h e Af*.. e q u i v a l e n c e ^ o n i s d e f i n e d b y t ^ ^ i f a n d o n l y i f [ t 2 ] ,A f * Af* T h e n t h e b i j e c t i o n i : U ^ / ^ t l 'Af i s given b y i ( t ~ ) •= [tV We m u s t c h e c k t h a t t h e f u n c t i o n s a n d p r e d i c a t e f u n c t i o n s o f Af a r e w e l l d e f i n e d ' ; ' I f ' f. e F , P e - P ., t . , • • «;,'t V l L . A "arid n n 1 ri A7 tVV't:' , ••• , t ^ t' ., then " f i r s t l y ; , •>- 1 n n = [P(tj_,« = W • , v n ) ; [ t / A , ( l P ( v Af* .f rAf*i . , - . - , v ) ; [ t ' l , - - - , [ t ' F ] I n - 1 n , t ^ ) ] ^ s o t h a t P i l ? ( t 1 , . . - , t n ) / F = l P ( t l f . - . f t n ) l / F . , t ; ) i / F •= P^ct'.-.-.t;) . T h u s p-ct~,...,t~) • , t n ) / F i s . w e l l d e f i n e d . S e c o n d l y , [ f ^ C ^ , • • • ,t ) ] Af* . . , A f * , / r tM* ' r l A f * \ . t M l ^ * = Tf Ct' • • • . t ' ' ) l ^ * T h e r e f o r e , V ^ l ' * * * ' ^ = f A - ( t l » ' * * ' t n ) " ' i s w e l l d e f i n e d . T h e l a s t s t e p i s t o c h e c k t h a t t h e p a i r i , g . i s a n i s o m o r p h i s m N Af* I f c £ C , t h e n i ( c _ ) = i ( c ~ ) = i ( c " ) •= [ c ] f £ Fn a n d t £ , " - , t ~ £ , t h e n i ( f ^ ( t ] [ , • • • , t ~ ) ) = C M * = C M ' I f ,Af*. = Kf^C^,...,^)-) =-i(f(t 1,...,t n)-). = [fO^,-..,^)] = f^([t/*,---,[tnr) = f^ ( i ( t i - ) , . , . , i ( t ; ) ) = yi(t1),...,i(t;)) P e P n a n d t £ , - - - , t ~ e f t h e n g(P^(t~,» g ( P W ( t l - * * * ' t n ) / F ) = g C l P ( t i ' * , * » t n ) l / F ) = V ^ t 1 ] ^ , . . . , [ t n ] ^ ) = p ^ . ( i ( t i ) ) . . . , i ( t ; ) ) . P M ( i ( t l ) » * , * ' i ( t n ) ) ' 65 C h a p t e r 5 C h a r a c t e r i z a t i o n T h e o r e m s I t i s k n o w n [ 1 7 , p p . 7 6 , 7 7 , 9 4 , 9 5 ] i n a n u m b e r o f c a s e s t h a t a t h e o r y i s e q u i v a l e n t t o o n e w h o s e a x i o m s , a r e i n a c e r t a i n c l a s s i f a n d o n l y i f t h e c l a s s o f r e l a t i o n a l m o d e l s o f t h e t h e o r y i s c l o s e d u n d e r o n e o r m o r e a l g e b r a i c x q p e r a t i o n s . / P r o v i d i n g we ...can.. d e f i n e ,cpi".r :es;p B o o l e a n v a l u e d s t r u c t u r e s , t h e same t h e o r e m s s h o u l d h o l d . w i t h " r e l a t i o n a l m o d e l " r e p l a c e d b y " B o o l e a n v a l u e d m o d e l " . T h i s m u s t b e t r u e , f o r i f we h a d a B o o l e a n v a l u e d c o u n t e r e x a m p l e o f o n e o f t h e s e t h e o r e m s , t h e n b y t a k i n g m a x i m a l q u o t i e n t s we w o u l d . o b t a i n a r e l a t i o n a l c o u n t e r e x a m p l e , p r o v i d e d . t h a t t h e q u o t i e n t o p e r a t i o n c o m m u t e d w i t h •She a l g e b r a i c o p e r a t i o n s . , i n v o l v e d . I n t'he p r o o f s "below'.we s h o u l d n o t u s e t h e .-Axiom o f C h o i c e , o r t h e U l t - r a f I - l t e * r ' T h e p r e m r ' s l n c e -t h e a b o v e r e m a r k s c o n s t i t u t e a p r o o f o f a n y c h a r a c t e r i z a t i o n t h e o r e m f o r w h i c h t h e a l g e b r a i c o p e r a t i o n s a r e d e f i n e d on. B o o l e a n v a l u e d s t r u c t u r e s a n d c o m m u t e w i t h t h e q u o t i e n t o p e r a t i o n . I n s e c t i o n 1 , some n e c e s s a r y l e m m a s a r e p r o v e n a n d i n s e c t i o n 2 c h a r a c t e r i z a t i o n s o f o p e n t h e o r i e s a n d e x i s t e n t i a l t h e o r i e s a r e g i v e n . ' S e c t i o n -1 T h e M o d e l E x t e n s i o n T h e o r e m a n d O t h e r Lemmas T h e M o d e l E x t e n s i o n T h e o r e m c a n b e p r o v e d i n a ' m o r e g e n e r a l f o r m t h a n i s a c t u a l l y n e e d e d . F o r t h i s g e n e r a l f o r m we n e e d t h e n o t i o n o f a T - s u b s t r u c t u r e : L e t M a n d N b e s t r u c t u r e s f o r . a l a n g u a g e L a n d l e t T b e a s e t o f f o r m u l a s o f . L . We s a y M i s a r - s u b s t r u c t u r e o f N , o r t h a t N i s a r - e x t e n s i o n o f M , i f ( 3 ) f o r a l l f e Fn , ^ = ' ^ 1 ^ , ( 4 ) f o r e v e r y <j> e T a n d e v e r y v a l u a t i o n a i n M , A s w i t h t h e d e f i n i t i o n o f ( o r d i n a r y ) s u b s t r u c t u r e , we may h a v e - a n i n j e c t i o n i : —> U^ ,7 i n s t e a d i f U^ ,, c a n d a m o n o m o r p h i s m g : B,, -r-*- B „ r a t h e r t h a n B,. c B „ . I n t h i s c a s e , ( 3 ) a n d (4.) b e c o m e : M N M N (3«) f o r a l l f e Fn , i ° f ^ = f ^ ° i n , ( 4 ' ) f o r e v e r y <j> e T a n d e v e r y v a l u a t i o n a i n M , &U,^M = L<f»,i(a)]^ . We w i l l m a k e t h e s a m e i d e n t i f i c a t i o n o f t h i s c a s e w i t h t h e s t r i c t r - s u b s t r u c t u r e s a s we d i d w i t h ( o r d i n a r y ) s u b s t r u c t u r e s . Two p r e v i o u s d e f i n i t i o n s a r e s p e c i a l c a s e s o f r - s u b s t r u c t u r e s : I f T i s t h e s e t o f o p e n f o r m u l a s o f L , t h e n M i s a r - s u b s t r u c t u r e o f N i f a n d o n l y i f M i s a ( n ) ( o r d i n a r y ) s u b s t r u c t u r e o f N « I f T i s t h e s e t o f a l l f o r m u l a s o f L , t h e n AT i s a T - s u b s t r u c t u r e o f N i f a n d o n l y i f M i s a n e l e m e n t a r y s u b s t r u c t u r e o f N . I f T i s a s e t o f f o r m u l a s , w e l e t T* b e t h e s e t o f a l l B o o l e a n  c o m b i n a t i o n s o f f o r m u l a s i n T . A p r e c i s e d e f i n i t i o n i s b y i n d u c t i o n : ( 1 ) r c r * , ( 2 ) . i f <J>,4» e T* , t h e n ~<j> e T* .and * v ip e r*. . F i n a l l y , we s a y T i s c l o s e d u n d e r s u b s t i t u t i o n o f v a r i a b l e s i f * e T i m p l i e s <j> [ v ^ ] e T w h e r e v. I s f r e e f o r v . i n <j> « T h e M o d e l E x t e n s i o n T h e o r e m a n d o t h e r t h e o r e m s we w i l l p r o v e r e q u i r e t h a t we t r e a t e l e m e n t s o f a s t r u c t u r e a s c o n s t a n t s y m b o l s o f a l a n g u a g e , - N a m e l y , i f we h a v e a s t r u c t u r e Af f o r t h e l a n g u a g e L , w e e x t e n d L t o a l a n g u a g e L(Af) b y a d d i n g t o t h e s e t o f c o n s t a n t s y m b o l s a new s y m b o l f o r e a c h e l e m e n t o f U '. T o s i m p l i f y n o t a t i o n , i f a e U , - t h e . c o n s t a n t s y m b o l i n L(Af) c o r r e s p o n d i n g t o - I s d e n o t e d b y a i t s e l f . I n o t h e r w o r d s , we c o m m i t a common a b u s e o f l a n g u a g e a n d l e t t h e e l e m e n t s o f b e n a m e s f o r t h e m s e l v e s i n L(Af) , I f N => ~M , i n p a r t i c u l a r , i f N = Af ., we may c o n s i d e r N a s a s t r u c t u r e NQd) f,or L(M) b y s p e c i f y i n g t h a t f o r a l l n e w c o n s t a n t s a t h a t ajy(M) = a C'the a o n t h e l e f t i s a c o n s t a n t s y m b o l ; t h e a o n t h e r i g h t i s a h e l e m e n t o f c U^)« A n i m p o r t a n t f e a t u r e o f t h e s e " d e f i n i t i o n s ; i s t h a t - g i v e n a n y v a l u a t i o n a i n Af , we may c o n s i d e r a t o b e a s e q u e n c e o f t e r m s o f LiM) , T h e n f o r a n y f o r m u l a <j> o f L , ^ [ a ] i s a s e n t e n c e o f L(M) . I t i s t h e n e a s y t o s e e t h a t f o r a n y N o M , ^ [ " ^ ( M ) = • <!>[«] i s c a l l e d a n A f - i n s t a n c e o f $ . F o r a n y s e t T, o f f o r m u l a s o f L , we l e t r(Af) b e t h e s e t o f a l l A / - i n s t a n c e s o f f o r m u l a s o f T . T h e ; M o d e l ^ E x t e n s i o n T h e o r e m w h i c h f o l l o w s t e l l s u s w h e n we c a n T - e x t e n d a g o o d s t r u c t u r e t o a g o o d m o d e l o f a g i v e n t h e o r y , T h e o r e m 1, L e t T. b e a s e t o f f o r m u l a s c o n t a i n i n g a l l a t o m i c f o r m u l a s a n d c l o s e d u n d e r s u b s t i t u t i o n o f v a r i a b l e s . A g o o d s t r u c t u r e M h a s a g o o d T - e x t e n s i o n N w h i c h i s a m o d e l o f a t h e o r y T i f a n d o n l y i f e v e r y e l e m e n t o f T* w h i c h i s a t h e o r e m o f T i s v a l i d i n Af , P r o o f . T o p r o v e t h e c o n d i t i o n i s n e c e s s a r y , s u p p o s e M h a s a T - e x t e n s i o n // w h i c h i s a m o d e l o f T . N o t e t h a t N i s a l s o a r * - e x t e n s i o n o f M . L e t 0 e T* b e a t h e o r e m . o f T • T h e n f o r -any v a l u a t i o n a i n M , [ 9 , a ] , , = I0,a]„-•= 1 s i n c e N i s a m o d e l o f T . M . N T h u s 0 i s v a l i d i n M . T o pr.pve ;. s u f f i . c i c n c y , . . l e t ^ u s ^ . s u p p o s , ^ a., g o o d s t r u c t u r e M- . L e t 2" b e t h e t h e o r y w i t h l a n g u a g e L(M) w h o s e n o n l o g i c a l a x i o m s a r e t h o s e o f T . T h e r - d i a g r a m D o f M i s t h e s e t o f a l l s e n t e n c e s 0 i n r*(A/) s u c h t h a t I 0 ^ ( ^ ) = 1 * T h e n .the t h e o r y T1[D] i s c o n s i s t e n t . F o r s u p p o s e n o t . T i s c o n s i s t e n t o r e l s e M c o u l d n ' t s a t i s f y t h e c o n d i t i o n . T h u s T' . b e i n g a c o n s e r v a t i v e - e x t e n s i o n o f T , i s a l s o c o n s i s t e n t . S o i f 2" [£>] i s i n c o n s i s t e n t - , 2" I- ~ 6 f o r some c o n j u n c t i o n 0 o f f o r m u l a s , o f - D: 'Now r e p l a c e e a c h c o n s t a n t a e i n 0 t h r o u g h o u t b y s o m e new v a r i a b l e v ^ , o b t a i n i n g a f o r m u l a 0'' o f L * B y t h e T h e o r e m o n C o n s t a n t s , T V ~ 0 ' , B u t 9 w a s o b t a i n e d f r o m a f o r m u l a o f r * b y r e p l a c i n g f r e e v a r i a b l e s b y . n a m e s .a e a n d 9' w a s o b t a i n e d f r o m 9 b y r e - r e p l a c i n g t h e s e n a m e s b y v a r i a b l e s . S i n c e V i s c l o s e d u n d e r s u b s t i t u t i o n o f v a r i a b l e s , 9' e T * a n d ~ 9 ' e r * . B y t h e c o n d i t i o n , ~ 0 ' i s v a l i d i n M T h u s t 6 ' , a ] ^ = 0 f o r a l l v a l u a t i o n s ' a i n M , I n p a r t i c u l a r , t a k e a s u c h t h a t i f v^. r e p l a c e d a i n 9 w h e n we g o t 0' , t h e n a.. = a . W i t h t h i s a w e may w r i t e ^ ^ ( ^ ) = ^ ' » a ^ v f = 0 • We h a v e a r r i v e d a t a c o n j u n c t i o n o f e l e m e n t s o f D w h o s e v a l u e i n MQd) i s 0 , a c o n t r a d i c t i o n . C o n s e q u e n t l y , 2 " [ D ] m u s t b e c o n s i s t e n t a n d t h e r e f o r e i t h a s a c a n o n i c a l m o d e l . L e t Q b e t h e c a n o n i c a l m o d e l r e s t r i c t e d . t o t h e l a n g u a g e L , Q i s a m o d e l o f T s o we w o u l d l i k e t o m a k e Q i n t o a T - e x t e n s i o n o f M , T o d o t h i s , we m u s t f i r s t i d e n t i f y s o m e o f t h e e l e m e n t s o f t h e u n d e r l y i n g s e t U n o f Q . - R e c a l l t h a t M' i s t h e s e t o f v a r i a b l e * f r e e terms'* o f L(M) w h i c h c o n t a i n s a l l n a m e s o f n. e l e m e n t s o f U,, . F o r e a c h f e F a n d n a m e s . c . a , ••••«a e U„, d e f i n e M xi. 1 n M fX'a, •>-:a. ) V c, i f X i f w (.a .,.••»• ,aj.) =-,c. i n , . U> . -iTlien,., .''w. ; i s - ; , ( t a n ; b e e x t e n d e d t o ) a n e q u i v a l e n c e r e l a t i o n o n Un and, i n f a c t , t h e q u o t i e n t N of Q b y { 1 } a n d ^ i s d e f i n e d : if ' V a l ' " " , a n ) = C * t h 6 n • | I f ( a i » - " ' » a n ) - c ] w ( M ) = 1 s o f ( a , , • • • , a ) =• c i s a n a x i o m o f I " [£>]„ * T h u s f o r e v e r y P e P .and v a r i a b l e f r e e t e r m s t 0 , o f L(M)„ , z m r l 'PCcy.t^ ., • • ••,-t m) P ( f ( a - p • • • , a n ) , t 2 , * ' , t m ) i s -a t h e o r e m o f '.? ; ,7(Af) a n d t h e r e f o r e P ^ ( c , t 2 , • * * » t m ) = P ^ ( f ( a 1 , • • • , a h ) , t 2 , • - ' v t ^ ) . A l s o f 1 ( f ( a ^ , • • • , a n ) , t 2 , * * ' , t m ) = ' f ' ( c , t 2 » * * *»t ) i s a t h e o r e m f o r e a c h f £ Fm a n d s o f£(f ( a ^ • • • . a ^ , t , , , • • • ,t m).-= f £ ( c , t 2 , • • • , O . T h e p r o o f f o r o t h e r a r g u m e n t s o f P a n d f i s t h e s a m e . T h u s t h e q u o t i e n t N i s d e f i n e d . I t i s N we w i l l m a k e i n t o a T - e x t e n s i o n o f M . T o d e f i n e t h e i n j e c t i o n i : —* we s i m p l y l e t i ( a ) - a ~ ' f o r a l l a c • ... T h e " a " o n t h e r i g h t i s t h e name o f a £ U,. a n d I s a n e l e m e n t o f U „ « M Q - N o t e t h a t i i s o n e - t o - o n e a s r e q u i r e d . T h e a l g e b r a i s t h e r a n g e o f t h e f u n c t i o n !I , , s o a s a c o n s e q u e n c e o f C o r o l l a r y 3 . 2 , 3 we h a v e t h a t e v e r y e l e m e n t o f B ^ h a s t h e f o r m H a , a ] f o r s o m e q u a n t i f i e r f r e e , i . e . , o p e n , f o r m u l a a a n d M v a l u a t i o n a . D e f i n e g : B ^ —*• B ^ b y g l l a , a ] ^ = L l o " , i ( a ) ] f f . F i r s t , l e t u s s h o w t h a t g i s w e l l d e f i n e d . I f la,a]y = H ip ,3]^ w h e r e ^ i s a l s o o p e n , t h e n da [a] ^ [ 3 ] ] ^ ^ = 1 » B u t r c o n t a i n s a l l a t o m i c f o r m u l a s w h i c h m e a n s t h a t T* c o n t a i n s a l l o p e n f o r m u l a s . We g e t , t h e n , a [a] ip[3 l e D . T h e r e f o r e (- a [ a l *-> a n d h e n c e 2 " [D] f- a [a] t|>[8] , i . e . , | a [a ] <J/[3l I = 1 « F r o m t h i s we g e t tto.iCa)!^ = I a [ a ] l / { 1 } = | a [ a ] I = |i|>[e]| = = ( 1^ ,1 (3 )^ T o s h o w t h a t g i s o n e - t o - o n e , s u p p o s e [ a , i ( a ) ] ^ = Ri|<, i(3)] « We g e t f r o m t h i s | o [ o ] l / { l } = I * [ p ] l / { 1 } , i . e . , | a [ a ] l = l ip[3] I o r | a [ a ] ip[8 l I = 1 • T h u s 2"[Z?]„ |- a [ a ] ip[&] w h i c h i m p l i e s 2" [£>] I- a [ a ] i|i[3] s i n c e a [ a ] C61 i s a s e n t e n c e o f L(A/) * B y t h e R e d u c t i o n T h e o r e m , t h e r e a r e s e n t e n c e s 5 , , •••,6 o f 2? s u c h i . n t h a t T 1 h- 6, A»«»A 6 —> ( a [ a ] «-* i|)[3]) • B y t h e T h e o r e m o n C o n s t a n t s , J. n T V 6^ A..«A 6^ —»- ( a ' ip ' ) w h e r e n a m e s a e h a v e b e e n r e p l a c e d t h r o u g h o u t b y new v a r i a b l e s . A s w i t h 6' a b o v e , we h a v e 6* A«.«A 6' —*- ( a ' •<-* tp') e r * b e c a u s e a a n d ip a r e o p e n * B y t h e i n c o n d i t i o n o f t h e t h e o r e m , t h i s f o r m u l a i s v a l i d i n M , S o I f w e t a k e Y t o b e t h e v a l u a t i o n i n M w h i c h " u n d o e s " t h i s l a s t s u b s t i t u t i o n , we f i n d t h a t 1 = 116' A...A 6 ' -* ( o ' «-*• i f , ' ) ] I n M . = I 4 i A...A 6 n -> <a[o] ~ H B ] ) ^ = I 6 X A...A 6 ^ - l a t a ] ~ ^ S l ^ • B u t ^ A - A 6 ^ = 1 s i n c e e a c h 6^ i s i n D . T h u s I a [ a ] -«-»• ^£813 ^ ) = 1 a n d s o C l e a r l y , g i s a h o m o m o r p h i s m , s o w e m u s t o n l y v e r i f y n ow t h a t t h e p a i r i , g m a k e s M a T - s u b s t r u c t u r e o f N « We k n o w b y t h e d e f i n i t i o n o f g t h a t g l l 0 , a l = l l 9 , i ( a ) ] f o r a l l o p e n 9 b u t w e . M A/ m u s t s h o w t h i s e q u a l i t y h o l d s f o r a l l 9 i n T . So l e t tp b e a n y f o r m u l a i n T a n d l e t a b e a n y v a l u a t i o n i n Af . S i n c e M i s g o o d t h e r e i s a n o p e n 9 a n d v a l u a t i o n g s u c h t h a t llip,a]^ = I I 9 , 6 ] ^ . T h e n Hip [ a ] ^ ©[3] 3 = 1 a n d s i n c e t p[a] 9 [ B ] i s i n r*(M) , A? (AO we c o n c l u d e t h a t tp[a] -*-»- 9 [ 8 ] i s a n a x i o m o f 2" [ D ] . H e n c e T'[D] I- * [ a ] ^> 9 [ B ] a n d t h u s g l i p.al^ = gte.e]^ = 118,1(3) = I G[33 I = |ip[a] I = | [ i p,i(a)]l^ . F o r a n y f e Fn a n d a . ^ * - " ^ e , f ^ ( i ^ ) , , • • • » i ( a n ) ) = % ( a " [ , - - - , a ~ ) = f Q ( a v - ' , a n ) ~ = f ( a l f • • • , a n ) ~ = K ^ . - . a J ) . T h u s a l l c o n d i t i o n s a r e s a t i s f i e d a n d . W i s a T - s u b s t r u c t u r e o f N a n d N i s a m o d e l o f 2- . T h e o r e m 2. , L e t T ,;be ,a ,„set .of f o r m u l a s o f L a n d l e t I \ v b e t h e s e t o f f o r m u l a s o f V w h i c h a r e t h e o r e m s o f T . T h e n T i s e q u i v a l e n t t o a t h e o r y w h o s e n o n l o g i c a l a x i o m s a r e i n T i f a n d o n l y i f f o r e v e r y g o o d s t r u c t u r e Af, Af (= T i m p l i e s t h a t Af i s a m o d e l o f T. t h ( I f A i s a s e t o f f o r m u l a s , Af t= A m e a n s Af P A f o r e a c h <j> e A ) . P r o o f . T h e c o n d i t i o n i s n e c e s s a r y , f o r s u p p o s e T i s e q u i v a l e n t t o 2" , w h e r e t h e n o n l o g i c a l a x i o m s o f 2" a r e i n T , S u p p o s e , a l s o , t h a t M 1= r ^  . I f d> e T i s a n a x i o m o f 2" , t h e n <j> i s a t h e o r e m o f T . T h u s •* i s i n T , s o Af p A . Af i s t h e r e f o r e a m o d e l t h o f 2" , s o Af i s a l s o a m o d e l o f T . Now s u p p o s e t h e c o n d i t i o n h o l d s . L e t 2" b e t h e t h e o r y w h o s e n o n l o g i c a l a x i o m s a r e t h e f o r m u l a s o f r . C l e a r l y , e v e r y t h e o r e m o f 2" i s a t h e o r e m o f T . S u p p o s e t h e r e i s a t h e o r e m a o f T w h i c h i s n o t a t h e o r e m o f 2" . T h i s m e a n s t h a t 2" i s c o n s i s t e n t a n d a l s o t h a t 2 " [ ~ o ] i s c o n s i s t e n t . So I 7 ' [ ~ a ] h a s a . g o o d m o d e l Af ,. B y d e f i n i t i o n o f I " , Af T , s o b y t h e c o n d i t i o n Af i s a m o d e l o f T . H e n c e t h Af f= a , b u t w e a l s o h a v e Af b ~ a , a c o n t r a d i c t i o n * So n o s u c h a e x i s t s , i . e . , e v e r y t h e o r e m o f T i s a t h e o r e m o f 2" . I t s h o u l d b e n o t e d t h a t t h e t h e o r e m I s s t i l l v a l i d w i t h o u t t h e r e s t r i c t i o n " g o o d " o n Af . T h e same t e c h n i q u e t h a t w a s j u s t u s e d t o p r o v e T h e o r e m 1 c a n b e e m p l o y e d t o p r o v e T h e o r e m 2.2.4 : T h e o r e m 3. F o r a n y s t r u c t u r e Af , t h e r e i s a g o o d s t r u c t u r e A7 s u c h t h a t Af < N . P r o o f . L e t T b e t h e t h e o r y o v e r t h e l a n g u a g e L(M) w h o s e n o n l o g i c a l a x i o m s a r e a l l t h o s e <j> s u c h t h a t ^-^M(M) ~ ^ * ^" 1 S c o n s i s t e n t s i n c e Af(Af) i s o n e o f i t s m o d e l s . T h u s T h a s a c a n o n i c a l m o d e l a n d we l e t Q b e t h e c a n o n i c a l r e s t r i c t e d t o L , B y g o i n g t h r o u g h t h e s a m e p r o c e d u r e s we w e n t t h r o u g h i n t h e p r o o f o f T h e o r e m 1 , we may s h o w t h a t f o r s o m e q u o t i e n t N o f Q , Af < N' * One m o r e s e t o f d e f i n i t i o n s i s n e e d e d b e f o r e w e m o v e t o p r o v i n g t h e c h a r a c t e r i z a t i o n t h e o r e m s . L e t A f ^ , M^,'" b e a s e q u e n c e o f s t r u c t u r e s f o r a l a n g u a g e L . We s a y t h a t t h i s s e q u e n c e i s a c h a i n ( o f s t r u c t u r e s ) i f A f Q <= ^n+i f o r e a c h n = 1 , 2 , • • • . G i v e n s u c h a c h a i n , we w o u l d l i k e t o d e f i n e a s t r u c t u r e w h i c h i s t h e u n i o n o f t h e c h a i n . We c a n n o t a l w a y s d o t h i s , b u t w h e n i t i s p o s s i b l e , we d e f i n e t h e u n i o n Af = U^n °f t h e c h a i n i n t h e o b v i o u s w a y : ( 1 ) ( 2 ) \ = UB„ . ( 3 ) i f P £ P n ' P/.f ( 4 ) i f f £ * n ' f M ( 5 ) i f c e C , CW = c l = c "2 " T h e s e a r e s t a n d a r d d e f i n i t i o n s f o r t h e u n i o n o f a n a l g e b r a i c o b j e c t , s o i t s h o u l d b e e v i d e n t t h a t e v e r y t h i n g i s w e l l d e f i n e d . T h e r e i s n o t r o u b l e v e r i f y i n g t h e c o n d i t i o n s f o r t h e e q u a l i t y f u n c t i o n =^ . T h e d i f f i c u l t y l i e s . i n d e f i n i n g t h e f u n c t i o n I , ] ^ < I n g e n e r a l , i t c a n n o t b e s h o w n t h a t t h e a l g e b r a h a s e n o u g h s u p r e m u m s . T h e r e i n o n e c a s e w h e r e t h e u n i o n i s a l w a y s d e f i n e d w h i c h we now g i v e . A c h a i n Af^ c c « « . i s s a i d t o b e a n e l e m e n t a r y c h a i n i f f o r e a c h n , -M -<"M , . n n + 1 T h e o r e m 4. L e t Af^ <, b e a n e l e m e n t a r y c h a i n . T h e u n i o n Af i s d e f i n e d a n d f o r e a c h n , Af ^ Af , n P r o o f W e m u s t s h o w t h a t B ^ h a s e n o u g h s u p r e m u m s a n d t h a t f o r e a c h f o r m u l a <j> a n d e a c h v a l u a t i o n a i n Af . ( e ) G<t>,a!n = U,alM . T h i s i s d o n e b y i n d u c t i o n o n t h e l e n g t h o f (j> . I t I s n o t h a r d t o s h o w t h a t i t h o l d s f o r 9 V ip a n d ~ 9 , g i v e n t h a t i t h o l d s f o r 9 a n d ijj . Now s u p p o s e w e h a v e s h o w n t h a t ( e ) h o l d s f o r 9 . T h a t I s , f o r a l l k a n d v a l u a t i o n s B i n Af, , ff9,B]u = 1 9 , 8 ] . We w a n t t o s h o w t h a t I(avj)9 ,a l n = E(3v ).6,a]^ . F o r e a c h x e t h e r e i s a k > n s u c h t h a t x e U, . T h e n a i s a l s o a v a l u a t i o n i n Af a n d k k tte.aCj |x)]^ = |6,aCj lx)]k = B(av j)0,ol k = I I ( 3 v _ j ) 9 , a ] n . T h u s I (3v..) 9 . a ] ^ i s a n u p p e r b o u n d f o r t h e s e t { 1 9 , a ( j | x ) ] ^ : x e u " ^ } . Now s u p p o s e y 1 S a n y o t h e r u p p e r b o u n d . T h e n f o r some k > n , Y e B . F o r e a c h x e U. , ff9,a(j |x) ] , - H 8 , a ( j l x ) ] ^ Y» h e n c e k K • K M H ( 3 v - ) 8 , a ] •= I ( a v . ) e , a ] , < Y <• T h e r e f o r e J n j tc E ( 3 v J ) 8 , a ] n = s u p { G 8 , a ( j | x ) ] ^ : x e i y = (I ( 3 v _ . ) 9 , a ] ^ . T h e o r e m 5 , I f c M <=••• i s a c h a i n w i t h a n e l e m e n t a r y s u b c h a i n M £ M w h o s e u n i o n i s M , t h e n e v e r y s u b c h a i n h a s a u n i o n e q u a l n l n 2 t o M , i n p a r t i c u l a r , t h e u n i o n o f Af^ <= c « i s d e f i n e d . P r o o f . T h i s i s t r u e b e c a u s e f o r a n y o t h e r s u b c h a i n M, c M, c « . we h a v e [)U, = (Ju , UBv. = U B a n d f o r e a c h P e P a n d f e F• , ^ fcc^ n ti UP =UPN a n d \Jf =Ufn • fci n i i i S e c t i o n 2 O p e n T h e o r i e s a n d E x i s t e n t i a l T h e o r i e s A t h e o r y T i s s a i d t o b e o p e n i f a l l o f t h e n o n l o g i c a l a x i o m s o f T a r e o p e n , t h a t i s , q u a n t i f i e r f r e e . F r o m C h a p t e r 1 w e k n o w t h a t a t h e o r y i s e q u i v a l e n t t o a n o p e n t h e o r y i f a n d o n l y i f a l l i t s n o n l o g i c a l a x i o m s c o n t a i n o n l y u n i v e r s a l q u a n t i f i e r s w h e n i n p r e n e x f o r m . T h e n e x t t h e o r e m t e l l s u s t h a t t h e o p e n t h e o r i e s a r e e x a c t l y t h e o n e s f o r w h i c h s u b s t r u c t u r e s o f m o d e l s a r e a l w a y s m o d e l s . I n t u i t i v e l y , t h i s i s n o t h a r d t o u n d e r s t a n d . I f N i s a m o d e l o f a n o p e n t h e o r y T , t h e n a n o n l o g i c a l a x i o m o f T s a y s t h a t a l l ( n - t u p l e s o f ) e l e m e n t s o f h a v e s o m e p r o p e r t y . S o f o r a n y s u b s t r u c t u r e M c N , a l l ( n - t u p l e s o f ) e l e m e n t s o f w i l l h a v e t h i s p r o p e r t y , s o M w i l l b e a m o d e l o f T . C o n v e r s e l y , i f T c o n t a i n e d some a x i o m o f t h e f o r m ( 3 v ) 9 , t h e n t h e r e w o u l d b e some m o d e l o f T i n w h i c h n o t a l l e l e m e n t s o f s a t i s f i e d 6 ( o r e l s e ( v V g ) 9 w o u l d b e a t h e o r e m o f T)* T h e n t h e r e o u g h t t o b e a s u b s t r u c t u r e M o f N c o n t a i n i n g o n l y e l e m e n t s w h i c h d i d n o t s a t i s f y 9 a n d t h e n M w o u l d n ' t b e a m o d e l o f T < . T h e o r e m 1. A t h e o r y T i s e q u i v a l e n t t o a n o p e n t h e o r y i f a n d o n l y i f e v e r y s u b s t r u c t u r e o f a m o d e l o f T i s a m o d e l o f T < P r o o f . S u p p o s e T i s e q u i v a l e n t t o a n o p e n t h e o r y 2" . I n v i e w o f T h e o r e m 3.2.9 , we s h o w i f N i s a m o d e l o f 2"' a n d M c N , t h e n M i s a m o d e l o f 2" . S o i f 9 i s a n a x i o m o f T' , 6 h a s n o q u a n t i f i e r s o f o r a l l v a l u a t i o n s a i n M , [ 9 , a ] w = I9,a]„ = 1 . H e n c e M £ 9 . M N Now s u p p o s e t h e c o n d i t i o n i s s a t i s f i e d . L e t A b e t h e s e t o f o p e n f o r m u l a s a n d l e t A b e t h e o p e n f o r m u l a s w h i c h a r e t h e o r e m s o f T . t h We w i l l u s e T h e o r e m 1.2 s o l e t M b e a g o o d s t r u c t u r e s a t i s f y i n g e v e r y f o r m u l s o f A , . A c o n t a i n s a l l a t o m i c f o r m u l a s , i s c l o s e d u n d e r t h s u b s t i t u t i o n o f v a r i a b l e s , a n d e v e r y e l e m e n t o f A * = A w h i c h i s a t h e o r e m o f T i s v a l i d i n M , T h e r e f o r e , b y T h e o r e m l . l , M h a s a g o o d A - e x t e n s i o n N w h i c h i s a m o d e l o f T , t h a t i s , M c N i n t h e r e g u l a r s e n s e . B y t h e c o n d i t i o n , M i s a m o d e l o f T a n d b y T h e o r e m 1.2 T i s e q u i v a l e n t t o a n o p e n t h e o r y . N o t e t h a t t h e t h e o r e m r e m a i n s v a l i d i f we r e p l a c e " « . » e v e r y s u b s t r u c t u r e o f a m o d e l . . . " b y ".«.every g o o d s u b s t r u c t u r e o f a g o o d m o d e l . . . " . A t h e o r y T I s c a l l e d e x i s t e n t i a l i f a l l o f t h e a x i o m s o f T a r e e x i s t e n t i a l , t h a t i s , t h e a x i o m s c o n t a i n n o u n i v e r s a l q u a n t i f i e r s I n p r e n e x f o r m . T h e s e c o n d t h e o r e m o f t h i s s e c t i o n s a y s t h a t t h e c l a s s o f 76 e x i s t e n t i a l t h e o r i e s i s i d e n t i c a l t o t h e c l a s s o f t h e o r i e s w h o s e s e t s o f m o d e l s a r e c l o s e d u n d e r u n i o n s o f c h a i n s . I f f i s e x i s t e n t i a l , i t i s r e a s o n a b l e t o b e l i e v e t h a t t h e u n i o n o f a n y c h a i n o f m o d e l s o f T w o u l d b e a m o d e l o f T . A n e x a m p l e o f a t h e o r y n o t e x i s t e n t i a l i s t h e t h e o r y PM o f p a r t i a l l y o r d e r e d s e t s w i t h m a x i m a l e l e m e n t . F o r e a c h n a t u r a l n u m b e r n , t h e s e t M^. o f i n t e g e r s l e s s t h a n o r e q u a l t o n i s a m o d e l o f PM . B u t t h e u n i o n \ J ^ n n o t « T h e o r e m 2. A t h e o r y T i s e q u i v a l e n t t o a n e x i s t e n t i a l t h e o r y i f a n d o n l y i f f o r e v e r y c h a i n c <=••• o f m o d e l s o f T , i f t h e u n i o n M o f t h e c h a i n i s d e f i n e d , t h e n M i s a m o d e l o f T'» P r o o f . S u p p o s e T i s e q u i v a l e n t t o a n e x i s t e n t i a l t h e o r y 2 " . L e t c #2 c*** D e a c h a i n o f m o d e l s o f 2 1' w h o s e u n i o n M e x i s t s . We m u s t s h o w t h a t M i s a m o d e l o f 2" . T h u s ' l e t T a v 1 ' • * v k ) ' 6 b e a n a x i o m o f - 2 " , w h e r e 6 i s o p e n w i t h v a r i a b l e s v i » " " » v i c + n ' T h e n f o r a n y s e q u e n c e a ^ + L i ' * * > a k + n 6 t n e r e s o m e 3 w i t h a k + l ' * " ' a k + n £ U j a n d ^V'VHfl^'^nVV F°r a11  X l ' " , - X k e U j » ! I 0 i x l - * " ' x k ' a k + l ' * * , » a k + n ] 1 j = 1 I 0 i x l - * - , - x k - a k + l » * * , » a k + n ] W * K ^ 1 . . . v k ) e ; a k + 1 , . . . , a k + n ^ . T h a t i s , II ( S v ^ • .-v^ 6; a k + 1 , • • • , a k + n ^ i s a n u p p e r b o u n d f o r t h e s e t {•[[ 6 ; x p • •• » x k > a k + i > * * * i ak+n"' j : x l ' *"" " x n e U j ^ * H e n c e 1 = II • - v ^ e j a ^ , • • • . a ^ < K ^ - v ^ ^ ^ . - . a ^ . T h e r e f o r e , M i s a m o d e l o f 2" . Now a s s u m e t h a t t h e c o n d i t i o n h o l d s f o r T . B y T h e o r e m 1.2 , i t i s s u f f i c i e n t f o r u s t o s h o w t h a t i f M i s a g o o d s t r u c t u r e i n w h i c h a l l t h e e x i s t e n t i a l t h e o r e m s o f 2V a r e v a l i d , , t h e n M i s a m o d e l o f T. T o t h i s e n d , w e w i l l c o n s t r u c t a c h a i n c M 2 <=••• o f g o o d s t r u c t u r e s w i t h t h e f o l l o w i n g p r o p e r t i e s : ( 1 ) M± = M , ( 2 ) M„ <= M, c M, c . . . i s a c h a i n o f m o d e l s o f T , ( 3 ) A f^ c M^ c c » " i s a n e l e m e n t a r y c h a i n . T o s t a r t , l e t Af, = M . Now s u p p o s e Af h a s b e e n d e f i n e d . L e t J- 2 n - l A b e t h e s e t o f u n i v e r s a l f o r m u l a s o f L a n d l e t ip e A* b e a t h e o r e m o f 2" . B y t h e V a r i a n t T h e o r e m , we a s s u m e t h a t i f a v a r i a b l e v_. h a s a b o u n d o c c u r r e n c e i n ip , v . o c c u r s n o w h e r e e l s e i n ip « T h e c o n j u n c t i v e n o r m a l f o r m o f ip i s i p ^ A«»«A i p ^ , x ? h e r e e a c h i p ^ h a s t h e f o r m ~ 0 , V " « v ~6 v a , v • • • v o w i t h 6., a . e A , T h e n 2 1 V <p. f o r 1 m l n i ' j i . e a c h i a n d i f we w r i t e ip. a s a b o v e , t h e n T h ~9„ v..«v ~Q v <f> v.««v i 1 m l w h e r e <p^  i s t h e m a t r i x o f . B u t t h i s f o r m u l a , i n p r e n e x f o r m , i s e x i s t e n t i a l , s o b y a s s u m p t i o n , i t i s v a l i d i n M - M^ . I f t h e b o u n d v a r i a b l e s o f a . v«»«v a w e r e v , , , , » , v , a n d t h e f r e e v a r i a b l e s o f 1 n 1* ' p • ip^ a r e v , _ , t h e n t h e c l o s u r e I p + 1 ' * p+q ' ('Vv^-'-v ) ( ~ 6 j _ v . . . v ~ e m v <p1 v . . . v (j)n) i s v a l i d i n Af a l s o . S i n c e Af £ A L . , t h i s c l o s u r e i s v a l i d i n A L . . So t h e f o r m u l a 2 n - l 2 n ~ l ( V v , " ' v ) ( ~ 6 , v . . . v ~e v <j> v . . - v A ) i s v a l i d i n Af , t o o . 1 p 1 m l n 2 n ~ l S i n c e v , , , , , , v e a c h o c c u r i n e x a c t l y o n e p l a c e i n A v««»v A a n d 1' p i v T l n n o t a t a l l i n ~6„ v«««v ~6 , t h i s f o r m u l a i s e q u i v a l e n t t o 1 m ~9 v . v ~e v a , v . . . v a , i . e . , t o ip . T h u s Af , t= i p. f o r l m l n i 2 n ~ l l e a c h i a n d s o AT , V ip . B y t h e M o d e l E x t e n s i o n T h e o r e m , A L • 2 n - l 3 2 n - l h a s a g o o d A - e x t e n s i o n Af w h i c h i s a m o d e l o f T , S i n c e A c o n t a i n s 2 n a l l o p e n f o r m u l a s , Af c Af . 2 n - l 2 n N e x t we w a n t t o g e t a g o o d e x t e n s i o n A L , o f A L w h i c h i s a n 2 n + l 2 n e l e m e n t a r y e x t e n s i o n o f A L , . We l e t L ' b e t h e l a n g u a g e L(M ) 2 n - l 2 n _ l ar i d A' b e t h e u n i v e r s a l f o r m u l a s o f L ' . N o t e t h a t w e may w r i t e a n y f o r m u l a o f A' a s a [ a . . , • • • - a ] w h e r e a e A a n d a..,*««,a e U . ' 1' n I n 2 n _ l Now l e t 2" b e t h e t h e o r y o v e r L ' w h o s e n o n l o g i c a l a x i o m s D a r e t h o s e s e n t e n c e s <j> o f L 1 s u c h t h a t HA! = 1 w h e r e X i s M„ , ,) • D I s k n o w n a s t h e c o m p l e t e d i a g r a m o f AL , . I f w e 2 n ~ l 2 n - l z n - J . w r i t e ¥ f o r ^ 2 n ^ 2 n - l ^ » t h e n w e b a v e t h a t X i s a A ' - s u b s t r u c t u r e o f ¥ s i n c e f o r a n y f o r m u l a a [ a ^ , * • • , a ^ ] o f A ' , w h e r e a e A . a n d v a l u a t i o n 8 i n X w h i c h i s a l s o a v a l u a t i o n i n AL , , 2 n ~ l . I o [ a 1 . - - f a n ] i e ] j p = ^ ; a 1 , " - , a n , b n + l | . . - l 2 n _ 1 = Ha j a ^ • • • ,a n.b n + 1, •• • ] 2 n = ttata1,*,,,an],8]v . A n o t h e r e v i d e n t f a c t i s t h a t X i s a m o d e l o f 2" . We now u s e t h e M o d e l E x t e n s i o n T h e o r e m t o e x t e n d ¥ t o a m o d e l Z o f 2" . So l e t r b e t h e s e t o f o p e n f o r m u l a s o f Ly a n d l e t 9 e T* b e a t h e o r e m o f 2" . T h e n 2" r A w h e r e A i s t h e c l o s u r e o f 6 . B u t * e A ' a n d , s i n c e X i s a m o d e l o f T\ II <M = 1 -A C o n s e q u e n t l y , tt*]y = 1 a n d h e n c e 6 i s v a l i d I n ¥ , T h u s t h e r e i s a g o o d T - e x t e n s i o n Z o f J w h i c h i s a m o d e l o f 2" « We l e t AL 2 n + l b e t h e r e s t r i c t i o n o f Z t o t h e l a n g u a g e L » S i n c e ¥ <= Z , w e . h a v e Mn c Mn - • Now l e t b e a n y f o r m u l a o f L a n d l e t a b e a 2 n 2 n + l ' v a l u a t i o n i n AL , . T h e r e i s a n o p e n f o r m u l a 6 o f J a n d a n o t h e r 2 n - l v a l u a t i o n B i n Af , s u c h t h a t I^,a] = I6,8]„ . S i n c e t h i s 2 n ~ l 2 n _ l 2 n ~ l me a n s Ityla]6[B]]„ = 1 , ty[a] 6 [8] i s a n a x i o m o f 2" « a n d A t h e r e f o r e I* [ a ] 6 [8 ] ] = 1 o r u > , a ] _ = 16,0] . B u t Z 2 n + l 2 n + l b e c a u s e 6 i s o p e n , 15 ,81 = &6,8]„ . C o m b i n i n g t h e s e t h r e e 2 n ~ l 2 n + l e q u a t i o n s we o b t a i n ttip.al , = G 6 , 8 L • = G6,8]n ^, = l t y , a ] 0 , . Z n - 1 2 n - l z n + 1 z n + 1 T h u s • W < Af a n d Af • i s g o o d . 2 n ~ l 2 n + l 2 n + l We now h a v e a c h a i n Af c A? 2 c * * * s u c h t h a t Af 2 c Af^ c Afg • • • i s a c h a i n o f m o d e l s o f T a n d s u c h t h a t W c Af^ c Af^ • • * i s a n e l e m e n t a r y c h a i n . B y T h e o r e m 1 , 5 , t h e u n i o n Af o f t h e c h a i n i s d e f i n e d B y t h e c o n d i t i o n o f t h e t h e o r e m , t h e u n i o n i s a m o d e l o f .T . S i n c e T h e o r e m 1.4 s a y s t h a t Af •£ Af , Af = Af^ i s a m o d e l o f T a n d a s w e h a v e s a i d , t h i s i m p l i e s t h a t T i s e q u i v a l e n t t o a n e x i s t e n t i a l t h e o r y . . 8 0 C h a p t e r 6 A d d i t i o n a l T h e o r e m s T h e s e c t i o n s o f t h i s c h a p t e r b r i e f l y e x p l o r e f o u r o t h e r a r e a s i n t h e t h e o r y o f B o o l e a n v a l u e d s t r u c t u r e s . T h e s u b j e c t m a t t e r o f t h e f i r s t t w o s e c t i o n s h a s a n e x a c t p a r a l l e l i n t h e t h e o r y o f r e l a t i o n a l s t r u c t u r e s , T h e r e s u l t s , i n f a c t , c a n b e e x p r e s s e d i n t h e s a m e w o r d s [ 1 3 ] . I n t h e t h i r d s e c t i o n , w e s e e how t w o d i s t i n c t c o n c e p t s i n B o o l e a n v a l u e d m o d e l t h e o r y c o r r e s p o n d t o a s i n g l e c o n c e p t i n r e l a t i o n a l m o d e l t h e o r y . T h e l a s t s e c t i o n g i v e s a n a p p l i c a t i o n a n d s h o w s how t h e t h e o r y c a n b e u s e d t o p r o v e t h e o r e m s o f M a t h e m a t i c s w i t h o u t u s i n g t h e A x i o m o f C h o i c e . S e c t i o n 1 T h e P r e f i x P r o b l e m I f ip i s a u n i v e r s a l f o r m u l a a n d M c N a r e a n y t w o g o o d s t r u c t u r e s , w e h a v e b y t h e r e m a r k s i n s e c t i o n 2.2 t h a t H\|/,ct] ^ tip,-a 3^  f o r a l l v a l u a t i o n s a i n .Af . S i m i l a r l y , i f <J> i s e x i s t e n t i a l , t h e n Id>,ct]^ 5 (Id>,a3 . We may a b s t r a c t t h e s e p r o p e r t i e s a n d g e n e r a l i z e t h e m w i t h t h e n o t i o n o f r e l a t i v e p e r s i s t e n c e : A f o r m u l a 9 i s s a i d t o b e p e r s i s t e n t u n d e r r e s t r i c t i o n r e l a t i v e t o a t h e o r y T i f f o r e v e r y g o o d m o d e l N o f T a n d s u b m o d e l Af o f T , iQ.aJ.. > Ll8,a]„ f o r a l l v a l u a t i o n s a i n Af . 9 i s s a i d t o b e p e r s i s t e n t u n d e r e x t e n s i o n r e l a t i v e t o T i f f o r e v e r y g o o d m o d e l Af o f T a n d g o o d e x t e n s i o n N o f Af, a l s o a m o d e l , tt9,a]^ <- 1 8 , a ] f o r a l l v a l u a t i o n s a i n Af . I f 8 i s p e r s i s t e n t b o t h u n d e r r e s t r i c t i o n a n d u n d e r e x t e n s i o n r e l a t i v e t o T , we s a y 8 i s i n v a r i a n t r e l a t i v e t o T, T h e f i r s t r e m a r k s o f t h i s s e c t i o n t h e n s h o w t h a t a l l u n i v e r s a l f o r m u l a s a r e p e r s i s t e n t u n d e r r e s t r i c t i o n ( r e l a t i v e t o a n y t h e o r y ) a n d a l l e x i s t e n t i a l f o r m u l a s a r e p e r s i s t e n t u n d e r e x t e n s i o n ( r e l a t i v e t o a n y t h e o r y ) . I n a d d i t i o n , q u a n t i f i e r f r e e f o r m u l a s a r e i n v a r i a n t ( r e l a t i v e t o a n y t h e o r y ) . T h e o b v i o u s q u e s t i o n s , t h e n , a r e : G i v e n a n y t h e o r y T , i s e v e r y f o r m u l a p e r s i s t e n t u n d e r r e s t r i c t i o n r e l a t i v e t o T e q u i v a l e n t i n T t o a u n i v e r s a l f o r m u l a ? I s e v e r y f o r m u l a p e r s i s t e n t u n d e r e x t e n s i o n r e l a t i v e t o T e q u i v a l e n t i n T t o a n e x i s t e n t i a l f o r m u l a ? I s e v e r y f o r m u l a i n v a r i a n t r e l a t i v e t o T e q u i v a l e n t i n T t o a n o p e n f o r m u l a ? T h e f i r s t t w o o f t h e s e q u e s t i o n s h a v e a f f i r m a t i v e a n s w e r s , w h i l e t h e t h i r d i s t r u e w i t h a r e s t r i c t i o n o n T . We f i r s t p r o v e a m o r e g e n e r a l s t a t e m e n t , f i r s t f o r s e n t e n c e s a n d t h e n f o r f o r m u l a s : T h e o r e m 1 . L e t d>,i> b e s e n t e n c e s o f a t h e o r y T w i t h t h e p r o p e r t y t h a t g i v e n g o o d m o d e l s M c N o f 2" I<j>]^ > I ^ J ^ * T h e n t h e r e I s a u n i v e r s a l s e n t e n c e 8 s u c h t h a t T r i> —*• 8 a n d T V 6 —>- d> . P r o o f . L e t H b e t h e s e t o f a l l u n i v e r s a l s e n t e n c e s a s u c h t h a t T V if —*• a . T h e n t h e t h e o r y 27[#f~<|>] i s i n c o n s i s t e n t . F o r s u p p o s e o t h e r w i s e . T h e n T[HT~$] h a s a g o o d m o d e l M , I f w e l e t D b e t h e s e t o f a l l o p e n s e n t e n c e s 6 o f L(M) s u c h t h a t [ 6 ] . . = 1 (Z? i s M(M) t h e d i a g r a m o f A f ) , t h e n 2" [D] i s c o n s i s t e n t , w h e r e 2" i s t h e t h e o r y o v e r ZJ(Af) w h o s e n o n l o g i c a l a x i o m s a r e t h o s e o f T , s i n c e Af (Af ) I s o n e o f i t s m o d e l s . A s i n t h e p r o o f o f t h e M o d e l E x t e n s i o n T h e o r e m , we c a n c o n s t r u c t a n e x t e n s i o n N o f Af b y t a k i n g a q u o t i e n t o f Q , t h e r e s t r i c t i o n o f t h e c a n o n i c a l m o d e l o f 2" [D] t o L « N o t e t h a t N i s a m o d e l o f T , B y a s s u m p t i o n , t h e n , llil)] < E*] = 0 , I n o t h e r w o r d s , . N M 1~^Q = U~^3^ = 1 , s o 2 " [ D ] f ~ip . B y t h e R e d u c t i o n T h e o r e m , t h e r e i s a c o n j u n c t i o n 6 [ a ^ , * * * f a n l °f e l e m e n t s o f D , w h e r e 6 i s a f o r m u l a o f L w i t h f r e e v a r i a b l e s v , • • • • • v , s u c h t h a t 2" f- 6 [ a , ,*«*,a ] —> I n - 1 ' n o r Tx V i|» —> ~<5[a^, • • • , a n ] . B y t h e T h e o r e m o n C o n s t a n t s , T V —*• ~6 a n d t h e V - i n t r o d u c t i o n . r u l e g i v e s 2" \- ip —*• (Vv^« • '.v ) ~ 5 . T h u s ( V v ••«v ) ~ 5 , w h i c h we c a l l o , i s i n ff a n d t h e r e f o r e h a s I n v a l u e 1 i n Af . B u t . i s e q u i v a l e n t t o ( 3 v ^ " « v n ) 6 w h i c h a l s o h a s v a l u e 1 s i n c e E ( H v ^ • • v n ) 6 ] ^ > 16 j a . ^ • • • , a n 3 ^ = 16 [ a 1 , • • • ,a^\ 3 ^ ^ = 1 , T h i s i s a c o n t r a d i c t i o n , s o 2'[#,~<j>] m u s t b e I n c o n s i s t e n t . T h e n f o r some u n i v e r s a l s e n t e n c e 6 , e q u i v a l e n t t o s o m e c o n j u n c t i o n o f e l e m e n t s o f H , 2'[0 A ~ A ] i s i n c o n s i s t e n t . T h i s e n t a i l s t h a t T Y ~ ( 6 A ~<j,) . , o r T V 0 • - » • <j> . • B u t 0 e 5 s o 2 ' ( - i J ) - > 0 a l s o . . T h e o r e m 2. I f * i s a s e n t e n c e p e r s i s t e n t u n d e r r e s t r i c t i o n r e l a t i v e t o a t h e o r y T , t h e n f o r some u n i v e r s a l s e n t e n c e 0 , T V *-«-*• 8, T h e o r e m 3. L e t <t>,ip b e s e n t e n c e s o f a t h e o r y 2" w i t h t h e p r o p e r t y t h a t g i v e n g o o d m o d e l s Af c N o f T , Hiji],, < I*] , . T h e n t h e r e i s a n Af TV. e x i s t e n t i a l s e n t e n c e 0 s u c h t h a t T V 4> —> 9 a n d T V 0 —*- <f> . P r o o f . T a k e A i n T h e o r e m 1 t o b e a n d ip t o b e ~<j) . T h e o r e m 4. I f if i s a s e n t e n c e p e r s i s t e n t u n d e r e x t e n s i o n r e l a t i v e t o a t h e o r y T , t h e n t h e r e i s a n e x i s t e n t i a l s e n t e n c e 6 s u c h t h a t T f- <j> Q . T h e s e t h e o r e m s c a n b e e x t e n d e d t o i n c l u d e f o r m u l a s b y a d d i n g a s u i t a b l e n u m b e r o f n e w c o n s t a n t s y m b o l s t o L . We t h e n o b t a i n t h e f o l l o w i n g 8 3 T h e o r e m 5. L e t <j> a n d b e f o r m u l a s o f a t h e o r y T s u c h t h a t f o r a l l g o o d m o d e l s M c N o f T , [ A , a ] , > [IiJ;,a] f o r a l l v a l u a t i o n s a M N i n M t T h e n t h e r e i s a u n i v e r s a l f o r m u l a 9 s u c h t h a t T f- tj> -* 6 a n d T h 9 -+ A . T h e o r e m 6. I f A i s a f o r m u l a p e r s i s t e n t u n d e r r e s t r i c t i o n r e l a t i v e t o a t h e o r y T , t h e n t h e r e i s a u n i v e r s a l f o r m u l a 9 s u c h t h a t T V <j> «-»• 8 , T h e o r e m 7. L e t <j> a n d ip b e f o r m u l a s o f a t h e o r y 2" s u c h t h a t f o r a l l g o o d m o d e l s M c N o f 21 , [ i p . a ] ^ ^ H A , a l ^ f o r a l l v a l u a t i o n s a i n Af . T h e n t h e r e i s a n e x i s t e n t i a l f o r m u l a 9 s u c h t h a t T V -> 0 a n d 2" H 6 A , T h e o r e m 8. v I f • lA • i " i s 'a -irormul:awp-ei?slsljen1;"«'Un^^^ t o a t h e o r y 2 1 , t h e n t h e r e i s a n e x i s t e n t i a l f o r m u l a 9 s u c h t h a t 2 1 h A •*-*• 0 . F i n a l l y , i f 2* i s a n o p e n t h e o r y , we may c o m b i n e t h e a b o v e r e s u l t s : T h e o r e m 9, I f T i s a n o p e n t h e o r y a n d <j> i s a f o r m u l a I n v a r i a n t r e l a t i v e t o T , t h e n f o r some q u a n t i f i e r f r e e f o r m u l a 0 , T \r A -<-> 9 « P r o o f . T h e p r o o f u s e s t h e a b o v e r e s u l t s I n a p u r e l y s y n t a c t i c a l w a y . T h e d e t a i l s c a n b e f o u n d i n R o b i n s o n [ 1 3 J , S e c t i o n 2 O b s t r u c t i o n s , t o E l e m e n t a r y E x t e n s i o n s We w i l l d e f i n e a n d t h e n c h a r a c t e r i z e i n d i f f e r e n t t e r m s t h r e e l e v e l s o f o b s t r u c t i o n . We w i l l t h e n u s e t h e s e n o t i o n s t o - g i v e a m o d e l t h e o r e t i c c h a r a c t e r i z a t i o n o f s e n t e n c e s e q u i v a l e n t i n a t h e o r y t o V 3 - s e n t e n c e s ( a V S - s e n t e n c e i s o n e o f t h e f o r m ( ^ v ] _ ' * * v n ) ( ^ v n + l * * * vn+m^ 0 w h e r e 6 i s q u a n t i f i e r f r e e ) . I f M N are g o o d s t r u c t u r e s , w e s a y t h a t N o b s t r u c t s M i f n o e x t e n s i o n o f N i s a n e l e m e n t a r y e x t e n s i o n o f M . T h e o r e m 1 . L e t M c N b e g o o d s t r u c t u r e s . T h e f o l l o w i n g a r e e q u i v a l e n t ( 1 ) N o b s t r u c t s M , ( 2 ) f o r s o m e u n i v e r s a l s e n t e n c e 4> o f L (M) , 1 * 3 ^ ^ * ^-^nQt) ' ( 3 ) f o r s o m e u n i v e r s a l s e n t e n c e * o f L(M) , [*],,,.,» = 1 M{M) P r o o f . S u p p o s e N o b s t r u c t s M < L e t S b e t h e s e t o f a l l s e n t e n c e s <f> o f L(M) s u c h t h a t I M ',,,<> = 1 a n d l e t D b e t h e o p e n MK.M) s e n t e n c e s d> o f L(N) s u c h t h a t K*^GV) ~ 1 ' N o t e t h a t e v e r y f o r m u l a o f L(M) i s a f o r m u l a o f L(N) , I f t h e t h e o r y w i t h n o n l o g i c a l a x i o m s S u D w e r e c o n s i s t e n t , i t w o u l d h a v e a c a n o n i c a l m o d e l . B y r e s t r i c t i n g t h i s m o d e l t o L , we w o u l d o b t a i n a s t r u c t u r e Q s u c h t h a t M S Q a n d N c Q w h i c h i s i m p o s s i b l e . So f o r s o m e c o n j u n c t i o n 6 [ a a 1 o f JL n e l e m e n t s o f D , w h e r e 5 i s a n o p e n f o r m u l a o f a n d a^,"*,a^ e u # \ % t t n e t h e o r y [ 5 , 5 [ a ^ j • , a 1] ( t h e t h e o r y w h o s e n o n l o g i c a l a x i o m s a r e S.[a^,*»»,a ] a n d t h e e l e m e n t s o f 5 ) i s i n c o n s i s t e n t , i . e . , [ 5 ] h ~ 6 [ a ^ , • • • , a Q l < B y t h e T h e o r e m o n C o n s t a n t s , 8 5 [S] <r ( V v . . . . v )~6 . T h e n II ( V v , • • • V T J ~ 6 < ] = 1 s i n c e Af(Af) i s a I n i n M(M) m o d e l o f [ 5 ] , b u t [ ( V v ^ • • • * l > ~ « ^ (Af) = 1 < 3 v l * * ' V ^ (Af) £ H 6 [ a 1 t , " » a n ] ] ^ A 0 = 0 ' T h u s ( 3 ) h o l d s . C l e a r l y , ( 3 ) i m p l i e s ( 2 ) . S u p p o s e f o r some u n i v e r s a l s e n t e n c e A o f L (A f ) , 1*3^ ^ j * H*]^(M) • T h e n w e m u s t h a v e H*J/^(^) > 1*3^/^ ' * f t h e r e w e r e a n e x t e n s i o n Q a A? s u c h t h a t Af < § , we w o u l d h a v e & = s ff*]A7(Af) < L*LM{M) a c o n t r a d i c t i o n . Af m u s t t h e r e f o r e b e o b s t r u c t e d b y N . L e t Af b e a g o o d s t r u c t u r e w i t h l a n g u a g e L . A t h e o r y T o v e r L o b s t r u c t s Af i f e v e r y g o o d , m o d e l o f T e x t e n d i n g " Af o b s t r u c t s Af * P r o o f s o f t h e n e x t t h e o r e m a n d o f t h e t w o f o l l o w i n g may b e t a k e n f r o m t h e c o r r e s p o n d i n g p r o o f s f o r r e l a t i o n a l s t r u c t u r e s , a s f o u n d i n R o b i n s o n . j T h e o r e m 2. T o b s t r u c t s Af i f a n d o n l y i f f o r some u n i v e r s a l s e n t e n c e <j> o f L (A f ) , 2" h ~<j> , w h e r e 2" i s t h e t h e o r y o v e r L (A f ) w h o s e n o n l o g i c a l a x i o m s a r e t h o s e o f T . We s a y a t h e o r y 2V, o b s t r u c t s a t h e o r y 2V^  i f 2"2 o b s t r u c t s s ome m o d e l o f . T h e o r e m 3. 2V, o b s t r u c t s 2^ i f a n d o n l y i f f o r s o m e V 3 ~ s e n t e n c e <J> o f L , 2^ h A a n d 2"^[~A] i s c o n s i s t e n t . A s e n t e n c e 6 i s s a i d t o b e a - p e r s i s t e n t r e l a t i v e t o a t h e o r y T i f g i v e n a c h a i n Af^ c A f 2 <=••• o f m o d e l s o f T w i t h t h e u n i o n M d e f i n e d , d e l £ | 8 ] , , f o r a l l n . n Af 8 6 T h e o r e m -4, A s e n t e n c e ip i s o - p e r s i s t e n t r e l a t i v e t o T i f a n d o n l y i f f o r s o m e v a - s e n t e n c e 6- T f- TI* 9 * S e c t i o n 3 C o m p l e t e n e s s a n d M o d e l C o m p l e t e n e s s A t h e o r y T o v e r L i s s a i d t o b e c o m p l e t e i f T i s c o n s i s t e n t a n d i f f o r a n y s e n t e n c e | o f L e i t h e r T h <f> o r T V ~<j> . G i v e n a t h e o r y T, t h e f o l l o w i n g s t a t e m e n t s i n t h e t h e o r y o f r e l a t i o n a l s t r u c t u r e s a r e e q u i v a l e n t [ 1 3 ] : ( 1 ) f o r a n y m o d e l M o f T , T'[D] i s c o m p l e t e , w h e r e 2" i s t h e t h e o r y o v e r L(M) w h o s e n o n l o g i c a l a x i o m s a r e t h o s e o f T a n d D i s t h e s e t o f o p e n s e n t e n c e s o f L(M) w i t h ^ - ^ ( j ^ ) ~ x » ( 2 ) g i v e n a n y m o d e l s M <= N o f T , we h a v e M S N , I f a t h e o r y T s a t i s f i e s ( 1 ) o r ( 2 ) w i t h r e s p e c t t o r e l a t i o n a l s t r u c t u r e s , i t i s s a i d t o b e r - m o d e l c o m p l e t e ( ' r ' f o r " r e l a t i o n a l " ) . I f T s a t i s f i e s ( 1 ) w i t h r e s p e c t t o g o o d B o o l e a n v a l u e d s t r u c t u r e s , T i s s a i d t o b e d - m o d e l  c o m p l e t e ('d' f o r " d i a g r a m " ) . I f T s a t i s f i e s ( 2 ) w i t h r e s p e c t t o g o o d B o o l e a n v a l u e d s t r u c t u r e s , T i s s a i d t o b e e - m o d e l c o m p l e t e ('e' f o r " e l e m e n t a r y " ) * T h e p r o p e r e x t e n s i o n o f r - m o d e l c o m p l e t e n e s s I s e - m o d e l c o m p l e t e n e s s , b u t b e f o r e we s h o w t h i s , we g i v e , ' u s i n g t h e U l t r a f i l t e r T h e o r e m , a n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n f o r a s t r u c t u r e t o b e a n e l e m e n t a r y s u b s t r u c t u r e o f a n o t h e r s t r u c t u r e * T h e o r e m 1. S u p p o s e M c ft a r e g o o d . T h e n M <, N i f a n d o n l y i f f o r e v e r y m a x i m a l q u o t i e n t N o f N ( i . e . , N. i s r e l a t i o n a l ) a n d i n d u c e d q u o t i e n t M o f M (M i s a l s o r e l a t i o n a l ) # M S N « P r o o f . I f N i s t h e q u o t i e n t o f N b y ^ a n d F , t h e n we,.get a q u o t i e n t Af o f Af b y r e s t r i c t i n g ^ t o a n d F t o B ^ , T h e n c l e a r l y , i f M < N , t h e n M < N f o r e v e r y q u o t i e n t Z? a n d M i n d u c e d b y N . Now s u p p o s e Af i s n o t a n e l e m e n t a r y s u b s t r u c t u r e o f N * F o r so m e f o r m u l a a t h e r e i s a v a l u a t i o n a i n Af s u c h t h a t Ha,a].. * Ha,a],,. . L e t a b e s u c h a f o r m u l a w i t h t h e l e a s t n u m b e r o f Af N q u a n t i f i e r s . B y t a k i n g c o m p l e m e n t s i f n e c e s s a r y , we may a s s u m e a h a s t h e f o r m ( 3 v Q ) e . T h e n , i n f a c t , Ho,a~lM < Ho-.a]^ . B y t h e U l t r a f i l t e r T h e o r e m , t h e r e i s a n u l t r a f i l t e r F o n B^, s u c h t h a t tto,a]^ t F a n d lla,a]^ e F , I f 'v i s t h e c o r r e s p o n d i n g l a r g e s t e q u i v a l e n c e r e l a t i o n o n U ^ , t h e n i f N i s t h e q u o t i e n t o f N. b y % F a n d Af i s t h e i n d u c e d q u o t i e n t , ffa,a~]^ = Her , a ] w / ( F n B ^ ) = 0 w h i l e Ha,a~]^ = [ a . a ^ / F = 1 . H e n c e .A? £ N . T h e o r e m 2. A t h e o r y I 7 I s r - m o d e l c o m p l e t e i f a n d o n l y i f T i s e - m o d e l c o m p l e t e . P r o o f . T h i s i s i m m e d i a t e f r o m T h e o r e m 1 . T h e n e x t q u e s t i o n o n e may a s k i s w h a t i s t h e r e l a t i o n b e t w e e n d - m o d e l c o m p l e t e n e s s a n d e - m o d e l c o m p l e t e n e s s ? We f i r s t s h o w t h a t d - m o d e l c o m p l e t e n e s s i s a v e r y s t r o n g p r o p e r t y : T h e o r e m 3. A t h e o r y T i s d - m o d e l c o m p l e t e i f a n d o n l y i f T h a s o n l y 2 - m o d e l s , t h a t i s , i f Af i s a m o d e l o f T , t h e n B ^ = { 0 , 1 } . P r o o f . S u p p o s e . T i s d - m o d e l c o m p l e t e . I f Af i s a m o d e l o f T t t h e n T'[D] i s c o m p l e t e , w i t h T1 a n d D a s b e f o r e . F o r a n y f o r m u l a <j> o f L e n d v a l u a t i o n a i n Af , <j>[a] i s a s e n t e n c e o f L(M) • H e n c e e i t h e r 2" [D] h d>[a] o r [27] r ~ * [ c t ] . S i n c e Af(Af) i s a m o d e l o f 2" [D] , t h i s m e a n s E<j>[a] ] = 0 i . e > E<p,a3M = 0 o r 1 . S i n c e B i s t h e r a n g e o f II , ] M » S u p p o s e T h a s o n l y 2 - m o d e l s a n d l e t Af b e a m o d e l o f T . T h e n 2"[D] i s c o n s i s t e n t s i n c e M(M) i s o n e i t s m o d e l s * T h e r e f o r e • 2" [D] h a s a c a n o n i c a l m o d e l Q . L e t N b e Q r e s t r i c t e d t o t h e l a n g u a g e L • If i s a m o d e l o f T s o B ^ = B ^ = { 0 , 1 } . S i n c e B ^ i s t h e L i n d e n b a u m a l g e b r a o f 2 " ' [ D ] I , , 2" [ Z ? ] T I i s c o m p l e t e a n d s o 2" [D] i s c o m p l e t e * H r l T h e o r e m 4. I f T i s d - m o d e l c o m p l e t e , t h e n T i s e - m o d e l c o m p l e t e . H a v i n g o n l y 2 - m o d e l s i s q u i t e a s t r o n g c o n d i t i o n . I t i s c l e a r l y e n o u g h t o i m p l y c o m p l e t e n e s s o f t h e t h e o r y . T h e r e i s a w e a k e r c o n d i t i o n w h i c h i s a c t u a l l y e q u i v a l e n t t o c o m p l e t e n e s s : " T h e o r e m 5. "A " t h e o r y " T - i s ' c o m p l e t e " I f ' a n ^ * o n T l y * ' ± i ! w ^ o r ' , 8 e v e r y ^ m o c l e l M o f T a n d s e n t e n c e ip , e i t h e r II ^ 3^ = 0 o r II ^ 3^ = 1 • P r o o f . T h e c o n d i t i o n i s c l e a r l y n e c e s s a r y * S u p p o s e T i s n o t c o m p l e t e . T h e n some s e n t e n c e \p i s u n d e c i d a b l e i n T a n d t h e r e a r e g o o d m o d e l s M a n d N o f T s u c h t h a t = 0 a n < i - 1 • T h e p r o d u c t M*N ( r e d u c e d b y t h e t r i v i a l f i l t e r ) i s d e f i n e d a n d b y T h e o r e m 3.3,2 i t i s a m o d e l o f T . B u t b y t h e same t h e o r e m , WM*N = (WMM~lN) = ( 0 , D w h i c h i s n e i t h e r 0 n o r 1 i n B ^ , To e n d t h i s s e c t i o n , t w o t h e o r e m s o n q u a n t i f i e r e l i m i n a t i o n a r e s t a t e d . A c o n s i s t e n t t h e o r y T i s s a i d t o a d m i t e l i m i n a t i o n o f q u a n t i f i e r s i f f o r e v e r y f o r m u l a d> , t h e r e i s a n o p e n f o r m u l a 9 s u c h t h a t 21 r- <j> 8 . T h e o r e m 6. I f T a d m i t s e l i m i n a t i o n o f q u a n t i f i e r s , t h e n T i s e - m o d e l c o m p l e t e . T h i s t h e o r e m a l l o w s a p a r t i a l c o n v e r s e : T h e o r e m 7. I f T i s o p e n , t h e n i f T i s e - m o d e l c o m p l e t e , T a d m i t s e l i m i n a t i o n o f q u a n t i f i e r s , . S e c t i o n A H i l b e r t ' s 1 7 - t h P r o b l e m H u b e r t ' s 1 7 - t h p r o b l e m , t h a t o f p r o v i n g t h a t n o n n e g a t i v e p o l y n o m i a l s a r e s u m s o f s q u a r e s , - w a s s o l v e d b y A r t i n a n d S c h r e i e r [ 6 ] . T h e i r t h e o r y o f r e a l - c l o s e d f i e l d s , h o w e v e r , u s e s t h e A x i o m o f C h o i c e i n s e v e r a l . . p l a c e s , I n t h i s s e c t i o n we w i l l sh.ow h o w ,(one v e r s i o n o f ) H i l b e r t ' s 1 7 - t h p r o b l e m c a n b e s o l v e d b y w a y o f B o o l e a n v a l u e d m o d e l s w i t h o u t u s i n g t h e A x i o m o f C h o i c e . I t w i l l b e n o t i c e d t h a t AC i s m e n t i o n e d i n t h e e x a m p l e . T h i s i s n o t t h e same a s u s i n g AC a n d t h e m e n t i o n i s n o t e v e n e s s e n t i a l b u t i t d o e s s i m p l i f y t h e p r o o f ( d u e t o A. A d l e r ) . L e t M b e t h e r a t i o n a l f u n c t i o n s i n X o v e r t h e r e a l n u m b e r s , T h a t i s i s a s t r u c t u r e f o r t h e l a n g u a g e L - {0,1,-,-"-,+ »• ,=} a n d i s t h e s e t o f q u o t i e n t s o f p o l y n o m i a l s i n X w i t h r e a l c o e f f i c i e n t s a n d B ^ = { 0 , 1 } . Now e x t e n d L(M) t o a l a n g u a g e L' b y a d d i n g a b i n a r y p r e d i c a t e < . S u p p o s e u ( X ) e i s n o t a sum o f s q u a r e s . L e t T b e t h e t h e o r y o v e r £ ' w h o s e n o n l o g i c a l a x i o m s c o n s i s t o f : ( 1 ) t h e d i a g r a m o f M , i . e . , a l l o p e n f o r m u l a s d> i n L(M) s u c h t h a t U d O ^ ) = 1 , ( 2 ) u ( X ) < 0 , ( 3 ) t h e a x i o m s f o r a r e a l - c l o s e d o r d e r e d f i e l d [ 1 3 ] * T h e n T i s c o n s i s t e n t s i n c e a u s e o f t h e A x i o m o f C h o i c e c a n p r o v i d e a r e a l - c l o s e d o r d e r e d e x t e n s i o n o f M[6] . T h u s T h a s a c a n o n i c a l m o d e l 'Q . L e t N b e Q r e s t r i c t e d t o L" = { 0 , 1 , - , * , + , • , = » < } s o t h a t N i s a m o d e l o f t h e t h e o r y , o f r e a l - c l o s e d o r d e r e d f i e l d s . Now N r e s t r i c t e d t o L i s a n e x t e n s i o n o f M a n d R , t h e f i e l d o f r e a l n u m b e r s , i s , m i n u s i t s o r d e r , a s u b s t r u c t u r e o f M . H e n c e R m i n u s i t s o r d e r i s a s u b s t r u c t u r e o f N r e s t r i c t e d t o L . B u t < i n t h e t h e o r y o f r e a l c l o s e d f i e l d s i s c o m p l e t e l y d e t e r m i n e d b y a l g e b r a i c r e l a t i o n s ( a < c i f f ( 3 c ) ( a + c 2 = b ) ) ; h e n c e R c N ( a s s t r u c t u r e s f o r L " ) . Now u ( v Q ) < 0 i s a f o r m u l a o f L"(R, a n d X , t h e p o l y n o m i a l , i s a n e l e m e n t o f . T h u s B ( 3 V Q ) ( U ( V Q ) < 0 ) ] ^ ( ^ ) & Qu(X) < 0 ] ^ ( # ) = 1 • I t i s k n o w n t h a t t h e t h e o r y o f r e a l - c l o s e d f i e l d s a d m i t s q u a n t i f i e r e l i m i n a t i o n [ 1 9 ] a n d s o b y T h e o r e m 3.6 R £ N H e n c e II ( 3 V Q ) (U(VQ) < Q)3^>(^) = 1 . R i s g o o d s o f o r s o m e a e , i . e . , some r e a l n u m b e r , Hu(a) < 0 ] ^ ^ j = 1 o r u ( a ) < 0 . H e n c e , u ( X ) i s n o t n o n n e g a t i v e . 9 1 B i b l i o g r a p h y [ 1 ] B e l l , J . L , a n d S l o m s o n , A.B. M o d e l s a n d U l t r a p r o d u c t s , N o r t h H o l l a n d , A m s t e r d a m - L o n d o n 1 9 7 9 . [ 2 ] C o h e n , P . J . T h e I n d e p e n d e n c e o f t h e C o n t i n u u m H y p o t h e s i s , P r o c . N a t l . A c a d . S c i . U.S.A. j>0 ( 1 9 6 3 ) 1 1 4 3 - 1 1 4 8 , 5 1 ( 1 9 6 4 ) 1 0 5 - 1 1 0 . [ 3 ] C o h e n , P . J . S e t T h e o r y a n d t h e C o n t i n u u m H y p o t h e s i s , B e n j a m i n , New Y o r k 1 9 6 6 . [ 4 ] F r a y n e , T. , M o r e l , A. a n d S c o t t , D. R e d u c e d D i r e c t P r o d u c t s , F u n d a m e n t a M a t h e m a t i c a e 5 1 ( 1 9 6 2 ) 1 9 5 - 2 2 8 . [ 5 ] H a l m o s , P.R. L e c t u r e s o n B o o l e a n A l g e b r a s , V a n N o s t r a n d , P r i n c e t o n 1 9 6 3 . [ 6 ] J a c o b s o n , N. L e c t u r e s i n A b s t r a c t A l g e b r a , V o l . 3 , V a n N o s t r a n d , P r i n c e t o n 1 9 6 4 . [ 7 ] J e c h , T . J , T h e A x i o m o f C h o i c e , N o r t h H o l l a n d , A m s t e r d a m - L o n d o n , 1 9 7 3 . [ 8 ] J e c h , T . J . L e c t u r e s i n S e t T h e o r y , S p r i n g e r - V e r l a g , B e r l i n - H e i d e l b e r g - N e w Y o r k 1 9 7 1 . [ 9 ] M o s t o w s k i , A, P r o o f s o f N o n - d e d u c i b i l i t y i n I n t u i t i o n i s t i c F u n c t i o n a l C a l c u l u s , J o u r n a l o f S y m b o l i c L o g i c 13. ( 1 9 4 8 ) 2 0 4 - 2 0 7 , [ 1 0 ] / R a s i o w a , H, a n d S i k o r s k i , R. A P r o o f o f t h e C o m p l e t e n e s s T h e o r e m o f G S d e l , F u n d a m e n t a M a t h e m a t i c a e 37 ( 1 9 5 0 ) 1 9 3 - 2 0 0 , [ 1 1 ] R a s i o w a , H. a n d S i k o r s k i , R. T h e M a t h e m a t i c s o f M e t a m a t h e m a t i c s , W a r s a w 1 9 6 3 . [ 1 2 ] R e s s a y r e , J . - P . B o o l e a n M o d e l s a n d I n f i n i t a r y F i r s t O r d e r L a n g u a g e s , A n n a l s o f M a t h e m a t i c a l L o g i c , V0I.-6 N o . l ( 1 9 7 3 ) 4 1 - 9 2 . [ 1 3 1 R o b i n s o n , A. I n t r o d u c t i o n t o M o d e l T h e o r y a n d t o t h e M e t a m a t h e m a t i c s o f A l g e b r a , N o r t h , H o l l a n d , A m s t e r d a m 1 9 6 3 . [ 1 4 ] R o s s e r , J . B . S i m p l i f i e d I n d e p e n d e n c e P r o o f s , A c a d e m i c P r e s s , New Y o r k - L o n d o n 1 9 6 9 . [ 1 5 ] R u t k o w s k i , A* Some R e m a r k s A b o u t B o o l e a n - v a l u e d M o d e l s , B u l l , A c a d , P o l o n . S c i , S e r , S c i * M a t h , A s t r o n o m , P h y s , JL9 N o . 2 ( 1 9 7 1 ) 8 7 - 9 3 . [ 1 6 ] S c o t t , D, A P r o o f o f t h e I n d e p e n d e n c e o f t h e C o n t i n u u m H y p o t h e s i s , M a t h e m a t i c a l S y s t e m s T h e o r y 1^ ( 1 9 6 7 ) 8 9 - 1 1 1 . [ 1 7 ] S h o e n f i e l d , J . R . M a t h e m a t i c a l L o g i c , A d d i s o n - W e s l e y , R e a d i n g - L o n d o n 1 9 6 7 , [ 1 8 ] S z c z e r b a , L.W, T h e N o t i o n o f E l e m e n t a r y S u b s y s t e m f o r a B o o l e a n -v a l u e d R e l a t i o n a l S y s t e m , F u n d a m e n t a M a t h e m a t i c a e 80. ( 1 9 7 3 ) 5 - 1 2 . [ 1 9 ] T a r s k i , A . A D e c i s i o n M e t h o d f o r E l e m e n t a r y A l g e b r a a n d G e o m e t r y , U n i v e r s i t y o f C a l i f o r n i a P r e s s , B e r k e l e y - L o s A n g e l e s 1 9 5 1 . [ 2 0 ] T a r s k i , A, L o g i c , S e m a n t i c s , M e t a m a t h e m a t i c s , O x f o r d U n i v e r s i t y P r e s s , L o n d o n 1 9 5 6 ,