Determinacy of Borel games II

By the end of the previous post, I had said what a Borel subset of $\mathbb{N}^{\mathbb{N}}$ 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 $\alpha$ 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 $x$ such that $x^2+5=30$ , you don’t guess, but instead you systematically simplify the conditions. You say to yourself, “Well, $x^2$ will have to be 25, but in that case we know that $x$ is $\pm 5$ .” 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 $G_1$ , and that Player I has a winning strategy for a different game $G_2$ . Under what circumstances would this provide Player I with a winning strategy for $G_1$ ? (I am asking for a reasonably simple sufficient condition rather than a complete characterization.)

A natural way to use $G_2$ is to play a game of $G_2$ on the side and use the moves of $G_2$ to choose moves for $G_1$ . How would this work? Well, one thing we would need is a map from $G_2$ positions to $G_1$ positions. Let me write $P(G)$ for the set of all possible positions in a game $G$ and let $\phi:P(G_2)\to P(G_1)$ be the map that gives us a $G_1$ position whenever we’ve got a $G_2$ position. Let us also write $A_i$ for the subset of $G_i$ that Player I is trying to reach and Player II is trying to avoid.

If Player I has a winning strategy $\sigma$ for $G_2$ , then she will need the initial position of $G_2$ to map to the initial position of $G_1$ . Then she can play the move that $G_2$ dictates and can make the corresponding move in $G_1$ . What is this corresponding move? It is the move that turns the initial position into $\phi$ of the position reached in $G_2$ . But this isn’t obviously a valid move in $G_1$ , so we had better add that as a requirement. More formally, if Player I can make a valid move from position $p$ to position $p'$ in game $G_2$ , then the move from position $\phi(p)$ to position $\phi(p')$ in game $G_1$ 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 $G_1$ — Player I can’t oblige him to make a $G_2$ move — but Player I can continue to use game $G_2$ for guidance if she can interpret Player II’s move as a move in game $G_2$ . For that, a sensible sufficient condition is that there should be a map $\psi$ from $P(G_1)$ to $P(G_2)$ such that valid $G_1$ moves map to valid $G_2$ 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 $G_1$ . Whenever it is her turn, she converts the current $G_1$ position $p$ into the $G_2$ position $\psi(p)$ , plays the $G_2$ move dictated by $\sigma$ , and converts the resulting $G_2$ position $p'$ into the $G_1$ position $\phi(p')$ .

Of course, we are looking for more than just a way of turning $G_2$ strategies into $G_1$ strategies: we want winning strategies to become winning strategies. If $\sigma$ is a winning strategy for $G_2$ and Player I plays $G_1$ according to the strategy suggested above, then she will end up with a sequence $\mathbb{n}$ that belongs to $A_2$ in the game $G_2$ . For this to result in a win in the game $G_1$ we need $\phi(\mathbb{n})$ to belong to $A_1$ .

Something isn’t quite right about what I’ve just written, since I said that $\phi$ was a map from $G_2$ positions to $G_1$ positions, and the terminal sequence isn’t really a position. So to clear all this up, let me insist that $\phi$ maps sequences of length $k$ to sequences of length $k$ , and that if one finite sequence is an initial segment of another, then the same is true of their images under $\phi$ . Then $\phi$ 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 $G_1$ on $\mathbb{N}^{\mathbb{N}}$ there is a game $G_2$ that has the following properties.

(i) The positions of $G_2$ are finite sequences of elements of some set $\Gamma$ .

(ii) There is a map $\phi$ that takes finite sequences from $\Gamma$ to finite sequences of the same length from $\mathbb{N}$ and that preserves the is-an-initial-segment-of relation.

(iii) There is another map $\psi$ with the same property that goes the other way.

(iv) If $A$ is the set of all infinite sequences that are a win for Player I in $G_1$ , then $\phi^{-1}(A)$ is the set of all infinite sequences that are a win for Player I in $G_2$ .

(v) $G_2$ 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 $\phi$ will do the job. Where it comes in is in explaining how to turn a $G_2$ strategy into a $G_1$ strategy. But that isn’t really part of what we require of the game $G_2$ — it’s more like part of the proof that the determinacy of $G_2$ implies the determinacy of $G_1$ .

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 $G_1$ there is an open game $G_2$ with the properties above, then $A_1$ would be a closed set and $\phi^{-1}(A_1)$ would therefore be closed as well (because $\phi$ , as is easily checked, is continuous). So if we can always obtain an open game $G_2$ , 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 $G_2$ 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 $n_1$ 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 $n$ th move for some $n$ 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 $G$ be a game played on $\mathbb{N}^{\mathbb{N}}$ . I’ll start with a simple observation: suppose that Player I fixes a strategy $\sigma$ . Then if she fails to use $\sigma$ , there must be some finite stage at which she plays a move that is not the move dictated by $\sigma$ . 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 $\sigma$ , the set of possible sequences that result if Player I plays according to $\sigma$ is closed.

