Add an exercise section (with the exercises on ordinals already written separately).

1 files changed, 376 insertions, 0 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index ec5c1e1..9f9f8ca 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -29,6 +29,8 @@
 \newtheorem{comcnt}{Tout}[subsection]
 \newcommand\thingy{%
 \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
 \newtheorem{defn}[comcnt]{Définition}
 \newtheorem{prop}[comcnt]{Proposition}
 \newtheorem{lem}[comcnt]{Lemme}
@@ -60,6 +62,15 @@
 \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\relax\else\egroup\fi\par}
+%
 \newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}}
 %
 %
@@ -5198,6 +5209,371 @@ où Roxane commence (exactement analogue : Roxane choisit $(x_0,x_1)
 %
 %
 
+\section{Exercices}\label{section-exercises}
+
+\subsection{Introduction et typologie}
+
+\subsection{Jeux en forme normale}
+
+\subsection{Jeux de Gale-Stewart et détermination}
+
+\subsection{Théorie de l'induction bien-fondée}
+
+\subsection{Introduction aux ordinaux}
+
+\exercice
+
+Ranger les ordinaux suivants par ordre croissant :
+\spaceout $\omega^{\omega+1} + \omega^\omega\cdot 33$ ;
+\spaceout $\omega\cdot 3 + 42$ ;
+\spaceout $\omega^{\omega+1} + \omega + 33$ ;
+\spaceout $\omega^{\omega+2} + \omega^\omega$ ;
+\spaceout $\omega^2\cdot 42 + 1000$ ;
+\spaceout $\omega^2 + \omega$ ;
+\spaceout $\omega^2\cdot 42 + \omega$ ;
+\spaceout $\omega^{\omega^2 + 1}$ ;
+\spaceout $\omega^{\omega^{(\omega\cdot 2)}}$ ;
+\spaceout $\omega^{\omega^\omega} + 1$ ;
+\spaceout $\omega^{\omega+1} + \omega\cdot 33$ ;
+\spaceout $\omega^{\omega^2}$ ;
+\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega\cdot 2}\cdot 1000$ ;
+\spaceout $\omega^{\omega^2 + \omega}$ ;
+\spaceout $\omega\cdot 3$ ;
+\spaceout $\omega^{(\omega^\omega\cdot 2)}$ ;
+\spaceout $\omega^{\omega^3}$ ;
+\spaceout $\omega^{\omega+1} + 1000$ ;
+\spaceout $\omega^{\omega+2}$ ;
+\spaceout $\omega^{\omega+1}\cdot 2$ ;
+\spaceout $\omega\cdot 2 + 1729$ ;
+\spaceout $\omega^2 + 1000$ ;
+\spaceout $42$ ;
+\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2 + 1}$ ;
+\spaceout $\omega^{\omega\cdot 2}\cdot 1000$ ;
+\spaceout $\omega^2\cdot 42$ ;
+\spaceout $\omega^{\omega+1} + \omega^2\cdot 33$ ;
+\spaceout $\omega^2$ ;
+\spaceout $\omega$ ;
+\spaceout $\omega^{\omega+1}$ ;
+\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega^2}\cdot 42$ ;
+\spaceout $\omega^{\omega\cdot 2} + \omega^{\omega+2}$ ;
+\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2} + \omega^{\omega+1}$ ;
+\spaceout $\omega^{\omega^{(\omega^2)}}$ ;
+\spaceout $\omega^{\omega^2 + 1}\cdot 2$ ;
+\spaceout $\omega^2 + \omega\cdot 42$ ;
+\spaceout $\omega + 42$ ;
+\spaceout $\omega^{\omega^2\cdot 2}$ ;
+\spaceout $\omega^{\omega\cdot 2 + 42}$ ;
+\spaceout $\omega^{\omega\cdot 2}$ ;
+\spaceout $\omega\cdot 2$ ;
+\spaceout $\omega^{\omega+1} + \omega^2 + 33$ ;
+\spaceout $\omega^{\omega^{(\omega+1)}}$ ;
+\spaceout $\omega^\omega$ ;
+\spaceout $\omega^{\omega^2 + \omega + 1}$ ;
+\spaceout $\omega^{\omega^\omega}\cdot 2$ ;
+\spaceout $\omega^{\omega^\omega}$ ;
+\spaceout $0$ ;
+\spaceout $\omega^{\omega^2} + \omega^{\omega+1}$ ;
+\spaceout $\omega^{(\omega^\omega + 1)}$.
+
+\begin{corrige}
+On vérifie que tous ces ordinaux sont écrits en forme normale de
+Cantor (et les exposants de $\omega$ aussi, etc.).  On les compare
+donc en comparant à chaque fois la plus grande puissance de $\omega$.
+
+Dans l'ordre croissant : \spaceout $0$ ;
+\spaceout $42$ ;
+\spaceout $\omega$ ;
+\spaceout $\omega + 42$ ;
+\spaceout $\omega\cdot 2$ ;
+\spaceout $\omega\cdot 2 + 1729$ ;
+\spaceout $\omega\cdot 3$ ;
+\spaceout $\omega\cdot 3 + 42$ ;
+\spaceout $\omega^2$ ;
+\spaceout $\omega^2 + 1000$ ;
+\spaceout $\omega^2 + \omega$ ;
+\spaceout $\omega^2 + \omega\cdot 42$ ;
+\spaceout $\omega^2\cdot 42$ ;
+\spaceout $\omega^2\cdot 42 + 1000$ ;
+\spaceout $\omega^2\cdot 42 + \omega$ ;
+\spaceout $\omega^\omega$ ;
+\spaceout $\omega^{\omega+1}$ ;
+\spaceout $\omega^{\omega+1} + 1000$ ;
+\spaceout $\omega^{\omega+1} + \omega + 33$ ;
+\spaceout $\omega^{\omega+1} + \omega\cdot 33$ ;
+\spaceout $\omega^{\omega+1} + \omega^2 + 33$ ;
+\spaceout $\omega^{\omega+1} + \omega^2\cdot 33$ ;
+\spaceout $\omega^{\omega+1} + \omega^\omega\cdot 33$ ;
+\spaceout $\omega^{\omega+1}\cdot 2$ ;
+\spaceout $\omega^{\omega+2}$ ;
+\spaceout $\omega^{\omega+2} + \omega^\omega$ ;
+\spaceout $\omega^{\omega\cdot 2}$ ;
+\spaceout $\omega^{\omega\cdot 2} + \omega^{\omega+2}$ ;
+\spaceout $\omega^{\omega\cdot 2}\cdot 1000$ ;
+\spaceout $\omega^{\omega\cdot 2 + 42}$ ;
+\spaceout $\omega^{\omega^2}$ ;
+\spaceout $\omega^{\omega^2} + \omega^{\omega+1}$ ;
+\spaceout $\omega^{\omega^2 + 1}$ ;
+\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega\cdot 2}\cdot 1000$ ;
+\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega^2}\cdot 42$ ;
+\spaceout $\omega^{\omega^2 + 1}\cdot 2$ ;
+\spaceout $\omega^{\omega^2 + \omega}$ ;
+\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2} + \omega^{\omega+1}$ ;
+\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2 + 1}$ ;
+\spaceout $\omega^{\omega^2 + \omega + 1}$ ;
+\spaceout $\omega^{\omega^2\cdot 2}$ ;
+\spaceout $\omega^{\omega^3}$ ;
+\spaceout $\omega^{\omega^\omega}$ ;
+\spaceout $\omega^{\omega^\omega} + 1$ ;
+\spaceout $\omega^{\omega^\omega}\cdot 2$ ;
+\spaceout $\omega^{(\omega^\omega + 1)}$ ;
+\spaceout $\omega^{(\omega^\omega\cdot 2)}$ ;
+\spaceout $\omega^{\omega^{(\omega+1)}}$ ;
+\spaceout $\omega^{\omega^{(\omega\cdot 2)}}$ ;
+\spaceout et enfin\spaceout $\omega^{\omega^{(\omega^2)}}$.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+(a) Que vaut $(\omega+1) + (\omega+1)$ ?
+
+(b) Plus généralement, que vaut $(\omega+1) + \cdots + (\omega+1)$
+avec $n$ termes $\omega+1$ (où $n$ est un entier naturel $\geq 1$) ?
+
+(c) En déduire ce que vaut $(\omega+1)\cdot n$.
+
+(d) En déduire ce que vaut $(\omega+1)\cdot \omega$.
+
+(e) En déduire ce que vaut $(\omega+1)\cdot(\omega+1)$.
+
+(f) En déduire ce que vaut $(\omega+1)^2$.
+
+\begin{corrige}
+(a) On a $(\omega+1) + (\omega+1) = \omega + 1 + \omega + 1 = \omega +
+  (1 + \omega) + 1 = \omega + \omega + 1 = \omega\cdot 2 + 1$.
+
+(b) En procédant de même, on voit que dans la somme de $n$ termes
+  $\omega + 1$, chaque $1$ est absorbé par le $\omega$ qui
+  \emph{suit}, sauf le dernier $1$ qui demeure : la somme vaut
+  donc $\omega\cdot n + 1$.
+
+(c) Quel que soit l'ordinal $\alpha$, la somme $\alpha + \cdots +
+  \alpha$ avec $n$ termes $\alpha$ vaut $\alpha\cdot n$ (ceci se voit
+  soit par une récurrence immédiate sur $n$ avec la définition par
+  induction de la multiplication, soit en utilisant la distributivité
+  à droite, c'est-à-dire $\alpha\cdot n = \alpha\cdot(1 + \cdots + 1)
+  = \alpha + \cdots + \alpha$).  On a donc $(\omega+1)\cdot n =
+  \omega\cdot n + 1$.
+
+(d) L'ordinal $(\omega+1)\cdot \omega$ est donc la limite
+  (c'est-à-dire la borne supérieure) des $(\omega+1)\cdot n =
+  \omega\cdot n + 1$ pour $n\to\omega$.  Cette borne supérieure
+  vaut $\omega^2$ : en effet, $\omega^2 \geq \omega\cdot n + 1$ pour
+  chaque $n<\omega$, mais inversement, si $\gamma < \omega^2$, on a
+  $\gamma < \omega\cdot n$ pour un certain $n$ (par exemple en
+  utilisant le fait que $\omega^2 = \omega\cdot\omega$ est elle-même
+  la limite des $\omega\cdot n$, c'est-à-dire le plus petit ordinal
+  supérieur ou égal à eux), et en particulier $\gamma < \omega\cdot n
+  + 1$ ; ou, si on préfère, quel que soit $n$ on a $\omega\cdot n \leq
+  \omega\cdot n + 1 \leq \omega\cdot (n + 1)$ où $\omega\cdot n$ et
+  $\omega\cdot (n+1)$ ont la même limite $\omega^2$ quand
+  $n\to\omega$, d'où il résulte que $\omega\cdot n + 1$ aussi.
+
+(e) On a $(\omega+1)\cdot (\omega+1) = (\omega+1)\cdot \omega +
+  (\omega + 1) = \omega^2 + \omega + 1$.
+
+(f) On a toujours $\alpha^2 = \alpha\cdot\alpha$, donc $(\omega+1)^2 =
+  \omega^2 + \omega + 1$ comme on vient de le montrer.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+(a) Que vaut $(\omega 2) \cdot (\omega 2)$ ?
+
+(b) Plus généralement, que vaut $(\omega 2) \cdots (\omega 2)$ avec
+$n$ facteurs $\omega 2$ (où $n$ est un entier naturel $\geq 1$) ?
+
+(c) En déduire ce que vaut $(\omega 2)^n$.
+
+(d) En déduire ce que vaut $(\omega 2)^\omega$.  Comparer avec
+$\omega^\omega \cdot 2^\omega$.
+
+(e) En déduire ce que vaut $(\omega 2)^{\omega+n}$ pour $n\geq 1$
+entier naturel.
+
+(f) En déduire ce que vaut $(\omega 2)^{\omega 2}$.
+
+\begin{corrige}
+(a) On a $(\omega 2) \cdot (\omega 2) = \omega \cdot 2 \cdot \omega
+  \cdot 2 = \omega \cdot (2 \cdot \omega) \cdot 2 = \omega \cdot
+  \omega \cdot 2 = \omega^2 \cdot 2$.
+
+(b) En procédant de même, on voit que dans le produit de $n$ facteurs
+  $\omega 2$, chaque $2$ est absorbé par le $\omega$ qui \emph{suit},
+  sauf le dernier $2$ qui demeure : le produit vaut donc $\omega^n
+  \cdot 2$.
+
+(c) Quel que soit l'ordinal $\alpha$, le produit $\alpha \cdots
+  \alpha$ avec $n$ facteurs $\alpha$ vaut $\alpha^n$ (ceci se voit
+  soit par une récurrence immédiate sur $n$ avec la définition par
+  induction de l'exponentiation, soit en écrivant $\alpha^n =
+  \alpha^{1+\cdots+1} = \alpha \cdots \alpha$).  On a donc $(\omega
+  2)^n = \omega^n \cdot 2$.
+
+(d) L'ordinal $(\omega 2)^\omega$ est la limite (c'est-à-dire la borne
+  supérieure) des $\omega^n \cdot 2$ pour $n\to\omega$.  Cette borne
+  supérieure vaut $\omega^\omega$ : en effet, $\omega^\omega \geq
+  \omega^n \cdot 2$ pour chaque $n<\omega$, mais inversement, si
+  $\gamma < \omega^\omega$, on a $\gamma < \omega^n$ pour un
+  certain $n$ (par exemple en utilisant le fait que $\omega^\omega$
+  est lui-même la limite des $\omega^n$, c'est-à-dire le plus petit
+  ordinal supérieur ou égal à eux), et en particulier $\gamma <
+  \omega^n \cdot 2$ ; ou, si on préfère, quel que soit $n$ on a
+  $\omega^n \leq \omega^n \cdot 2 \leq \omega^{n+1}$ où $\omega^n$ et
+  $\omega^{n+1}$ ont la même limite $\omega^\omega$ quand
+  $n\to\omega$, d'où il résulte que $\omega^n \cdot 2$ aussi.
+
+  Bref, $(\omega 2)^\omega = \omega^\omega$.  En revanche,
+  $\omega^\omega \cdot 2^\omega = \omega^\omega \cdot \omega =
+  \omega^{\omega+1}$ est strictement plus grand.
+
+(e) On a $(\omega 2)^{\omega + n} = (\omega 2)^\omega \cdot (\omega
+  2)^n = \omega^\omega \cdot \omega^n \cdot 2$ d'après les questions
+  précédentes, donc ceci vaut $\omega^{\omega+n} \cdot 2$.
+
+(f) L'ordinal $(\omega 2)^{\omega 2}$ est la limite des
+  $\omega^{\omega+n} \cdot 2$ pour $n\to\omega$, et le même
+  raisonnement qu'en (d) montre que cette limite est
+  $\omega^{\omega+\omega} = \omega^{\omega 2}$.  Bref, $(\omega
+  2)^{\omega 2} = \omega^{\omega 2}$.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+On dit qu'un ordinal $\alpha$ est \textbf{infini} lorsque
+$\alpha\geq\omega$.  Montrer qu'un ordinal est infini si et seulement
+si $1+\alpha = \alpha$.
+
+\begin{corrige}
+Si $\alpha$ est infini, on a $\alpha \geq \omega$, donc il existe un
+unique ordinal $\beta$ tel que $\alpha = \omega + \beta$.  On a alors
+$1 + \alpha = 1 + (\omega + \beta) = (1 + \omega) + \beta = \omega +
+\beta = \alpha$.
+
+Si, en revanche, $\alpha$ est fini, c'est-à-dire $\alpha < \omega$,
+alors $\alpha$ est un entier naturel, et comme l'addition ordinale sur
+les entiers naturels coïncide avec l'addition usuelle sur ceux-ci, on
+a $1 + \alpha > \alpha$.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+On rappelle que si $\alpha' \geq \alpha$ sont deux ordinaux, il existe
+un unique $\beta$ tel que $\alpha' = \alpha + \beta$.\spaceout (a) En
+déduire que si $\gamma < \gamma'$ alors $\omega^\gamma +
+\omega^{\gamma'} = \omega^{\gamma'}$ (on pourra utiliser la conclusion
+de l'exercice précédent).\spaceout (b) Expliquer pourquoi
+$\omega^{\gamma'} + \omega^\gamma$, lui, est strictement plus grand
+que $\omega^{\gamma'}$ et $\omega^\gamma$.
+
+\begin{corrige}
+(a) Si $\gamma < \gamma'$, il existe $\beta$ tel que $\gamma' = \gamma
+  + \beta$, si bien qu'on a $\omega^\gamma + \omega^{\gamma'} =
+  \omega^\gamma + \omega^{\gamma + \beta} = \omega^\gamma +
+  \omega^\gamma \cdot \omega^\beta = \omega^\gamma (1 +
+  \omega^\beta)$.  La conclusion voulue découle donc du fait que $1 +
+  \omega^\beta = \omega^\beta$ : or ceci résulte de l'exercice
+  précédent (on a $\beta \neq 0$ puisque $\gamma' \neq \gamma$, donc
+  $\beta \geq 1$, donc $\omega^\beta \geq \omega$).
+
+(b) On a $\omega^\gamma > 0$ donc $\omega^{\gamma'} + \omega^\gamma >
+  \omega^{\gamma'}$ (par stricte croissance de la somme en la variable
+  de droite), et comme $\omega^{\gamma'} > \omega^\gamma$, la somme
+  est également $> \omega^\gamma$.  (On pouvait aussi invoquer la
+  comparaison des formes normales de Cantor.)
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercice
+
+(A) (1) Que vaut $2^{\omega+1}$ ?\spaceout (2) Que vaut
+$2^{\omega^2}$ ?\spaceout (3) Expliquer pourquoi $\omega^\omega =
+\omega\cdot \omega^\omega$.  En déduire ce que vaut
+$2^{\omega^\omega}$.\spaceout (À chaque fois, on écrira les ordinaux
+demandés en forme normale de Cantor.)
+
+(B) On suppose que $\varepsilon = \omega^\varepsilon$.\spaceout
+(1) Que vaut $\varepsilon^\varepsilon$ ?\spaceout (2) Que vaut
+$\varepsilon^{\varepsilon^\varepsilon}$ (on pourra utiliser un des
+deux exercices précédents) ?\spaceout (À chaque fois, plusieurs
+écritures sont possibles.)
+
+\begin{corrige}
+(A) (1) On a $2^{\omega+1} = 2^\omega\cdot 2^1 = \omega\cdot
+  2$.\spaceout (2) On a $2^{\omega^2} = 2^{\omega\cdot\omega} =
+  (2^\omega)^\omega = \omega^\omega$.\spaceout (3) On a $\omega\cdot
+  \omega^\omega = \omega^1 \cdot \omega^\omega = \omega^{1+\omega} =
+  \omega^\omega$.  On en déduit que $2^{\omega^\omega} =
+  2^{\omega\cdot \omega^\omega} = (2^\omega)^{\omega^\omega} =
+  \omega^{\omega^\omega}$.
+
+(B) (1) On a $\varepsilon^\varepsilon =
+  (\omega^\varepsilon)^\varepsilon = \omega^{\varepsilon^2}$ ou, si on
+  préfère, $\omega^{\omega^{\varepsilon\cdot 2}}$.\spaceout  (2) On a
+  $\varepsilon^{\varepsilon^\varepsilon} =
+  (\omega^\varepsilon)^{\varepsilon^\varepsilon} = \omega^{\varepsilon
+    \cdot \varepsilon^\varepsilon} = \omega^{\varepsilon^{1 +
+      \varepsilon}}$.  Or $1 + \varepsilon = \varepsilon$ d'après un
+  des exercices précédents (parce que $\varepsilon$ est infini ou
+  parce que la somme est $\omega^0 + \omega^\varepsilon$), donc
+  $\varepsilon^{\varepsilon^\varepsilon} =
+  \omega^{\varepsilon^\varepsilon}$.  D'après la sous-question
+  précédente, c'est aussi $\omega^{\omega^{\varepsilon^2}}$ ou encore
+  $\omega^{\omega^{\omega^{\varepsilon\cdot 2}}}$.
+\end{corrige}
+
+%
+%
+%
+
+\subsection{Jeux combinatoires impartiaux à information parfaite}
+
+\subsection{Notions sur les combinatoires partisans à information parfaite}
+
+
+
+%
+%
+%
+
 \printindex