Reorganized by moving stuff on non-well-founded graphs to a different section.

1 files changed, 81 insertions, 59 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 8cea295..20f6ee3 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -786,6 +786,13 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 
 \subsection{Graphes orientés bien-fondés}
 
+Le but de cette section est de présenter les outils fondamentaux sur
+les graphes orientés bien-fondés (cf. \ref{definitions-graphs})
+permettant utiles à la théorie combinatoire des jeux impartiaux.  Il
+s'agit notamment de la théorie de l'induction bien-fondée
+(cf. \ref{scholion-well-founded-induction}
+et \ref{scholion-well-founded-definition}).
+
 \begin{defn}\label{definitions-graphs}
 Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
 d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
@@ -822,7 +829,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}\label{definition-accessibility-downstream-wfpart}
+\begin{defn}\label{definition-accessibility-downstream}
 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
@@ -838,12 +845,6 @@ de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire, considérer le
 graphe dont l'ensemble des sommets est l'aval de $x$ et dont les
 arêtes sont celles qui partent d'un tel sommet).  On remarquera la
 convention faite que $x$ appartient à son propre aval.
-
-L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
-autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
-suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour
-chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
-source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
 \end{defn}
 
 \thingy On peut remarquer que la relation d'accessibilité sur $G$ est
@@ -852,7 +853,7 @@ seulement si $G$ est acyclique.  Lorsque $G$ est bien-fondé, la
 relation d'accessibilité est elle-même bien-fondée (i.e., le graphe
 qu'elle définit est bien-fondé).
 
-\begin{defn}
+\begin{defn}\label{definition-downstream-closed-inductive}
 Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
 $G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
 « si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $P$ »
@@ -861,7 +862,7 @@ $G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
 
 Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$
 est \textbf{aval-inductif} lorsqu'il vérifie la propriété suivante :
-« lorsque $x \in G$ est tel que tout voisin sortant de $x$ appartient
+« si $x \in G$ est tel que tout voisin sortant de $x$ appartient
   à $P$, alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient
   tout sommet dont tous les voisins sortants sont dans $P$ »).
 \end{defn}
@@ -878,13 +879,6 @@ 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 :
@@ -896,9 +890,10 @@ Pour un graphe orienté $G$, les affirmations suivantes sont
   c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in
   N$ (i.e., aucun voisin sortant de $x$ n'appartient à $N$).
 \item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété
-  suivante « lorsque $x \in G$ est tel que tout voisin sortant de $x$
+  suivante « si $x \in G$ est tel que tout voisin sortant de $x$
     appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e.,
-  « $P$ est aval-inductif »), alors $P = G$.
+  « $P$ est aval-inductif »,
+  cf. \ref{definition-downstream-closed-inductive}), alors $P = G$.
 \end{itemize}
 \end{prop}
 \begin{proof}
@@ -931,43 +926,17 @@ compréhensible, mais en un certain sens la définition (\ddag) est « la
 ou (\ddag), et en mathématiques constructives il faut
 utiliser (\ddag)).  En voici une traduction informelle :
 
-\begin{scho}
+\begin{scho}\label{scholion-well-founded-induction}
 Pour montrer une propriété $P$ sur les sommets d'un graphe bien-fondé,
 on peut supposer (comme « hypothèse d'induction »), lorsqu'il s'agit
 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}\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
-  G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors
-  $x$ lui-même appartient à $P$ » entre guillemets dans (\ddag)
-de \ref{well-founded-induction}).
-\end{prop}
-\begin{proof}
-La plus petite partie aval-inductive de $G$ a bien un sens, car
-l'intersection de toutes les parties aval-inductives est encore
-aval-inductive (cf. \ref{trivial-remark-downstream}).
-
-Si $x$ est un sommet de $G$ et $\downstr(x)$ désigne son aval
-(considéré comme sous-graphe induit de $G$), il est clair que pour
-toute partie $P$ aval-inductive de $G$, la partie $P \cap \downstr(x)$
-de $\downstr(x)$ est aval-inductive dans ce dernier (le point
-important étant que les voisins sortants d'un sommet de $\downstr(x)$
-dans ce dernier sont les mêmes que ceux dans $G$).  En particulier, si
-$\downstr(x)$ est bien-fondé (c'est-à-dire, si $x$ appartient à la
-partie bien-fondée de $G$), alors $x$ appartient à toute partie
-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é,
-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}
+Exactement comme le principe de récurrence sur les entiers naturels,
+le principe d'induction bien-fondée peut servir non seulement à
+démontrer des propriétés sur les graphes bien-fondés, mais aussi à
+définir des fonctions dessus :
 
 \begin{thm}[définition par induction bien-fondée]\label{well-founded-definition}
 Soit $G$ un graphe orienté bien-fondé et $Z$ un ensemble quelconque.
