By the end of the previous post, I had said what a Borel subset of was, and what a determined subset was. Martin’s theorem is the statement that all Borel sets are determined.
I also commented that an intersection of two determined sets does not have to be determined, which suggests that in order to prove that all Borel sets are determined, we will need to find a clever inductive hypothesis. This hypothesis should be of the form, “All Borel sets of index less than have property P,” where having property P implies that you are determined, and it is also preserved when you take countable intersections and unions.
Since the property of being determined is quite a strange property, it seems rather unlikely that we will be able to find a much simpler property that does the job. So it is natural to look for a property that is itself related to games and determinacy. But what might such a property be?
I have not come anywhere near the level of understanding where I can make the next remark not seem to be a slight jump — that is, in some sense the “obvious” thing to think. However, I think that once one has seen it, it is a fairly natural jump. The idea is to prove that Borel games are determined by showing that they can be “lifted” to simpler games where we know how to prove determinacy. With that vague plan in the back of our minds, let us think about how determinacy of one game could imply determinacy of another.
Guess and adjust: a technique for finding non-obvious objects in mathematics
I should warn anyone who is reading this, that most of the post is going to be a bit of a mess, and I will end up covering very little ground. If this bothers you, then you might like to skim it and wait for the third post, where the presentation is more conventional. What I could do at this point is look at an account of the proof on the internet, copy out the correct, rather complicated definition of “lifting”, and go through the somewhat complicated verification that it works. However, I also want to give some idea of why the definition is as it is. More precisely, I want to show how certain aspects of it can be thought of as arising from the application of a very general technique for constructing mathematical objects with certain properties. (In this case, the object I’m referring to is the method of “lifting” one game to another, and the properties are basically that the method should allow us to deduce the determinacy of the original game from the determinacy of the lifted game.)
One technique for finding mathematical objects with certain properties is pure guesswork: you just keep trying things until you chance on one that does the job.
Sometimes — and particularly if you know that the object must belong to some class of highly structured objects that you know to be small — this approach is a good one. But often it isn’t at all good: there are just too many things to try and the conditions are too complicated for it to be realistic to hope to chance on a construction that works.
A more systematic approach is to think of the task as something a bit like solving an equation. If you need to find a number such that , you don’t guess, but instead you systematically simplify the conditions. You say to yourself, “Well, will have to be 25, but in that case we know that is .” In this case, you have worked out what the object is (or rather, what all possibilities for the object are).
But often neither of these approaches is easy to make work. For example, sometimes the conditions do not come anywhere near to specifying your object uniquely. Then you need to do things like adding extra conditions to pin them down more (hoping as you do so that you don’t end up with an inconsistent set of conditions). Typically, these extra conditions take the form of making various things as simple and elegant as they can be.
Sometimes even adding conditions doesn’t help enough to make the problem tractable. In that case, another technique can be very useful, which I like to call guess and adjust. (I’m sure someone else — Polya perhaps — has already named it.) The idea is that you go ahead and make a guess and start trying to prove that it works. Almost certainly it doesn’t, but when it doesn’t, instead of throwing your guess out and starting all over again, you look at what has gone wrong and try to adjust your original guess so that the thing that went wrong no longer goes wrong. Often the original guess will come to seem rather naive — you had a simple approach that you come to see fails for an obvious reason, but you can find a related, more complicated approach that doesn’t fail for that reason. The hope is that after a process of successive approximation, you will end up with a definition that is as simple as it can be, given that it does the job it is supposed to do.
I think most mathematicians apply guess-and-adjust instinctively rather than consciously thinking of it as a technique. Certainly, that was at one time the case for me: perhaps it wasn’t completely unconscious, but neither would I say to myself, “Now I’m in guess-and-adjust mode.” These days I find it quite helpful to be fully aware of what I’m doing when I use it.
The mess in the rest of this post is an account of my guessing and adjusting. Of course, I haven’t proved the result for myself. What I did was skimmed through the proof, forgot quite a lot of it, missed some important details, and then tried to reconstruct it. From time to time I would get stuck and return to existing accounts of the proof for hints. What you get below is a rough account of that process, except that I haven’t written it as a diary of my own thoughts (so instead of saying, “Let me try this … oh damn, it doesn’t work,” I say something more like, “A reasonable thing to try might be this … ah, it doesn’t work,”) and haven’t specified when I went back for hints (though you may be able to guess with reasonable accuracy).
With all that said, let us return to the question of how we might deduce the determinacy of one game from the determinacy of another, simpler one.
Using one game to help play another game
Imagine first that Player I and Player II are playing a game , and that Player I has a winning strategy for a different game . Under what circumstances would this provide Player I with a winning strategy for ? (I am asking for a reasonably simple sufficient condition rather than a complete characterization.)
A natural way to use is to play a game of on the side and use the moves of to choose moves for . How would this work? Well, one thing we would need is a map from positions to positions. Let me write for the set of all possible positions in a game and let be the map that gives us a position whenever we’ve got a position. Let us also write for the subset of that Player I is trying to reach and Player II is trying to avoid.
If Player I has a winning strategy for , then she will need the initial position of to map to the initial position of . Then she can play the move that dictates and can make the corresponding move in . What is this corresponding move? It is the move that turns the initial position into of the position reached in . But this isn’t obviously a valid move in , so we had better add that as a requirement. More formally, if Player I can make a valid move from position to position in game , then the move from position to position in game should be a valid move as well.
Now let’s consider what happens when Player II makes his first move. This will of course be a move in game — Player I can’t oblige him to make a move — but Player I can continue to use game for guidance if she can interpret Player II’s move as a move in game . For that, a sensible sufficient condition is that there should be a map from to such that valid moves map to valid moves in the same sense as in the previous paragraph.
If we have these conditions, then Player I can use the following strategy to play the game . Whenever it is her turn, she converts the current position into the position , plays the move dictated by , and converts the resulting position into the position .
Of course, we are looking for more than just a way of turning strategies into strategies: we want winning strategies to become winning strategies. If is a winning strategy for and Player I plays according to the strategy suggested above, then she will end up with a sequence that belongs to in the game . For this to result in a win in the game we need to belong to .
Something isn’t quite right about what I’ve just written, since I said that was a map from positions to positions, and the terminal sequence isn’t really a position. So to clear all this up, let me insist that maps sequences of length to sequences of length , and that if one finite sequence is an initial segment of another, then the same is true of their images under . Then extends straightforwardly to a map from infinite sequences to infinite sequences.
Let me summarize where we’ve got to. We would like to show that all Borel games are determined. Our general plan is to prove by induction that for every Borel game on there is a game that has the following properties.
(i) The positions of are finite sequences of elements of some set .
(ii) There is a map that takes finite sequences from to finite sequences of the same length from and that preserves the is-an-initial-segment-of relation.
(iii) There is another map with the same property that goes the other way.
(iv) If is the set of all infinite sequences that are a win for Player I in , then is the set of all infinite sequences that are a win for Player I in .
(v) is sufficiently simple that we can prove that it is determined.
Looking at the above, it seems that property (iii) isn’t really playing any role, since any right inverse of will do the job. Where it comes in is in explaining how to turn a strategy into a strategy. But that isn’t really part of what we require of the game — it’s more like part of the proof that the determinacy of implies the determinacy of .
What is a “simple” game?
An obvious answer to this would be an open game. However, if we can prove that for every closed game there is an open game with the properties above, then would be a closed set and would therefore be closed as well (because , as is easily checked, is continuous). So if we can always obtain an open game , then for closed games we can obtain a clopen game. But then, taking complements, the same is true for open games. So in the end the most natural definition of simplicity to go for in the game is that it should be a clopen game — that is, a game where the set of wins for Player I (and hence also for Player II) is both open and closed.
What are clopen games like? They are games where the outcome is always decided after a finite time, whichever player wins. Again, the length of time can be unbounded: for example, the game might be that the winner is the player who has played more 1s in the first terms of the sequence. (If, however, one restricts to a finite alphabet, then König’s lemma implies that a clopen game must be decided by the th move for some that depends only on the game and not on the particular play of the game.)
A failed attempt to lift to a clopen game
Let be a game played on . I’ll start with a simple observation: suppose that Player I fixes a strategy . Then if she fails to use , there must be some finite stage at which she plays a move that is not the move dictated by . This suggests a rather crude way of making a game “more closed”: insist that Player I declares her strategy in advance. The mathematical fact I am referring to here is that for any strategy , the set of possible sequences that result if Player I plays according to is closed.
Similarly, the set of possible sequences that result if Player II fails to play according to some strategy is open.
So here is a suggestion (which doesn’t work, but is illuminating nevertheless) for a way of lifting to a clopen game . Let be the set of all possible strategies for , and let and be the strategies for Player I and II, respectively. The game is played in the set and the rules are as follows.
Player I begins by naming a strategy , and Player II follows this by naming a strategy . These two strategies uniquely define the sequence that results if Player I uses and Player II uses . The rules of are that after the initial declaration of the strategies and , the players alternate choosing integers . If ever a player chooses that is not equal to , then that player loses. Otherwise, the winner is Player I if (where is the set of winning sequences for Player I in ) and Player II otherwise.
Let us see whether this idea achieves anything at all. (We should be very suspicious of it in advance, since I have made no assumption at all about the game .) First of all, is the resulting game clopen? To answer that, let us think about when Player I wins. If strategy defeats strategy , then the only way she can lose is if at some point she foolishly decides to stop using . Unfortunately, she can always do this, so the game is not open. Similarly, if defeats , then Player II can always depart from and lose, so the game is not closed either.
Let us not be too discouraged by this, since the game is at least a countable union of closed sets and a countable intersection of closed sets, and we could hope to prove that such games, which are far simpler than general Borel games, are determined. In fact, this game is trivially determined. If Player I has a winning strategy for , then declaring and sticking to is a winning strategy for , and if Player II has a winning strategy for , then whatever strategy Player I declares, Player II can declare and stick to a strategy that defeats it. (This triviality is of course quite worrying, as it suggests that no work has been done.) For now, let us focus on whether winning strategies for the game are any help to us if we want to play .
What can a winning strategy for Player I be like? It must be a strategy that defeats all strategies — that is, a winning strategy for — and Player I must abide by the strategy.
Actually, that is not quite true: if Player II chooses a strategy and does not abide by it, then Player I can do anything. So we find ourselves in the following awkward situation. Suppose that Player I plays in the game and the move dictated by in the original game . Suppose that Player II responds with in and in . Now suppose that both players play according to their declared strategies until at some point Player II stops playing according to . At that point, Player II loses . So Player I could have as a strategy: declare a winning strategy and play according to except that if Player II ever departs from his strategy then from that moment play 1s. This would be a winning strategy for Player I in the game , but it is not very helpful in the game .
Of course, one could argue that Player I doesn’t have to play the same numbers in as she plays in . What about the following method for converting winning strategies into winning strategies: you just play according to the strategy you played in your first move of ?
This certainly takes a winning strategy for Player I to a winning strategy for Player I, but again there is something worryingly trivial about it. In particular, what we are not doing here is providing a map from finite sequences of elements of to positive integer sequences of the same length.
More problematic is what tells us if there is a winning strategy for Player II. As we observed above, all Player II has to do to win is come up with a strategy that defeats whatever strategy Player I declared and stick to it. But how is this to help with , given that Player I will certainly not want to give away her strategy in advance. If Player II is “really” playing but is playing a game of on the side in order to choose his moves, what should he take to be Player I’s first move in the game ? There doesn’t seem to be an answer to this question.
That isn’t surprising, since we are not expecting a trivial proof that all games are trivially determined.
A second attempt
Some of the difficulties outlined in the previous section are more serious than others. Before we go any further, let me clear up a couple of the less serious ones.
First of all, the difficulty about the game not being clopen can be circumvented as follows. We just force the two players to stick to their declared strategies. There are two ways we can do that. One is to define a map that takes a sequence of the form to , where are the first moves in the game if Player I uses strategy and Player II uses strategy . Then the object of Player I in game is for strategy to defeat strategy in game , and the object of Player II is the reverse. So game is decided after each player has made one move, which definitely makes it clopen. (We still have the problem that a winning strategy for Player II in game doesn’t obviously translate into a winning strategy for Player II in game , but we know that we have to have a problem like that if we don’t use any property of .)
An alternative approach, which is the one usually taken, is to define games on infinite trees. The set of all finite sequences of positive integers has a natural tree structure (we join a sequence to all possible sequences of the form ) and infinite paths in this tree correspond to infinite sequences. The definition of a game generalizes straightforwardly to an arbitrary rooted tree as follows: the players start at the root and take turns to move from the current vertex to a neighbouring vertex (without ever going backwards); some set of infinite paths that start at the root is the set of winning paths for Player I and the rest form the winning set for Player II.
With this set-up, we can define the game as follows. The tree consists of all sequences of the form
such that . The map takes to . So basically, is the game with the two players announcing their strategies in advance — Player I doing so first.
So now the real problem is laid bare: that it is easy to come up with a fairly natural clopen game based on , but less easy to do so in such a way that the determinacy of (which is trivial for the game just defined) implies the determinacy of .
To begin to tackle this problem, let’s think about the first non-trivial case of what we are trying to prove: that a closed game can be lifted to an open game (and hence, by continuity, to a clopen game) in a useful way. This gives us certain advantages. In particular, if the game is closed, then it is not as obvious that this will be a problem, since in this case we know that if for every there exists that defeats , then there exists a that works for every .
That follows just from the determinacy of , so perhaps another question we could ask (again expecting the answer no, but the point is to try to understand why the information we have available is useful) is whether we can lift every determined game to a clopen game in a useful way.
The problem at the moment is that the game is too easy for Player II: all he has to do is defeat one strategy rather than find a strategy that defeats all strategies. And because we have made the game too easy for Player II, success at that game does not translate into success in .
What could we do to make things harder? One idea would be for Player II to declare a strategy and release Player I from her obligation to use her declared strategy . Then Player II would have a guaranteed win only if was a winning strategy. But then it is no longer clear what the role is of the strategy in the game.
Let us at least make the following observation. Suppose we have a game where Player I declares a strategy and wins the game, regardless of what Player II does, if and only if
is a winning strategy for . This is a clopen game and Player I has a winning strategy for if and only if she has a winning strategy for . However, Player II has a winning strategy for if and only if Player I does not have a winning strategy for , and that doesn’t directly give Player II a winning strategy for .
It is high time we used the fact that is a closed game. This tells us that if Player II wins the game , then he must have won it by some finite stage. That gives us yet another option to consider. If Player I declares a strategy that is not a winning strategy, then Player II can find a finite sequence that is compatible with (meaning that is always equal to ), all of whose extensions belong to (where is the closed set of winning sequences in for Player I). So another idea for a game is that Player I declares a strategy , then Player II declares a finite sequence compatible with . After that, they play the finite sequence. If all continuations of the finite sequence belong to , then Player II wins, and otherwise Player I wins.
What happens here? Again, the game is decided after the first move from each player. So what can be done with a winning strategy? The only way that Player I can guarantee to win is if her first move is a winning strategy for , so that is straightforward. But if she does not have a winning strategy, that just tells us that for every , Player II has a strategy that defeats and plays itself out in finite time.
Let’s think a bit more about how we might try to use the game to help with the game . As things stand, there is a big problem if Player II wants to use , because he will have to deem Player I to be declaring some strategy when she manifestly isn’t.
In a desperate attempt to get round this problem, Player II could play as follows. After Player I’s first move , Player II pretends that Player I has declared a strategy that is compatible with as a first move. If is not a winning strategy, then he follows this by choosing a finite sequence compatible with , all of whose extensions are wins for him (which he can do because is a closed game), and plays . If Player I does not at this point play , thereby demonstrating that she was not after all using strategy , then Player II finds some other strategy that is compatible with and pretends that was the strategy declared by Player I. And so on.
If at any stage in this process, the game actually reaches a sequence all of whose extensions are wins for Player II, then Player II has won the game.
Lifting a game to another game — towards a revised definition
I won’t pursue this thought too much further here, except to say that it motivates an important change to the definition we have adopted up to now of what it means to “lift” one game to another. Previously, our idea for how to use an auxiliary game to help us play a game was this. We have a map that takes positions of (or more formally, finite paths in the tree that defines ) to positions in of the same length and that respects the “is an initial segment of” relation. We also have a map in the opposite direction. We assume that the inverse image under (or rather the unique continuous extension of to infinite paths) of the set of winning sequences in is the set of winning sequences in . Then given a strategy for for Player I, we convert it into a strategy for by simply setting .
This is perhaps the most obvious notion of a “homomorphism” from one game to another, but it has led us into difficulties, and a more relaxed notion is sufficient for using one game to play another. Suppose that is a clopen game, that Player I has a winning strategy for playing , and that there is a map as above. All Player I needs in order to win is a strategy such that for any sequence that is compatible with there exists a sequence that is compatible with such that . Then whenever it is Player I’s turn, she looks at the current sequence , picks a preimage compatible with , plays the move in that dictates, and then plays the move in such that . At some finite stage she reaches a sequence in such that all continuations belong to , and then all continuations of belong to , so she wins the game.
Hmm … that doesn’t quite work. The problem is that if Player I keeps switching sequences in the game , then it is no longer necessarily the case that she is playing according to the strategy , so we cannot be sure that she will win.
What we therefore need is a stronger condition. We want that for every infinite sequence that is compatible with there should be a preimage under that is compatible with . This implies the statement for finite sequences. Player I can now play as above, and at the end of the game will have reached an infinite sequence that has at least some preimage that is compatible with . Since is a winning strategy for , this preimage will belong to , so the sequence itself will belong to .
Note that this argument does not imply that itself is open. Before we have finished playing according to the strategy , we do not know much about what the preimage compatible with is going to be. So there is no point at which we can say, “Right, Player I has won now.” This is of course very encouraging, since we don’t want a definition that would work only if we could prove the false statement that all closed games are open.
The revised definition
Here, then, is the correct (in the sense of genuinely useful) definition of lifting one game to another. By this stage in the post, it is probably a good idea to be fairly formal about it.
Let , therefore, be a game that is played on an infinite tree . I’ll assume that this tree is pruned, which means that every finite path in can be extended to an infinite branch. (The idea is that if there are any finite paths that can’t be extended, you cut them off at the last point that does have an infinite path coming out of it. The reason pruned trees are convenient is of course that one wants it always to be possible for a game played on to continue.) Let be the set of infinite paths in (by “path” I always mean a path that begins at the root) that are winning paths for Player I.
Now let be another game, this one played on a pruned tree . Let be a map that takes finite paths in to paths of the same length in and preserves the relation is-an-initial-segment-of. Then induces a map from infinite paths in to infinite paths in , which we will also call . This map is continuous in the topology with basic open sets of the form “the set of all infinite paths that start like this.” We also require that is the set of winning paths for Player I in the game .
To complete the definition we need a map from strategies to strategies. We will no longer say anything about how that map should be constructed, but instead say what properties it is supposed to have. If is a strategy, then it should map to a strategy with the property that for every infinite path in that is consistent with , there should exist an infinite path in that is consistent with and satisfies . That is, every run of the game in where is being applied is the image of some run in where is being applied.
Another property asked for is that the behaviour of on sequences of length at most should depend only on the behaviour of on sequences of length at most .
To round off the post, let me give once again the argument that if is a winning strategy in , then is a winning strategy in . This is very simple. I’ll assume that is a strategy for Player I — the argument is similar for Player II. If Player I plays according to strategy , then the resulting infinite path is the image under of some path in that is consistent with the strategy . But is a winning strategy for Player I in , so all paths consistent with belong to . Therefore, , so Player I has won the game by applying the strategy .
This post has reached my approximate word limit for this series (of 5,000 words), so I’ll finish it here, and turn next time to the question of how to lift a closed game to an open game. I’ve done enough guessing and adjusting to feel quite a lot more comfortable with the definition, so I’ll probably just go ahead and say what the lifting is and verify that it works.