My aim in this post (if I have enough space) is to prove that every closed game can be lifted to an open (and therefore, by continuity, which is part of the definition of lifting, clopen) game. Since I am discussing a formal proof, I shall be a little more formal with my definitions than I have been so far. Much of what I write to begin with will be repeating things I have already said in the two previous posts.
Trees and paths
Recall the definition of a pruned tree. This is an infinite rooted tree such that from every vertex there is at least one directed infinite path. (Less formally, if you are walking away from the root, you never get stuck.) Given such a tree , we write for the set of infinite directed paths in . If we are working in , then the tree we will work with has finite sequences as its vertices, with each sequence joined to its extensions . Then .
If and are finite paths in (I’ll stop using the word “directed” — all paths are supposed to be directed away from the root) — then we write to mean that is an initial segment of and if is a proper initial segment. Also, if is a path that starts where another path ends, I’ll write for the concatenation of and . In paths are represented by integer sequences. In that case, if and , then denotes the sequence . That is, we view the path as starting at the sequence . This isn’t exactly consistent with the previous definition, but it is the only definition that makes sense, so no confusion should arise.
If is a tree and is a path that starts at the root, then denotes the tree of all such that .
We topologize by taking sets of the form as the basic open sets. Thus, a subset is open if for every there exists a finite path such that and for every infinite path such that .
Games and strategies on trees
Given a pruned tree and a “payoff set” , we can define a two-player game as follows. The players build up a path that starts at the root, taking turns to decide which the next vertex will be. Thus, if is the root, then the players take turns choosing subject to the condition that should be a path in for every . At the end of the game, the players have defined an infinite path . Player I wins if and otherwise Player II wins.
A game is called open/closed/Borel/etc. if and only if the payoff set is open/closed/Borel/etc. in .
A strategy for Player I is a function from even-length paths in that takes each such path to a path of length one greater such that . A strategy for Player II is similar but for odd-length paths.
It can be helpful to associate strategies with subtrees of . A strategy for Player I can be used to create a subtree of that consists of all vertices in that can be reached by a path consistent with , together with the edges induced by those vertices. The strategy is a winning strategy if and only if — that is, every infinite path consistent with the strategy is in the payoff set . (Everything I say about Player I can be easily adapted to corresponding statements about Player II — I won’t keep pointing this out.)
Which subtrees can be obtained in this way? A subtree is derived from some strategy for Player I if and only if it has the following property. Let us say that a vertex is a successor of a vertex if it is a neighbour of and is further away from the root. Then for each vertex of at an even distance from the root, there should be exactly one successor in , and for each vertex at an odd distance from the root, every successor should be in . To define a strategy from which is derived is easy. Given a vertex in at even distance from the root, let be the unique path that ends at and let be the unique path in of length one greater than . If is a path of even length not in , then can be defined arbitrarily, but this is not very important, since cannot be reached if Player I uses the strategy . Thus, there isn’t exactly a one-to-one correspondence between strategies and certain subtrees, but there is a correspondence between “the parts of strategies that actually matter” and those subtrees.
Note that if and are subtrees corresponding to strategies and for Player I and II, respectively, then is an infinite path. Indeeed, it is precisely the path that results if Player I plays and Player II plays . This path we denote by .
A quasistrategy on is a bit like a strategy except that it doesn’t determine moves uniquely. For example, a quasistrategy for Player I in a closed game is, “If you can move to a position that is not a winning position for Player II, then do so, and otherwise move arbitrarily.” (This is a winning quasistrategy if Player II does not have a winning strategy.) Subtrees are a convenient way of formalizing the notion of a quasistrategy: we can define a quasistrategy for Player I on to be any subtree such that for each vertex of at even distance from the root at least one successor belongs to , and for each vertex at odd distance from the root, every successor belongs to . (Again, it is not too important to know what happens at vertices that cannot be reached if the quasistrategy is applied, but it is easy to invent a definition that does specify this.)
Lifting one game to another
Given a tree and a payoff set , let us write for the associated game. A lifting of is another game together with a map and a map that takes strategies for to strategies for with the following properties.
(i) For every , takes paths of length to paths of length . (In other words, if is a path in , then the images form a path in , which we will denote by . We will also use for the resulting map on infinite paths: that is, we will sometimes regard as a map from to .)
(ii) . (Here we are already regarding as a map from to .)
(iii) If is a strategy for , then is a strategy for the same player, and what does to sequences of length at most depends only on what does to sequences of length at most .
(iv) For every strategy for and every infinite path in that is consistent with there exists an infinite path in that is consistent with such that . (Informally, every run of the game in with being applied is the image of some run of the game in with being applied.)
We make a couple of remarks about this definition. Note first of all that the map is continuous, since if , then if is any path that agrees with for the first steps, will agree with for the first steps.
Note too that if is a winning strategy in the game , then is a winning strategy in the game . Indeed, if is a run of that is consistent with , then there must be a run of consistent with such that . Since is a winning strategy, will belong to or as appropriate (i.e., according to whether is a strategy for Player I or Player II), and therefore will belong to or as appropriate.
How much structure do liftings have?
Our ultimate aim is going to be to lift an arbitrary Borel game to a clopen game . How easy is this likely to be? Are liftings difficult things to construct?
At first one might think that even if we completely ignore the map that takes strategies to strategies, if is a rather complicated Borel set it would be hard to find a continuous function such that is clopen. However, this is not as hard as it sounds: it is a reasonably straightforward exercise to show that every Borel set is a continuous image of a closed set. (The converse is not true. For example, the non-Borel set described in an earlier post, of all graphs on that contain an infinite clique, is, more or less by definition, a continuous image of a closed set.)
Once we have chosen the function , it is tempting to think that there are too few constraints on the function . However, the constraint that what does to sequences of length at most depends only on what does to sequences of length at most restricts the possibilities for quite considerably.
Let’s write for the set of all infinite subtrees that satisfy the conditions described earlier: that each vertex at an even distance from the root is joined to exactly one successor, while each vertex at an odd distance is joined to all its successors. Let us call such trees strategic. Let us also call a finite tree strategic if all its leaves are at the same distance from the root and all vertices apart from the leaves satisfy the conditions of an infinite strategic tree. Thus, finite strategic trees are restrictions of infinite strategic trees to some depth . Let us write for the set of all such trees. If is a function that satisfies condition (iii) above, then for each it induces a function . The definition of is obvious: given a strategic tree in of depth , extend it to an arbitrary tree and define to be the restriction to the first levels of . This is well-defined, by condition (iii).
Suppose now that we have a collection of maps with . If they are all derived from some map that satisfies condition (iii), then they have to satisfy a simple compatibility condition. Let us write for the restriction of a tree to its first levels. Then we require that, for any and any strategic tree , .
Conversely, if we are given such a sequence of maps we can define a map that gives rise to all of them in a natural way. (It is clearly some kind of inverse limit, but I haven’t thought carefully about exactly what the category is.) Given a strategic tree , we define to be the union of the trees . The compatibility conditions ensure that the trees are nested, and since they are strategic it follows that their union is strategic.
The fact that is an inverse limit shows that it is very far from an arbitrary function from strategies to strategies (or strategic trees to strategic trees). Let us think about how we might build up a sequence satisfying the compatibility conditions. That is, if we have defined already, what more do we need to specify in order to define ?
To begin at the beginning, the first move of a strategy is just a choice of a successor of the root. Let us write and for the “level-” vertices in the trees and , respectively. Then can be thought of as a map from to .
Once we have decided on , the map is also decided, since Player I has no decisions to make in the second move. So the next choice to make is of . Informally, is a map from “how Player I makes her first two moves in ” to “how Player I makes her first two moves in “. More formally, it is a map from strategic trees of depth 3 to strategic trees of depth 3. To specify a strategic tree of depth 3 in we have to specify a successor of the root, and for each of its successors we have to specify a further successor. So we can split up the domain of according to the choice of . For each fixed , the specification of a tree is a function defined on the set of successors of , which takes each successor to one of its successors. Meanwhile, the codomain of this restriction of can be thought of as a function defined on the set of successors of , which again takes each successor to one of its successors. So this restriction of is an arbitrary function from a huge set of functions to a huge set of functions. And we then need to choose such functions for every .
Already we see that we are dealing with a vast and unstructured set. Should we worry about this? (The kind of worry I am talking about is that we have so much flexibility that it is hard to see why the theorem we are trying to prove isn’t trivial.) I think not, for the following reason. If we visualize the tree laid out “horizontally” with the root at the left and the levels living in vertical lines, then all the lack of structure is “vertical”, which is somehow appropriate because the set of successors of any given vertex is just a set and has no structure. On the other hand, trees have a lot of “horizontal structure” (for example, the topology is “defined horizontally”), and this is where the restrictions on make themselves felt.
Of course, condition (iii) is not the only condition that a lifting has to satisfy: there is also the all-important condition (iv). However, I will save a similar discussion of that condition for later.
Lifting a closed game to an open game
Now at long last comes the definition of the lifting we shall use. Let be a pruned tree, let be a closed set and let be the game . We define a tree as follows. Its vertices are certain sequences of the form
where is a path in (I should put the root before everything, but I take it as implicit that every path starts at the root and only the subsequent vertices need to be specified) and and are extra pieces of information that I will describe in a moment. The reason I said “certain sequences” above is that the information and will restrict what is allowed for the .
The map is the map that takes to (or to if you prefer to think of it like that — there is a one-to-one correspondence between paths in and their end vertices). In other words, simply forgets the extra information.
What is this “extra information”? In the case of , it is easy: Player I has to provide not just a successor of the root in but also a quasistrategy for the game that results in playing . We can think of it as follows: Player I plays but in addition says, “This is my quasistrategy.” If Player I plays the move as her first move, then all subsequent choices of must result in a sequence compatible with . In terms of trees, the subtree of with as its root projects to the subtree of that corresponds to the quasistrategy and starting move .
The definition of is less obvious, since Player II has two options. He can either provide a sequence of length that is consistent with , such that all extensions of live in , or a quasistrategy for the game played in the tree that is derived from (that is, the tree given by all possible runs of the game that are consistent with ). The quasistrategy must have the property that every infinite sequence that can result from it belongs to . In other words, it must be a losing quasistrategy (in the strong sense that it guarantees a loss) for Player II.
If Player II plays a move of the form , then both players must play along the sequence until they reach the end of it, and then they must continue consistently with . If Player II plays a move of the form , then both players must play consistently with the quasistrategies and . (Again, the force of this “must” is that the game is taking place inside a certain subtree. In other words, it’s not that they lose if they don’t play consistently with their quasistrategies: rather, they cannot but play consistently with their quasistrategies.)
Since is such a simple map, it is easy to say who wins the game : Player I wins if the resulting infinite sequence, ignoring the extra information, belongs to , and otherwise Player II wins.
Another easy observation is that this game is clopen. To see that it is closed, observe that is obviously continuous and is closed. To see that it is open, note that if Player II plays a move of the form , then since the two players continue along and all continuations of belong to , Player II wins the game in this case, whereas if Player II plays a move of the form , where is a guaranteed-losing quasistrategy, then by definition the sequence that results at the end of the game belongs to and Player I wins. So the result of the game is entirely decided after Player II’s first move.
The fact that the game is decided after Player II’s first move suggests that we have not actually used the assumption that is closed, since we could ignore the first proof that is a closed game and just use the fact that it is decided after Player II’s first move. However, the assumption that is closed has sneaked in under the radar via the unspoken assertion that Player II can play a move of one of the two types above. Suppose Player I were to play a guaranteed-losing quasistrategy . Then Player II would not be able to counter with a move of the second type, so would be forced to find a finite sequence all of whose extensions live in . This may not be possible if isn’t closed.
Who wins the game ?
This subsection isn’t strictly necessary, but it seems a pretty sensible thing to think about.
If Player I has a winning strategy for , then an obvious first move in is the move , where is the first move in determined by .
This move automatically results in a win for Player I in , since there is no sequence consistent with , all of whose extensions lie in . (If there were, then would by definition not be a winning strategy.) So Player II is forced to play a move of the second type and therefore loses.
If Player I plays a move , where is not a winning quasistrategy (which in particular happens automatically if Player I does not have a winning quasistrategy), then there must be some infinite sequence consistent with that lives in . Since is open, there is some initial segment of , all of whose continuations lie in . If Player II plays , then the two players continue to the end of , at which point the resulting sequence is guaranteed to belong to , and Player II wins.
What we have observed is that if Player I has a winning strategy for , then she has a winning strategy for , and if she does not have a winning strategy for , then Player II has a winning strategy for . The interesting thing to note here is that I did not deduce the latter statement from the determinacy of . That is, I didn’t say, “If Player I doesn’t have a winning strategy for , then, since is closed, Player II must have a winning strategy for . We use that to create a winning strategy for as follows.” Rather, I directly defined a winning strategy for Player II in using the fact that is closed and the quasistrategy is not winning.
What we are trying to do, however, is the reverse. We want to show that if Player I has a winning strategy for , then at least somebody has a winning strategy for , and likewise for Player II. (As I write this, I haven’t yet digested the proof enough to know whether the same player has a winning strategy for , but my impression is that that isn’t necessarily the case. We shall soon see. [Added later: I now see that that was a silly remark, since I’ve already observed that the lifting property ensures that if is a winning strategy for then is a winning strategy for for the same player.])
A bad way of converting Player I strategies for into Player I strategies for
What is a strategy for Player I like in the game ? It consists of an initial move , where is a quasistrategy for , and then a strategy for playing the remainder of the game consistently with not just but also with either the sequence or the quasistrategy given by Player II in his first move.
How can we use this for creating a strategy for ? An obvious first thought is that the strategy should be some strategy that is consistent with the quasistrategy . (The meaning of “consistent with” is I hope obvious.) Does that work? Certainly, what does to sequences of length at most depends only on what does to sequences of length at most , since it depends only on what does in the very first move.
What about the lifting property? Suppose that is a sequence consistent with . Is there some play of consistent with that yields the same sequence?
There are two cases to consider here: the case and the case .
If , then pick a strategy for Player II such that . If Player II plays the move in , then the result will be that for the remainder of the game the players will produce the sequence , just as required.
If , then choose an initial segment of of even length such that all continuations of belong to and let Player II play the move in . Then the sequence is consistent with and , so again it results from a play of .
So it seems that creating a strategy from a strategy and obtaining the lifting property is almost trivial. The problem is that in the actual proof something more complicated is done, so the above argument has to be wrong somehow. But how? It took me about a day (not of continuous thought, I hasten to add, and not writing anything down, but a day nevertheless) to see my stupid mistake. I’m leaving the above wrong argument in, since I think it helps to understand why the right argument is as it is. You may prefer to test your understanding by working out for yourself what is wrong with the argument rather than just reading my explanation below.
The problem is that to define the strategy I ignored most of the strategy, so it wasn’t actually true that I obtained the lifting property. Recall that a strategy for Player I consists of two things: a first move , where is some quasistrategy, and then a strategy for playing consistently not just with but also with Player II’s extra information — either a sequence that must be followed or a quasistrategy . So if in the game Player I just plays an arbitrary strategy that is consistent with , there is no reason to think that this will result from some play of with the strategy “Start with and continue with the strategy or .” We need to depend on somehow.
A better way of converting Player I strategies for into Player I strategies for
Let’s have another try. (I admit that for this I am just copying from an existing account of the proof.) Suppose that Player I’s first move in the game (according to a given strategy ) is , where is a quasistrategy for . Now consider the game restricted to . That is, we associate with a tree in the manner described earlier, and the payoff set is . This game can be thought of as with the restriction that Player I is required to play consistently with the quasistrategy .
Since is a closed set, so is in this restricted game. Therefore the game is determined. However, there is a twist. We shall ask for Player I to play the open game with payoff set , which is also determined. Or rather, we shall insist on the following: if Player I has a winning strategy for getting into the open set , then she must play according to such a strategy.
This may seem a rather bizarre thing for Player I to do: the reason for it is to force the game to reach a sequence , all of whose continuations belong to , which is good for us because we can then deem Player II to have played the sequence in his first move in the game .
We could perhaps summarize this by saying that in the case where Player I has a winning strategy for the “reverse game”, she is not in a very good position in the game , so instead she plays in a way that will ensure that Player II wins, but will also ensure that the run of the game lifts properly.
Another puzzling feature of the argument so far
The next thing I don’t understand is this. To prove that is determined, we use the fact that is determined. The way we use that is to show that a winning strategy for maps to a winning strategy for for the same player. So it would seem that we don’t need a map from arbitrary strategies to strategies, but just a map from winning strategies to winning strategies.
But a winning strategy for Player I for must start with a move such that is a winning quasistrategy for , or else Player II can play a move of the type , where is a finite sequence, consistent with , all of whose continuations lie in . And if Player I starts with a winning quasistrategy, and if is the tree defined above, we have that , so Player I cannot possibly have a winning strategy for producing a finite sequence with all its continuations in . So that complicated case would appear not to arise, or at least not to arise in any relevant way.
I can’t see anything wrong with this simplification, but I have a guess about why we would be ill advised to make it. The reason is that all we are considering at the moment is the base case of the induction. Later on, we are going to have to look at countable intersections and countable unions. It seems at least possible (and in fact very likely) that we will have to consider images of non-winning strategies at that stage, for example if some of the sets are wins for Player I and some are wins for Player II. So let us persist with the not yet obviously necessary task of constructing the map that is defined on arbitrary strategies.
Converting Player I strategies for into Player I strategies for , continued
So far we have defined what does in the case that Player I has a winning strategy for arriving in , where is the tree that corresponds to the quasistrategy in Player I’s first move . Or rather, we have said what the important part is. Let me briefly describe this case in full, repeating a few things I’ve already said.
If is Player I’s strategy for , then the strategy is defined as follows. Let be the first move required by and let be the tree corresponding to the quasistrategy . If Player I has a winning strategy for the game , then she must choose such a strategy and play it. After a point has been reached where all continuations of the current sequence lie in , Player I must continue with whatever strategy dictates in the case that Player II plays the sequence as his first move.
If Player I does not have a winning strategy for the game , then Player II must have a winning strategy for this game, since it is open (in ) and therefore determined. In fact, we know that the quasistrategy “always move to a position that is not a winning position for Player I” is a winning quasistrategy for Player II. Let be this quasistrategy. Player I’s strategy for is as follows. For as long as Player II plays consistently with the quasistrategy , she plays whatever dictates if Player II’s first move is . If Player II ever departs from , then he moves to a losing position for the game , that is, a winning position for Player I in this game. In that case, Player I goes back to the previous approach: that is, choosing a winning strategy for that game (given the current position), playing it until a finite sequence is reached, all of whose continuations are in , and continuing as dictates.
How to remember the definition of for Player I strategies
This post has passed the 5000-word limit, but I think I should finish it with a quick verification that the all-important lifting property holds for this strategy. But before I do that, let me try to describe in a less formal way what does to Player I strategies for .
The best way to think about it (or rather, the way I find helpful at the time of writing) is to forget all about winning and losing and just concentrate on the lifting property. That is, if we have a strategy for Player I, we don’t try to map it to a strategy that will maximize Player I’s chances of winning. We don’t care about that, since all we need is that if is a winning strategy for Player I, then the lifting property will guarantee that is a winning strategy for Player I in the game . So instead, we focus entirely on the lifting property.
Once we think about things this way, the definition writes itself to some extent. All we have to do is work out what sequences in can possibly arise during runs of the strategy and devise a strategy for Player I for creating one of those sequences. In other words, we end up playing a different game — the one where Player I’s aim is to create what one might call a -compatible sequence.
What are these sequences? There are two kinds, according to the kind of move Player II makes. Again let be Player I’s first move as dictated by . One kind is a sequence consistent with that has an initial segment , all of whose continuations belong to and that continues according to the strategy . The other kind is a sequence that could result if Player II plays some quasistrategy against that always yields a sequence in and Player I does what dictates in response to that quasistrategy.
Can Player I force the game to yield a sequence of such a kind? Clearly yes if she has a winning strategy for producing the requisite initial segments . If she doesn’t, then we would like to find a suitable quasistrategy for Player II, and the most natural one (sometimes called the canonical quasistrategy) is the “avoid losing if you can” quasistrategy that we chose.
As a matter of fact, I think I’ll end the post here, since with the above explanation it becomes clear that (not too surprisingly) the strategy has been defined in a way that makes absolutely sure that the lifting property holds. So the lifting property holds. I don’t feel the need for a more formal proof.
A brief preview of the next post
It remains to say what does to strategies for Player II and then to discuss countable unions and intersections. It turns out that the countable unions and intersections are easier to deal with than the base step of the induction (that is, the statement that closed games can be lifted to clopen games). However, there is one aspect of the proof that I have not yet mentioned, since I didn’t want it to be a distraction. It’s that we actually need a very slight further strengthening of the inductive hypothesis. We need not just that the game lifts to a clopen game but that for every the game lifts to a clopen game in such a way that the first levels of the tree are the same as the first levels of the tree . The modifications needed are completely straightforward (roughly speaking you don’t introduce the extra information until the first moves are complete) but complicate the notation. So I decided to present the case , which contains the main idea.
The reason for needing the result for general is that that enables us to do a diagonal construction when we come to look at countable unions and intersections.