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.
September 2, 2013 at 3:07 pm |
Perhaps the easiest auxiliary game construction is Martin’s proof of analytic determinacy from a measurable cardinal. The hard part is ultimately the groundwork theorems that represent analytic sets in terms of infinite trees and their branches. (I assume the Ramsey property of measurable cardinals is deep within your explanatory comfort zone.)
September 3, 2013 at 10:33 am
Thanks for the suggestion. I’ve actually finished the proof of Borel determinacy now (there are two more posts written, which I’ll put up fairly soon), but if I get the time, then that would make a good basis for a further series of posts. I say “series” because I think I’d need to have a post about basic properties of analytic sets, something I lectured about in a graduate course about 17 years ago and haven’t thought much about since.