Similarly, the set of possible sequences that result if Player II fails to play according to some strategy $\tau$ is open.

So here is a suggestion (which doesn’t work, but is illuminating nevertheless) for a way of lifting $G$ to a clopen game $G'$ . Let $\Sigma$ be the set of all possible strategies for $G$ , and let $\Sigma_{I}$ and $\Sigma_{II}$ be the strategies for Player I and II, respectively. The game $G'$ is played in the set $(\mathbb{N}\cup\Sigma)^{\mathbb{N}}$ and the rules are as follows.

Player I begins by naming a strategy $\sigma\in\Sigma_I$ , and Player II follows this by naming a strategy $\tau\in\Sigma_{II}$ . These two strategies uniquely define the sequence $\sigma\circ\tau=(n_1,n_2,n_3,\dots)$ that results if Player I uses $\sigma$ and Player II uses $\tau$ . The rules of $G'$ are that after the initial declaration of the strategies $\sigma$ and $\tau$ , the players alternate choosing integers $m_3,m_4,\dots$ . If ever a player chooses $m_i$ that is not equal to $n_i$ , then that player loses. Otherwise, the winner is Player I if $\sigma\circ\tau\in A$ (where $A$ is the set of winning sequences for Player I in $G$ ) 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 $G$ .) First of all, is the resulting game clopen? To answer that, let us think about when Player I wins. If strategy $\sigma$ defeats strategy $\tau$ , then the only way she can lose is if at some point she foolishly decides to stop using $\sigma$ . Unfortunately, she can always do this, so the game is not open. Similarly, if $\tau$ defeats $\sigma$ , then Player II can always depart from $\tau$ 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 $\sigma$ for $G$ , then declaring and sticking to $\sigma$ is a winning strategy for $G'$ , and if Player II has a winning strategy for $G$ , then whatever strategy Player I declares, Player II can declare and stick to a strategy $\tau$ 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 $G'$ are any help to us if we want to play $G$ .

What can a winning strategy for Player I be like? It must be a strategy $\sigma\in\Sigma_I$ that defeats all strategies $\tau\in\Sigma_{II}$ — that is, a winning strategy for $G$ — and Player I must abide by the strategy.

Actually, that is not quite true: if Player II chooses a strategy $\tau$ 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 $\sigma$ in the game $G'$ and the move $n_1$ dictated by $\sigma$ in the original game $G$ . Suppose that Player II responds with $\tau$ in $G'$ and $\tau(n_1)$ in $G$ . Now suppose that both players play $G$ according to their declared strategies until at some point Player II stops playing according to $\tau$ . At that point, Player II loses $G'$ . So Player I could have as a $G'$ strategy: declare a winning $G$ strategy $\sigma$ and play according to $\sigma$ except that if Player II ever departs from his strategy $\tau$ then from that moment play 1s. This would be a winning strategy for Player I in the game $G'$ , but it is not very helpful in the game $G$ .

Of course, one could argue that Player I doesn’t have to play the same numbers in $G$ as she plays in $G'$ . What about the following method for converting winning $G'$ strategies into winning $G$ strategies: you just play $G$ according to the strategy you played in your first move of $G'$ ?

This certainly takes a winning $G'$ strategy for Player I to a winning $G$ 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 $\mathbb{N}\cup\Sigma$ to positive integer sequences of the same length.

More problematic is what $G'$ tells us if there is a winning strategy for Player II. As we observed above, all Player II has to do to win $G'$ is come up with a strategy $\tau$ that defeats whatever strategy $\sigma$ Player I declared and stick to it. But how is this to help with $G$ , given that Player I will certainly not want to give away her strategy in advance. If Player II is “really” playing $G$ but is playing a game of $G'$ on the side in order to choose his moves, what should he take to be Player I’s first move in the game $G'$ ? 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 $G'$ 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 $\phi$ that takes a sequence of the form $(\sigma,\tau,m_3,m_4,\dots,m_k)$ to $(n_1,\dots,n_k)$ , where $n_1,\dots,n_k$ are the first $k$ moves in the game $G$ if Player I uses strategy $\sigma$ and Player II uses strategy $\tau$ . Then the object of Player I in game $G'$ is for strategy $\sigma$ to defeat strategy $\tau$ in game $G$ , and the object of Player II is the reverse. So game $G'$ 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 $G'$ doesn’t obviously translate into a winning strategy for Player II in game $G$ , but we know that we have to have a problem like that if we don’t use any property of $G$ .)

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 $(n_1,\dots,n_k)$ to all possible sequences of the form $(n_1,\dots,n_k,n)$ ) 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 $G'$ as follows. The tree consists of all sequences of the form

