Clarify how we can exchange the players' roles.

1 files changed, 148 insertions, 96 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 2226df7..71e4383 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1297,14 +1297,15 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 Soit $X$ un ensemble non vide quelconque (à titre indicatif, les cas
 $X = \{0,1\}$ et $X = \mathbb{N}$ seront particulièrement
 intéressants).  Soit $A$ un sous-ensemble de $X^{\mathbb{N}}$.  Le
-\textbf{jeu de Gale-Stewart} $G_X(A)$ est défini de la manière
-suivante : Alice et Bob choisissent tour à tour un élément de $X$
-(autrement dit, Alice choisit $x_0 \in X$ puis Bob choisit $x_1 \in X$
-puis Alice choisit $x_2 \in X$ et ainsi de suite).  Ils jouent un
-nombre infini de tours, « à la fin » desquels la suite
-$(x_0,x_1,x_2,\ldots)$ de leurs coups définit un élément de
-$X^{\mathbb{N}}$ : si cet élément appartient à $A$, Alice
-\textbf{gagne}, sinon c'est Bob (la partie n'est jamais nulle).
+\textbf{jeu de Gale-Stewart} $G_X(A)$ (ou $G_X^{\mathrm{a}}(A)$,
+cf. \ref{remark-player-names}) est défini de la manière suivante :
+Alice et Bob choisissent tour à tour un élément de $X$ (autrement dit,
+Alice choisit $x_0 \in X$ puis Bob choisit $x_1 \in X$ puis Alice
+choisit $x_2 \in X$ et ainsi de suite).  Ils jouent un nombre infini
+de tours, « à la fin » desquels la suite $(x_0,x_1,x_2,\ldots)$ de
+leurs coups définit un élément de $X^{\mathbb{N}}$ : si cet élément
+appartient à $A$, Alice \textbf{gagne}, sinon c'est Bob (la partie
+n'est jamais nulle).
 
 Dans ce contexte, les suites finies $(x_0,\ldots,x_{\ell-1})$
 d'éléments de $X$ s'appellent les \textbf{positions} (y compris la
@@ -1318,43 +1319,106 @@ du jeu $G_X$.  Une \textbf{partie} ou
 de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$.
 \end{defn}
 
+\thingy\label{remark-player-names} Il peut arriver qu'on ait envie de
+faire commencer la partie à Bob.  Il va de soi que ceci ne pose aucune
+difficulté, il faudra juste le signaler le cas échéant.
+
+De façon générale, sauf précision expresse du contraire, « Alice » est
+le joueur qui cherche à jouer dans l'ensemble $A$ tandis que « Bob »
+est celui qui cherche à jouer dans son complémentaire $B :=
+X^{\mathbb{N}} \setminus A$.  Le « premier joueur » est celui qui
+choisit les termes pairs de la suite, le « second joueur » est celui
+qui choisit les termes impairs.
+
+On pourra noter $G_X^{\mathrm{a}}(A)$ lorsqu'il est souhaitable
+d'insister sur le fait qu'Alice joue en premier, et
+$G_X^{\mathrm{b}}(A)$ lorsqu'on veut indiquer que Bob joue en
+premier : formellement, le jeu $G_X^{\mathrm{b}}(A)$ est le même que
+$G_X^{\mathrm{a}}(X^{\mathbb{N}}\setminus A)$ si ce n'est que les noms
+des joueurs sont échangés.
+
 \begin{defn}
 Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une
-\textbf{stratégie} pour Alice (resp. Bob) est une fonction $\varsigma$
-qui à une suite finie (=position) de longueur paire (resp. impaire)
-d'éléments de $X$ associe un élément de $X$, autrement dit une
-fonction $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell}\big) \to X$
-(resp. $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell+1}\big) \to X$).
+\textbf{stratégie} pour le premier joueur (resp. le second joueur) est
+une fonction $\varsigma$ qui à une suite finie (=position) de longueur
+paire (resp. impaire) d'éléments de $X$ associe un élément de $X$,
+autrement dit une fonction $\big(\bigcup_{\ell=0}^{+\infty}
+X^{2\ell}\big) \to X$ (resp. $\big(\bigcup_{\ell=0}^{+\infty}
+X^{2\ell+1}\big) \to X$).
 
 Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G_X$
 on a $\varsigma((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ pair (y
 compris $\varsigma(()) = x_0$ en notant $()$ la suite vide), on dit
-qu'Alice a joué la partie selon la stratégie $\varsigma$ ; de même,
-lorsque $\tau((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ impair, on
-dit que Bob a joué la partie selon la stratégie $\tau$.
-
-Si $\varsigma$ et $\tau$ sont deux stratégies pour Alice et Bob
-respectivement, on définit $\varsigma \ast \tau$ comme la partie jouée
-lorsque Alice joue selon $\varsigma$ et Bob selon $\tau$ : autrement
-dit, $x_i$ est défini par $\varsigma((x_0,\ldots,x_{i-1}))$ si $i$ est
-pair ou $\tau((x_0,\ldots,x_{i-1}))$ si $i$ est impair.
-
-Donnée une partie $A$ de $X^{\mathbb{N}}$, la stratégie $\varsigma$
-pour Alice est dite \textbf{gagnante} (dans $G_X(A)$) lorsque Alice
-gagne toute partie où elle joue selon $\varsigma$.  La stratégie
-$\tau$ pour Bob est dite \textbf{gagnante} lorsque Bob gagne toute
-partie où il joue selon $\tau$.  Lorsque l'un ou l'autre joueur a une
-stratégie gagnante, le jeu est dit \textbf{déterminé}.
+que le premier joueur a joué la partie selon la
+stratégie $\varsigma$ ; de même, lorsque $\tau((x_0,\ldots,x_{i-1})) =
+x_i$ pour chaque $i$ impair, on dit que le second joueur a joué la
+partie selon la stratégie $\tau$.
+
+Si $\varsigma$ et $\tau$ sont deux stratégies pour le premier et le
+second joueurs respectivement, on définit $\varsigma \ast \tau$ comme
+la partie jouée lorsque le premier joueur joue selon $\varsigma$ et le
+second selon $\tau$ : autrement dit, $x_i$ est défini par
+$\varsigma((x_0,\ldots,x_{i-1}))$ si $i$ est pair ou
+$\tau((x_0,\ldots,x_{i-1}))$ si $i$ est impair.
+
+Si on se donne une partie $A$ de $X^{\mathbb{N}}$ et qu'on convient
+qu'Alice joue en premier : la stratégie $\varsigma$ pour Alice est
+dite \textbf{gagnante} (dans $G_X^{\mathrm{a}}(A)$) lorsque Alice
+gagne toute partie où elle joue selon $\varsigma$ comme premier
+joueur, et la stratégie $\tau$ pour Bob est dite gagnante lorsque Bob
+gagne toute partie où il joue selon $\tau$.  Lorsque l'un ou l'autre
+joueur a une stratégie gagnante, le jeu $G_X^{\mathrm{a}}(A)$ est dit
+\textbf{déterminé}.
 \end{defn}
 
-\thingy Il peut arriver qu'on ait envie d'échanger les rôles d'Alice
-et Bob, c'est-à-dire soit de faire commencer la partie à Bob, soit de
-définir le jeu par l'ensemble $B$ des suites qui font gagner Bob (et
-qui est simplement $X^{\mathbb{N}} \setminus A$), soit les deux.  Il
-va de soi que ceci ne pose aucune difficulté, il faudra juste le
-signaler le cas échéant.
+\thingy\label{unshifting-notation} Introduisons la notation suivante :
+si $\underline{x} := (x_0,\ldots,x_{\ell-1})$ est une suite finie
+d'éléments de $X$ et si $A$ est un sous-ensemble de $X^{\mathbb{N}}$,
+on notera $\underline{x}^\$ A$ l'ensemble des suites $(x_\ell,
+x_{\ell+1}, \ldots) \in X^{\mathbb{N}}$ telles que
+$(x_0,\ldots,x_{\ell-1}, x_\ell, \ldots)$ appartienne à $A$.
+Autrement dit, il s'agit de l'image réciproque de $A$ par
+l'application $X^{\mathbb{N}} \to X^{\mathbb{N}}$ qui insère
+$x_0,\ldots,x_{\ell-1}$ au début de la suite.
+
+On utilisera notamment cette notation pour une suite à un seul terme :
+si $x\in X$ alors $x^\$ A$ est l'ensemble des $(x_1,x_2,x_3,\ldots)
+\in X^{\mathbb{N}}$ telles que $(x,x_1,x_2,\ldots) \in A$.  (Ainsi, si
+$\underline{x} := (x_0,\ldots,x_{\ell-1})$, on a $\underline{x}^\$ A =
+x_{\ell-1}^{\$} \cdots x_1^{\$} x_0^{\$} A$.)
+
+\thingy\label{gale-stewart-positions-as-games} Toute position
+$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart peut être considéré
+comme définissant un nouveau jeu de Gale-Stewart consistant à jouer
+\textbf{à partir de là}, c'est-à-dire, comme si les $\ell$ premiers
+coups étaient imposés.
+
+La notation \ref{unshifting-notation} permet d'en donner une
+définition formelle : la position $\underline{x} :=
+(x_0,\ldots,x_{\ell-1})$ du jeu $G_X^{\mathrm{a}}(A)$ (où Alice joue
+en premier) sera considérée comme définissant le jeu
+$G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair (=c'est
+à Alice de jouer), et $G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque
+$\ell$ est impair (=c'est à Bob de jouer).  Autrement dit, les joueurs
+choisissent $x_{\ell},x_{\ell+1},x_{\ell+2},\ldots$, on insère les
+coups imposés $x_0,\ldots,x_{\ell-1}$ au début de la partie, et on
+regarde si la suite tout entière appartient à $A$ (ce qui revient à
+regarder si la suite choisie appartient à $\underline{x}^\$ A$) pour
+déterminer le gagnant.
+
+(Symétriquement, bien sûr, la position $\underline{x}$ du jeu
+$G_X^{\mathrm{b}}(A)$ sera considérée comme définissant le jeu
+$G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair, et
+$G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.)
 
-\smallbreak
+\thingy\label{gale-stewart-winning-positions} On dira qu'une position
+$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart $G_X(A)$ est
+\textbf{gagnante} pour Alice lorsque Alice a une stratégie gagnante
+dans le jeu qui consiste à jouer à partir de cette position
+(cf. \ref{gale-stewart-positions-as-games}).  On définit de meme une
+position gagnante pour Bob.
+
+\medbreak
 
 La proposition suivante est presque triviale et signifie qu'Alice (qui
 doit jouer) possède une stratégie gagnante si et seulement si elle
@@ -1363,23 +1427,19 @@ une stratégie gagnante, et Bob en possède une si et seulement si
 n'importe quel coup $x$ joué par Alice amène à une position d'où il
 (Bob) a une stratégie gagnante :
 \begin{prop}\label{strategies-forall-exists-lemma}
-Soit $X$ un ensemble non vide et $A \subseteq X^{\mathbb{N}}$.  Pour
-$x \in X$, on notera $x^{\$} A$ l'ensemble des suites
-$(x_1,x_2,x_3,\ldots) \in X^{\mathbb{N}}$ telles que
-$(x,x_1,x_2,\ldots) \in A$ (autrement dit, l'image réciproque de $A$
-par l'application $X^{\mathbb{N}} \to X^{\mathbb{N}}$ qui insère
-un $x$ en début de la suite).
-
-Dans le jeu de Gale-Stewart $G_X(A)$ :
+Soit $X$ un ensemble non vide et $A \subseteq X^{\mathbb{N}}$.  Dans
+le jeu de Gale-Stewart $G_X^{\mathrm{a}}(A)$, et en utilisant la
+notation \ref{unshifting-notation} :
 \begin{itemize}
 \item Alice (premier joueur) possède une stratégie gagnante si et
   seulement si il existe $x \in X$ tel qu'elle (=Alice) possède une
   stratégie gagnante en jouant en second dans le jeu de Gale-Stewart
-  défini par le sous-ensemble $x^{\$} A$ ;
+  $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble $x^{\$}
+  A$ ;
 \item Bob (second joueur) possède une stratégie gagnante si et
   seulement si pour tout $x \in X$ il (=Bob) possède une stratégie
-  gagnante en jouant en premier dans le jeu de Gale-Stewart défini par
-  le sous-ensemble $x^{\$} A$.
+  gagnante en jouant en premier dans le jeu de Gale-Stewart
+  $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble $x^{\$} A$.
 \end{itemize}
 \end{prop}
 \begin{proof}
@@ -1390,86 +1450,76 @@ gagnante pour Bob est prête à répondre à n'importe quel coup d'Alice
 après quoi il a une stratégie gagnante » :
 
 Si Alice (premier joueur) possède une stratégie $\varsigma$ gagnante
-dans $G_X(A)$, on pose $x := \varsigma(())$ le premier coup préconisé
-par cette stratégie, et on définit
+dans $G_X^{\mathrm{a}}(A)$, on pose $x := \varsigma(())$ le premier
+coup préconisé par cette stratégie, et on définit
 $\varsigma'((x_1,x_2,\ldots,x_{i-1})) =
 \varsigma((x,x_1,x_2,\ldots,x_{i-1}))$ pour $i$ pair : cette
 définition fait que si $(x_1,x_2,x_3,\ldots)$ est une confrontation où
 Alice joue en second selon $\varsigma'$ alors $(x,x_1,x_2,x_3,\ldots)$
 en est une où elle joue en premier selon $\varsigma$, donc cette suite
 appartient à $A$ puisque $\varsigma$ est gagnante pour Alice
-dans $G_X(A)$, donc $(x_1,x_2,x_3,\ldots)$ appartient à $x^{\$} A$, et
-Alice a bien une stratégie gagnante, $\varsigma'$, en jouant en second
-dans $G_X(x^{\$} A)$.
+dans $G_X^{\mathrm{a}}(A)$, donc $(x_1,x_2,x_3,\ldots)$ appartient
+à $x^{\$} A$, et Alice a bien une stratégie gagnante, $\varsigma'$
+dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où elle joue en second).
 
 Réciproquement, si Alice possède une stratégie gagnante $\varsigma'$
-en jouant en second dans $G_X(x^{\$} A)$, on définit $\varsigma$ par
-$\varsigma(()) = x$ et $\varsigma((x,x_1,x_2,\ldots,x_{i-1})) =
+dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où elle joue en second), on définit
+$\varsigma$ par $\varsigma(()) = x$ et
+$\varsigma((x,x_1,x_2,\ldots,x_{i-1})) =
 \varsigma'((x_1,x_2,\ldots,x_{i-1}))$ pour $i > 0$ pair : cette
 définition fait que si $(x_0,x_1,x_2,x_3,\ldots)$ est une
 confrontation où Alice joue en premier selon $\varsigma$ alors $x_0 =
 x$ et $(x_1,x_2,x_3,\ldots)$ est confrontation où elle (Alice) joue en
 second selon $\varsigma'$, donc cette suite appartient à $x^{\$} A$
 puisque $\varsigma'$ est gagnante pour Alice second joueur
