Well-ordered sets.

1 files changed, 213 insertions, 9 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index dbe81be..672c428 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -35,6 +35,7 @@
 %
 \newcommand{\outnb}{\operatorname{outnb}}
 \newcommand{\downstr}{\operatorname{downstr}}
+\newcommand{\precs}{\operatorname{precs}}
 \newcommand{\mex}{\operatorname{mex}}
 \newcommand{\id}{\operatorname{id}}
 \newcommand{\limp}{\Longrightarrow}
@@ -2569,6 +2570,11 @@ $x_{i+1}$ soit voisin sortant de $x_i$ (on autorise $n=0$,
 c'est-à-dire que chaque sommet est toujours accessible à partir de
 lui-même).
 
+On pourra aussi introduire la relation d'\textbf{accessibilité
+  stricte} qui est la clôture transitive : autrement dit, la
+différence avec l'accessibilité définie ci-dessus est qu'on
+impose $n>0$, i.e., on ne relie pas un sommet à lui-même.
+
 L'ensemble des sommets accessibles à partir d'un sommet $x$
 s'appellera aussi l'\textbf{aval} de $x$ et pourra se noter
 $\downstr(x)$ (c'est donc la plus petite partie $P$ de $G$ telle que
@@ -2581,16 +2587,17 @@ remarquera la convention faite que $x$ appartient à son propre aval.
 \end{defn}
 
 \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.  Lorsque $G$ est bien-fondé, la
-relation d'accessibilité est elle-même bien-fondée (au sens où le
+antisymétrique (i.e., est une relation d'ordre partiel large) si et
+seulement si $G$ est acyclique : l'accessibilité stricte est alors
+l'ordre strict correspondant.  Lorsque $G$ est bien-fondé, la relation
+d'accessibilité stricte est elle-même bien-fondée (au sens où le
 graphe qu'elle définit est bien-fondé) : si on la voit comme une
 relation d'ordre partiel ($x>y$ signifiant que $y$ est accessible à
 partir de $x$), cela signifie qu'il n'y a pas de suite strictement
 décroissante.
 
-Une relation d'ordre \emph{total} $>$ qui soit bien-fondée, i.e.,
-telle qu'il n'existe pas de suite strictement décroissante, est
+Une relation d'ordre \emph{total} (strict) $>$ qui soit bien-fondée,
+i.e., telle qu'il n'existe pas de suite strictement décroissante, est
 appelée un \textbf{bon ordre}, ou définir un ensemble
 \textbf{bien-ordonné}.
 
@@ -3319,15 +3326,17 @@ $\omega+1 > \omega$).
 
 \thingy Comme la récurrence pour les entiers naturels, il y a sur les
 ordinaux (ou de façon équivalente, sur les ensembles bien-ordonnés) un
-principe d'\emph{induction transfinie}, qui est en fait l'application
-directe à eux du principe d'induction bien-fondée : son énoncé est
-essentiellement le même que le principe parfois appelé de « récurrence
-forte » pour les entiers naturels, c'est-à-dire que :
+principe d'\emph{induction transfinie}
+(cf. \ref{scholion-transfinite-induction}), qui est en fait
+l'application directe à eux du principe d'induction bien-fondée : son
+énoncé est essentiellement le même que le principe parfois appelé de
+« récurrence forte » pour les entiers naturels, c'est-à-dire que :
 \begin{center}
 Pour montrer une propriété sur tous les ordinaux $\alpha$ on peut
 faire l'hypothèse d'induction qu'elle est déjà connue pour les
 ordinaux $<\alpha$ au moment de la montrer pour $\alpha$.
 \end{center}
+
 Comme la récurrence sur les entiers naturels, et comme l'induction
 bien-fondée dont c'est un cas particulier, l'induction transfinie
 permet soit de \emph{démontrer} des propriétés sur les ordinaux, soit
@@ -3537,6 +3546,201 @@ successeur si et seulement si le dernier terme (le plus à droite) est
 un entier naturel non nul.
 
 
