4
$\begingroup$

I was reading the introduction to the actual proof of Borel Determinacy in Kechris' "Classical Descriptive Set Theory". Here is an extract: enter image description here

What I don't get is why we define $\varphi$ in this way and why should it be substancially different from $\pi$. They are of course different since, as I'll explain, their domain is very different, but the their image is basically the same, as I'm going to argue. First of all let's define precisely what is a strategy (wlog for the first player I) in $G(T,X)$. A strategy $\sigma$ is a pruned subtree $\sigma \subseteq T$, such that:

  • $\exists! s_0$ s.t. $(s_0) \in \sigma$
  • $\forall (s_0,s_1,\dots,s_{2n}) \in \sigma \ [(s_0,s_1,\dots,s_{2n},s_{2n+1}) \in T \Rightarrow (s_0,s_1,\dots,s_{2n},s_{2n+1}) \in \sigma]$
  • $\forall (s_0,s_1,\dots,s_{2n-1}) \in \sigma \ \exists! (s_0,s_1,\dots,s_{2n-1},s_{2n}) \in T [(s_0,s_1,\dots,s_{2n-1},s_{2n}) \in \sigma]$

Intuitively, the strategy of the first player must take into account every possible move of the second player and must have a unique response to every move of his. Let's denote by $ \Sigma(T)$ the set of all strategies over $T$ and by $\Sigma_n (T)$ the set of all partial strategies of length $n$. Then we can see $\varphi$ as a function $$\varphi: \Sigma(T') \cup \Sigma_n (T') \rightarrow \Sigma(T) \cup \Sigma_n (T)$$

such that:

  1. $\varphi(\Sigma_n (T')) \subseteq \Sigma_n (T)$ (that is it sends partial strategies of length n to partial strategies of the same length)
  2. $\varphi(\Sigma (T')) \subseteq \Sigma(T)$
  3. Given $\sigma_n \in \Sigma_n (T')$ and $\sigma_m \in \Sigma_m (T')$ with $\sigma_n \subseteq \sigma_m$ then we have $\varphi(\sigma_n) \subseteq \varphi(\sigma_m)$
  4. Given $\sigma \in \Sigma(T')$ then $\varphi(\sigma) = \bigcup_n \varphi(\sigma|_n)$ with $\sigma|_n$ denoting the n-th partial strategy induced by $\sigma$.

Condition iv) of the text also asks that:

  1. For all strategies $\sigma \in \Sigma(T')$ we have $[\varphi(\sigma)] \subseteq \pi([\sigma])$

So know I claim that, given what I just wrote (that represent faithfully what it's written in Kechris' book), for all strategies (and partial strategies) $\sigma$ we have $\varphi(\sigma) = \pi(\sigma)$. In fact we have that by 5) $[\varphi(\sigma)]\subseteq \pi([\sigma]) = [\pi(\sigma)]$. Then let's notice that, given $s \in \varphi(\sigma)$, since each strategy is a pruned tree, then we have that $\exists x \in [\varphi(\sigma)]$ s.t. $s = x|_n$. Moreover, since $x$ also belongs to $[\pi(\sigma)]$ we have that $x|_n \in \pi(\sigma)$ and therefore $s \in \pi(\sigma)$. So we've show that $$\varphi(\sigma) \subseteq \pi(\sigma)$$. Now we notice also that $$\pi(\Sigma(T')) \subseteq \Sigma(T)$$ So also $\pi$ sends (partial) strategies to (partial) strategies. This is not a direct consequence of the definition of $\pi$, which by itself does not guarantee this, but by the requirement iv) of the text (the fifth point I've written) we need to assume this. Otherwise the only way $\pi(\sigma)$ has to not be a strategy is to avoid to specify some possible player II's moves (in some odd layer), but in this case $\varphi(\sigma)$, given what we've just said ($\varphi(\sigma) \subseteq \pi(\sigma)$), needs to avoid to specify those same moves, in contradition with its being a strategy (by 2.). Said this I claim that, given two strategies $\sigma, \theta \in \Sigma (T)$ with $\sigma \subseteq \theta$ then $\sigma = \theta$. This is easy to prove by induction:

  • $(a_0) \in \theta \Rightarrow (a_0) \in \sigma$, this is the basis for the induction
  • Given that $\sigma|_{n-1} = \theta|_{n-1}$ then, given the definition of strategy and that by hypothesis $\sigma \subseteq \theta$, it is evident that, both when $n$ is even (player I has to play) or odd, $\sigma|_n = \theta|_n$

So we end up with $\varphi(\sigma) = \pi(\sigma)$ for all strategies $\sigma \in \Sigma(T')$. Then, if what i've written in right, why don't we define a Covering Game as follows:

A Covering of $T$ is a couple $(\tilde{T}, \pi)$ where:

  1. $\tilde{T}$ is a non-empty pruned tree (on some $\tilde{A}$)
  2. $\pi: \tilde{T} \rightarrow T$ is monotone with $length(s) = length(\pi(s))$. Thus $\pi$ gives rise to a continuous (actually Lipschitz) function from $[\tilde{T}]$ into $[T]$ also denoted as $\pi$.

Strategies $\tilde{\sigma} \in \Sigma(\tilde{T})$ are sent to $\pi(\tilde{\sigma})$ which is going to be a strategy in $T$. $\pi$ in mapping strategies satisfies all the requirements specified in the previous definition with respect to $\varphi$. So

  • $\pi$ maps partial strategies to partial strategies in a monotone and lenght preserving way.
  • Of course $[\pi(\tilde{\sigma})] = \pi([\tilde{\sigma}])$

What is wrong with this new definition of covering?

EDIT: And even if what I wrote before introducing this new definition was flawed, why wouldn't we use this new definition nonetheless? My intuition regarding the definition of Covering Game is that the requests over $\pi$ (continuous and length preserving) are necessary to deal with k-coverings and unravelings, but when it comes to $\varphi$ our only concern is that it maps strategies into strategies and, more important, winning strategies into winning strategies. So, even if my argument is wrong, and $\pi$ does not cover every possible $\varphi$ that satisfies the book's definition, why would we care? The strategy mapping provided by $\pi$ already does the job.

$\endgroup$
2
+50
$\begingroup$

One problem with your argument is that, in general, $\pi$ does not need to send strategies to strategies. One of the particular $\pi$s that appear in the proof of Martin's theorem in Kechris (Lemma 20.7, in the case of $0$-coverings) has the following form: $$ \pi((x_0,A),(x_1,B),x_2,\dots,x_l)) = (x_0,\dots,x_l). $$ It is not at all obvious that the direct image by $\pi$ of a strategy $\sigma$ for Player I in $T'$ is a strategy, since the second move of I in play in $T'$ most probably depends on what the object $B$ is. This information is disregarded by the projection $\pi$, and hence $\pi(\sigma)$ will likely contain two successors of $(x_0,x_1)$.

Another thing is that it is not so clear is the equality $[\pi(\sigma)] = \pi([\sigma])$; from the beginning, it is suspect that the image of a closed set is again closed. More concretely, I don't regard as obvious the fact that a play in $[\pi(\sigma)]$ must arise as the image of a play according to $\sigma$.

On a side note, again your specification of $\phi$ is imprecise; it should be like this: $$ \textstyle\varphi: \Sigma(T') \cup \bigcup_n\Sigma_n (T') \rightarrow \Sigma(T) \cup \bigcup_n\Sigma_n (T). $$

Finally, it should be worth looking at Gowers' account of the proof at his blog; the elucidation of the role of $\varphi$ (called $\psi$ there) takes place in the third post of the series.


Note: I'm leaving my older answer below; the question was a bit defaced, so it is no longer relevant, but I feel reluctant to delete my previous work.


Let me first point out that your definition of the domain of $\varphi$ looks a bit strange. It seems that what you're using below is something like $$ \mathcal{U}(T) = \textstyle\bigcup\{\{\sigma\}\times\sigma : \sigma \in \Sigma(T)\}, $$ since you write $\varphi(s)=\varphi(\sigma,s)$ where $s\in\sigma$. I think this is where the confusion lies: $\varphi$ can't be construed as a map from sequences to sequences. It really sends finite trees (as in partial strategies in Kechris) to finite trees of the same height. So it doesn't make sense to write something like “$\varphi((s_0,s_1))$.”

An instance of this might be given as follows. Consider a game on $\mathbb{N}$, and two strategies for Player I: $\sigma$ instructs to “play 1 always;” and $\sigma'$ states “if the first move of your opponent is 2, move 2 onward; otherwise, play 1 always”. Now $\varphi$ may map strategies according to “switch the moves in response to a 0 in the first move of Player II with those in response to a 2 in that move.” This definition is monotone as required, but considering $\varphi(\sigma)$ and $\varphi(\sigma')$ it should be clear that there is no consistent choice for something as “$\varphi((1,0,1))$.”

$\endgroup$
9
  • $\begingroup$ Thanks for the answer! I edited the question and added an EDIT to respond to your answer. $\endgroup$ – Lorenzo Jun 24 '19 at 14:46
  • $\begingroup$ I added a new edit so to make my doubts more intelligible. $\endgroup$ – Lorenzo Jun 24 '19 at 15:42
  • 1
    $\begingroup$ In your "Edit 2", $\pi$ sends strategies to strategies (I understand, by direct image) and thus it is an example of some $\varphi$s. But many other choices of $\varphi$ can't be obtained in this way. I claim that the example I provided is not obtainable this way. $\endgroup$ – Pedro Sánchez Terraf Jun 24 '19 at 16:16
  • 1
    $\begingroup$ With respect to your example, what are $\pi$ and $T$? By the way it is intuitive what you are saying, but the problem is in fact that, if my reasonment is correct, there are actually no other choices of $\varphi$. $\endgroup$ – Lorenzo Jun 24 '19 at 16:28
  • 1
    $\begingroup$ @Lorenzo Hmm, I see that this $\varphi$ is not relevant (there seem to be no adequate $\pi$). I'll give it a thought. $\endgroup$ – Pedro Sánchez Terraf Jun 24 '19 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.