From b5ccc9cc7db3aee752cee352181794ab7b122ab6 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 15 Dec 2015 15:22:07 +0100
Subject: Incremental improvements.

---
 notes-mitro206.tex | 89 ++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 69 insertions(+), 20 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 72876d7..8cea295 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -822,7 +822,7 @@ notions sont distinctes, l'exemple le plus évident étant sans doute
 celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$
 à $i+1$ pour chaque $i$.
 
-\begin{defn}
+\begin{defn}\label{definition-accessibility-downstream-wfpart}
 Si $G$ est un graphe orienté on appelle \textbf{relation
   d'accessibilité} la clôture réflexive-transitive de la relation
 donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est
@@ -878,6 +878,13 @@ intersection quelconque d'ensembles aval-inductifs est aval-inductive.
 Leur nature, au moins dans un graphe bien-fondé, va être précisée dans
 ce qui suit, et ceci justifiera le terme d'« aval-inductif ».
 
+Il sera utile pour la suite de remarquer que la partie bien-fondée
+de $G$ est à la fois aval-close et aval-inductive (car on peut
+construire une suite infinie $x_0, x_1, x_2\ldots$, avec $x_{i+1}$
+voisin sortant de $x_i$, commençant par un $x_0$ donné si et seulement
+si on peut le faire en commençant pour un certain voisin sortant $x_1$
+de ce $x_0$).
+
 \begin{prop}[induction bien-fondée]\label{well-founded-induction}
 Pour un graphe orienté $G$, les affirmations suivantes sont
 équivalentes :
@@ -931,7 +938,7 @@ de montrer que $x$ a la propriété $P$, que cette propriété est déjà
 connue de tous les voisins sortants de $x$.
 \end{scho}
 
-\begin{prop}
+\begin{prop}\label{wfpart-is-smallest-inductive}
 Si $G$ est un graphe orienté non supposé bien-fondé, la partie
 bien-fondée de $G$ est la plus petite (pour l'inclusion) partie $P$
 aval-inductive de $P$ (i.e., vérifiant la propriété « lorsque $x \in
@@ -956,9 +963,10 @@ aval-inductive de $G$.
 
 Mais réciproquement, la partie bien-fondée de $G$ est elle-même
 aval-inductive (car si $\downstr(y)$ est bien-fondé pour tout voisin
-sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé),
-donc un sommet qui appartient à toute partie aval-inductive de $G$
-est, en particulier, dans la partie bien-fondée de $G$.
+sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé,
+cf. \ref{trivial-remark-downstream}), donc un sommet qui appartient à
+toute partie aval-inductive de $G$ est, en particulier, dans la partie
+bien-fondée de $G$.
 \end{proof}
 
 \begin{thm}[définition par induction bien-fondée]\label{well-founded-definition}
@@ -1055,7 +1063,7 @@ on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) =
 
 Voici un autre exemple de définition par induction bien-fondée :
 
-\begin{defn}
+\begin{defn}\label{definition-grundy-function}
 Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
 qu'un nombre fini de voisins sortants.  En utilisant le
 théorème \ref{well-founded-definition}, on définit alors une fonction
@@ -1079,7 +1087,30 @@ de valeur de Grundy $0$ comme voisin sortant.
 
 On verra que la notion de fonction de Grundy, et particulièrement le
 fait que la valeur soit nulle ou pas, a énormément d'importance dans
-l'étude de la théorie des jeux impartiaux.
+l'étude de la théorie des jeux impartiaux.  On verra aussi comment la
+définir sans l'hypothèse que chaque sommet n'a qu'un nombre fini de
+voisins sortants (mais ce ne sera pas forcément un entier naturel).
+En attendant, peut se passer de cette hypothèse pour définir isolément
+l'ensemble des sommets de valeur de Grundy $0$ :
+
+\begin{defn}\label{definition-grundy-kernel}
+Soit $G$ un graphe orienté bien-fondé.  En utilisant le
+théorème \ref{well-founded-definition}, on définit alors une partie $P
+\subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P =
+\varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x)
+\to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la
+valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la
+fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence
+et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x
+\in G : f(x) = 0\}$.
+
+Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou
+P-positions) de $G$, tandis que les éléments du complémentaire
+$G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions)
+de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins
+  sortants sont des N-sommets, et un N-sommet est un sommet qui a au
+  moins un P-sommet pour voisin sortant}.
+\end{defn}
 
 
 \subsection{Écrasement transitif}
@@ -1218,7 +1249,9 @@ 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.
+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-accessibility-downstream-wfpart}) du graphe $G$.
 
 \begin{defn}
 Pour un jeu $G$ comme
@@ -1232,17 +1265,17 @@ Une \textbf{partie} 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 qu'Alice perd et que Bob gagne, tandis que lorsque
-le dernier $x_i$ défini l'est pour un $i$ impair, on dit qu'Alice
-gagne et que Bob 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
-survivent sans gagner.  Lorsque de plus $\varsigma(x_i) = x_{i+1}$
-pour chaque $i$ pair pour lequel $x_i$ est défini (et en interprétant
-$\bot$ comme « non-défini »), on dit qu'Alice a joué la partie selon
-la stratégie $\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour
-chaque $i$ impair pour lequel $x_i$ est défini, on dit que Bob a joué
-la partie selon la stratégie $\tau$.
+un $i$ pair, on dit qu'Alice \textbf{perd} et que Bob \textbf{gagne},
+tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair,
+on dit qu'Alice gagne et que Bob 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.  Lorsque de plus
+$\varsigma(x_i) = x_{i+1}$ pour chaque $i$ pair pour lequel $x_i$ est
+défini (et en interprétant $\bot$ comme « non-défini »), on dit
+qu'Alice a joué la partie selon la stratégie $\varsigma$ ; tandis que
+si $\tau(x_i) = x_{i+1}$ pour chaque $i$ impair pour lequel $x_i$ est
+défini, on dit que Bob a joué la partie selon la stratégie $\tau$.
 
 Si $\varsigma$ et $\tau$ sont deux stratégies, on définit $\varsigma
 \ast \tau$ comme la partie jouée lorsque Alice joue $\varsigma$ et Bob
@@ -1255,9 +1288,25 @@ s'arrête).
 La stratégie $\varsigma$ est dite \textbf{gagnante pour Alice} lorsque
 Alice gagne toute partie où elle joue selon $\varsigma$.  La stratégie
 $\tau$ est dite \textbf{gagnante pour Bob} lorsque Bob gagne toute
-partie où il joue selon $\tau$.
+partie où il joue selon $\tau$.  On définit de même une stratégie
+survivante (c'est-à-dire, permettant d'assurer au moins le nul) pour
+Alice, resp. Bob.
 \end{defn}
 
+\begin{thm}
+Soit $G$ un jeu impartial à information parfaite : exactement l'une
+des trois affirmations suivantes est vraie :
+\begin{itemize}
+\item Alice possède une stratégie gagnante,
+\item Bob possède une stratégie gagnante,
+\item Alice et Bob possèdent une stratégie survivante — ce cas ne
+  pouvant pas se produire si $G$ est terminant.
+\end{itemize}
+\end{thm}
+\begin{proof}
+\textcolor{red}{...}
+\end{proof}
+
 %
 %
 %
-- 
cgit v1.2.3

