Write answer to fourth exercise.

1 files changed, 193 insertions, 34 deletions

diff --git a/controle-20250626.tex b/controle-20250626.tex
index 80dee86..4205a47 100644
--- a/controle-20250626.tex
+++ b/controle-20250626.tex
@@ -650,8 +650,8 @@ On se propose dans cet exercice de montrer qu'il existe une partie $A
 joueurs n'ait de stratégie gagnante).
 
 (La démonstration a été découpées en questions admettant des réponses
-très courtes, parfois d'une seule ligne.  Aucune ne demande de
-raisonnement compliqué.)
+courtes, parfois d'une seule ligne.  Aucune ne demande de raisonnement
+très compliqué.)
 
 \textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$
 (resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble
@@ -660,6 +660,26 @@ des stratégies d'Alice (resp. de Bob) au jeu $G(A)$.
 une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est
 à Alice, resp. à Bob, de jouer.)
 
+\begin{corrige}
+L'ensemble $P_{\mathrm{A}}$ des positions où c'est à Alice de jouer
+sont les suites binaires finies de longueur paires : on peut les
+énumérer dans l'ordre de longueur et, pour chaque longueur, dans
+l'ordre lexicographique ($()$, $00$, $01$, $10$, $11$, $0000$, $0001$,
+$0010$, etc.).  Ceci fournit une bijection $g_{\mathrm{A}}\colon
+\mathbb{N} \to P_{\mathrm{A}}$ : on en déduit une bijection
+$h_{\mathrm{A}}\colon \{0,1\}^{P_{\mathrm{A}}} \to
+\{0,1\}^{\mathbb{N}}$ par $h_{\mathrm{A}}(u) = (n \mapsto
+u(g_{\mathrm{A}}(n)))$.  Or $\{0,1\}^{P_{\mathrm{A}}}$ est exactement
+l'ensemble des stratégies d'Alice (ce sont les fonctions qui à une
+position où c'est à Alice de jouer associent un coup d'Alice).
+
+Exactement le même raisonnement fournit le résultat pour
+$h_{\mathrm{B}}$ : il faut simplement considérer cette fois l'ensemble
+$P_{\mathrm{B}}$ des positions où c'est à Bob de jouer, qui sont les
+suites binaires finies de longueur paires ($0$, $1$, $000$, $001$,
+etc.).
+\end{corrige}
+
 \textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut
 montrer qu'il existe une relation de bon ordre sur n'importe quel
 ensemble (théorème du bon ordre).} qu'il existe une relation de bon
@@ -670,20 +690,63 @@ l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont
 deux à deux distincts et $\{u_\xi : \xi < \gamma\} =
 \{0,1\}^{\mathbb{N}}$).
 
+\begin{corrige}
+Soit $W$ l'ensemble $\{0,1\}^{\mathbb{N}}$ muni du bon ordre $\preceq$
+qu'on a supposé exister, et soit $\gamma = \#W$ son ordinal.  À tout
+élément $w$ de $W$ on associe un ordinal $\#w$ qui est l'ordinal de
+l'ensemble $\{x \in W : x \prec w\}$ des prédécesseurs stricts
+de $w$ : ceci constitue une bijection strictement croissante entre $W$
+et l'ensemble $\{\xi < \gamma\}$ des ordinaux $<\gamma$ ; on appelle
+alors $\xi \mapsto u_\xi$ la bijection réciproque.
+
+(Si on préfère : l'ordinal de $W$ est le même que l'ordinal de $\{\xi
+< \gamma\}$, à savoir $\gamma$, donc il y a une — unique — bijection
+croissante entre les deux, et on appelle $\xi \mapsto u_\xi$ sa
+réciproque.)
+\end{corrige}
+
 \textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit
 ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$
 de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$
 sur l'ensemble $\{0,1\}^{\mathbb{N}}$.
 
