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 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

### Like this:

Like Loading...

*Related*

Tags: first order logic, logic, logic games, math

This entry was posted on November 18, 2010 at 10:49 am and is filed under math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

November 20, 2010 at 12:19 pm |

[…] Me, Myself and Mathematics Saurabh Joshi’s Blog about math, algorithms, theorems, puzzles …. « Logic and Games […]