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