$((\sigma,n_1),(\tau,n_2),n_3,n_4,\dots)$

such that $\sigma\circ\tau=(n_1,n_2,n_3,\dots)$ . The map $\phi$ takes $((\sigma,n_1),(\tau,n_2),n_3,n_4,\dots)$ to $(n_1,n_2,n_3,n_4,\dots)$ . So basically, $G'$ is the game $G$ 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 $G'$ based on $G$ , but less easy to do so in such a way that the determinacy of $G'$ (which is trivial for the game $G'$ just defined) implies the determinacy of $G$ .

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 $G$ is closed, then it is not as obvious that this will be a problem, since in this case we know that if for every $\sigma\in\Sigma_I$ there exists $\tau\in\Sigma_{II}$ that defeats $\sigma$ , then there exists a $\tau$ that works for every $\sigma$ .

That follows just from the determinacy of $G$ , 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 $G$ to a clopen game $G'$ in a useful way.

The problem at the moment is that the game $G'$ is too easy for Player II: all he has to do is defeat one strategy $\sigma$ rather than find a strategy $\tau$ that defeats all strategies. And because we have made the game $G'$ too easy for Player II, success at that game does not translate into success in $G$ .

What could we do to make things harder? One idea would be for Player II to declare a strategy $\tau$ and release Player I from her obligation to use her declared strategy $\sigma$ . Then Player II would have a guaranteed win only if $\tau$ was a winning strategy. But then it is no longer clear what the role is of the strategy $\sigma$ in the game.

Let us at least make the following observation. Suppose we have a game $G'$ where Player I declares a strategy $\sigma$ and wins the game, regardless of what Player II does, if and only if
$\sigma$ is a winning strategy for $G$ . This is a clopen game and Player I has a winning strategy for $G'$ if and only if she has a winning strategy for $G$ . However, Player II has a winning strategy for $G'$ if and only if Player I does not have a winning strategy for $G$ , and that doesn’t directly give Player II a winning strategy for $G$ .

It is high time we used the fact that $G$ is a closed game. This tells us that if Player II wins the game $G$ , then he must have won it by some finite stage. That gives us yet another option to consider. If Player I declares a strategy $\sigma$ that is not a winning strategy, then Player II can find a finite sequence $u$ that is compatible with $\sigma$ (meaning that $u_{2i+1}$ is always equal to $\sigma(u_1,\dots,u_{2i})$ ), all of whose extensions belong to $A^c$ (where $A$ is the closed set of winning sequences in $G$ for Player I). So another idea for a game $G'$ is that Player I declares a strategy $\sigma$ , then Player II declares a finite sequence $u$ compatible with $\sigma$ . After that, they play the finite sequence. If all continuations of the finite sequence belong to $A^c$ , 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 $G'$ is if her first move $\sigma$ is a winning strategy for $G$ , so that is straightforward. But if she does not have a winning strategy, that just tells us that for every $\sigma$ , Player II has a strategy that defeats $\sigma$ and plays itself out in finite time.

Let’s think a bit more about how we might try to use the game $G'$ to help with the game $G$ . As things stand, there is a big problem if Player II wants to use $G'$ , because he will have to deem Player I to be declaring some strategy $\sigma$ when she manifestly isn’t.

In a desperate attempt to get round this problem, Player II could play $G$ as follows. After Player I’s first move $n_1$ , Player II pretends that Player I has declared a strategy $\sigma$ that is compatible with $n_1$ as a first move. If $\sigma$ is not a winning strategy, then he follows this by choosing a finite sequence $(n_1,\dots,n_k)$ compatible with $\sigma$ , all of whose extensions are wins for him (which he can do because $G$ is a closed game), and plays $n_2$ . If Player I does not at this point play $n_3$ , thereby demonstrating that she was not after all using strategy $\sigma$ , then Player II finds some other strategy $\sigma'$ that is compatible with $(n_1,n_2,n_3)$ and pretends that $\sigma'$ was the strategy declared by Player I. And so on.

