New terminology: "downstream-closed" and "downstream-inductive", clarify things.

1 files changed, 83 insertions, 19 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 7c1f585..b0b9779 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -33,6 +33,7 @@
 \renewcommand{\qedsymbol}{\smiley}
 %
 \newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
 \newcommand{\mex}{\operatorname{mex}}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -823,10 +824,36 @@ 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}
 
-On peut remarquer que la relation d'accessibilité sur $G$ est
+\thingy On peut remarquer que la relation d'accessibilité sur $G$ est
 antisymétrique (i.e., est une relation d'ordre partiel) si et
-seulement si $G$ est acyclique.  \textcolor{red}{Détailler + discuter
-  si $G$ est bien-fondé.}
+seulement si $G$ est acyclique.  Lorsque $G$ est bien-fondé, la
+relation d'accessibilité est elle-même bien-fondée.
+
+\begin{defn}
+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$ »
+(i.e. « tout sommet accessible à partir d'un sommet de $P$ est encore
+  dans $P$ »).
+
+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
+  à $P$, alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient
+  tout sommet dont tous les voisins sortants sont dans $P$ »).
+\end{defn}
+
+\thingy\label{trivial-remark-downstream} Il est clair qu'une
+intersection ou réunion quelconque d'ensembles aval-clos est encore
+aval-close.  L'aval de $x$ (ensemble des sommets accessibles
+depuis $x$) est toujours aval-clos, et il est facile de se convaincre
+qu'un ensemble de sommets est aval-clos si et seulement si il est une
+réunion d'avals.
+
+Pour ce qui est des ensembles aval-inductifs, il est clair qu'une
+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.
 
 \begin{prop}[induction bien-fondée]\label{well-founded-induction}
 Pour un graphe orienté $G$, les affirmations suivantes sont
@@ -840,19 +867,19 @@ Pour un graphe orienté $G$, les affirmations suivantes sont
   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$
-    appartient à $P$, alors $x$ lui-même appartient à $P$ », alors $P
-  = G$.
+    appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e.,
+  « $P$ est aval-inductif »), 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 voisin sortant de $x$ appartient à $P$ » équivaut à « aucun
-voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un puits
-pour $N$ »).
+contraposée à l'intérieur de la propriété d'être aval-inductif (entre
+guillemets dans (\ddag)), et encore une fois dans la prémisse de cette
+propriété (« tout voisin sortant de $x$ appartient à $P$ » équivaut à
+« aucun voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un
+  puits 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
@@ -872,21 +899,43 @@ 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)).
+utiliser (\ddag)).  En voici une traduction informelle :
+
+\begin{scho}
+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}
 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 voisin sortant
-  de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ »
-(i.e., la propriété entre guillemets dans (\ddag)
+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}
-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.
+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é),
+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}
@@ -918,7 +967,22 @@ 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...}
+Pour montrer l'existence, on considère l'ensemble $\mathfrak{E}$ des
+fonctions $e\colon H\to Z$ définies sur une partie aval-close $H
+\subseteq G$ et telles que pour tout $e(x) = \Phi(x, e|_{\outnb(x)})$
+pour tout $x\in H$.  Si $e,e' \in \mathfrak{E}$ alors $e$ et $e'$
+coïncident là où toutes deux sont définies, comme le montre l'unicité
+qu'on a montrée (appliquée à $e$ et $e'$ sur l'ensemble aval-clos $H
+\cap H'$ de définition commun de $e$ et $e'$).  En particulier, la
+réunion [des graphes] de tous les $e\in\mathfrak{E}$ définit encore un
+élément $f$ de $\mathfrak{E}$, maximal pour le prolongement.  Soit $P$
+l'ensemble des $x \in G$ où $f$ est définie.  Si $P$ contient (i.e.,
+$f$ est définie sur) tous les voisins sortants d'un certain $x\in G$,
+alors $f$ est nécessairement définie aussi en $x$, sans quoi on
+pourrait l'y prolonger par $f(x) = \Phi(x,\, f|_{\outnb(x)})$, ce qui
+contredirait la maximalité de $f$.  Par induction bien-fondée, on en
+conclut $P = G$, c'est-à-dire que $f$ est définie sur $G$ tout entier.
+C'est ce qu'on voulait.
 \end{proof}
 
 Ce théorème est difficile à lire.  En voici une traduction