More about well-founded and non-well-founded inductions.

1 files changed, 113 insertions, 20 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 92db678..409e706 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -2457,7 +2457,7 @@ Un bonus au
 théorème \ref{positional-determinacy-of-perfect-information-games} est
 l'affirmation suivante :
 
-\begin{prop}
+\begin{prop}\label{p-d-n-vertices-of-perfect-information-games}
 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
@@ -2520,7 +2520,7 @@ 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}).
 
-\subsection{Graphes orientés bien-fondés}
+\subsection{Graphes orientés bien-fondés}\label{subsection-well-founded-graphs}
 
 \begin{defn}\label{definitions-graphs}
 Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
@@ -2549,7 +2549,8 @@ arête pour tout $i\in\mathbb{N}$ (i.e., aucun cycle ni chemin infini,
 cf. ci-dessous).
 \end{defn}
 
-\thingy Il est évident que tout graphe bien-fondé est acyclique (s'il
+\thingy\label{finite-graph-is-well-founded-iff-acyclic} Il est
+évident que tout graphe bien-fondé est acyclique (s'il
 existe un cycle $x_0,\ldots,x_{n-1}$, on en déduit une suite infinie
 en posant $x_i = x_{i\mod n}$) ; pour un graphe \emph{fini}, la
 réciproque est vraie : en effet, s'il existe une suite infinie
@@ -2750,19 +2751,21 @@ voisin sortant de $x$, dans la définition de $f(x)$.
 Voici un exemple d'application de la définition par induction
 bien-fondée :
 
-\begin{defn}
+\begin{defn}\label{definition-well-founded-rank}
 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
-$\rho\colon G \to \mathbb{N}$ par $\rho(x) = \max\{\rho(y) :
-y\in\outnb(x)\} + 1$ où il est convenu que $\max\varnothing = -1$ ;
-formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) :
-y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ si $x$ est un puits, et
-qu'on appelle $\rho$ la fonction telle que $\rho(x) = \Phi(x,
-\rho|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par
-le théorème.  Cette fonction $\rho$ s'appelle la \textbf{fonction
-  rang} sur $G$, on dit que $\rho(x)$ est le rang (ou rang bien-fondé)
-d'un sommet $x$.
+qu'un nombre fini de voisins sortants (par exemple, un graphe fini
+acyclique).  En utilisant le théorème \ref{well-founded-definition},
+on définit alors une fonction $\rho\colon G \to \mathbb{N}$ par
+$\rho(x) = \max\{\rho(y) : y\in\outnb(x)\} + 1$ où il est convenu que
+$\max\varnothing = -1$ ; formellement, c'est-à-dire qu'on pose
+$\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$
+si $x$ est un puits, et qu'on appelle $\rho$ la fonction telle que
+$\rho(x) = \Phi(x, \rho|_{\outnb(x)})$ dont l'existence et l'unicité
+sont garanties par le théorème.  Cette fonction $\rho$ s'appelle la
+\textbf{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou
+rang bien-fondé) d'un sommet $x$.  (Voir
+aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
+généralisation.)
 \end{defn}
 
 \thingy Autrement dit, un sommet de rang $0$ est un puits,
@@ -2793,7 +2796,9 @@ $\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
 \gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont
 garanties par le théorème.  Cette fonction $\gamma$ s'appelle la
 \textbf{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
-valeur de Grundy d'un sommet $x$.
+valeur de Grundy d'un sommet $x$.  (Voir
+aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
+généralisation.)
 \end{defn}
 
 \thingy En particulier, un sommet de valeur de Grundy $0$ est un
@@ -2806,9 +2811,10 @@ 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.  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$ :
+voisins sortants (mais ce ne sera pas forcément un entier naturel :
+cf. \ref{ordinal-valued-rank-and-grundy-function}).  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
@@ -2836,6 +2842,53 @@ 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).
 
