Determinacy of Borel games V

This post is a kind of postscript to the previous four. It consists of miscellaneous observations that shed some light on the proof of Borel determinacy. I’m writing it mainly for my own benefit, but there seems to be no harm in posting it, just in case anyone else finds it interesting.

An attempt to lift that sort of works and sort of doesn’t

One way to get some further insight into the proof of Borel determinacy is to look at some auxiliary games that don’t work as lifts. A particularly natural candidate is this. Let $T$ be an infinite (pruned) tree, let $A\subset[T]$ and let $G$ be the game $G(T,A)$ . Now define a game $G'$ as follows. Player I plays a move of the form $(x_1,\sigma)$ , where $\sigma$ is a strategy for $G$ with first move $x_1$ . Player II plays a move of the form $(x_2,\tau)$ , where $\tau$ is a strategy for $G$ and $x_2=\tau(x_1)$ . Thereafter, the two players must play the strategies $\sigma$ and $\tau$ .

Clearly the outcome of this game is decided after the first two moves: if $\sigma$ beats $\tau$ then Player I wins and otherwise Player II wins.

Now let’s try to map $G'$ strategies to $G$ strategies. Given a strategy $\sigma'$ for Player I for $G'$ , let the first move be $(x_1,\sigma)$ . Then it makes sense to let $\sigma$ be the image of $\sigma'$ . Does this give us the lifting property? Well, if $x$ is a run of $G$ with Player I playing the strategy $\sigma$ , then there must be some Player II strategy $\tau$ for $G$ (in fact there are several) such that $\sigma\circ\tau=x$ (that is, if Player I plays $\sigma$ and Player II plays $\tau$ then $x$ is the sequence produced). So if Player II plays $(x_2,\tau)$ (where $x_2$ is the second term of $x$ ) as his first move in $G'$ the result of the run of $G'$ when projected to $T$ will be the sequence $x$ . So far so good.

The problem comes when we try to map Player II strategies. Let $\tau'$ be a strategy for Player II in $G'$ . This can be thought of as a map that takes Player I strategies for $G$ to Player II strategies for $G$ . (Player I’s first move is of the form $(x_1,\sigma)$ , but actually $x_1$ is determined by $\sigma$ . Likewise, $x_2$ is determined by $\sigma$ and $\tau$ .) Given such a map, how are we supposed to create a strategy out of it?

Let’s think about the set of all possible runs of the game that can result if Player II uses the $G'$ strategy $\tau'$ . They are the sequences of the form $\sigma\circ\tau'(\sigma)$ . In order to be able to find a suitable image for $\tau'$ , we need to be able to find a strategy $\tau$ such that every possible run of $G$ if Player II uses $\tau$ gives us a sequence of the form $\sigma\circ\tau'(\sigma)$ . In other words, we need Player II to have a winning strategy for this set of sequences. Note that we need to be able to do this for every $G'$ strategy $\tau$ — that is, every function from Player I strategies to Player II strategies.

Now the one thing that matters about $\tau'(\sigma)$ is the sequence $\sigma\circ\tau'(\sigma)$ and the one thing we know about that is that it is a sequence that can result if Player I plays the strategy $\sigma$ . Since $\tau'$ is arbitrary, we need to show that if $U$ is any set of sequences with the property that for every Player I strategy $\sigma$ there is at least one $u\in U$ that can result if Player I plays $\sigma$ , then Player II has a winning strategy for $U$ . But the assumption we are making about $U$ is precisely that Player I does not have a winning strategy for $U^c$ . (Proof: if $\sigma$ is any strategy for Player I, there is, by assumption, a sequence not in $U^c$ that can result if Player II plays appropriately.)

So we find that what we are asking for is precisely this: that if $V$ is any set for which Player I does not have a winning strategy, then Player II has a winning strategy for $V^c$ . (Here $V$ is playing the role of $U^c$ above.) But this is the statement that all sets are determined, otherwise known as the axiom of determinacy. And of course, if we have that, then we don’t need to go to any trouble to prove that all Borel sets are determined.

