diff options
| -rw-r--r-- | notes-mitro206.tex | 99 |
1 files changed, 93 insertions, 6 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 71e4383..fa39db5 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1524,7 +1524,7 @@ fin.) \subsection{Topologie produit} -\begin{defn} +\begin{defn}\label{definition-product-topology} 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 @@ -1613,6 +1613,19 @@ est ouvert. \subsection{Détermination des jeux ouverts} +\thingy\label{fundamental-neighorhood-terminates-game} La remarque +suivante, bien que complètement évidente, sera cruciale : si +$(x_0,\ldots,x_{\ell-1})$ est une suite finie d'éléments de $X$ (i.e., +une position de $G_X$) et $A$ une partie contenant le voisinage +fondamental (cf. \ref{definition-product-topology}) défini par +$(x_0,\ldots,x_{\ell-1})$, alors Alice possède une stratégie gagnante +à partir de $(x_0,\ldots,x_{\ell-1})$ dans le jeu $G_X(A)$ +(cf. \ref{gale-stewart-positions-as-games}). Mieux : quoi que fassent +l'un et l'autre joueur à partir de ce point, la partie sera gagnée par +Alice. C'est tout simplement qu'on a fait l'hypothèse que +\emph{toute} suite commençant par $x_0,\ldots,x_{\ell-1}$ appartient +à $A$. + \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é. @@ -1657,11 +1670,85 @@ 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. +$(x_0,\ldots,x_{\ell-1})$ +(cf. \ref{fundamental-neighorhood-terminates-game} : elle ne peut que +gagner à partir de là). Or 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} + +\begin{proof}[Seconde démonstration] +Comme dans la première démonstration (premier paragraphe), on remarque +qu'il suffit de traiter le cas ouvert. Soit $A \subseteq +X^{\mathbb{N}}$ ouvert. + +On utilise la notion d'ordinaux qui sera introduite ultérieurement. +Soit $X^* := \bigcup_{\ell=0}^{+\infty} X^\ell$ l'arbre des positions +de $G_X$. + +On définit les positions « gagnantes en $0$ coups pour Alice » comme +les positions $(x_0,\ldots,x_{\ell-1})$ qui définissent un voisinage +fondamental inclus dans $A$ +(cf. \ref{fundamental-neighorhood-terminates-game} : quoi que les +joueurs fassent à partir de là, Alice aura gagné, et on peut +considérer qu'Alice a déjà gagné). + +En supposant définies les positions gagnantes en $\alpha$ coups pour +Alice, on définit les positions « gagnantes en $\alpha+1$ coups pour + Alice » de la façon suivante : ce sont les positions +$(x_0,\ldots,x_{\ell-1})$ où c'est à Alice de jouer et pour lesquelles +il existe un $x$ tel que $(x_0,\ldots,x_{\ell-1},x)$ soit gagnante en +$\alpha$ coups pour Alice, ainsi que les positions +$(x_0,\ldots,x_{\ell-1})$ où c'est à Bob de jouer et pour lesquels, +quel que soit $x\in X$, la position $(x_0,\ldots,x_{\ell-1},x)$ est +gagnante en $\alpha+1$ coups pour Alice (au sens où on vient de le +dire). + +Enfin, si $\delta$ est un ordinal limite, en supposant définies les +positions « gagnantes en $\alpha$ coups pour Alice » pour tout $\alpha +< \delta$, on définit une position comme gagnante en $\delta$ coups +par Alice lorsqu'elle est gagnante en $\alpha$ coups pour un +certain $\alpha < \delta$. + +La définition effectuée a les propriétés suivantes : (o) si une +position est gagnante en $\alpha$ coups pour Alice alors elle est +gagnante en $\alpha'$ coups pour tout $\alpha'>\alpha$, (i) si une +position où c'est à Bob de jouer est gagnante en $\alpha$ coups pour +Alice, alors tout coup (de Bob) conduit à une position gagnante en +$\alpha$ coups pour Alice, et (ii) si une position où c'est à Alice de +jouer est gagnante en $\alpha > 0$ coups pour Alice, alors il existe +un coup (d'Alice) conduisant à une position gagnante en strictement +moins que $\alpha$ coups (en fait, si $\alpha = \beta+1$ est +successeur, il existe un coup conduisant à une position gagnante en +$\beta$ coups par Alice, et si $\alpha$ est limite, la position +elle-même est déjà gagnable en strictement moins que $\alpha$ coups). + +Si la position initiale $()$ est gagnante en $\alpha$ coups par Alice +pour un certain ordinal $\alpha$, alors Alice possède une stratégie +gagnante consistant à jouer, depuis une position gagnante en $\alpha$ +coups, vers une position gagnante en $\beta$ coups pour un certain +$\beta < \alpha$ (ou bien $\beta = 0$), qui existe d'après (ii) +ci-dessus : comme Bob ne peut passer d'une position gagnante en +$\alpha$ coups par Alice que vers d'autres telles positions (cf. (i)), +et comme toute suite strictement décroissante d'ordinaux termine, ceci +assure à Alice d'arriver en temps fini à une position gagnante en $0$ +coups. + +Réciproquement, si la position initiale $()$ n'est pas gagnante en +$\alpha$ coups par Alice quel que soit $\alpha$ (appelons-la « non + comptée »), alors Bob possède une stratégie consistant à jouer +toujours sur des telles positions non décomptées : d'après la +définition des positiosn gagnantes en $\alpha$ coup, quand c'est à +Alice de jouer, une position non comptée ne conduit qu'à des positions +non comptées, et quand c'est à Bob de jouer, une position non comptée +conduit à au moins une condition non comptée. Ainsi, si Bob joue +selon cette stratégie, la confrontation $(x_0,x_1,x_2,\ldots)$ ne +passe que par des positions non comptées, et en particulier, ne passe +jamais par une position gagnante en $0$ coups par Alice, c'est-à-dire +qu'elle ne peut pas avoir un voisinage fondamental inclus dans $A$, et +comme $A$ est ouvert, elle n'appartient pas à $A$, i.e., la +confrontation est gagnée par Bob. \end{proof} |