-\textbf{Définition :} On notera $\mathfrak{c}$ l'ordinal dont on vient
-de justifier l'existence (i.e., le plus petit $\gamma$ tel qu'on
-puisse écrire $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour
-une certaine fonction $\xi \mapsto u_\xi$).
+\begin{corrige}
+En une ligne : on vient de montrer qu'un tel $\gamma$ existe, donc il
+y en a un plus petit.
+
+(En un tout petit peu plus détaillé : comme les ordinaux sont
+bien-ordonnés, dès qu'il existe un ordinal tel que (quelque chose),
+alos il y en a un plus petit ; or il existe un ordinal tel que $\{\xi
+< \gamma\}$ se surjecte sur $\{0,1\}^{\mathbb{N}}$ — on vient de voir
+l'existence d'une telle bijection —, donc il en existe un plus petit.)
+\end{corrige}
+
+\textbf{Définition :} On notera\footnote{Il s'agit ici d'un ‘c’
+gothique (cet ordinal s'appelle le « cardinal du continu ») ; si on ne
+veut pas écrire de ‘c’ gothique on pourra, par exemple, faire un ‘c’
+souligné.}  $\mathfrak{c}$ l'ordinal dont on vient de justifier
+l'existence (i.e., le plus petit $\gamma$ tel qu'on puisse écrire
+$\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour une certaine
+fonction $\xi \mapsto u_\xi$).
+
+\textbf{(4)} \textbf{(a)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments
+quelconques de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$,
+expliquer en une ligne pourquoi il existe un élément $x$ de
+$\{0,1\}^{\mathbb{N}}$ différent de tous
+les $v_\xi$.\quad\textbf{(b)} Si $w$ est encore un élément de
+$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut aussi trouver $x$
+différent de $w$.
 
-\textbf{(4)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments quelconques
-de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, expliquer en
-une ligne pourquoi il existe un élément de $\{0,1\}^{\mathbb{N}}$
-différent de tous les $v_\xi$.
+\begin{corrige}
+\textbf{(a)} En une ligne : $\xi \mapsto v_\xi$ n'est pas surjective
+par minimalité de $\mathfrak{c}$.
+
+\textbf{(b)} Si $\alpha$ est fini, il est évident qu'on peut trouver
+$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini).
+Si $\alpha$ est infini, alors $\alpha = 1 + \alpha$ donc on n'a qu'à
+poser $v'_0 = w$ et $v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et
+appliquer (a).
+\end{corrige}
 
 \textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu
 $G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la
@@ -692,41 +755,82 @@ simplement les termes successifs de $y$ (indépendamment de ce que fait
 Alice ; i.e., $\sigma \ast y$ est une suite binaire dont la suite des
 termes impairs, ceux joués par Bob, est donnée par $y$, tandis
 qu'Alice joue les termes pairs selon la stratégie $\sigma$).
+Symétriquement, si $\tau$ est une stratégie de Bob et $z \in
+\{0,1\}^{\mathbb{N}}$, on définit $z \ast \tau$ comme la confrontation
+dans laquelle Alice joue les termes de la suite $z$ et Bob joue
+selon $\tau$.
 
 \textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une
 ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de
 $\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective.
 
+\begin{corrige}
+En une ligne : si $\sigma \ast y = \sigma \ast y'$, ils ont les mêmes
+termes impairs, donc $y = y'$.
+
+(Si on préfère : $y$ se retrouve à partir de $\sigma \ast y$ comme la
+suite de ses termes impairs.)
+\end{corrige}
+
 \textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques
-de $\{0,1\}^{\mathbb{N}}$ où $\alpha < \mathfrak{c}$, déduire de
-(4) et (5) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
+de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire de
+(4)(a) et (5) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
 $\sigma \ast y$ soit différent de tous les $a_\xi$.
 
-\textbf{Supposition :} Dans les questions (7) à (8), on suppose que
+\begin{corrige}
+Pour chaque $\xi < \alpha$, si $a_\xi$ est de la forme $\sigma \ast
+v$, appelons $v_\xi$ le $v$ en question (qui est unique d'après (5)),
+et sinon, soit $v_\xi$ quelconque (par exemple la suite nulle).  (Ou,
+si on préfère, on peut appeler $v_\xi$ la suite des termes impairs
+de $a_\xi$.)  D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$
+qui est différent de tous les $v_\xi$ pour $\xi < \alpha$.  Alors
+$\sigma \ast y$ ne peut pas être égal à $a_\xi$, car si c'était le
+cas, c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast
+v_\xi = \sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la
+définition de $y$.
+\end{corrige}
+
+\textbf{Supposition :} Dans les questions (7) à (9), on suppose que
 $(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et
 $(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob.  On les
-définira après la question (8), mais on n'a pas besoin d'en savoir
+définira après la question (9), mais on n'a pas besoin d'en savoir
 plus pour l'instant.
 
 \textbf{(7)} En supposant préalablement définis des éléments
 $(a_\xi)_{\xi<\alpha}$ et $(b_\xi)_{\xi<\alpha}$ de
-$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire des
-questions précédentes qu'il existe $b_\alpha$ qui soit de la forme
-$\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$),
-mais qui soit différent de tous les $a_\xi$ ; et, symétriquement,
-qu'il existe $a_\alpha$ qui soit de la forme $z \ast \tau_\alpha$
-(pour un certain $z \in \{0,1\}^{\mathbb{N}}$), mais différent de tous
-les $b_\xi$.
+$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire en une
+ligne des questions précédentes qu'il existe $b_\alpha$ qui soit de la
+forme $\sigma_\alpha \ast y$ (pour un certain $y \in
+\{0,1\}^{\mathbb{N}}$), mais qui soit différent de tous les $a_\xi$.
+Expliquer pourquoi il existe $a_\alpha$ aussi qui soit de la forme $z
+\ast \tau_\alpha$ (pour un certain $z \in \{0,1\}^{\mathbb{N}}$), mais
+différent de tous les $b_\xi$ pour $\xi<\alpha$ mais aussi du
+$b_\alpha$ qu'on vient de trouver.
+
+\begin{corrige}
+On pose $b_\alpha = \sigma_\alpha \ast y$, où l'existence de $y$ a été
+prouvée en (6) (pour $\sigma = \sigma_\alpha$).
+
+La construction de $a_\alpha$ est symétrique, il n'y a qu'à remarquer
+que $z \mapsto z \ast \tau$ est injective, car si $z \ast \tau = z'
+\ast \tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le
+reste est presque pareil.  La seule chose qui diffère est qu'on a un
+élément de plus à éviter ($b_\alpha$), mais la question (4)(b) donne
+justement ce point
+\end{corrige}
 
 On \emph{admettra} qu'il ne pose pas de problème pour
 choisir\footnote{Ceci constitue une utilisation de l'axiome du choix
 (qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la
-question (2)).}  de tels $a_\alpha$ et $b_\alpha$.
+question (2)).}  de tels $a_\alpha$ et $b_\alpha$ en fonction de tous
+les autres paramètres.
 
 \textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi
   < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que :
 \begin{itemize}
-\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$,
+\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$ (i.e., pour
+  tous $\xi<\mathfrak{c}$ et tout $\zeta<\mathfrak{c}$, on a $a_\xi
+  \neq b_\zeta$),
 \item pour tout $\xi < \mathfrak{c}$, on a $b_\xi = \sigma_\xi \ast y$
   pour un certain $y \in \{0,1\}^{\mathbb{N}}$,
 \item pour tout $\xi < \mathfrak{c}$, on a $a_\xi = z \ast \tau_\xi$
@@ -734,25 +838,80 @@ question (2)).}  de tels $a_\alpha$ et $b_\alpha$.
 \end{itemize}
 (C'est tout ce qu'on aura besoin de savoir pour la suite.)
 