A small additional remark here is that, as I’ve sort of said but not fully spelt out, we could change the rules of the $G'$ so that Player II plays not a strategy $\tau$ but just some sequence $u$ that is consistent with $\sigma$ . In other words, we don’t actually care about $\tau$ : we just care about $\sigma\circ\tau$ .

Yet another remark is that in the argument above, the payoff set $A$ played no role. That’s because the proof that the game is decided after the first move of each player is particularly simple: the entire sequence is decided after these moves, and therefore whatever set $A$ we take, we know after those moves which player is destined to win. In other words, the map above from $G'$ strategies to $G$ strategies simultaneously lifts all games to clopen games. So it gives us a neat way of proving the axiom of determinacy, using … er … the axiom of determinacy.

An attempt to lift that doesn’t work

In the previous example, we showed that if all games are determined, then all games can be lifted to clopen games, and indeed to games that are decided after the first move of each player.

What if we try to prove the much stronger result that every determined game can be lifted? This is stronger because we are not allowed to use the determinacy of all sets in the proof, as we did above in an absolutely critical way, but instead just the determinacy of the payoff set in the game we are trying to lift.

Let the game be $G=G(T,A)$ as above. Then the initial data we have consists of $T$ , $A$ , and either a winning strategy $\sigma$ for Player I or a winning strategy $\tau$ for Player II. We now have to devise an auxiliary game. I’m just going to write down the obvious thing, with no thought of whether it works — and then show that it doesn’t work.

Let’s define $G'$ as follows. If Player I has a winning strategy $\sigma$ for $G$ , then we pick one and let $G'$ be an arbitrary run of $\sigma$ . That is, $G'$ is played on the tree of all paths in $T$ that are consistent with $\sigma$ and all paths are considered wins for Player I. So this game is in fact decided before it even starts.

Does the lifting property hold? Well, there is only one possible $G'$ strategy for Player I, since every point at even distance from the root has just one successor. The obvious $G$ strategy to map that to is $\sigma$ , and then trivially every run of $G$ with Player I playing $\sigma$ comes from a run of $G'$ .

How about the other way round? A strategy for Player II in the game $G'$ can be thought of as a sequence $u$ that is consistent with $\sigma$ . What should we map that to? We need to map it to a $G$ strategy that guarantees that the resulting sequence will be $u$ . But that’s obviously out of the question: Player I can easily play in a way that doesn’t produce $u$ . (Note that in $G$ there is no reason for Player I to apply the strategy $\sigma$ . Indeed, she doesn’t even need to apply a winning strategy.)

What went wrong here, when it was all looking so good for Player I? The rough answer is that the game $G'$ restricts far too much what Player I can do and places no restrictions on Player II. That’s all very well when we are trying to show that Player I has a winning strategy for the set of sequences that can result from a run of $G'$ , but when we try to show the same for Player II, the fact that Player I’s moves are so circumscribed in $G'$ is a disaster: it means that it is easy for Player I to make moves in $G$ that couldn’t have come from a run of $G'$ .

Another attempt to lift that doesn’t work

Suppose we try to imitate Martin’s proof that closed sets can be lifted, but show instead that all sets can be lifted. We define the auxiliary game $G'$ as follows. Player I declares a quasistrategy $\sigma$ . Player II then declares either an infinite sequence $u$ that’s compatible with $\sigma$ and belongs to $A^c$ or a quasistrategy $\tau$ for the tree defined by $\sigma$ such that all possible outcomes lie in $A$ . The difference between this and what we did before is that the sequence $u$ is infinite, rather than being a finite sequence with all its continuations in $A^c$ .

Actually, this is rather similar to the first attempt. The differences are that Player I declares a quasistrategy rather than a strategy, and instead of sequences that end up in $A$ , Player II plays quasistrategies that end up entirely in $A$ . But I think these will turn out to be minor variations, so I won’t discuss this after all — I’m almost certain that this is another example that works, but only if you assume the axiom of determinacy.

Determinacy can be thought of as a Ramsey property

