summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-04-04 20:37:26 +0200
committerDavid A. Madore <david+git@madore.org>2019-04-04 20:37:26 +0200
commit40be8c435e5f6dfe1c4b37c03b000924f09ebbe3 (patch)
tree99470565050314e7463edd3c983bb8d652d1bab1
parent8e08c8d40d7e80db19436e14877eb776cc342c3e (diff)
downloadmitro206-40be8c435e5f6dfe1c4b37c03b000924f09ebbe3.zip
mitro206-40be8c435e5f6dfe1c4b37c03b000924f09ebbe3.tar.gz
mitro206-40be8c435e5f6dfe1c4b37c03b000924f09ebbe3.tar.bz2
Write answers to second exercise (and get very much messed up).
-rw-r--r--controle-20190408.tex209
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}
+
%
%