-\textbf{Définitions :} Posons maintenant $\sigma_\xi :=
+\begin{corrige}
+On définit $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi <
+  \mathfrak{c}}$ par induction transfinie sur $\xi$ : si $(a_\xi)_{\xi
+  < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, alors
+on choisit $a_\alpha$ et $b_\alpha$ comme l'existence a été montrée
+en (7).
+
+Pour vérifier le premier point, on distingue les cas $\xi < \zeta$ et
+$\zeta \leq \xi$.  Dans le premier cas, la définition même de
+$b_\zeta$ était d'être différent de tous les $a_\xi$ pour $\xi <
+\zeta$ ; dans le second cas, la définition même de $a_\xi$ était
+d'être différent de tous les $b_\zeta$ pour $\zeta < \xi$ et aussi de
+$b_\xi$.
+
+Les deux points suivants font partie de la définition des $b_\xi$ et
+des $a_\xi$, il n'y a rien de plus à dire.
+\end{corrige}
+
+\textbf{Définition :} Appelons maintenant $A = \{a_\xi : \xi <
+\mathfrak{c}\}$ l'ensemble des $a_\xi$ qu'on vient de construire
+en (8).
+
+\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\tau_\xi$
+n'est pas gagnante pour Bob au jeu $G(A)$.  Montrer que la stratégie
+$\sigma_\xi$ n'est pas gagnante pour Alice à ce même jeu (attention,
+ce n'est pas exactement symétrique vu que $A$ est l'ensemble
+des $a_\alpha$).
+
+\begin{corrige}
+Supposons par l'absurde que la stratégie $\tau_\xi$ soit gagnante pour
+Bob : mais on a vu que $a_\xi = z \ast \tau_\xi$ pour un certain $z$,
+donc $z \ast \tau_\xi$ est dans $A$, c'est-à-dire qu'Alice gagne la
+confrontation, ce qui contredit le fait que $\tau_\xi$ soit gagnante
+pour Bob.
+
+Supposons par l'absurde que la stratégie $\sigma_\xi$ soit gagnante
+pour Alice : mais on a vu que $b_\xi = \sigma_\xi \ast y$ pour un
+certain $y$ ; or $b_\xi$ ne peut pas être dans $A$ car il serait alors
+égal à l'un des $a_\zeta$ et on a vu que ce n'était pas le cas.
+C'est-à-die que Bob gagne la confrontation, ce qui contredit le fait
+que $\sigma_\xi$ soit gagnante pour Bob.
+\end{corrige}
+
+\textbf{Définition :} Posons maintenant $\sigma_\xi :=
 h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et
 $u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
 
