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.
October 30, 2013 at 7:42 pm |
It is not very nice in this post that in the “Lifting one game to another section”
is used for
strategies, while later it is used for
strategies and
for
strategies.