summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-03-14 14:22:46 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-03-14 14:22:46 (GMT)
commitda4f117ea32e404567d908a63e3b066bf6b6dd84 (patch)
tree86ecb087349044daf79c532b24187411078ec9a3 /notes-mitro206.tex
parentdb165c9af5c43cab140119b133f5a95ef6f1c1ea (diff)
downloadmitro206-da4f117ea32e404567d908a63e3b066bf6b6dd84.zip
mitro206-da4f117ea32e404567d908a63e3b066bf6b6dd84.tar.gz
mitro206-da4f117ea32e404567d908a63e3b066bf6b6dd84.tar.bz2
Definition of ordinals.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex98
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}
+
%