Well-founded graphs and well-founded induction.

1 files changed, 206 insertions, 0 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 183307a..18cfddc 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -29,6 +29,7 @@
 \newtheorem{lem}[comcnt]{Lemme}
 \newtheorem{thm}[comcnt]{Théorème}
 \newtheorem{cor}[comcnt]{Corollaire}
+\newtheorem{scho}[comcnt]{Scholie}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -751,6 +752,211 @@ Avec les hypothèses et notations du corollaire, l'ensemble des $x$
 tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
 compact $C_0 \neq \varnothing$ inclus dans $C$.
 
+
+%
+%
+%
+
+\section{Théorie combinatoire des jeux impartiaux}
+
+\subsection{Graphes orientés bien-fondés}
+
+\begin{defn}
+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
+ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
+d'un ensemble $G$ muni d'une relation $E$ irreflexive.  Les éléments
+de $G$ s'appelle \textbf{sommets} et les éléments de $E$
+\textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une
+arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de
+cible $y$, ou encore que $y$ est \textbf{atteint} par une arête de
+source $x$, ou encore que $y$ est un \textbf{successeur} de $x$.  Un
+sommet qui n'a pas de successeur est dit \textbf{terminal} dans $G$.
+
+Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
+que $E$ l'est alors aussi).  Il est dit \textbf{acyclique} lorsqu'il
+n'existe pas de suite finie (« cycle ») $x_0,\ldots,x_{n-1}$ de
+sommets telle que $(x_i,x_{i+1})$ soit une arête pour chaque $0\leq
+i\leq n-1$, où on convient que $x_n = x_0$.
+
+Un graphe orienté (possiblement infini) est dit \textbf{bien-fondé}
+lorsqu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets telle
+que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$.
+\end{defn}
+
+\thingy 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
+$x_0,x_1,x_2,\ldots$ avec une arête de $x_i$ à $x_{i+1}$ pour
+chaque $i$, il doit exister $n$ tel que $x_n = x_0$, et on obtient
+alors un cycle $x_0,\ldots,x_{n-1}$.  En général, cependant, les
+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}
+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
+accessible à partir de $x$ lorsqu'il existe $x =
+x_0,x_1,\ldots,x_{n-1},x_n = y$ tels que pour chaque $i$ le sommet
+$x_{i+1}$ soit atteint par une arête de source $x_i$ (on autorise
+$n=0$, c'est-à-dire que chaque sommet est toujours accessible à partir
+de lui-même).
+
+L'ensemble des sommets accessibles à partir d'un sommet $x$
+s'appellera aussi l'\textbf{aval} de $x$.  On peut considérer l'aval
+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).
+
+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}
+
+\begin{prop}[induction bien-fondée]\label{well-founded-induction}
+Pour un graphe orienté $G$, les affirmations suivantes sont
+équivalentes :
+
+\begin{itemize}
+\item[(*)]$G$ est bien-fondé.
+\item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$
+  contient un sommet $x \in N$ qui est terminal pour $N$,
+  c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in
+  N$ (i.e., aucun successeur 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 successeur de $x$
+    appartient à $P$, alors $x$ lui-même appartient à $P$ », alors $P
+  = G$.
+\end{itemize}
+\end{prop}
+\begin{proof}
+L'équivalence entre (\dag) et (\ddag) est complètement formelle : elle
+s'obtient en posant $P = G\setminus N$ ou réciproquement $N =
+G\setminus P$, en passant à la contraposée, et en passant aussi à la
+contraposée à l'intérieur de la propriété entre guillemets
+dans (\ddag), et encore une fois dans la prémisse de cette propriété
+(« tout successeur de $x$ appartient à $P$ » équivaut à « aucun
+  successeur de $x$ n'appartient à $N$ », i.e., « $x$ est terminal
+  pour $N$ »).
+
+Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à
+l'ensemble $N := \{x_0,x_1,x_2,\ldots\}$ des sommets d'une suite telle
+qu'il y ait une arête de $x_i$ à $x_{i+1}$.
+
+Pour montrer que (*) implique (\dag), on suppose que $N$ est un
+ensemble non-vide de sommets sans sommet terminal : comme $N$ est
+non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas terminal on
+peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par une arête,
+puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de suite — par
+récurrence (et par l'axiome du choix [dépendants]), on construit ainsi
+une suite $(x_i)$ de sommets telle qu'il y ait une arête de $x_i$
+à $x_{i+1}$.
+\end{proof}
+
+La définition (*) choisie pour un graphe bien-fondé est la plus
+compréhensible, mais en un certain sens la définition (\ddag) est « la
+  bonne » (en l'absence de l'axiome du choix, il faut utiliser (\dag)
+ou (\ddag), et en mathématiques constructives il faut
+utiliser (\ddag)).
+
+\begin{prop}
+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$
+vérifiant la propriété « lorsque $x \in G$ est tel que tout successeur
+  de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ »
+(i.e., la propriété entre guillemets dans (\ddag)
+de \ref{well-founded-induction}).
+\end{prop}
+\begin{proof}
+Il est clair que la partie bien-fondée $Q$ de $G$ vérifie cette
+propriété.  Maintenant, si $P$ vérifie la propriété en question, alors
+$P \cap Q$ la vérifie aussi, ce qui montre bien que $Q$ est la plus
+petite.
+\end{proof}
+
+\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.
+Notons $\mathrm{succ}(x) = \{y : (x,y) \in E\}$ l'ensemble des
+successeurs d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une
+arête de source $x$).
+
+Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et
+$f$ une fonction de l'ensemble des successeurs de $x$ vers $Z$
+(autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \big(\{x\}\times
+Z^{\mathrm{succ}(x)}\big)$).  Soit enfin $\Phi\colon \mathscr{F} \to Z$
+une fonction quelconque.  Alors il existe une unique fonction $f\colon
+G \to Z$ telle que pour tout $x \in G$ on ait
+\[
+f(x) = \Phi(x,\, f|_{\mathrm{succ}(x)})
+\]
+\end{thm}
+\begin{proof}
+Montrons d'abord l'unicité : si $f$ et $f'$ vérifient toutes les deux
+la propriété anoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels
+que $f(x) = f'(x)$.  Si $x \in G$ est tel que $\mathrm{succ}(x)
+\subseteq P$, c'est-à-dire que $f|_{\mathrm{succ}(x)} =
+f'|_{\mathrm{succ}(x)}$, alors $f(x) = \Phi(x,\,
+f|_{\mathrm{succ}(x)}) = \Phi(x,\, f'|_{\mathrm{succ}(x)}) = f'(x)$,
+autrement dit, $x\in P$.  La phrase précédente affirme précisément que
+$P$ vérifie la propriété entre guillemets dans (\ddag)
+de \ref{well-founded-induction}, et d'après la proposition en
+question, on a donc $P = G$, c'est-à-dire $f = f'$.  Ceci montre
+l'unicité.
+
+\textcolor{red}{Existence...}
+\end{proof}
+
+Ce théorème est difficile à lire.  En voici une traduction
+informelle :
+
+\begin{scho}
+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 sommets successeurs de $x$ : autrement dit, on
+peut librement utiliser la valeur de $f(y)$ sur chaque sommet $y$
+successeur de $x$, dans la définition de $f(x)$.
+\end{scho}
+
+Voici un exemple d'application de la définition par induction
+bien-fondée.
+
+\begin{defn}
+Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
+qu'un nombre fini de successeurs.  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\mathrm{succ}(x)\} + 1$ où $\mathrm{succ}(x)$ désigne l'ensemble
+des successeurs de $x$ et où on est convenu que $\max\varnothing =
+-1$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) :
+y\in\mathrm{succ}(x)\} + 1$ (avec $\Phi(x, r) = 0$ si $x$ est terminal
+dans $G$) et qu'on appelle $\rho$ la fonction telle que $\rho(x) =
+\Phi(x, \rho|_{\mathrm{succ}(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 $G$.
+\end{defn}
+
+\thingy Autrement dit, un sommet de rang $0$ est un sommet terminal,
+un sommet de rang $1$ est un sommet non-terminal dont tous les
+successeurs sont terminaux, un sommet de rang $2$ est un sommet dont
+tous les successeurs 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.
+
 %
 %
 %