## Logic and Games

Dear All,

This post is a side effect of a fruitful discussion with Ramprasad, which also refreshed my memories about a course “Logic in Computer science”.

An interesting way to capture the power of First Order logic is in terms of Ehrenfeucht–Fraïssé games. Essentially, it is a two player game. Given two different structures A and B and set of k pebbles the game is played as follows. Spoiler tries to show that A and B are indeed different where as Duplicator will try to hide this fact. Each of them take turn. In every round, spoiler will choose one of the two structure and put a pebble on one of the element of that structure. Duplicator puts a pebble on the other structure so that the two substructures induced by pebbles are isomorphic with respect to the relations specified.

For example, take two graphs A and B. A consists of two disconnected 5-cycles and B be a 10-cycle. One can see that it is impossible to distinguish these two graphs if only 3 pebbles are given. Try the exercise with 4 pebbles and the spoiler wins irrespective of the number of rounds played. Similarly, structures could be bit strings. Given P pebbles, one can always construct two bit strings of length greater than $2^b + 2$ such that one of then has odd parity and another one has even parity yet the spoiler has no way of winning. In general, parity checking or even st-connectivity ( whether there is a path from s to t in a graph ) can not be expressed in any first order logic. Here, pebbles corresponds to variables in the FO ( first order ) formula and a round corresponds to the quantifier depth of a formula. Hence, when we say duplicator wins in 5 pebble 10 round game,  is equivalent of saying that a formula which uses 5 variables and 10 quantifier depth can not express the property in question. When, the rounds are unbounded, it means that FO can not distinguish.

More interesting details/references can be found from wikipedia link given in this post. Thanks to Dr Anil Seth for introducing me to such a wonderful world of logic.

— Saurabh Joshi