summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-03-09 18:26:33 +0100
committerDavid A. Madore <david+git@madore.org>2016-03-09 18:26:33 +0100
commitdbb423648ea7dde71b82f3a9245a54a23ce3369f (patch)
treea6f5f9cca32c0c43489c8106c4e76bf81e991548
parentac917f5ec32b5401db42e185f4eb59e8d3b1766e (diff)
downloadmitro206-dbb423648ea7dde71b82f3a9245a54a23ce3369f.tar.gz
mitro206-dbb423648ea7dde71b82f3a9245a54a23ce3369f.tar.bz2
mitro206-dbb423648ea7dde71b82f3a9245a54a23ce3369f.zip
Well-founded induction, von Neumann ordinals.
-rw-r--r--notes-mitro206.tex53
1 files changed, 52 insertions, 1 deletions
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.
+
%
%