@@ -1019,7 +988,7 @@ C'est ce qu'on voulait.
 Ce théorème est difficile à lire.  En voici une traduction
 informelle :
 
-\begin{scho}
+\begin{scho}\label{scholion-well-founded-definition}
 Pour définir une fonction $f$ sur un graphe bien-fondé, on peut
 supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e.,
 connu) sur tous les voisins sortants de $x$ : autrement dit, on
@@ -1052,14 +1021,11 @@ tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de
 rang exactement $1$, et ainsi de suite.
 
 Il revient au même de définir le rang de la manière suivante : le rang
-$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est le plus
-grand $n$ tel qu'il existe une suite $x_0,x_1,\ldots,x_n$ telle que
-$x_0 = x$ et que pour chaque $i$ le sommet $x_{i+1}$ soit atteint par
-une arête de source $x_i$.
-
-Pour un graphe non supposé bien-fondé, on peut définir son rang comme
-on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) =
-\infty$ lorsque $x$ n'appartient pas à la partie bien-fondée.
+$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus
+grande longueur possible d'un chemin orienté partant de $x$,
+c'est-à-dire, le plus grand $n$ tel qu'il existe une suite
+$x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le
+sommet $x_{i+1}$ soit atteint par une arête de source $x_i$.
 
 Voici un autre exemple de définition par induction bien-fondée :
 
@@ -1112,6 +1078,62 @@ de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins
   moins un P-sommet pour voisin sortant}.
 \end{defn}
 
+On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si
+le graphe est bien-fondé, les P-sommets sont les positions du jeu à
+partir desquelles le joueur précédent a une stratégie gagnante, tandis
+que les N-sommets sont celles à partir desquelles le joueur suivant
+(`N' comme « Next ») a une stratégie gagnante (consistant, justement,
+à jouer vers un P-sommet).
+
+
+\subsection{Généralisations aux graphes non nécessairement bien-fondés}
+
+\begin{defn}\label{definition-wfpart}
+L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
+autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
+suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour
+chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
+source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
+\end{defn}
+
+\thingy\label{trivial-remark-wfpart} 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}\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é « si $x \in
+  G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors
+  $x$ lui-même appartient à $P$ »,
+cf. \ref{definition-downstream-closed-inductive}).
+\end{prop}
+\begin{proof}
+La plus petite partie aval-inductive de $G$ a bien un sens, car
+l'intersection de toutes les parties aval-inductives est encore
+aval-inductive (cf. \ref{trivial-remark-downstream}).
+
+Si $x$ est un sommet de $G$ et $\downstr(x)$ désigne son aval
+(considéré comme sous-graphe induit de $G$), il est clair que pour
+toute partie $P$ aval-inductive de $G$, la partie $P \cap \downstr(x)$
+de $\downstr(x)$ est aval-inductive dans ce dernier (le point
+important étant que les voisins sortants d'un sommet de $\downstr(x)$
+dans ce dernier sont les mêmes que ceux dans $G$).  En particulier, si
+$\downstr(x)$ est bien-fondé (c'est-à-dire, si $x$ appartient à la
+partie bien-fondée de $G$), alors $x$ appartient à toute partie
+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é,
+cf. \ref{trivial-remark-wfpart}), donc un sommet qui appartient à
+toute partie aval-inductive de $G$ est, en particulier, dans la partie
+bien-fondée de $G$.
+\end{proof}
+
 
 \subsection{Écrasement transitif}
 
@@ -1251,7 +1273,7 @@ auteurs font implicitement une des deux hypothèses
 « 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-accessibility-downstream-wfpart}) du graphe $G$.
+(cf. \ref{definition-wfpart}) du graphe $G$.
 
 \begin{defn}
 Pour un jeu $G$ comme