From 63c3a18a60a464e27881a78a8ab91d2dae0440cd Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 4 Apr 2016 13:46:22 +0200
Subject: Various additions or clarifications after course on 2016-04-04.

---
 notes-mitro206.tex | 135 +++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 110 insertions(+), 25 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 6281638..049d82c 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -3886,13 +3886,19 @@ 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).
 \end{cor}
+Une telle bijection peut s'appeler un \textbf{isomorphisme} d'ensemble
+bien-ordonnés, et on peut dire que $W$ et $W'$ ont \defin[isomorphes
+  (ensembles bien-ordonnés)]{isomorphes} lorsqu'il existe un
+isomorphisme entre eux (on conviendra en
+cf. \ref{definition-of-ordinals} ci-dessous qu'on le note $\#W =
+\#W'$).
 \begin{proof}
 Si $f,g\colon W\to W'$ sont deux bijections croissantes, appliquer le
 corollaire précédent à la composée de l'une et de la réciproque de
 l'autre.
 \end{proof}
 
-\begin{cor}
+\begin{cor}\label{uniqueness-of-initial-segment-isomorphic-to-a-well-ordered-set}
 Si $W$ est un ensemble bien-ordonné, $x\in W$ et $\precs(x) = \{y :
 y<x\}$, alors il n'existe pas de fonction strictement croissante $W
 \to \precs(x)$.
@@ -3916,7 +3922,10 @@ des affirmations suivantes est vraie :
 \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}.)
+d'après \ref{uniqueness-of-isomorphisms-between-well-ordered-sets}.
+De plus, $y$ est unique dans le premier cas et $x$ l'est dans le
+second,
+d'après \ref{uniqueness-of-initial-segment-isomorphic-to-a-well-ordered-set}.)
 \end{thm}
 \begin{proof}
 Les affirmations sont exclusives d'après le corollaire précédent.
@@ -3968,7 +3977,7 @@ 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}
+\begin{defn}\label{definition-of-ordinals}
 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 =
@@ -3979,20 +3988,29 @@ 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'\defin{ordinal}
-de $W$.
+d'équivalence qu'on vient de définir.  La
+proposition \ref{triviality-on-comparison-of-initial-segments-in-well-ordered-sets}
+assure que si $w,w'$ sont deux éléments d'un même ensemble
+bien-ordonné, alors $\#\precs(w) < \#\precs(w')$ se produit si et
+seulement si $w < w'$, et de même en remplaçant le signe $<$ par
+$=$ ou $>$.
+
+La classe d'équivalence\footnote{Pour être parfaitement rigoureux, à
+  cause de subtilités ensemblistes, 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$ pour la relation $\#W = \#W'$ s'appelle l'\defin{ordinal}
+de $W$.  Par abus de notation, si $w$ est un élément d'un ensemble
+bien-ordonné, on peut noter $\#w$ pour $\#\precs(w)$ (autrement dit,
+on associe un ordinal non seulement à un ensemble bien-ordonné, mais
+aussi à un élément d'un ensemble bien-ordonné).
 
 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$ (\defin[von Neumann (ordinal de)]{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}
+(cf. \ref{definition-transitive-collapse}) de $W$ (\defin[von Neumann
+  (ordinal de)]{ordinal de von Neumann}), à savoir $\#W = \{\#x : x\in
+W\}$ où $\#x = \{\#y : y<x\}$, cette définition ayant bien un sens par
+induction transfinie (\ref{transfinite-definition}
 et \ref{scholion-transfinite-definition}).
 \end{defn}
 
@@ -4013,7 +4031,7 @@ 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.  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
+important de garder à l'esprit que l'ensemble des ordinaux strictement
 plus petits est $\{\#\precs(x) : x \in W\}$ (par définition de
 l'ordre !), et que $\alpha = \#\{\beta < \alpha\}$ (idem).  Même si
 nous éviterons de supposer explicitement que les ordinaux sont
@@ -4125,14 +4143,16 @@ de $\delta$).  Ceci permet de dire que $\sup\{\beta < \alpha\} =
 limite ainsi :
 
 \thingy Si $\delta$ est un ordinal limite et $f$ est une fonction
