×

Model-theoretic logics. (Parts A-C). (English) Zbl 0587.03001

Perspectives in Mathematical Logic. New York etc.: Springer-Verlag. XVIII, 893 p. DM 480.00 (1985).
The book consists of twenty chapters and a unified bibliography giving a substantial coverage of general model theory, the theory initiated by Mostowski’s study of cardinality quantifiers, by the work of Tarski, his colleagues and students on infinitary languages, and by Lindström’s work on generalized quantifiers and characterizations of first-order logic.
The genesis of the book is described by S. Feferman in his preface (pp. vii-x). The book is divided into six parts (A-F); each part is preceded by an introductory guide from which the reader can learn which chapters have a general character and which are mainly devoted to a special research interest. Grosso modo, the chapters in the first half of the book are meant to be accessible to any reader with a knowledge of basic first-order model theory, while the other chapters, rather than reporting on a relatively settled subject, present a picture of an evolving subject, bringing readers with adequate model theoretic or set theoretic background to the frontiers of research.
Part A is devoted to a presentation of the basic theory. In Chapter I (Model-theoretic logics: background and aims, pp. 3-23), J. Barwise provides motivation for the study of model theoretic logics by first arguing against the thesis according to which whatever is undefinable in first-order logic is automatically outside the scope of logic. Now, one of the aims of generalized model theory is to build logics similar to first-order logic to recover such notions as ”finite”, ”countable”, ”open set”, ”measure zero”, which are banned from logic by the above theory. Experience gained in the construction of new logics may, in turn, help to clarify the problem of what is meant by a natural logic, and what are the relations between various properties of logics. Thus for example, the logic \(L(Q_ 0)\) expressing the finite/infinite distinction has been gradually superseded by infinitary logics, for only the latter can express finiteness while at the same time being closed under implicit definability. To fully appreciate definability and other model theoretic properties one cannot restrict to the study of first-order logic, just as one cannot fully see the importance of continuity and differentiability by limiting attention to the polynomials. The author discusses the role of abstract model theory in characterizing first-order logic itself, and also in giving a better understanding of the relations between compactness, interpolation, Löwenheim-Skolem and other model theoretic properties.
Chapter II (Extended logics: the general framework, pp. 25-76) by H.-D. Ebbinghaus provides the general framework for the remaining chapters. After defining the basic closure properties of logics the author introduces several examples of logics occurring in the literature, with a discussion of their fundamental properties. For instance, using projective classes and reduction techniques a simple proof is given of the countable compactness of the logic \(L(Q_ 1)\) with the quantifier ”there are uncountably many”, as well as the compactness and axiomatizability of the logic with cofinality \(\omega\) quantifier. Lindström quantifiers are next introduced, and the back and forth characterization of elementary equivalence is generalized to all logics generated by monotone quantifiers: as an application, the author presents Keisler’s counterexample to the interpolation property of \(L(Q_ 1)\). The last three sections deal with compactness, definability, Löwenheim- Skolem properties and their variants.
Chapter III (Characterizing logics, pp. 77-120) by J. Flum deals with characterization theorems for logics. The prototype of such theorems, proved by Lindström in 1966, states that no proper extension of first-order logic \(L_{\omega \omega}\) can satisfy both the countable compactness and the Löwenheim-Skolem theorem. Using back and forth methods and projective classes, a number of variants of Lindström’s theorem are proved, showing that first-order logic is maximal with respect to other combinations of properties. Cardinality quantifiers, too, are abstractly characterized among all unary monotone quantifiers. In a final section, a general method is developed to obtain Lindström- like characterizations of logics for enriched structures, such as topological structures. This connects with work in Chapter XV.
Part B is concerned with finitary logics with additional quantifiers. Chapter IV (The quantifier ”There exist uncountably many” and some of its relatives, pp. 123-176) by M. Kaufmann investigates the quantifier \(Q_ 1\) and some of its relatives, such as the almost all quantifier aa, and Magidor-Malitz quantifiers. A main theme of the chapter is the development of methods extending Keisler’s completeness theorem for \(L(Q_ 1)\) to logics stronger than \(L(Q_ 1)\). To this purpose one essentially reduces the given logic to first-order logic in such a way that the necessary tools from first-order model theory can be applied. Fuhrken’s reduction method, together with weak models, is used to give a fairly unified treatment of all completeness theorems, in the first three sections of the chapter. Section 4 deals with filter quantifiers stronger than \(Q_ 1\), and culminates with the proof of completeness, countable compactness and omitting types of the logic with the aa quantifier. Section 5 deals with Magidor-Malitz logics and other related logics. Section 6 surveys definability properties of \(L(Q_ 1)\) and its extensions.
In Chapter V (Transfer theorems and their applications to logics, pp. 177-209), J. H. Schmerl deals with the problem of transferring results known about \(L(Q_{\alpha})\) to some other \(L(Q_{\beta})\), with particular reference to \(\alpha =1\) and to the properties of countable compactness and axiomatizability. Many results of this chapter depend on special set-theoretical assumptions. For instance, from GCH it follows that the axioms and rules that are complete for \(L(Q_ 1)\) are also complete for \(L(Q_{\beta +1})\) whenever \(\aleph_{\beta}\) is regular. The author includes many transfer theorems by Keisler, Chang, Fuhrken and R. B. Jensen, which are directly inspired by Vaught’s two- cardinal theorem. Models having canonical, internal proper elementary extensions of themselves are used to prove the Mac-Dowell-Specker-Shelah theorem. The author finally surveys cardinality interpretations of the Magidor-Malitz logic, and transfer theorems for the infinitary logic \(L_{\omega_ 1\omega}(Q_ 1).\)
In Chapter VI (Other quantifiers: an overview, pp. 211-233), the present reviewer surveys the properties and compares the expressive power of several logics with additional quantifiers that are outside the scope of Chapters IV and V. These include logics with partially ordered quantifiers, such as Henkin’s quantifier \(Q^ H\), similarity quantifiers, such as Härtig’s equicardinality quantifier I, as well as quantifiers whose underlying classes are structures equipped with equivalence relations, or with various kinds of orders. For instance, it is shown that \(L(Q^ H)\) and monadic second-order logic \(L^{mII}\) have equivalent \(\Delta\)-closures, and hence they have the same Löwenheim and Hanf numbers, and the same set of valid sentences (up to recursive equivalence). L(I) is similarly related to \(L^{mII}\), assuming constructibility. On the other hand it is shown that \(L(Q_ 0)\leq L(I)\leq L(Q^ H)\), and the inclusions are strict. The chapter also discusses general properties of large classes of quantifiers, such as isomorphism quantifiers, monadic, binary, securable, and free-variable quantifiers.
Chapter VII (Decidability and quantifier elimination, pp. 235-268) by A. Baudisch, D. Seese, P. Tuschik and M. Weese is an introduction to decidability of theories with extra quantifiers. The authors concentrate attention on the Magidor-Malitz, Härtig and aa quantifiers. Three main decision techniques are presented: quantifier elimination, interpretations, and dense systems. These are well known methods from first-order model theory, which turn out to have efficient generalizations in the field of strong logics. Application of each procedure is given to theories of modules and abelian groups, well- order, linear order, boolean algebras, in each of the above mentioned logics. Much of the material presented in this chapter is related to the authors’ text on decidability and generalized quantifiers, where the reader may find further examples and details.
Part C is devoted to languages with infinitely long formulas. Chapter VIII (\({\mathcal L}_{\omega_ 1\omega}\) and admissible fragments, pp. 271- 316) by M. Nadel presents \(L_{\omega_ 1\omega}\), its admissible fragments, and its extensions by new propositional connectives. The chapter begins with the original motivations for studying infinitary languages, and covers many of the developments that have taken place since H. J. Keisler’s book: Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers (1971; Zbl 0222.02064). In the first part, back and forth methods, consistency properties and Scott sentences are introduced, and the basic facts about \(L_{\omega_ 1\omega}\) are proved. The second part deals with admissible sets, Barwise completeness and compactness, interpolation, Hanf numbers, Löwenheim-Skolem results, and recursively saturated models. The final section discusses extensions by propositional connectives, showing the difficulties of the program of characterizing \(L_{\omega_ 1\omega}\) by its model-theoretic properties.
Chapter IX (Larger infinitary languages, pp. 317-363) by M. A. Dickmann is an introduction to the logics \(L_{\kappa \lambda}\), and presents the developments on the field since the author’s book: Large infinitary languages. Model theory (1975; Zbl 0324.02010). Examples and counterexamples are initially presented to illustrate the expressive power of these logics; some of the subsequent model theoretic results are elaborations from these examples. Topics discussed in the chapter include negative results on several forms of compactness and definability, positive results on preservation of infinitary equivalence by sums and products, Löwenheim-Skolem theorems, Hanf numbers. The chapter concludes with a fairly general treatment of partial isomorphisms and the infinitary back and forth method, stressing functoriality under reduced products, and applications to real closed fields.
Chapter X (Game quantification, pp. 365-421) by Ph. G. Kolaitis is devoted to game quantification. The first section presents the basic definitions and results on infinite strings of quantifiers \((Q_ 0x_ 0,Q_ 1x_ 1,...)\), where \(Q_ i\in \{\exists,\forall \}\) for all i. The interpretation of such strings is via two-person infinite games with perfect information. The Gale-Stewart theorem is proved at the outset. The interaction between game quantification and global definability theory is the subject of Section 2. Here the main result is Svenonius’ theorem, from which it follows that game quantifier formulas can be approximated by \(L_{\omega_ 1\omega}\) formulas, thus allowing one to apply the rich model theory of the latter logic (see Chapter VIII) to analyze \(\Sigma^ 1_ 1\) and \(\Pi^ 1_ 1\) formulas. A proof of Vaught’s covering theorem is outlined. Section 3 contains an overview of model theoretic applications of the absoluteness of game logic. Section 4 surveys the relationship between game quantification, generalized recursion theory, and descriptive set theory, beginning with Moschovakis’ absolute version of the Svenonius theorem.
Chapter XI (Applications to algebra, pp. 423-441) by P. C. Eklof presents several applications of infinitary logics to algebra. The first two sections deal with results that are expressible in purely algebraic terms, e.g., the construction by Macintyre and Shelah of nonisomorphic universal locally finite groups of the same cardinality, and Baldwin’s application of \(L_{\omega_ 1\omega}\) to count the number of subdirectly irreducible algebras in a variety. In the remaining sections, logical notions are also occurring in the statement of the results. A formalization of Lefschetz’s heuristic principle in algebraic geometry is given using the back and forth characterization of \(L_{\infty \omega}\) developed in Chapter IX. Further topics include a study of the algebraic significance of \(L_{\lambda \omega}\)-equivalence of abelian groups, a characterization of the algebras in a variety which are \(L_{\infty \kappa}\)-equivalent to a free algebra, and Hodges’ formalization of the notion of effective algebraic construction.
[For parts D-F see the review below (Zbl 0587.03002).].
Reviewer: D.Mundici

MSC:

03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03C70 Logic on admissible sets
03C95 Abstract model theory
03C80 Logic with extra quantifiers and operators
03C52 Properties of classes of models
03-06 Proceedings, conferences, collections, etc. pertaining to mathematical logic and foundations
03B25 Decidability of theories and sets of sentences
03C40 Interpolation, preservation, definability
03B15 Higher-order logic; type theory (MSC2010)
03B48 Probability and inductive logic
03C60 Model-theoretic algebra
03C85 Second- and higher-order model theory