zbMATH — the first resource for mathematics

Models and games. (English) Zbl 1233.03001
Cambridge Studies in Advanced Mathematics 132. Cambridge: Cambridge University Press (ISBN 978-0-521-51812-3/hbk). xi, 367 p. (2011).
To verify the elementary equivalence of relational structures, R. Fraïssé introduced the back-and-forth method in his thesis (see [“Sur quelques classifications des systèmes de rélations”, Publ. Sci. Univ. Alger, Sér. A 1, 35–182 (1955; Zbl 0068.24302)]). In his paper [“Sur quelques classifications des rélations, basées sur des isomorphismes restreints. II: Application aux rélations d’ordre, et construction d’exemples montrant que ces classifications sont distinctes”, Publ. Sci. Univ. Alger, Sér. A 2, 273–295 (1957; Zbl 0126.01401)], he gave a characterization of elementary equivalence in terms of back-and-forth sequences. To characterize first-order logic, P. Lindström used the back-and-forth method in his paper [“On extensions of elementary logic”, Theoria 35, 1–11 (1969; Zbl 0206.27202)]. The back-and-forth method was reformulated in game-theoretic terms by A. Ehrenfeucht in his paper [“An application of games to the completeness problem for formalized theories”, Fundam. Math. 49, 129–141 (1961; Zbl 0096.24303)]. The resulting game-theoretic artifact, now known as “Ehrenfeucht-Fraïssé games”, or “back-and-forth games”, is very flexible and turns out to be applicable in classical as well as in finite model theory, with further applications to Mostowski-Lindström quantifiers and infinitary languages.
This book provides a unified account of these topics. The first chapters are devoted to combinatorial, game-theoretic and model-theoretic prerequisites. As shown in Chapter 6, models constructed by games yield a unifying tool to prove several basic results of first-order logic, such as the Löwenheim-Skolem, compactness, Craig interpolation, and Beth definability theorems. Chapters 7–9 are devoted to applications to infinitary languages. The final Chapter 10 is devoted to games for Mostowski-Lindström quantifiers. Completeness theorems are proved for various logics. Several exercises of varying difficulty are included at the end of each section.
The book can be used for reference purposes as well as for teaching and self-study at the graduate level. It is a welcome addition to the literature on game-theoretic model-theory.

03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03Cxx Model theory
91A80 Applications of game theory