Determinacy of combinatorial games for positional strategies (fairly tedious).upload-20160308

1 files changed, 387 insertions, 194 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index d30e163..2c4cf75 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -2113,22 +2113,396 @@ notion de « stratégie » implicite dans le
 théorème \ref{determinacy-of-perfect-information-games} est une notion
 \emph{historique} : puisque c'est ainsi qu'elles ont été définies
 en \ref{definition-strategies-for-gale-stewart-games}, les stratégies
-ont le droit de choisir le coup à jouer en fonction de tous les coups
-joués antérieurement.  Il se trouve en fait qu'on a les mêmes
+ont le droit de choisir le coup à jouer en fonction de \emph{tous les
+  coups joués antérieurement}.  Il se trouve en fait qu'on a les mêmes
 résultats avec des stratégies \emph{positionnelles}, c'est-à-dire, qui
-ne choisissent un coup qu'en fonction du sommet $x \in G$.
+ne choisissent un coup qu'en fonction du sommet $x \in G$.  C'est ce
+qui va être démontré dans la section suivante.
 
-\textcolor{red}{À compléter.}
 
-% Note: if we consider the tree of the historical strategy, all of its
-% branches are finite (because an infinite branch would be a draw).
+\subsection{Détermination pour les stratégies positionnelles}
 
