Product and exponentiation of ordinals.upload-20160314

1 files changed, 194 insertions, 2 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 9c296df..cfbd2c9 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -4114,7 +4114,9 @@ inductives de la seconde).
 suivantes :
 \begin{itemize}
 \item l'addition est associative, c'est-à-dire que
-  $(\alpha+\beta)+\gamma = \alpha+(\beta+\gamma)$ ;
+  $(\alpha+\beta)+\gamma = \alpha+(\beta+\gamma)$ (on notera donc
+  simplement $\alpha+\beta+\gamma$ et de même quand il y a plus de
+  termes) ;
 \item l'ordinal nul est neutre à gauche comme à droite, c'est-à-dire
   que $0+\alpha = \alpha = \alpha+0$ ;
 \item le successeur de $\alpha$ est $\alpha + 1$ ;
@@ -4130,9 +4132,199 @@ suivantes :
 \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
-  soustraction \emph{à gauche}).
+  soustraction \emph{à gauche}) ;
+\item comme conséquence de l'une des deux propriétés précédentes : si
+  $\alpha + \beta = \alpha + \beta'$ alors $\beta = \beta'$
+  (simplification \emph{à gauche} des sommes ordinales).
 \end{itemize}
 
+\thingy On pourrait aussi définir des sommes de séries d'ordinaux, ces
+séries étant elles-mêmes indicées par d'autres ordinaux (le cas des
+séries ordinaires étant le cas où l'ensemble d'indices est $\omega$).
+Précisément, si $\alpha_\iota$ est un ordinal pour tout $\iota <
+\gamma$ (avec $\gamma$ un autre ordinal), on peut définir
+$\sum_{\iota<\gamma} \alpha_\iota$ par induction transfinie
+sur $\gamma$ :
+\begin{itemize}
+\item $\sum_{\iota<0} \alpha_\iota = 0$ (somme vide !),
+\item $\sum_{\iota<\gamma+1} \alpha_\iota = \big(\sum_{\iota<\gamma}
+  \alpha_\iota\big) + \alpha_\gamma$ (cas successeur),
+\item $\sum_{\iota<\delta} \alpha_\iota = \lim_{\xi\to\delta}
+  \sum_{\iota<\xi} \alpha_\iota$ (cas limite).
+\end{itemize}
+Ainsi, dans le cas d'une série indicée par les entiers naturels,
+$\sum_{n<\omega} \alpha_n$ est la limite $n\to\omega$ de la suite
+croissante d'ordinaux $\alpha_0 + \cdots + \alpha_{n-1}$ (limite qui
+existe toujours en tant qu'ordinal).
+
+Cette notion de somme peut servir à définir le produit, $\alpha\beta =
+\sum_{\iota<\beta} \alpha$, mais on va le redéfinir de façon plus
+simple :
+
+\thingy Il existe deux façons équivalentes de définir le produit
+$\alpha\cdot\beta$ (ou $\alpha\beta$) de deux ordinaux.
+
+La première façon consiste à prendre un ensemble bien-ordonné $W$ tel
+que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta =
+\#W'$, et définir $\alpha \cdot \beta := \#(W\times W')$ où $W \times
+W'$ est l'ensemble bien-ordonné qui est le produit cardésien de $W$ et
+$W'$ avec l'ordre lexicographique donnant plus de poids à $W'$,
+c'est-à-dire $(w_1,w_1') < (w_2,w_2')$ ssi $w_1' < w_2'$ ou bien $w_1'
+= w_2'$ et $w_1 < w_2$ (il est facile de voir qu'il s'agit bien d'un
+bon ordre).
+
+Autrement dit, intuitivement, une rangée de $\alpha\beta$ allumettes
+s'obtient en prenant une rangée de $\beta$ allumettes et en y
+\emph{remplaçant} chaque allumette par une rangée de $\alpha$
+allumettes.
+
+La seconde façon consiste à définir $\alpha\beta$ par induction
+transfinie sur $\beta$ (le \emph{second} facteur) :
+\begin{itemize}
+\item $\alpha \cdot 0 = 0$,
+\item $\alpha \cdot (\beta+1) = (\alpha\cdot\beta) + \alpha$ (cas successeur),
+\item $\alpha \cdot \delta = \lim_{\xi\to\delta} (\alpha\cdot\xi)$
+  si $\delta$ est limite.
+\end{itemize}
+
+Nous ne ferons pas la vérification du fait que ces définitions sont
+bien équivalentes, qui n'est cependant pas difficile (il s'agit de
+vérifier que la première définition vérifie bien les clauses
+inductives de la seconde).
+
+\thingy Quelques propriétés de la multiplication des ordinaux sont les
+suivantes :
+\begin{itemize}
+\item la multiplication est associative, c'est-à-dire que
+  $(\alpha\beta)\gamma = \alpha(\beta\gamma)$ (on notera donc
+  simplement $\alpha\beta\gamma$ et de même quand il y a plus de
+  facteurs) ;
+\item l'ordinal nul est absorbant à gauche comme à droite, c'est-à-dire
+  que $0\cdot\alpha = 0 = \alpha\cdot0$ ;
+\item l'ordinal $1$ est neutre à gauche comme à droite, c'est-à-dire
+  que $1\cdot\alpha = \alpha = \alpha\cdot1$ ;
+\item la multiplication est distributive \emph{à droite} sur
+  l'addition, c'est-à-dire que $\alpha(\beta+\gamma) = \alpha\beta +
+  \alpha\gamma$ (en particulier, $\alpha\cdot 2 = \alpha+\alpha$) ;
+\item la multiplication n'est pas commutative en général : par exemple,
+  $2\cdot\omega = \omega$ (en doublant chaque allumette)
+  alors que $\omega \cdot 2 > \omega$ ;
+\item la distributivité à gauche ne vaut pas en général : par exemple,
+  $(1+1)\cdot\omega = 2\cdot\omega = \omega$ n'est pas égal à
+  $\omega+\omega = \omega\cdot 2$ ;
+\item la multiplication est croissante en chaque variable, et même
+  strictement croissante en la seconde lorsque la première est non
+  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 \textbf{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)
+  uniques tels que $\alpha = \beta\gamma + \rho$ (on prendra garde au
+  fait qu'il s'agit d'une division \emph{à gauche}) ;
+\item comme conséquence de l'une des deux propriétés précédentes : si
+  $\beta\gamma = \beta\gamma'$ avec $\beta>0$, alors $\gamma =
+  \gamma'$ (simplification \emph{à gauche} des produits ordinaux).
+\end{itemize}
+
+À titre d'exemple concernant la division euclidienne, tout ordinal
+$\alpha$ peut s'écrire de façon unique comme $\alpha = \omega\gamma +
+r$ avec $r$ un entier naturel : on a alors $r>0$ si et seulement si
+$r$ est successeur (les ordinaux limites sont donc exactement les
+$\omega\gamma$ avec $\gamma>0$).
+
+\thingy On pourrait aussi définir des produits d'ordinaux, ces
+produits étant eux-mêmes indicés par d'autres ordinaux (le cas des
+produits infinis ordinaires étant le cas où l'ensemble d'indices
+est $\omega$).  Précisément, si $\alpha_\iota$ est un ordinal non nul
+pour tout $\iota < \gamma$ (avec $\gamma$ un autre ordinal), on peut
+définir $\prod_{\iota<\gamma} \alpha_\iota$ par induction transfinie
+sur $\gamma$ :
+\begin{itemize}
+\item $\prod_{\iota<0} \alpha_\iota = 1$ (produit vide !),
+\item $\prod_{\iota<\gamma+1} \alpha_\iota = \big(\prod_{\iota<\gamma}
+  \alpha_\iota\big) \cdot \alpha_\gamma$ (cas successeur),
+\item $\prod_{\iota<\delta} \alpha_\iota = \lim_{\xi\to\delta}
+  \prod_{\iota<\xi} \alpha_\iota$ (cas limite),
+\end{itemize}
+et on peut étendre au cas où certains ordinaux sont nuls en décrétant
+que, dans ce cas, le produit est nul (évidemment).
+
+Ainsi, dans le cas d'un produit d'ordinaux non nuls indicé par les
+entiers naturels, $\prod_{n<\omega} \alpha_n$ est la limite
+$n\to\omega$ de la suite croissante d'ordinaux $\alpha_0 \cdots
+\alpha_{n-1}$ (limite qui existe toujours en tant qu'ordinal).
+
+Cette notion de produit peut servir à définir le produit,
+$\alpha^\beta = \prod_{\iota<\beta} \alpha$, mais on va le redéfinir
+de façon plus simple :
+
+\thingy Il existe deux façons équivalentes de définir l'exponentielle
+$\alpha^\beta$ de deux ordinaux.
+
+La première façon consiste à prendre un ensemble bien-ordonné $W$ tel
+que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta =
+\#W'$, et définir $\alpha ^ \beta := \#(W^{(W')})$ où $W^{(W')}$ est
+l'ensemble des fonctions $W' \to W$ \emph{prenant presque partout la
+  valeur $0$}, c'est-à-dire partout sauf en un nombre fini de points
+la plus petite valeur de $W$, cet ensemble étant muni de l'ordre
+lexicographique donnant plus de poids aux grandes composantes de la
+fonction, c'est-à-dire que $f < g$ lorsque le plus grand $w' \in W'$
+tel que $f(w') \neq g(w')$ vérifie en fait $f(w') < g(w')$ (on peut
+vérifier qu'il s'agit bien d'un bon ordre).
+
+La seconde façon consiste à définir $\alpha^\beta$ par induction
+transfinie sur $\beta$ (l'exposant) :
+\begin{itemize}
+\item $\alpha ^ 0 = 1$,
+\item $\alpha ^ {\beta+1} = (\alpha^\beta) \cdot \alpha$ (cas successeur),
+\item $\alpha ^ \delta = \lim_{\xi\to\delta} \alpha^\xi$
+  si $\delta$ est limite.
+\end{itemize}
+
+Nous ne ferons pas la vérification du fait que ces définitions sont
+bien équivalentes, qui n'est cependant pas difficile (il s'agit de
+vérifier que la première définition vérifie bien les clauses
+inductives de la seconde).
+
+\thingy Quelques propriétés de l'exponentiation des ordinaux sont les
+suivantes :
+\begin{itemize}
+\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$.
+\end{itemize}
+
+\thingy\label{base-tau-writing-of-ordinals} Soient $\alpha,\tau$ des
+ordinaux avec $\tau>1$ (dans la pratique, on ne s'intéressera guère
+qu'à $\tau = 2$ et $\tau = \omega$) : alors il existe une unique
+écriture
+\[
+\alpha = \tau^{\gamma_s} \xi_s + \cdots + \tau^{\gamma_1} \xi_1
+\]
+où $\gamma_s > \cdots > \gamma_1$ et $\xi_s,\ldots,\xi_1$ tous non
+nuls et strictement inférieurs à $\tau$, ou, ce qui revient au même
+(mais en changeant $\xi_i$ en $\xi_{(\gamma_i)}$),
+\[
+\alpha = \cdots + \tau^\iota \xi_{(\iota)} + \cdots + \tau \xi_{(1)} + \xi_{(0)}
+\]
+où les $\xi_{(\iota)}$ sont tous nuls sauf un nombre fini (ce qui rend
+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.
+
+Les deux cas les plus importants sont $\tau=2$ et $\tau=\omega$ : le
+cas $\tau=2$ correspond à l'\textbf{écriture binaire} d'un ordinal,
+c'est-à-dire son écriture comme somme décroissante finie de puissances
+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$.
+
+
 
 
 %