Various clarifications / improvements on Gale-Stewart games.

1 files changed, 235 insertions, 190 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 96dfe79..b4f7f29 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -50,6 +50,8 @@
 \newcommand{\rk}{\operatorname{rk}}
 \newcommand{\fuzzy}{\mathrel{\|}}
 %
+\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
+%
 \DeclareUnicodeCharacter{00A0}{~}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
@@ -1593,26 +1595,31 @@ joueurs.
 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
-\defin[Gale-Stewart (jeu de)]{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 \defin[gain]{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 \defin[position]{positions} (y
-compris la suite vide $()$, qui peut s'appeler position initiale)
-de $G_X(A)$, ou de $G_X$ vu que $A$ n'intervient pas ici ; leur
-ensemble $\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle parfois
-l'\defin[arbre d'un jeu]{arbre} du jeu $G_X$.  Une \defin[partie|see{confrontation}]{partie} ou
+\defin[Gale-Stewart (jeu de)]{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
+\defin[gain]{gagne}, sinon c'est Bob (la partie n'est jamais nulle).
+
+Dans ce contexte, les suites finies $\underline{x} =
+(x_0,\ldots,x_{\ell-1})$ d'éléments de $X$ s'appellent les
+\defin[position]{positions} (y compris la suite vide $()$, qui peut
+s'appeler position initiale) de $G_X(A)$, ou de $G_X$ vu que $A$
+n'intervient pas ici ; leur ensemble $\bigcup_{\ell=0}^{+\infty}
+X^\ell$ s'appelle parfois l'\defin[arbre d'un jeu]{arbre} du
+jeu $G_X$ ; l'entier $\ell$ (tel que $\underline{x} \in X^\ell$)
+s'appelle la \textbf{longueur} de $\underline{x} =
+(x_0,\ldots,x_{\ell-1})$.  Une
+\defin[partie|see{confrontation}]{partie} ou
 \defin{confrontation}\footnote{Le mot « partie » peut malheureusement
   désigner soit un sous-ensemble soit une partie d'un jeu au sens
   défini ici : le mot « confrontation » permet d'éviter l'ambiguïté.}
-de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$.
+de $G_X$ est une suite infinie $\dblunderline{x} =
+(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
@@ -1631,7 +1638,13 @@ 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.
+des joueurs sont échangés.  On utilisera parfois $G_X(A)$ pour
+désigner indifféremment $G_X^{\mathrm{a}}(A)$ ou $G_X^{\mathrm{b}}(A)$
+(avec une tournure comme « quel que soit le joueur qui commence »).
+
+Donnée une position $\underline{x}$ de longueur $\ell$, le joueur
+« qui doit jouer » dans $\underline{x}$ désigne le premier joueur si
+$\ell$ est paire, et le second joueur si $\ell$ est impaire.
 
 \begin{defn}\label{definition-strategies-for-gale-stewart-games}
 Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une
@@ -1642,28 +1655,29 @@ 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
+Lorsque dans une 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
-que le premier joueur a joué la partie selon la
+que le premier joueur a joué la confrontation \textbf{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$.
+confrontation 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
+l'unique confrontation dans laquelle 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 \index{stratégie gagnante}\defin[gagnante (stratégie)]{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
+dite \index{stratégie gagnante}\defin[gagnante (stratégie)]{gagnante}
+(dans $G_X^{\mathrm{a}}(A)$) lorsque Alice gagne toute confrontation
+où elle joue selon $\varsigma$ comme premier joueur, et la stratégie
+$\tau$ pour Bob est dite gagnante lorsque Bob gagne toute
+confrontation 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
 \defin[déterminé (jeu)]{déterminé}.
 \end{defn}
 
@@ -1674,7 +1688,8 @@ gagnantes pour les deux joueurs : elle devrait simultanément
 appartenir et ne pas appartenir à $A$).
 
 En revanche, il faut se garder de croire que les jeux $G_X(A)$ sont
-toujours déterminés.
+toujours déterminés (on verra cependant des résultats positifs
+dans \ref{section-determinacy-of-gale-stewart-games}).
 
 \thingy\label{unshifting-notation} Introduisons la notation suivante :
 si $\underline{x} := (x_0,\ldots,x_{\ell-1})$ est une suite finie
@@ -1692,34 +1707,46 @@ si $x\in X$ alors $x^\$ A$ est l'ensemble des $(x_1,x_2,x_3,\ldots)
 $\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ée
-comme définissant un nouveau jeu de Gale-Stewart consistant à jouer
-\defin{à 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
+\thingy\label{gale-stewart-positions-as-games} Si $\underline{x} :=
+(x_0,\ldots,x_{\ell-1})$ est une position dans un jeu de Gale-Stewart
+$G_X(A)$, on peut considérer qu'elle définit un nouveau jeu
+$G_X(\underline{x}, A)$ consistant à jouer \defin{à partir de là},
+c'est-à-dire que les joueurs jouent pour compléter cette suite, ou, ce
+qui revient au même, que leurs $\ell$ premiers coups sont imposés.
+
+Plus précisément, on introduit le jeu $G_X^{\mathrm{a}}(\underline{x},
+A)$ (resp. $G_X^{\mathrm{b}}(\underline{x}, A)$), qui est la
+modification du jeu $G_X^{\mathrm{a}}(A)$
+(resp. $G_X^{\mathrm{b}}(A)$) où les $\ell$ premiers coups sont
+imposés par les valeurs de $\underline{x}$ (autrement dit, lorsque
+$i<\ell$, au $i$-ième coup, seule la valeur $x_i$ peut être jouée).
+On identifiera parfois abusivement la position $\underline{x}$ du jeu
+$G_X(A)$ avec le jeu $G_X(\underline{x}, A)$ joué à partir de cette
+position.
+
+Bien sûr, plutôt qu'\emph{imposer} les $\ell$ premiers cours, on peut
+aussi considérer que les joueurs jouent directement à partir du coup
+numéroté $\ell$ (donc pour compléter $\underline{x}$) : 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
+coups imposés $x_0,\ldots,x_{\ell-1}$ au début de la confrontation, et
+on regarde si la suite tout entière appartient à $A$ pour déterminer
+le gagnant.  Quitte à renuméroter les coups effectivement choisis pour
+commencer à $0$, on retrouve un jeu de Gale-Stewart, défini comme suit
+en utilisant la notation \ref{unshifting-notation} : à savoir, le jeu
+$G_X^{\mathrm{a}}(\underline{x}, A)$ peut s'identifier au jeu
+$G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair (=c'est
+à Alice de jouer dans la position $\underline{x}$), et
+$G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair
+(=c'est à Bob de jouer) ; symétriquement, bien sûr,
+$G_X^{\mathrm{b}}(\underline{x}, A)$ peut s'identifier au jeu
 $G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair, et
-$G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.)
+$G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.
 
 \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
-\defin[gagnante (position)]{gagnante} pour Alice lorsque Alice a une stratégie gagnante
-dans le jeu qui consiste à jouer à partir de cette position
+$\underline{x} = (x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart
+$G_X(A)$ est \defin[gagnante (position)]{gagnante} pour Alice lorsque
+Alice a une stratégie gagnante dans le jeu $G_X(\underline{x},A)$ qui
+consiste à jouer à partir de cette position
 (cf. \ref{gale-stewart-positions-as-games}).  On définit de même une
 position gagnante pour Bob.
 
@@ -1733,19 +1760,26 @@ 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}}$.  Dans
-le jeu de Gale-Stewart $G_X^{\mathrm{a}}(A)$, et en utilisant la
-notation \ref{unshifting-notation} :
+le jeu de Gale-Stewart $G_X^{\mathrm{a}}(A)$, et en utilisant les
+définitions faites en
+\ref{unshifting-notation} et \ref{gale-stewart-positions-as-games} :
 \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
-  $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
-  $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble $x^{\$} A$.
+\item Alice (premier joueur) possède une stratégie gagnante dans
+  $G_X^{\mathrm{a}}(A)$ si et seulement si \emph{il existe} $x \in X$
+  tel qu'elle (=Alice) possède une stratégie gagnante dans le jeu
+  $G_X^{\mathrm{a}}(x, A)$ (dont on rappelle qu'il peut s'identifier
+  au jeu $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble
+  $x^{\$} A$ et où Bob joue en premier) ;
+\item Bob (second joueur) possède une stratégie gagnante dans
+  $G_X^{\mathrm{a}}(A)$ si et seulement si \emph{pour tout} $x \in X$
+  il (=Bob) possède une stratégie gagnante dans le jeu
+  $G_X^{\mathrm{a}}(x, A)$ (dont on rappelle qu'il peut s'identifier
+  au jeu $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble
+  $x^{\$} A$ et où Bob joue en premier).
 \end{itemize}
+(Les mêmes affirmations valent, bien sûr, en échangeant « Alice » et
+    « Bob » tout du long ainsi que $G_X^{\mathrm{a}}$
+    et $G_X^{\mathrm{b}}$.)
 \end{prop}
 \begin{proof}
 La démonstration suivante ne fait que (laborieusement) formaliser
@@ -1810,7 +1844,7 @@ second).
 \thingy\label{strategies-forall-exists-reformulation} En utilisant la
 terminologie \ref{gale-stewart-winning-positions}, la
 proposition \ref{strategies-forall-exists-lemma} peut se reformuler de
-la façon suivante :
+la façon suivante, peut-être plus simple :
 \begin{itemize}
 \item une position $\underline{z}$ est gagnante pour le joueur qui
   doit jouer si et seulement si \emph{il existe} un coup $x$ menant à
@@ -1826,31 +1860,84 @@ $\underline{z} := (z_0,\ldots,z_{\ell-1})$ doit bien sûr se comprendre
 comme menant à la position $\underline{z}x :=
 (z_0,\ldots,z_{\ell-1},x)$ obtenue en ajoutant $x$ à la fin.)
 
+\thingy On peut donc encore voir les choses comme suit : dire qu'Alice
+a une stratégie gagnante dans le jeu $G_X^{\mathrm{a}}(A)$ signifie
+que la position intiale $()$ est gagnante pour Alice, ce qui équivaut
+(d'après ce qu'on vient de voir) à : $\exists x_0$ tel que la position
+$(x_0)$ soit gagnante pour Alice ; ce qui équivaut à : $\exists x_0\,
+\forall x_1$ la position $(x_0,x_1)$ est gagnante pour Alice ; ou
+encore : $\exists x_0\, \forall x_1\, \exists x_2$ la position
+$(x_0,x_1,x_2)$ est gagnante pour Alice ; ou encore : $\exists x_0\,
+\forall x_1\, \exists x_2\, \forall x_3$ la position
+$(x_0,x_1,x_2,x_3)$ est gagnante pour Alice ; et ainsi de suite.
+
+Il peut donc être tentant de noter l'affirmation « Alice a une
+  stratégie gagnante dans le jeu $G_X^{\mathrm{a}}(A)$ » par
+l'écriture abusive
+\[
+\exists x_0\, \forall x_1\, \exists x_2\, \forall x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) \in A)
+\tag{$\mathscr{A}$}
+\]
+Cette écriture abusive n'a pas de sens mathématique, mais on peut la
+\emph{définir} comme signifiant « Alice a une stratégie gagnante dans
+  le jeu $G_X^{\mathrm{a}}(A)$ », tandis que « Bob a une stratégie
+  gagnante dans le jeu $G_X^{\mathrm{a}}(A)$ » se noterait
+\[
+\forall x_0\, \exists x_1\, \forall x_2\, \exists x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) \not\in A)
+\tag{$\mathscr{B}$}
+\]
+Ces notations sont intuitivement intéressantes, mais elles présentent
+l'inconvénient de laisser croire que l'affirmation $\mathscr{A}$ est
+la négation de $\mathscr{B}$, ce qui n'est pas le cas en général
+(comme on l'a dit, il se peut qu'aucun des joueurs n'ait de stratégie
+gagnante).  Ce qui est vrai en revanche est que la négation
+$\neg\mathscr{A}$ de $\mathscr{A}$ peut se réécrire (avec la notation
+abusive définie ci-dessus) comme
+\[
+\begin{aligned}
+\neg\exists x_0\, \forall x_1\, \exists x_2\, \forall x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) &\in A)\\
+\forall x_0\, \neg\forall x_1\, \exists x_2\, \forall x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) &\in A)\\
+\forall x_0\, \exists x_1\, \neg\exists x_2\, \forall x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) &\in A)\\
+\forall x_0\, \exists x_1\, \forall x_2\, \neg\forall x_3\cdots
+((x_0,x_1,x_2,x_3,\ldots) &\in A)\\
+\end{aligned}
+\]
+mais on ne peut pas traverser l'« infinité de quantificateurs » pour
+passer à $\mathscr{B}$ sauf par exemple dans les conditions qu'on
+verra en \ref{section-determinacy-of-gale-stewart-games}.
+
 
 \subsection{Topologie produit}
 
 \begin{defn}\label{definition-product-topology}
