diff options
| -rw-r--r-- | exercices-ordinaux.tex | 78 | ||||
| -rw-r--r-- | notes-mitro206.tex | 34 |
2 files changed, 110 insertions, 2 deletions
diff --git a/exercices-ordinaux.tex b/exercices-ordinaux.tex index 3f5849e..6be2488 100644 --- a/exercices-ordinaux.tex +++ b/exercices-ordinaux.tex @@ -203,6 +203,84 @@ Dans l'ordre croissant : \spaceout $0$ ; \end{corrige} + +% +% +% + +\exercice + +(a) Que vaut $(\omega+1) + (\omega+1)$ ? + +(b) Plus généralement, que vaut $(\omega+1) + \cdots + (\omega+1)$ +avec $n$ termes $\omega+1$ (où $n$ est un entier naturel $\geq 1$) ? + +(c) En déduire ce que vaut $(\omega+1)\cdot n$. + +(d) En déduire ce que vaut $(\omega+1)\cdot \omega$. + +(e) En déduire ce que vaut $(\omega+1)\cdot(\omega+1)$. + +(f) En déduire ce que vaut $(\omega+1)^2$. + +\begin{corrige} +(a) On a $(\omega+1) + (\omega+1) = \omega + 1 + \omega + 1 = \omega + + (1 + \omega) + 1 = \omega + \omega + 1 = \omega\cdot 2 + 1$. + +(b) En procédant de même, on voit que dans la somme de $n$ termes + $\omega + 1$, chaque $1$ est absorbé par le $\omega$ qui + \emph{suit}, sauf le dernier $1$ qui demeure : la somme vaut + donc $\omega\cdot n + 1$. + +(c) Quel que soit l'ordinal $\alpha$, la somme $\alpha + \cdots + + \alpha$ avec $n$ termes $\alpha$ vaut $\alpha\cdot n$ (ceci se voit + soit par une récurrence immédiate sur $n$ avec la définition par + induction de la multiplication, soit en utilisant la distributivité + à droite, c'est-à-dire $\alpha\cdot n = \alpha\cdot(1 + \cdots + 1) + = \alpha + \cdots + \alpha$). On a donc $(\omega+1)\cdot n = + \omega\cdot n + 1$. + +(d) L'ordinal $(\omega+1)\cdot \omega$ est la limite des $\omega\cdot + n + 1$ pour $n\to\omega$. Cette limite vaut $\omega^2$ : en effet, + $\omega^2 \geq \omega\cdot n + 1$ pour chaque $n<\omega$, mais + inversement, si $\gamma < \omega^2$, on a $\gamma < \omega\cdot n$ + pour un certain $n$ (par exemple en utilisant le fait que $\omega^2 + = \omega\cdot\omega$ est elle-même la limite des $\omega\cdot n$, + c'est-à-dire le plus petit ordinal supérieur ou égal à eux), et en + particulier $\gamma < \omega\cdot n + 1$. + +(e) On a $(\omega+1)\cdot (\omega+1) = (\omega+1)\cdot \omega + \omega + + 1 = \omega^2 + \omega + 1$. + +(f) On a toujours $\alpha^2 = \alpha\cdot\alpha$, donc $(\omega+1)^2 = + \omega^2 + \omega + 1$ comme on vient de le montrer. +\end{corrige} + + + +% +% +% + +\exercice + +On dit qu'un ordinal $\alpha$ est \textbf{infini} lorsque +$\alpha\geq\omega$. Montrer qu'un ordinal est infini si et seulement +si $1+\alpha = \alpha$. + +\begin{corrige} +Si $\alpha$ est infini, on a $\alpha \geq \omega$, donc il existe un +unique ordinal $\beta$ tel que $\alpha = \omega + \beta$. On a alors +$1 + \alpha = 1 + (\omega + \beta) = (1 + \omega) + \beta = \omega + +\beta = \alpha$. + +Si, en revanche, $\alpha$ est fini, c'est-à-dire $\alpha < \omega$, +alors $\alpha$ est un entier naturel, et comme l'addition ordinale sur +les entiers naturels coïncide avec l'addition usuelle sur ceux-ci, on +a $1 + \alpha > \alpha$. +\end{corrige} + + % % % diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 2f4dc73..c07b1a4 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -4012,9 +4012,13 @@ aussi définir $\#W$ comme l'écrasement transitif W\}$ où $\#x = \{\#y : y<x\}$, cette définition ayant bien un sens par induction transfinie (\ref{transfinite-definition} et \ref{scholion-transfinite-definition}). + +On appelle $\omega$ l'ordinal $\#\mathbb{N}$ de l'ensemble des entiers +naturels, et on identifie tout entier naturel $n$ à l'ordinal de +$\precs(n) = \{0,\ldots,n-1\}$ dans $\mathbb{N}$. \end{defn} -\thingy Ces deux façons de définir les ordinaux reviennent +\thingy Les deux façons de définir les ordinaux reviennent essentiellement au même : en effet, s'il y a une bijection croissante $W \to W'$ (forcément unique), alors les écrasements transitifs de $W$ et $W'$ coïncident, et réciproquement, si les écrasements transitifs @@ -4333,7 +4337,14 @@ suivantes : $\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$). +$\omega\gamma$ avec $\gamma>0$) ; ce $r$ sera le « chiffre des +unités » de l'écriture de $\alpha$ en forme normale de Cantor +($\xi_{(0)}$ dans la notation de \ref{base-tau-writing-of-ordinals}). +On peut aussi écrire tout ordinal $\alpha$ de façon unique comme +$\alpha = 2\gamma + r$ avec $r$ valant $0$ ou $1$ : on peut dire que +$\alpha$ est « pair » ou « impair » selon le cas (à titre d'exemple, +$\omega$ est pair car $\omega = 2\cdot\omega$) ; ce $r$ sera de même +le « chiffre des unités » de l'écriture binaire. \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 @@ -4404,6 +4415,25 @@ suivantes : transfinie). \end{itemize} +Il peut être éclairant de vérifier $2^\omega = \omega$ avec les deux +définitions de l'exponentiation. Selon la définition avec des +ensembles bien-ordonnés, $2^\omega = \#(\{0,1\}^{(\mathbb{N})})$ où +$\{0,1\}^{(\mathbb{N})}$ est l'ensemble des suites de $0$ et de $1$ +dont presque tous les termes sont des $0$, ordonnées par l'ordre +lexicographique donnant le plus de poids aux valeurs lointaines de la +suite : or de telles suites peuvent se voir comme des écritures +binaire (écrites à l'envers, i.e., en commençant par le poids faible), +et se comparent comme des écritures binaires, si bien que +$\{0,1\}^{(\mathbb{N})}$ est isomorphe, en tant qu'ensemble +bien-ordonné, à l'ensemble $\mathbb{N}$ des naturels, et son ordinal +est bien $\omega$. Selon la définition inductive, $2^\omega$ est la +limite de $2^n$ pour $n\to\omega$, c'est-à-dire la borne supérieure de +$\{2^0,2^1,2^2,2^3,\ldots\}$, or cette borne supérieure est $\omega$ +(ce ne peut pas être plus, parce que tous les $2^n$ sont des entiers +naturels donc majorés par $\omega$, et ce ne peut pas être moins car +aucun ordinal $<\omega$, i.e., aucun entier naturel, ne majore tous +les $2^n$). + \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 |