-\emph{croissante} de $\delta$ (i.e., des ordinaux strictement plus
-petits que $\delta$) vers les ordinaux, on appelle \defin{limite} de
-$f$ en $\delta$ la valeur $\sup\{f(\xi) : \xi<\delta\}$.  On pourra la
+\emph{croissante} définie sur les ordinaux strictement plus petits
+que $\delta$ et à valeurs ordinales, on appelle \defin{limite} de $f$
+en $\delta$ la valeur $\sup\{f(\xi) : \xi<\delta\}$.  On pourra la
 noter $\lim_{\xi\to\delta} f(\xi)$ ou simplement $\lim_\delta f$.  (Il
 s'agit bien d'une limite pour une certaine topologie : la topologie de
 l'ordre ; plus exactement, c'est une limite car pour tous $\beta_1 <
 \lim_\delta f < \beta_2$, il existe $\xi_0$ tel que $\beta_1 < f(\xi)
-< \beta_2$ si $\xi_0 \leq \xi < \delta$.)
+< \beta_2$ si $\xi_0 \leq \xi < \delta$.)  Si $f$ est aussi définie en
+$\delta$ et que $f(\delta) = \lim_\delta f$, on dit que $f$ est
+\defin[continue (fonction ordinale)]{continue} en $\delta$.
 
 Ainsi, si $\delta$ est un ordinal limite, on peut écrire $\delta =
 \lim_{\xi\to\delta} \xi$ (et réciproquement, si $f$ est
@@ -4204,6 +4224,9 @@ suivantes :
   $\alpha+\beta < \alpha+\beta'$ ; le fait que $0<1$ mais $0+\omega =
   1+\omega$ explique qu'il n'y a pas croissante stricte en la première
   variable) ;
+\item l'addition est continue en la seconde variable (c'est exactement
+  ce que dit le cas limite dans la définition par induction
+  transfinie) ;
 \item lorsque $\alpha \leq \alpha'$, il existe un unique $\beta$ tel
   que $\alpha' = \alpha + \beta$ (certains auteurs le notent $-\alpha
   + \alpha'$ : on prendra garde au fait qu'il s'agit d'une
@@ -4293,6 +4316,9 @@ suivantes :
   nulle (si $\alpha\leq\alpha'$ alors $\alpha\cdot\beta \leq
   \alpha'\cdot\beta$, et si $\beta<\beta'$ et $\alpha>0$ alors
   $\alpha\cdot\beta < \alpha\cdot\beta'$) ;
+\item la multiplication est continue en la seconde variable (c'est
+  exactement ce que dit le cas limite dans la définition par induction
+  transfinie) ;
 \item \defin{division euclidienne} : pour tout $\alpha$ (ici appelé
   dividende) et tout $\beta>0$ (ici appelé diviseur) il existe
   $\gamma$ (ici appelé quotient) et $\rho<\beta$ (ici appelé reste)
@@ -4369,7 +4395,13 @@ suivantes :
 \item pour tout $\beta$, on a $1^\beta = 1$ ;
 \item pour tout $\beta>0$, on a $0^\beta = 0$ (en revanche, $0^0=1$) ;
 \item on a $\alpha^{\beta+\gamma} = \alpha^\beta \cdot \alpha^\gamma$ ;
-\item on a $\alpha^{\beta\gamma} = (\alpha^\beta)^\gamma$.
+\item on a $\alpha^{\beta\gamma} = (\alpha^\beta)^\gamma$ ;
+\item l'exponentiation est croissante en chaque variable (si on écarte
+  $0^0 = 1$), et même strictement croissante en l'exposant ($\beta$)
+  lorsque la base $\alpha$ est $>1$ ;
+\item l'exponentiation est continue en l'exposant variable (c'est
+  exactement ce que dit le cas limite dans la définition par induction
+  transfinie).
 \end{itemize}
 
 \thingy\label{base-tau-writing-of-ordinals} Soient $\alpha,\tau$ des
@@ -4402,10 +4434,28 @@ de $2$ distinctes, et le cas $\tau=\omega$ s'appelle écriture en
 \defin[Cantor (forme normale de)]{forme normale de Cantor}, c'est-à-dire comme somme
 décroissante finie de puissances de $\omega$.
 
-\thingy La forme normale de Cantor permet de comprendre, et de
-manipuler informatiquement, les ordinaux strictement inférieurs à
-l'ordinal appelé $\varepsilon_0$.  On peut donner la définition
-suivante : un ordinal $<\varepsilon_0$ est \emph{soit} un entier
+La forme normale de Cantor est la manière usuelle d'écrire les
+ordinaux (par exemple, $\omega$, $\omega+7$, $\omega\cdot 5$,
+$\omega^2$, $\omega^\omega$ ou encore $\omega^{\omega\cdot 2}$ sont
+des formes normales de Cantor, fussent-elles un peu dégénérées ; un
+exemple moins dégénéré serait $\omega^{\omega 3}\cdot 7 +
+\omega^{\omega+5}\cdot 42 + \omega^3 + 666$) ; on va expliquer au
+paragraphe suivant que la forme normale de Cantor itérée (c'est-à-dire
+appliquée aux exposants $\gamma_i$ eux-mêmes, et à leurs exposants, et
+ainsi de suite) permet de « comprendre » et de manipuler
+informatiquement un ordinal $\varepsilon_0$ passablement grand.
+L'écriture binaire est moins souvent utilisée pour les ordinaux, et
+son rapport avec la forme normale de Cantor sera expliqué
+en \ref{binary-versus-cantor-normal-form}.
+
+\thingy La forme normale de Cantor (ou plus exactement, la forme
+normale de Cantor \emph{itérée}, c'est-à-dire appliquée récursivement
+aux exposants de la forme normale de Cantor) permet de comprendre, et
+de manipuler informatiquement, les ordinaux strictement inférieurs à
+un certain ordinal \index{epsilon 0 (ordinal)}appelé $\varepsilon_0$.
+
+Plus exactement, on peut donner la définition suivante :
+un ordinal $<\varepsilon_0$ est \emph{soit} un entier
 naturel $n$ (qui pourra aussi s'écrire $\omega^0\cdot n$ si on le
 souhaite), qu'on compare comme on compare usuellement les entiers
 naturels, \emph{soit} une écriture de la forme $\omega^{\gamma_s} n_s