There is a way of thinking of determinacy that I find quite helpful. Let us think of the payoff set $A$ as a 2-colouring of $[T]$ , the set of infinite paths in $T$ . To make this more vivid, I’ll reword it in colouring terms, so let’s say that we have coloured the paths in $[T]$ with two colours, red and blue, the red paths being precisely the paths in $A$ .

A typical Ramsey theorem tells us that we can find a monochromatic substructure of some kind — that is, a substructure that is nice in some way and has all its elements of the same colour. Sometimes we consider off-diagonal Ramsey theorems, where we want either a red substructure of one kind or a blue substructure of another kind.

Let’s define a I-tree to be a subtree $S$ of $T$ that contains the root and has the property that each vertex at even distance from the root has precisely one successor in $S$ , whereas for each vertex of $S$ at odd distance from the root, the successors in $S$ are the same as the successors in $T$ . Every strategy $\sigma$ for Player I defines a I-tree — the tree of all finite paths that can be obtained if Player I plays with the strategy $\sigma$ . The strategy $\sigma$ is a winning strategy if and only if all infinite paths in the corresponding I-tree $S$ are red.

Similarly, we can define II-trees, and once we have done so, the statement “ $A$ is determined” is equivalent to the statement, “Either there is a I-tree $S_1$ such that $[S_1]$ is red or there is a II-tree $S_2$ such that $[S_2]$ is blue.

The monochromatic structures we are looking at for this off-diagonal Ramsey theorem are particularly nice sets of paths.

There are quite strong parallels here with the infinite Ramsey theorem of Galvin and Prikry. Let us write $X^{(\omega)}$ for the set of all infinite subsets of $X$ . Then the Galvin-Prikry theorem says (or at least implies) that for every Borel subset $A$ of $\mathbb{N}^{(\omega)}$ (in the product topology) there is an infinite subset $X\subset\mathbb{N}$ such that either $X^{(\omega)}\subset A$ or $X^{(\omega)}\subset A^c$ . As with determinacy, to find any set that fails this theorem one needs to use the axiom of choice (or, to be more accurate, something like a non-principal ultrafilter, which is a strictly weaker assumption than the axiom of choice, but most naturally proved using the axiom of choice).

What happens if we try to use strategies instead of quasistrategies?

Going back to Martin’s proof itself, let’s try to understand what would go wrong if the players declared strategies in the places that they actually declare quasistrategies. We have sort of seen this — there are places in the proof where we need to deem a player to have played a certain quasistrategy. But was that just a convenience, or was it essential?

I’m considering the following auxiliary game. Player I’s first move is $(x_1,\sigma)$ , where now $\sigma$ is a strategy, and not just a quasistrategy. Player II either plays $(x_2,u)$ , where $u$ is a finite sequence consistent with $\sigma$ , all of whose continuations lie in $A^c$ , or $(x_2,\tau)$ , where $\tau$ is a strategy inside the tree corresponding to $\sigma$ .

The first thing to note here is that $\tau$ is effectively an infinite sequence $v$ . So let’s reword this to say that Player II plays $(x_2,\bullet)$ , where $\bullet$ is either a finite sequence $u$ with all its continuations in $A^c$ or an infinite sequence $v$ that lives in $A$ . In both cases, the sequence must be consistent with the strategy $\sigma$ declared by Player I.

In the first case, the players must play along $u$ and after that are released from all obligations. In the second case, they must play along $v$ .

Now let $\sigma'$ be a strategy for Player I in this auxiliary game $G'$ and let $(x_1,\sigma)$ be its first move. What infinite sequences can arise? They are all sequences $x$ with one of the following two properties:

1. $x$ has an initial segment $u$ consistent with $\sigma$ such that all continuations of $u$ lie in $A^c$ , and the rest of $x$ is consistent with the strategy $\sigma'$ , given the initial moves $(x_1,\sigma)$ and $(x_2,u)$ ;

2. $x$ is consistent with $\sigma$ and lies in $A$ .

If Player I has a winning strategy for the first class of sequence, then she plays it, and after reaching $u$ such that all continuations lie in $A^c$ , she does whatever $\sigma'$ dictates.

