From da4f117ea32e404567d908a63e3b066bf6b6dd84 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 14 Mar 2016 15:22:46 +0100 Subject: Definition of ordinals. --- notes-mitro206.tex | 98 +++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file 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\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} + % -- cgit v1.2.3