-On pose enfin $A = \{a_\xi : \xi < \mathfrak{c}\}$ l'ensemble des
-$a_\xi$ qu'on vient de construire en (8).
+\textbf{(10)} Montrer que ni Alice ni Bob n'ont de stratégie gagnante
+au jeu $G(A)$.
 
-\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie
-$\sigma_\xi$ n'est pas gagnante pour Alice au jeu $G(A)$.  Montrer que
-la stratégie $\tau_\xi$ n'est pas gagnante pour Bob à ce même jeu
-(attention, ce n'est pas exactement symétrique vu que $A$ est
-l'ensemble des $a_\alpha$).
-
-\textbf{(10)} Déduire de tout ce qui précède que ni Alice ni Bob n'ont
-de stratégie gagnante au jeu $G(A)$.
+\begin{corrige}
+La fonction $h_{\mathrm{A}}$ est surjective par définition,
+c'est-à-dire que n'importe quel stratégie d'Alice est de la forme
+$h_{\mathrm{A}}(u)$ pour un certain $u \in \{0,1\}^{\mathbb{N}}$ ;
+mais $\xi \mapsto u_\xi$ est surjective, c'est-à-dire que tout $u \in
+\{0,1\}^{\mathbb{N}}$ est de la forme $u_\xi$ pour un certain $\xi$.
+Autrement dit, n'importe quelle stratégie d'Alice est une des
+$\sigma_\xi$.  Symétriquement, n'importe quelle stratégie de Bob est
+une des $\tau_\xi$.
+
+On vient de voir que ni $\sigma_\xi$ ni $\tau_\xi$ ne peut être une
+stratégie gagnante pour le joueur concerné : donc il n'y a aucune
+stratégie gagnante à ce jeu.
+\end{corrige}
 
 \textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en
 cours ?
 
+\begin{corrige}
+Les résultats du cours concernent les parties ouvertes, fermées, ou
+plus généralemnt boréliennes de $\{0,1\}^{\mathbb{N}}$.  Ici on doit
+conclure que la partie $A$ n'est pas borélienne.
+\end{corrige}
+
 
 
 %