+\subsection{Ensembles bien-ordonnés et induction transfinie}
+
+\thingy Un ensemble \textbf{[partiellement] ordonné} est un ensemble
+muni d'une relation $>$ (d'ordre \emph{strict}) qui soit à la fois
+\begin{itemize}
+\item irréflexive ($x>x$ n'est jamais vrai quel que soit $x$), et
+\item transitive ($x>y$ et $y>z$ entraînent $x>z$).
+\end{itemize}
+Une telle relation est automatiquement antisymétrique ($x>y$ et $y>x$
+ne sont jamais simultanément vrais pour $x\neq y$).  On peut tout
+aussi bien définir un ensemble partiellement ordonné en utilisant
+l'ordre \emph{large} $\geq$ ($x\geq y$ étant défini par $x>y$ ou
+$x=y$, ou symétriquement $x>y$ étant défini par $x\geq y$ et $x\neq
+y$), réflexive, antisymétrique et transitive.  On note bien sûr $x\leq
+y$ pour $y\geq x$ et $x<y$ pour $y>x$.
+
+Un ensemble partiellement ordonné est dit \textbf{totalement ordonné}
+lorsque pour tous $x\neq y$ on a soit $x>y$ soit $y>x$.
+
+Un ensemble totalement ordonné bien-fondé $W$ est dit
+\textbf{bien-ordonné}.  D'après \ref{well-founded-induction}, ceci
+peut se reformuler de différentes façons :
+\begin{itemize}
+\item[(*)]$W$ est un ensemble totalement ordonné dans lequel il
+  n'existe pas de suite strictement décroissante.
+\item[(\dag)]$W$ est un ensemble (partiellement) ordonné dans lequel
+  toute partie \emph{non vide} $N$ a un plus petit élément.
+\item[(\ddag)]$W$ est totalement ordonné, et si une partie $P\subseteq
+  W$ vérifie la propriété suivante « si $x \in W$ est tel que tout
+    élément strictement plus petit que $x$ appartient à $P$, alors $x$
+    lui-même appartient à $P$ » (on pourra dire « $P$ est inductif »),
+  alors $P = W$.
+\end{itemize}
+(Dans (\dag), « partiellement ordonné » suffit car si $\{x,y\}$ a un
+plus petit élément c'est bien qu'on a $x<y$ ou $y>x$.)
+
+\begin{scho}[principe d'induction transfinie]\label{scholion-transfinite-induction}
+Pour montrer une propriété $P$ sur les éléments d'un ensemble
+bien-ordonné $W$, 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 éléments strictement plus petits
+que $x$.
+\end{scho}
+
+\begin{prop}\label{downward-closed-subsets-of-well-ordered-sets}
+Soit $W$ un ensemble bien-ordonné et $S \subseteq W$ tel que $u < v$
+avec $v \in S$ implique $u \in S$ (on peut dire que $S$ est
+« aval-clos »).  Alors soit $S = W$ soit il existe $x\in W$ tel que $S
+= \precs(x) := \{y\in W : y<x\}$.
+\end{prop}
+\begin{proof}
+Si $S \neq W$, soit $x$ le plus petit élément de $W$ qui n'est pas
+dans $S$.  Si $y < x$ alors $y \in S$ par minimalité de $x$.  Si $y
+\geq x$ alors on a $y \not\in S$ car le contraire ($y \in S$)
+entraînerait $x \in S$ d'après l'hypothèse faite sur $S$.  On a donc
+montré que $y \in S$ si et seulement si $y < x$, c'est-à-dire
+précisément $S = \precs(x)$.
+\end{proof}
+
+Le théorème suivant est un cas particulier du
+théorème \ref{well-founded-definition} :
+
+\begin{thm}[définition par induction transfinie]\label{transfinite-definition}
+Soit $W$ un ensemble bien-ordonné et $Z$ un ensemble quelconque.
+Notons $\precs(x) = \{y : y<x\}$ l'ensemble des éléments strictement
+plus petits que $x$ dans $W$.
+
+Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in W$ et
+$f$ une fonction de $\precs(x)$ vers $Z$ (autrement dit, $\mathscr{F}$
+est $\bigcup_{x \in W} \big(\{x\}\times Z^{\precs(x)}\big)$).  Soit
+enfin $\Phi\colon \mathscr{F} \to Z$ une fonction quelconque.  Alors
+il existe une unique fonction $f\colon W \to Z$ telle que pour tout $x
+\in W$ on ait
+\[
+f(x) = \Phi(x,\, f|_{\precs(x)})
+\]
+\end{thm}
+
+\begin{scho}\label{scholion-transfinite-definition}
+Pour définir une fonction $f$ sur un ensemble bien-ordonné, on peut
+supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e.,
+connu) sur tous les éléments strictement plus petits que $x$ :
+autrement dit, on peut librement utiliser la valeur de $f(y)$
+pour $y<x$, dans la définition de $f(x)$.
+\end{scho}
+
+\thingy Avant d'énoncer les résultats suivants, faisons une remarque
+évidente et une définition.  La remarque est que si $W$ est
+bien-ordonné et $E \subseteq W$ est un sous-ensemble de $W$, alors $E$
+est lui-même bien ordonné (pour l'ordre induit) ; ceci s'applique en
+particulier à $\precs(x) = \{y : y<x\}$.  La définition est qu'une
+fonction $f$ entre ensembles ordonnés est dite \textbf{croissante}
+lorsque $x \leq y$ implique $f(x) \leq f(y)$, et \textbf{strictement
+  croissante} lorsque $x < y$ implique $f(x) < f(y)$, ce qui entre des
+ensembles totalement ordonnés signifie exactement la même chose que
+« injective et croissante ».
+
+\begin{prop}
+Si $W$ est un ensemble bien-ordonné, et si $f\colon W\to W$ est
+strictement croissante, alors $x \leq f(x)$ pour tout $x\in W$.
+\end{prop}
+\begin{proof}
+Montrons par induction transfinie que $x \leq f(x)$.  Par hypothèse
+d'induction, on peut supposer $y \leq f(y)$ pour tout $y<x$.
+Supposons par l'absurde $f(x) < x$.  Alors l'hypothèse d'induction
+appliquée à $y := f(x)$ donne $f(x) \leq f(f(x))$, tandis que la
+stricte croissance de $f$ appliquée à $f(x) < x$ donne $f(f(x)) <
+f(x)$.  On a donc une contradiction.
+\end{proof}
+
+\begin{cor}
+Si $W$ est bien-ordonné, la seule bijection croissante $W \to W$ est
+l'identité.
+\end{cor}
+\begin{proof}
+Si $f\colon W\to W$ est une bijection croissante, la proposition
+précédente appliquée à $f$ montre $x \leq f(x)$ pour tout $x \in W$,
+mais appliquée à $f^{-1}$ elle montre $x \leq f^{-1}(x)$ donc $f(x)
+\leq x$ et finalement $f(x) = x$.
+\end{proof}
+
+\begin{cor}
+Si $W,W'$ sont deux ensembles bien-ordonnés, il existe \emph{au plus
+  une} bijection croissante $W \to W'$ (i.e., s'il en existe une, elle
+est unique).
+\end{cor}
+\begin{proof}
+Si $f,g\colon W\to W'$ sont deux bijections croissantes, appliquer le
+corollaire précédent à la composée de l'une et de la réciproque de
+l'autre.
+\end{proof}
+
+\begin{cor}
+Si $W$ est un ensemble bien-ordonné, $x\in W$ et $\precs(x) = \{y :
+y<x\}$, alors il n'existe pas de fonction strictement croissante $W
+\to \precs(x)$.
+\end{cor}
+\begin{proof}
+Une telle fonction serait en particulier une fonction strictement
+croissante $W \to W$, donc vérifierait $x \leq f(x)$ d'après la
+proposition, ce qui contredit $f(x) \in \precs(x)$.
+\end{proof}
+
+Le théorème suivant assure que donnés deux ensembles bien-ordonnés, il
+y a moyen de les comparer :
+\begin{thm}
+Si $W,W'$ sont deux ensembles bien-ordonnés, alors exactement l'une
+des affirmations suivantes est vraie :
+\begin{itemize}
+\item il existe une bijection croissante $f\colon W \to \precs(y)$
+  avec $y\in W'$,
+\item il existe une bijection croissante $f\colon \precs(x) \to W'$
+  avec $x\in W$,
+\item il existe une bijection croissante $f\colon W \to W'$.
+\end{itemize}
+\end{thm}
+\begin{proof}
+Les affirmations sont exclusives d'après le corollaire précédent.
+Plus précisément, s'il existe une fonction strictement croissante
+$f\colon W \to W'$, en composant à droite par $f$ on voit qu'il ne
+peut pas exister de fonction strictement croissante $W' \to
+\precs(x)$, donc le premier ou le dernier cas excluent celui du
+milieu, mais par symétrie les deux derniers excluent le premier et les
+trois cas sont bien exclusifs.
+
+Considérons maintenant l'ensemble des couples $(x,y) \in W\times W'$
+tels qu'il existe une bijection croissante (forcément unique !) entre
+$\precs_W(x)$ et $\precs_{W'}(y)$ : d'après ce qu'on vient
+d'expliquer, pour chaque $x$ il existe au plus un $y$ tel qu'il y ait
+une telle bijection croissante, et pour chaque $y$ il existe au plus
+un $x$.  On peut donc voir cet ensemble de couples comme (le graphe
+d')une fonction partielle injective $\varphi\colon W \dasharrow W'$
+(autrement dit, $\varphi(x)$ est l'unique $y$, s'il existe, tel qu'il
+existe une bijection croissante entre $\precs_W(x)$
+et $\precs_{W'}(y)$).
+
+Si $x_0 \leq x$ et si $\varphi(x) =: y$ est défini, une bijection
+croissante $f\colon \precs_W(x) \to \precs_{W'}(y)$ peut se
+restreindre à $\precs_W(x_0)$ et il est clair que son image est
+exactement $\precs_{W'}(f(x_0))$, ce qui montre que $\varphi(x_0)$ est
+définie et vaut $f(x_0) < y = \varphi(x)$, notamment $\varphi$ est
+strictement croissante.
+D'après \ref{downward-closed-subsets-of-well-ordered-sets}, l'ensemble
+de définition de $\varphi$ est soit $W$ tout entier soit de la forme
+$\precs_W(x)$ pour un $x\in W$.  Symétriquement, son image est soit
+$W'$ tout entier soit de la forme $\precs_{W'}(y)$ pour un $y\in W'$.
+Et comme on vient de le voir, $\varphi$ est une bijection croissante
+entre l'un et l'autre.  Ce ne peut pas être une bijection croissante
+entre $\precs_W(x)$ et $\precs_{W'}(y)$ sinon $(x,y)$ lui-même serait
+dans $\varphi$, une contradiction.  C'est donc que $\varphi$ est
+exactement une bijection comme un des trois cas annoncés.
+\end{proof}
+
+
+
 %
 %
 %