@@ -4435,6 +4485,40 @@ comparant le premier exposant, dans les deux cas $\omega\cdot 3$, puis
 son coefficient, dans les deux cas $7$, puis l'exposant suivant, et
 c'est là qu'on constate que $\omega+5$ dépasse $\omega+4$).
 
+Formellement, on peut définir $\varepsilon_0$ comme l'ordinal (le $\#$
+au sens de \ref{definition-of-ordinals}) de l'ensemble bien-ordonné
+des écritures qu'on vient de présenter pour l'ordre qu'on vient de
+dire.  Cet ordinal est la limite de
+$\omega,\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$
+c'est-à-dire le plus petit ordinal tel que $\varepsilon =
+\omega^\varepsilon$.
+
+\thingy (\textbf{Digression.}  Plus généralement, on appelle
+$\varepsilon_\alpha$ le $\alpha$-ième ordinal tel que $\varepsilon =
+\omega^\varepsilon$ : si on préfère, $\varepsilon_{\beta+1}$ est la
+limite de $\varepsilon_\beta, \varepsilon_\beta^{\varepsilon_\beta},
+\varepsilon_\beta^{\varepsilon_\beta^{\varepsilon_\beta}}, \ldots$, et
+lorsque $\delta$ est limite, $\varepsilon_\delta$ est la limite des
+$\varepsilon_\xi$ pour $\xi\to\delta$ ; on pourrait utiliser ce genre
+de notations jusqu'à
+$\varepsilon_{\varepsilon_{\varepsilon_{\varepsilon_{...}}}}$ qui est le
+plus petit ordinal tel que $\zeta = \varepsilon_\zeta$.  Mais il ne
+faut pas s'imaginer qu'on puisse espérer épuiser les ordinaux par ce
+genre d'opérations : tous les ordinaux que nous venons de mentionner
+sont \emph{dénombrables}, c'est-à-dire qu'ils sont les ordinaux de
+certains bons ordres sur $\mathbb{N}$ (ou un ensemble fini), et toutes
+les opérations $(\alpha,\beta) \mapsto \alpha+\beta$, $(\alpha,\beta)
+\mapsto \alpha\beta$, $(\alpha,\beta) \mapsto \alpha^\beta$ et même
+$\alpha \mapsto \varepsilon_\alpha$ envoient les ordinaux dénombrables
+sur les ordinaux dénombrables.  Or il existe des ordinaux
+indénombrables, le plus petit étant appelé $\omega_1$, qui est donc la
+borne supérieure des ordinaux dénombrables, ou, dans la construction
+de von Neumann, l'ensemble des ordinaux dénombrables : cet ordinal a
+la propriété que \emph{toute suite strictement croissante (indicée par
+  les entiers naturels) à valeurs dans [les ordinaux plus petits
+    que] $\omega_1$ est bornée}, c'est-à-dire qu'on ne peut jamais le
+fabriquer comme limite d'une suite.)
+
 \thingy Expliquons rapidement pourquoi la forme normale de Cantor
 permet de calculer la somme ou le produit de deux ordinaux.
 
@@ -4477,7 +4561,8 @@ vaut $\omega^{\omega 4}\cdot 5 + \omega^{\omega 2}\cdot 24 +
 \omega^7\cdot 3$, et dans l'autre sens il vaut $\omega^{\omega 4}\cdot
 2 + \omega^{\omega 2 + 7}\cdot 3$.
 
-\thingy Puisque $\omega = 2^\omega$ (et par conséquent,
+\thingy\label{binary-versus-cantor-normal-form}
+Puisque $\omega = 2^\omega$ (et par conséquent,
 $\omega^\gamma\, 2^c = 2^{\omega\gamma + c}$), l'écriture binaire d'un
 ordinal s'obtient en remplaçant chaque chiffre $n$ (un entier naturel)
 dans sa forme normale de Cantor par l'écriture binaire de $n$ (somme
-- 
cgit v1.2.3