-Soit $X$ un ensemble non vide.  Si $\underline{x} :=
+Soit $X$ un ensemble non vide.  Si $\dblunderline{x} :=
 (x_0,x_1,x_2,\ldots)$ est une suite d'éléments de $X$ et
 $\ell\in\mathbb{N}$, on appelle $\ell$-ième \defin{voisinage
-  fondamental} de $\underline{x}$, et on note $V_\ell(\underline{x})$
-l'ensemble de tous les éléments $(z_0,z_1,z_2,\ldots)$ de
-$X^{\mathbb{N}}$ dont les $\ell$ premiers termes coïncident avec
-celles de $\underline{x}$, autrement dit $z_i = x_i$ si $i<\ell$.
+  fondamental} de $\dblunderline{x}$, et on note
+$V_\ell(\dblunderline{x})$ l'ensemble de tous les éléments
+$(z_0,z_1,z_2,\ldots)$ de $X^{\mathbb{N}}$ dont les $\ell$ premiers
+termes coïncident avec celles de $\dblunderline{x}$, autrement dit
+$z_i = x_i$ si $i<\ell$.
 
 On dit aussi qu'il s'agit du voisinage fondamental défini par la suite
-finie $(x_0,\ldots,x_{\ell-1})$ (il ne dépend manifestement que de ces
-termes), et on peut le noter $V_\ell(x_0,\ldots,x_{\ell-1})$ ou
-$V(x_0,\ldots,x_{\ell-1})$.
+finie $\underline{x} = (x_0,\ldots,x_{\ell-1})$ (il ne dépend
+manifestement que de ces termes), et on peut le noter
+$V_\ell(x_0,\ldots,x_{\ell-1})$ ou $V(x_0,\ldots,x_{\ell-1})$.
 
 Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \defin{ouvert}