-dans $G_X(x^{\$} A)$, donc $(x_0,x_1,x_2,x_3,\ldots)$ appartient
-à $A$, et Alice a bien une stratégie gagnante, $\varsigma$, en jouant
-en premier dans $G_X(A)$.
+dans $G_X^{\mathrm{b}}(x^{\$} A)$, donc $(x_0,x_1,x_2,x_3,\ldots)$
+appartient à $A$, et Alice a bien une stratégie gagnante, $\varsigma$,
+dans $G_X^{\mathrm{a}}(A)$ (où elle joue en premier).
 
 Si Bob (second joueur) possède une stratégie $\tau$ gagnante
-dans $G_X(A)$ et si $x \in X$ est quelconque, on définit
+dans $G_X^{\mathrm{a}}(A)$ et si $x \in X$ est quelconque, on définit
 $\tau'((x_1,x_2,\ldots,x_{i-1})) = \tau((x,x_1,x_2,\ldots,x_{i-1}))$
 pour $i$ impair : cette définition fait que si $(x_1,x_2,x_3,\ldots)$
 est une confrontation où Bob joue en premier selon $\tau'$ alors
 $(x,x_1,x_2,x_3,\ldots)$ en est une où il joue en second selon $\tau$,
 donc cette suite n'appartient pas à $A$ puisque $\tau$ est gagnante
