diff options
| -rw-r--r-- | notes-mitro206.tex | 49 |
1 files changed, 48 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index b3303a6..8bd781f 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1798,7 +1798,8 @@ Alice. C'est tout simplement qu'on a fait l'hypothèse que \begin{thm}[D. Gale \& F. M. Stewart, 1953]\label{gale-stewart-theorem} Si $A \subseteq X^{\mathbb{N}}$ est ouvert, ou bien fermé, alors le -jeu $G_X(A)$ est déterminé. +jeu $G_X(A)$ (qu'il s'agisse de $G_X^{\mathrm{a}}(A)$ ou +$G_X^{\mathrm{b}}(A)$) est déterminé. \end{thm} \begin{proof}[Première démonstration] Il suffit de traiter le cas ouvert : le cas fermé s'en déduit @@ -1921,6 +1922,52 @@ comme $A$ est ouvert, elle n'appartient pas à $A$, i.e., la confrontation est gagnée par Bob. \end{proof} +\thingy Il ne faut pas croire que l'hypothèse « $A$ est ouvert ou bien + fermé » est anodine : il existe des jeux $G_X^{\mathrm{a}}(A)$ qui +ne sont pas déterminés — autrement dit, même si dans toute +confrontation donnée l'un des deux joueurs gagne, aucun des deux n'a +de moyen systématique de s'en assurer. + +Il ne faut pas croire pour autant que les seuls jeux déterminés soient +ceux définis par une partie ouverte. Par exemple, il est facile de +voir que si $A$ est dénombrable, alors Bob possède une stratégie +gagnante (en effet, si $a = \{a_0,a_1,a_2,a_3,\ldots\}$, alors Bob +peut jouer au premier coup pour exclure $a_0$, c'est-à-dire jouer un +$x_1$ tel que $x_1 \neq a_{0,1}$, puis au second coup pour exclure +$a_1$, c'est-à-dire jouer un $x_3$ tel que $x_3 \neq a_{1,3}$, et +ainsi de suite $x_{2i+1} \neq a_{i,2i+1}$ : il s'agit d'un « argument + diagonal constructif » ; l'argument fonctionne encore, quitte à +décaler les indices, si c'est Bob qui commence). + +Le résultat ci-dessous généralise à la fois le +théorème \ref{gale-stewart-theorem} et ce qu'on vient de dire, et il +assez technique à démontrer : + +\begin{thm}[D. A. Martin, 1975] +Si $A \subseteq X^{\mathbb{N}}$ est \emph{borélien}, c'est-à-dire +appartient à la plus petite partie de $\mathscr{P}(X^{\mathbb{N}})$ +stable par complémentaire et réunions dénombrables (également appelée +« tribu »), alors le jeu $G_X(A)$ est déterminé. +\end{thm} + +(Autrement dit, non seulement un ouvert et un fermé sont déterminés, +mais aussi une intersection dénombrable d'ouverts et une réunion +dénombrable de fermés, ou encore une réunion dénombrable +d'intersections dénombrables d'ouverts et une intersection dénombrable +de réunions dénombrables de fermés, « et ainsi de suite » ; les mots +« et ainsi de suite » glosent ici sur la construction des boréliens, +qui est plus complexe qu'une simple récurrence.) + +\thingy Des résultats de détermination encore plus forts ont été +étudiés, et ne sont généralement pas prouvables dans la théorie des +ensembles usuelle (par exemple, l'« axiome de détermination + projective », indémontable dans $\mathsf{ZFC}$) ou sont même +incompatibles avec elle (l'« axiome de détermination », qui affirme +que pour toute partie $A \subseteq \{0,1\}^{\mathbb{N}}$ le jeu +$G_{\{0,1\}}(A)$ est déterminé, contredit l'axiome du choix, et a des +conséquences mathématiques remarquables comme le fait que toute partie +de $\mathbb{R}$ est mesurable au sens de Lebesgue). + \subsection{Détermination des jeux combinatoires} |