You are here

Independence-Friendly Logic: A Game-Theoretic Approach

Allen L. Mann, Gabriel Sandu and Merlijn Sevenster
Cambridge University Press
Publication Date: 
Number of Pages: 
London Mathematical Society Lecture Note Series 386
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Leon Harkleroad
, on

Dual Review of

  • Independence-Friendly Logic: A Game-Theoretic Approach, by Allen L. Mann, Gabriel Sandu and Merlijn Sevenster
  • Models and Games, by Jouro Väänänen

At first glance, mathematical logic and game theory might appear poles apart, the highly abstract in contrast to the concrete and applied. The two fields even reside in opposite ends of the MSC classification scheme, at 03 and 91, respectively. However, these areas have long interacted in a variety of ways, ranging from determinacy axioms in set theory, with roots in Banach-Mazur games, to the ties between games and computability theory explored in a recent book by Hearn and Demaine.

For a simple example of the kind of interaction that the two books under review treat (indeed, this example appears in both books), consider the epsilon-delta statement of continuity of a function. This can be turned into a game in which my opponent plays an epsilon, and I counter with a delta. In case my delta is appropriate for the epsilon, I win; otherwise, I lose.

The truth of the continuity statement then means that I have a winning strategy — regardless of my opponent’s choice, I can respond successfully. Falsity of the statement, i.e., discontinuity, means that my opponent can win with a suitable pick for epsilon. From such a viewpoint, the difference in quantifier order between continuity everywhere and uniform continuity (∀x∀ε∃δ vs. ∀ε∃δ∀x) corresponds to a difference between games in which my opponent has to make the x-move up front or gets to wait until after I play my delta.

Thus games may be used to investigate the truth of a statement within a given structure (model). Likewise, they may address the consistency of a statement — the existence of some model in which it is true — as well as the search, given two structures, for statements true in one but not in the other.

Väänänen’s book emphasizes these three flavors of games throughout. Ultimately, however, the main thrust lies in the model theory, with the game theory serving as a tool — highly valuable and frequently used, but still a tool and far from the only one. As the Preface states, Models and Games “can be used as a text for a course in model theory with a game- and set-theoretic bent.” Väänänen treats not only usual first-order logic, but also infinitary logics and generalized quantifiers.

Although Independence-Friendly Logic relegates games to its subtitle, it grants game theory a more equal partnership with logic than does Models and Games. Here the logic-games interplay itself becomes a focal point.

Independence-friendly logic was introduced by Hintikka and Sandu, with a precursor in the work of Henkin. This logic allows natural constructions not expressible in usual first-order logic, such as “for every x and ε, there exist y, dependent only on x, and δ, dependent only on ε, such that…” Game-theoretically, this corresponds to games of imperfect information, which call for probabilistic mixed strategies. Mann, Sandu, and Sevenster give an account of how this all plays out, so to speak, incorporating recent results of their own.

Of the two books, Independence-Friendly Logic requires less background and sets a more accessible tone. Its back-cover blurb describes it as “suitable for graduate students and advanced undergraduates who have taken a course on first-order logic,” while the blurb of Models and Games pitches that text as “ideal for graduate courses.” These assessments hit the mark fairly well, although the latter book betrays some inconsistency in the level at which it aims. For example, given that it treats forcing, Cohen subsets, and the like as topics already familiar to the reader, why does it see fit to include an exercise to “list the elements of {0,1,2}×{0,1}”? Note, however, that Väänänen does provide more than 550 exercises, while Mann, Sandu, and Sevenster’s book contains none. One other difference between the texts: Models and Games is more prone to minor inaccuracies, while Independence-Friendly Logic is fairly clean in that regard.

In recent years Leon Harkleroad has mostly concentrated on mathematical aspects of music, but he still enjoys revisiting his old stomping grounds of mathematical logic.

1. Introduction
2. Game theory
3. First-order logic
4. Independence-friendly (IF) logic
5. Properties of IF logic
6. Expressive power of IF logic
7. Probabilistic IF logic
8. Further topics