summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex99
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}