Logic and games -2


In the earlier post I mentioned about using games as a mean to prove/disprove expressibility of FO ( First Order Logic ).

Let us modify the game that we saw last time. Now each round consists of the following : The spoiler chooses one of the structure, chooses a subset of elements of that structure, duplicator has to do the same on the other structure. Now, the spoiler puts a pebble on one of the elements of the subset he/she has chosen and duplicator replies by playing it on the other structure. We have seen in the earlier post that it is impossible to distinguish between two graph A (two disconnected 5-cycle )and B ( one 10-cycle ) using only 3 pebbles. In fact, you will need log 2k pebbles to distinguish between two disconnected k-cycles and one 2k-cycle.

However, in this modified game, only 3 pebble suffices for the spoiler to win for any k. Here is the strategy for the spoiler to expose the difference between two structure.

Look at the figure. Spoiler first chooses one of the k-cycle in A and puts a pebble. Duplicator selects k-points in B ( 2k-cycle ) and puts a pebble. Now, the spoiler chooses the second k-cycle and puts a pebble and duplicator replies. For the third round, the spoiler chooses to play on B. It selects the shortest path between two fixed pebbles as subset, and puts a pebble right in the middle of it. Duplicator now has to play it in A ( two disconnected k-cycles ). Now, according to pigeonhole principle one of the k-cycle will have two pebbles. As shown in figure, (1,2) and (2,3) are in different cycles. Now on, spoiler will always play in graph B. it will choose a pair of pebbles belonging to different cycles in A, selects the pair having shortest path in graph B and puts the pebble right in the middle of it. The spoiler always maintain that it divides the path between pebbles images of which are in different cycles in the other graph. it is easy to see that, after some time, duplicator will have no answer to spoiler’s move ( isomorphism implied by pebbles can not be maintained in the other graph ).


This game gives rise to a logic which is strictly powerful than FO. However, Ramprasad mentions that due to a recent result one can always construct pairs of graphs that spoiler can not win for any k-pebble game. Also, this game has some connection to graph isomorphism but probably ramprasad will give details in the comment 😉


Similar games are designed to prove/disprove the expressibility of temporal logic, but may be some other time 🙂


— Saurabh Joshi


Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: