From dbb423648ea7dde71b82f3a9245a54a23ce3369f Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 9 Mar 2016 18:26:33 +0100 Subject: Well-founded induction, von Neumann ordinals. --- notes-mitro206.tex | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 52 insertions(+), 1 deletion(-) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index f1f495d..dfb50d7 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -3317,8 +3317,31 @@ ordinaux ont de nombreux points en commun avec les entiers naturels (l'addition n'est pas commutative : on a $1+\omega = \omega$ mais $\omega+1 > \omega$). -\thingy Ce qui importe pour la théorie des jeux est le fait suivant : +\thingy Comme la récurrence pour les entiers naturels, il y a sur les +ordinaux (ou de façon équivalente, sur les ensembles bien-ordonnés) un +principe d'\emph{induction transfinie}, qui est en fait l'application +directe à eux du principe d'induction bien-fondée : son énoncé est +essentiellement le même que le principe parfois appelé de « récurrence +forte » pour les entiers naturels, c'est-à-dire que : +\begin{center} +Pour montrer une propriété sur tous les ordinaux $\alpha$ on peut +faire l'hypothèse d'induction qu'elle est déjà connue pour les +ordinaux $<\alpha$ au moment de la montrer pour $\alpha$. +\end{center} +Comme la récurrence sur les entiers naturels, et comme l'induction +bien-fondée dont c'est un cas particulier, l'induction transfinie +permet soit de \emph{démontrer} des propriétés sur les ordinaux, soit +de \emph{définir} des fonctions sur ceux-ci : +\begin{center} +Pour définir une fonction sur tous les ordinaux $\alpha$ on peut faire +l'hypothèse d'induction qu'elle est déjà définie pour les +ordinaux $<\alpha$ au moment de la définir pour $\alpha$. +\end{center} + +\thingy Ce qui importe surtout pour la théorie des jeux est le fait suivant : +\begin{center} \emph{toute suite strictement décroissante d'ordinaux est finie} +\end{center} (généralisation du fait que toute suite strictement d'entiers naturels est finie). À cause de ça, les ordinaux peuvent servir à « mesurer » toutes sortes de processus qui terminent à coup sûr en temps fini, ou @@ -3346,6 +3369,34 @@ graphe pour la relation $>$ (i.e., on fait pointer une arête orientée de chaque ordinal $\beta$ vers chaque ordinal strictement plus petit), est bien-fondé, ou de façon équivalente, bien-ordonné. +\thingy La construction moderne des ordinaux, introduite par +von Neumann en 1923, est mathématiquement très élégante mais peut-être +d'autant plus difficile à comprendre qu'elle est subtile : +\begin{center} +\emph{un ordinal est l'ensemble des ordinaux strictement plus petits que lui} +\end{center} +— ainsi, l'entier $0$ est défini comme l'ensemble vide $\varnothing$ +(puisqu'il n'y a pas d'ordinaux plus petits que lui), l'entier $1$ est +défini comme l'ensemble $\{0\} = \{\varnothing\}$ ayant pour seul +élément $0$ (puisque $0$ est le seul ordinal plus petit que $1$), +l'entier $2$ est défini comme $\{0,1\} = +\{\varnothing,\{\varnothing\}\}$, l'entier $3$ comme $\{0,1,2\} = +\{\varnothing,\{\varnothing\}, \penalty0 +\{\varnothing,\{\varnothing\}\}\}$, et ainsi de suite, et l'ordinal +$\omega$ est défini comme l'ensemble $\mathbb{N} = \{0,1,2,3,\ldots\}$ +de tous les entiers naturels, puis $\omega+1$ comme l'ensemble $\omega +\cup \{\omega\}$ des entiers naturels auquel on a ajouté le seul +élément $\omega$, et plus généralement $\alpha+1 = \alpha \cup +\{\alpha\}$. Formellement, un ordinal est l'écrasement transitif +(cf. \ref{definition-transitive-collapse}) d'un ensemble bien-ordonné +(i.e., totalement ordonné bien-fondé). + +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. + % % -- cgit v1.2.3