-[pour la topologie produit] lorsque pour tout $\underline{x} \in A$ il
-existe un $\ell$ tel que le $\ell$-ième voisinage fondamental
-$V_\ell(\underline{x})$ de $\underline{x}$ soit inclus dans $A$.
+[pour la topologie produit] lorsque pour tout $\dblunderline{x} \in A$
+il existe un $\ell$ tel que le $\ell$-ième voisinage fondamental
+$V_\ell(\dblunderline{x})$ de $\dblunderline{x}$ soit inclus dans $A$.
 Autrement dit : dire que $A$ est ouvert signifie que lorsque $A$
-contient une suite $\underline{x} := (x_0,x_1,x_2,\ldots)$, il existe
-un rang $\ell$ tel que $A$ contienne n'importe quelle suite obtenue en
-modifiant la suite $\underline{x}$ à partir du rang $\ell$.
+contient une suite $\dblunderline{x} := (x_0,x_1,x_2,\ldots)$, il
+existe un rang $\ell$ tel que $A$ contienne n'importe quelle suite
+obtenue en modifiant la suite $\dblunderline{x}$ à partir du
+rang $\ell$.
 
 Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \defin{fermé}
 lorsque son complémentaire $B := X^{\mathbb{N}} \setminus A$ est
@@ -1860,24 +1947,24 @@ ouvert.
 \thingy On notera qu'il existe des parties de $X^{\mathbb{N}}$ à la
 fois ouvertes et fermées : c'est le cas non seulement de $\varnothing$
 et de $X^{\mathbb{N}}$, mais plus généralement de n'importe quel