-% Note: consider a maximal winning-from-were-defined positional
-% strategy (Zorn), show that it is defined on all "positional N"
-% positions.  All inductive P resp. N are positional P resp. N by
-% minimality, and all inductive D are positional D by explicit
-% strategy, and ditto for s/positional/historical/, so they all
-% coincide.
+\thingy Le but de la définition suivante est de formaliser, pour un
+jeu combinatoire comme
+en \ref{first-definition-impartial-combinatorial-game}, les notions de
+stratégie positionnelle (dans laquelle un joueur ne choisit le coup à
+jouer qu'en fonction de la position actuelle), et de stratégie
+historique (dans laquelle il fait son choix en fonction de tous les
+coups joués antérieurement), sachant qu'on veut montrer au final que
+cette distinction a peu d'importance.  Mais la définition sur laquelle
+on va vraiment travailler est formulée
+en \ref{set-of-everywhere-winning-positional-strategies}, donc on peut
+se contenter de lire celle-ci.
+
+\begin{defn}
+Soit $G$ un graphe orienté
+(cf. \ref{first-definition-impartial-combinatorial-game} et \ref{definitions-graphs}).
+Une \textbf{stratégie positionnelle} sur $G$ est une fonction
+partielle $\varsigma\colon G \dasharrow G$ (i.e., une fonction définie
+sur un sous-ensemble de $G$) telle que $\varsigma(x)$ soit, s'il est
+défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut
+comprendre que le joueur abandonne la partie).  Une \textbf{stratégie
+  historique} sur $G$ une fonction partielle $\varsigma
+\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où
+$\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des
+suites finies de $G$ de longueur non nulle (i.e., des suites
+$z_0,\ldots,z_{\ell-1}$ d'éléments de $G$ avec $\ell>0$ entier) telle
+que $\varsigma(z_0,\ldots,z_{\ell-1})$ soit un voisin sortant
+de $z_{\ell-1}$.
+
+Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ (à
+partir d'une position initiale $x_0$) on a $\varsigma(x_i) = x_{i+1}$
+pour chaque $i$ pair pour lequel $x_i$ est défini, on dit que le
+premier joueur a joué la partie selon la stratégie positionnelle
+$\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour chaque $i$
+impair pour lequel $x_i$ est défini, on dit que le second joueur a
+joué la partie selon la stratégie $\tau$.  Pour une stratégie
+historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$ et $\tau(x_i)
+= x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et
+$\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement.
+
+La position initiale $x_0 \in G$ ayant été fixée, si $\varsigma$ et
+$\tau$ sont deux stratégies (positionnelles ou historiques), on
+définit $\varsigma \ast \tau$ comme la confrontation jouée lorsque le
+premier joueur joue selon $\varsigma$ et le second joue selon $\tau$ :
+autrement dit, $x_0$ est la position initiale, et, si $x_i$ est
+défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ ou
+$\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou
+$\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas
+défini, la suite s'arrête là).
+
+La stratégie (positionnelle ou historique) $\varsigma$ est dite
+\textbf{gagnante pour le premier joueur} à partir de la position
+initiale $x_0$ lorsque le premier joueur gagne toute confrontation où
+il joue selon $\varsigma$, c'est-à-dire que la confrontation est finie
+et que le dernier $x_i$ défini l'est pour un $i$ impair.  On définit
+de même une stratégie $\varsigma$ \textbf{survivante} (c'est-à-dire,
+permettant d'assurer au moins le nul) pour le premier joueur à partir
+d'une position initiale $x_0$, c'est-à-dire que dans toute
+confrontation où il joue selon $\varsigma$, soit la confrontation est
+infinie (donc nulle) soit le dernier $x_i$ défini l'est pour un $i$
+impair.
+\end{defn}
+
+\thingy La notion de stratégie pour le second joueur peut être définie
+de façon analogue, bien sûr, mais la notion n'a pas beaucoup
+d'intérêt : une stratégie gagnante pour le second joueur à partir de
+$x_0$ est la même chose qu'une stratégie gagnante pour le premier
+joueur à partir de tout voisin sortant de $x_0$.  Pour travailler avec
+les stratégies positionnelles, il vaut mieux supposer qu'elles sont,
+en fait, gagnantes partout où elles sont définies, ce qui amène à
+faire la définition suivante :
+
+\thingy\label{set-of-everywhere-winning-positional-strategies} Dans ce
+qui suit, on va fixer un graphe orienté $G$ et on aura besoin
+d'introduire l'ensemble $\mathcal{S}$ de ce qu'on pourrait appeler les
+« stratégies positionnelles gagnantes partout où définies »,
+c'est-à-dire des stratégies positionnelles $\varsigma$ gagnantes pour
+le premier joueur à partir de n'importe quel point $x_0$ où
+$\varsigma$ est défini ; autrement dit, il s'agit de l'ensemble des
+fonctions partielles $\varsigma\colon G \dasharrow G$ telles que
+\begin{itemize}
+\item si $\varsigma(x)$ est défini alors il est un voisin sortant
+  de $x$, et que
+\item si $\varsigma(x_0)$ est défini et si $(x_i)$ est une suite
+  (\textit{a priori} finie ou infinie) partant de $x_0$, dans laquelle
+  $\varsigma(x_i) = x_{i+1}$ pour $i$ impair, et $x_{i+1}$ est voisin
+  sortant de $x_i$ pour tout $i$, alors la suite est de longueur finie
+  et le dernier $x_i$ défini l'est pour un $i$ impair
+\end{itemize}
+(i.e., le premier joueur gagne n'importe quelle confrontation à partir
+d'une position initiale $x_0$ du domaine de définition de $\varsigma$
+et où il joue selon $\varsigma$).
+
+L'ensemble $\mathcal{S}$ est partiellement ordonné par l'inclusion (si
+$\varsigma,\tau \in \mathcal{S}$, on dit que $\varsigma$
+\textbf{prolonge} $\tau$ et on note $\varsigma \supseteq \tau$ ou
+$\tau \subseteq \varsigma$, lorsque l'ensemble de définition de
+$\varsigma$ contient celui de $\tau$ et que $\varsigma$ et $\tau$
+coïncident là où $\tau$ est définie : ceci signifie bien que
+$\varsigma \supseteq \tau$ en tant qu'ensembles).
+
+\begin{lem}\label{positional-strategies-merging-lemma}
+Si $\varsigma,\varsigma' \in \mathcal{S}$ avec la notation introduite
+en \ref{set-of-everywhere-winning-positional-strategies}, alors il
+existe $\varsigma'' \in \mathcal{S}$ qui prolonge $\varsigma$ et qui
+est également définie en tout point où $\varsigma'$ l'est.
+\end{lem}
+\begin{proof}
+Définissons $\varsigma''$ par $\varsigma''(x) = \varsigma(x)$ si
+$\varsigma(x)$ est définie et $\varsigma''(x) = \varsigma'(x)$ si
+$\varsigma(x)$ n'est pas définie mais que $\varsigma'(x)$ l'est.  Il
+est évident que $\varsigma''$ prolonge $\varsigma$ et est également
+définie en tout point où $\varsigma'$ l'est : il reste à voir que
+$\varsigma'' \in \mathcal{S}$.  Mais si $x_0,x_1,x_2,\ldots$
+(\textit{a priori} finie ou infinie) est une confrontation jouée par
+le premier joueur selon $\varsigma''$, montrons qu'elle est
+nécessairement gagnée par le premier joueur : or le premier joueur a
+soit joué selon $\varsigma$ tout du long, soit selon $\varsigma'$ tout
+du long, soit selon $\varsigma'$ puis $\varsigma$, mais dans tous les
+cas il gagne.  De façon détaillée : soit $x_0$ est domaine de
+définition de $\varsigma$ auquel cas tous les $x_i$ pairs le sont et
+la confrontation est gagnée par le premier joueur ; soit $x_0$ est
+dans le domaine de définition de $\varsigma'$ mais pas de $\varsigma$,
+auquel cas il n'existe qu'un nombre fini de $i$ pairs tels que $x_i$
+ne soit pas dans domaine de définition de $\varsigma$ (puisque
+$\varsigma'$ ne peut pas donner une partie nulle) et si $j$ est le
+plus grand d'entre eux, $x_{j+1}$ est défini, et soit $x_{j+2}$ n'est
+pas défini (auquel cas le premier joueur a gagné) soit $x_{j+2}$ est
+dans le domaine de définition de $\varsigma$ et de nouveau le premier
+joueur gagne à partir de là.
+\end{proof}
+
+\begin{lem}\label{positional-strategies-union-lemma}
+Si $\varsigma_i \in \mathcal{S}$ pour chaque $i\in I$ avec la notation
+introduite en \ref{set-of-everywhere-winning-positional-strategies},
+et si pour tous $i,j$ les fonctions $\varsigma_i$ et $\varsigma_j$
+coïncident là où elles sont toutes deux définies, alors la fonction
+$\bigcup_{i\in I} \varsigma_i$ (c'est-à-dire la fonction définie sur
+la réunion des ensembles de définition des $\varsigma_i$ et qui
+coïncide avec n'importe quel $\varsigma_i$ sur l'ensemble de
+définition de celui-ci) appartient encore à $\mathcal{S}$.
+\end{lem}
+\begin{proof}
+Si $x_0,x_1,x_2,\ldots$ (\textit{a priori} finie ou infinie) est une
+confrontation jouée par le premier joueur selon $\varsigma :=
+\bigcup_{i\in I} \varsigma_i$, alors en fait elle est jouée tout du
+long selon $\varsigma_i$ où $i$ est n'importe quel indice tel que
+$\varsigma_i(x_0)$ soit définie.  Comme $\varsigma_i \in \mathcal{S}$,
+cette confrontation est gagnée par le premier joueur.
+\end{proof}
+
+Le résultat ensembliste suivant sera admis (même si on pourrait s'en
+sortir en appliquant \ref{fixed-point-lemma-for-partial-functions} à
+la place) :
+\begin{lem}[principe maximal de Hausdorff]\label{hausdorff-maximal-principle}
+Soit $\mathscr{F}$ un ensemble de parties d'un ensemble $A$.  On
+suppose que $\mathscr{F}$ est non vide et que pour toute partie non
+vide $\mathscr{T}$ de $\mathscr{F}$ totalement ordonnée par
+l'inclusion (c'est-à-dire telle que pour $P,P' \in \mathscr{T}$ on a
+soit $P \subseteq P'$ soit $P \supseteq P'$) la réunion $\bigcup_{P
+  \in \mathscr{T}} P$ soit contenue dans un élément de $\mathscr{F}$.
+Alors il existe dans $\mathscr{F}$ un élément $M$ maximal pour
+l'inclusion (c'est-à-dire que si $P \supseteq M$ avec $P \in
+\mathscr{F}$ alors $P=M$).
+\end{lem}
+
+\begin{prop}\label{existence-of-maximal-positional-strategy}
+Avec la notation introduite
+en \ref{set-of-everywhere-winning-positional-strategies}, il existe
+$\varsigma \in \mathcal{S}$ maximal pour l'inclusion (au sens où si
+$\varsigma \subseteq \varsigma'$ avec $\varsigma' \in \mathcal{S}$
+alors $\varsigma = \varsigma'$) ; de plus, si $\varsigma' \in
+\mathcal{S}$, alors $\varsigma$ est défini en tout point où
+$\varsigma'$ l'est.
+\end{prop}
+\begin{proof}
+L'existence de $\varsigma \in \mathcal{S}$ maximal pour l'inclusion
+découle immédiatement de \ref{hausdorff-maximal-principle} en
+utilisant \ref{positional-strategies-union-lemma} pour constater que
+si $\mathscr{T} \subseteq \mathcal{S}$ est totalement ordonné pour
+l'inclusion alors la réunion $\bigcup_{\varsigma\in\mathscr{T}}
+\varsigma$ appartient à $\mathcal{S}$.
+
+Une fois trouvé $\varsigma \in \mathcal{S}$ maximal pour l'inclusion,
+si $\varsigma' \in \mathcal{S}$,
+d'après \ref{positional-strategies-merging-lemma}, on peut trouver
+$\varsigma''$ prolongeant $\varsigma$ et défini partout où
+$\varsigma'$ l'est, et comme $\varsigma$ est maximal, on a
+$\varsigma'' = \varsigma$, donc $\varsigma$ est bien défini partout où
+$\varsigma'$ l'est.
+\end{proof}
+
+\thingy\label{notation-n-and-p-sets-for-combinatorial-games} En
+contituant les notations introduites
+en \ref{set-of-everywhere-winning-positional-strategies}, on fixe
+maintenant $\varsigma \in \mathcal{S}$ maximal pour l'inclusion (dont
+l'existence est garantie par la
+proposition \ref{existence-of-maximal-positional-strategy}).  Soit $N$
+l'ensemble des sommets $x$ de $G$ où $\varsigma(x)$ est défini (i.e.,
+le domaine de définition de $\varsigma$) ; on vient de voir que $N$
+est aussi l'ensemble des points où un élément quelconque de
+$\mathcal{S}$ est défini, i.e., l'ensemble des positions à partir
+desquelles le premier joueur a une stratégie positionnelle gagnante.
+Soit $P$ l'ensemble des sommets $x\in G$ dont tous les voisins
+sortants appartiennent à $N$ (y compris s'il n'y a pas de voisin
+sortant, i.e., si $x$ est un puits) : clairement, $P$ est l'ensemble
+des positions à partir desquelles le second joueur a une stratégie
+positionnelle gagnante (quel que soit le coup du joueur adversaire, il
+amènera à une position où on a une stratégie gagnante).
+
+Enfin, on note $D := G\setminus(N\cup P)$ l'ensemble des sommets
+restants.
+
+\begin{prop}
+Avec les notations introduites en
+\ref{set-of-everywhere-winning-positional-strategies} et \ref{notation-n-and-p-sets-for-combinatorial-games},
+\begin{itemize}
+\item[(i)]un sommet $x\in G$ appartient à $N$ si et seulement si il a
+  au moins un voisin sortant qui appartient à $P$,
+\item[(ii)]un sommet $x\in G$ appartient à $P$ si et seulement si tous
+  ses voisins sortants appartiennent à $N$.
+\end{itemize}
+\end{prop}
+\begin{proof}
+L'affirmation (ii) est la définition même de $P$ et n'a donc pas à
+être prouvée.  Il s'agit donc de montrer (i).
+
+Si $x\in N$ alors $y := \varsigma(x)$ est un voisin sortant de $x$ qui
+appartient à $P$ puisque $\varsigma \in \mathcal{S}$.  Réciproquement,
+si $x$ a un voisin sortant $y$ qui appartient à $P$, et si
+$\varsigma(x)$ n'était pas défini, on pourrait étendre $\varsigma$ en
+posant $\varsigma(x) = y$, ce qui donnerait un élément de
+$\mathcal{S}$ (toute partie jouée à partir de $x$ conduit à $y$ et de
+là à des points où $\varsigma$ est définie, donc est gagnée par le
+premier joueur), contredisant la maximalité de $\varsigma$ ; c'est
+donc que $\varsigma(x)$ était bien défini, i.e., $x\in N$.
+\end{proof}
+
+\thingy Par contraposée, sur l'ensemble $D := G\setminus(N\cup P)$ des
+sommets restants de $G$, on a les propriétés suivantes : $x\in G$
+appartient à $D$ si et seulement si
+\begin{itemize}
+\item[(i*)]tous les voisins sortants de $x$ sont dans $N\cup D$
+  \emph{et}
+\item[(ii*)]au moins l'un d'entre eux appartient à $D$.
+\end{itemize}
+
+On définit alors une stratégie positionnelle $\tau$ étendant
+$\varsigma$ de la façon suivante : si $\varsigma(x)$ est défini (i.e.,
+$x \in N$), on pose $\tau(x) = \varsigma(x)$, et si $x \in D$ on
+choisit pour $\tau(x)$ un voisin sortant de $x$ qui appartienne à $D$
+(lequel voisin existe d'après (ii*)).  À partir d'un sommet $x_0$
+dans $D$, si l'un ou l'autre joueur joue selon $\tau$, ce joueur
+survit, puisque soit son adversaire le laisse toujours dans $D$ auquel
+cas le joueur considéré peut toujours jouer (selon $\tau$) en restant
+dans $D$, soit son adversaire quitte $D$ et d'après (i*) joue
+vers $N$, et alors le joueur considéré gagne puisqu'il joue
+selon $\varsigma$.
+
+Bref, à partir d'un sommet de $N$ le premier joueur a une stratégie
+\emph{positionnelle} gagnante, à partir d'un sommet de $P$ c'est le
+second joueur qui en a une, et à partir d'un sommet de $D$ les deux
+joueurs ont une stratégie positionnelle survivante.  (Dans tous les
+cas, on peut utiliser le $\tau$ qu'on vient de construire comme
+stratégie positionnelle.)
+
+\begin{thm}\label{positional-determinacy-of-perfect-information-games}
+Soit $G$ un graphe orienté.  Quel que soit le sommet $x_0$ de $G$
+choisi comme position initiale, dans le jeu combinatoire impartial à
+information parfaite considéré
+en \ref{first-definition-impartial-combinatorial-game}, exactement
+l'une des trois affirmations suivantes est vraie :
+\begin{itemize}
+\item le premier joueur (Alice) possède une stratégie positionnelle gagnante,
+\item le second joueur (Bob) possède une stratégie positionnelle gagnante,
+\item chacun des deux joueurs possède une stratégie positionnelle survivante.
+\end{itemize}
+
+En particulier, l'existence d'une stratégie positionnelle gagnante ou
+survivante est équivalente à celle d'une stratégie historique de même
+nature.
+
+De plus, si $N,P,D$ sont les ensembles de sommets $x_0$ à partir
+desquels chacune des trois affirmations ci-dessus est vraie,
+\begin{itemize}
+\item un sommet $x\in G$ appartient à $N$ si et seulement si il a
+  au moins un voisin sortant qui appartient à $P$,
+\item un sommet $x\in G$ appartient à $P$ si et seulement si tous
+  ses voisins sortants appartiennent à $N$,
+\item un sommet $x\in G$ appartient à $D$ si et seulement si tous ses
+  voisins sortants appartiennent à $N\cup D$ et au moins l'un d'eux
+  appartient à $D$.
+\end{itemize}
+\end{thm}
+\begin{proof}
+L'existence des stratégies positionnelles a déjà été montré ci-dessus,
+ainsi que les propriétés sur $N,P,D$.  L'équivalence entre stratégies
+positionnelles et historiques vient du fait que toute stratégie
+positionnelle peut être vue comme une stratégie historique (en
+ignorant l'historique) et du fait que les trois cas sont exclusifs
+aussi bien pour les stratégies historiques que positionnelles.
+\end{proof}
+
+\thingy On a en particulier redémontré le
+théorème \ref{determinacy-of-perfect-information-games}, même si la
+démonstration suivie ici (consistant à prendre une stratégie
+positionnelle maximale pour l'inclusion) n'est peut-être pas très
+éclairante.
+
+En utilisant la notion d'ordinaux, on pourrait donner une autre
+démonstration, plus explicite, du
+théorème \ref{positional-determinacy-of-perfect-information-games} :
+elle consiste à reprendre la seconde démonstration qui a été donnée du
+théorème \ref{determinacy-of-perfect-information-games} et à constater
+qu'en la modifiant à peine elle conduit maintenant à définir une
+stratégie positionnelle ; un peu plus précisément, on définit par
+induction sur l'ordinal $\alpha$ les positions gagnantes en $\alpha$
+coups par le premier joueur et les positions gagnantes en $\alpha$
+coups par le second joueur, et une stratégie gagnante consiste à jouer
+d'une position gagnante en $\alpha$ coups pour le premier joueur vers
+une position gagnante en $\beta<\alpha$ coups pour le second joueur
+(pour les stratégies survivantes, on complète en jouant d'une position
+non étiquetée vers une position non étiquetée, mais le problème de la
+survie est de toute façon plus simple).
+
+Dans le cas des jeux définis par un graphe bien-fondé
+(cf. \ref{definitions-graphs}), c'est-à-dire que le nul est
+impossible, la détermination est beaucoup plus simple à démontrer en
+on en verra encore une nouvelle démonstration dans le cadre de la
+théorie de Grundy.
+
+Un bonus au
+théorème \ref{positional-determinacy-of-perfect-information-games} est
+l'affirmation suivante :
+
+\begin{prop}
+Dans le contexte du
+théorème \ref{positional-determinacy-of-perfect-information-games}, si
+$N^*,P^*,D^*$ est une partition de $G$ en trois parties vérifiant les
+trois propriétés qui ont été énoncées pour $N,P,D$ (en remplaçant
+$N,P,D$ par $N^*,P^*,D^*$ respectivement), alors on a $N\subseteq N^*
+\subseteq N\cup D$ et $P\subseteq P^* \subseteq P\cup D$ et bien sûr
+$D\supseteq D^*$.
+
+En particulier, si on utilise le
+théorème \ref{non-well-founded-definition} ci-dessous pour définir la
+\emph{plus petite} (pour l'inclusion) fonction partielle $f\colon G
+\dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$ telle que $f(x)$ vaille
+$\mathrm{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel
+$f(y) = \mathrm{N}$, et que $f(x)$ vaille $\mathrm{N}$ ssi pour tout
+voisin sortant $y$ de $x$ on a $f(y) = \mathrm{P}$, alors $f(x)$ vaut
+$\mathrm{P}$ ou bien $\mathrm{N}$ ou bien est indéfinie lorsque
+respectivement le premier joueur a une stratégie gagnante, le second
+joueur en a une, ou les deux ont une stratégie survivante.
+\end{prop}
+\begin{proof}
+Si $N^*,P^*,D^*$ ont les mêmes propriétés que $N,P,D$, on peut définir
+une stratégie (positionnelle) consistant à jouer à partir de $N^*$
+dans $P^*$ (c'est-à-dire à choisir pour chaque sommet de $N^*$ un
+voisin sortant dans $P^*$) et à partir de $D^*$ dans $D^*$ : si le
+premier joueur suit cette stratégie à partir d'un sommet dans $N^*$ ou
+$D^*$ ne peut pas perdre puisque les propriétés des parties font que
+son coup sera toujours défini : donc $N^* \cup D^* \subseteq N \cup
+D$, ce qui signifie en passant au complémentaire $P^* \supseteq P$, et
+si le second joueur suit cette stratégie à partir d'un sommet dans
+$P^*$ ou $D^*$ il ne peut pas perdre non plus : donc $P^* \cup D^*
+\subseteq P \cup D$, ce qui signifie exactement $N^* \supseteq N$.
+
+Le deuxième paragraphe est une reformulation de la même affirmation :
+la fonction $f \colon G \dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$
+définie par $f(x) = \mathrm{P}$ lorsque $x \in P$ et $f(x) =
+\mathrm{N}$ lorsque $x \in N$ est la plus petite fonction partielle
+vérifiant les propriétés qu'on a dites, i.e., la plus petite telle que
+$f(x) = \Phi(x, f|_{\outnb(x)})$ avec les notations du
+théorème \ref{non-well-founded-definition} et $\Phi(x, g)$ valant
+$\mathrm{N}$ si $g(y)$ est défini et vaut $\mathrm{N}$ pour au moins
+un $y \in \outnb(x)$ et $\mathrm{P}$ si $g(y)$ est défini et vaut
+$\mathrm{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente
+en la seconde variable, on est bien dans le cas d'application
+duthéorème \ref{non-well-founded-definition}, même si ici on a déjà
+démontré l'existence d'une plus petite $f$).
+\end{proof}
 
 
 
@@ -2568,7 +2942,7 @@ partout sur la partie bien-fondée de $G$.
 
 La démonstration du théorème repose crucialement sur le lemme suivant,
 dont on va donner deux démonstrations :
-\begin{lem}
+\begin{lem}\label{fixed-point-lemma-for-partial-functions}
 Soient $X$ et $Z$ deux ensembles quelconques : notons $\mathscr{D}$
 l'ensemble des fonctions partielles $X\dasharrow Z$, qu'on verra comme
 des parties de $X\times Z$ ne contenant jamais deux couples $(x,z_1)$
@@ -2791,187 +3165,6 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$).
 %
 %
 
-\section{Théorie combinatoire des jeux impartiaux à information parfaite}\label{section-combinatorial-impartial-games}
-
-\textcolor{red}{Section à refondre.}
-
-\subsection{Généralités sur les jeux et stratégies}
-
-\begin{defn}\label{definition-impartial-combinatorial-game}
-Un jeu \textbf{impartial à information parfaite} est un graphe
-orienté $G$ muni d'un sommet $x_0$ appelé \textbf{position initiale}
-et vérifiant de plus :
-\begin{itemize}
-\item pour un jeu « court » : $G$ est fini acyclique (ou de façon
-  équivalente, fini et bien-fondé) ;
-\item pour un jeu « terminant » : $G$ est bien-fondé ;
-\item pour un jeu « fini à boucles » : $G$ est fini.
-\item pour un jeu « non nécessairement terminant » : (aucune
-  hypothèse).
-\end{itemize}
-Les sommets de $G$ sont aussi appelés les \textbf{positions} de $G$,
-et les voisins sortants d'une position $x \in G$ sont aussi appelés
-les \textbf{options} à partir de $x$.
-
-On supposera que tout sommet de $G$ est accessible à partir de $x_0$ ;
-si ce n'est pas le cas, il reviendra au même de supprimer tous les
-sommets inaccessibles, assurant du coup cette hypothèse.
-\end{defn}
-
-La terminologie est malheureusement peu standardisée : la plupart des
-auteurs font implicitement une des deux hypothèses
-(« bien-fondé »=« terminant », et/ou « fini ») sur le jeu $G$, le cas
-« court » étant la conjonction des deux.  Ici, on fera le plus souvent
-l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait
-que cela signifie que $x_0$ appartient à la partie bien-fondée
-(cf. \ref{definition-wfpart}) du graphe $G$.
-
-\thingy\label{playing-from-a-position} Si $G$ est un jeu comme
-en \ref{definition-impartial-combinatorial-game}, et $x \in G$ une
-position quelconque de $G$, on définit le jeu joué \textbf{à partir}
-de $x$ comme l'aval de $x$ (c'est-à-dire l'ensemble des positions
-accessibles à partir de $x$,
-cf. \ref{definition-accessibility-downstream}) considéré comme un
-graphe (le sous-graphe induit) et muni du sommet $x$ lui-même comme
-position initiale.  Ceci définit un nouveau jeu qui sera parfois noté
-$G_x$ et qui sera parfois identifié à $x$ quand aucune confusion ne
-peut en résulter.  (Ainsi, $G_{x_0}$ est exactement $G$.)
-
-De façon moins formelle : on peut toujours considérer une position $x$
-quelconque d'un jeu $G$ comme position initiale d'un nouveau jeu (le
-jeu joué si une fois atteinte la position $x$).  Cette remarque
-triviale permet de considérer n'importe quelle fonction d'un jeu
-impartial à information parfaite comme une fonction de n'importe
-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} 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
-un $i$ pair, on dit que le premier joueur \textbf{perd} et que les
-second \textbf{gagne}, tandis que lorsque le dernier $x_i$ défini
-l'est pour un $i$ impair, on dit que le premier joueur gagne et que le
-second perd ; enfin, lorsque $x_i$ est défini pour tout entier
-naturel $i$ (ce qui ne peut pas se produire si $G$ est bien-fondé), on
-dit que la partie est nulle ou que les deux joueurs \textbf{survivent}
-sans gagner.
-\end{defn}
-
-\thingy Il est parfois plus agréable de donner aux joueurs des noms
-comme « Alice » et « Bob ».  Il faut néanmoins se rappeler, dans la
-théorie des jeux \emph{impartiaux} considérée dans cette section, que
-l'identité des joueurs n'est inscrite nulle part dans le jeu : ils ont
-tous les deux toutes les options possibles depuis chaque position
-(comparer le jeu de Hackenbush impartial avec les autres
-en \ref{introduction-hackenbush}).
-
-Plutôt que de parler de « premier » et de « second » joueur, on peut
-aussi parler de \textbf{joueur suivant} et de \textbf{joueur
-  précédent} : le joueur suivant est celui qui doit jouer,
-c'est-à-dire le premier, et le joueur précédent est celui qui vient de
-jouer, c'est-à-dire le second.  (Ceci est d'ailleurs très malheureux
-compte tenu des initiales de ces quatre mots...)  Il peut paraître
-bizarre de dire que le second joueur « vient de jouer » quand on
-commence la partie, mais c'est logique vu que c'est à l'autre de
-jouer, et c'est cohérent avec la
-convention \ref{playing-from-a-position} : si on a atteint la position
-$x$ d'un jeu $G$, le second joueur pour le jeu $G_x$ partant de $x$
-est bien le joueur qui vient de jouer pour amener à la position $x$.
-L'avantage de parler de joueur suivant et de joueur précédent est
-qu'on se rappelle plus facilement qu'ils échangent leurs rôles à
-chaque tour.  À l'inverse, quand on nomme les joueurs Alice et Bob, on
-entend généralement que l'un ou l'autre peut commencer mais qu'ils
-gardent leur identité d'un tour sur l'autre.
-
-\medbreak
-
-Définissons maintenant la notion de stratégie.  On distinguera les
-stratégies positionnelles, où le choix d'un coup à effectuer dépend
-uniquement de l'état du jeu, et les stratégies historiques, où le
-choix dépend de tous les coups joués jusqu'à ce point :
-
-\begin{defn}
-Pour un jeu $G$ comme
-en \ref{definition-impartial-combinatorial-game}, une
-\textbf{stratégie positionnelle} est une fonction partielle
-$\varsigma\colon G \dasharrow G$ telle que $\varsigma(x)$ soit, s'il
-est défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut
-comprendre que le joueur abandonne la partie).  Une \textbf{stratégie
-  historique} est une fonction partielle $\varsigma
-\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où
-$\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des
-suites finies de $G$ de longueur non nulle (i.e., des suites
-$z_0,\ldots,z_{\ell-1}$ d'éléments de $G$ avec $\ell>0$ entier) telle
-que $\varsigma(z_0,\ldots,z_{\ell-1})$ soit un voisin sortant
-de $z_{\ell-1}$.
-
-Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ on
-a $\varsigma(x_i) = x_{i+1}$ pour chaque $i$ pair pour lequel $x_i$
-est défini, on dit que le premier joueur a joué la partie selon la
-stratégie positionnelle $\varsigma$ ; tandis que si $\tau(x_i) =
-x_{i+1}$ pour chaque $i$ impair pour lequel $x_i$ est défini, on dit
-que le second joueur a joué la partie selon la stratégie $\tau$.  Pour
-une stratégie historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$
-et $\tau(x_i) = x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et
-$\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement.
-
-Si $\varsigma$ et $\tau$ sont deux stratégies (positionnelles ou
-historiques), on définit $\varsigma \ast \tau$ comme la partie jouée
-lorsque le premier joueur joue selon $\varsigma$ et le second joue
-selon $\tau$ : autrement dit, $x_0$ est la position initiale du jeu,
-et, si $x_i$ est défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ ou
-$\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou
-$\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas
-défini, la suite s'arrête là).
-
-La stratégie (positionnelle ou historique) $\varsigma$ est dite
-\textbf{gagnante pour le premier joueur} lorsque le premier joueur
-gagne toute partie où il joue selon $\varsigma$.  La stratégie $\tau$
-est dite \textbf{gagnante pour le second joueur} lorsque le second
-joueur gagne toute partie où il joue selon $\tau$.  On définit de même
-une stratégie \textbf{survivante} (c'est-à-dire, permettant d'assurer
-au moins le nul) pour le premier joueur, resp. le second joueur.
-\end{defn}
-
-Le résultat suivant explique que, au moins pour les stratégies
-survivantes, la différence entre stratégies positionnelles et
-stratégies historiques est sans importance (ce sera aussi le cas pour
-les stratégies gagnantes, mais on le verra plus loin) :
-\begin{prop}
-Soit $G$ un jeu impartial à information parfaite : un joueur possède
-une stratégie positionnelle survivante si et seulement si ce même
-joueur possède une stratégie historique survivante.
-\end{prop}
-\begin{proof}
-Si $\varsigma$ est une stratégie positionnelle, on en déduit une
-stratégie historique $\varsigma_\sharp$ par
-$\varsigma_\sharp(z_0,\ldots,z_{\ell-1}) = \varsigma(z_{\ell-1})$
-(i.e., en ignorant l'historique).  Comme une partie est jouée selon
-$\varsigma_\sharp$ si et seulement si elle l'est selon $\varsigma$, il
-est évident que $\varsigma_\sharp$ est survivante si $\varsigma$
-l'est.  Traitons l'autre implication.  Mettons pour fixer les idées
-que le joueur considéré est le premier.
-
-Si $\varsigma$ est une stratégie historique, définissons une stratégie
-positionnelle $\varsigma_\flat$ de la façon suivante : si $y \in G$,
-s'il existe au moins une partie (=confrontation)
-$x_0,\ldots,x_{\ell-1}$ dans laquelle le premier joueur joue selon
-$\varsigma$ et vérifiant $x_{\ell-1} = y$, alors on pose
-$\varsigma_\flat(y) = \varsigma(x_0,\ldots,x_{\ell-1})$ pour un choix
-quelconque de $x_0,\ldots,x_{\ell-1}$ (et sinon, $\varsigma_\flat(y)$
-n'est pas défini).  Soit $x_0,x_1,x_2,\ldots$ une confrontation où le
-premier joueur joue selon $\varsigma_\flat$ : pour chaque $i$, la
-confrontation $x_0,\ldots,x_{2i}$ (s'arrêtant à $2i$) est jouée par le
-premier joueur selon $\varsigma$, et le fait que $\varsigma$ soit une
-stratégie survivante pour le premier joueur impose que
-$\varsigma(x_0,\ldots,x_{2i})$ soit défini, ce qui impose à son tour
-que $\varsigma_\flat(x_{2i})$ soit défini, i.e., $x_{2i+1}$ est
-toujours défini : donc le premier joueur survit.
-\end{proof}
-
 %
 %
 %