%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} \usepackage{hyperref} % %\externaldocument{notes-mitro206}[notes-mitro206.pdf] % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\thingy{% \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} \renewcommand{\qedsymbol}{\smiley} % \newcommand{\outnb}{\operatorname{outnb}} \newcommand{\downstr}{\operatorname{downstr}} \newcommand{\precs}{\operatorname{precs}} \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} \newcommand{\gr}{\operatorname{gr}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\fuzzy}{\mathrel{\|}} % \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} % \DeclareFontFamily{U}{manual}{} \DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} \newcommand{\manfntsymbol}[1]{% {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} \newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % \newcommand{\spaceout}{\hskip1emplus2emminus.5em} \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\par\smallbreak\else\egroup\par\fi} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{12 avril 2021} \maketitle \pretolerance=8000 \tolerance=50000 \vskip1truein\relax \noindent\textbf{Consignes.} Les exercices sont totalement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. La longueur du sujet ne doit pas effrayer : d'une part, l'énoncé est long parce que des rappels ont été faits et que la rédaction des questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera pas nécessaire de tout traiter pour obtenir la totalité des points. Les remarques en petits caractères ne font pas partie du sujet et peuvent être ignorées. \medbreak L'usage de tous les documents (notes de cours manuscrites ou imprimées, feuilles d'exercices, livres) est autorisé. L'usage des appareils électroniques est interdit. \medbreak Durée : 2h Barème \emph{indicatif} : chaque question numérotée aura approximativement la même valeur (environ $1$ à $1.5$ points). \ifcorrige Ce corrigé comporte 10 pages (page de garde incluse). \else Cet énoncé comporte 5 pages (page de garde incluse). \fi \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice On considère le jeu en forme normale, à deux joueurs, à somme nulle, dont la matrice de gains est la suivante, où $x$ est un réel (la table donne les gains d'Alice, qui choisit la ligne, ceux de Bob, qui choisit la colonne, sont opposés) : \begin{center} \begin{tabular}{r|rrrr} $\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline $\mathrm{P}$&$0$&$1$&$-1$&$x$\\ $\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ $\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ $\mathrm{S}$&$-x$&$1$&$1$&$0$\\ \end{tabular} \end{center} On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte qui réalise un gain espéré au moins égal à la valeur du jeu contre toute stratégie (pure donc mixte) de l'adversaire. \textbf{(0)} Quelle est la valeur du jeu dans ce cas ? (Ne pas faire de calcul !) \begin{corrige} On a affaire à un jeu à somme nulle \emph{symétrique} (c'est-à-dire que sa matrice de gains est antisymétrique), donc la valeur du jeu est nulle. \end{corrige} \textbf{(1)} À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P avec probabilité $\frac{1}{2}$, et chacun de Q et R avec probabilité $\frac{1}{4}$) est-elle optimale ? \begin{corrige} Ajoutons à la matrice des gains du jeu une ligne correspondant à la stratégie considérée : \begin{center} \begin{tabular}{r|rrrr} $\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline $\mathrm{P}$&$0$&$1$&$-1$&$x$\\ $\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ $\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ $\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline \hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$& $0$&$0$&$0$&$\frac{x-1}{2}$\\ \end{tabular} \end{center} Pour qu'elle réalise un gain au moins égal à la valeur du jeu, c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$, c'est-à-dire $x\geq 1$. \end{corrige} \textbf{(2)} À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ (consistant à choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec probabilité $\frac{1}{x+2}$) définit-elle une stratégie optimale ? \begin{corrige} L'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ définit une stratégie (mixte) lorsque ses coefficients sont positifs de somme $1$ : le fait qu'ils soient de somme $1$ est toujours vrai, et ils sont tous positifs lorsque $x\geq 0$. Ajoutons à la matrice des gains du jeu une ligne correspondant à la stratégie en question : \begin{center} \begin{tabular}{r|rrrr} $\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline $\mathrm{P}$&$0$&$1$&$-1$&$x$\\ $\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ $\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ $\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline \hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$& $0$&$\frac{2(1-x)}{x+2}$&$0$&$0$\\ \end{tabular} \end{center} Pour qu'elle réalise un gain au moins égal à la valeur du jeu, c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de l'adversaire, il faut et il suffit donc que $\frac{2(1-x)}{x+2} \geq 0$, c'est-à-dire $x\leq 1$, donc finalement $0\leq x\leq 1$. \end{corrige} \textbf{(3)} Donner une stratégie optimale lorsque $x\leq 0$. \begin{corrige} Lorsque $x\leq 0$, la stratégie pure $\mathrm{S}$ est optimale puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc mixte) de l'adversaire. \end{corrige} \textbf{(4)} Dans chacun des deux cas $x=0$ et $x=1$, exhiber une infinité de stratégies optimales distinctes. \begin{corrige} Lorsque $x = 0$, on a trouvé deux stratégies optimales, à savoir $\frac{1}{2}\mathrm{P} + \frac{1}{2}\mathrm{S}$ (trouvée en (2)) et $\mathrm{S}$ (trouvée en (3)). Toute combinaison convexe de ces deux stratégies optimales est donc encore optimale, c'est-à-dire $\frac{t}{2}\,\mathrm{P} + \frac{2-t}{2}\,\mathrm{S}$ pour $t\in[0;1]$. Lorsque $x = 1$, on a trouvé deux stratégies optimales, à savoir $\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (trouvée en (1)) et $\frac{1}{3}\mathrm{P} + \frac{1}{3}\mathrm{R} + \frac{1}{3}\mathrm{S}$ (trouvée en (2)). Toute combinaison convexe de ces deux stratégies optimales est donc encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} + \frac{t}{4}\,\mathrm{Q} + \frac{4-t}{12}\,\mathrm{R} + \frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$. \end{corrige} \textbf{(5)} En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au hasard} selon une loi uniforme entre $0$ et $1$ une fois que les joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S, le joueur qui a choisi P reçoit un gain aléatoire uniforme entre $0$ et $1$ ; cet aléa est, évidemment, indépendant de tous ceux que les joueurs auraient pu utiliser dans la détermination de leur propre stratégie !), quelle stratégie adopteriez-vous dans ce jeu ? \begin{corrige} On cherche à maximiser le gain \emph{espéré} minimal contre toute stratégie de l'adversaire ; mais comme $x$ est indépendant des choix qu'ont pu faire les joueurs, on peut le remplacer par son espérance, c'est-à-dire que le jeu considéré revient à prendre $x = \frac{1}{2}$. D'après la question (2), une stratégie optimale est donnée par $\frac{2}{5}\mathrm{P} + \frac{1}{5}\mathrm{R} + \frac{2}{5}\,\mathrm{S}$. \end{corrige} % % % \exercice Dans cet exercice, on va d'abord définir les ordinaux $\varepsilon_\iota$, puis on va s'intéresser à ceux qui sont $<\varepsilon_1$. Les parties de cet exercice sont indépendantes à l'exception de ce qui est explicitement rappelé. \medskip \underline{Première partie.} \nobreak On définit une fonction $\varphi$ des ordinaux vers les ordinaux par $\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est \emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ alors $\varphi(\alpha) < \varphi(\beta)$). \textbf{(1)} Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie par définition la chose suivante : si $\delta$ est un ordinal limite, alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où $\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour $\sup\{\varphi(\xi) : \xi < \delta\}$ lorsque $\varphi$ est croissante. \begin{corrige} La continuité de la fonction $\varphi\colon \alpha \mapsto \omega^\alpha$ fait partie de la définition inductive de l'exponentiation ordinale ($\omega ^ \delta = \lim_{\xi\to\delta} \omega^\xi$ si $\delta$ est limite). \end{corrige} Pour éviter de partir dans des fausses directions, il est conseillé, jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$ et de retenir seulement que $\varphi$ est strictement croissante et continue. \textbf{(2)} Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour tout $\alpha$. \begin{corrige} On a vu en cours que si $\varphi$ est une fonction strictement croissante d'un ensemble bien-ordonné vers lui-même, alors $\varphi(x) \geq x$ pour tout $x$ : il suffit d'appliquer ce résultat à la fonction $\varphi$. (Pour être tout à fait exact, on veut plutôt appliquer la \emph{démonstration} de ce résultat, vu que le résultat ne s'applique pas tel quel faute d'un ensemble bien-ordonné auquel l'appliquer vu que les ordinaux ne constituent pas un ensemble ; mais la démonstration s'applique exactement sans changement : on montre $x \leq \varphi(x)$ par induction, en effet, si par l'absurde on avait $\varphi(x) < x$, alors l'hypothèse d'induction appliquée à $y := \varphi(x)$ donnerait $\varphi(x) \leq \varphi(\varphi(x))$, tandis que la stricte croissance de $\varphi$ appliquée à $\varphi(x) < x$ donnerait $\varphi(\varphi(x)) < \varphi(x)$, ce qui est une contradiction.) \end{corrige} On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ lorsque $\varphi(\gamma) = \gamma$. \textbf{(3)} Soit dans cette question $\alpha$ un ordinal quelconque : considérons la suite $(\gamma_n)$ (indicée par les entiers naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} = \varphi(\gamma_n)$. Montrer que $(\gamma_n)$ est croissante (c'est-à-dire que $m\leq n$ implique $\gamma_m \leq \gamma_n$). Montrer que sa limite $\gamma_\omega := \lim_{n\to\omega} \gamma_n := \sup\{\gamma_n : n \in \mathbb{N}\}$ est un point fixe de $\varphi$. Montrer qu'il s'agit du plus petit point fixe de $\varphi$ qui soit $\geq\alpha$ (c'est-à-dire que si $\delta$ est un point fixe de $\varphi$ et $\delta\geq\alpha$ alors $\delta\geq\gamma_\omega$ : on pourra pour cela montrer que $\delta\geq\gamma_n$ pour tout $n$). \begin{corrige} On vient de voir que $\varphi(\alpha)\geq\alpha$ pour tout $\alpha$, ce qui montre $\gamma_{n+1}\geq\gamma_n$, donc la suite $(\gamma_n)$ est croissante. (Si on veut vraiment faire la démonstration jusqu'au bout : montrons que $m\leq n$ implique $\gamma_m \leq \gamma_n$ par récurrence sur $n\geq m$ : pour $n=m$ c'est évident, et si on a $\gamma_m \leq \gamma_n$, alors $\gamma_m \leq \gamma_n \leq \varphi(\gamma_n) = \gamma_{n+1}$ ce qui conclut la récurrence.) Montrons maintenant $\varphi(\gamma_\omega) = \gamma_\omega$. Par continuité de $\varphi$, on a $\varphi(\lim_{n\to\omega} \gamma_n) = \lim_{n\to\omega} \varphi(\gamma_n)$ (pour être tout à fait complet dans la démonstration de cette affirmation : $\gamma_\omega$ est par définition le plus petit ordinal supérieur ou égal à tous les $\gamma_n$ pour $n<\omega$, donc tout ordinal $\zeta<\gamma_\omega$ est majoré par un $\gamma_n$ pour un certain $n<\omega$, et par croissance de $\varphi$ on a alors $\varphi(\zeta)$ majoré par $\varphi(\gamma_n)$, donc la borne supérieure des $\varphi(\gamma_n)$ pour $n<\omega$ est aussi la borne supérieure des $\varphi(\zeta)$ pour $\zeta<\gamma_\omega$ : or cette dernière borne supérieure est $\varphi(\gamma_omega)$ par continuité de $\varphi$, ce qui montre $\varphi(\gamma_\omega) = \lim_{n\to\omega} \varphi(\gamma_n)$), c'est-à-dire $\varphi(\gamma_\omega) = \lim_{n\to\omega} \gamma_{1+n} = \gamma_\omega$, comme affirmé. Enfin, si $\delta$ est un point fixe de $\varphi$ et $\delta \geq \alpha$, alors par récurrence sur $n$ on a $\delta \geq \gamma_n$ pour tout $n<\omega$ (le cas $n=0$ est l'hypothèse, et $\delta \geq \gamma_n$ implique $\varphi(\delta) \geq \varphi(\gamma_n)$ par croissance de $\varphi$, c'est-à-dire $\delta \geq \gamma_{n+1}$), ce qui donne $\delta \geq \gamma_\omega$ puisque $\gamma_\omega$ est la borne supérieure des $\gamma_n$ pour $n<\omega$. \end{corrige} La question (3) implique notamment : \emph{pour tout ordinal $\alpha$ il existe un point fixe de $\varphi$ qui soit $\geq\alpha$}. On définit maintenant $\varepsilon_\iota$ pour tout ordinal $\iota$ par : \begin{itemize} \item $\varepsilon_0$ est le plus petit point fixe de $\varphi$ (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq 0$) ; \item pour $\iota+1$ ordinal successeur, $\varepsilon_{\iota+1}$ est le plus petit point fixe de $\varphi$ qui soit $>\varepsilon_\iota$ (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq (\varepsilon_\iota)+1$), \item pour $\delta$ ordinal limite, $\varepsilon_\delta$ est $\lim_{\xi\to\delta} \varepsilon_\xi$ (c'est-à-dire $\sup\{\varepsilon_\xi : \xi < \delta\}$). \end{itemize} Cette définition a bien un sens d'après ce qu'on vient de dire. \textbf{(4)} Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement croissante. Montrer que $\varepsilon_\delta$ est un point fixe de $\varphi$ aussi pour $\delta$ limite (c'est vrai dans les autres cas par la définition) : pour cela, on expliquera pourquoi $\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$. \begin{corrige} Remarquons tout d'abord que $\varepsilon_{\iota+1}$ est le plus petit point fixe de $\varphi$ qui soit strictement supérieur à $\varepsilon_\iota$, et notamment $\varepsilon_{\iota+1} > \varepsilon_\iota$, quel que soit $\iota$. Il est sans doute plus agréable, ensuite, de montrer que $\iota \mapsto \varepsilon_\iota$ est croissante à partir du fait que $\varepsilon_{\iota+1} \geq \varepsilon_\iota$ et de la continuité aux ordinaux limites (on peut légitimement tenir ce fait pour évident vu qu'il est sous-entendu par l'énoncé de la question en ce qu'elle définit $\lim_{\xi\to\delta} \varepsilon_\xi$ comme $\sup\{\varepsilon_\xi : \xi < \delta\}$). Pour cela, on montre par induction transfinie sur $\beta$ que $\alpha \leq \beta$ implique $\varepsilon_\alpha \leq \varepsilon_\beta$. Or si $\alpha = \beta$ il n'y a rien à prouver, donc supposons $\alpha < \beta$. Si $\beta$ est successeur, disons $\beta = \gamma+1$, alors $\alpha < \beta$, signifie $\alpha \leq \gamma$, auquel cas l'hypothèse d'induction (comme $\gamma<\beta$) donne $\varepsilon_\alpha \leq \varepsilon_\gamma$ et d'après la remarque qu'on a faite, $\varepsilon_\alpha \leq \varepsilon_\gamma \leq \varepsilon_{\gamma+1} = \varepsilon_\beta$ comme on voulait. Enfin, si $\beta$ est limite, alors $\varepsilon_\beta$ est défini comme la borne supérieure des $\varepsilon_\xi$ pour $\xi<\beta$, mais en particulier $\varepsilon_\alpha$ est dans cet ensemble dont on a pris la borne supérieure, donc $\varepsilon_\alpha \leq \varepsilon_\beta$. Ensuite, pour passer de croissant à strictement croissant, il suffit de dire que $\alpha < \beta$ équivaut à $\alpha+1 \leq \beta$, la croissance donne $\varepsilon_{\alpha+1} \leq \varepsilon_\beta$, et on a déjà remarqué $\varepsilon_\alpha < \varepsilon_{\alpha+1}$, d'où $\varepsilon_\alpha < \varepsilon_\beta$. Montrons enfin que $\varepsilon_\delta$ est point fixe de $\varphi$ pour $\delta$ limite. Le point crucial est qu'on a $\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$ par continuité de $\varphi$ (pour etre tout à fait complet dans la démonstration de cette affirmation : $\varepsilon_\delta$ est par définition le plus petit ordinal supérieur ou égal à tous les $\varepsilon_\xi$ pour $\xi<\delta$, donc tout ordinal $\zeta<\varepsilon_\delta$ est majoré par un $\varepsilon_\xi$ pour un certain $\xi<\delta$, et par croissance de $\varphi$ on a alors $\varphi(\zeta)$ majoré par $\varphi(\varepsilon_\xi)$, donc la borne supérieure des $\varphi(\varepsilon_\xi)$ pour $\xi<\delta$ est aussi la borne supérieure des $\varphi(\zeta)$ pour $\zeta<\varepsilon_\delta$ : or cette dernière borne supérieure est $\varphi(\varepsilon_\delta)$ par continuité de $\varphi$, ce qui montre $\varphi(\varepsilon_\delta) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$). On montre alors $\varphi(\varepsilon_\iota) = \varepsilon_\iota$ par induction sur $\xi$ : le cas successeur étant contenu dans la définiton même de $\varepsilon$, il n'y a qu'à traiter le cas limite, et on a alors $\varphi(\varepsilon_\delta) = \varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi) = \lim_{\xi\to\delta} \varepsilon_\xi = \varepsilon_\delta$. \end{corrige} \textbf{(5)} Montrer que tout ordinal $\gamma$ qui est un point fixe de $\varphi$ est de la forme $\varepsilon_\alpha$ pour un certain ordinal $\alpha$ (on pourra montrer qu'il existe $\alpha$ tel que $\varepsilon_\alpha\geq\gamma$ puis considérer le plus petit tel $\alpha$). \begin{corrige} Pour la même raison qu'en (2), on a $\varepsilon_\alpha \geq \alpha$ pour tout $\alpha$. Donné un point fixe $\gamma$ de $\varphi$, on sait donc qu'il existe $\alpha$ tel que $\varepsilon_\alpha \geq \gamma$ (on vient de voir que $\alpha=\gamma$ convient). Considérons le plus petit tel $\alpha$ : ceci a un sens car les ordinaux sont bien-ordonnés. On veut montrer qu'on a $\varepsilon_\alpha = \gamma$. Si $\alpha$ est successeur, disons $\alpha = \beta+1$, alors $\varepsilon_\beta < \gamma$ par minimalité de $\alpha$, mais comme $\gamma$ est un point fixe de $\varphi$ et que $\varepsilon_{\beta+1}$ est le plus petit point fixe après $\varepsilon_\beta$, on doit avoir $\varepsilon_{\beta+1} \leq \gamma$, soit $\varepsilon_\alpha \leq \gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$. Si $\alpha$ est limite, en revanche, par minimalité de $\alpha$, on a $\varepsilon_\xi < \gamma$ pour tout $\xi<\alpha$; or $\varepsilon_\alpha$ a été défini comme la borne supérieure de ces $\varepsilon_\xi$, donc on a $\varepsilon_\alpha \leq \gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$. \end{corrige} {\footnotesize\textit{Remarque.} On a donc démontré que la fonction $\varphi(1,\tiret) \colon \alpha \mapsto \varepsilon_\alpha$, qui énumère les points fixes de $\varphi(0,\tiret) = \varphi \colon \alpha \mapsto \omega^\alpha$ strictement croissante continue, est elle-même strictement croissante et continue. On pourrait donc continuer le procédé et appeler $\varphi(2,\tiret)$ la fonction énumérant les points fixes de $\varphi(1,\tiret)$ (c'est-à-dire que $\varphi(2,0)$ est le plus petit ordinal $\zeta$ tel que $\zeta = \varepsilon_\zeta$ puis $\varphi(2,1)$ est le suivant, etc.), « et ainsi de suite ». Ce procédé de construction d'ordinaux s'appelle les « fonctions de Veblen » : on peut bien sûr continuer en définissant $\varphi(1,0,0)$ comme le premier ordinal $\delta$ tel que $\delta = \varphi(\delta,0)$ et au-delà.\par} \medskip \underline{Deuxième partie.} \nobreak On appelle $\varepsilon_0$ le plus petit ordinal tel que $\varepsilon = \omega^\varepsilon$, et $\varepsilon_1$ le suivant, c'est-à-dire le plus petit ordinal $>\varepsilon_0$ vérifiant cette même équation $\varepsilon = \omega^\varepsilon$ (l'existence de ces ordinaux résulte de la première partie de cet exercice). On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une représentation unique sous forme normale de Cantor itérée, et que celle-ci permet de les comparer, de les ajouter et de les multiplier. On va s'intéresser ici aux ordinaux $<\varepsilon_1$, et leur donner \emph{deux} systèmes différents d'écriture, qu'on appellera « écriture 1 » et « écriture 2 ». \textbf{(6)} Soit $\alpha < \varepsilon_1$ un ordinal différent de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait, démontré en (2), que $\omega^\gamma \geq \gamma$ pour tout ordinal $\gamma$). \begin{corrige} Notons pour commencer que $\omega^{\gamma_i} \leq \alpha$ (ceci résulte de la comparaison entre les formes normales de Cantor). Si on avait $\gamma_i \geq \alpha$ alors on aurait $\alpha \geq \omega^{\gamma_i} \geq \gamma_i \geq \alpha$ : donc en fait toutes ces inégalités sont des égalités et $\alpha = \gamma_i = \omega^{\gamma_i}$ est un point fixe de la fonction $\gamma \mapsto \omega^\gamma$, ce qui, pour $\alpha < \varepsilon_1$, n'est possible que lorsque $\alpha = \varepsilon_0$, or on a supposé le contraire. C'est donc bien que $\gamma_i < \alpha$. \end{corrige} On appellera \emph{écriture 1} d'un ordinal $\alpha < \varepsilon_1$ l'écriture qui est \underline{ou bien} $\varepsilon_0$ (considéré comme un symbole spécial), \underline{ou bien} une forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où les exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits en écriture 1 (ceci a bien un sens par (6)). À titre d'exemple, $\omega^\omega\,2$ ou $\varepsilon_0$ ou bien $\omega^{\varepsilon_0} + 1$ ou encore $\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1. En revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor), ni $\varepsilon_0\,2$, ni $(\varepsilon_0)^2$. \textbf{(7)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ possède bien une écriture 1 unique. Il est alors facile de voir que cette écriture 1 permet algorithmiquement de manipuler les ordinaux $<\varepsilon_1$ : c'est-à-dire de les comparer, de les ajouter et de les multiplier (on ne demande pas de le justifier, les algorithmes étant essentiellement les mêmes que vus en cours pour les ordinaux $<\varepsilon_0$ sur la forme normale de Cantor : il faut simplement bien se rappeler dans les calculs intermédiaires le fait que $\varepsilon_0 = \omega^{\varepsilon_0}$ pour convertir $\varepsilon_0$ en forme normale de Cantor dès qu'on en a besoin). Calculer notamment $\varepsilon_0\cdot 2$ et $\varepsilon_0\cdot \omega$ en écriture 1. Expliquer ensuite comment calculer $(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est lui-même donné en écriture 1. Notamment, écrire $(\varepsilon_0)^{\omega 2}$ en écriture 1. \begin{corrige} L'existence et l'unicité de l'écriture 1 résulte du (6) : donné un ordinal $<\varepsilon_1$, soit il est égal à $\varepsilon_0$, auquel cas il a une écriture 1 par définition (et celle-ci est bien unique car on n'autorise pas de forme normale de Cantor pour lui), soit on l'écrit sous forme normale de Cantor avec des exposants strictement plus petits que lui, cette représentation est unique, et on peut recommencer le procédé, ce qui termine au bout d'un nombre fini d'étapes puisqu'on a affaire à des ordinaux qui décroissent strictement. (Ou, si on préfère, on montre par induction transfinie sur $\alpha < \varepsilon_1$ que $\alpha$ possède une écriture 1 unique par le raisonnement qu'on vient de dire.) Calculons $\varepsilon_0\cdot 2$ en écriture 1 : il suffit de réécrire $\varepsilon_0$ comme $\omega^{\varepsilon_0}$, et alors $\omega^{\varepsilon_0}\cdot 2$ est une écriture 1 légitime (c'est bien une forme normale de Cantor dont les exposants sont tous écrits en écriture 1 et plus petit que l'ordinal donné). De même, calculons $\varepsilon_0\cdot \omega$ : pour cela, on écrit $\varepsilon_0\cdot \omega = \omega^{\varepsilon_0}\cdot \omega = \omega^{\varepsilon_0+1} = \omega^{\omega^{\varepsilon_0}+1}$, ce qui est une écriture 1 légitime. Pour calculer $(\varepsilon_0)^\alpha$, on l'écrit comme $(\omega^{\varepsilon_0})^\alpha = \omega^{\varepsilon_0\,\alpha}$, or on vient de dire qu'on peut calculer algorithmiquement l'écriture 1 de $\varepsilon_0\,\alpha$ en fonction de celle de $\alpha$ : en la remplaçant dans l'exposant, on obtient alors une écriture 1 de $\omega^{\varepsilon_0\,\alpha}$ (sauf pour $\alpha=1$ auquel cas on laisse $\varepsilon_0$ comme résultat). Calculons $(\varepsilon_0)^{\omega 2}$ en écriture 1 : on vient de voir qu'il vaut $\omega^{\varepsilon_0\,\omega 2}$, or $\varepsilon_0\,\omega 2 = \omega^{\omega^{\varepsilon_0}+1}\,2$ comme ci-dessus, donc $(\varepsilon_0)^{\omega 2} = \omega^{\omega^{\omega^{\varepsilon_0}+1}\,2}$ (avec le parenthésage : $\omega^{((\omega^{((\omega^{\varepsilon_0})+1)})\cdot 2)}$). \end{corrige} \textbf{(8)} Indépendamment des questions précédentes, rappeler pourquoi tout ordinal $\alpha$ possède une écriture unique sous la forme $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$ sont des ordinaux et où $\xi_s,\ldots,\xi_1$ sont des ordinaux tous non nuls et strictement inférieurs à $\varepsilon_0$. \begin{corrige} Il s'agit de l'écriture en base $\tau$ des ordinaux, dans le cas particulier de $\tau = \varepsilon_0$. \end{corrige} \textbf{(9)} Indépendamment des questions précédentes, montrer que $\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que $\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma < \gamma'$). En déduire que $\varepsilon_0 \cdot \varepsilon_1 = \varepsilon_1$. En déduire que $(\varepsilon_0)^{\varepsilon_1} = \varepsilon_1$. Réciproquement, montrer que si $\delta$ est un ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors il vérifie aussi $\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta \leq \omega^{\varepsilon_0 \delta} = \delta$) et en déduire que $\delta \geq \varepsilon_1$. En déduire que $\varepsilon_1$ est le plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. \begin{corrige} On a $\varepsilon_0 + \varepsilon_1 = \omega^{\varepsilon_0} + \omega^{\varepsilon_1} = \omega^{\varepsilon_1}$ car $\varepsilon_0 < \varepsilon_1$. On en déduit $\varepsilon_0 \cdot \varepsilon_1 = \omega^{\varepsilon_0} \cdot \omega^{\varepsilon_1} = \omega^{\varepsilon_0 + \varepsilon_1} = \omega^{\varepsilon_1} = \varepsilon_1$. On en déduit $(\varepsilon_0)^{\varepsilon_1} = ((\omega^{\varepsilon_0})^{\varepsilon_1} = \omega^{\varepsilon_0\cdot\varepsilon_1} = \omega^{\varepsilon_1} = \varepsilon_1$. Si $(\varepsilon_0)^{\delta} = \delta$ alors $\delta \leq \omega^\delta \leq \omega^{\varepsilon_0 \delta} = (\omega^{\varepsilon_0})^\delta = (\varepsilon_0)^{\delta} = \delta$ où les deux inégalités résultent de (2) et de la croissance de $\gamma\mapsto\omega^\gamma$, donc toutes ces inégalités sont des égalités et notamment $\omega^\delta = \delta$. Comme $\varepsilon_1$ est le deuxième point fixe de $\gamma \mapsto \omega^\gamma$, on en déduit que soit $\delta = \varepsilon_0$ soit $\delta \geq \varepsilon_1$ : la première possibilité est exclue car $\varepsilon_0^{\varepsilon_0} > \varepsilon_0$ (par stricte croissance de l'exponentiation ordinale en l'exposant lorsque la base est $\geq 2$), et on a donc $\delta \geq \varepsilon_1$. On a bien prouvé que $\varepsilon_1$ est le plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. \end{corrige} On appellera \emph{écriture 2} d'un ordinal $\alpha < \varepsilon_1$ une écriture $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ comme en (7), où les exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits en écriture 2, et où les $\xi_s,\ldots,\xi_1$ (qui sont $<\varepsilon_0$) sont écrits en forme normale de Cantor itérée. À titre d'exemple, $\omega^\omega\,2$ (il faut sous-entendre $(\varepsilon_0)^0$ devant, qui vaut $1$) ou $(\varepsilon_0)^2 + 1$ ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore $(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des écritures 2. En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une (les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une forme normale de Cantor itérée, dont l'exposant ne fait donc jamais intervenir $\varepsilon_0$). \textbf{(10)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ possède bien une écriture 2 unique. Esquisser un algorithme permettant de convertire l'écriture 2 d'un ordinal $<\varepsilon_1$ en écriture 1 (on utilisera la question (7)). \begin{corrige} L'existence et l'unicité de l'écriture 2 résulte de (8) et de l'existence et unicité de la forme normale de Cantor itérée pour les ordinaux $<\varepsilon_0$. Pour convertir de l'écriture 2 en écriture 1, on part de l'écriture 2, on convertit chaque exposant de $(\varepsilon_0)^\gamma$ de l'écriture 1 en écriture 2 en utilisant l'algorithme récursivement (ceci termine bien car les exposants sont strictement plus simples, ou plus petits comme on voudra dire). On calcule alors la valeur de $(\varepsilon_0)^\gamma$ en partant de l'écriture 1 de $\gamma$ en utilisant la question (7). Il ne reste alors plus qu'à distribuer à droite les produits $(\varepsilon_0)^\gamma\cdot\xi$ avec $\xi$ écrit comme forme normale de Cantor itérée, et enfin calculer l'expression globale en écriture 1 (ce qui ne fait intervenir que des sommes et des produits, qu'on sait calculer). \end{corrige} {\footnotesize\textit{Remarque.} Il est aussi possible de convertir algorithmiquement de l'écriture 1 vers l'écriture 2 : ceci passe par calculer les $\omega^\alpha$ pour $\alpha$ donné en écriture 2.\par} \medskip \underline{Troisième partie.} \nobreak On aura besoin ici des définitions des ordinaux $\varepsilon_0$ et $\varepsilon_1$ données en tête de la première partie, mais pas plus. On s'intéresse à un jeu de Hercule et de l'hydre qui est analogue au jeu considéré en cours mais avec une extension : comme en cours, l'hydre est un arbre fini enraciné, mais l'hydre a maintenant deux types de têtes (= feuilles de l'arbre) : des têtes normales, et des \emph{œufs} (pouvant donner naissance à de nouvelles hydres). Quand Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant d'exemplaires qu'elle le veut, œufs compris, de tout le sous-arbre partant du nœud $y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine (sinon, l'hydre ne joue pas). En revanche, si Hercule coupe un œuf, cet œuf éclot est remplacé par une nouvelle hydre, c'est-à-dire par un sous-arbre, arbitrairement complexe (choisi par le joueur qui contrôle l'hydre), mais ne comportant lui-même pas d'œuf, qui prend la place de la tête où était situé l'œuf. A titre d'exemple, sur le dessin suivant, où les œufs ont été représentés par des ovales gris, selon la tête coupée par Hercule : \begin{center} \begin{tikzpicture}[baseline=0] \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (0,2) {}; \node (P3) at (-1,3) {}; \node (P4) at (1,3) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P2) -- (P3); \draw (P2) -- (P4); \fill[fill=gray] (P3) to[out=0,in=270] ($(P3) + (0.3,0.3)$) to[out=90,in=0] ($(P3) + (0,1.0)$) to[out=180,in=90] ($(P3) + (-0.3,0.3)$) to[out=270,in=180] (P3); \end{scope} \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node at (P3) {}; \end{scope} \end{tikzpicture} peut devenir \begin{tikzpicture}[baseline=0] \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (0,2) {}; \node (P3) at (-1,3) {}; \node (P4) at (1,3) {}; \node (P3a) at (-1.5,4) {}; \node (P3b) at (-1,4) {}; \node (P3c) at (-0.5,4) {}; \node (P3aa) at (-1.75,4.5) {}; \node (P3ab) at (-1.25,4.5) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P2) -- (P3); \draw (P2) -- (P4); \draw (P3) -- (P3a); \draw (P3) -- (P3b); \draw (P3) -- (P3c); \draw (P3a) -- (P3aa); \draw (P3a) -- (P3ab); \end{scope} \end{tikzpicture} ou \begin{tikzpicture}[baseline=0] \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (0,2) {}; \node (P3a) at (-1,3) {}; \node (P2b) at (0.5,2) {}; \node (P3b) at (-0.25,3) {}; \node (P2c) at (1,2) {}; \node (P3c) at (0.5,3) {}; \node (P2d) at (1.5,2) {}; \node (P3d) at (1.25,3) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P1) -- (P2b); \draw (P1) -- (P2c); \draw (P1) -- (P2d); \draw (P2) -- (P3a); \draw (P2b) -- (P3b); \draw (P2c) -- (P3c); \draw (P2d) -- (P3d); \fill[fill=gray] (P3a) to[out=0,in=270] ($(P3a) + (0.3,0.3)$) to[out=90,in=0] ($(P3a) + (0,1.0)$) to[out=180,in=90] ($(P3a) + (-0.3,0.3)$) to[out=270,in=180] (P3a); \fill[fill=gray] (P3b) to[out=0,in=270] ($(P3b) + (0.3,0.3)$) to[out=90,in=0] ($(P3b) + (0,1.0)$) to[out=180,in=90] ($(P3b) + (-0.3,0.3)$) to[out=270,in=180] (P3b); \fill[fill=gray] (P3c) to[out=0,in=270] ($(P3c) + (0.3,0.3)$) to[out=90,in=0] ($(P3c) + (0,1.0)$) to[out=180,in=90] ($(P3c) + (-0.3,0.3)$) to[out=270,in=180] (P3c); \fill[fill=gray] (P3d) to[out=0,in=270] ($(P3d) + (0.3,0.3)$) to[out=90,in=0] ($(P3d) + (0,1.0)$) to[out=180,in=90] ($(P3d) + (-0.3,0.3)$) to[out=270,in=180] (P3d); \end{scope} \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node at (P3a) {}; \node at (P3b) {}; \node at (P3c) {}; \node at (P3d) {}; \end{scope} \end{tikzpicture} \end{center} \textbf{(11)} En associant à toute position du jeu (= tout arbre enraciné dont certaines feuilles sont qualifiées d'œufs) un ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours, c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en temps fini (quoi qu'il fasse et quoi que fasse l'hydre). \begin{corrige} À toute hydre $T$ on associe un ordinal $o(T) <\varepsilon_1$ par récurrence sur la profondeur de l'arbre, de la façon suivante : si $T$ est un œuf, alors on pose $o(T) = \varepsilon_0$ ; sinon, si $T_1,\ldots,T_r$ sont les sous-arbres ayant pour racine les fils de la racine, triés de façon que $o(T_1) \geq \cdots \geq o(T_r)$, alors on pose $o(T) = \omega^{o(T_1)} + \cdots + \omega^{o(T_r)}$. Exactement les mêmes démonstrations que dans le cours tiennent, il faut simplement ajouter la clause suivante : si $T$ est un œuf et $T'$ est une hydre sans œuf, alors $o(T') < \varepsilon_0 = o(T)$, donc en remplaçant l'œuf par une hydre sans œuf quelconque, on fait strictement décroître l'ordinal. (Remarquons que, comme $\varepsilon_0 = \omega^{\varepsilon_0}$, une tige de longueur arbitraire se finissant par un œuf a toujours la même valeur $\varepsilon_0$ avec ce système : ce n'est pas un problème, et ce n'est pas surprenant puisque de telles tiges offrent essentiellement les mêmes possibilités à l'hydre.) \end{corrige} \textbf{(12)} Donner un exemple de position du jeu associé à l'ordinal $(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11). \begin{corrige} L'hydre suivante (dans laquelle les œufs ont été représentés par des ovales gris) : \begin{center} \begin{tikzpicture} \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (0,2) {}; \node (P3) at (-1,3) {}; \node (P4) at (1,3) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P2) -- (P3); \draw (P2) -- (P4); \fill[fill=gray] (P3) to[out=0,in=270] ($(P3) + (0.3,0.3)$) to[out=90,in=0] ($(P3) + (0,1.0)$) to[out=180,in=90] ($(P3) + (-0.3,0.3)$) to[out=270,in=180] (P3); \fill[fill=gray] (P4) to[out=0,in=270] ($(P4) + (0.3,0.3)$) to[out=90,in=0] ($(P4) + (0,1.0)$) to[out=180,in=90] ($(P4) + (-0.3,0.3)$) to[out=270,in=180] (P4); \end{scope} \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node at (P3) {}; \node at (P4) {}; \end{scope} \end{tikzpicture} \end{center} a la valeur $\omega^{\omega^{\varepsilon_0\,2}} = \omega^{(\omega^{\varepsilon_0})^2} = \omega^{\varepsilon_0^2} = (\omega^{\varepsilon_0})^{\varepsilon_0} = (\varepsilon_0)^{\varepsilon_0}$, comme demandé. \end{corrige} {\footnotesize\textit{Remarque.} Pour rendre ce jeu plus intéressant, il faudrait sans doute ajouter une règle selon laquelle Hercule ne peut couper un œuf que s'il ne reste aucune tête non-œuf à couper, sinon il est assez clair qu'il a intérêt à commencer par éliminer tous les œufs. Mais cette contrainte, puisqu'elle ne concerne qu'Hercule n'a aucune influence sur ce qu'on vient de prouver.\par} % % % \end{document}