[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