Models and Games

Description

This gentle introduction to logic and model theory is based on a systematic use of three important games in logic: the semantic game; the Ehrenfeucht-Fraïssé game; and the model existence game. The third game has not been isolated in the literature before but it underlies the concepts of Beth tableaux and consistency properties. Jouko Väänänen shows that these games are closely related and in turn govern the three interrelated concepts of logic: truth, elementary equivalence and proof. All three methods are developed not only for first order logic but also for infinitary logic and generalized quantifiers. Along the way, the author also proves completeness theorems for many logics, including the cofinality quantifier logic of Shelah, a fully compact extension of first order logic. With over 500 exercises this book is ideal for graduate courses, covering the basic material as well as more advanced applications. Cover......Page 1 Half-title......Page 3 Series-title......Page 4 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Preface......Page 13 1 Introduction......Page 15 2.1 Finite Sequences......Page 17 Finite Sets......Page 18 2.2 Equipollence......Page 19 2.3 Countable sets......Page 20 2.4 Ordinals......Page 21 2.5 Cardinals......Page 23 2.6 Axiom of Choice......Page 24 Exercises......Page 25 A Preliminary Example: Nim......Page 28 Games – a more general formulation......Page 30 3.3 The Mathematical Concept of Game......Page 34 3.4 Game Positions......Page 35 3.5 Infinite Games......Page 38 Exercises......Page 42 4.2 First-Order Language of Graphs......Page 49 4.3 The Ehrenfeucht–Fraïssé Game on Graphs......Page 52 4.4 Ehrenfeucht–Fraïssé Games and Elementary Equivalence......Page 57 4.5 Historical Remarks and References......Page 62 Exercises......Page 63 5.1 Introduction......Page 67 5.2 Basic Concepts......Page 68 5.3 Substructures......Page 76 5.4 Back-and-Forth Sets......Page 77 5.5 The Ehrenfeucht–Fraïssé Game......Page 79 5.6 Back-and-Forth Sequences......Page 83 Exercises......Page 85 6.2 Basic Concepts......Page 93 6.3 Characterizing Elementary Equivalence......Page 95 6.4 The Löwenheim–Skolem Theorem......Page 99 6.5 The Semantic Game......Page 107 6.6 The Model Existence Game......Page 112 6.7 Applications......Page 116 6.8 Interpolation......Page 121 6.9 Uncountable Vocabularies......Page 127 6.10 Ultraproducts......Page 133 6.11 Historical Remarks and References......Page 139 Exercises......Page 140 7.2 Preliminary Examples......Page 153 7.3 The Dynamic Ehrenfeucht–Fraïssé Game......Page 158 7.4 Syntax and Semantics of Infinitary Logic......Page 171 7.5 Historical Remarks and References......Page 184 Exercises......Page 185 8.2 Löwenheim–Skolem Theorem for L…......Page 190 8.3 Model Theory of L…......Page 193 8.4 Large Models......Page 198 8.5 Model Theory of L…......Page 205 Closed game formulas......Page 215 Closed Vaught formulas......Page 223 8.7 Historical Remarks and References......Page 236 Exercises......Page 237 9.2 Infinite Quantifier Logic......Page 242 9.3 The Transfinite Ehrenfeucht–Fraïssé Game......Page 263 9.4 A Quasi-Order of Partially Ordered Sets......Page 268 9.5 The Transfinite Dynamic Ehrenfeucht–Fraïssé Game......Page 272 9.6 Topology of Uncountable Models......Page 284 9.7 Historical Remarks and References......Page 289 Exercises......Page 292 10.1 Introduction......Page 297 10.2 Generalized Quantifiers......Page 298 10.3 The Ehrenfeucht–Fraïssé Game of Q......Page 310 10.4 First-Order Logic with a Generalized Quantifier......Page 321 10.5 Ultraproducts and Generalized Quantifiers......Page 326 10.6 Axioms for Generalized Quantifiers......Page 328 10.7 The Cofinality Quantifier......Page 347 10.8 Historical Remarks and References......Page 356 Exercises......Page 357 Index......Page 367