MATH EXPLORERS' CLUB Cornell Department of Mathematics 

Ehrenfeucht-Fraïssé games


Ehrenfeucht-Fraïssé games (in short EF games) represent an important tool in twentieth-century logic. From simple to very complex, these games are delightful to play among friends and equaly delightful for logicians, as they adapt fruitfully to a wide range of logics and structures.

We will start by describing how EF games are played in the familiar context of directed and undirected graphs. Lesson #3 discusses examples of EF games and winning strategies for the Spoiler and the Duplicator. Lesson #5 reformulates those strategies in terms of first order logic. Finally we present applications of EF games in proving inexpressibility results.

  1. Lecture #1: History of the Ehrenfeucht-Fraïssé games.
  2. Lecture #2: Description of the Ehrenfeucht-Fraïssé games.
  3. Lecture #3: Examples of EF games. Winning Strategies.
  4. Lecture #4: First order logic (FO) for graphs.
  5. Lecture #5: EF games and FO logic: Winning Strategies reconsidered.
  6. Lecture #6: EF games and FO logic: Expressive power of FO.
  7. References

This work was made possible due to a grant from the National Science Foundation.

Top Next lesson