+\thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant
+sur la notion d'ordinaux introduite dans la
+section \ref{section-ordinals}, la fonction rang peut se généraliser à
+n'importe quel graphe bien-fondé (sans hypothèse de nombre fini de
+voisins sortants), à condition d'autoriser des valeurs ordinales
+quelconques : précisément, on définit $\rho(x) = \sup\{\rho(y)+1 :
+y\in\outnb(x)\}$ (avec cette fois $\sup\varnothing = 0$ pour garder
+$\rho(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rho(x)$ est le
+plus petit ordinal strictement supérieur à $\rho(y)$ pour tout
+$y\in\outnb(x)$.
+
+De même, la fonction de Grundy peut se généraliser à n'importe quel
+graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) :
+y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal
+\emph{n'appartenant pas} à $S$.  Il reste vrai que $\gamma(x)$ est nul
+si et seulement si $x$ est un N-sommet.
+
+\thingy\label{well-founded-induction-algorithm} Lorsque $G$ est
+\emph{fini} et bien-fondé, i.e., est un graphe fini acyclique
+(cf. \ref{finite-graph-is-well-founded-iff-acyclic}), la fonction $f$
+définie par le théorème \ref{well-founded-definition} peut se calculer
+algorithmiquement de la façon suivante :
+\begin{itemize}
+\item utiliser un algorithme de \textbf{tri topologique} (en ayant
+  inversé le sens des arêtes pour se ramener à la convention usuelle)
+  pour trouver une numérotation des sommets de $G$ telle que pour
+  toute arête $(x,y)$ de $G$ le sommet $y$ précède $x$ dans la
+  numérotation ;
+\item parcourir tous les éléments $x\in G$ dans l'ordre de cette
+  numérotation, et définir $f(x) = \Phi(x, f|_{\outnb(x)})$, qui aura
+  toujours un sens car tous les éléments de $\outnb(x)$ auront été
+  parcourus avant $x$.
+\end{itemize}
+Si le tri topologique a été effectué par parcours en largeur, il est
+compatible avec la fonction rang (et inversement, tout tri raffinant
+la fonction rang est un tri topologique et peut s'obtenir par parcours
+en largeur).  La notion de rang ordinal
+(cf. \ref{ordinal-valued-rank-and-grundy-function}) est donc une forme
+de généralisation transfinie du tri topologique.
+
+Un algorithme évitant le tri topologique, au prix d'une plus grande
+complexité, mais ayant le bénéfice de fonctionner dans une situation
+plus générale (graphes non nécessairement bien-fondés/acycliques),
+sera exposé dans la section suivante
+(cf. \ref{non-well-founded-induction-algorithm}).
+
+
 
 \subsection{Généralisations aux graphes non nécessairement bien-fondés}
 
@@ -3061,6 +3114,46 @@ $f_\alpha \subseteq h$ alors $f_{\alpha+1} = \Psi(f_\alpha) \subseteq
 est bien le plus petit $f$ tel que $\Psi(f) = f$.
 \end{proof}
 
+\thingy\label{non-well-founded-induction-algorithm} Lorsque $G$ est
+\emph{fini}, la fonction $f$ définie par le
+théorème \ref{non-well-founded-definition} (et \textit{a fortiori} par
+le théorème \ref{well-founded-definition}) peut se calculer
+algorithmiquement de la façon suivante :
+\begin{itemize}
+\item initialement, poser $f(x) = \mathtt{undefined}$ pour tout $x\in
+  G$ ;
+\item parcourir tous les éléments $x\in G$ et, si $f(y)$ est défini
+  pour suffisamment de voisins sortants $y$ de $x$ pour imposer
+  $f(x)$, autrement dit, si $\Phi(x, f|_{\outnb(x)})$ est défini,
+  alors définir $f(x)$ à cette valeur (noter qu'elle ne changera
+  jamais ensuite du fait de la cohérence de $\Phi$) ; et
+\item répéter l'opération précédente jusqu'à ce que $f$ ne change
+  plus.
+\end{itemize}
+La démonstration donnée avec les ordinaux correspond exactement à cet
+algorithme, à ceci près que « répéter l'opération » devra peut-être se
+faire de façon transfinie.
+
+\thingy Les différentes définitions par induction bien-fondée
+proposées en exemple dans la
+section \ref{subsection-well-founded-graphs}, c'est-à-dire la notion
+de rang bien-fondé (cf. \ref{definition-well-founded-rank}), de
+fonction de Grundy (cf. \ref{definition-grundy-function}) et de
+P-sommets et N-sommets (cf. \ref{definition-grundy-kernel}), et même
+la généralisation ordinale des deux premiers
+(cf. \ref{ordinal-valued-rank-and-grundy-function}), peuvent se
+généraliser à des graphes non nécessairement bien-fondés en utilisant
+le théorème \ref{non-well-founded-definition} : il faudra juste
+admettre que ce soient des fonctions \emph{partielles}, non définies
+sur certains sommets (voire, tous les sommets) qui ne sont pas dans la
+partie bien-fondée du graphe (cf. \ref{definition-wfpart}).
+Néanmoins, ces définitions ne présentent qu'un intérêt limité : le
+rang bien-fondé, par exemple, s'avère être défini exactement sur la
+partie bien-fondée de $G$ (vérification facile) et coïncider avec le
+rang bien-fondé sur ce sous-graphe, et pour ce qui est des P-sommets
+et N-sommets, on obtient exactement la fonction évoquée
+en \ref{p-d-n-vertices-of-perfect-information-games}.
+
 
 
 \subsection{Écrasement transitif}
@@ -3180,7 +3273,7 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$).
 %
 %
 
-\section{Introduction aux ordinaux}
+\section{Introduction aux ordinaux}\label{section-ordinals}
 
 \subsection{Présentation informelle}