diff options
| -rw-r--r-- | controle-20190408.tex | 209 |
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} + % % |