[FOM] generalizing results to higher quantifier complexity

Curtis Franks cfranks at uci.edu
Sat Jan 29 19:28:59 EST 2005


I am studying Pudlak's manuscript "Consistency and Games--In search of 
New Combinatorial Principles". It is an interesting essay from several 
angles, and I would recomend it especially for persons interested in 
"mathematical" incompletenesses:

http://www.math.cas.cz/~pudlak/moje-bib.html

I have a question about a comment Pudlak makes in passing. It concerns 
general forms for Alice (Eloise) strategies for Herbrand disjunctions. 
(In the essay these are match strategies for simultaneous games with a 
match win for Eloise in case she wins on at least one board).

Pudlak points out that general forms exist in the case of matches 
defined by AEA formulae and AEAE formulae, but not for EAEA and higher 
complexity formulae. The reason is clear to anyone with experience 
playing chess against a computer program with a take-back-move button: 
In the AEAE case Eloise opens depending on Bob's (Abelard's) open and 
also on her knowledge of his reply to her opening on all the previous 
boards. Then she postpones repling on any board until after Abelard has 
replied to all her opening moves. In this case we can say that she is 
playing with the greatest possible about of information at every step, 
so the schematic disjunction Pudlak gives is fully general. In the EAEA 
case Eloise could play similarly. Her open on board i should be informed 
by Abelard's replies on all boards 1 thru i-1. Then she could again 
delay all her replies until Abelard has opened on every board, gleaning 
as much information from Abelard's openings as possible. However, this 
keeps potentially valuable information from Eloise on her openings. If 
she postponed opening on board i until Abelard not only had opened on 
all boards 1 thru i-1 but also had replied to some of her replies on 
those boards, then she would have a better informed opening on board i. 
But this, of course, at the cost of having replied on some boards 1 thru 
i-1 with less information than in the earlier case. So there is no ideal 
order for her moves, at least independent of the details of the game 
(the quantifier free matrix) being played on each board. This means 
there is no general schematic disjunction to describe the match and 
Eloise' strategy.

Pudlak comments that "this is the traditional stumbling block to the 
attmepts to generalize results to longer quantifier prefixes." Can 
anyone illuminate this remark?

Thanks.
Curtis Franks
cfranks at uci.edu



More information about the FOM mailing list