If Player I does not have a winning strategy for the first class of sequence, then in the Martin proof, she would deem Player II to be playing the canonical quasistrategy for the complement of that class. However, that option is not open to us if we aren’t allowed quasistrategies. So she has a problem.

But maybe it isn’t a huge problem, since in $G'$ she will be required to play consistently with $\sigma$ , whatever Player II does. Since $\sigma$ is a strategy rather than a quasistrategy, we don’t have to make any choices, and therefore don’t have to “deem” Player II to have declared any particular sequence $v$ .

What I’m saying here is that in the second case Player I should simply play the strategy $\sigma$ , but if Player II ever departs from the canonical quasistrategy and gets to a position where Player I can force a finite sequence $u$ of the first type, then Player I switches to doing that and continuing with $\sigma'$ . Otherwise, play continues for ever, consistently with $\sigma$ and producing an element $v$ of $A$ . So Player I can deem Player II to have declared that element.

So it seems as though quasistrategies are not yet essential. But now let’s think about Player II. If $\tau'$ is a $G'$ strategy for Player II, then it defines a map from Player I strategies $\sigma$ to finite sequences $u$ with continuations in $A^c$ and infinite sequences that live in $A$ , always consistent with $\sigma$ . Let $U$ be the set of finite sequences that can arise. In Martin’s proof, we then consider the canonical quasistrategy for avoiding $U$ , if Player I has such a thing. Call this $\sigma$ . Then Player II’s strategy for $G$ is roughly this. Assume that Player I is playing $\sigma$ and do whatever $\tau'$ dictates. If Player I ever departs from $\sigma$ , then force a sequence in $U$ .

If we are forced to consider strategies, then the above doesn’t make sense: $\tau'$ doesn’t dictate a response to a quasistrategy. So let’s just think about what sequences could possibly arise. For each strategy $\sigma$ declared by Player I that doesn’t produce some $u\in U$ , $\tau'$ will give rise to an infinite sequence $v$ that’s consistent with $\sigma$ .

I think that yet again we’re back in the situation where Player II does have a winning strategy for the appropriate set of sequences if we assume the axiom of determinacy, but otherwise doesn’t. To see that, just consider the case where $A=\emptyset$ . In this case, we never get the finite sequences — we just get for each strategy $\sigma$ an infinite sequence consistent with $\sigma$ , and we want to show that Player II has a winning strategy for the resulting set of sequences.

So I think the situation is that we need Player I to be able to play, at the very least, canonical quasistrategies for closed sets. And once that is permitted, I think it forces us to allow Player II to use quasistrategies as well. (I haven’t checked this, but at any rate the analysis for Player I above used in an important way the fact that $\sigma$ was a strategy and not just a quasistrategy.)

Another connection with Ramsey theory

This one’s a bit more of a stretch, but I find it quite useful. It takes a while to explain.

To begin with I want to consider a simple way of reformulating Ramsey statements that is sometimes useful. Let $\mathcal{A}$ be a collection of subsets of a set $X$ . We call $\mathcal{A}$ an up-set if whenever $A\in\mathcal{A}$ and $A\subset B$ we have $B\in\mathcal{A}$ . Sometimes up-sets are called monotone set systems. Given an up-set $\mathcal{A}$ we can form an up-set $\mathcal{A}^*$ by taking the set of all sets $C$ such that $A\cap C\ne\emptyset$ for every $A\in\mathcal{A}$ . We call such a set $C$ a transversal of $\mathcal{A}$ . Note that $\mathcal{A}^{**}=\mathcal{A}$ , so this is a form of duality. It is trivial that $\mathcal{A}\subset\mathcal{A}^{**}$ . In the other direction, if $B\notin\mathcal{A}$ , then no subset of $B$ can belong to $\mathcal{A}$ (since $\mathcal{A}$ is an up-set) and therefore $X\setminus B$ is a transversal of $\mathcal{A}$ that does not intersect $B$ .