-voisinage fondamental $V_\ell(\underline{x})$ (en effet,
-$V_\ell(\underline{x})$ est ouvert car si $\underline{y} \in
-V_\ell(\underline{x})$, c'est-à-dire si $\underline{y}$ coïncide avec
-$\underline{x}$ sur les $\ell$ premiers termes, alors toute suite
-$\underline{z}$ qui coïncide avec $\underline{y}$ sur les $\ell$
-premiers termes coïncide aussi avec $\underline{x}$ dessus, et
-appartient donc à $V_\ell(\underline{x})$, autrement dit,
-$V_\ell(\underline{y})$ est inclus dans $V_\ell(\underline{x})$ ; mais
-$V_\ell(\underline{x})$ est également fermé car si $\underline{y}
-\not\in V_\ell(\underline{x})$, alors toute suite $\underline{z}$ qui
-coïncide avec $\underline{y}$ sur les $\ell$ premiers termes ne
-coïncide \emph{pas} avec $\underline{x}$ dessus, donc n'appartient pas
-à $V_\ell(\underline{x})$, autrement dit $V_\ell(\underline{y})$ est
-inclus dans le complémentaire de $V_\ell(\underline{x})$).
+voisinage fondamental $V_\ell(\dblunderline{x})$ (en effet,
+$V_\ell(\dblunderline{x})$ est ouvert car si $\dblunderline{y} \in
+V_\ell(\dblunderline{x})$, c'est-à-dire si $\dblunderline{y}$ coïncide avec
+$\dblunderline{x}$ sur les $\ell$ premiers termes, alors toute suite
+$\dblunderline{z}$ qui coïncide avec $\dblunderline{y}$ sur les $\ell$
+premiers termes coïncide aussi avec $\dblunderline{x}$ dessus, et
+appartient donc à $V_\ell(\dblunderline{x})$, autrement dit,
+$V_\ell(\dblunderline{y})$ est inclus dans $V_\ell(\dblunderline{x})$ ; mais
+$V_\ell(\dblunderline{x})$ est également fermé car si $\dblunderline{y}
+\not\in V_\ell(\dblunderline{x})$, alors toute suite $\dblunderline{z}$ qui
+coïncide avec $\dblunderline{y}$ sur les $\ell$ premiers termes ne
+coïncide \emph{pas} avec $\dblunderline{x}$ dessus, donc n'appartient pas
+à $V_\ell(\dblunderline{x})$, autrement dit $V_\ell(\dblunderline{y})$ est
+inclus dans le complémentaire de $V_\ell(\dblunderline{x})$).
 
 Il sera utile de remarquer que l'intersection de deux voisinages
