diff options
| -rw-r--r-- | notes-mitro206.tex | 135 |
1 files changed, 110 insertions, 25 deletions
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 |