Definition of ordinals.

1 files changed, 90 insertions, 8 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 409e706..9073ef4 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -2594,13 +2594,13 @@ 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.
+partir de $x$), cela signifie qu'il n'y a pas de suite infinie
+strictement décroissante.
 
 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é}.
+i.e., telle qu'il n'existe pas de suite infinie strictement
+décroissante, est appelée un \textbf{bon ordre}, ou définir un
+ensemble \textbf{bien-ordonné}.
 
 \begin{defn}\label{definition-downstream-closed-inductive}
 Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
@@ -3663,7 +3663,7 @@ Un ensemble totalement ordonné bien-fondé $W$ est dit
 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.
+  n'existe pas de suite infinie 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
@@ -3760,7 +3760,7 @@ 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}
+\begin{cor}\label{uniqueness-of-isomorphisms-between-well-ordered-sets}
 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).
@@ -3784,7 +3784,7 @@ proposition, ce qui contredit $f(x) \in \precs(x)$.
 
 Le théorème suivant assure que donnés deux ensembles bien-ordonnés, il
 y a moyen de les comparer :
-\begin{thm}
+\begin{thm}\label{comparison-of-well-ordered-sets}
 Si $W,W'$ sont deux ensembles bien-ordonnés, alors exactement l'une
 des affirmations suivantes est vraie :
 \begin{itemize}
@@ -3794,6 +3794,8 @@ des affirmations suivantes est vraie :
   avec $x\in W$,
 \item il existe une bijection croissante $f\colon W \to W'$.
 \end{itemize}
+(Dans chaque cas, la bijection est automatiquement unique
+d'après \ref{uniqueness-of-isomorphisms-between-well-ordered-sets}.)
 \end{thm}
 \begin{proof}
 Les affirmations sont exclusives d'après le corollaire précédent.
@@ -3832,6 +3834,86 @@ dans $\varphi$, une contradiction.  C'est donc que $\varphi$ est
 exactement une bijection comme un des trois cas annoncés.
 \end{proof}
 
+L'affirmation suivante est une trivialité, mais peut-être utile à
+écrire explicitement :
+\begin{prop}\label{triviality-on-comparison-of-initial-segments-in-well-ordered-sets}
+Soit $X$ un ensemble bien-ordonné : si $w,w' \in X$ et qu'on pose $W =
+\precs_X(w)$ et $W' = \precs_X(w')$, les trois cas du
+théorème \ref{comparison-of-well-ordered-sets} se produisent
+exactement lorsque $w < w'$, resp. $w > w'$, resp. $w = w'$.
+\end{prop}
+\begin{proof}
+C'est évident : si $w < w'$ alors l'identité fournit une bijection
+croissante $W \to \precs_{W'}(w)$, et de même dans les autres cas.
+\end{proof}
+
+\begin{defn}
+Soient $W,W'$ deux ensembles bien-ordonnés.  On notera $\#W < \#W'$,
+resp. $\#W > \#W'$, resp. $\#W = \#W'$, dans les trois cas du
+théorème \ref{comparison-of-well-ordered-sets}.  Autrement dit, $\#W =
+\#W'$ signifie qu'il existe une bijection croissante $W \to W'$
+(unique
+d'après \ref{uniqueness-of-isomorphisms-between-well-ordered-sets}),
+ce qui définit une relation d'équivalence entre ensembles
+bien-ordonnés, et on note $\#W < \#W'$ lorsque $\#W = \#\precs(y)$
+pour un $y \in W'$, le théorème \ref{comparison-of-well-ordered-sets}
+assurant qu'il s'agit d'une relation d'ordre total entre les classes
+d'équivalence qu'on vient de définir.
+
+La classe d'équivalence\footnote{Pour être parfaitement rigoureux, on
+  ne peut pas vraiment définir des classes d'équivalence de façon
+  usuelle dans ce contexte, d'où l'intérêt de la définition suivante
+  (ordinaux de von Neumann).} $\#W$ s'appelle l'\textbf{ordinal}
+de $W$.
+
+Si on préfère éviter la définition par classe d'équivalence, on peut
+aussi définir $\#W$ comme l'écrasement transitif
+(cf. \ref{definition-transitive-collapse}) de $W$ (\textbf{ordinal de
+  von Neumann}), à savoir $\#W = \{\#\precs(x) : x\in W\}$ où
+$\#\precs(x) = \{\#\precs(y) : y<x\}$, cette définition ayant bien un
+sens par induction transfinie (\ref{transfinite-definition}
+et \ref{scholion-transfinite-definition}).
+\end{defn}
+
+\thingy Ces deux façons de définir les ordinaux reviennent
+essentiellement au même : en effet, s'il y a une bijection croissante
+$W \to W'$ (forcément unique), alors les écrasements transitifs de $W$
+et $W'$ coïncident, et réciproquement, si les écrasements transitifs
+de $W$ et $W'$ coïncident, on définit une bijection croissante $W \to
+W'$ en envoyant $x \in W$ sur l'unique $y \in W'$ tel que
+$\precs_W(x)$ et $\precs_{W'}(y)$ aient le même écrasement transitif
+(on peut au préalable montrer le lemme suivant : si $W$ est
+bien-ordonné et $y < x$ dans $W$ alors l'écrasement transitif de
+$\precs(y)$, qui est un élément de celui de $\precs(x)$, ne lui est
+pas égal — ceci résulte d'une induction transfinie sur $x$).
+
+Les ordinaux de von Neumann ont l'avantage d'être des ensembles
+bien-définis et de vérifier $\beta < \alpha$ si et seulement si $\beta
+\in \alpha$ ; ils ont comme inconvénient d'être peut-être plus
+difficiles à visualiser.
+
+Le théorème \ref{comparison-of-well-ordered-sets} a la conséquence
+importante suivante sur les ordinaux :
+
+\begin{thm}
+Tout ensemble d'ordinaux est bien-ordonné : deux ordinaux sont
+toujours comparables (on a toujours $\beta<\alpha$ ou $\beta>\alpha$
+ou $\beta=\alpha$), et il n'existe pas de suite infinie strictement
+décroissante d'ordinaux.
+\end{thm}
+\begin{proof}
+Le théorème \ref{comparison-of-well-ordered-sets} signifie exactement
+que les ordinaux sont \emph{totalement} ordonnés.  Reste à expliquer
+qu'ils sont bien-ordonnés, c'est-à-dire, qu'il n'existe pas de suite
+infinie strictement décroissante $\alpha_0 > \alpha_1 > \alpha_2 >
+\cdots$.  Mais si on avait une telle suite, en appelant $W$ un
+ensemble bien-ordonné tel que $\#W = \alpha_0$, chaque $\alpha_i$
+suivant s'écrit $\#\precs(w_i)$ pour un $w_i \in W$, et
+d'après \ref{triviality-on-comparison-of-initial-segments-in-well-ordered-sets}
+on devrait avoir une suite strictement décroissante $w_1 > w_2 >
+\cdots$ dans $W$, ce qui contredit le fait que $W$ est bien-ordonné.
+\end{proof}
+
 
 
 %