Now let us take a typical Ramsey statement, such as van der Waerden’s theorem. The statement that for every 2-colouring of $\mathbb{N}$ there is a monochromatic arithmetic progression of length $k$ can be reformulated as follows. Let $\mathcal{A}$ be the set of all subsets of $\mathbb{N}$ that contain an arithmetic progression of length $k$ . If no set in $\mathcal{A}$ consists entirely of blue elements, then the set of red elements is a transversal of $\mathcal{A}$ , and conversely. Therefore, we need to prove that every transversal of $\mathcal{A}$ contains a progression of length $k$ — that is, belongs to $\mathcal{A}$ .

This reformulation can be applied to all (sufficiently conventional) Ramsey statements. They tell us that every transversal of a certain up-set must contain a set of a certain kind.

Now let’s consider what it means to lift a game not just to a clopen game but to a game whose outcome is decided after the first move of each player. (Recall that we showed that every closed game can be lifted to a clopen game of this kind.) I want to concentrate particularly on the condition that there should be a map $\psi$ from $G'$ strategies to $G$ strategies such that every run of $G$ consistent with $\psi(\sigma)$ should be the image of some run of $G'$ consistent with $\sigma$ .

I want to go further still and consider the case where the tree $T'$ of $G'$ consists of certain paths of the form $((x_1,u),(x_2,v),x_3,x_4,\dots,x_k)$ , where $(x_1,\dots,x_k)$ is a path in $T$ (and $u$ and $v$ can be thought of as “extra information” of some kind). Here $u$ belongs to some set $U$ and $v$ belongs to some set $V(u)$ .

I haven’t thought whether this is a genuine further restriction or whether it’s more or less a WLOG. But it’s the situation I want to think about.

After the first two moves have been played, the possible further moves can be thought of as a subtree of $T_{x_1,x_2}$ (which itself is the set of all descendants of $x_2$ ). Let us call this subtree $T_{u,v}$ and let $T_u=\bigcup_{v\in V(u)}T_{u,v}$ . Then we can think of the extra information $u$ as the tree $T_u$ and each $T_{u,v}$ as a subtree of $T_u$ . So the way that $G'$ works is this. Player I plays a subtree $T_u$ of $T$ , Player II plays a subtree $T_{u,v}$ of $T_u$ , and after that the game is played in the subtree $T_{u,v}$ .

I stress that I certainly don’t mean that Player I plays an arbitrary subtree of $T$ or that Player II plays an arbitrary subtree of $T_u$ . Rather, there will be some class of subtrees that Player I is allowed to choose from, and for each $T_u$ there will be some class of subtrees that Player II is allowed to choose from. Let us call a subtree that belongs to the class it needs to belong to valid.

A small remark here is that we don’t actually need to think about the tree $T_u$ . We could regard Player I as playing the set $\{T_{u,v}:v\in V(u)\}$ and Player II choosing a tree from that set. Indeed, sometimes it is clearer to think of things this way.

It will be convenient to adopt the following definition. If $T$ is an infinite rooted tree, then I’ll define a I-subtree of $T$ to be a subtree $S$ that contains the root such that every vertex at even distance from the root has exactly one successor in $S$ and every vertex at odd distance has the same successors in $S$ as it has in $T$ . (Equivalently, it is the tree of finite sequences that could result from Player I playing a certain strategy.) We’ll also define a II-tree in a similar way.

Now let us look at the lifting property. Let $\sigma'$ be a strategy for Player I for $G'$ and let $(x_1,u)$ be its first move. Then $T_u$ is the subtree chosen by Player I (from a set of trees $\{T_u:u\in U\}$ ) in which the rest of the game $G'$ will take place.

What possible sequences can arise? Well, at the next move, Player II plays some $(x_2,v)$ , and $\sigma'$ will give Player I a strategy for playing in the tree $T_{u,v}$ . The set of sequences consistent with this strategy is an arbitrary I-subtree $R_{u,v}$ of $T_{u,v}$ . Or rather, it is a set of the form $[R_{u,v}]$ , where $R_{u,v}$ is a I-subtree of $T_{u,v}$ . And we need that however Player I chooses these I-subtrees $R_{u,v}$ , their union will contain a I-subtree of $T$ .

