Product topology and open determinacy.

1 files changed, 201 insertions, 27 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 30f16f2..2226df7 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1176,7 +1176,7 @@ de Nash.
 
 \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games}
 
-\begin{thm}[« du minimax », von Neumann, 1928]\label{theorem-minimax}
+\begin{thm}[« du minimax », J. von Neumann, 1928]\label{theorem-minimax}
 Soient $C$ et $C'$ deux convexes compacts dans des espaces affines
 réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$
 une application bi-affine (c'est-à-dire, affine en chaque variable
@@ -1294,23 +1294,24 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 \subsection{Définitions}
 
 \begin{defn}\label{definition-gale-stewart-game}
-Soit $X$ un ensemble 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).
-
-Dans ce contexte, les suites finies d'éléments de $X$ s'appellent les
-\textbf{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'\textbf{arbre} du jeu $G_X$.  Une \textbf{partie} ou
+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).
+
+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
+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'\textbf{arbre}
+du jeu $G_X$.  Une \textbf{partie} ou
 \textbf{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é.}
@@ -1320,9 +1321,9 @@ de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$.
 \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 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$
+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$
@@ -1361,12 +1362,13 @@ peut jouer un coup $x$ qui l'amène à une position d'où elle (Alice) a
 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}
-Soit $X$ un ensemble 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).
+\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)$ :
 \begin{itemize}
@@ -1438,6 +1440,178 @@ $(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)$.
 \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
+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),
+\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).
+\end{itemize}
+
+
+\subsection{Topologie produit}
+
+\begin{defn}
+Soit $X$ un ensemble non vide.  Si $\underline{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 \textbf{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$.
+
+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})$.
+
+Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \textbf{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$.
+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$.
+
+Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dite \textbf{fermé}
+lorsque son complémentaire $B := X^{\mathbb{N}} \setminus A$ est
+ouvert.
+\end{defn}
+
+\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})$).
+
+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
+est tout simplement égale à $V$ ou à $V'$).
+
+\medbreak
+
+L'énoncé suivant est une généralité topologique :
+\begin{prop}
+Soit $X$ un ensemble non vide.  Alors, dans $X^{\mathbb{N}}$ (pour la
+topologie produit) :
+\begin{itemize}
+\item[(i)]$\varnothing$ et $X^{\mathbb{N}}$ sont ouverts,
+\item[(ii)]une réunion quelconque d'ouverts est un ouvert (i.e., si
+  $A_i$ est ouvert pour chaque $i\in I$ alors $\bigcup_{i\in I} A_i$
+  est ouvert),
+\item[(iii)]une intersection finie d'ouverts est un ouvert (i.e., si
+  $A_1,\ldots,A_n$ sont ouverts alors $A_1\cap \cdots \cap A_n$ est
+  ouvert).
+\end{itemize}
+\end{prop}
+\begin{proof}
+L'affirmation (i) est triviale.
+
+Montrons (ii) : si les $A_i$ sont ouverts et si $\underline{x} \in
+\bigcup_{i\in I} A_i$, alors la définion 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
+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}$
+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'$
+est ouvert.
+\end{proof}
+
+
+\subsection{Détermination des jeux ouverts}
+
+\begin{thm}[D. Gale \& F. M. Stewart, 1953]
+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).
+
+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
+dans $A$) n'a pas de stratégie gagnante, alors Bob (le joueur qui
+cherche à jouer dans le complémentaire) en a une.  On va définir une
+stratégie $\tau$ pour Bob en évitant les positions où Alice a une
+stratégie gagnante.
+
+Si $(x_0,\ldots,x_{i-1})$ est une position où c'est à Bob de jouer et
+qui n'est pas gagnante pour Alice (c'est-à-dire qu'Alice n'a pas de
+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 $x' \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.
+
+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
+(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.
+
+On utilise maintenant le fait que $A$ est supposé ouvert : si
+$x_0,x_1,x_2,\ldots$ appartient à $A$, alors il existe $\ell$ tel que
+toute suite commençant par $x_0,\ldots,x_{\ell-1}$ appartienne à $A$.
+Mais alors Alice a une stratégie gagnante à partir de la position
+$(x_0,\ldots,x_{\ell-1})$, même, elle ne peut que gagner à partir de
+là.  Si Bob a joué selon $\tau$, ceci contredit la conclusion du
+paragraphe précédent.  On en déduit que si Bob joue selon $\tau$, la
+confrontation n'appartient pas à $A$, c'est-à-dire que $\tau$ est
+gagnante pour Bob.
+\end{proof}
+
 
 
 %