1. INTRODUCTION AND PRELIMINARIES We will be concerned here with a game invented by Fred Galvin, with some modifications of this game, and with a well-ordering defined in terms of these games. The original Galvin game is played on a tree T having no infinite branches. A white and a black pawn are placed initially at the root of T and players white and black move alternately, a move consisting of pushing either one of the pawns (but only one) from the node on which it sits to any immediate successor node, the player whose pawn first reaches a terminal node being declared the winner as in chess, white moves first. (Actually, Galvin's original formulation of the game was in terms of progressively finite directed graphs rather than branch-finite trees, but it is readily seen that this makes no difference.) Galvin showed by an elegant reduotio ad absurdum (Theorem 2.4) that white has a winning strategy for any such T, and he also exhibited the strategy explicitly in the case where T is finite (see 3.2 and 3.5). This left open the problem of explicitly describing such a strategy for infi- nite (but branch-finite) T. The rather complicated machinery necessary for solving this problem is developed in Chapters 3 and 4, and the strate- gy itself described in the proof of Theorem 4.13. Historically, our moti- vation for developing this machinery arose not only from the inherent interest in having an explicit description of the winning strategy, but also in order to prove that white still has a winning strategy in a variant of Galvin's game proposed by Laver, in which black has infinitely many pawns (see Definition 8.1). Subsequent to our proof of this fact, however, Martin gave a proof which did not rely on our explicit description of white's strategy, but used only methods reminiscent of Galvin's proof of Theorem 2.4 in turn, we simplified Martin's argument, yielding the result which appears here as Lemma 2.13, and allowing us to give the proof of Theorem 8.3 in its present form. It turns out that in each of the cases mentioned above, the proof shows that white has a strategy which is particularly nice in that white never has to move the black pawn except possibly immediately after black has moved it, so in some sense placing such restriction on white as part *Received by the editors September 8, 1983. Research supported in part by University of Colorado and Boettcher Founda- tion Graduate Fellowships and University of Calgary Post-Doctoral Fellow- ship. This paper is an expanded version of the author's Ph.D. thesis, written at the University of Colorado in 1982. 2 Dedicated to Cheryl Brower, Lise Cotter, and Anne Havard. 1
Previous Page Next Page