diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 425 |
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}$. |