Introduction to Model Games

For Nathan Carter's MA305H class.

An Model Game is a game played between two players, the Challenger and the Defender. The game helps us understand which sentences of QL are true in a particular model. (Recall that QL is the first-order language introduced in the textbook forallx in Lurch.)

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

To play now:

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:

(The Defender can read the universal quantifier ∀x as, "No matter what my opponent chooses for x," and the existential quantifier ∃x as, "I can find an x such that...")

When there are no more quantifiers left, it is easy to check to see if the statement is true or false, using the model and the values the players chose.
If the sentence is true, the Defender wins; he or she successfully defended the statement from attack. If it is false, the Challenger wins.

Example:

\(\forall x, \exists y, greater(x,y)\)

UD:     whole numbers
\(greater(x,y)\):     \(x\) is greater than \(y\)
(that is, \(\{(0,1),(1,2),(0,2),(-1,0),\ldots\}\), an infinite list)

The players might play this game as follows.

  1. Starting to read the sentence from the left, we come to \(\forall x\).
  2. Let's say that the Challenger chooses \(x=3\). Then the remainder of the sentence (after the first quantifier) now reads \(\exists y, greater(3,y)\), because we replaced \(x\) with 3.
  3. Continuing reading the sentence, we next come to \(\exists y\).
  4. The Defender is trying to make \(greater(x,y)\) true, or rather \(greater(3,y)\), which means "3 is greater than \(y\)." So the Defender chooses \(y=2\). Thus the remainder of the sentence now reads \(greater(3,2)\), because we replaced \(y\) with 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 \(greater(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.

If the Defender wins, that does not mean the statement is true in the model. Maybe the Challenger just played badly! Similarly, if the Challenger wins, the statement may still be true in the model. Maybe the Defender just played badly.

The statement is true in the model if the Defender has a winning strategy, that is, a procedure he or she can follow to always win. The statement is false in the model if the Challenger has a winning strategy. We will discuss in class how to describe winning strategies.