Transitive collapse, etc.

1 files changed, 69 insertions, 16 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index fede523..2ccd9ff 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -32,6 +32,7 @@
 \newtheorem{scho}[comcnt]{Scholie}
 \renewcommand{\qedsymbol}{\smiley}
 %
+\newcommand{\succr}{\operatorname{succ}}
 \newcommand{\mex}{\operatorname{mex}}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -772,8 +773,10 @@ 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$.
+source $x$, ou encore que $y$ est un \textbf{successeur} de $x$, et on
+notera $\succr(x) = \{y : (x,y) \in E\}$ l'ensemble des successeurs
+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
@@ -883,27 +886,27 @@ petite.
 
 \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
+Notons $\succr(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$
+Z^{\succr(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)})
+f(x) = \Phi(x,\, f|_{\succr(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)$,
+que $f(x) = f'(x)$.  Si $x \in G$ est tel que $\succr(x)
+\subseteq P$, c'est-à-dire que $f|_{\succr(x)} =
+f'|_{\succr(x)}$, alors $f(x) = \Phi(x,\,
+f|_{\succr(x)}) = \Phi(x,\, f'|_{\succr(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
@@ -932,12 +935,11 @@ 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 =
+y\in\succr(x)\} + 1$ 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
+y\in\succr(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
+\Phi(x, \rho|_{\succr(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$.
@@ -966,12 +968,12 @@ 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
 $\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(y) :
-y\in\mathrm{succ}(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
+y\in\succr(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
 := \mathbb{N}\setminus S$ pour le plus petit entier naturel
 \emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose
-$\Phi(x, g) = \mex\{g(y) : y\in\mathrm{succ}(x)\}$ et qu'on appelle
+$\Phi(x, g) = \mex\{g(y) : y\in\succr(x)\}$ et qu'on appelle
 $\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
-\gamma|_{\mathrm{succ}(x)})$ dont l'existence et l'unicité sont
+\gamma|_{\succr(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$.
@@ -983,6 +985,57 @@ successeurs (ceci inclut le cas particulier d'un sommet terminal),
 tandis qu'un sommet de valeur de Grundy $>0$ est un sommet ayant au
 moins un sommet de valeur de Grundy $0$ comme successeur.
 
+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.
+
+\begin{defn}\label{definition-transitive-collapse}
+Soit $G$ un graphe orienté bien-fondé.  En utilisant le
+théorème \ref{well-founded-definition} (modulo la remarque qui suit),
+on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
+y\in\succr(x)\}$.  L'image de $G$ par la fonction $f$ (c'est-à-dire
+l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
+  transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
+$f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
+autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
+orienté) s'appelle l'écasement transitif du sommet $x$.
+\end{defn}
+
+\thingy En particulier, un sommet terminal a pour
+écrasement $\varnothing$, un sommet qui n'a pour successeurs que des
+sommets terminaux a pour écrasement $\{\varnothing\}$, un sommet qui
+n'a pour successeurs que de tels sommets a pour écrasement
+$\{\{\varnothing\}\}$ tandis que s'il a aussi des sommets terminaux
+pour successeurs ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$,
+et ainsi de suite.
+
+Il y a une subtilité ensembliste dans la définition ci-dessus, c'est
+qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel
+$f$ prend sa valeur : il faut en fait appliquer une généralisation
+de \ref{well-founded-definition} où $Z$ est remplacé par l'univers de
+tous les ensembles : nous ne rentrerons pas dans ces subtilités, et
+admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui
+vérifie $f(x) = \{f(y) : y\in\succr(x)\}$ pour chaque $x\in G$.
+
+\begin{defn}
+Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux
+sommets $x$ et $x'$ ayant le même ensemble de successeurs ($\succr(x)
+= \succr(x')$) sont égaux.
+\end{defn}
+
+\begin{prop}
+Un graphe orienté bien-fondé est extensionnel si et seulement si sa
+fonction d'écrasement $f$ définie
+en \ref{definition-transitive-collapse} est injective.
+\end{prop}
+\begin{proof}
+Supposons $G$ transitif et montrons par induction bien-fondée que $f$
+est injective sur l'aval de tout sommet $x$.  Soit $P$ l'ensemble des
+$y$ tels que $f$ restreinte à l'aval de $y$ soit injective.  Soit $x$
+un sommet dont tous les successeurs appartiennent à $P$ :
+\textcolor{red}{à finir.}
+\end{proof}
+
 %
 %
 %