1 files changed, 97 insertions, 2 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index b4cc416..e19150f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -3689,7 +3689,7 @@ distinction étant souvent utile dans les inductions :
 sont des exemples de ces trois cas.  D'autres ordinaux limites sont
 $\omega\cdot 2$, ou $\omega^2$, ou encore $\omega^\omega +
 \omega^3\cdot 7$, ou bien $\omega^{\omega+1}$ ; en revanche,
-$\omega^\omega + 1$ ou $\omega^{\omega\cdot 2} + 1729$ sont
+$\omega^\omega + 1$ ou $\omega^{\omega 2} + 1729$ sont
 successeurs.  Dans la forme normale de Cantor, un ordinal est
 successeur si et seulement si le dernier terme (le plus à droite) est
 un entier naturel non nul.
@@ -4133,6 +4133,10 @@ objet).
 
 \subsection{Somme, produit et exponentielle d'ordinaux}
 
+Les résultats de cette section seront admis (ils ne sont pas très
+difficiles à montrer — presque toujours par induction transfinie —
+mais seraient trop longs à traiter en détails).
+
 \thingy Il existe deux façons équivalentes de définir la somme
 $\alpha+\beta$ de deux ordinaux.
 
@@ -4369,7 +4373,9 @@ finie la somme ci-dessus) et tous $<\tau$.
 Deux telles expressions se comparent par l'ordre lexicographique
 donnant le plus de poids aux puissances élevées de $\tau$.  On parle
 d'écriture de $\alpha$ \textbf{en base $\tau$} : on dit que les
-$\xi_{(\iota)}$ sont les \emph{chiffres} de cette écriture.
+$\xi_{(\iota)}$ sont les \emph{chiffres} de cette écriture.  On
+souligne que les chiffres sont \emph{tous nuls sauf un nombre fini}
+(ce qui permet de les comparer lexicographiquement).
 
 Les deux cas les plus importants sont $\tau=2$ et $\tau=\omega$ : le
 cas $\tau=2$ correspond à l'\textbf{écriture binaire} d'un ordinal,
@@ -4378,6 +4384,95 @@ de $2$ distinctes, et le cas $\tau=\omega$ s'appelle écriture en
 \textbf{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
+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
++ \cdots + \omega^{\gamma_1} n_1$ où $\gamma_s > \cdots > \gamma_1$
+sont eux-mêmes des ordinaux $<\varepsilon_0$ (précédemment définis),
+et les $n_i$ sont des entiers naturels non nuls, et de telles
+expressions se comparent par ordre lexicographique (i.e., comparer
+d'abord $\gamma_s$, ou, s'ils sont égaux, comparer les $n_s$, ou,
+s'ils sont égaux, comparer le terme suivant, etc.).
+
+À titre d'exemple, $\alpha := \omega^{\omega^{\omega 3}\cdot 7 +
+  \omega^{\omega+5}\cdot 42}\cdot 1729 + \omega^{\omega^{\omega
+    2}\cdot 1000 + \omega + 33}\cdot 299\,792\,458$ est un ordinal
+$<\varepsilon_0$ (écrit en forme normale de Cantor) car le premier
+exposant, $\omega^{\omega 3}\cdot 7 + \omega^{\omega+5}\cdot 42$, est
+lui-même un ordinal $<\varepsilon_0$ écrit en forme normale de Cantor
+et supérieur au second exposant, $\omega^{\omega 2}\cdot 1000 + \omega
++ 33$.  L'ordinal $\alpha$ est plus grand que $\beta :=
+\omega^{\omega^{\omega 3}\cdot 7 + \omega^{\omega+4}\cdot 333}\cdot
+2016 + \omega^{\omega^{\omega 3}\cdot 5 + \omega + 33}\cdot
+299\,792\,458$ car (une fois qu'on a vérifié, de même, que $\beta$ est
+correctement écrit) le premier exposant de $\alpha$, à savoir
+$\omega^{\omega 3}\cdot 7 + \omega^{\omega+5}\cdot 42$, est supérieur
+au premier exposant de $\beta$, à savoir $\omega^{\omega 3}\cdot 7 +
+\omega^{\omega+4}\cdot 333$ (cette comparaison se fait elle-même en
+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$).
+
+\thingy Expliquons rapidement pourquoi la forme normale de Cantor
+permet de calculer la somme ou le produit de deux ordinaux.
+
+Pour l'addition, à part le fait qu'elle est associative, on a
+simplement besoin de savoir que :
+\begin{itemize}
+\item si $\gamma < \gamma'$ alors $\omega^\gamma\cdot n +
+  \omega^{\gamma'}\cdot n' = \omega^{\gamma'} \cdot n'$ (autrement
+  dit, les plus grandes puissances de $\omega$ absorbent les plus
+  petites situées à leur gauche),
+\item et bien sûr, $\omega^\gamma\cdot n + \omega^\gamma \cdot n' =
+  \omega^\gamma \cdot (n+n')$ par associativité à droite (on peut donc
+  regrouper deux puissances égales).
+\end{itemize}
+
+À titre d'exemple, la somme de $\omega^{\omega 2}\cdot 2 +
+\omega^7\cdot 3$ et $\omega^{\omega 2}\cdot 5 + 12$ dans cet ordre
+vaut $\omega^{\omega 2}\cdot 7 + 12$, et dans l'autre sens elle vaut
+$\omega^{\omega 2}\cdot 7 + \omega^7\cdot 3$.
+
+Pour la multiplication, comme elle est distributive à droite et
+associative, il suffit de savoir calculer le produit de
+$\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ (en forme
+normale de Cantor, avec les $\gamma_i$ strictement décroissants et les
+$n_i$ strictement positifs) par $\omega^{\gamma'}$ \emph{à droite}, et
+par $n' > 0$ (entier) lui aussi \emph{à droite}.  Or on a :
+\begin{itemize}
+\item $(\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1) \times
+  \omega^{\gamma'} = \omega^{(\gamma_s + \gamma')}$ dès que
+  $\gamma'>0$, et
+\item $(\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1) \times
+  n' = \omega^{\gamma_s} n_s n' + \cdots + \omega^{\gamma_1} n_1$ dès
+  que $n'>0$ (i.e., seul le coefficient le plus à gauche est multiplié
+  par $n'$, les autres sont inchangés).
+\end{itemize}
+
+À titre d'exemple, le produit de $\omega^{\omega 2}\cdot 2 +
+\omega^7\cdot 3$ et $\omega^{\omega 2}\cdot 5 + 12$ dans cet ordre
+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,
+$\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
+de $2^c$ pour des entiers naturels $c$ distincts).  À titre d'exemple,
+\[
+\begin{array}{rllll}
+&\omega^{\omega^2\cdot 3}\cdot 5 &\strut + \omega^{\omega+1}\cdot 8
+&\strut + \omega^{17}\cdot 6 &\strut + 12\\
+=& 2^{\omega^3\cdot 3 + 2} + 2^{\omega^3\cdot 3} &\strut + 2^{\omega^2+\omega+3}
+&\strut + 2^{\omega\cdot 17+2} + 2^{\omega\cdot 17+1} &\strut + 2^3 + 2^2
+\end{array}
+\]
+