diff options
| -rw-r--r-- | notes-mitro206.tex | 97 |
1 files changed, 95 insertions, 2 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index dfb50d7..e06f8c4 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -3175,7 +3175,7 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$). \section{Introduction aux ordinaux} -\subsection{Explication intuitive} +\subsection{Présentation informelle} \thingy Les ordinaux sont une sorte de nombres, totalement ordonnés et même « bien-ordonnés », qui généralisent les entiers naturels en @@ -3395,7 +3395,100 @@ Cette définition a certains avantages, par exemple la borne supérieure d'un ensemble $S$ d'ordinaux est simplement la réunion $\bigcup_{\alpha\in S} \alpha$ de(s éléments de) $S$. Néanmoins, elle n'est pas vraiment nécessaire à la théorie des ordinaux, et nous -tâcherons d'éviter d'en dépendre. +tâcherons d'éviter d'en dépendre. Mais il faut au moins retenir une +idée : + +\thingy Tout ensemble $S$ d'ordinaux, il existe un ordinal qui est +plus grand que tous les éléments de $S$ ; il existe même un \emph{plus + petit} ordinal plus grand que tous les éléments de $S$, +c'est-à-dire, une \emph{borne supérieure} de $S$. Ce fait est la clé +de l'inexhaustibilité des ordinaux : quelle que soit la manière dont +on essaie de rassembler des ordinaux en un ensemble, on peut trouver +un ordinal strictement plus grand qu'eux (en particulier, les ordinaux +ne forment pas un ensemble, pour un peu la même raison que l'ensemble +de tous les ensembles n'existe pas : il est « trop gros » pour tenir +dans un ensemble). + +\thingy Pour aider à comprendre comment les choses commencent, et en +partant de l'idée générale que +\begin{center} +\emph{comprendre un ordinal, c'est comprendre tous les ordinaux + strictement plus petits que lui, et comment ils s'ordonnent} +\end{center} +voici comment s'arrangent les plus petits ordinaux. + +Après les entiers naturels $0,1,2,3,\ldots$ vient l'ordinal $\omega$ +puis $\omega+1,\omega+2,\omega+3$ et ainsi de suite, après quoi +viennent $\omega 2, \omega 2+1, \omega 2+2,\ldots$ qui sont suivis de +$\omega 3$ et le même mécanisme recommence. Les ordinaux $\omega k + +n$ pour $k,n\in\mathbb{N}$ sont ordonnés par l'ordre lexicographique +donnant plus de poids à $k$ : l'ordinal qui vient immédiatement après +(c'est-à-dire, leur ensemble, si on utilise la construction de +von Neumann) est $\omega\cdot\omega = \omega^2$, qui est suivi de +$\omega^2+1,\omega^2+2,\ldots$ et plus généralement des $\omega^2 + +\omega k + n$, qui sont eux-mêmes suivis de $\omega^2 \cdot 2$. Les +$\omega^2 \cdot n_2 + \omega \cdot n_1 + n_0$ sont ordonnés par +l'ordre lexicographique donnant plus de poids à $n_2$, puis à $n_1$ +puis à $n_0$. L'ordinal qui vient immédiatement après tous ceux-ci +est $\omega^3$. + +En itérant ce procédé, on fabrique de même $\omega^4$, puis $\omega^5$ +et ainsi de suite : les $\omega^r \cdot n_r + \cdots + \omega \cdot +n_1 + n_0$ (c'est-à-dire en quelque sorte des polynômes en $\omega$ à +coefficients dans $\mathbb{N}$) sont triés par ordre lexicographique +en donnant plus de poids aux coefficients $n_i$ pour $i$ grand (et en +identifiant bien sûr un cas où $n_r = 0$ par celui où il est omis : il +s'agit de l'ordre lexicographique sur les suites d'entiers nulles à +partir d'un certain rang). L'ordinal qui vient immédiatement après +est $\omega^\omega$, puis on a tous les $\omega^\omega + \omega^r +\cdot n_r + \cdots + \omega \cdot n_1 + n_0$ jusqu'à $\omega^\omega +\cdot 2$, et de même $\omega^\omega \cdot 3$, etc., jusqu'à +$\omega^\omega \cdot \omega = \omega^{\omega+1}$. + +En répétant $\omega$ fois toute cette séquence, on obtient +$\omega^{\omega+2}$, puis de nouveau $\omega^{\omega+3}$ et ainsi de +suite : après quoi vient $\omega^{\omega 2}$, et on voit comment on +peut continuer de la sorte. + +\thingy Plus généralement, tout ordinal va s'écrire de façon unique +sous la forme $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ +où $\gamma_s > \cdots > \gamma_1$ sont des ordinaux et +$n_s,\ldots,n_1$ sont des entiers naturels non nuls (si un $n_i$ est +nul il convient de l'omettre) : il s'agit d'une sorte d'écriture en +« base $\omega$ » de l'ordinal, appelée \textbf{forme normale de + Cantor}. On compare deux formes normales de Cantor en comparant le +terme dominant (le plus à gauche, i.e., $\omega^{\gamma_s} n_s$ dans +les notations qui viennent d'être données, ce qui se fait lui-même en +comparant les $\gamma_s$ et sinon, les $n_s$), et s'ils sont égaux, en +comparant le suivant et ainsi de suite. + +La forme normale de Cantor ne permet cependant pas de « comprendre » +tous les ordinaux, car il existe des ordinaux tels que $\varepsilon = +\omega^\varepsilon$. Le plus petit d'entre eux est noté +$\varepsilon_0$ et est la limite de +$\omega,\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$ + +\thingy On retiendra qu'il existe trois sortes d'ordinaux, cette +distinction étant souvent utile dans les inductions : +\begin{itemize} +\item l'ordinal nul $0$, qui est souvent un cas spécial, +\item les ordinaux « successeurs », c'est-à-dire ceux qui sont de la + forme $\beta+1$ pour $\beta$ un ordinal plus petit (de façon + équialente, il y a un plus grand ordinal strictement plus petit), +\item les ordinaux qui sont la borne supérieure (ou « limite ») des + ordinaux strictement plus petits et qu'on appelle, pour cette + raison, « ordinaux limites » (autrement dit, $\delta$ est limite + lorsque pour tout $\beta<\delta$ il existe $\beta'$ avec + $\beta<\beta'<\delta$). +\end{itemize} +À titre d'exemple, l'ordinal $0$, l'ordinal $42$ et l'ordinal $\omega$ +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 +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. % |