Introduction to EF Games

For Nathan Carter's MA305H class, Fall 2008.

An Ehrenfeucht-Fraïssé Game is a game played between two players, the Challenger and the Defender. The game helps us understand which sentences of QL are tautologies. (Recall that QL is the first-order language introduced in P.D. Magnus's textbook forallx.)

Each statement of QL is a game that can be played.

  • The Defender tries to defend the statement, that is, tries to make it be true.
  • The Challenger tries to oppose the statement, that is, tries to make it be false.

To play now:

See any of the following pages to play EF Games now online. Or read on for detailed directions.

Here is how they play:

The two players do not take turns. Rather, we read through the statement from left to right, and play as follows:

  • Whenever a universal quantifier like ∀x is read, the Challenger gets to choose the value of x.
  • Whenever an existential quantifier like ∃y is read, the Defender gets to choose the value of y.

When there are no more quantifiers left, it is easy to check to see if the statement is true or false, using the symbolization key and the values the players chose.
If the sentence is true, the Defender wins. If it is false, the Challenger wins.

Example:

∀x ∃y Gxy

UD: whole numbers
Gxy: x is greater than y

The players might play this game as follows.

  1. Starting to read the sentence from the left, we come to ∀x.
  2. Let's say that the Challenger chooses x = 3.
  3. Continuing reading the sentence, we next come to ∃y.
  4. The Defender is trying to make Gxy true, which now means G3y, or "3 is greater than y." So the Defender chooses y = 2.
  5. We read through the rest of the sentence without finding any more quantifiers, so we can now determine who wins.
  6. The quantifiers gone, we have G 3 2, or "3 is greater than 2," according to the symbolization key. Obviously this is true, so the Defender wins.

Notes:

If a statement has only universal quantifiers in it, then the Defender never gets to play; the Challenger makes all the moves. But of course the Defender can still win, if the sentence comes out true.

Similarly, if a sentence has only existential quantifiers in it, the Challenger never gets to play, but may still win if the Defender's choices result in a false statement in the end.

This page does not describe how EF Games relate to which sentences of QL are tautologies; we will discuss that in class, or you can read about it online..