From 807ea647844b24f5afe9a285312d6fef2a8f2f00 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 23 Mar 2016 14:56:22 +0100 Subject: Start part on impartial combinatorial games. Also, clearly rename top-level sections as "parts". --- notes-mitro206.tex | 221 +++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 173 insertions(+), 48 deletions(-) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index bd89ae5..a9ccf7f 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -44,6 +44,8 @@ \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} % \DeclareUnicodeCharacter{00A0}{~} % @@ -875,7 +877,7 @@ stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en a une. \thingy\label{introduction-gale-stewart-games} Les \defin[Gale-Stewart (jeu de)]{jeux de - Gale-Stewart} (cf. section \ref{gale-stewart-games}) : soit $A$ un sous-ensemble de + Gale-Stewart} (cf. partie \ref{section-gale-stewart-games}) : soit $A$ un sous-ensemble de $\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$. Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans le premier cas) ou de $\{0,1\}$ (dans les deux suivants). Ils jouent @@ -967,7 +969,7 @@ véritablement changer le jeu. \subsection{Plan} -La section \ref{section-games-in-normal-form} concerne les jeux en +La partie \ref{section-games-in-normal-form} concerne les jeux en forme normale et la notion d'équilibre de Nash : on gardera donc à l'esprit les exemples tels que le dilemme du prisonnier (\ref{prisonners-dilemma}), le @@ -976,15 +978,17 @@ sexes (\ref{battle-of-sexes}). On évoque plus particulièrement les jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}). -La section \ref{gale-stewart-games} introduit la notion de jeux de +La partie \ref{section-gale-stewart-games} introduit la notion de jeux de Gale-Stewart et prouve un théorème fondamental de détermination (la détermination des jeux \emph{ouverts}). -La section \ref{section-well-founded-induction} introduit la notion de +La partie \ref{section-well-founded-induction} introduit la notion de graphe bien-fondée et d'induction bien-fondée qui est essentielle pour -la suite. +la suite. La partie \ref{section-ordinals} introduit la notion +d'ordinaux qui permet de généraliser beaucoup de résultats du fini à +l'infini. -La section \ref{section-combinatorial-impartial-games} concerne la +La partie \ref{section-combinatorial-impartial-games} concerne la théorie, dite « combinatoire », des jeux impartiaux à information parfaite, dont le modèle est décrit en \ref{introduction-graph-game} (sans coloriage) et dont l'archétype est le jeu de nim @@ -1463,7 +1467,7 @@ joueurs. % % -\section{Jeux de Gale-Stewart et détermination}\label{gale-stewart-games} +\section{Jeux de Gale-Stewart et détermination}\label{section-gale-stewart-games} \subsection{Définitions} @@ -1989,7 +1993,7 @@ On va définir ici rapidement les notions relatives aux jeux impartiaux ramener à des jeux de Gale-Stewart et comment la détermination des jeux ouverts peut s'appliquer dans ce contexte : -\begin{defn}\label{first-definition-impartial-combinatorial-game} +\begin{defn}\label{definition-impartial-combinatorial-game} Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une relation $E$ irréflexive dont les éléments sont appelés arêtes du graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions @@ -2018,7 +2022,7 @@ est nulle ou que les deux joueurs \defin[survie]{survivent} sans gagner. \end{defn} \thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme -en \ref{first-definition-impartial-combinatorial-game}, va définir un, +en \ref{definition-impartial-combinatorial-game}, va définir un, ou plutôt deux, jeux de Gale-Stewart : l'intuition est que si un joueur enfreint la « règle » du jeu (i.e., choisit un sommet qui n'est pas un voisin sortant du sommet actuel), il a immédiatement perdu — il @@ -2058,7 +2062,7 @@ Gale-Stewart ! Si on préfère, on peut les faire commencer à $0$, et mettre dans $A$ toutes les suites qui ne commencent pas par $x_0$.) Le jeu de Gale-Stewart $G_X(A)$ est essentiellement identique au jeu -considéré en \ref{first-definition-impartial-combinatorial-game}, à +considéré en \ref{definition-impartial-combinatorial-game}, à ceci près que les confrontations nulles sont comptées comme des gains de Bob ; le jeu $G_X(A \cup D)$, pour sa part, est lui aussi identique à ceci près que les nuls sont comptés comme des gains d'Alice. @@ -2081,7 +2085,7 @@ pair. \begin{thm}\label{determinacy-of-perfect-information-games} Soit $(G,x_0)$ un jeu combinatoire impartial à information parfaite -comme en \ref{first-definition-impartial-combinatorial-game}. Alors +comme en \ref{definition-impartial-combinatorial-game}. Alors exactement l'une des trois affirmations suivantes est vraie : \begin{itemize} \item le premier joueur (Alice) possède une stratégie gagnante, @@ -2137,7 +2141,7 @@ qui va être démontré dans la section suivante. \thingy Le but de la définition suivante est de formaliser, pour un jeu combinatoire comme -en \ref{first-definition-impartial-combinatorial-game}, les notions de +en \ref{definition-impartial-combinatorial-game}, les notions de stratégie positionnelle (dans laquelle un joueur ne choisit le coup à jouer qu'en fonction de la position actuelle), et de stratégie historique (dans laquelle il fait son choix en fonction de tous les @@ -2149,7 +2153,7 @@ se contenter de lire celle-ci. \begin{defn} Soit $G$ un graphe orienté -(cf. \ref{first-definition-impartial-combinatorial-game} et \ref{definitions-graphs}). +(cf. \ref{definition-impartial-combinatorial-game} et \ref{definitions-graphs}). Une \index{positionnelle (stratégie)}\defin{stratégie positionnelle} sur $G$ est une fonction partielle $\varsigma\colon G \dasharrow G$ (i.e., une fonction définie sur un sous-ensemble de $G$) telle que $\varsigma(x)$ soit, s'il est @@ -2404,7 +2408,7 @@ stratégie positionnelle.) Soit $G$ un graphe orienté. Quel que soit le sommet $x_0$ de $G$ choisi comme position initiale, dans le jeu combinatoire impartial à information parfaite considéré -en \ref{first-definition-impartial-combinatorial-game}, exactement +en \ref{definition-impartial-combinatorial-game}, exactement l'une des trois affirmations suivantes est vraie : \begin{itemize} \item le premier joueur (Alice) possède une stratégie positionnelle gagnante, @@ -2525,7 +2529,7 @@ démontré l'existence d'une plus petite $f$). \section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction} -Le but de cette section est de présenter les outils fondamentaux sur +Le but de cette partie est de présenter les outils fondamentaux sur les graphes orientés bien-fondés (cf. \ref{definitions-graphs}) utiles à la théorie combinatoire des jeux impartiaux. Il s'agit notamment de la théorie de l'induction bien-fondée @@ -2767,14 +2771,14 @@ bien-fondée : Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a qu'un nombre fini de voisins sortants (par exemple, un graphe fini acyclique). En utilisant le théorème \ref{well-founded-definition}, -on définit alors une fonction $\rho\colon G \to \mathbb{N}$ par -$\rho(x) = \max\{\rho(y) : y\in\outnb(x)\} + 1$ où il est convenu que +on définit alors une fonction $\rk\colon G \to \mathbb{N}$ par +$\rk(x) = \max\{\rk(y) : y\in\outnb(x)\} + 1$ où il est convenu que $\max\varnothing = -1$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ -si $x$ est un puits, et qu'on appelle $\rho$ la fonction telle que -$\rho(x) = \Phi(x, \rho|_{\outnb(x)})$ dont l'existence et l'unicité -sont garanties par le théorème. Cette fonction $\rho$ s'appelle la -\defin[rang]{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou +si $x$ est un puits, et qu'on appelle $\rk$ la fonction telle que +$\rk(x) = \Phi(x, \rk|_{\outnb(x)})$ dont l'existence et l'unicité +sont garanties par le théorème. Cette fonction $\rk$ s'appelle la +\defin[rang]{fonction rang} sur $G$, on dit que $\rk(x)$ est le rang (ou rang bien-fondé) d'un sommet $x$. (Voir aussi \ref{ordinal-valued-rank-and-grundy-function} pour une généralisation.) @@ -2787,7 +2791,7 @@ tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de rang exactement $1$, et ainsi de suite. Il revient au même de définir le rang de la manière suivante : le rang -$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus +$\rk(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus grande longueur possible d'un chemin orienté partant de $x$, c'est-à-dire, le plus grand $n$ tel qu'il existe une suite $x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le @@ -2799,15 +2803,15 @@ Voici un autre exemple de définition par induction bien-fondée : Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a qu'un nombre fini de voisins sortants. En utilisant le théorème \ref{well-founded-definition}, on définit alors une fonction -$\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(y) : +$\gr\colon G \to \mathbb{N}$ par $\gr(x) = \mex\{\gr(y) : y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S := \mathbb{N}\setminus S$ pour le plus petit entier naturel \emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle -$\gamma$ la fonction telle que $\gamma(x) = \Phi(x, -\gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont -garanties par le théorème. Cette fonction $\gamma$ s'appelle la -\defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la +$\gr$ la fonction telle que $\gr(x) = \Phi(x, +\gr|_{\outnb(x)})$ dont l'existence et l'unicité sont +garanties par le théorème. Cette fonction $\gr$ s'appelle la +\defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gr(x)$ est la valeur de Grundy d'un sommet $x$. (Voir aussi \ref{ordinal-valued-rank-and-grundy-function} pour une généralisation.) @@ -2849,9 +2853,9 @@ N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous sommet qui a au moins un P-sommet pour voisin sortant}. \end{defn} -\thingy Dans un jeu combinatoire comme exposé en +\thingy\label{discussion-n-and-p-vertices} Dans un jeu combinatoire comme exposé en \ref{introduction-graph-game} et/ou -\ref{first-definition-impartial-combinatorial-game}, si le graphe est +\ref{definition-impartial-combinatorial-game}, si le graphe est bien-fondé, les P-sommets sont les positions du jeu à partir desquelles le joueur Précédent (=second joueur) a une stratégie gagnante, tandis que les N-sommets sont celles à partir desquelles le @@ -2873,40 +2877,42 @@ en temps fini, et celui qui a joué pour aller vers les P-sommets aura gagné puisqu'il peut toujours jouer). \thingy Pour illustrer la technique de démonstration par induction -bien-fondée, montrons que si $\gamma$ est la fonction de Grundy +bien-fondée, montrons que si $\gr$ est la fonction de Grundy introduite en \ref{definition-grundy-function} et si $P$ est la partie introduite en \ref{definition-grundy-kernel}, alors on a $x \in P$ si -et seulement si $\gamma(x) = 0$, i.e., les P-sommets sont ceux pour +et seulement si $\gr(x) = 0$, i.e., les P-sommets sont ceux pour lesquels la fonction de Grundy est nulle. Par induction bien-fondé (cf. \ref{scholion-well-founded-induction}), on peut supposer la propriété (« $x \in P$ si et seulement si - $\gamma(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du + $\gr(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du sommet $x$ où on cherche à la vérifier. Si $x \in P$, cela signifie par définition de $P$ que tous ses voisins sortants $y$ de $x$ sont dans $G \setminus P$, et d'après l'hypothèse d'induction cela signifie -$\gamma(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire -$\mex\{\gamma(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et -seulement si $0 \not\in S$), ce qui signifie $\gamma(x) = 0$. Toutes +$\gr(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire +$\mex\{\gr(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et +seulement si $0 \not\in S$), ce qui signifie $\gr(x) = 0$. Toutes ces reformulations étaient des équivalences : on a bien montré que $x -\in P$ équivaut à $\gamma(x) = 0$, ce qui conclut l'induction. +\in P$ équivaut à $\gr(x) = 0$, ce qui conclut l'induction. \thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant sur la notion d'ordinaux introduite dans la -section \ref{section-ordinals}, la fonction rang peut se généraliser à +partie \ref{section-ordinals}, la fonction rang peut se généraliser à n'importe quel graphe bien-fondé (sans hypothèse de nombre fini de voisins sortants), à condition d'autoriser des valeurs ordinales -quelconques : précisément, on définit $\rho(x) = \sup\{\rho(y)+1 : +quelconques : précisément, on définit $\rk(x) = \sup\{\rk(y)+1 : y\in\outnb(x)\}$ (avec cette fois $\sup\varnothing = 0$ pour garder -$\rho(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rho(x)$ est le -plus petit ordinal strictement supérieur à $\rho(y)$ pour tout +$\rk(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rk(x)$ est le +plus petit ordinal strictement supérieur à $\rk(y)$ pour tout $y\in\outnb(x)$. De même, la fonction de Grundy peut se généraliser à n'importe quel -graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) : +graphe bien-fondé en définissant $\gr(x) = \mex\{\gr(y) : y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal -\emph{n'appartenant pas} à $S$. Il reste vrai (avec la même -démonstration) que $\gamma(x)$ est nul si et seulement si $x$ est un +\emph{n'appartenant pas} à $S$ +(voir \ref{definition-grundy-function-again} pour une écriture +formelle de cette définition). Il reste vrai (avec la même +démonstration) que $\gr(x)$ est nul si et seulement si $x$ est un P-sommet. On peut donc résumer ainsi la stratégie gagnante « universelle » pour @@ -3573,11 +3579,12 @@ est obligé de choisir un $N$ fini en formulant le vœu de redevenir humain, et Jafar peut choisir au moins $N$ vœux et gagne le combat (ainsi que quelques paquets de carambars). -\thingy La construction moderne des ordinaux, introduite par -von Neumann en 1923, est mathématiquement très élégante mais peut-être +\thingy\label{introduction-von-neumann-ordinals} +La construction moderne des ordinaux, introduite par +J. 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} +\index{von Neumann (ordinal de)}\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 @@ -3701,7 +3708,8 @@ 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. -\thingy Les ordinaux vont servir à définir différents jeux qui, pris +\thingy\label{introduction-nimbers-and-numbers} +Les ordinaux vont servir à définir différents jeux qui, pris isolément, sont extrêmement peu intéressants, mais qui ont la vertu de permettre de « mesurer » d'autres jeux : ces jeux ont en commun que, partant d'un ordinal $\alpha$, l'un ou l'autre joueur, ou les deux, @@ -3722,7 +3730,7 @@ ordinal $\alpha$ : $\beta'<\beta$. Il s'agit du jeu de nim (cf. \ref{introduction-nim-game}) avec une seule ligne d'allumettes ayant initialement $\alpha$ allumettes. Ce jeu s'appelle parfois le - « nimbre » associé à l'ordinal $\alpha$. + \index{nimbre}« nimbre » associé à l'ordinal $\alpha$. \item Deux jeux \emph{partiaux} (=partisans), où un joueur n'a aucun coup possible (il a donc immédiatement perdu si c'est à son tour de jouer, ce qui rend le jeu, pris isolément, encore plus inintéressant @@ -4480,6 +4488,123 @@ de $2^c$ pour des entiers naturels $c$ distincts). À titre d'exemple, \end{array} \] + + +% +% +% + +\section{Jeux combinatoires impartiaux à information parfaite}\label{section-combinatorial-impartial-games} + +\subsection{Récapitulations} + +\thingy On a introduit en \ref{introduction-graph-game} et plus +formellement en \ref{definition-impartial-combinatorial-game} la +notion de \emph{jeu combinatoire impartial} (à information parfaite) +associé à un graphe $G$ muni d'un sommet initial $x_0$ (c'est le jeu +où, partant de $x = x_0$, chacun des deux joueurs choisit à son tour +un voisin sortant de $x$ : si l'un des joueurs ne peut pas jouer, il a +perdu, tandis que si la confrontation se continue indéfiniment, elle +est considérée comme nulle) ; on a vu +en \ref{determinacy-of-perfect-information-games} que ces jeux sont +déterminés. + +On fera dans toute cette partie l'hypothèse supplémentaire que le +graphe $G$ est bien-fondé (cf. \ref{definitions-graphs}), c'est-à-dire +qu'aucune confrontation ne peut être nulle (=durer indéfiniement) : il +arrive forcément un point où l'un des joueurs ne peut plus jouer (et a +donc perdu), et la détermination signifie qu'un des joueurs a une +stratégie \emph{gagnante}. On peut qualifier un tel jeu de +\index{bien-fondé (jeu)}« bien-fondé » ou de \defin[terminant + (jeu)]{terminant}. + +\thingy\label{combinatorial-positions-as-games} Il va de soi qu'une +position $x$ d'un jeu combinatoire impartial $G$ peut elle-même être +considérée comme un jeu combinatoire impartial : le jeu joué \defin{à + partir de là}, à savoir celui dont $x$ est la position initiale (on +avait fait une remarque semblable pour les jeux de Gale-Stewart +en \ref{gale-stewart-positions-as-games}) et dont l'ensemble des +positions est $G$ ou, mieux (cf. paragraphe suivant) l'aval de $x$. +On se permettra souvent d'identifier ainsi une position et un jeu. + +Pour éviter des discussions inutiles, on fera aussi souvent +implicitement l'hypothèse, en parlant d'un jeu combinatoire impartial +$(G,x_0)$, que tout sommet de $G$ est accessible depuis $x_0$ +(cf. \ref{definition-accessibility-downstream} ; i.e., il n'y a pas de +positions « inutiles » car inaccessibles) : on peut toujours se +ramener à cette hypothèse en remplaçant $G$ par l'aval de $x_0$, +c'est-à-dire, en supprimant les positions inaccessibles. + +On rappelle la définition de la fonction de Grundy +(généralisant \ref{definition-grundy-function} à des valeurs non +nécessairement finies, comme expliqué +en \ref{ordinal-valued-rank-and-grundy-function}) : + +\begin{defn}\label{definition-grundy-function-again} +Soit $G$ un graphe orienté bien-fondé. On appelle \defin[Grundy + (fonction de)]{fonction de Grundy} sur $G$ la fonction $\gr$ +définie sur $G$ et à valeurs ordinales définie inductivement (en +utilisant le théorème \ref{well-founded-definition}) par $\gr(x) = +\mex\{\gr(y) : y\in\outnb(x)\}$ (où $\mex S$ désigne le plus petit +ordinal n'appartenant pas à $S$, qui existe d'après +\ref{sets-of-ordinals-are-well-ordered} +et \ref{sup-and-strict-sup-of-sets-of-ordinals}). On appelle fonction +(ou valeur) de Grundy du jeu combinatoire impartial (terminant) +associé à $(G,x_0)$ la valeur $\gr(x_0)$. +\end{defn} + +On rappelle qu'on a vu (cf. \ref{discussion-n-and-p-vertices} +à \ref{ordinal-valued-rank-and-grundy-function}) que le second joueur +(=joueur précédent) a une stratégie gagnante si et seulement si la +valeur de Grundy est $0$, tandis que le premier joueur (=joueur +suivant) en a une si et seulement si elle est $\neq 0$. La stratégie +« universelle » consiste toujours à \emph{jouer de façon à annuler la + fonction de Grundy} du sommet vers lequel on joue. La signification +de la valeur exacte de la fonction de Grundy (au-delà du fait qu'elle +soit nulle ou non nulle) est plus mystérieuse. Pour l'éclaircir, on +va introduire les \emph{nimbres} (déjà évoqués +en \ref{introduction-nimbers-and-numbers}) : + +\begin{defn}\label{definition-nimber} +Soit $\alpha$ un ordinal. On appelle alors \defin{nimbre} associé +à $\alpha$, et on note $*\alpha$, le jeu combinatoire impartial dont +\begin{itemize} +\item l'ensemble des positions est l'ensemble des ordinaux $\beta \leq + \alpha$ (c'est-à-dire, si on utilise la construction de von Neumann + des ordinaux, cf. \ref{introduction-von-neumann-ordinals}, + l'ensemble $\alpha+1$), +\item la relation d'arête (définissant le graphe) est $>$, + c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les + ordinaux $\beta'<\alpha$, +\item la position initiale est $\alpha$. +\end{itemize} +Autrement dit, il s'agit du jeu où, partant de l'ordinal $\beta = +\alpha$, chaque joueur peut dimininuer l'ordinal $\beta$, c'est-à-dire +le remplacer par un ordinal $\beta' < \beta$ de son choix (ce jeu +termine en temps fini d'après +\ref{decreasing-sequences-of-ordinals-terminate} +ou \ref{sets-of-ordinals-are-well-ordered}). + +On dira aussi que $*\alpha$ est le jeu constituée d'« une rangée de + $\alpha$ allumettes » au nim (si $\alpha$ est fini, cela coïncide +bien avec ce qu'on a dit en \ref{introduction-nim-game}). En accord +avec la remarque \ref{combinatorial-positions-as-games}, on peut +identifier les positions du nimbre $*\alpha$ avec les jeux $*\beta$ +pour $\beta\leq\alpha$. +\end{defn} + +\begin{prop} +La valeur de Grundy du nimbre $*\alpha$ est $\alpha$. +\end{prop} +\begin{proof} +On procède par induction transfinie +(cf. \ref{scholion-transfinite-induction}) : si on sait que +$\gr(*\beta) = \beta$ pour tout $\beta<\alpha$, alors +$\gr(*\alpha)$ est le plus petit ordinal différent de $\beta$ +pour $\beta<\alpha$, c'est donc exactement $\alpha$. +\end{proof} + + % % % -- cgit v1.2.3