diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 376 |
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 |