-fondamentaux $V,V'$ d'une même suite $\underline{x}$ est encore un
-voisinage fondamental de $\underline{x}$ (en fait, cette intersection
+fondamentaux $V,V'$ d'une même suite $\dblunderline{x}$ est encore un
+voisinage fondamental de $\dblunderline{x}$ (en fait, cette intersection
 est tout simplement égale à $V$ ou à $V'$).
 
 \medbreak
@@ -1899,24 +1986,24 @@ topologie produit) :
 \begin{proof}
 L'affirmation (i) est triviale.
 
-Montrons (ii) : si les $A_i$ sont ouverts et si $\underline{x} \in
+Montrons (ii) : si les $A_i$ sont ouverts et si $\dblunderline{x} \in
 \bigcup_{i\in I} A_i$, alors la définition d'une réunion fait qu'il
-existe $i$ tel que $\underline{x} \in A_i$, et comme $A_i$ est ouvert
-il existe un voisinage fondamental de $\underline{x}$ inclus
+existe $i$ tel que $\dblunderline{x} \in A_i$, et comme $A_i$ est ouvert
+il existe un voisinage fondamental de $\dblunderline{x}$ inclus
 dans $A_i$, donc inclus dans $\bigcup_{i\in I} A_i$ : ceci montre que
 $\bigcup_{i\in I} A_i$ est ouvert.
 
 Montrons (iii) : il suffit de montrer que si $A, A'$ sont ouverts
-alors $A \cap A'$ est ouvert.  Soit $\underline{x} \in A \cap A'$.  Il
-existe des voisinages fondamentaux $V$ et $V'$ de $\underline{x}$
+alors $A \cap A'$ est ouvert.  Soit $\dblunderline{x} \in A \cap A'$.  Il
+existe des voisinages fondamentaux $V$ et $V'$ de $\dblunderline{x}$
 inclus dans $A$ et $A'$ respectivement (puisque ces derniers sont
 ouverts) : alors $V \cap V'$ est un voisinage fondamental de
-$\underline{x}$ inclus dans $A \cap A'$ : ceci montre que $A \cap A'$
+$\dblunderline{x}$ inclus dans $A \cap A'$ : ceci montre que $A \cap A'$
 est ouvert.
 \end{proof}
 
 
-\subsection{Détermination des jeux ouverts}
+\subsection{Détermination des jeux ouverts}\label{section-determinacy-of-gale-stewart-games}
 
 \thingy\label{fundamental-neighorhood-terminates-game} La remarque
 suivante, bien que complètement évidente, sera cruciale : si
@@ -1956,12 +2043,14 @@ stratégie gagnante à partir de là,
 cf. \ref{gale-stewart-winning-positions}), alors
 d'après \ref{strategies-forall-exists-lemma}, (a) il existe un $x$ tel
 que $(x_0,\ldots,x_{i-1},x)$ ne soit pas gagnante pour Alice :
-choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ :
-toujours d'après \ref{strategies-forall-exists-lemma}, (b) quel que
-soit $y \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas
-gagnante pour Alice (et c'est de nouveau à Bob de jouer).  Aux points
-où $\tau$ n'a pas été défini par ce qui vient d'être dit, on le
-définit de façon arbitraire.
+choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$.
+Aux points où $\tau$ n'a pas été défini par ce qui vient d'être dit,
+on le définit de façon arbitraire.  Par ailleurs, si
+$(x_0,\ldots,x_{i-1})$ est une position où c'est à Alice de jouer et
+qui n'est pas gagnante pour Alice, toujours
+d'après \ref{strategies-forall-exists-lemma}, on remarque que (b) quel
+que soit $y \in X$, la position $(x_0,\ldots,x_{i-1},y)$ n'est pas
+gagnante pour Alice.
 
 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
@@ -6343,12 +6432,12 @@ $X$ (non vide) et une fonction $u \colon X^{\mathbb{N}} \to
 \mathbb{R}$ dite fonction de gain d'Alice (la fonction de gain de Bob
 serait $-u$).  Alice et Bob choisissent tour à tour un élément de $X$
 comme pour un jeu de Gale-Stewart, et jouent un nombre infini de
-coups, « à la fin » desquels la suite $\underline{x} =
-(x_0,x_1,x_2,\ldots)$ définit un élément $\underline{x} \in
-X^{\mathbb{N}}$.  Le gain d'Alice est alors $u(\underline{x})$ (le but
-d'Alice est de le maximiser) et le gain de Bob est $-u(\underline{x})$
+coups, « à la fin » desquels la suite $\dblunderline{x} =
+(x_0,x_1,x_2,\ldots)$ définit un élément $\dblunderline{x} \in
+X^{\mathbb{N}}$.  Le gain d'Alice est alors $u(\dblunderline{x})$ (le but
+d'Alice est de le maximiser) et le gain de Bob est $-u(\dblunderline{x})$
 (le but de Bob est de maximiser cette quantité, c'est-à-dire de
-minimiser $u(\underline{x})$).
+minimiser $u(\dblunderline{x})$).
 
 \smallbreak
 