If at any stage in this process, the game actually reaches a sequence $(n_1,\dots,n_k)$ 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 $G'$ to help us play a game $G$ was this. We have a map $\phi$ that takes positions of $G'$ (or more formally, finite paths in the tree that defines $G'$ ) to positions in $G$ of the same length and that respects the “is an initial segment of” relation. We also have a map $\psi$ in the opposite direction. We assume that the inverse image under $\phi$ (or rather the unique continuous extension of $\phi$ to infinite paths) of the set of winning sequences in $G$ is the set of winning sequences in $G'$ . Then given a strategy $\sigma$ for $G'$ for Player I, we convert it into a strategy $\tau$ for $G$ by simply setting $\tau=\phi\sigma\psi$ .

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 $G'$ is a clopen game, that Player I has a winning strategy $\sigma$ for playing $G'$ , and that there is a map $\phi$ as above. All Player I needs in order to win $G$ is a strategy $\tau$ such that for any sequence $(n_1,\dots,n_k)$ that is compatible with $\tau$ there exists a sequence $(m_1,\dots,m_k)$ that is compatible with $\sigma$ such that $\phi(m_1,\dots,m_k)=(n_1,\dots,n_k)$ . Then whenever it is Player I’s turn, she looks at the current sequence $(n_1,\dots,n_k)$ , picks a preimage $(m_1,\dots,m_k)$ compatible with $\sigma$ , plays the move $m_{k+1}$ in $G'$ that $\sigma$ dictates, and then plays the move $n_{k+1}$ in $G$ such that $\phi(m_1,\dots,m_k,m_{k+1})=(n_1,\dots,n_k,n_{k+1})$ . At some finite stage she reaches a sequence $(m_1,\dots,m_{r})$ in $G'$ such that all continuations belong to $\phi^{-1}(A)$ , and then all continuations of $\phi(m_1,\dots,m_r)$ belong to $A$ , so she wins the game.

Hmm … that doesn’t quite work. The problem is that if Player I keeps switching sequences in the game $G'$ , then it is no longer necessarily the case that she is playing according to the strategy $\sigma$ , so we cannot be sure that she will win.

What we therefore need is a stronger condition. We want that for every infinite sequence $(n_1,n_2,\dots)$ that is compatible with $\tau$ there should be a preimage $(m_1,m_2,\dots)$ under $\phi$ that is compatible with $\sigma$ . 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 $\sigma$ . Since $\sigma$ is a winning strategy for $\phi^{-1}(A)$ , this preimage will belong to $\phi^{-1}(A)$ , so the sequence itself will belong to $A$ .

Note that this argument does not imply that $G$ itself is open. Before we have finished playing $G$ according to the strategy $\tau$ , we do not know much about what the preimage compatible with $\sigma$ 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 $G$ , therefore, be a game that is played on an infinite tree $T$ . I’ll assume that this tree is pruned, which means that every finite path in $T$ 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 $T$ to continue.) Let $A$ be the set of infinite paths in $T$ (by “path” I always mean a path that begins at the root) that are winning paths for Player I.

Now let $G'$ be another game, this one played on a pruned tree $T'$ . Let $\phi$ be a map that takes finite paths in $T'$ to paths of the same length in $T$ and preserves the relation is-an-initial-segment-of. Then $\phi$ induces a map from infinite paths in $T'$ to infinite paths in $T$ , which we will also call $\phi$ . 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 $\phi^{-1}(A)$ is the set of winning paths for Player I in the game $G'$ .

To complete the definition we need a map from $G'$ strategies to $G$ 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 $\sigma'$ is a $G'$ strategy, then it should map to a $G$ strategy $\sigma$ with the property that for every infinite path $p$ in $T$ that is consistent with $\sigma$ , there should exist an infinite path $p'$ in $T'$ that is consistent with $\sigma'$ and satisfies $\phi(p')=p$ . That is, every run of the game in $G$ where $\sigma$ is being applied is the image of some run in $G'$ where $\sigma'$ is being applied.

Another property asked for is that the behaviour of $\sigma$ on sequences of length at most $n$ should depend only on the behaviour of $\sigma'$ on sequences of length at most $n$ .

To round off the post, let me give once again the argument that if $\sigma'$ is a winning strategy in $G'$ , then $\sigma$ is a winning strategy in $G$ . This is very simple. I’ll assume that $\sigma$ is a strategy for Player I — the argument is similar for Player II. If Player I plays according to strategy $\sigma$ , then the resulting infinite path $p$ is the image under of some path $p'$ in $T'$ that is consistent with the strategy $\sigma'$ . But $\sigma'$ is a winning strategy for Player I in $G'$ , so all paths consistent with $\sigma'$ belong to $\phi^{-1}(A)$ . Therefore, $\phi(p')=p\in A$ , so Player I has won the game $G$ by applying the strategy $\sigma$ .

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.

About these ads

This entry was posted on August 31, 2013 at 8:57 am and is filed under complexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Determinacy of Borel games II”

william e emba Says:
September 2, 2013 at 3:07 pm | Reply
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.)
- gowers Says:
  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.

Gowers's Weblog