1 files changed, 70 insertions, 5 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index ded15ef..15ac029 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -850,7 +850,8 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
 stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
 a une.
 
-\thingy Les \textbf{jeux de Gale-Stewart} : soit $A$ un sous-ensemble de
+\thingy\label{introduction-gale-stewart-games} Les \textbf{jeux de
+  Gale-Stewart} (cf. section \ref{gale-stewart-games}) : soit $A$ un sous-ensemble de
 $\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$.
 Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans
 le premier cas) ou de $\{0,1\}$ (dans les deux suivants).  Ils jouent
@@ -903,6 +904,10 @@ sexes (\ref{battle-of-sexes}).  On évoque plus particulièrement les
 jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des
 jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}).
 
+La section \ref{gale-stewart-games} introduit la notion de jeux de
+Gale-Stewart et prouve un théorème fondamental de détermination (la
+détermination des jeux \emph{ouverts}).
+
 La section \ref{section-well-founded-induction} introduit la notion de
 graphe bien-fondée et d'induction bien-fondée qui est essentielle pour
 la suite.
@@ -1281,6 +1286,69 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 %
 %
 
+\section{Jeux de Gale-Stewart et détermination}\label{gale-stewart-games}
+
+\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
+\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é.}
+de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$.
+\end{defn}
+
+\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$
+(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$), 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égig gagnante, le jeu est dit \textbf{déterminé}.
+\end{defn}
+
+
+
+%
+%
+%
+
 \section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction}
 
 Le but de cette section est de présenter les outils fondamentaux sur
@@ -1989,10 +2057,7 @@ quelle position de n'importe quel jeu.
 \begin{defn}
 Soit $G$ un jeu comme
 en \ref{definition-impartial-combinatorial-game}.  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é.} de $G$ est une suite finie ou infinie $(x_i)$ de
+ou \textbf{confrontation} de $G$ est une suite finie ou infinie $(x_i)$ de
 sommets de $G$ telle que $x_0$ soit la position initiale et que pour
 chaque $i$ pour lequel $x_{i+1}$ soit défini, ce dernier soit un
 voisin sortant de $x_i$.  Lorsque le dernier $x_i$ défini l'est pour