@@ -6359,7 +6448,7 @@ généralisation des jeux de Gale-Stewart.
 Si $G_X(A)$ où $A \subseteq X^{\mathbb{N}}$ est un jeu de Gale-Stewart
 défini par un sous-ensemble $A$ de $X^{\mathbb{N}}$, on peut définir
 une fonction $u \colon X^{\mathbb{N}} \to \mathbb{R}$ par
-$u(\underline{x}) = 1$ si $x\in A$ et $u(\underline{x}) = -1$
+$u(\dblunderline{x}) = 1$ si $x\in A$ et $u(\dblunderline{x}) = -1$
 si $x\not\in A$, c'est-à-dire utiliser la valeur $+1$ pour un gain
 d'Alice et $-1$ pour un gain de Bob.  Les buts d'Alice et de Bob dans
 le jeu défini par cette fonction sont alors exactement les mêmes que
@@ -6370,29 +6459,29 @@ dans le jeu $G_X(A)$.
 
 (2) On suppose désormais que $u \colon X^{\mathbb{N}} \to \mathbb{R}$
 est \emph{continue}, ce qui signifie par définition que pour tout
-$\underline{x} \in X^{\mathbb{N}}$ et tout $\varepsilon > 0$ réel, il
-existe $\ell$ tel que pour tout $y \in V_\ell(\underline{x})$ on ait
-$|u(\underline{y}) - u(\underline{x})| < \varepsilon$.  Montrer que
-quel que soit $v \in\mathbb{R}$ l'ensemble des $\underline{x}$ tels
-que $u(\underline{x}) > v$ est ouvert, et de même pour l'ensemble des
-$\underline{x}$ tels que $u(\underline{x}) < v$.
+$\dblunderline{x} \in X^{\mathbb{N}}$ et tout $\varepsilon > 0$ réel, il
+existe $\ell$ tel que pour tout $y \in V_\ell(\dblunderline{x})$ on ait
+$|u(\dblunderline{y}) - u(\dblunderline{x})| < \varepsilon$.  Montrer que
+quel que soit $v \in\mathbb{R}$ l'ensemble des $\dblunderline{x}$ tels
+que $u(\dblunderline{x}) > v$ est ouvert, et de même pour l'ensemble des
+$\dblunderline{x}$ tels que $u(\dblunderline{x}) < v$.
 
 \begin{corrige}
-Fixons un réel $v$.  Montrons que l'ensemble $A_v$ des $\underline{x}$
-tels que $u(\underline{x}) > v$ est ouvert.  Si $\underline{x}$ est
-dans $A_v$, i.e., vérifie $u(\underline{x}) > v$, alors la définition
-de la continuité appliquée à ce $\underline{x}$ et à $\varepsilon :=
-u(\underline{x}) - v$ assure qu'il existe $\ell$ tel que pour tout $y
-\in V_\ell(\underline{x})$ on ait $|u(\underline{y}) -
-u(\underline{x})| < \varepsilon$, et cette dernière inégalité implique
-$u(\underline{y}) > u(\underline{x}) - \varepsilon = v$, donc on a
-encore $u(\underline{y}) > v$, autrement dit $\underline{y} \in A_v$.
-On a donc montré que pour tout $\underline{x}$ dans $A_v$ il existe
-$\ell$ tel que tout $\underline{y}$ dans $V_\ell(\underline{x})$ soit
+Fixons un réel $v$.  Montrons que l'ensemble $A_v$ des $\dblunderline{x}$
+tels que $u(\dblunderline{x}) > v$ est ouvert.  Si $\dblunderline{x}$ est
+dans $A_v$, i.e., vérifie $u(\dblunderline{x}) > v$, alors la définition
+de la continuité appliquée à ce $\dblunderline{x}$ et à $\varepsilon :=
+u(\dblunderline{x}) - v$ assure qu'il existe $\ell$ tel que pour tout $y
+\in V_\ell(\dblunderline{x})$ on ait $|u(\dblunderline{y}) -
+u(\dblunderline{x})| < \varepsilon$, et cette dernière inégalité implique
+$u(\dblunderline{y}) > u(\dblunderline{x}) - \varepsilon = v$, donc on a
+encore $u(\dblunderline{y}) > v$, autrement dit $\dblunderline{y} \in A_v$.
+On a donc montré que pour tout $\dblunderline{x}$ dans $A_v$ il existe
+$\ell$ tel que tout $\dblunderline{y}$ dans $V_\ell(\dblunderline{x})$ soit
 encore dans $A_v$, c'est exactement dire que $A_v$ est ouvert.  Le cas
