Has every sentence in first-order logic a gaming metaphor?

125 Views Asked by At

In Terence Tao's book Analysis 1 (see sample chapters), he explains quantifiers through so-called gaming metaphors – here an example (for $\forall\exists$)

To continue the gaming metaphor, suppose you play a game where your opponent first picks a positive number x, and then you pick a positive number y. You win the game if y 2 = x. If you can always win the game regardless of what your opponent does, then you have proven that for every positive x, there exists a positive y such that y 2 = x.

I figured out that one can imagine a $\exists\forall$ sentence, say $\exists x\forall y: P(x, y)$, also a gaming metaphor: I choose an $x$, then my oponent chooses any $y$; I have won iff $P(x, y)$. If I can always win this game with a fixed $x$, then the sentence $\exists x\forall y: P(x, y)$ is true.

Has every sentence in first-order logic a gaming metaphor?

I gave two examples: $\forall\exists$ and $\exists\forall$ – but there are so many other combinations of these quantifiers, for example $\exists\forall \exists\forall\exists$. It's hard for me to find a corresponding gaming metaphor for these types of sentences.

2

There are 2 best solutions below

0
On

Yes, imagine there are two players — call them $\exists$ and $\forall.$

Put the sentence into prenex normal form: first all the quantifiers (the prefix part), followed by a part without any quantifiers at all (the matrix part).

The two players make moves in the order specified by the quantifiers. Each move is simply a value for the indicated variable. So, for instance, if the first quantifier is $\exists x,$ then the first move is made by player $\exists$ and the move itself is a choice of a value for $x.$

After all the moves are made, player $\exists$ wins if the matrix (the non-quantifier part, after all the quantifiers) is true for the chosen values of the variables; otherwise, player $\forall$ wins.

Then the sentence is true iff there's a winning strategy for player $\exists,$ and the sentence is false iff there's a winning strategy for player $\forall.$

0
On