This node is part of the game proof of the Baire category theorem, and won't make any sense unless you're coming from there!

Suppose Bob is guaranteed a win when playing on any one of G1, G2, ... Let G=G1∪G2∪... be their union; we wish to show how Bob is guaranteed a win even when playing on all of G (recall that "larger" target sets G should help Alice, not Bob). To that end, we outline Bob's winning strategy for G.

On the first move, Alice has already played some bit sequence A1. At the very least, Bob must play to ensure that x won't be in G1, so Bob pretends he's just playing G1, and makes the appropriate response B1,1 to Alice's A1 when playing G1.

Alice responds with some sequence A2, and the position looks like 0. A1 B1,1 A2. So Bob first works out the appropriate response B2,1 to 0.A1 B1,1 A2 when playing G1, and then (since he doesn't want x to be in G2, either) the appropriate response B2,2 to 0.A1 B1,1 A2 B2,1 when playing G2 (note that this could have been Alice's first move when playing G2, so Bob's winning strategy has an appropriate response to it!). Bob then plays B2,1 B2,2.

Continuing, after Alice's n+1'th move, the position is

0. A1 B1,1 A2 B2,1 B2,2 A3 ... An Bn,1 Bn,2 ... Bn,n An+1,
and Bob must play. Alice's n+1'th move when playing G1 could have been Bn,2 ... Bn,n An+1, so Bob's winning strategy for G1 tells him to play some move Bn+1,1; now Bob pretends Alice's n'th move when playing G2 was Bn,3 ... Bn,n An+1 Bn+1,1, and his winning strategy for G2 tells him to play some Bn+1,2; Bob continues in this manner, letting Bn+1,k be the response his winning strategy for Gk tells him to play if Alice's move n+2-k when playing Gk had been Bn,k+1 ... Bn,n An+1 Bn+1,1 ... Bn+1,k-1. After getting the n+1 bit strings Bn+1,1, ..., Bn+1,n+1, Bob plays them all in sequence (still a finite digit string, so it's a legal move!).

Now consider the x that results from Bob's strategy. It cannot be in any Gk, since Bob has been following a line of play guaranteed (assuming Alice plays in a certain way, which includes some of Bob's responses) to keep x out of Gk. So x cannot be in any of Gk, hence Bob has a guaranteed win when playing the union of the Gk's.

Log in or register to write something here or to contact authors.