That is the same as saying the following. Let $R_u$ be a pruned subtree of $T_u$ such that for every $v$ , $R_u\cap T_{u,v}$ contains $R_{u,v}$ for some I-subtree $R_{u,v}$ of $T_{u,v}$ . Then $R_u$ contains a I-subtree of $T$ .

We can think of this as a weak Ramsey statement about the set of trees $\{T_{u,v}:v\in V(u)\}$ . Instead of saying that every transversal of this set contains a I-subtree of $T$ , we are assuming something stronger than the transversality property: we require that $R_u\cap T_{u,v}$ is not just non-empty, but contains a I-subtree of $T_{u,v}$ .

I won’t do it here, but if one translates this into a statement about red-blue colourings, it says something of the following flavour: either the blue set contains a structure of one kind or the red set contains a large subset of a structure of another kind. It is in that sense that it is a “weak” Ramsey theorem.

This may seem a bit artificial, but actually weak Ramsey statements can be useful, as I once found out myself, when to solve a problem in Banach spaces I formulated and proved a weak Ramsey statement that said something along the following lines: if you 2-colour the sequences (of a certain kind) in a Banach space, then there is a subspace such that all the sequences in that subspace are of one colour, or Player I has a winning strategy in a certain game for producing sequences of the other colour.

So far I’ve analysed the lifting property for Player I strategies. The analysis for Player II strategies is somewhat similar, but different enough that I should give the details.

A strategy for Player II in the game $G'$ consists in selecting a way of choosing, for every valid subtree $T_u$ , a valid subtree $T_{u,v}$ and after that a strategy for playing the game defined by $T_{u,v}$ . (Again, I don’t really care what the payoff set is — strategies, quasistrategies, subtrees etc. are all defined without reference to the payoff set.) We can think of that strategy as a II-subtree $S_{u,v}$ of $T_{u,v}$ .

The property we need is this. However Player II chooses the subtrees $S_{u,v}$ , their union will contain a II-subtree of $T$ .

In a moment I’ll state as concisely as I can the two weak Ramsey properties that we require of our sets of valid subtrees in order to have a lift of anything at all. But before I do that, let me now comment about where payoff sets fit in. They add a huge extra constraint: if $A$ is the payoff set, then for every valid subtree $T_{u,v}$ we must have either $[T_{u,v}]\subset A$ or $[T_{u,v}]\subset A^c$ . So the question is whether we can combine this constraint with the weak Ramsey constraints. In the next section, I’ll give a couple of simple examples of classes of valid subtrees that satisfy the Ramsey constraint.

Summary of the conclusions reached in the previous section

Let $T$ be a rooted pruned tree. Suppose we define an auxiliary tree $T'$ as follows. Its first layer of vertices consists of labels $u\in U$ that standa for subtrees $T_u$ of $T$ (where by subtree I mean pruned subtree that contains the root). Then each successor of $u$ is a label $v\in V$ that stands for a subtree $T_{u,v}$ of $T_u$ . The descendants of each $v$ are given by a copy of $T_{u,v}$ .

We are interested in the following question. Under what conditions is it possible to map every strategy $\sigma'$ for $T'$ to a strategy $\sigma$ for $T$ such that every run of $\sigma$ is the image (under the obvious map) of a run of $\sigma'$ ? The conclusion I reached was this.

1. For every Player I strategy to be mappable in this sense we need that for every $u$ the set system $\{T_{u,v}:v\in V(u)\}$ has the following weak Ramsey property: every tree $R_u$ such that $R_{u,v}\cap T_{u,v}$ contains a I-subtree of $T_{u,v}$ for every $v\in V(u)$ contains a I-subtree of $T$ .

2. For every Player II strategy to be mappable in this sense we need that if for each $u$ we pick some $v(u)$ and a II-subtree $S_u$ of $T_{u,v(u)}$ , then the union of the $S_u$ contains a II-subtree of $T$ .