-de l'ensemble $B_v$ des $\underline{x}$ tels que $u(\underline{x}) <
+de l'ensemble $B_v$ des $\dblunderline{x}$ tels que $u(\dblunderline{x}) <
 v$ est exactement analogue (on prendra $\varepsilon := v -
-u(\underline{x})$).
+u(\dblunderline{x})$).
 \end{corrige}
 
 \smallbreak
@@ -6407,7 +6496,7 @@ du jeu.
 
 \begin{corrige}
 (a) Quel que soit $v$ réel, on vient de voir que l'ensemble $A_v$ des
-  $\underline{x}$ tels que $u(\underline{x}) > v$ est ouvert.  La
+  $\dblunderline{x}$ tels que $u(\dblunderline{x}) > v$ est ouvert.  La
   détermination des jeux de Gale-Stewart ouverts
   (théorème \ref{gale-stewart-theorem}) implique donc que soit Alice a
   une stratégie lui garantissant de tomber dans $A_v$, c'est-à-dire un
@@ -6474,8 +6563,8 @@ utiliser (4)).\spaceout (b) Montrer que si une position
 $(z_0,\ldots,z_{i-1})$ où c'est à Bob de jouer est presque
 $w$-gagnante, alors \emph{pour tout} $x \in X$ (coup de Bob), la
 position $(z_0,\ldots,z_{i-1},x)$ est presque $w$-gagnante.\spaceout
-(c) Montrer que si $\underline{x} \in X^{\mathbb{N}}$ et
-$u(\underline{x}) < w$ alors il existe $\ell$ tel que
+(c) Montrer que si $\dblunderline{x} \in X^{\mathbb{N}}$ et
+$u(\dblunderline{x}) < w$ alors il existe $\ell$ tel que
 $(x_0,\ldots,x_{\ell-1})$ ne soit pas presque $w$-gagnante.\spaceout
 (d) En déduire (en construisant une stratégie d'Alice qui cherche à
 rester dans des positions presque $w$-gagnantes) que si la position
@@ -6511,10 +6600,10 @@ initiale est presque $w$-gagnante, alors elle est $w$-gagnante.
   la position $\underline{z}x$ est presque $w$-gagnante, ce qu'on
   voulait montrer.
 
-(c) Si $u(\underline{x}) < w$, et si $v$ est choisi tel que
-  $u(\underline{x}) < v < w$, alors par continuité de $u$
+(c) Si $u(\dblunderline{x}) < w$, et si $v$ est choisi tel que
+  $u(\dblunderline{x}) < v < w$, alors par continuité de $u$
   (cf. question (2)), il existe $\ell$ tel que $u$ soit $<v$ sur
-  $V_\ell(\underline{x})$, autrement dit, aucune confrontation qui
+  $V_\ell(\dblunderline{x})$, autrement dit, aucune confrontation qui
   prolonge $x_0,\ldots,x_{\ell-1}$ ne peut donner un gain $\geq v$ à
   Alice, et en particulier, la position $x_0,\ldots,x_{\ell-1}$ n'est
   pas $v$-gagnante, donc elle n'est pas presque $w$-gagnante.
@@ -6528,7 +6617,7 @@ initiale est presque $w$-gagnante, alors elle est $w$-gagnante.
   nouveau à elle de jouer).  Aux points où $\tau$ n'a pas été défini
   par ce qui vient d'être dit, on le définit de façon arbitraire.
 
-Si $\underline{x} = (x_0,x_1,x_2,\ldots)$ est une confrontation où
+Si $\dblunderline{x} = (x_0,x_1,x_2,\ldots)$ est une confrontation où
 Alice joue selon $\tau$, on voit par récurrence sur $i$ que chacune
 des positions $(x_0,\ldots,x_{i-1})$ est presque $w$-gagnante si la
 position initiale l'est : pour $i=0$ c'est l'hypothèse faite (à savoir
@@ -6536,7 +6625,7 @@ que la position initiale est presque $w$-gagnante), pour les positions
 où c'est à Alice de jouer, c'est la construction de $\tau$ qui assure
 la récurrence (cf. (a) ci-dessus), et pour les positions où c'est à
 Bob de jouer, c'est la question (b) qui assure la récurrence.  Mais la
-question (c) assure qu'on a alors $u(\underline{x}) \geq w$.  On a
+question (c) assure qu'on a alors $u(\dblunderline{x}) \geq w$.  On a
 donc bien défini une stratégie qui garantit à Alice un gain $\geq w$.
 \end{corrige}
 
@@ -6600,56 +6689,12 @@ jeu où les coups de Bob sont purement et simplement ignorés).
   \mathbb{R}$, en considérant la fonction $\hat u\colon
   \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui ignore les coups joués par
   Bob et calcule $u$ sur les coups joués par Alice (i.e.,
-  formellement, $\hat u(\underline{x}) = u(\check{\underline{x})}$ où
+  formellement, $\hat u(\dblunderline{x}) = u(\check{\dblunderline{x})}$ où
   $\check x_i = x_{2i}$), il est clair qu'Alice a une stratégie lui
   garantissant un gain $\geq v$ si et seulement si $u$ prend une
   valeur $\geq v$.  Comme on vient de voir qu'il existe un plus grand
   tel $v$ (la valeur du jeu), cela signifie bien que $u$ est bornée et
   atteint ses bornes.