-pour Bob dans $G_X(A)$, donc $(x_1,x_2,x_3,\ldots)$ n'appartient pas
-à $x^{\$} A$, et Bob a bien une stratégie gagnante, $\tau'$, en jouant
-en premier dans $G_X(x^{\$} A)$.
+pour Bob dans $G_X^{\mathrm{a}}(A)$, donc $(x_1,x_2,x_3,\ldots)$
+n'appartient pas à $x^{\$} A$, et Bob a bien une stratégie gagnante,
+$\tau'$, dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où il joue en premier).
 
-Réciproquement, si Bob possède une stratégie gagnante en jouant en
-second dans $G_X(x^{\$} A)$ pour chaque $x\in X$, on en choisit une
-$\tau_x$ pour chaque $x$, et on définit $\tau$ par
+Réciproquement, si pour chaque $x\in X$ Bob possède une stratégie
+gagnante dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où il joue en premier), on
+en choisit une $\tau_x$ pour chaque $x$, et on définit $\tau$ par
 $\tau((x,x_1,x_2,\ldots,x_{i-1})) = \tau_x((x_1,x_2,\ldots,x_{i-1}))$
 pour $i$ impair : cette définition fait que si
 $(x_0,x_1,x_2,x_3,\ldots)$ est une confrontation où Bob joue en second
 selon $\tau$ alors $(x_1,x_2,x_3,\ldots)$ est confrontation où il
 (Bob) joue en premier selon $\tau_{x_0}$, donc cette suite
 n'appartient pas à ${x_0}^{\$} A$ puisque $\tau_{x_0}$ est gagnante
