SOME USEFUL GENERALIZATIONS OF FIRST ORDER LANGUAGES, by JAMES ANDREW FINLAY B.Sc, University of British Columbia 1969 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in the Department of MATHEMATICS We accept this thesis as conforming to the required standard The University of British Columbia September, 1971 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia Vancouver 8, Canada ABSTRACT We begin with a disucssion of some of the serious deficiencies of f i r s t order predicate languages. These include the non-characterizability by f i r s t order sentences of such common mathematical structures as the class of well-ordered sets, the class of f i n i t e sets, the class of Archimedean fields and the standard models of arithmetic and analysis. Two methods of generalizing f i r s t order predicate languages are then studied. The f i r s t approach is to allow for "expressions of i n f i n i t e length"; the second method is the introduction of "generalized quantifiers." For the languages resulting from each approach, we consider to what extent such deficiencies as those mentioned above may be overcome and also to what extent some of the elementary model-theoretic and proof-theoretic theorems of f i r s t order logic may be generalized to these new languages. Among the languages with expressions of i n f i n i t e length, we f i r s t consider the ^ - languages which generalize f i r s t order languages by extending the recursive definition of a formula to allow countable conjunctions and disjunctions of formulas as formulas. It is shown that with the use of such languages we are able to describe categorically the standard model of arithmetic, the class of f i n i t e sets, the class of Archimedean fields and other common mathematical structures which cannot be characterized in f i r s t order languages. Generalizations of the Lowenheim-Skolem and completeness theorems of f i r s t order logic are given as well as a countable isomorphism theorem due to Dana Scott. We make use of a characterization of rank equivalence due to Carol Karp to demonstrate i i . that neither the standard model of analysis nor the class of well-ordered sets may be described in any L - language. In fact, our argument indicates that these characterizations are not possible in any extension of a ^ - language which, for any i n f i n i t e cardinal a , allows as formulas conjunctions and disjunctions of less than a formulas. This result leads us naturally to a consideration of the class of L - languages, any element of which is obtained from a ^ - language by modifying the rules for formula formation to allow not only denumerable conjunctions and disjunctions but also quantifications over denumerable sets of variables. (These ideas are made more precise in the text of the thesis.) The standard model of analysis and the class of well-ordered sets are each seen to be characterizable by single L - sentences. Other infin i t a r y o)1u)1 languages are also mentioned, including languages with i n f i n i t e l y long atomic formulas. Among the languages with generalized quantifiers we restric t ourselves to the L(Q Q) ~ languages, where a i s an ordinal, which are obtained from f i r s t order languages by adding a new quantifier symbol Q to be read "there exist i\f ... In addition to being able a a to characterize sets of various cardinalities, we give a categorical description of the standard model of arithmetic by a single L ( Q q ) - sentence. Among the model-theoretic results possible are generalizations of the compactness theorem, Los's theorem and the downward Lowenheim - Skolem theorem of f i r s t order logic. Finally, i i i . on the proof-theoretic side, we show that in the case a = 0 there exists no recursive axiomatization which yields a completeness result in the case a = 1 , however, such an axiomatization is possible. i v . Table of Contents Page Preface v i i Chapter One: Fi r s t Order Predicate Languages. 1 1.1 Basic Definitions and Notation 1.1.1 Syntax 1 1.1.2 Model Theory 3 1.2 Some Well-known Theorems of F i r s t Order Logic 1.2.1 The Compactness Theorem 8 1.2.2 The Lowenheim-Skolem Theorems 8 1.2.3 Los's Theorem 9 1.2.4 Completeness Theorems 9 1.2.5 Remarks Concerning the Theorems 11 1.3 Some Deficiencies of First Order Logic 1.3.1 Non-standard Models of Arithmetic 12 1.3.2 Other Deficiencies 15 Chapter Two: Languages With Expressions of Infinite Length. 17 2.1 The L - Languages 2.1.1 Syntax and Semantics 18 2.1.2 Characterizability Results 19 2.1.3 Failure of the Compactness Theorem 22 2.1.4 Lowenheim-Skolem Theorems 27 2.1.5 Completeness Theorems 31 2.1.6 A Result Concerning Weil-Ordered Systems 33 2.1.7 A Characterization of Elementary Equivalence 35 2.1.8 Non-Characterizability of the Real Numbers 38 2.1.9 Non-Characterizability of Well-Orders 39 2.2 The L - Languages 2.2.1 Syntax and Semantics 43 2.2.2 Characterizability Results 44 2.2.3 Lowenheim-Skolem Theorems 46 2.2.4 Completeness Theorems . 47 2.2.5 Infinitary Predicate Letters 47 V . Page Chapter Three: Languages with Generalized Quantifiers. 49 3.1 Syntax and Semantics 51 3.2 Characterization of the Natural Numbers 53 3.3 Lowenheim-Skolem Theorems 53 3.4 Compactness Theorems 54 3.5 Completeness Theorems 58 Bibliography 61 v i . Acknowledgements I should like to thank f i r s t of a l l my supervisor Dr. Andrew Adler for his assistance, patience and encouragement during the preparation of this thesis. My appreciation is also extended to Dr. Tim Cramer who read the thesis with interest and to Eve Hamilton who performed the very d i f f i c u l t task of typing extremely well. Finally I wish to thank the National Research Council of Canada for i t s financial assistance given me during the last two years. v i i . PREFACE Fir s t order predicate languages, despite their usefulness for a great variety of mathematical purposes, suffer nevertheless from a number of shortcomings. Perhaps the most famous deficiency of such languages i s the result f i r s t demonstrated by Skolem [31] that the set of natural numbers cannot be categorically described by f i r s t order sentences. In other words, for no set of f i r s t order sentences are the models precisely a l l those structures isomorphic to the standard model of arithmetic. There are many other failings of f i r s t order logic which, i f they are less famous, are certainly no less disturbing. Some of these deficiencies w i l l be discussed i n the text of this thesis. In an attempt to overcome such deficiencies, efforts have been made to obtain more powerful languages by generalizing the languages of f i r s t order logic. Two approaches .in particular have proved to be quite successful. The f i r s t method, due to Tarski, consists in extending the definition of a f i r s t order formula to allow for "expressions of i n f i n i t e length." In essence, this approach does not require new symbols; i t merely extends the rules by which the given symbols may be combined to yield formulas. The second method for generalizing f i r s t order languages was initia t e d by Mostowski. In contrast to Tarski's approach, Mostowski proposed the introduction of new logical symbols to serve as "generalized quantifiers." Each of these approaches, by the way, was suggested in the year 1957 and has since enjoyed widespread attention from a number of prominent logicians. v i i i . The purpose of this thesis i s twofold. F i r s t l y , we wish to investigate to what extent the deficiencies of f i r s t order logic may be overcome when we pass to those kinds of languages originally proposed by Tarski and Mostowski. Secondly, we shall be interested in the extent to which the elementary model-theoretic and proof-theoretic results of f i r s t order logic carry over to these generalized languages. In Chapter one we begin with a brief review of f i r s t order logic. This chapter serves to f i x notation, to outline some of the important theorems of f i r s t order logic and f i n a l l y to expose some of the serious shortcomings of f i r s t order languages. Chapter two is then devoted to a study of "languages with expressions of i n f i n i t e length" and Chapter three to "languages with generalized quantifiers." It i s our hope that this thesis w i l l be accessible to anyone with a minimal knowledge of f i r s t order logic. In fact, Chapter one gives most of the important details. However, some prior knowledge is required. For example i t is assumed that the reader can distinguish between "free" and "bound" occurences of variables in a formula. Information of that kind may be found i n any standard text of f i r s t order logic, for example [19] or [23]. A f i n a l comment about proofs. In a survey of this kind f u l l proofs of a l l theorems are clearly impossible. For theorems of f i r s t order logic, moreover, they are uninteresting as they may easily be found in many standard textbooks. Let us agree then that a result of f i r s t order logic i s "well-known" i f i t i s proved in Be l l and Slomson's book "Model Theory and Ultraproducts" ([2]). Proofs of well-known results are not included in this thesis. As for the results stated for the generalized ix. languages, our attitude is usually one of providing references for the proofs rather than exhaustively exhibiting the proofs here. Instead, we seek to explore possible generalizations of such theorems and to mark out the boundaries of possible theorems by providing counter-examples. In those cases where elaborate proofs are supplied, i t is hoped that the proofs serve to highlight the methods of the subject and are therefore instructive in themselves. CHAPTER ONE FIRST ORDER PREDICATE LANGUAGES In this chapter we quickly review the important elements of f i r s t order logic. Our purpose is threefold: to give the basic definitions and notation, to review some of the principal theorems and f i n a l l y to examine some of the deficiencies of f i r s t order predicate languages. 1.1 Basic Definitions and Notation. 1.1.1 Syntax We now describe the basic syntactical notions for f i r s t order predicate languages with equality. The symbols for a typical f i r s t order language L are the following: 1) Variables. The variables of L are elements of the denumerable set {v : n e to} . n 2) Predicate Letters. The predicate letters for L are the elements of the set {P^: y < p) where p is any cardinal. To each predicate letter P there i s associated Y a positive integer <5(y) , the degree of P^ . 3) Equality Symbol. The equality symbol "=" denotes a special predicate letter of degree 2 , the inter-pretation of which i s always the identity relation. 2. 4) Constant Symbols. The language L contains a collection of constant symbols {c^ : £ < a} . The cardinal a is arbitrary here. 5) Logical Connectives. The basic logical connectives for f i r s t order languages are the negation symbol "~" and the conjunction symbol " A" . The symbols "v" , "+" and *W , to be read "or", "implies" and " i f and only i f " respectively are defined in terms of "~" and " A" i n the usual way. 6) Quantifier Symbols. The basic quantifier symbol is "3" , to be read "there exists". The universal quantifier symbol 'V is defined in terms of "3" and "~-" in the usual way. 7) Punctuation Symbols. We make free use of brackets, commas and periods whenever i t seems convenient. Normally one also includes a collection of function letters among the basic symbols of f i r s t order languages. We choose to omit such symbols since their introduction creates unnecessary complications in many of the subsequent definitions. A function, after a l l , i s simply a special kind of relation and we shall find i t convenient to treat i t as such. Also we note that the cardinals p and a above are arbitrary and may indeed be zero. Hence, a f i r s t order language need not be equipped with any predicate letters beyond the equality symbol and need not contain any constant symbols. A formula of a f i r s t order language L i s a special sort of f i n i t e string of symbols. The precise definition i s i n three parts. We f i r s t define a symbol to be a term i f i t i s either a variable or a constant symbol. An atomic formula of L is then defined to be any sequence of symbols of the form t n = t„ or of the form P (t , , t _ , .. ., t., ..) where P is 1 2 y 1 2 6(Y) Y a predicate letter of degree 6(Y) and each t^ i s a term. Finally, we are able to define the class of formulas F to be the smallest set which contains the atomic formulas and is closed with respect to the following rules: . (a) If {F l fF }C F then ~F ] [ e F and A £ F . (b) If F e F and v is a variable then 3v F e F . n n A sentence of L is simply a formula without free variables. 1.1.2 Model Theory We turn now to some elementary concepts of model theory. By a relational structure or realization A of our f i r s t order language L we understand a system < A , {P^ y e p} , {k^ : £ < 2} > where A is_a non-empty set to be called the domain of A , P^ is a <5(y) - ary relation defined on A for each y e p and k^ is a fixed element of A for each £ < a . The structure A serves as an interpretation of our language L : the variables of L are thought of as elements of A while for each yep the predicate letter P i s interpreted as the relation P and for each Y Y E, < a the constant symbol c • i s interpreted as the fixed element k^ of A . We now investigate what i t means for a sentence <j> of our language L to be "true" i n the relational structure A . To begin, we consider any denumerable sequence x = < ao,a^,a2»••• > of elements of A . Such a sequence i s called a valuation of the variables of L . Intuitively, such a valuation x satisfies a formula § in A , in which case we write A ^ <{> , i f the formula <f> says something true about A when the variables, predicates and constant symbols are properly interpreted. For example, l e t us consider the f i r s t order language with single binary predicate letter < and a single constant symbol c . The relational structure we have in mind is the set of integers Z with usual order < , and in which we interpret c as the number zero; that i s , Z = < Z , {<} , {0} > . For our formula <J> we consider ^(v^ < c) . Clearly a valuation x = < a , a , > satisfies i> in Z i f f a n is • o 1 1 non-negative. Tarski has been able to make this idea mathematically precise. His definition i s in two parts. For given valuation of the variables * x = < a , a , > we f i r s t define an evaluation function x from the o 1 set of terms into A as follows: (a) x (v ) = a ; n e u n n (b) x*(c ) = k^ ; C < a . Tarski's definition for A |= <j> may now be given recursively: x (i) A f= t^ = i f f x (t^) i s the same element as x ( i i ) A*=P"Y ( t r . . . , t 6 ( Y ) ) i f f < x * ( t l ) , . . . , x * ( t 6 ( Y ) ) > e P y ( i i i ) A t= ^ (J) i f f not A\=. <j> . x x (i v ) A{=<J)^iJ; i f f A J= tb and A t= ij> x x x (v) At=3v 'I' i f f A N * f o r some a e A , where x(n/a) n x(n/a) i s the valuation of the va r i a b l e s obtained from x by replacing a^ by a . Clearly, this definition corresponds to our intuitive conception of a valuation of the variables satisfying a formula in a relational structure. The reader may easily check that the following statements are true: 1) A}= <j> v ijj i f f A (= <j> or At== y> • 2) A \= <j) •+ 4> i f f A|==^ (f> or A tj= (() ^ i|) . 3) ^ ^ ^ v n ^ ^ where y i s any valuation of the th variables differing from x i n at most the n position. 4) Suppose y = < b o >b^,... > is any valuation of the variables such that whenever a variable v occurs free i n 6 then n a = b . Then A |= <p i f f A t= d> . n n ^x T y If we apply this last result in the special case where (f> is a sentence, we see that i f A(=<j> for some valuation x then A(=<j> for a l l valuations x . In this case we write simply A <j> and say that the sentence (j) is true or valid in A . The relational structure A i s then said to be a model for the sentence <J> . Finally, i f Z is a collection of sentences of L , we define a relational structure A. to be a model of £ i f A is a model for each sentence of E . To c l a r i f y these ideas we give the following example in which we describe the theory of abelian groups. The appropriate f i r s t order language i s one with a ternary predicate A to represent group addition and a constant symbol 0 to be interpreted as the group unit. A relational structure < G , + , 0 > where G i s a non-empty set, + a ternary relation and 0 a constant i s then an abelian group i f , with the obvious interpretation of the symbols, the following sentences are true: GJ, V v o V v 1 3 v 2 V v 3 [ I(v o,v 1,v 3) <-* v 2 = v 3 ] G.2 V v o V v 1 V v 2 V / v 3 V v 4 V v 5 [ A ( V Q , V 1 , V 3 ) A A(v 3 >v 2,v 4) A A ( V 1 > V 2 , V 5 ) , + A(v o,v 5,v 4)] G.3 V v ^ V v 1 V v 2 [A(v o,v l fv 2) •* A( V ; L,v o,v 2)] G.4 Vv A(v,0,v) G.5 Vv 3 v n A(v ,v. ,0) o 1 o 1 Here axioms G.l, G.2, G.3 give the uniqueness, associativity and commutativity of addition respectively. Axiom G.4 says that 0 i s a unit, while axiom G.5 gives the existence of an inverse. We now discuss two relationships which may exist between realizations of a f i r s t order language:, isomorphism and elementary equivalence. To this end we consider the realizations of our f i r s t order language L given by A = < k,{V^ : y e p } , {a^ : £ < a} > and B=<B,{R : Y e p ) > (b_ : £ < a] > with the obvious interpretations for the symbols. A function h : A -> B i s a homomorphism of A into 8 i f f for each yep and each £ < a the following conditions are satisfied: (i) h(a ) - b . ( i i ) If < a^,...,a^^^ > e P^ then < h(a^),. .. ,h(a^^^) > e R^ . If there exists a one-to-one and onto homomorphism h : A 8 we say that h i s an isomorphism and that the structures A and 8 are isomorphic. This is written A - 8 . We define structures A and 8 to be elementarily equivalent with respect to the language L i f the set of sentences of L true in A i s precisely the set of sentences of L true in 8 . Clearly, both isomorphism and elementary equivalence are equivalence relations. While obviously two isomorphic structures are elementarily equivalent, the converse is -false. As an example we consider the relational structures of the real numbers < IR , < > and the rational numbers < Q , < > each ordered by < in the usual way. These structures are not isomorphic since (R i s uncountable while Q is countable. However i t is well-known (and w i l l follow from Theorem 2 - 9 ) that these systems are elementarily equivalent with respect to the appropriate f i r s t order language. We complete this section with two definitions. If E is a collection of f i r s t order sentences and 3 any cardinal, we say that Z i s g-categorical i f a l l models of Z of cardinality 3 are isomorphic. (A model is of cardinality 3 i f i t s domain is of cardinality 3)- Finally, Z i s categorical i f Z i s 3-categorical for a l l cardinals 3 , that is i f a l l models of Z are isomorphic. 8. 1.2 Some well-known theorems of f i r s t order logic. We now catalogue some important theorems of f i r s t order logic. We shall be interested to know whether results analagous to these hold in the languages to be considered i n chapters two and three. 1.2.1 The Compactness Theorem. The most important theorem for the existence of models is the following: Theorem 1-1 (The Compactness Theorem). A set E of f i r s t order sentences has a model i f f each f i n i t e subset of E has a model. 1.2.2 Lowenheim-Skolem Theorems. Given a collection E of f i r s t order sentences with a model A , i t is of interest to know under what conditions E also has models of cardinalities different from the cardinality of A . The answer i s provided by the following theorems: Theorem 1-2 (Downward Lowenheim-Skolem Theorem). Let E be a set of f i r s t order sentences of cardinality a for which there exists an i n f i n i t e model of cardinality at least a . If a is i n f i n i t e , E has a model of cardinality a ; while i f a i s f i n i t e , E has a denumerable model. 9. Theorem 1-3 (Upward Lowenheim-Skolem Theorem). Let Z be a set of f i r s t order sentences of cardinality a . If Z has an i n f i n i t e model, then Z has a model of any i n f i n i t e cardinality at least as large as a . These results may be combined to yield: Theorem 1-4 (Lowenheim-Skolem Theorem). Let Z be a set of f i r s t order sentences of cardinality a with an i n f i n i t e model. Then Z has a model of any cardinality at least as large as MAX(a , % q) . 1.2.3 Los's Theorem. We consider an indexed collection' of relational structures {A. : i e 1} where each A. is of a..common tyne. If F is an u l t r a f i l t e r on I , we denote by II A./F the associated ultraproduct. i e l 1 (For the development of the ultraproduct construction the reader is referred to Bell and Slomson [2].) Los's Theorem is as follows: Theorem 1-5 (Los's Theorem) For any f i r s t order sentence <J> , nA./Ft=<j> i f f { i e l : A (= <(>} e F . i e l 1 1.2.4 Completeness Theorems Each of the theorems 1-1 to 1-5 is model-theoretic in character. We now turn our attention to some proof-theoretic concepts. We describe a formal system which yields a notion of proof such that the provable sentences 10. of a f i r s t order language L are precisely the class of universally valid sentences - that i s , the class of sentences true in a l l realizations of L . Our axiom system consists of a l l instances of the following schemas where A , B , C are formulas, v and v, , are variables and t is a term: A . l A (B A) A.2 [A -* (B -> C) ] -> [(A -> B) -* (A •> C) ] A. 3 OB -> -vA] -*- [A ->• B] A. 4 Vv A(v ) -> A(t) where t i s free for v in A(v ) o o o o A.5 Vv [A ->- B] [A ->• Vv B] where A contains no free occurences of v o o o A. 6 Vv (v = v ) o o o A. 7 Vv Vv, [v = v, -*• (A -*• A') 1 where v, is free for v in A and A1 o 1 o 1 J 1 o i s obtained from A by replacing at least one of the free occurences of v in A by v, . o J 1 There are two rules of inference: Modus Ponens: B i s an immediate consequence of A -> B and A . Generalization: Vv A is an immediate consequence of A . We define a sentence § to be provable i f f there exists a f i n i t e sequence of sentences d>, d>0 . . . . . <J> such that d> = d> and for each i < n <f>. is an instance 1 2 n n — I of one of the axioms or follows immediately from preceding sentences by one of the two rules of inference. Such a sequence <{>. d>0 , .. . , <J> is 1 z n called a proof of the theorem <f> . Our f i r s t completeness result states that the class of theorems of a f i r s t order language L coincides with the 11. class of sentences true in a l l realizations of L . Theorem 1-6. (Weak Completeness Theorem). A sentence <j> of a f i r s t order language is provable i f f i t is universally valid. In addition to axioms A.1-A.7 we w i l l often wish to adjoin various other axioms which w i l l vary from theory to theory. For example, for our theory of abelian groups we would want to adjoin the axioms G.1-G.5 of §1.1.2. If E is a set of f i r s t order sentences we extend our notion of proof by defining a sentence <j> to be provable from the hypotheses _E i f i t is provable when we adjoin the sentences of E to our axiom schemas A.1-A.7. Thus, for example, by Theorem 1-6 a sentence is universally valid i f f i t i s provable from the null set. For this strengthened notion of proof we obtain a more powerful completeness theorem: Theorem 1-7 (Strong Completeness Theorem) A sentence (J> is provable from the hypotheses E i f f i t is true in a l l models of E . 1.2.5 Remarks concerning the theorems. We conclude section §1.2 with a comment concerning the relative importance of the above results. In this thesis, we take the view that the truth of a sentence i s of greater importance than i t s provability. It i s of course both interesting and helpful to know whether there exists a formal calculus 12. which w i l l y i e l d true sentences as theorems. However, we regard the existence of such a calculus as a desireable but unnecessary luxury. Our real concern in evaluating the u t i l i t y of a language centres around "what we can say" with the language. It is well-known that f i r s t order languages can say much of interest; our theory of abelian groups is but one of many examples which could be given. However, there are several deficiencies inherent i n f i r s t order languages. For example, we have already remarked that there is no class of sentences of any f i r s t order language in a single binary relation which can distinguish between the ordered sets of real and rational numbers. Moreover, as we shall presently see, deficiencies of this sort are consequences of such "nice" results as theorems 1-1 to 1-5. It follows that to obtain languages which avoid these deficiencies we w i l l have to sacrifice some of our model-theoretic results. Finally, i t is our view that the weakening of these results i s largely a loss of "aesthetic appeal" and hence not a sacrifice which occasions much grief. 1.3 Some Deficiencies of F i r s t Order Logic. 1.3.1 Non-Standard Models of Arithmetic. The standard model of arithmetic is the relational structure W = < IN , {+,-js} , 0 > where IN is the set of natural numbers, + and the ternary relations of addition and multiplication, s the binary successor relation and 0 the natural number zero. One of the alarming failings of f i r s t order logic is the inability of any f i r s t order language to describe this structure )\( Q-categorically. Precisely, i t has been shown by Skolem [31] that for any set $ of f i r s t order sentences which admits 13. W as a model, there exist denumerable models of <£> which are not isomorphic to W . We now give a demonstration of this result. The f i r s t order language L which we employ has two ternary predicate letters A and M Si to represent addition and multiplication respectively, a binary predicate letter S to represent the successor relation and constant symbols 0 and a , the f i r s t of which is to be interpreted as zero. We agree to write v + v, = v 0 for A(v ,v..,v,J , v -v = v„ for M(v ,v n,v 0) and o l z o l z o 1 2 o 1 2 v' = v . for S(v ,v,) . Also we define the binary predicate letter < o o 1 by writing V q < v^ as an abreviation for 3^2^v2 ^ ^ A Vo + v2 = v l ^ ' The class of sentences of L true in the standard model of arithmetic i s a denoted by TH(W) . Clearly W i s a model of TH(N) when we interpret "a" as any fixed natural number. To see that there exist "non-standard" models of TH(W) , we begin by defining the denumerable set E = { 0 < " a , l < a , 2 < a , . . . } where n is the n successor of 0 . Obviously any f i n i t e subset of E U TH(W) must exclude for some natural number n , a l l the sentences o n < a for every n greater than n Q . Thus, for a given f i n i t e subset of E U TH(W) , we can choose the successor of such a number n Q for our interpretation of "a" and W i s then clearly a model for that f i n i t e subset of E U TH(W) . Hence by the compactness theorem 1-1 E U TH(W) has a model. 14. Moreover, since Z U TH(W) is denumerable, we see by the Lowenheim-Skolem 1-4 theorem that Z U TH(W) has a denumerable model which we denote by W . Finally W is not a model of Z \J TH(W) for i f we pick any natural number n as over interpretation of "a" in M , the sentence n < a of Z w i l l be false in W . Thus our model U is a.denumerable model of TH(W) , and so certainly a model of any collection of sentences true in W , which is not isomorphic to the standard model of arithmetic. Such a model N is called a non-standard model of arithmetic. Despite the fact that we cannot obtain JvC^-categoricity, i t w i l l be helpful to make use of the following f i n i t e axiom system for formal arithmetic: F . l Vv Vv. [v = v, -y v* = v.*] o 1 o 1 o 1 F.2 Vv ~ [v' = 0] F.3 Vv Vv. [v' = v! + v = v j o 1 o 1 o 1 F.4 Vv Vv Vv„Vv , [(v = v- A v„ = v.) -> (v + v„ = v.. + v»)] IV5 V v o V v 1 V v 2 V v 3 [(vo = V I A v 2 = v3) - (vQ-v2 = V l .v 3 ) ] F.6 Vv [v + 0 = v] F.7 Vv Vv, [v + v' = (v + v,)*] o 1 o 1 o 1 F. 8 Vv [vO = 0] F.9 Vv Vv, [v «v' = v 'vn + v ] o l o l - o l o Axioms F.1-F.3 give us the formal analogues for three of Peano's four famous postulates for arithmetic. The remaining Peano axiom is the principle 15. of mathematical induction and cannot be f u l l y expressed in a f i r s t order language. Finally we remark that since the sentence V v ^ 3v, [v < < v'l is easily proved from the hypotheses F.1-F.9, o l o l o every non-standard model of these axioms must contain elements which are bigger (with respect to <••) than a denumerable number of other elements. Such big elements are said to be non- standard. 1.3.2 Other Deficiencies. There are many other deficiencies of f i r s t order logic which result from the model-theoretic results of §1.2. F i r s t l y , we remark that methods entirely similar to those of §1.3.1 show that we cannot characterize categorically by f i r s t order sentences the standard model of analysis given by < R , {+ , •} , {0 , 1} > where R i s the set of real numbers and the relations and constants are the usual ones. Just as there are non-standard models of arithmetic so too there exist non-standard models of analysis. A. Robinson has made interesting use of such non-standard models in his book [28] to which the reader i s referred. We note here that the non-standard models of analysis are non-Archimedean with respect to the usual order; i t immediately follows that the class of Archimedean fields cannot be characterized by any set of f i r s t order sentences. A similar result holds for the class of well-ordered systems: i t i s well-known (and w i l l follow from Proposition 2-10) that there is no collection of f i r s t order sentences in a single binary relation the models of which are precisely the well-ordered systems. 16. Axiomatized set theory also suffers from the model theory of f i r s t order logic. Intuitively, we wish the models of set theory to be very large. However, i f our axiom system is a f i n i t e collection of f i r s t order sentences, as in Godel-Bernays class-set theory, then the Lowenheim-Skolem Theorem provides us with denumerable models. Moreover, for any i n f i n i t e cardinal a , an axiom system of cardinality a w i l l yield models of cardinality a . Clearly, however, we want our models of set theory to be much larger. The same Lowenheim-Skolem Theorem implies that the class of f i n i t e sets cannot be characterized by a class of f i r s t order sentences. That i s , there exists no collection £ of f i r s t order sentences for which the models are exactly a l l f i n i t e sets. For by Theorem 1-4 any such collection would admit models of cardinality at least MAX(|z| , JV/ ) • It follows immediately, of course, that the class of i n f i n i t e sets cannot be characterized. Hence quantifiers which say "there exist a f i n i t e number . or "there exist i n f i n i t e l y .many ..." are not definable in f i r s t order languages. Finally we mention two deficiencies of f i r s t order logic in describing algebraic structures. A f i e l d F is of characteristic zero i f i t i s not of characteristic p for any prime number p ; that i s , i f F i s a f i e l d such that for no prime number p is the sentence Vv(p-v = 0) A M(Vv(p-l) -v=0) v (Vv(p.-2)-v = 0)v ... v(Vv l«v = 0)] true in F . (Here p*v abbreviates the sum of v with i t s e l f p times 17. 0 i s the additive unit of the field.) It is demonstrated in [2] that no single f i r s t order sentence can characterize the class of fields of characteristic zero. A similar argument shows that the class of torsion-free groups - those abelian groups without elements of f i n i t e order -cannot be characterized by a single f i r s t order sentence. Chapter Two. Languages with Expressions of Infinite Length. In his paper "Remarks on Predicate Logic with Infinitely Long Expressions" [32], Tarski initiated the study of L - languages which, vaguely speaking, are distinguished from f i r s t order languages by the following two innovations: (i) Conjunctions and disjunctions of a denumerable number of formulas are admitted as formulas. permitted. These statements w i l l soon be made more precise. Tarski was able to show in [32] that the class of well-ordered systems can be characterized by a Scott in a subsequent paper [29] has demonstrated that there are many advantages to be gained from studying L - languages which allow ( i i ) Quantifications over denumerable sets of variables are also single sentence of a L - language. only the f i r s t of Tarski's innovations. We shall begin therefore by considering these L u>,u> - languages; in §2.2 we shall examine the L languages originally suggested by Tarski. 18. Our notation for these languages, by the way, is due to Karp [11]. For cardinals a and 8 where a is regular and a >_ 8 ^ _ to , Karp has defined a L - language to be one obtained from a f i r s t order ap language by (a) allowing conjunctions and disjunctions of any set of fewer than a formulas and (b) allowing quantifications over any set of fewer than 8 variables. For example, using this notation we could refer to a f i r s t order language as a L - language. Karp has studied completeness toco properties of such - languages for many large values of a and 8 • For our part, we shall largely ignore the L - languages for a > 8 > to CXp since such languages are not required for our investigations in the realm of "everyday mathematics". 2.1 The L - languages. to^ to s — E — 2.1.1 Syntax and Semantics. The symbols for a L - language correspond to those of a to^ to f i r s t order language with the exceptions: (1) We now admit an uncountable set of variables {v^ : B, < to^ } (2) We introduce an additional logical connective "M" for infini t a r y conjunction. The class of formulas F is defined by extending our recursive definition in §1.1.1 to include the following clause: (c) For any ordinal a < to, , i f {F.}. C F then M F. E F . J 1 I i<a i i<a 19. The model-theoretic concepts of f i r s t order logic are easily generalized to the L - languages. In particular, we define the notion of a valuation of the variables x = < a^ : £ < to, > satisfying a L £ 1 Wjto formula <j> in realization A , again written A <J> , by adding the following clause to the recursive definition of §1.1.2: (vi) A t= M d>. i f f A A. for each l < a < co, . x . l x i 1 K a The infinitary disjunction symbol "W" is introduced by writing W tt. as an abbreviation for the formula ^( M ^ <f>.) . Clearly, i<a i<a we have A t= W <(>. i f f A t== <f>. for some i < a . Finally, in the interests i<a of c l a r i t y , we shall sometimes write <f> A ty^ A <f>.j A • • « for M 4^ and similarly <j>^ v ^ V $3 V • • • for W <j>_^ . i<co §2.1.2 Characterizability Results. Many of the deficiencies of f i r s t order logic discussed in §1.3 are easily overcome when we pass to L - languages. 10.^ 10 For example, we now produce a single L - sentence a for co^ to which a l l models are isomorphic to the system of natural numbers. For this we consider the L - language with single binary relation S to represent V the successor relation and a constant symbol 0 to represent zero. As in §1.3.1, we write v 1 = v, for S(v ,v,) . Our characterization of the o . l o 1 20. natural numbers is achieved by expressing in this language each of Peano's axioms for the natural numbers. In §1.3.1 we remarked that only Peano's axiom of mathematical induction i s inexpressible in a f i r s t order language. Essentially this axiom says that every set which contains zero and the successor of each natural number contains a l l natural numbers. Hence, an element x i s a natural number i f f x is zero or x i s the successor of zero or x i s the successor of the successor of zero or .... The "or ..." here requires an infinitary disjunction for i t s expression. Precisely, we express Peano's axiom of induction by the L - sentence d> given by \/v [ v = 0 v v = 0 ' v v = 0"v ...] . We then define the sentence a to be the conjunction of this sentence and axioms F . l - F.3 of §1.3.1. The usual proof of the categoricity of Peano's axioms can be used to show that a l l models of a are isomorphic to the- system of natural numbers. Thus the natural numbers may be described categorically by a single L w w ~ sentence. In L - languages i t i s also possible to produce a single sentence for which the models are exactly a l l f i n i t e sets. To do this we 3 > n — , where n is a positive integer, by 3 - n = 3 v 1 3 v 2 ...3v n [(v x j* v 2 A v± + V 3 A ... Av 1')» v n ) A <V 2 ^ V 3 A . . • A V 2 ^ V N ) A . . . A ( V N _ 1 $ V N ) ] . (Here we have written v. 3^ v. for ^ v. = v.) . Obviously, a relational 21 structure A satisfies 3 " " ° i f f A has at least n elements. Hence, i f we define 3 l n to be the sentence 3 — n A ^ 3 — , we see that the models of 3 ' n are a l l relational structures of exactly n elements. Finally, we define J to be the L - sentence W_Jl . The class of models 3 ° to,to 1 n<to of J i s then the class of a l l f i n i t e sets; similarly, the models of are a l l sets of i n f i n i t e cardinality. As another example we show, again in contrast to our results for f i r s t order logic, that we can characterize the class of Archimedean-ordered fields by a single L - sentence. For this we consider the L to^ co to^ to language with ternary predicate letters A and M to represent addition and multiplication respectively, a binary predicate letter R and constant symbols 0 and 1 . We write v + v, = v n for A(v ,vn ,v_) and o ± z o x z v R v. for R(v ,v.) . The Archimedean axiom is then given by the single o 1 o 1 ° sentence: \ / V q [ 0 R V Q -> V v 1 3 v 2 W (v± R v 2 A v 2 - n . v Q ) ] . (A) n<to where n-v is short for the sum of v taken with i t s e l f n times, o o Our characterization of the Archimedean - ordered fields i s obtained by taking the conjunction of this axiom and the usual f i r s t order axioms for a f i e l d . The class of fields of characteristic zero may also be described categorically by a single ^ - sentence. Precisely, we take the conjunction 22. of the usual f i e l d axioms and, for each, prime number p , the sentence 0^ given by C p =Vv(p-v=0) [cVv(p-l)-v=0) v cVv(p-2)-v=0)v . . . v(Vv(l.v=0))] Similarly, the class of torsion-free groups can be characterized by the single ^ - sentence given by the conjunction of the usual axioms for groups and, for each positive integer n , the sentence : D = ~3v (v 4 0 A n-v = 0) n The reader may have noticed that we have not attempted characterizations by L - sentences of either the class of well-ordered systems or the standard model of analysis. We shall have more to say about the pos s i b i l i t y of such characterizations later in this chapter. 2.1.3 Failure of the Compactness Theorem. As we demonstrated in §1.3, many of the deficiencies of f i r s t order logic are induced by the "aesthetically Pleasing" properties of models summarized i n theorems 1-1 to 1-5. It i s not surprising, therefore, in view of the examples of the preceding section, that some of these model-theoretic results w i l l f a i l to generalize f u l l y to the ^ - languages. It w i l l be presently shown, for example, that the compactness theorem 1-1 23. f a i l s to hold in L - languages. F i r s t , however, we define a set of formulas {E (v ) : a E u j which w i l l play an important role i n much a o 1 of our subsequent discussion. We consider a L - language with a binary relation < and a constant symbol 0 . As usual, < (v is written v < v. . The formula J o 1 o 1 E (v ) where a e (D- is defined by transfinite induction as follows: a o 1 EJVJ =~3v [v < v ] O O ± 1 o (E) E (v ) =Vv1[v. <v « W E r(v )] a o 1 1 o K 1 We now prove the following proposition: Proposition 2-1. Suppose A = < A , < , 0 > i s a relational structure where < is a total order on A with least element 0 . Then for any a e to^ , an element a e A satisfies E (v ) in A i f f the set {a e A : a < a } o a o o is well-ordered by < in type a . (By "a o e A satisfies E a ( v D ) i n A " , we mean that any valuation of the variables which interprets V q by a Q satisfies E (v ) in A .) a o The proof is by transfinite induction on the ordinal a . T r i v i a l l y , the proposition i s true for a = 0 . We assume the following 24. induction hypothesis ( I ) : For each C E a , a satisfies E„(v ) in o C o (I) A i f f {a : a < a Q} i s well-ordered by < in type C . We wish to show that a satisfies E (v ) in A i f f - {a : a < a } o a o o is well-ordered by < in type a . Suppose f i r s t that a satisfies E (v ) = \/v, [v, < v W E^Cv,)] , o a o 1 1 o C 1 C<a By the induction hypothesis ( I ) , for each a e A we have a < a Q i f f the set {x e A : x < a} is well-ordered in type C for some ^ £ ct . It follows that {a : a < aQ} = {a : {x e A : x < a} is well-ordered by < in type £ for some C e a:.} . Suppose now that S is a non-empty subset of £a : a < aj . We note that S C {a : a < s} U {a : s < a} U {s} for some s e S such that {a : a < s} is well-ordered by < in type £ for some £ e a . If S f l {a : a < s) = f then S has least element s while i f S D {a : a < s} ^ <Ji. then this set i s a non-empty subset of a well-ordered set and so again S has a least element. Hence {a : a < a } . o is well-ordered and, by an easy contradiction, i s of type a . Conversely, assuming that {a : a < a Q} i s well-ordered by < in type a , we wish to show that a satisfies E (v ) . For any b < a Q , b e A , the set {a e A : a < b} is a proper subset of a well-ordered set of type a and hence is well-ordered by < in type £ for some £ e a . It follows by the induction hypothesis (I) that V q = b satisfies E^(v ) and so v = a satisfies Vv, k<v -> W E_(v,)] £ o' o 1 1 o C 1 25. Moreover i f v^ = c , c e A , satisfies E^(v^) for some c e a then {a : a < c} i s well-ordered by < i n type E, e a whence c < a Q since {a : a < a^} is well-ordered i n type a . Thus V q = a actually satisfies E (v ) =Vv 1[v 1 < v W. E_(v-)] in A and so a satisfies E (v ) in A a o l 1 " 1 o _ £ 1 o a o £<a Thus a satisfies E (v ) i f f {a e A : a < a } is well-ordered o a o o by < i n type a and so by transfinite induction our proof i s complete. We make use of this result to give an example due to Scott [29] which shows that the compactness theorem 1-1 f a i l s to hold i n L - languages. co^ co In fact, Scott produces a collection Z of L - sentences which has (O^tO no model but is such that every countable (finite or denumerable) subset of £ does have a model. We consider a L - language with binary relations < and R , a ternary relation A to represent group addition and a constant symbol 0 to represent the group unit. Again, we write V q < v^ for <(v ,v..) and v R v n for R(v ,vn) . Our set Z is the union of four o 1 o 1 o 1 sets of axioms which we now describe. To bjegin, we take the uncountable set of sentences {3v E (v ) A Vv Vv. [ (E (v ) ^ v , < v ) -»- v, R v ] : a e t o , ) ? . o a o o 1 a o 1 o 1 o IS By proposition 2-1 we see that the f i r s t conjunct of the sentence 3v E (v ) A Vv Vv, [(E (v ) A v, < v ) •>• v, R v ] says that there exists an J o a o x o 1 a o 1 o 1 o til a element with respect to the order < ; the second conjunct of this sentence says the elements of the i n i t i a l < - segment determined by the • a - element v are also less than v with respect to the order R . o o ^ 26. We adjoin our axioms for abelian groups given by G.l - G.5 of §1.1.2. Next we take the following axioms which say R i s a total ordering: 0.1 \/ v ^ (v R v ) v o o o 0.2 \ / v V v , V v „ [v R v, A v n R v 0 v R v j O J . Z O 1 1 2 O 2. 0.3 V v V v - [v R v. v v.- R v v v = v. ] o 1 o 1 1 o o 1 Finally, we include the Archimedean axiom given by (A) of §2.1.2. Clearly for this set of sentences E , a relational structure 8 » < B , {+,<,R} , 0 > is a model for £ , with the obvious interpretations for the relations and constant, i f f B is an abelian group Archimedean - ordered by R with a subset ordered by < in type co^ . But, as we now show, there can be no such set B . For i f B is Archimedean - ordered by R and b is any element of B for which 0 R b , then the set {b , b + b , b + b + b , ...} would have to be cofinal in B with respect to the group order < . This implies that co i s cofinal in co^ - which, of course, is false. Hence Z has no model. However any countable subset of E i s clearly satisfied by the ordered group of rationals. It is not true therefore that a set of L - sentences has a model i f f every f i n i t e subset, or indeed every countable co^ to subset, has a model. Thus, the compactness theorem 1-1 does not generalize f u l l y to the L - languages. coxco Recently, however, Kreisel and others have considered various sub-languages of the L - languages which allow as formulas infin i t a r y co, co 27. conjunctions and disjunctions only of sets of formulas generated in a certain constructive manner. These sub-languages are strong enough for the tasks usually demanded of languages with expressions of i n f i n i t e length since when we make an i n f i n i t e conjunction or disjunction, the components are f a i r l y simply related one with the other. In [1] Barwise has proved a compactness result for such sub-languages. The interested reader i s also referred to the papers [18] and [13] ofKreisel and.Karp respectively. 2.1.4 Lowenheim-Skolem Theorems. Scott has shown in [29] that weak generalizations of the Lowenheim-Skolem theorems 1-2 and 1-3 are possible. Theorem 2-2. (Downward Lowenheim-Skolem for L .) . w Every countable set of L --sentences.with a model of some i n f i n i t e cardinality, has a model of each smaller i n f i n i t e cardinality. This result i s i n s t r i c t analogy with Theorem 1-2 except for the countability restriction. To see that this restriction is necessary, we consider the uncountable collection of L - sentences $ = ftv E (v ) : a e to.} U i<t>} -* o a o 1 where <J> is the f i r s t order sentence which says that < i s a total order. In view of proposition 2-1, the f i r s t uncountable ordinal Q ordered by set 28. membership i s e a s i l y seen to be a model of c a r d i n a l i t y . C l e a r l y , however, $ admits no countable models. For the upward theorem such a simple-minded extension i s not p o s s i b l e . For, as we have already seen, i t i s p o s s i b l e to describe the n a t u r a l numbers )K - c a t e g o r i c a l l y by a s i n g l e L - sentence. I t o b J J 6 to^ to turns out that an a d d i t i o n a l r e s t r i c t i o n i s required-. Theorem 2-3 (Upward Lowenheim-Skolem Theorem f o r L ) , E _ . y y Every countable set of L - sentences with a model of c a r d i n a l i t y at l e a s t "J has a model of each l a r g e r c a r d i n a l i t y . Here J ^ i s the c a r d i n a l i t y of the class of a l l sets of rank < to^ . More generally, f o r any o r d i n a l a we define the set r e c u r s i v e l y by V = d> , V = U PV_ where P i s the power set operation; ~1 i s then the c a r d i n a l i t y of V . a Scott [291 has shown that the r e s t r i c t i o n to the c a r d i n a l J "1 i n the hypothesis of theorem 2-3 cannot be improved.. To see t h i s , we consider the L - language with a s i n g l e binary predicate l e t t e r e . The l e t t e r s x , y , z w i l l represent v a r i a b l e s of t h i s language; e(x,y) w i l l be w r i t t e n x e y . For a < to. , the formula V (x) i s defined 1 a r e c u r s i v e l y by: 2 9 . v (x) =Vy C^ y e x) v (x) = w V y (y e x + v (y)) I f we i n t e r p r e t e as the set membership r e l a t i o n , i t i s e a s i l y seen that V = {m : x = m s a t i s f i e s V (x)} . F i n a l l y we define the sentence T by: a a a T =\/xVy [x = y -»Vz(z e x -«-»- z e y ) ] A \/x W V (x) . a 8<a p The f i r s t sentence i n t h i s c o n j u n c t i o n i s c a l l e d the e x t e n s i o n a l i t y axiom. Our demonstration depends upon the f o l l o w i n g r e s u l t : P r o p o s i t i o n 2-4. I f a < to^ then every model of T^ i s i s o m o r p h i c a l l y embeddable i n 8 = < V , e > where e i s the s e t membership r e l a t i o n r e s t r i c t e d to a a For the proof of t h i s p r o p o s i t i o n we consider, f o r f i x e d a < to^ , any model < M , r > of T . Given m e M , there e x i s t s at l e a s t one a o r d i n a l 8 < a such that x = m s a t i s f i e s V 0 (x) = wVy(y E x-> V_(y)) . 3 • C<8 K Hence there e x i s t s a t l e a s t one o r d i n a l £ , X < a , such t h a t x = m s a t i s f i e s \ / y ( y e x •+ V^(y)) . We denote by £ m the l e a s t such £ and define the map h : M -> V by h(m) = V . We c l a i m that h i s an m isomorphic embedding of < M , r > i n t o < , e > . 30. To show h i s one-to-one, we make use of the extensionality property of < M , r >. Assume then that m^ , e M are such that h(m^) ^ h(m2) . Without loss of generality, we write h(m^) = , h(m2) = where < ? 2 . By the definition of ^ = ^ , x = satisfies Vz(z e x -> V (z)) . However, since £, < £„ and by the minimality of £ 2 , x = m2 does not satisfy Vz(x e y -»- (z)) thus x = m^ , y = m2 does not satisfy V z ( z e x •«-»• z e y) and so by the extensionality property re must have m^ $ m2 . Hence the map h i s one-to-one. We now show h is a homomorphic embedding of < M , r > into < , e > . The proof of this rests upon the simple observation: I < ? implies V e V (*) This i s immediate because V e PV implies V e U PV,. and by definition V = U PV . Suppose that m.. , m_ £ M are such that m^ r m2 . We need show that h(m^) e h(m2) . Since m^ r m2 and x = n satisfies V y (y e x -»• (y)) , where h(m2> = ? 2 , we see that y = satisfies V (y) = W \ / t ( t e y -> V (t)) and so y = m satisfies h K<K2 K 31. V t ( t e y -> V^(t)) for at least one £ < £ 2 . Thus h ^ ) = for some £ < £ . Hence by (*) , V e V or equivalently h(m1) e h(m_) . 1 1 ^1 ^2 Thus h is an isomorphic embedding of < M , r > into < , e > and our proof of Proposition 2-4 i s complete. The above argument shows that for any a < co^ there is a single sentence T every model of which i s of cardinality at most card(V ) = 3 a a a Since 3 = l i m J , i t immediately follows that the restriction to J 1 a<co^ 1 in the hypothesis of theorem 2-3 cannot be improved. 2.1.5 Completeness Theorems. We now extend our notion of proof for f i r s t order logic to obtain completeness theorems for the L - languages. To our axiom system A l . - A.9 of §1.2.5 (where A , B , C are now L w ^ ~ formulas) we add the further axiom schema: A. 10 M A -*• A D where B < a < co. and for each £ < a A is a ~ £<a C 3 1 • 1 ;L - formula. In addition to modus ponens and generalization, we take the following i n f i n i t i s t i c rule of inference: (c) M B^ is an immediate consequence of the formulas B Q , B^ , B^ , .... where E, < a 32. A L - sentence A is said to be provable from a set £ to^ to x of L - sentences i f f there exists a (transfinite) sequence of sentences tO^ ti) <f> A A .... A where $ < w. such that <J> = <f> and for each E, < g A O X Z p 1 p c, i s either an instance of one of the axiom schemas A.1 - A.10 or a sentence of E or an immediate consequence of preceding sentences i n the sequence by one of the three rules of inference. Further, we require that every sentence A^ of the sequence have only a f i n i t e number of free variables. (This seems to be a reasonable restriction since i t i s easily seen that for any L - sentence, every sub-formula has only a f i n i t e to^to number of free variables.) Such a sequence A A <j> ... A is then said to o X z p be a proof of A from E . The sequence is called simply a proof of A i f i t i s a proof of A from the n u l l set. A sentence for which there exists a proof is again called a theorem; a sentence true in a l l models is said to be universally valid. With this definition of proof,theorem 1-6 generalizes f u l l y : Theorem 2-5. (Weak Completeness Theorem for L ) * u u A sentence A of a L - language is provable i f f i t is universally valid. We also get a strong completeness result which i s , however, somewhat weaker than that for f i r s t order logic: 33. Theorem 2-6 (Strong Completeness Theorem for ^ )* A sentence i> of a L - language is provable from a countable set £ of sentences i f f <j> i s true in a l l models of E . This result i s analagous to theorem 1-7 except for the countability restriction. The uncountable set £ , defined in §2.1.3 as a counter-example to a possible compactness theorem for L , also serves to demonstrate the necessity of the above restriction. For i f ¥ is any L - sentence then the sentence ¥ A i s certainly not provable from £ . (If i t were, i t would be provable from a countable subset of £ and hence by Theorem 2-6 would be true in any model of that subset.) However any sentence is t r i v i a l l y true i n a l l models of £ since, as we have seen in §2.1.3, the set £ has no models. Thus, Theorem 2-6 cannot be improved. Finally, we note that Lopez-Escobar has formulated i n [20] a complete axiomatization for those kinds of sub-languages of the L - languages mentioned in §2.1.3. 2.1.6. A Result Concerning Well-Ordered Systems. In §1.3.2 we remarked that the class of well-ordered systems cannot be characterized by a set of f i r s t order sentences. In this section we w i l l show that in L - languages a partial result i s possible; namely, for any given (countable) well-ordered structure A we w i l l produce a single L - sentence for which a l l countable models are isomorphic to A . This 34. result w i l l be seen to be an instance of a more general countable isomorphism theorem. We again make use of the formulas E (v ) , a e to, , defined by (E) a o i §2.1.3. As in that section, we consider the L - language with binary relation < and a constant symbol 0 . Suppose that A = < A , < , 0 > is a realization of this language where < is a well-order on A with least element 0 and the set A is of type a , a e to^ . In view of proposition 2-1, i t i s easy to check that any structure B is a model of the sentence S^ given by ^ l v E (v ) /v\/v W E_(v ) i f f B is a well-ordered system of 6 J J o a o v. o _ £ o type a . Such a model is clearly isomorphic to A . We have thus shown that the countable well-ordered structure A is described ^ - c a t e g o r i c a l l y by S . a In [29] Scott has offered the following theorem which generalizes the above situation: Theorem 2-7 (Countable Isomorphism Theorem for L ) v c w Any countable structure can be described 5K - categorically by a single L - sentence, to^ to I t follows immediately that countable structures are elementarily equivalent with respect to L - sentences i f f they are isomorphic. We 0)^0) might wonder, therefore, whether the relations of isomorphism and elementary equivalence are identical for the L - languages. The answer to this 35. conjecture w i l l be supplied in the next section. 2.1.7 A Characterization of Elementary Equivalence. In [12] Karp has studied a class of L - languages where a ato i s a regular cardinal, which generalize the L - languages by 'admitting to^ to as formulas conjunctions and disjunctions of < a formulas. As for the ^ - languages however, each of the - languages permits strings of quantifiers of only f i n i t e length. A L - sentence i s thus called a finite-quantifier sentence. Karp has given a characterization of elementary equivalence with respect to f i n i t e quantifier sentences. We shall f i r s t present a stronger result also due to Karp [12] from which this characterization w i l l follow. We begin by stating some definitions. The quantifier-rank of a L - formula <b i s defined recursively as follows: aco (i) qr(cj)) = 0 i f <}) is an atomic formula ( i i ) qrCH) = qr((J>) ( i i i ) qr(3v<») = qr(Vv<j)) = qr(<j>) + 1 (iv) qr( M $ ) = qr( W <j> ) = U qr(<}> ) for any g <_ a . If A , B are two realizations of a L - language then, for any ordinal aco 6 , A and B are equivalent with respect to finite-quantifier sentences of rank 6 , written A E B , i f f they satisfy the same sentences having rank 5 in any of the corresponding - languages. In fact, one can easily check 36. that A B i f f A , B satisfy the same sentences of rank at most 5 . If A i s a relational structure (without function letters) and {a^,...,an) i s a subset of the domain of A , then the sub-structure of A f i n i t e l y generated by {a^ a^ } , A' , i s simply the restriction of A to {a,,...,a } ; that i s , the domain of A' is { a . a } and the relations I n ± n of A 1 are those of A restricted to {a.,...,a } . I n With these definitions we are able to state the f i r s t of Karp's important theorems: Theorem 2 - 8 . Suppose A , B are two realizations of the same L - language with domains A , B respectively. Then for any ordinal 6 the following conditions are equivalent: (1) A =s B (2) For each ordinal 0 <_ <5 there i s a non-empty collection 1^ of isomorphisms on f i n i t e l y generated sub-structures of A into B such that I„CZ I whenever v < 0, and such that: 0 v — (a) If 6 < 6 then for each a e A , f e I g + 1 » there exists g e l . such that g extends f and a e Domain g . (b) If 0 < 6 then for any b e B , f e I , there exists g e-I f l such that g extends f and b e range g . 37. For a proof of this theorem, the reader is referred to [12]. As a corollary we obtain the following characterization of elementary equivalence: Theorem 2-9. Suppose A , 8 are realizations of the same L - language with domains A , B respectively. Then the following conditions are equivalent: (1) A and 8 are elementarily equivalent with respect to f i n i t e quantifier sentences. (2) There is a non-empty collection I of isomorphisms on finitely-generated substructures of A into 8 such that (a) Given a e A and f e I , there exists g e l such that g extends f and a e domain g . (b) Given b e B and f e I , there exists g e l such that g extends f and b e range g . The profound half of this theorem, that condition (1) implies (2), i s easily proved with the help of Theorem 2-8. For i f A and 8 are elementarily equivalent with respect to finite-quantifier sentences, then for any ordinal 6 we clearly have A = 8 . Hence, making use of the sets I o o given by condition (2) of Theorem 2-8, we can define I = U I. . It is e<co 9 immediate that this set satisfies condition (2) of Theorem 2-9. We conclude this section by demonstrating that the countability restriction in the countable isomorphism Theorem 2-7 cannot be removed. This is painlessly achieved with the use of Theorem 2-9 by considering 38. relational structures A = < A ,= > and 8 = < B , = > where A i s countable, B uncountable. Each structure i s equipped with the equality symbol as i t s only predicate letter. If we define the set I = {f : domain is any f i n i t e subset of A , range f C B and f is one-to-one} , then I easily s a t i s f i e s condition (2) of Theorem 2-9. Hence by that theorem, A and .8 are elementarily equivalent with respect to L - sentences. However, A i s not isomorphic to 8 since A is countable while 8 is uncountable and so our demonstration i s complete. 2.1.8 Non-characterizability of the Real Numbers. We are also able to make use of Theorem 2-9 to show that there i s no collection of finite-quantifier sentences for which a l l models are isomorphic to the system of real numbers. To this end we consider the relational structures A = < Q , < > and 8 = < R , < > of the rationals and reals respectively, ordered in the usual way by < . We define the set I = {f : domain f is any f i n i t e subset of Q , range f C R and f is one-to-one and order-preserving} . That this collection satisfies condition (2) of Theorem 2-9 is an easy consequence of the fact that Q i s dense in R . Hence, by the same theorem, A and 8 are elementarily equivalent with respect to f i n i t e quantifier sentences. We conclude that the system of real numbers cannot be described categorically by any collection of finite-quantifier sentences. Finally, we remark that since a l l order-complete fields are isomorphic to the real numbers and since we can easily state the axioms 39. for a totally ordered f i e l d in a f i r s t order language, i t follows that i t i s the completeness axiom which cannot be formulated in f i n i t e -quantifier languages. Thus, our future efforts to characterize the real numbers w i l l centre around an attempt to formulate this completeness property. 2.1.9 Non-characterizability of Well-orders. We conclude our study of finite-quantifier languages by outlining an argument of Karp [12] which shows that in languages of this kind we are unable to describe categorically the class of well-ordered sys terns. We f i r s t make a few definitions. Suppose 6 is an ordinal 6 for which 6 = U to and A = < A , R > is a totally ordered structure 6<6 with least element denoted by 0 . We then define the ordinal product of - 6 and A by: 6 8 A = ' { < £ , a > : € < 6 , a e A } this structure i s ordered anti-lexicographically by the relation < : < £ , a > - < < v , b > i f f aRb or a = b and £ < v . For 0 < 6 we define a to - interval of 6 to be any left-closed 0 0 interval of the form [to •£ , to •(£+!)) for some £ < 6 . Similarily 40. 0 0 a co - Interval of 6 8 A is an interval of the form [<co • £ , a> , <to *(£+l),a>) for some £ < 5 , a £ A . It is easy to check that any co - interval of 6 is contained in 6 and any co - interval of 6 8 A i s contained in 6 8 A . With these definitions we can state the following proposition: Proposition 2-10. If 6 = U co6 then < 6 , < > = < 6 8 A , - < >. 0<6 6 For the proof we define I Q , 0 < 6 , by: I. = (f : f is a restriction to a f i n i t e subset of 6 containing o 0 of an order-preserving one-to-one translation of a union 0 Q of co - intervals of 6 to a union of co - intervals 0 Q of 6 8 A which carries [0 , co ) to [<0,0> , <co ,0>).} We now check that the set {I. : 0 < 6} satisfies the condition (2) of Theorem 2-8. To begin, I is non-empty for each 0 < 6 since the function 0 f : {0} {<0,0>} is contained in each I n . We also notice that i f 0 0 0 0 v _< 6 then any co - interval of 6 , [co •£ , co -(E+l)) say, is a union 0 0 v 0~ v of cov - intervals of 6 . Indeed, [co • £ , co '(£+1)) = U [co • (co -C+ot), , 6-v aeco 0 — 0 cov« (co v-£+a+l)) j similarly, every co - interval of 6 8 A is a union of coV - intervals of 6 8 A whenever v < 0 . Therefore, i f f e I Q then f E I whenever v < 0 ; that i s v < 0 implies I . e . I v — — 0 v 41. It remains only to check statements (a) and (b) of Theorem 2-8. In [12] Karp has verified (b); here we check (a). Suppose then that 0 < 6 , f e I.,, and c e 6 . We show there exists a function 5+1 g e l which extends f and i s such that c £, domain g . By the 6 definition of I , f i s a restriction to a f i n i t e subset of 6 o+l containing 0 of some order-preserving one-to-one translation F of 0+1 0+1 to - intervals of 6 to a union of to - intervals of 6 8 A 0+1 0+1 which carries [0,to ) to [<0,0> , <to ,0 ) . We write as ©+1 J , J, , . . . , J the l i s t of to - intervals of 6 , in increasing o 1 n order, which contain elements of domain f . There are two cases to consider: (i) c e for some k e {0 , 1 , ... , n} . In this case we define g to be the extension of f which maps c to F(c) ; g is then a f i n i t e restriction of F and so ( i i ) c j for any k e {0 , 1 , . .. , n} We denote by J the rightmost of the intervals J. to the J m b x Q l e f t of c . Then J is a union of to - intervals of which only a m f i n i t e number, J J J , say, contain elements of domain ml mz mp We denote the f i r s t to - interval to the right of c by J ; m,P+l 0 the co - interval which contains c i s denoted by K Clearly K i s to the right of.. J .'for i f K -were to m 42. 0 intersect J i t would have to coincide with one of i t s co - sub-m intervals and we would have c E J . It i s also easy to see that the m interval J , l i e s to the right of K . We define g to be the m+1 restriction to {c} U domain f of the translation which agrees with F on J. , i ^ m and on J J and which maps K into 1 ml mp F(J ...) in the required one-to-one order-preserving fashion. Again m>P'^ L the function g satisfies the statement (a) of Theorem 2-8 and our proof of Proposition 2-10 is complete. Using this proposition we can demonstrate that no f i n i t e -quantifier sentence in a single binary relation characterizes the class of well-ordered systems. The argument is as follows. Suppose there 0 were such a sentence A . We pick 6 = U co to be any cardinal 0<6 ^ to u qr(A) . If 8 i s any ordered structure which is not well-ordered, then < 6 8 8 , -< > cannot be well-ordered and so A is false in < 6 8 8 ,-< > . However A is true in the well-ordered structure < 6 , < > But by Proposition 2-10 < 6 ' ® 8 , - < > = g < 6 , < - > and so we have a contradiction. Hence no such sentence A exists. Since in the class of f i n i t e quantifier languages we have access to conjunctions of arbitrary length, i t immediately follows that no set of such finite-quantifier sentences can characterize the class of well-ordered systems. 2.2 The L - languages. co^ co^ 2 — e — As we remarked at the beginning of this chapter, Tarski 4 3 . originally proposed in [32] a class of ^ - languages which generalizes the L - languages by "allowing quantifications over denumerable sets of variables." The u t i l i t y of the L - languages was strikingly demonstrated by Tarski's proof in [32] that the class of well-ordered systems can be described categorically by a .single L sentence. In §.2.2 we investigate more carefully this class of L languages. As we shall see, the increased expressive power of these languages i s achieved at some cost to both our model-theoretic and proof theoretic results. 2.2.1 Basic Syntax and Semantics. The symbols for L - languages are identical to those for L - languages. The difference l i e s in the definition of the class F of L - formulas. We add to the recursive definition given in §2.1. the following clause: (d) If u = < v ,v ,,v „,... > is a denumerable sequence of oo ol o2 n variables and F e F then 3 u F e F . The model-theoretic definitions of §2.1.1 also generalize to the L - languages in a natural way. For example, our notion of a L - formula a) being satisfied in a relational structure A by a 44. valuation of the variables x = < a^ : £ < to^ > i s obtained by adding the following clause to the analagous definition given in §2.1.1: (vii) A 1= 3 u A where u = < v ,v .,v ... > x oo o l o2 i f f there i s a sequence <b ,b , ,b „,...> C A such that for i , j < co ^ oo' o l ' o2' ' J i f v . = v . then b . = b . , and A fc= d> where y is the valuation of ox oj oi oj y the variables obtained from x by replacing for each i < co the element a . by b . . (The idea here is that i f u = < v ,v l 5 v > contains oi o i oo' ol o2 more than one occurence of a given variable then each occurence is interpreted in a uniform way.) If u = < v ,v ,,v _,...>, we may sometimes write oo' o l o2 J an 3 v 3v . 3v „ ... A for 3uA . Finally, we write VuA as oo o l o2 abbreviation for ^3u(^A) . 2.2.2 Characterizability Results. In §§2.1.8 and 2.1.9 we demonstrated that in no finite-quantifier language could we characterize either the ordered system < R , < > of real numbers or the class of well-ordered systems. We now show that both these characterizations are possible i n L - languages. We are also co^ co^ able to formulate the quantifier which says "there exists a denumerably i n f i n i t e number this gives us an immediate generalization of the countable isomorphism Theorem 2-7. In §2.1.8, i t was pointed out that the completeness axiom (that every increasing sequence which is bounded above has a least upper bound) could not be expressed in any finite-quantifier language. 45. By contrast, in the L - language with the single binary relation < this axiom i s easily formulated as follows: \fv VviVv„. . . [ Qv M v.<v /s M v.<v. ..) 3s [ M v.<s A \ / V ( -*M V . <V -* s<vvs=v) ¥ o v 1 2 . x . 1 l+l . i . 1 Kli) KtO KtO KtO Hence the ordered system < R , < > is categorically described by the single L - sentence given by the conjunction of this sentence and the f i r s t order axioms which say that < i s a total ordering. In the same L - language we are able to describe the class (O^tO^ of well-ordered systems categorically by a single sentence. This is achieved simply by taking the conjunction of the f i r s t order axioms for a total ordering and the L - sentence w l w l ^ Y l V 2 - " [ M Vn+1 < V n ] n<co Also, the quantifier which says "there exists an uncountable number ..." is easily definable in any L - language. Indeed, a relational structure i s of uncountable cardinality i f f the sentence J 1 = V v 0 V v 1 V v 2 . .. j v ( M v * v n) n<to is true in that structure. Conversely, the class of models for the 46. sentence ^3 consists of a l l countable ( f i n i t e or denumerable) sets. The class of denumerably i n f i n i t e sets is described categorically by the single sentence 3' given by _J A v f ~ where 3 is as i n §2.1.2. This last result makes i t at once obvious that the following generalization of Theorem 2-7 is correct. Theorem 2-10 (Countable Isomorphism Theorem for L .) : ^ Every denumerably i n f i n i t e structure can be described categorically by a single L - sentence. V i Finally, we remark in passing that Kopperman has given in [17] a categorical description of the theory of Hilbert spaces. In the same paper i t is shown that this theory cannot be so described by f i r s t order sentences. 2.2.3 Lowenheim-Skolem Theorems. The sentence J defined above allows us to see immediately that the downward Lowenheim-Skolem theorem for L , Theorem 2-2, f a i l s to "7—1 generalize to L - languages. For the sentence —1 has a model of cardinality but can have no denumerable models. It is unknown to the author whether the upward Lowenheim-Skolem theorem for L , co^ to Theorem 2-3, can be generalized to L - languages; in particular, i t i s not known whether there exists a countable set of L - sentences 47. with a model of cardinality > 13 , but no models of some larger i n f i n i t e cardinality. 2.2.4 Completeness Theorems. As we have already mentioned, Karp has extensively studied in '[11] the completeness properties of the L - languages for many values cxp of a and g . However, the question of the existence of a complete formal deductive system for the L - languages was not answered by co1co1 Karp in [11] and i s , we believe, s t i l l an open question. 2.2.5 Infinitary Predicate Letters. Our a b i l i t y in L - languages to quanitify over a denumerable to1(o1 number of variables makes i t reasonable to consider a further extension of these languages, namely, the introduction of infinitary predicates. In fact Tarski, in his early paper [32], mentioned this possibility. The idea is to allow predicate letters (or function letters) of denumerable degree. R>r such a predicate letter P , we then admit P(v ,v^,v^,...) as an atomic formula; our recursive definition of a formula i s otherwise unchanged. A principal advantage of languages with infinitary predicates is their a b i l i t y to express various limiting notions in a natural way. For instance, an i n f i n i t e series of numbers, £ a. , can be readily formulated i<w in a L - language with an infin i t a r y function letter to represent 48. " i n f i n i t a r y addition." More generally, the fact that a number "a" is the limit of a sequence {a.} expresses a relation between a i<to denumerable number of elements and so is most naturally described by an i n f i n i t a r y predicate letter . Languages of this kind have not been greatly studied in the literature. Henkin, in an early paper [10], studied a class of languages which generalize those of f i r s t order solely by the introduction of inf i n i t a r y predicate letters. However, since no provision is made for quantifying over a denumerable- of variables, i t is impossible to obtain a sentence (that i s , a formula without free variables) from a formula which contains an infini t a r y predicate letter. This leads to a great deal of unnaturalness in the definitions and a scarcity of "decisive" theorems. We conclude our study of languages with i n f i n i t e l y long expressions by mentioning one further extension of the L - languages. V i Henkin considers elsewhere in [10] languages which allow not only denumerable strings of quantifiers but also denumerable alternations of the universal and existential quantifiers. In such languages we admit expressions such as 'V V Q 3v^Vv 2 3v^ ••• F" as formulas. The study of such languages bears an intimate relationship to the theory of certain i n f i n i t e games. The interested reader is also referred to H.J. Keisler's papers [14] and [16]. 49. Chapter Three. Languages With Generalized Quantifiers. In Chapter two we were able to describe categorically sets of various cardinalities which cannot be characterized in f i r s t order logic. The reader w i l l r e c a l l , for example, the infi n i t a r y sentences _J and -J for which the models are the i n f i n i t e sets and the sets of uncountable cardinality respectively. Such characterizations, however, were essentially by-products of the i n f i n i t i s t i c approach of the last chapter. It was not Tarski's original purpose in [32] to obtain such characterizations. Indeed, the principal result of [32] i s to show that the class of well-ordered systems can be described categorically in a L - language; the characterizations of sets of given cardinality occur nowhere in that paper. In this chapter we consider a generalization of f i r s t order logic which i s more directly motivated by the desire to characterize sets of various cardinalities. This is the introduction of generalized quantifiers f i r s t suggested by Mostowski in [24], published a year before Tarski's paper [32]. The motivation for Mostowski's approach is rooted i n the feeling that i t is somehow unfair to ignore quantifiers which are in widespread use throughout "everyday mathematics". For example, in topology one defines the product topology of an indexed collection {(X , T ) : a e A} of topological spaces to be that topology with base consisting of a l l those til subsets of IT X such that for each B e A the B - coordinate is A A aeA T - open and is X for a l l but a f i n i t e number of B • The expression p B "for a l l but a f i n i t e number", or equivalently "not for an i n f i n i t e number", 50. could be expressed most naturally by equipping our language with a new quantifier Q to be read "there exists an i n f i n i t e number ... " . o In fact i t was this attitude which Mostowski expressed in an address to an international colloquium: "It i s usual in logic courses to admit only two quantifiers expressed by the words "there exists" and "for a l l " . However, mathematicians have for a long time been used to other quant-i f i e r s , for example "for almost a l l x " or "for a set of at most a denumerable number of x ," etc. It seems that the omission of these quantifiers from courses in logic i s not j u s t i f i e d . " * Inspite of the essential difference between this approach and the i n f i n i t i s t i c approach of Chapter two, certain similarities in the resulting languages do occur. We have already noted that at least some generalized quantifiers are "definable" - a word soon to be made more precise - i n the infinitary languages of the last chapter. Moreover, as we shall soon see, the system of natural numbers which we have described categorically by a single ^ - sentence may similarly be characterized in a language with the generalized quantifier Q q which says "there exists More generally, the languages to be considered in this chapter are obtained from f i r s t order languages by adding a single quantifier Q. , where a i s an ordinal, to be read "there exists > % .... " Such — a languages w i l l be called L ( ^ a ) ~ languages. Actually, Mostowski's Mostowski [25], p. 26. programme in [24] i s more ambitious, i n effect treating our ^(Q^) ~ languages as well as many others. In this respect our treatment follows that of Fuhrken [5] who also concentrates his discussion on the ^(Q^) -languages. 3.1 Syntax and Semantics. The important syntactic and semantic definitions for a L(Q Q) -language are easy extensions of f i r s t order concepts. As outlined above, the symbols of a L(Q^) - language consist of those of a f i r s t order language plus the additional quantifier symbol . For the definition of the class of formulas F we add to the recursive definition given in §1.1.1 the clause: (c) If F e F and v is a variable, then (Q v ) F e F n a n (and the variable v^ no longer occurs freely.) If A i s a relational structure, x = < a ,a,,a„,... > a valuation, of o 1 2 the variables and (j> a ^(Q^) ~ sentence, we define the notion of x satisfying <J> in A , again written A ( = <J> , by adding the following clause to the recursive definition of §1.1.2: (vi) A |= (<(> v H i f f Card{a e A : A ' t=. N <)>} > % . t-^ T \ r a n / y x(n/a) — a (Again x(n/a) is the valuation of the variables obtained from x by replacing a by a .) 52. Following Fuhrken [5], we make an important alteration in our definition of a model; namely, we require that a model of a set of L(Q^) - sentences must be of cardinality _^ 5^ . If such a convention were not adopted we would be confronted with bothersome complications in our model theory. For example, the sentence (Q a v) <KV) where <j>(v) is any formula, would be t r i v i a l l y false i n every structure of cardinality < %^ . For emphasis, then, we make the following convention (C) : Henceforth i t i s implicitly assumed that any model of a set (C) L(Q a) - sentences i s of cardinality _> 5^ • We now give a precise definition for a phrase which we have already informally used. We say a quantifier symbol Q is definable in f i r s t order logic i f f for each L(Q) - sentence a we can find a f i r s t order sentence * such that the sentence a <j> is true in a l l realizations of the L(Q) - language. For example i t follows from our definition of the sentence 3'n i n §2.1.2 that the quantifier which says "there exists exactly n elements such that ... " is definable in f i r s t order logic. Hence i t would be quite superfluous to consider a'"new" language obtained by adding this quantifier to a f i r s t order language. The quantifiers , however, are not definable in f i r s t order logic since the sentence (Q^v)(v = v) gives a categorical description of the sets of cardinality >^ . It i s not d i f f i c u l t to see that these sets cannot be described — a in f i r s t order languages. In the special case where a = 0 we note that the sentence (Q v)(v = v) gives us a characterization of the in f i n i t e sets, o 53. 3.2 Characterization of the Natural Numbers. It i s also possible i n a L(Q o) - language to give a categorical description of the system of natural numbers. In fact such a description i s given by the sentence a obtained by taking the conjunction of the axioms F . l - F.9 of §1.3.1 and the L(Q ) -o sentence Vv ^ (Q v.,)(v, < v ) . This last sentence says that each v o v o Y 1 o J element i s preceded by at most a f i n i t e number of other elements; in other words, no model of a can contain non-standard elements. Hence a l l models of o are isomorphic to the system of natural numbers. This characterization of the natural numbers w i l l have important implications when we investigate the completeness of the L(Q 0) ~ languages. 3.3 Lowenheim-Skolem Theorems. We turn now to a consideration of the model - theoretic results for our L(Q a) ~ languages. Again we expect that these results w i l l be somewhat weaker than those of f i r s t order logic i n view of the increased expressive capabilities of the generalized languages. In fact, the Upward Lowenheim-Skolem Theorem 1-3 f a i l s to generalize to any L(Q^) - language. To see this we consider the ^(Qa) ~ language with binary relation < and constant symbol 0 . We define a to be the sentence • A (Q V ) ( V = v)/s V v ^(Q v.) (v < v ) a o a 1 1 o 54. where <j> i s the f i r s t order sentence that says < i s a total ordering with least element 0 . Clearly a structure can be a model of a i f f i t is a totally ordered set of cardinality % in which every proper i n i t i a l segment is of cardinality < % . Hence a has a model < % a » £ » 0 > but no models of cardinality > % . A generalization of the Downward Lowenheim-Skolem Theorem 1-2, however, is possible: Theorem 3-1. (Downward Lowenheim-Skolem Theorem for L(<J) )) a If £ i s any set of L(Q ) - sentences and £ has a model a of cardinality _^ B , then £ has a model of cardinality B . (Note that by our convention (C) of §3.1 the cardinal B i s assumed to be i t - ' The proof is entirely analagous to that for the similar result of f i r s t order logic. 3.4 Compactness Theorems. The following example due to Bell and Slomson [2] shows that the Compactness Theorem 1-1 in i t s f u l l generality does not hold for any L(Q ) - language. We consider a collection {P_ : £ < Ji } of )lf a £ ' a 'a unary predicate letters and define £ to be the following collection of L(Q ) - sentences: 55. £ = (3v(P (v) A P c(v)) : 0 < C < % } o £ a O 3 v) (p (v) A P fl(v) : 0 < e < 6 < K } c, O 01 (j 0(Q av)P o(v)} If A were a model of £ , then from the f i r s t two sets of sentences making up E we see that v = a must satisfy P Q ( V ) i n A f ° r — elements a i n the domain of A . [If v = a satisfies P Q ( V ) A P^(v) for some £ < %^ and v = a' satisfies P Q ( V ) A p ^ » ( v ) r o r some £' < , V f E , then we see by looking at the second set of sentences that a ^ a' for otherwise v = a would satisfy P^(v) A p ^ t ( v ) . Thus both v = a and v = a" satisfy P Q ( V ) • An easy inductive argument gives the result.] But ^(Q v)P (v) is also true in A and so we conclude that A cannot be a o a model of E . Hence the collection E has no model. However any f i n i t e subset of E involves only a f i n i t e number of the predicate letters P and so easily has a model. Thus we have produced a collection E of ^(Q^) -sentences such that every f i n i t e subset of E has a model but E i t s e l f has no model. The Compactness Theorem 1-1, therefore, does not immediately generalize to any of the L(Q ) - languages. a Weaker generalizations, however, are possible. A language i s defined to be m-compact,where m i s a cardinal, i f any collection of sentences E , of cardinality <^ m , has a model whenever every f i n i t e subset of E has a model. The above example, then, allows for the possibility that some of the 56. L(Q a) - languages may be m - compact for some m < 5^ . An important tool for investigating such results i s a generalization of Los's Theorem 1-5 given by Fuhrken in [5]. Let us f i r s t say that an i n f i n i t e cardinal g i s small for % i f for every indexed collection of cardinals {m. : i e l } , where m. < 5^ for each I I a i e l and Card I < 8 , we have II m. < %( . Los's Theorem for L(Q ) xel i s the following: Theorem 3-2 [Los's Theorem for L(Q ).] Let {A. : i e 1} be a collection of relational structures and x l e t F be an u l t r a f i l t e r on I . If Card I i s small for J([ , then for any sentence <}> of a ^(0,^) ~ language: nA. /T,t= d> i f f { i e l : A. t= <}>} e F . ' x/F x We make use of this result to prove a weak compactness theorem for the ^(Q^) ~ languages: Theorem 3-3. If 8 is small for W , then the L(Q') - languages are 8 - compact. a a Our method of proof i s analogous to Bell and Slomson's demonstration in [2] of the compactness theorem for f i r s t order logic. Suppose Z is a collection 5 7 . of L(Q ) - sentences such that Card £ < 8 • We let Y = {A i A c X and a — Card A '< ]\f } and assume that for each A e Y there i s a model A. of A . o A It i s our intention to construct an ultraproduct of these models A^ , A E Y , which w i l l be a model of £ . To this end we define for each A E Y & & & A = {A1 £ y : A CZ A1} . Clearly A ^ <j> for any A e Y since always A e A Also, given any f i n i t e subset {A^,A^,••.,A^} of Y we have A. u A_U ... UA e A n A H ... OA 1 2 .n 1 I n since A, U A~U ... UA is a f i n i t e subset of Y which contains A. 1 2. n l for each i = 1 , 2 , ... , n . Thus {A : A E Y} has the f i n i t e intersection property and so by a well-known theorem may be extended to an u l t r a f i l t e r F . (See, for example, B e l l and Slomson [2], P.16.) We show now that II A / AEY A / F i s a model of £ . Let a be any sentence of £ . Then {a} e Y , {o} = A^ say, and so A^ |= a whence clearly A^ , }= a i f A C A ' . Thus o A* = {A' E Y : A C A1} C {A' £ Y : A , \= o} o o A and since A e F we have the fact that (A' E Y : A.,fc= a} E o A 1 Hence by Theorem 3-2, noticing Card y = 8 for 8 > W , we have II A. /_t= a Aey / Thus TCA^j, is a model of a for any a E £ and therefore i s a model of £ Our proof i s complete. 58. Finally we remark that since i s not small for 5^ , Theorem 3-3 i s not helpful in determining whether the 1,(0;-^ - languages are J\f - compact. However, Fuhrken [5] has demonstrated that this question i s answered in the affirmative. His argument is lengthy and is thus omitted. 3.5 Completeness Theorems. We conclude our study of the L ( Q Q ) - languages by investigating completeness properties for the L(Q Q) a n d L(Q-^ ) ~ languages. As we shall see, the completeness property for M Q Q ) - languages f a i l s even in i t s weak form; that i s , there is no "suitable" notion of proof such that the class of universally valid L ( Q q ) - sentences coincides with the class of provable L ( Q q ) - sentences. For L ( Q ^ ) - languages, on the other hand, Keisler has produced a formal calculus for which a strong completeness result holds. Theorem 3-4 (Incompleteness Theorem for L ( Q P ) . ) There is no recursive axiomatization of a' L ( Q Q ) - language such that the class of provable sentences coincides with the class of universally valid sentences. If there were such an axiomatization then the class of universally valid sentences would be recursively enumerable. We demonstrate that this is not so. As we have already seen in §3.2 there is a single L ( Q ) - sentence 59. a for which a l l models are isomorphic to the system of natural numbers. Thus, a f i r s t order sentence <}> i s true in the standard model of arithmetic i f f the sentence a -»• <j> i s universally valid. Hence i f the universally valid L(Q 0) ~ sentences were recursively enumerable so also would be the f i r s t order sentences true in the system of natural numbers. But by Godel's incompleteness theorem, this cannot be so. We conclude that the universally vali d L ( Q q ) - sentences are not recursively enumerable and the proof of Theorem 3-4 is complete. By contrast, Vaught [33] was able to show that the universally valid L(Q^) - sentences are recursively enumerable. In a subsequent paper [15], Xeisler offered an exp l i c i t axiom system which consists of the f i r s t order axiom schemas A. 1 - A.9 of §1.2.4 together with a l l instances of the following L(Q^) - sentences: ± 1 V v o V v 1 - (Q 1 v 2)(v o = v 2 v v x = v 2) Q-2 Vv(4> -> *) -> [(Q^vH -KC^vH] Q-3 ( Q ^ ) <(,(vo) *-»- ( Q ^ ) * ( V ] L ) <M (Q 1v o)t /3vJ+ + ( Q ^ X J J v O <j, v ^ ( Q ^ ) * In these sentences <j> and IJJ may be any L(Q^) - formulas with the exception that in Q.3 v^ does not occur i n <KV0) • As rules of inference Keisler takes only those of f i r s t order predicate calculus: modus ponens and generalization. With this notion of proof Keisler is able to prove: 60. Theorem 3-5. (The Strong Completeness Theorem for L(Q^).) For any set £ of L(Q^) - sentences, the class of L(Q^) -sentences provable from the hypotheses £ is precisely the class of L(Q^) -sentences true in a l l models of £ . 61. Bibliography [1] Barwise, J.: "Implicit Definability and Compactness i n Infinitary Languages", Lecture Notes in Mathematics. 72 (The Syntax and Semantics of Infinitary Languages), Springer-Verlag, Heidelberg, 1968, pp. 1-35. [2] B e l l , J.L.; Slomson, A.B.: Models and Ultraproducts, North Holland, Amsterdam, 1969. [3] Chang, CC. : "Some Remarks on the Model Theory of Infinitary Languages", Lecture Notes in Mathematics.72 (The Syntax and Semantics of Infinitary Languages), Springer-Verlag, Heidelberg, 1968, pp. 36-63. [4] Fuhrken, E.G.: "On Generalized Quantifiers", American Mathematical Society Notices 9 (1962), p. 132. [5] Fuhrken, E.G. : "Languages With Added Quantifier 'there exist at least % The Theory of Models, North Holland, Amsterdam a1965, pp. 121-131. [6] Fuhrken E.G.; Vaught R.L.: "Noncharacterizability of the Ordering of the Natural Numbers", American Mathematical Society 9^ (1962), p. 321. [7] Hanf, W. : Some Fundamental Problems.Concerning Languages With Infinitely Long Expressions, ;Doctoral Dissertation, University.of California, Berkeley, 1962, 95 pp. [8] Hanf, W.: "incompactness i n Languages with Infinitely Long Expressions", Fundamenta Mathematicae 53 (1963), pp. 309-324. [9] Hatcher, W.S.: Foundations of Mathematics, W.B. Saunders Philadelphia, 1968. [10] Henkin, L.: "Some Remarks on Infinitely Long Formulas", I n f i n i t i s t i c Methods, Pergamon Press, Warszawa, 1961, pp. 167-183. [11] Karp, C.: Languages With Expressions of Infinite Length, North Holland, Amsterdam, 1964. [12] Karp, C : "Finite-Quantier Equivalence", The Theory of Models, North Holland, Amsterdam, 1965, pp. 407-412. [13] Karp, C.: "An Algebraic Proof of the Barwise Compactness Theorem", Lecture Notes in Mathematics 72 (The Syntax and Semantics of Infinitary Languages), Springer-Verlag, Heidelberg, 1968, pp.. 80-95. 62. [14] Keisler, H.J.: "Finite Approximations of Infinitely Long Formulas", The Theory of Models, North Holland, Amsterdam, 1965, pp. 158-169. [15] Keisler, H.J.: "On The Quantifier 'there exist uncountably many'", American Mathematical Society Notices Vol 15 (1968), p. 654. [16] Keisler, H.J.: "Formulas With Linearly Ordered Quantifiers", Lecture Notes in Mathematics 72 (The Syntax and Semantics of Infinitary Languages), Springer-Verlag, Heidelberg, 1968, pp. 96-130. [17] Kopperman, R.: "The L - Theory of Hilbert Spaces.", Journal of Symbolic Logic 32 (1967) pp. 295-304. [18] Kreisel, C.: "Choice of Infinitary Languages by Means of Definability Criter i a ; Generalized Recursion Theory", Lecture Notes in Mathematics 72 (The Syntax and Semantics of Infinitary Languages), Springer-Verlag, Heidelberg, 1968, pp. 139-151. [19] Kreisel, C.; Krivine, J.L.: Elements of Mathematical Logic; Model Theory, North Holland, Amsterdam, 1967. [20] Lopez-Escobar, E.G.K.: "Remarks on an Infinitary Language with Constructive Formulas", Journal of Symbolic Logic 32 (1967), pp. 305-318. [21] Maehara, S.; Takeuti, G.: "A Formal System of Firs t Order Predicate Calculus With Infinitely Long Expressions "Journal of the Mathematical Society of Japan 13 (1961), pp. 357-370. [22] Mendelson, E.: "On Non-Standard Models for Number Theory", Essays on The Foundations of Mathematics, North Holland, Amsterdam, 1962, pp. 259-268. [23] Mendelson, E.: Introduction to Mathematical Logic, Van Nostrand, Princeton, 1964. [24] Mostowski, A.: "On a Generalization of Quantifiers", Fundamenta Mathematicae 44 (1957), pp. 12-36. [25] Mostowski, A.: "Quelques Observations Sur l'Usage Des Methodes Non Finitistes Dans La Meta - Mathematique:, Le Raisonnement en Mathematiques et en Sciences Experimentales, Editions de Centre National de l a Recherche Scientifique, Paris, 1958, pp. 19-32. [26] Robinson, A.: "Model Theory and Non-Standard Arithmetic", I n f i n i t i s t i c Methods, Pergamon Press, Warszawa, 1961, pp. 265-302. 63. [27] Robinson, A.: Introduction to Model Theory and the Methamathematics of Algebra, North Holland, Amsterdam, 1963. [28] Robinson, A.: Non-Scandard Analysis, North Holland, Amsterdam, 1966. [29] Scott, D.: "Logic With Denumerably Long Formulas and Finite Strings of Quantifiers", The Theory of Models, North Holland, Amsterdam, 1965, pp. 329-341. [30] Scott D.; Tarski, A.: "The Sentential Calculus with Infinitely Long Expressions", Colloquium Mathematicum 6 (1958), pp. 165-170. [31] Skolem, T: "Uber Die Nicht-Charakterisierbarkeit Der Zahlenreihe Mittels endlich Oder Abzahlbar Unendlich Vieler Aussagen Mit Ausschliesslich Zahlenvariablen" Fundamenta Mathematicae 23 (1934), pp. 150-161. [32] Tarski, A. : "Remarks on Predicate Logic With Infinitely Long Expressions", Colloquium Mathematicum 6 (1958), pp. 171-176. [33] Vaught, R.L.: "The Completeness of Logic With the Added Quantifier 'there are uncountably many'", Fundamenta Mathematicae 54 (1964), pp. 303-304.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some useful generalizations of first order languages
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some useful generalizations of first order languages Finlay, James Andrew 1971
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Some useful generalizations of first order languages |
Creator |
Finlay, James Andrew |
Publisher | University of British Columbia |
Date Issued | 1971 |
Description | We begin with a disucssion of some of the serious deficiencies of first order predicate languages. These include the non-characterizability by first order sentences of such common mathematical structures as the class of well-ordered sets, the class of finite sets, the class of Archimedean fields and the standard models of arithmetic and analysis. Two methods of generalizing first order predicate languages are then studied. The first approach is to allow for "expressions of infinite length"; the second method is the introduction of "generalized quantifiers." For the languages resulting from each approach, we consider to what extent such deficiencies as those mentioned above may be overcome and also to what extent some of the elementary model-theoretic and proof-theoretic theorems of first order logic may be generalized to these new languages. Among the languages with expressions of infinite length, we first consider the Lω₁ω languages which generalize first order languages by extending the recursive definition of a formula to allow countable conjunctions and disjunctions of formulas as formulas. It is shown that with the use of such languages we are able to describe categorically the standard model of arithmetic, the class of finite sets, the class of Archimedean fields and other common mathematical structures which cannot be characterized in first order languages. Generalizations of the Lowenheim-Skolem and completeness theorems of first order logic are given as well as a countable isomorphism theorem due to Dana Scott. We make use of a characterization of rank equivalence due to Carol Karp to demonstrate that neither the standard model of analysis nor the class of well-ordered sets may be described in any Lω₁ω -language. In fact, our argument indicates that these characterizations are not possible in any extension of a Lω₁ω - language which, for any infinite cardinal α , allows as formulas conjunctions and disjunctions of less than a formulas. This result leads us naturally to a consideration of the class of Lω₁ω - languages, any element of which is obtained from a Lω₁ω - language by modifying the rules for formula formation to allow not only denumerable conjunctions and disjunctions but also quantifications over denumerable sets of variables. (These ideas are made more precise in the text of the thesis.) The standard model of analysis and the class of well-ordered sets are each seen to be characterizable by single Lω₁ω - sentences. Other infinitary languages are also mentioned, including languages with infinitely long atomic formulas. Among the languages with generalized quantifiers we restrict ourselves to the L(Qα) - languages, where α is an ordinal, which are obtained from first order languages by adding a new quantifier symbol Qα to be read "there exist Ɲα... .” In addition to being able to characterize sets of various cardinalities, we give a categorical description of the standard model of arithmetic by a single L(Qօ) - sentence. Among the model-theoretic results possible are generalizations of the compactness theorem, Lŏs's theorem and the downward Lowenheim - Skolem theorem of first order logic. Finally, on the proof-theoretic side, we show that in the case α = 0 there exists no recursive axiomatization which yields a completeness result; in the case α = 1 , however, such an axiomatization is possible. |
Subject |
Programming languages (Electronic computers) Logic, Symbolic and mathematical |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-05-06 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080440 |
URI | http://hdl.handle.net/2429/34341 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1971_A6_7 F55.pdf [ 3.41MB ]
- Metadata
- JSON: 831-1.0080440.json
- JSON-LD: 831-1.0080440-ld.json
- RDF/XML (Pretty): 831-1.0080440-rdf.xml
- RDF/JSON: 831-1.0080440-rdf.json
- Turtle: 831-1.0080440-turtle.txt
- N-Triples: 831-1.0080440-rdf-ntriples.txt
- Original Record: 831-1.0080440-source.json
- Full Text
- 831-1.0080440-fulltext.txt
- Citation
- 831-1.0080440.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080440/manifest