Here are a couple of extreme examples to illustrate this. First, let’s take the case where the trees $T_u$ are all possible I-subtrees of $T$ and the trees $T_{u,v}$ are all possible infinite paths in $T_u$ . We have looked at this case already, but in a different language.

Trivially if $T_u$ is a subtree of $T$ and all the infinite paths in $T_u$ belong to $R_u$ , then $R_u$ contains a I-subtree of $T$ , since it actually equals $T_u$ .

As for the second property, if for each I-subtree $T_u$ we can find an infinite path that’s a subset of a tree $R$ , then Player I does not have a winning strategy for $[R]^c$ , which, if we allow ourselves the axiom of determinacy, tells us that Player II has a winning strategy for $[R]$ , which implies that $R$ contains a II-subtree of $T$ and gives us the required property.

So as we saw earlier, to show that this system of trees works requires the axiom of determinacy.

As a second example, let’s take the case where there is only one subtree $T_u$ and it’s the whole of $T$ , and where the subtrees $T_{u,v}$ are all II-subtrees of $T$ .

Now the premise of the first weak Ramsey property is that every II-subtree $T_v$ of $T$ contains a I-subtree that is a subset of a certain tree $R$ . But a I-subtree of a II-subtree is just an infinite path, so this says that $[R]\cap[T_v]\ne\emptyset$ for every $v$ . Determinacy gives us that $R$ contains a I-subtree, as required. Without determinacy we can’t conclude that it does.

The second property says in this case that if we choose a II-subtree of a II-subtree of $T$ , then it must contain a II-subtree of $T$ , which is trivial, since the only II-subtree of a given II-subtree is that II-subtree itself.

What happened to the condition that what $\psi(\sigma)$ does for the first $n$ moves must depend only on what $\sigma$ does for the first $n$ moves?

I have to admit that I had rather forgotten about that. I now want to think about how much difference it makes if we add it in. In particular, I’d like to think about the example where Player I chooses an arbitrary strategy and Player II chooses an arbitrary sequence consistent with that strategy — the game where we used the axiom of determinacy to prove the lifting property.

Given a Player II strategy $\sigma'$ for $G'$ , here’s how we “defined” $\psi(\sigma')$ . We noted that $\sigma'$ gave us a map $\tau$ from Player I strategies $\sigma$ (for $G$ ) to sequences compatible with those strategies, and that the axiom of determinacy implies that the resulting sequences must give us a set for which Player II has a winning strategy $\rho$ (since Player I trivially hasn’t got a winning strategy for the complement). The strategy $\rho$ depends only on the map $\tau$ , which depends only on what $\sigma'$ does for Player II’s first move. So it seems as though we are safe here.

That’s a relief. The situation for Player I’s strategies is even simpler. Recall that Player I just plays in $G$ the strategy $\sigma$ that she declares in her first $G'$ move. So once again, what $\psi(\sigma')$ does for the first $n$ moves depends only on what $\sigma'$ does for the first move.

How do the various conditions sit in tension with each other?

In this section I want to do a rather simple exercise: I want to consider various potential monotonicity statements. Here once again are the properties I am interested in of the sets of subtrees $\{T_{u,v}:v\in V(u)\}$ .

1. For every $u$ the set system $\{T_{u,v}:v\in V(u)\}$ has the following property: every tree $R_u$ such that $R_u\cap T_{u,v}$ contains a I-subtree of $T_{u,v}$ for every $v\in V(u)$ contains a I-subtree of $T$ .

2. If for each $u$ we pick some $v(u)$ and a II-subtree $S_u$ of $T_{u,v(u)}$ , then the union of the $S_u$ contains a II-subtree of $T$ .

I want to answer questions like, “Does it help to have more sets $\{T_{u,v}:v\in V(u)\}$ ?” and “Does it make things easier if the trees $T_{u,v}$ are bigger?”

For property 1, since we require it to hold for every set $\{T_{u,v}:v\in V(u)\}$ , it is easier if there are fewer such sets. Also, if we add more trees $T_{u,v}$ to one of those sets, it makes the premise harder to satisfy, and therefore makes the conclusion more likely to hold. This again is helpful for property I.