-pour Bob premier joueur dans $G_X({x_0}^{\$} A)$, donc
+pour Bob premier joueur dans $G_X^{\mathrm{b}}({x_0}^{\$} A)$, donc
 $(x_0,x_1,x_2,x_3,\ldots)$ n'appartient pas à $A$, et Bob a bien une
-stratégie gagnante, $\tau$, en jouant en second dans $G_X(A)$.
+stratégie gagnante, $\tau$, dans $G_X^{\mathrm{a}}(A)$ (où il joue en
+second).
 \end{proof}
 
-\thingy\label{gale-stewart-winning-positions} On dira qu'une position
-$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart $G_X(A)$ est
-\emph{gagnante pour Alice} lorsque Alice a une stratégie gagnante dans
-le jeu qui consiste à continuer à partir de cette suite finie,
-autrement dit, avec la notation introduite
-en \ref{strategies-forall-exists-lemma}, dans le jeu défini par la
-partie $x_{\ell-1}^{\$} \cdots x_1^{\$} x_0^{\$} A$ qui est l'ensemble
-des suites $(x_\ell, x_{\ell+1}, \ldots) \in X^{\mathbb{N}}$ telles
-que $(x_0,\ldots,x_{\ell-1}, x_\ell, \ldots)$ appartienne à $A$, avec
-la convention qu'Alice joue en premier si $\ell$ est pair et en second
-si $\ell$ est impair (de façon à continuer comme dans $G_X(A)$).  On
-définit de même une position \emph{gagnante pour Bob}.
-
-(Ainsi, la position initiale $()$ est gagnante pour Alice, resp. Bob,
-si et seulement si Alice, resp. Bob, a une stratégie gagnante
-dans $G_X(A)$.)
-
-Avec cette convention, la
+\thingy En utilisant la
+terminologie \ref{gale-stewart-winning-positions}, la
 proposition \ref{strategies-forall-exists-lemma} peut se reformuler de
 la façon suivante :
 \begin{itemize}
 \item une position est gagnante pour le joueur qui doit jouer si et