-%%
-%% Montrons que $u$ est majorée (la minoration est exactement analogue,
-%% ou s'obtient en remplaçant $u$ par $-u$).  Si ce n'est pas le cas,
-%% pour chaque $n$ entier naturel, on peut choisir un
-%% $\underline{z}_{(n)} \in X^{\mathbb{N}}$ tel que
-%% $u(\underline{z}_{(n)}) \geq n$, et on va aboutir à une contradiction.
-%%
-%% Montrons que la suite $\underline{z}_{(n)}$ possède une valeur
-%% d'adhérence, c'est-à-dire, qu'il existe $\underline{y}$ tel que
-%% $\underline{z}_{(n)}$ passe infiniment souvent dans n'importe quel
-%% voisinage fondamental de $\underline{y}$.  Pour cela, considérons le
-%% premier terme $z_{(n),0}$ de $\underline{z}_{(n)}$ : comme il
-%% appartient à $X = \{0,1\}$, il doit valoir infiniment souvent $0$ ou
-%% infiniment souvent $1$ : appelons $y_0$ une valeur qu'il prend pour
-%% une infinité de $n$.  Parmi l'ensemble des $n$ tels que $z_{(n),0} =
-%% y_0$ (on vient de s'assurer qu'il est infini), le terme $z_{(n),1}$
-%% doit lui aussi valoir infiniment souvent $0$ ou infiniment
-%% souvent $1$ : appelons $y_1$ une valeur qu'il prend pour une infinité
-%% de $n$ (autrement dit, il existe une infinité de $n$ tels que
-%% $z_{(n),0} = y_0$ \emph{et} $z_{(n),1} = y_1$).  On procède ainsi par
-%% récurrence sur $k$ : parmi l'ensemble des $n$ tels que $z_{(n),i} =
-%% y_i$ pour tout $i<k$ (dont on s'est assuré par hypothèse de récurrence
-%% qu'il est infini), le terme $z_{(n),k}$ doit lui aussi valoir
-%% infiniment souvent $0$ ou infiniment souvent $1$ : on appelle $y_k$
-%% une valeur qu'il prend pour une infinité de $n$ (autrement dit, il
-%% existe une infinité de $n$ tels que $z_{(n),i} = y_i$ pour tout $i\leq
-%% k$).  Ceci définit une suite $\underline{y} = (y_0,y_1,y_2,\ldots)$
-%% qui possède la propriété que pour tout $k$ il existe une infinité de
-%% $n$ pour lesquels $z_{(n),i} = y_i$ pour tout $i < k$ : autrement dit,
-%% $\underline{z}_{(n)}$ appartient infiniment souvent au voisinage
-%% fondamental $V_k(\underline{y})$.
-%%
-%% Or la valeur $u(\underline{y})$ est un réel, disons $<N$ pour un
-%% certain entier $N$ : par continuité de $u$ (cf. question (2)), il
-%% existe $k$ tel que $u$ soit $<N$ sur $V_k(\underline{y})$.  Notamment,
-%% si $\underline{z}_{(n)} \in V_k(\underline{y})$ alors $n < N$.  Ceci
-%% contredit le fait qu'une infinité de $\underline{z}_{(n)}$ est censée
-%% appartenir à $V_k(\underline{y})$.
-%%
-%% (De façon plus sophistiquée, on peut aussi écrire : l'espace
-%% topologique $X = \{0,1\}$ est \emph{compact} car discret et fini, donc
-%% $X^{\mathbb{N}}$ est également compact par le théorème de Tychonoff,
-%% et l'image d'un compact par une fonction continue est un compact, donc
-%% en particulier bornée dans $\mathbb{R}$.)
 \end{corrige}
 
 \smallbreak
@@ -6663,9 +6708,9 @@ pour Bob ?).
 
 \begin{corrige}
 La fonction $u$ est continue car si $\varepsilon < 2^{-\ell-1}$
-  alors la valeur $u(\underline{x})$ est définie à $\varepsilon$ près
+  alors la valeur $u(\dblunderline{x})$ est définie à $\varepsilon$ près
   par la donnée des $\ell$ premiers termes de la
-  suite $\underline{x}$.  Il est évident qu'Alice a intérêt à ne jouer
+  suite $\dblunderline{x}$.  Il est évident qu'Alice a intérêt à ne jouer
   que des $1$ (jouer autre chose ne ferait que diminuer son gain) et
   Bob que des $0$.  La valeur du jeu est donc $u(0,1,0,1,0,1,\ldots) =
   \frac{1}{2}$.