%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[a4paper,margin=2.5cm]{geometry} \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{\dur}{\operatorname{dur}} \newcommand{\fuzzy}{\mathrel{\|}} % \newcommand{\dblunderline}[1]{\underline{\underline{#1}}} % \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{22 avril 2024} \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. \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 \ifcorrige Ce corrigé comporte 6 pages (page de garde incluse). \else Cet énoncé comporte 3 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 \textbf{(1)} On considère le jeu en forme normale défini par la matrice de gain suivante : \begin{center} \begin{tabular}{r|cc} $\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline $X$&$1$&$0$\\ $Y$&$0$&$2$\\ \end{tabular} \end{center} Un seul nombre a été inscrit dans chaque case car les gains des deux joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit (attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au lieu d'être opposés, les intérêts des deux joueurs sont parfaitement identiques). Étudier et déterminer tous les équilibres de Nash de ce jeu : on commencera par considérer ceux en stratégies pures, puis par considérer les cas où un joueur, ou l'autre, ou les deux, joue une stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$). \begin{corrige} Si Alice joue (purement) $X$, les options de Bob apportent les gains $1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob est de jouer purement $X$. De même, si Alice joue (purement) $Y$, les options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont la seule meilleure réponse de Bob est de jouer purement $Y$. Le rôle des deux joueurs étant symétrique, ceci prouve que, dans un équilibre de Nash, si l'un joue purement une des deux options, l'autre doit jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$ (avec gain $1$) et $(Y,Y)$ (avec gain $2$). Si Alice joue une stratégie strictement mixte dans un équilibre de Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain d'Alice doit être la même pour les deux options du support de sa stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$. Par symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \; \frac{2}{3}X + \frac{1}{3}Y)$. \end{corrige} \textbf{(2)} Plus généralement, on considère un jeu de la forme suivante : les deux joueurs ont le même ensemble d'options, notons-le $\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$ pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque $b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$ sont des réels strictement positifs ($g_i > 0$). Pour résumer : \begin{center} \begin{tabular}{r|ccc} $\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline $X_1$&$g_1$&$\cdots$&$0$\\ $\vdots$&$\vdots$&$\ddots$&$\vdots$\\ $X_N$&$0$&$\cdots$&$g_N$\\ \end{tabular} \end{center} \textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le support\footnote{On rappelle que le support d'une stratégie mixte est l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus dans $I$. (\emph{Indication :} toute option hors de $I$ apporte un gain espéré nul, donc strictement moins bon que n'importe quelle combinaison convexe d'options dans $I$.) En déduire par symétrie que $I=J$. \begin{corrige} Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob, tandis que toute option $X_i \in I$ apporte un gain strictement positif (puisque $g_i$ est pondéré avec un coefficient strictement positif, tout le reste étant nul). Il s'ensuit qu'une meilleure réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc inclure que des options dans $I$. Donc $J \subseteq I$. Et par symétrie des deux joueurs, $I \subseteq J$. Donc finalement $I = J$. \end{corrige} \textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte) d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire $X_i \in I$) sont tous égaux entre eux. En déduire par symétrie le résultat analogue pour la stratégie de Bob, donc qu'elles sont égales. En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$. \begin{corrige} En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être toujours le même. Or ce gain est $g_i p_i$. Donc tous les $g_i p_i$ pour $X_i \in I$ sont égaux. C'est-à-dire que les $p_i$ sont proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant nuls). Ceci détermine la stratégie d'Alice, et par symétrie c'est aussi celle de Bob. On a donc trouvé $2^N - 1$ équilibres de Nash potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$. \end{corrige} \textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont bien des équilibres de Nash du jeu, et conclure qu'il a exactement $2^N - 1$ équilibres de Nash, qu'on décrira explicitement. \begin{corrige} Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien décrit une stratégie mixte pour chacun des deux joueurs (c'est la même) : on a bien affaire à des réels $p_i$ positifs de somme $1$. Le gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si $X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a fortiori avec une stratégie mixte), donc cette stratégie est bien une meilleure réponse possible contre elle-même, et on a bien affaire à un équilibre de Nash. Pour résumer : tous les équilibres de Nash sont décrits de la façon suivante : pour une certaine partie non vide $I$ de $\{X_1,\ldots,X_N\}$, on pose \[ \left\{ \begin{array}{ll} p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\ p_i = 0&\text{sinon} \end{array} \right. \] et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien déterminé par l'équilibre puisque c'est le support commun des stratégies des deux joueurs, donc tous les équilibres qu'on vient de décrire sont distincts). Il y en a donc exactement $2^N - 1$. \end{corrige} % % % \exercice On considère un jeu de la forme suivante. Soit $A \subseteq \mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel. (Toutes ces données sont fixées à l'avance et sont des paramètres définissant le jeu. Ils sont supposés connus des deux joueurs.) Chaque joueur quand vient son tour choisit un élément $x_i \in X$ : plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis Alice choisit $x_2$, et ainsi de suite. Il n'y a aucune contrainte sur le choix du $x_i$ et chacun a connaissance de tous les coups antérieurs. Au bout d'un nombre infini de tours, on considère le réel \[ u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots \] c'est-à-dire la somme de la série $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Cette série converge car elle converge absolument\footnote{\label{footnote-series-converges}Preuve : $\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq \sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}. Si $u\in A$ alors Alice a gagné ; sinon, Bob a gagné. (Un cas particulier qu'on peut garder à l'esprit est celui où $X = \{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre binaire entre $0$ et $2$ en choisissant alternativement ses chiffres : $u = x_0.x_1 x_2 x_3\cdots$ en binaire.) On cherche à montrer que sous certaines conditions sur $A$, l'un des joueurs a une stratégie gagnante. \textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to \mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}} \in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$, alors il existe $\ell \in \mathbb{N}$ tel que toute suite $\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie $|\psi(\dblunderline{y})-u| < \varepsilon$. Autrement dit, il existe $\ell$ tel que l'image du $\ell$-ième voisinage fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est l'ensemble des suites commençant par les $\ell$ termes $x_0,\ldots,x_{\ell-1}$.} $V_\ell(\dblunderline{x})$ de $\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte $B_\varepsilon(u) := \mathopen]u-\varepsilon,u+\varepsilon\mathclose[$. (\emph{Indication :} s'inspirer de la note \ref{footnote-series-converges}.) \begin{corrige} Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| = |\psi(\dblunderline{y})-\dblunderline{x}| = \left|\sum_{i=\ell}^{+\infty} \frac{x_i}{b^i}\right| \leq \sum_{i=\ell}^{+\infty} \left|\frac{x_i}{b^i}\right| \leq \sum_{i=\ell}^{+\infty} \frac{M}{b^i} = \frac{Mb^\ell}{1-b}$. Cette quantité tend vers $0$ quand $\ell\to+\infty$, donc il existe $\ell$ tel qu'elle soit $<\varepsilon$. Ceci montre bien que si $\dblunderline{y} \in V_\ell(\dblunderline{x})$ on a $|\psi(\dblunderline{y})-u| < \varepsilon$. \end{corrige} \textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq \mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe $\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte (au sens de la topologie produit de la topologie discrète sur $X^{\mathbb{N}}$, qu'on a considérée en cours). \begin{corrige} Supposons que $U$ soit ouvert. Si $\dblunderline{x} \in \psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme $U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$, et d'après la question (1), il existe $\ell$ tel que $\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$. On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans $\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert. (Note : on a évité dans ce corrigé d'utiliser le mot « continu » car il n'a pas été défini en cours dans le contexte d'une application de $X^{\mathbb{N}}$ vers $\mathbb{R}$. Mais bien sûr, il est correct de dire que $\psi$ est continue en tant qu'application entre espaces topologiques.) \end{corrige} \textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie gagnante au jeu qu'on a décrit. \begin{corrige} Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par la partie $\psi^{-1}(A)$. Si $A$ est ouvert, alors la question (2) montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé d'après le théorème de détermination des jeux ouverts. Si $A$ est fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert, donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) = X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que $\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le théorème de détermination des jeux fermés. \end{corrige} \textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$ (autrement dit, Alice gagne si la somme $u$ de la série est rationnelle\footnote{Merci d'avance de ne pas prétendre que $\mathbb{Q}$ est ouvert, ni qu'il est fermé.}). Plus généralement, montrer ce résultat lorsque $A$ est borélien. \begin{corrige} L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$ pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ; l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans $X^{\mathbb{N}}$). D'après le théorème de détermination des jeux boréliens, le jeu est déterminé. Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$ préserve les réunions et intersections quelconques, ainsi que le complémentaire) et elle contient les ouverts (puisqu'on a vu que $\psi^{-1}(U)$ est ouvert pour $U$ ouvert). Elle contient donc les boréliens de $\mathbb{R}$. C'est-à-dire que si $B$ est borélien dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans $X^{\mathbb{N}}$. D'après le théorème de détermination des jeux boréliens, le jeu est déterminé dès que $A$ est borélien. \end{corrige} % % % \exercice On va développer dans cet exercice un algorithme pour calculer la somme et le produit d'ordinaux écrits en forme normale de Cantor (itérée). \textbf{(1)} On rappelle que $1 + \omega = \omega$. En déduire que si un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 + \alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire $\alpha = \omega + \beta$). En déduire que $1 + \omega^\gamma = \omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} + \omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$, et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 = \omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non nuls (et toujours avec $\gamma_1 < \gamma_2$). \begin{corrige} On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique $\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si $\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta = \alpha$. Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma \geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma = \omega^\gamma$. Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 + \gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} + \omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} = \omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} = \omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \, \omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$. Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} = \omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} + \omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes $\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut $\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2} n_2$, comme annoncé. \end{corrige} \textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et $n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ (idem) sont deux ordinaux écrits en forme normale de Cantor, en utilisant les résultats de la question précédente, expliquer comment calculer $\alpha + \alpha'$, en supposant qu'on sache algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$. \begin{corrige} On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que deux termes ne sont pas dans le bon ordre (i.e., si un $\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i < \gamma_j$), alors le premier disparaît purement et simplement ; et bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en $\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite. On se retrouve donc avec l'écriture en forme normale de Cantor de $\alpha + \alpha'$. \end{corrige} \textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot 3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha + \alpha'$ et $\alpha' + \alpha$. \begin{corrige} Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot 3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 + \omega\cdot 4$. Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) + (\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot 3 + 5$. \end{corrige} \textbf{(4)} Déduire de la question (2) que si $\alpha = \omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme normale de Cantor et $k \geq 1$ est un entier naturel, alors $\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots + \alpha$ avec $k$ termes identiques). \begin{corrige} En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de la distributivité à droite) et en appliquant les règles expliquées en (2), on voit que tous les termes autres que le plus haut de tous les termes autres que le dernier de la terme disparaissent purement et simplement (ils sont absorbés par le terme le plus haut du $\alpha$ suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$ plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ comme annoncé. \end{corrige} \textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega = \omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer $\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot \omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$ (\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$). \begin{corrige} On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot k$ (rappelons que cette limite est juste une borne supérieure). Par comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc $\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$. Mais inversement, la forme normale de Cantor de tout ordinal $<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s} N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas être $<\omega^{\gamma_s+1}$. Donc c'est exactement $\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega = \omega^{\gamma_s+1}$. Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' = 1+\gamma''$ comme on l'a déjà rappelé plus haut, et $\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} = \alpha\cdot\omega\omega^{\gamma''} = \omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} = \omega^{\gamma_s+\gamma'}$. \end{corrige} \textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme normale de Cantor, en utilisant les résultats de la question précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en supposant qu'on sache algorithmiquement comparer et ajouter les $\gamma_i$ et les $\gamma'_j$. \begin{corrige} Par distributivité à droite et comme on sait déjà calculer des sommes, on peut se ramener au cas où $\alpha'$ est un seul terme $\omega^{\gamma'} n'$. Par associativité, il suffit de savoir calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$. Le produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé par la question (5) si $\gamma'>0$. Et le produit par $n'$ est réglé par la question (4). Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel $\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j = \omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe (c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 = \omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$. Il n'y a plus qu'à ajouter tous ces termes dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s + \gamma'_2 > \gamma_s > \cdots > \gamma_1$). \end{corrige} \textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot 3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot \alpha'$ et $\alpha' \cdot \alpha$. \begin{corrige} Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot 3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier terme de $\alpha$ survit). Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4) (\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 + \omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$. \end{corrige} % % % \end{document}