diff options
Diffstat (limited to 'controle-20250626.tex')
| -rw-r--r-- | controle-20250626.tex | 227 |
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} + % |