2012 seminar talk: Racing Pawns, Internal Hyperarithmetic Comprehension, and the Law of the Excluded Middle

Talk held by Dan Turetsky (KGRC) at the KGRC seminar on 2012-10-11.


Galvin's "racing pawns" game involves two players using a tree as a chessboard and attempting to queen their pawn while interfering with their opponent's pawn. We show that the fact that the first player (“white”) wins every instance of this game (for countable trees) is equivalent to arithmetic transfinite recursion. Along the way we analyse the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.