-  seulement si il existe une manière de l'étendre d'un élément en une
-  position gagnante pour ce même joueur (qui est maintenant le
-  joueur qui vient de jouer),
+  seulement si \emph{il existe} un coup $x$ menant à une position
+  gagnante pour ce même joueur (qui est maintenant le joueur qui vient
+  de jouer),
 \item une position est gagnante pour le joueur qui vient de jouer si
-  et seulement si toutes les façons de l'étendre d'un élément donnent
-  des positions gagnantes pour ce même joueur (qui est maintenant le
-  joueur qui doit jouer).
+  et seulement si \emph{tous} les coups $x$ mènent à des positions
+  gagnantes pour ce même joueur (qui est maintenant le joueur qui doit
+  jouer).
 \end{itemize}
+(Dans ces affirmations, « un coup $x$ » depuis une position
+$(x_0,\ldots,x_{\ell-1})$ doit bien sûr se comprendre comme menant à
+la position $(x_0,\ldots,x_{\ell-1},x)$ obtenue en ajoutant $x$ à la
+fin.)
 
 
 \subsection{Topologie produit}
@@ -1568,9 +1618,11 @@ Si $A \subseteq X^{\mathbb{N}}$ est ouvert, ou bien fermé, alors le
 jeu $G_X(A)$ est déterminé.
 \end{thm}
 \begin{proof}[Première démonstration]
