Write answers to second exercise (and get very much messed up).

1 files changed, 179 insertions, 30 deletions

diff --git a/controle-20190408.tex b/controle-20190408.tex
index 1f6164c..795695c 100644
--- a/controle-20190408.tex
+++ b/controle-20190408.tex
@@ -373,31 +373,90 @@ bien-fondée.
 
 \medskip
 
+%% À toutes fins utiles, on signale le fait évident qu'on a $\xi =
+%% \sup^+ S$ si et seulement si on a (i) $\xi$ est strictement
+%% supérieur à tout élément de $S$, et (ii) tout ordinal $<\xi$ est
+%% inférieur ou égal à un élément de $S$.
+
+À toutes fins utiles, on signale le fait évident que $\sup^+ S$ ne
+change pas si on insère dans $S$ des nouveaux éléments qui sont
+majorés par des éléments déjà dans $S$.
+
+\medskip
+
 (1)(a) Calculer $m\boxplus n$ pour $0\leq m\leq 5$ et $0\leq n\leq
 5$.\quad(b) Conjecturer une formule générale pour $m\boxplus n$
 lorsque $m,n\in\mathbb{N}$ (c'est-à-dire
 $m,n<\omega$).\quad(c) Démontrer cette formule.
 
+\begin{corrige}
+(a)/(b) On construit le tableau de proche en proche en inscrivant dans
+  chaque case le plus petit entier strictement supérieur à tous les
+  nombres écrits plus haut dans la colonne ou plus à gauche dans la
+  ligne : on obtient $m\boxplus n = m + n$, et on peut imaginer que
+  c'est vrai en général.
+
+(c) Montrons que $m\boxplus n = m + n$ pour tous $m,n\in\mathbb{N}$ :
+  par récurrence (sur $m+n$), on peut supposer connu le fait que
+  $m'\boxplus n = m' + n$ pour tout $m'<m$ et $m\boxplus n' = m + n'$
+  pour tout $n'<n$, alors $m\boxplus n$.  On a alors $m \boxplus n =
+  \sup^+ \big( \{m' \boxplus n : m' < m\} \cup\, \{m \boxplus n' : n'
+  < n\}\big) = \sup^+ \big( \{m' + n : m' < m\} \cup\, \{m + n' : n' <
+  n\}\big)$ ; or l'ensemble dont on prend le $\sup^+$ ne contient que
+  des entiers $<m+n$ et contient $m+n-1$ donc ce $\sup^+$ vaut $m+n$,
+  ce qui conclut la récurrence.
+\end{corrige}
+
 \medskip
 
 (2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que
-$\alpha\boxplus\beta = \beta\boxplus\alpha$ quels que
-soient $\alpha,\beta$.\quad(b) Montrer que $\boxplus$ admet $0$ pour
-élément neutre, c'est-à-dire que $\alpha\boxplus 0 = 0\boxplus\alpha =
-\alpha$ pour tout ordinal $\alpha$.
+$\alpha_1\boxplus\alpha_2 = \alpha_2\boxplus\alpha_1$ quels que
+soient $\alpha_1,\alpha_2$.\quad(b) Montrer que $\boxplus$ admet $0$
+pour élément neutre, c'est-à-dire que $\alpha\boxplus 0 =
+0\boxplus\alpha = \alpha$ pour tout ordinal $\alpha$.\quad(c) Montrer
+que si $\alpha'\leq\alpha$ et $\beta'\leq\beta$ alors
+$\alpha'\boxplus\beta' \leq \alpha\boxplus\beta$, avec égalité stricte
+dans la conclusion si au moins une d'elles est stricte dans
+l'hypothèse.
+
+\begin{corrige}
+(a) Par induction transfinie sur $\alpha_1$ et $\alpha_2$, on prouve
+  $\alpha_2\boxplus\alpha_1 = \alpha_1\boxplus\alpha_2$ : en effet,
+  $\alpha_2\boxplus\alpha_1 = \sup^+ (\{\alpha_2\boxplus\beta_1:
+  \beta_1<\alpha_1\} \cup \{\beta_2\boxplus\alpha_1:
+  \beta_2<\alpha_2\})$, et par hypothèse d'induction ceci vaut $\sup^+
+  (\{\beta_1\boxplus\alpha_2: \beta_1<\alpha_1\} \cup
+  \{\alpha_1\boxplus\beta_2: \beta_2<\alpha_2\}) =
+  \alpha_1\boxplus\alpha_2$.
+
+(b) Par induction sur $\alpha$, on prouve $\alpha \boxplus 0 =
+  \alpha$ : en effet, $\alpha \boxplus 0 = \sup^+ \{\beta\boxplus 0:
+  \beta<\alpha\}$, et par hypothèse d'induction ceci vaut $\sup^+
+  \{\beta: \beta<\alpha\} = \alpha$.  Par la commutativité déjà
+  prouvée, $0 \boxplus \alpha$ vaut lui aussi $\alpha$.
+
+(c) Si $\alpha'<\alpha$ alors $\alpha'\boxplus\beta <
+  \alpha\boxplus\beta$ par définition même de $\alpha\boxplus\beta$,
+  et de même si $\beta'<\beta$ alors $\alpha\boxplus\beta' <
+  \alpha\boxplus\beta$.  Si on a à la fois $\alpha'<\alpha$ et
+  $\beta'<\beta$ alors $\alpha'\boxplus\beta' < \alpha'\boxplus\beta <
+  \alpha\boxplus\beta$ d'après ce qu'on vient de dire.  C'est
+  exactement ce qu'il fallait démontrer.
+\end{corrige}
 
 \medskip
 
 On \underline{admettra} pour la suite que $\boxplus$ est associative,
 c'est-à-dire que $(\alpha_1\boxplus\alpha_2) \boxplus \alpha_3 =
 \alpha_1 \boxplus (\alpha_2\boxplus\alpha_3)$ quels que soient
-$\alpha_1,\alpha_2,\alpha_3$, et que
+$\alpha_1,\alpha_2,\alpha_3$ ; et on admettra que
 $\alpha_1\boxplus\cdots\boxplus\alpha_n$ est le plus petit ordinal
 strictement supérieur à tous les
 $\alpha_1\boxplus\cdots\boxplus\beta_i\boxplus
 \cdots\boxplus\alpha_n$, où exactement un des $\alpha_i$ a été
 remplacé par un ordinal $\beta_i$ strictement plus petit
-(généralisation de la définition au cas de $n$ termes).
+(généralisation de la définition au cas de $n$ termes, analogue à un
+résultat vu en cours sur les sommes de nim).
 
 \smallskip
 
@@ -406,34 +465,97 @@ Si $\alpha$ est un ordinal et $n\geq 1$ un entier naturel, on
 \boxplus \cdots \boxplus \alpha$ de $n$ fois l'ordinal $\alpha$ (on
 pourra aussi poser $\alpha\boxdot 0 = 0$).  Dans ces conditions, il
 est trivial que $(\alpha\boxdot n) \boxplus (\alpha\boxdot n') =
-\alpha\boxdot (n+n')$.
+\alpha\boxdot (n+n')$ ; par ailleurs, on a $1\boxdot n = n$ d'après la
+question (1).
 
 \medskip
 
-(3) Montrer par induction transfinie sur $\alpha$ que si $\alpha =
-\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où $\gamma_1
-> \cdots > \gamma_r$ sont des ordinaux en ordre strictement
-décroissant et $n_1,\ldots,n_r$ des entiers naturels non nuls ;
-c'est-à-dire qu'il s'agit de la forme normale de Cantor de $\alpha$)
-alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots
-\boxplus (\omega^{\gamma_r} \boxdot n_r)$.
-
-\emph{Indication :} On imitera de près la démonstration du fait donné
-en cours que si $\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$ (où
-$\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre strictement
-décroissant ; c'est-à-dire qu'il s'agit de la l'écriture binaire
-de $\alpha$) alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus
-2^{\gamma_r}$.  Il n'y a pas grand-chose à modifier à part remplacer
-$\mex$ par $\sup^+$ aux endroits utiles.  (Cette question est un peu
-longue, mais il est possible de traiter la suite en l'admettant.)
+Considérons l'affirmation suivante :
+
+{\narrower\noindent\leavevmode\llap{(*) }si $\alpha =
+  \omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où
+  $\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre
+  strictement décroissant et $n_1,\ldots,n_r$ des entiers naturels non
+  nuls ; c'est-à-dire qu'il s'agit de la forme normale de Cantor
+  de $\alpha$), alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1)
+  \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot n_r)$\par}
+
+\noindent (ceci est à comparer au fait, démontré en cours, que si
+$\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$, où $\gamma_1 > \cdots
+> \gamma_r$ sont des ordinaux en ordre strictement décroissant,
+c'est-à-dire qu'il s'agit de l'écriture binaire de $\alpha$, alors on
+a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus 2^{\gamma_r}$).
+
+On pourrait démontrer (*) par induction transfinie sur $\alpha$.
+Comme c'est un peu fastidieux au niveau des notations, on va se
+contenter d'un cas représentatif :
 
 \medskip
 
-(4)(a) En déduire la manière dont on calcule $\alpha\boxplus\beta$ à
-partir des formes normales de Cantor de
-$\alpha$ et $\beta$.\quad(b) En particulier, calculer
-$(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) +
-(\omega+1)$.
+(3)(a) Si $n_1 \geq 1$, expliquer pourquoi $(\omega\boxdot n_1)
+\boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' :
+n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\, \{(\omega\boxdot
+n_1) \boxplus n_0' : n'_0 < n_0\}\big)$.\quad (b) Montrer par
+induction transfinie sur $\alpha$ que si $\alpha = \omega\, n_1 + n_0$
+où $n_0,n_1 \in \mathbb{N}$, alors $\alpha = (\omega \boxdot n_1)
+\boxplus n_0$.
+
+\begin{corrige}
+(a) D'après ce qu'on a admis ci-dessus, $(\omega\boxdot n_1) \boxplus
+  n_0$, qui est une somme naturelle de $n_1$ copies de $\omega$ et
+  $n_0$ fois $1$, est le plus petit ordinal strictement supérieur à
+  toutes les sommes naturelles obtenues en remplaçant un
+  des ($n_1+n_0$) termes par un terme strictement plus petit,
+  c'est-à-dire à tous les $(\omega\boxdot (n_1-1)) \boxplus b \boxplus
+  n_0$ pour $b<\omega$ et à $(\omega\boxdot n_1) \boxplus (n_0-1)$.
+  En se rappelant que $b \oplus n_0 = b + n_0$ (qui prend donc toutes
+  les valeurs $\geq n_0$) et qu'on a le droit d'insérer dans un
+  ensemble dont on prend le $\sup^+$ des nouveaux éléments qui sont
+  majorés par des éléments déjà dedans (et comme $\boxplus$ est
+  croissante en chaque variable d'après (2)(c)), on peut écrire
+  $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot
+  n'_1) \boxplus n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\}
+  \cup\, \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$
+  comme annoncé.
+
+(b) On procède par induction transfinie sur $\alpha = \omega n_1 +
+  n_0$.  On veut montrer que $\alpha = (\omega \boxdot n_1) \boxplus
+  n_0$.  Or, d'après ce qu'on vient de voir, $(\omega\boxdot n_1)
+  \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' :
+  n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\,
+  \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$.  D'après
+  l'hypothèse d'induction, et en utilisant le fait que les formes
+  normales de Cantor des ordinaux se comparent lexicographiquement,
+  ceci vaut encore $\sup^+ \big( \{\omega\, n'_1 + n_0' : n'_1 < n_1
+  \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\, \{\omega\, n_1 + n_0' :
+  n'_0 < n_0\}\big)$, qui est bien $\omega n_1 + n_0$ comme souhaité.
+\end{corrige}
+
+\medskip
+
+(4)(a) On admet maintenant l'affirmation (*) en toute généralité.  En
+déduire la manière dont on calcule $\alpha\boxplus\beta$ à partir des
+formes normales de Cantor de $\alpha$ et $\beta$.\quad(b) En
+particulier, calculer $(\omega+1)\boxplus(\omega+1)$, et comparer avec
+$(\omega+1) + (\omega+1)$.
+
+\begin{corrige}
+(a) En utilisant (*), on peut remplacer l'écriture en forme normale de
+  Cantor $\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ par
+  l'écriture analogue $(\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots
+  \boxplus (\omega^{\gamma_r} \boxdot n_r)$ pour l'addition
+  naturelle ; en faisant ceci pour les deux ordinaux à ajouter, en
+  regroupant les puissances égales de $\omega$ et en convertissant de
+  nouveau en forme normale de Cantor (pour l'addition usuelle), on a
+  montré que la somme naturelle se fait en ajoutant simplement terme à
+  terme les formes normales de Cantor, i.e., on ajoute les chiffres
+  (=coefficients) de chaque puissance de $\omega$.
+
+(b) En particulier, $(\omega+1)\boxplus(\omega+1) = \omega\,2 + 2$
+  (qui est aussi $(\omega\boxdot 2)\boxplus 2$ comme on l'a vu), alors
+  que $(\omega+1) + (\omega+1) = \omega + (1+\omega) + 1 = \omega +
+  \omega + 1 = \omega\,2 + 1$.
+\end{corrige}
 
 \medskip
 
@@ -450,10 +572,37 @@ possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$
 avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu.
 
 Montrer que, dans ce jeu, Blaise possède une stratégie gagnante
-lorsque $\rho > \alpha\boxplus\beta$, que Roxane possède une stratégie
-gagnante lorsque $\rho < \alpha\boxplus\beta$, et que le second joueur
+lorsque $\rho < \alpha\boxplus\beta$, que Roxane possède une stratégie
+gagnante lorsque $\rho > \alpha\boxplus\beta$, et que le second joueur
 possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$.
 
+\begin{corrige}
+On procède par induction transfinie (sur
+$\alpha\boxdot\beta\boxdot\rho$, si l'on veut) : on peut supposer la
+conclusion déjà connue pour tous les $(\alpha',\beta,\rho)$,
+$(\alpha,\beta',\rho)$ et $(\alpha,\beta,\rho')$ tels que dans la
+question.
+
+Si Blaise joue en premier : si $\rho < \alpha\boxplus\beta$, alors par
+définition de $\alpha\boxplus\beta$, il existe un
+$\alpha'\boxplus\beta$ avec $\alpha'<\alpha$ ou $\alpha\boxplus\beta'$
+avec $\beta'<\beta$ qui majore $\rho$ (au sens large), et Blaise peut
+faire le coup correspondant $(\alpha',\beta,\rho)$ ou
+$(\alpha,\beta',\rho)$ auquel cas il aura une stratégie gagnante par
+hypothèse d'induction ; si $\rho \geq \alpha\boxplus\beta$, alors quel
+que soit le coup $(\alpha',\beta,\rho)$ ou $(\alpha,\beta',\rho)$ fait
+par Blaise, on aura $\rho > \alpha'\boxplus\beta$ ou $\rho >
+\alpha\boxplus\beta'$ donc Roxane aura une stratégie gagnante.
+
+Si Roxane joue en premier : si $\rho > \alpha\boxplus\beta$, alors
+elle peut jouer vers $(\alpha,\beta,\rho')$ avec $\rho' =
+\alpha\boxplus\beta$, auquel cas elle aura une stratégie gagnante par
+hypothèse d'induction.  Si $\rho \leq \alpha\boxplus\beta$, alors quel
+que soit le coup qu'elle fait, elle arrivera à un
+$(\alpha,\beta,\rho')$ avec $\rho' < \alpha\boxplus\beta$ auquel cas
+Blaise a une stratégie gagnante par hypothèse d'induction.
+\end{corrige}
+
 
 %
 %