From 2e03dec5c53c31e97db35af0fa4122e118a44b3f Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 25 Feb 2016 14:38:53 +0100 Subject: Product topology and open determinacy. --- notes-mitro206.tex | 228 ++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 201 insertions(+), 27 deletions(-) (limited to 'notes-mitro206.tex') 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} + % -- cgit v1.2.3