summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-03-14 14:51:06 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-03-14 14:51:06 (GMT)
commit2b4bbf23ac224c1043ca0a68975f2ca6dd36b85c (patch)
treefb561fdbd44cd8241b0242e154c4c065e001692b /notes-mitro206.tex
parentda4f117ea32e404567d908a63e3b066bf6b6dd84 (diff)
downloadmitro206-2b4bbf23ac224c1043ca0a68975f2ca6dd36b85c.zip
mitro206-2b4bbf23ac224c1043ca0a68975f2ca6dd36b85c.tar.gz
mitro206-2b4bbf23ac224c1043ca0a68975f2ca6dd36b85c.tar.bz2
Split section on well-founded sets. Upper bounds of ordinals.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex40
1 files changed, 37 insertions, 3 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 9073ef4..f187c7f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -3641,7 +3641,8 @@ un entier naturel non nul.
\subsection{Ensembles bien-ordonnés et induction transfinie}
-\thingy Un ensemble \textbf{[partiellement] ordonné} est un ensemble
+\thingy\label{definition-well-ordered-set}
+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
@@ -3725,6 +3726,10 @@ autrement dit, on peut librement utiliser la valeur de $f(y)$
pour $y<x$, dans la définition de $f(x)$.
\end{scho}
+
+
+\subsection{Comparaison d'ensembles bien-ordonnés, et ordinaux}
+
\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$
@@ -3890,16 +3895,22 @@ 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.
+difficiles à visualiser. Mais même si on n'identifie pas $\alpha =
+\#W$ à l'ensemble des ordinaux strictement plus petits, il est
+important de garder à l'esprit que l'ensemble des ordinaux strictment
+plus petits est $\{\#\precs(x) : x \in W\}$ (par définition de
+l'ordre !), et que $\alpha = \#\{\beta < \alpha\}$ (idem).
Le théorème \ref{comparison-of-well-ordered-sets} a la conséquence
importante suivante sur les ordinaux :
-\begin{thm}
+\begin{thm}\label{sets-of-ordinals-are-well-ordered}
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.
+
+Autrement dit : dans tout ensemble d'ordinaux il y en a un plus petit.
\end{thm}
\begin{proof}
Le théorème \ref{comparison-of-well-ordered-sets} signifie exactement
@@ -3912,6 +3923,29 @@ 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é.
+
+La dernière affirmation vient de l'équivalence entre (*) et (\dag)
+dans \ref{definition-well-ordered-set}.
+\end{proof}
+
+\begin{prop}
+Tout ensemble $S$ d'ordinaux a une borne supérieure : autrement dit,
+il existe un ordinal $\sup S$ qui est le plus petit majorant (large)
+de $S$.
+\end{prop}
+\begin{proof}
+D'après ce qu'on vient de voir (dernière affirmation
+de \ref{sets-of-ordinals-are-well-ordered}), il suffit de montrer
+qu'il existe un majorant de $S$. Quitte à remplacer $S$ par sa
+réunion avec l'ensemble des ordinaux inférieurs à un ordinal
+quelconque de $S$ (pour les ordinaux de von Neumann, ceci revient à
+remplacer $S$ par $S \cup \bigcup_{\alpha\in S} \alpha$), on peut
+supposer que (*) si $\alpha \in S$ et $\beta < \alpha$ alors $\beta
+\in S$. On vient de voir que $S$ est bien-ordonné : si $\alpha =
+\#S$, montrons qu'il s'agit d'un majorant de $S$ ; or si $\beta \in
+S$, on a $\beta = \#\precs_S(\beta)$ d'après l'hypothèse (*) qu'on
+vient d'assurer, et la définiton de l'ordre sur les ordinaux donne
+$\beta<\alpha$.
\end{proof}