The monotonicity with respect to the trees $T_{u,v}$ themselves is a subtler matter. (In fact, I wrote an earlier draft of this post where the subtlety escaped me. I’ve decided in this instance that it is too much to expect someone to read through a whole lot of mistaken text before I come clean and admit that it is mistaken. So what you are getting here is not my actual thought processes but a later tidying up. But had I been more careful in the first place, then these might have been my thought processes I suppose.) The question we are asking is this. For a fixed set $R_u$ , what makes it easier for $R_u\cap T_{u,v}$ to contain a I-subtree of $T_{u,v}$ and what makes it harder? Basically, it is easier if Player I has more moves available but harder if Player II has more moves available.

That observation motivates the definition of two orderings on trees. Let’s write $T_1\subset_IT_2$ if $T_1$ is a subtree of $T_2$ with the following property: given any path in $T_2$ , if it ever leaves $T_1$ , then the first point at which it does so is at an odd distance from the root — that is, it offers Player I a move in $T_2$ that she does not have in $T_1$ . Similarly, $T_1\subset_{II}T_2$ if the same is true but with “odd” replaced by “even” (or Player I replaced by Player II). I’ll call $T_2$ I/II-larger than $T_1$ if $T_1\subset_1T_2/T_1\subset_{II}T_2$ .

For property 1 to be more likely to hold, we want the premise to be less likely to hold, so we want $R_u\cap T_{u,v}$ to be less likely to contain a I-subtree of $T_{u,v}$ . Therefore, we prefer $T_{u,v}$ to be I-smaller and II-bigger.

Now let us turn attention to property 2. This time it is helpful if there are more sets $\{T_{u,v}:v\in V(u)\}$ . It is also helpful if there the sets $\{T_{u,v}:v\in V(u)\}$ are smaller, since that makes it harder to create a counterexample to property 2. And it is also helpful if II-subtrees $S_u\subset T_{u,v(u)}\}$ are harder to come by, for which we prefer the trees $T_{u,v}$ to be II-smaller and I-bigger.

In every case, the monotonicity goes in opposite directions for properties 1 and 2. This is reassuring, since otherwise there would probably be some “collapse” where we would say something like, “Without loss of generality all the $T_{u,v}$ are equal to $T$ ,” and end up with a trivial definition.

Why do we need the lemma that closed sets can be lifted? (Section added later.)

Since putting up this post earlier today I have had the following thought. Every open set is a countable union of basic open sets, and every basic open set is also closed. Since basic open sets are clopen, they can trivially be lifted — to themselves. So why not start the “induction” at the basic open sets, and thereby avoid the need for the fairly complicated lemma that tells us that closed sets can be lifted to clopen sets?

It took me a while to realize the answer to this. It comes in the innocuous-looking final step of the argument for dealing with countable intersections. Recall that the technique was to find a simultaneous lifting (or rather $k$ -lifting) of all the sets to be intersected, so that they all become clopen. Then we argue that their intersection is at least closed, so it too can be lifted, by the complicated lemma. And that gives us our lift for the original intersection.

So the complicated lemma about lifting closed sets is essential at the point where we argue that an intersection of the clopen sets coming from the simultaneous lifting can be lifted.

I find this a useful point to highlight, since it shows that the lemma (lifting closed sets) is not just there to deal with the base case — it is driving the inductive step as well. So one can view the proof as a multiple (indeed, transfinitely multiple) application of that lemma.

About these ads

This entry was posted on September 16, 2013 at 10:38 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 V”

jaywillmath Says:
September 20, 2013 at 1:47 am | Reply
I’ve really enjoyed this series of posts, but then, I do descriptive set theory. One thing I’m still curious about: what got you looking at Borel determinacy in the first place?
william e emba Says:
September 24, 2013 at 2:55 pm | Reply
Something like the lifting of closed sets must be invoked at every step of the induction, because of Friedman’s theorem on the complexity of Borel determinacy.

Gowers's Weblog