Why are games so fascinating and pervasive that they gain the attention not only of computer scientists, philosophers, economists, and social scientists but also, as in the case of this book, of logicians and mathematicians?
Perhaps an example helps to illuminate the way from game-playing to pure mathematics. The board game of checkers has about 5 ¿ 1020 possible positions, and the task of solving the game in the sense of determining whether any player has a winning strategy is frightening. In 2007, after 18 years of continuous efforts by dozens of computers working with sophisticated artificial intelligence techniques, a team of eight scientists announced that perfect play by both sides leads to a draw: the most skilled player can only hope to avoid making a mistake that leads to a loss [1].
In 1913, Ernst Zermelo, one of the developers of Zermelo-Fraenkel (ZF) axiomatic set theory, proved by set-theoretical means that each finite two-player zero-sum game--a game with two players in which each player’s gain (or loss) is exactly balanced by the losses (or gains) of the other player--is determined: one of the two players has a winning (or better, a non-losing) strategy.
Zermelo’s combinatorial reasoning on games was probably the opening link between games and mathematical logic, generalized to infinite games in 1953 by David Gale and Frank M. Stewart. Determinacy of arbitrary games is a deep issue, connected to the foundations of mathematics. In 1962, Jan Mycielski and Hugo Steinhaus proposed what is called the full axiom of determinacy (AD), meaning that every set of real numbers is determined. It turns out that AD contradicts the axiom of choice and thus constitutes a principle that cannot be proved in ZF.
In this sense, games constitute a subject in mathematical logic, having been studied by great names such as J. Kemeny, P. Lorenzen, J. C. C. McKinsey, J. von Neumann, W. Quine, J. Robinson, and L. Henkin. However, in philosophical logic, Aristotle had already emphasized the role of games in connection with debate and argumentation.
As a mathematical subject, game theory has direct applications in economics and the social sciences--to a point where at least 12 Nobel laureates can be classified in the area of game theory, including John Forbes Nash, who proved in 1951 the existence of a Nash equilibrium for any game with a finite set of actions.
But this book has a more specific motivation in sight: it intends to study games in three different scenarios, connecting them by means of what it calls the “strategic balance of logic.” The first scenario involves semantic games, in which games can be used to determine the truth of a given sentence in a given model. The second scenario involves the model-existence games, in which the consistency of a theory (in the sense of non-contradictoriness, that is, the impossibility of deriving a contradiction) is at issue. The third comprehends the Ehrenfeucht-Fräissé games, in which games can be used to separate a model from another by finding a property that is true in the former model but false in the latter.
The three kinds of games are essentially variants of just one basic game, which arises from the understanding of the quantifiers. So it is the nature of quantifiers in first-order logic, in infinitary logic, and in logic with generalized quantifiers that sustains the interest of games for model theory. Quantifiers have natural game semantics and are closer in spirit (although mathematically much more elaborate) to the dialogue games studied and played by philosophers since Aristotle.
The first four chapters (“Introduction,” “Preliminaries and Notation,” “Games,” and “Graphs”) are really gentle introductions to the basics of set theory and introductory concepts of games and graphs.
Chapter 5, “Models,” is a bit more demanding, as it introduces the essentials of model theory, wholly fundamental in logic. Chapter 6, “First Order Logic,” defines the basic concepts of first-order language, which the author considers to be of primary importance--strong enough to express relevant concepts and facts, and still weak and flexible enough to permit powerful constructions. A special semantic game can express the truth of a first-order sentence in a structure, and this game is studied in detail. The model existence game (MEG), MEG (T, L) for a set T of L-sentences, is also defined, and it is proved that the central model existence theorem of first-order logic corresponds to a winning strategy in MEG (T, L).
Chapter 7, “Infinitary Logic,” introduces the dynamics games in the sense that it is possible for a player to change the length of the game (whether finite or infinite) while playing it. This leads to the dynamic Ehrenfeucht-Fräissé games, several versions of which are studied in this chapter. Chapter 8, “Model Theory of Infinitary Logic,” studies logics in which the model existence theorem fails in general and in which some of its prized consequences, such as the interpolation lemma, are lost. The notion of game quantifiers is then introduced, which permits attaining the covering theorem, a kind of abstract version of the interpolation theorem.
Chapter 9, “Stronger Infinitary Logic,” focuses on logics in which the truth predicate is not absolute; consequently, the completeness theorem, valid for first-order logic, cannot be attained. This apparent weakness, however, uncovers a great degree of flexibility, as the underlying logic can express deeper properties of models such as uncountability and completeness of a separable order, among other properties.
Finally, chapter 10, “Generalized Quantifiers,” investigates the model theory of languages endowed with new logical operations called generalized quantifiers. These quantifiers add extra power to logic, since first-order logic--with its candid quantifiers “for all” and “there exists”--is not able to express notions such as “there exists infinitely many elements such that...” or “there exists uncountably many elements such that....” The generalized quantifiers add precisely this expressive power to logic. Even if restricted to finite models, first-order logic is not able to express “there exists an even number of elements such that....” There are several generalized quantifiers, such as the Magidor-Malitz quantifiers, the H¿rtig quantifier, and the more complicated cofinality quantifier (“a linear order has cofinality ω”), and the quantifier for stationary logic (“there is a closed and unbounded system of countable sets”). The proof of the completeness theorem for the quantifier “there exists uncountably many elements such that...” is rather involved and treated in detail.
Each chapter is followed by a section of “Historical Remarks and References” and by a good number of exercises, some of them quite sophisticated.
This is a very valuable book, written by a highly competent logician and mathematician who has himself contributed to the field. Parts of it (roughly, chapters 1 to 7) can be used in an introductory course in model theory with a game-theoretical flavor. The last two or three chapters, however, will require a bit more mathematical bravery, but the effort pays off.
