summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex97
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.
%