-Il suffit de traiter le cas ouvert : le cas fermé s'en déduit en
-échangeant les deux joueurs (à condition d'avoir traité le cas ouvert
-aussi bien quand Alice joue en premier et quand Bob joue en premier).
+Il suffit de traiter le cas ouvert : le cas fermé s'en déduit
+d'après \ref{remark-player-names} en passant au complémentaire,
+c'est-à-dire en échangeant les deux joueurs (à condition d'avoir
+traité le cas ouvert aussi le cas $G_X^{\mathrm{a}}(A)$ où Alice joue
+en premier et le cas $G_X^{\mathrm{b}}(A)$ où Bob joue en premier).
 
 Soit $A \subseteq X^{\mathbb{N}}$ ouvert.  Quel que soit le joueur qui
 commence, on va montrer que si Alice (le joueur qui cherche à jouer
@@ -1595,9 +1647,9 @@ définit de façon arbitraire.
 Si $x_0,x_1,x_2,\ldots$ est une confrontation où Bob joue
 selon $\tau$, on voit par récurrence sur $i$ qu'aucune des positions
 $(x_0,\ldots,x_{i-1})$ n'est gagnante pour Alice : pour $i=0$ c'est
-l'hypothèse faite sur le jeu (Alice n'a pas de stratégie gagnante
-depuis la position initiale), pour les positions où c'est à Bob de
-jouer, c'est la construction de $\tau$ qui assure la récurrence
+l'hypothèse faite sur le jeu (à savoir, qu'Alice n'a pas de stratégie
+gagnante depuis la position initiale), pour les positions où c'est à
+Bob de jouer, c'est la construction de $\tau$ qui assure la récurrence
 (cf. (a) ci-dessus), et pour les positions où c'est à Alice de jouer,
 c'est le point (b) ci-dessus qui assure la récurrence.