diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 98 |
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} + % |