Game semantics for first-order logic

353 Views Asked by At

Here I've read about the game semantics for logical statements with quantifiers. It gives a good intuition about why $\forall x\exists y\,.\,P(x, y)$ means something different than $\exists y\forall x\,.\,P(x, y)$. The former statement means that one can always win this game: a devil gives you a $x$, and then you have to give a $y$ (that can depend on the $x$ given by the devil) with $P(x, y)$. Now, the latter statement is true if and only if one can win a slightly different game: first, one has to specify the $y$, and then the devil gives you a $x$.

I have a view questions concerning this game semantics for logical statements with quantifiers:

  1. Analogously to the above definition of game semantics for statements of the form $\forall x\exists y\,.\,P(x, y)$ or $\exists y\forall x\,.\,P(x, y)$ I can imagine how to define the game semantics for statements of the form $$Q_1xQ_2yQ_3z\dots\,.\, P(x, y, z, \dots),$$ where $Q_i\in\{\forall, \exists\}$ for all $i$ and $P$ is quantifier-free. But how does one define the game semantics for other statements like $\forall x\,.\,(\forall y \,.\,P(x, y))\lor (\exists z\,.\,Q(x, z))$?

  2. One can one prove that for each quantifier statement $\varphi$ in first-order logic, either $\forall$ has a winning strategy or $\exists$ has a winning strategy?

1

There are 1 best solutions below

1
On BEST ANSWER

You can treat $\lor$ as an existential quantifier over $2$ options: the left or right argument. So the devil gets to choose the left or right argument of the $\lor$ and the game continues.

Similarly, you can treat $\land$ as a universal quantifier over $2$ options. There you get to choose the left or right argument.

Finally, $\lnot$ switches the roles of the players.

The fact that one of the players has a winning strategy is just a particular instance of the fact that every finite deterministic two-player win/loss/draw game with perfect information has a winning or drawing strategy for one of the players.