diff options
author | David A. Madore <david+git@madore.org> | 2016-03-14 21:01:27 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2016-03-14 21:01:27 +0100 |
commit | 0c85d6fb339ff5c581a4b6c6662de1a48d66f818 (patch) | |
tree | c6c161103cee5ae720f8b61fec23a1fa0db66dac /notes-mitro206.tex | |
parent | 3ef1454c9ecbf07538981579500378fde7ec3c8b (diff) | |
download | mitro206-0c85d6fb339ff5c581a4b6c6662de1a48d66f818.tar.gz mitro206-0c85d6fb339ff5c581a4b6c6662de1a48d66f818.tar.bz2 mitro206-0c85d6fb339ff5c581a4b6c6662de1a48d66f818.zip |
Product and exponentiation of ordinals.upload-20160314
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r-- | notes-mitro206.tex | 196 |
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$. + + % |