diff options
| -rw-r--r-- | notes-mitro206.tex | 99 |
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} +\] + |