Détermination (théorie des ensembles)

Le premier jeu que nous allons considérer est le jeu à deux joueurs à information parfaite de longueur ω, dans lequel les joueurs jouent des entiers naturels. Ces jeux sont souvent appelés jeux de Gale–Stewart^[1].

Dans ce jeu, il y a deux joueurs, souvent nommés I et II, qui choisissent à tour de rôle des entiers naturels, le joueur I commence. Ils jouent une infinité de fois chacun. Quand ils ont fini, ils ont obtenu une suite infinie d'entiers naturels. Une condition prédéterminée décide alors quel joueur a gagné en fonction de la suite ainsi obtenue.

Plus formellement, considérons un sous-ensemble A de l'ensemble des suites d'entiers naturels. On appelle G_A le jeu suivant :

Le joueur I joue un entier naturel ${\displaystyle a_{0}}$_, puis II joue un entier naturel ${\displaystyle b_{0}}$_, I joue un entier naturel ${\displaystyle a_{1}}$_, et ainsi de suite. Le joueur I gagne le jeu si et seulement si la suite infinie ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )}$ appartient à A. Dans le cas contraire, le joueur II gagne.

L'ensemble A s'appelle alors l'ensemble de gain de G_A. Le but du joueur I est donc de s'assurer que la suite créée par les deux joueurs appartienne à l'ensemble A et le but du joueur II est de l'en empêcher.

Le jeu est à information parfaite : chaque joueur connaît tous les mouvements qui précèdent chacun de ses mouvements et connaît également la condition de victoire.

De manière informelle, une stratégie pour un joueur est une manière de jouer dans laquelle ses coups sont entièrement déterminés par les coups précédents.

Plus formellement, une stratégie pour le joueur I (pour un jeu au sens de la sous-section précédente) est une fonction qui accepte comme argument toute suite finie de nombres naturels de longueur paire et qui retourne un nombre naturel. Si σ est une telle stratégie et ${\displaystyle (a_{0},b_{0},\ldots ,a_{n},b_{n})}$ est une suite de coups, alors ${\displaystyle \sigma (a_{0},b_{0},\ldots ,a_{n},b_{n})}$ est le prochain coup que I va faire, s'il suit la stratégie σ. Les stratégies pour II sont les mêmes, en remplaçant « pair » par « impair ».

Nous n'avons pour l'instant rien dit sur la pertinence des stratégies. Une stratégie peut tout à fait obliger un joueur à faire de mauvais coups, cela reste quand même une stratégie. En réalité, il n'est même pas nécessaire de connaître la condition de victoire du jeu pour savoir quelles sont les stratégies possibles.

Une stratégie est gagnante si le joueur qui la suit gagne nécessairement, peu importe ce que joue son adversaire.

Autrement dit, soit σ une stratégie pour I dans le jeu G_A. On dit que σ est une stratégie gagnante pour I si, pour toute suite ${\displaystyle (b_{0},b_{1},\ldots )}$ d'entiers naturels joués par II, la suite de coups produits par la stratégie σ en réponse à ${\displaystyle (b_{0},b_{1},\ldots )}$, à savoir ${\displaystyle a_{0}=\sigma ()}$ puis ${\displaystyle a_{1}=\sigma (a_{0},b_{0})}$ puis ${\displaystyle a_{2}=\sigma (a_{0},b_{0},a_{1},b_{1})}$ et ainsi de suite, permet à I de gagner, c'est-à-dire que ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )\in A}$.

Un jeu est dit déterminé s'il existe une stratégie gagnante pour l'un des deux joueurs. Notez qu'il ne peut y avoir de stratégie gagnante pour les deux joueurs pour le même jeu, car s'il en existait, les deux stratégies pourraient être jouées l'une contre l'autre. Le résultat obtenu serait alors, par hypothèse, une victoire pour les deux joueurs, ce qui est impossible^[2].

Le plus souvent, on ne s'intéresse pas à un unique jeu, mais à une classe de jeux. Une classe de jeux est dite déterminée si, pour tous les jeux dans cette classe, il existe une stratégie gagnante pour l'un des joueurs (pas nécessairement le même joueur pour chaque instance)^[3].

Tous les jeux finis à information parfaite sans match nul sont déterminés : c'est le théorème de Zermelo.

Pour les jeux finis à information parfaite avec match nul, on a un résultat analogue : l'un des deux joueurs a une stratégie non-perdante, c'est-à-dire qu'en suivant cette stratégie, le joueur ne perd jamais, il obtient soit un match nul soit une victoire. Un bon nombre de jeux de la vie courante sont dans cette catégorie : tic-tac-toe, ⁣⁣échecs⁣⁣⁣ (cela suppose que la règle des 50 coups soit appliquée), Puissance 4 ...

Dans le formalisme des jeux de Gale-Stewart, le fait qu'un jeu soit fini correspond au fait que l'ensemble de gain A soit un ouvert-fermé pour la topologie usuelle sur l'espace de Baire. Autrement dit, pour déterminer le gagnant d'une partie ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )}$, il suffit de connaître un nombre fini de coups.

La preuve que de tels jeux sont déterminés est assez simple : le joueur I joue simplement pour ne pas perdre ; c'est-à-dire qu'il joue pour s'assurer que le joueur II n'a pas de stratégie gagnante après son coup. Si I ne peut pas le faire, cela signifie que le joueur II a eu une stratégie gagnante depuis le début. D'autre part, si le joueur I peut jouer ainsi, il doit gagner, car la partie sera terminée après un nombre fini de coups et il ne peut pas avoir perdu à ce moment-là.

Cette preuve n'exige pas que le jeu soit toujours terminé dans un nombre fini de coups, mais seulement dans un nombre fini de coups lorsque II gagne. Cette condition correspond au fait que l'ensemble A soit un fermé dans l'espace de Baire. Le fait que tous les jeux fermés sont déterminés s'appelle le théorème de Gale-Stewart. Notez que par symétrie, tous les jeux ouverts sont également déterminés (un jeu est ouvert si le joueur I ne peut gagner uniquement en un nombre fini de coups).

Le théorème de Gale-Stewart nous dit que lorsque l'ensemble de gain A est un ouvert ou un fermé de l'espace de Baire, alors le jeu associé est déterminé. On peut se demander ce qu'il en est lorsque l'on choisit des ensembles de gain de plus en plus complexes, par exemple selon la hiérarchie borélienne. Par la suite, on identifiera la complexité d'un jeu G_A à celle de l'ensemble de gain A vu comme partie de l'espace de Baire. Un jeu ouvert est donc un jeu pour lequel l'ensemble de gain A est ouvert, et ainsi de suite.

La détermination pour le deuxième niveau des jeux de la hiérarchie borélienne a été démontrée par Wolfe en 1955. Lors des vingt années suivantes, des recherches supplémentaires utilisant des arguments de plus en plus complexes ont permis d'établir que les troisième et quatrième niveaux de la hiérarchie borélienne étaient déterminés.

En 1975, Donald A. Martin a prouvé que tous les jeux boréliens étaient déterminés, c'est-à-dire que si A est un sous-ensemble borélien de l'espace de Baire, alors G_A est déterminé. Ce résultat, connu sous le nom de théorème de détermination borélienne (en), est le meilleur résultat de détermination possible prouvable dans ZFC, en ce sens que la détermination de la classe de Wadge (en) immédiatement supérieure ne peut pas être prouvée dans ZFC.

En 1971, avant que Martin obtienne sa preuve, Harvey Friedman montrait que toute preuve de la détermination borélienne devait utiliser l'axiome de remplacement de manière essentielle, afin de pouvoir itérer l'axiome de l'ensemble des parties de manière transfinie. Le travail de Friedman donne un résultat niveau par niveau détaillant le nombre d'itérations de l'axiome de l'ensemble des parties nécessaire pour garantir la détermination à chaque niveau de la hiérarchie borélienne.

Pour chaque entier naturel n, ZFC \ P (où P désigne l'axiome de l'ensemble des parties) prouve la détermination du n-ième niveau de la hiérarchie des différences des ensembles ${\displaystyle \mathbf {\Pi } _{3}^{0}}$, mais ZFC \ P ne prouve pas que pour tout entier n, le n-ième niveau de la hiérarchie des différences des ensembles ${\displaystyle \Pi _{3}^{0}}$ est déterminé. Voir l'article mathématiques inversées pour d'autres relations entre la détermination et les sous-systèmes de l'arithmétique du second ordre^{[réf. nécessaire]}.

Il y a des liens étroits entre la détermination et les grands cardinaux. En général, des axiomes de grands cardinaux plus forts permettent de prouver la détermination de classes (en) de jeux plus grandes, plus élevées dans la hiérarchie de Wadge (en). À l'inverse, la détermination de ces classes de jeux permet de prouver l’existence de modèles intérieurs (en) d’axiomes de grands cardinaux un peu plus faibles que ceux utilisés pour prouver la détermination de ces classes en premier lieu.

Il résulte de l'existence d'un cardinal mesurable que chaque jeu analytique (en) (également appelé jeu ${\displaystyle \mathbf {\Sigma } _{1}^{1}}$) est déterminé, ou, de manière équivalente, que chaque jeu coanalytique (ou ${\displaystyle \mathbf {\Pi } _{1}^{1}}$) est déterminé (voir hiérarchie projective (en) pour les définitions).

En réalité, un cardinal mesurable est plus que suffisant. Un principe plus faible — l'existence de 0^# (en) — suffit à prouver la détermination coanalytique, et un peu plus : le résultat précis est que l'existence de 0^# est équivalente à la détermination de tous les niveaux de la hiérarchie des différences en dessous du niveau ${\displaystyle \omega ^{2}}$, c'est-à-dire la détermination ${\displaystyle \omega .n-\mathbf {\Pi } _{1}^{1}}$ pour tout entier ${\displaystyle n}$.

D'un cardinal mesurable, nous pouvons très légèrement améliorer cette détermination jusqu'à la détermination ${\displaystyle \omega ^{2}-\mathbf {\Pi } _{1}^{1}}$.

De l'existence de plusieurs cardinaux mesurables, on peut prouver la détermination de plusieurs niveaux de la hiérarchie des différences sur ${\displaystyle \mathbf {\Pi } _{1}^{1}}$_.

Pour chaque nombre réel r, la détermination ${\displaystyle \Sigma _{1}^{1}(r)}$ est équivalente à l'existence de r^#. Pour illustrer comment les grands cardinaux conduisent au déterminisme, voici une preuve de la détermination ${\displaystyle \Sigma _{1}^{1}(r)}$ supposant l'existence de r^#.

Soit A un sous-ensemble ${\displaystyle \Sigma _{1}^{1}(r)}$ de l'espace de Baire. Il existe un arbre T sur ${\displaystyle (\omega ,\omega )}$, constructible à partir de r, tel que A = p[T] (c'est-à-dire que pour toute suite ${\displaystyle x}$ de l'espace de Baire, on a ${\displaystyle x\in A}$ si et seulement s'il existe y tel que ${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...)}$ est un chemin à travers T).

Étant donné une partie partielle s, soit ${\displaystyle T_{s}}$ le sous-arbre de T cohérent avec s et tel que ${\displaystyle \max(y_{0},y_{1},\ldots ,y_{len(s)-1})<len(s)}$. Cette dernière condition garantit que ${\displaystyle T_{s}}$ est fini. La cohérence signifie que chaque chemin à travers ${\displaystyle T_{s}}$ est de la forme ${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))}$ où ${\displaystyle (x_{0},x_{1},...,x_{i})}$ est un segment initial de s.

Pour prouver que A est déterminé, définissons un jeu auxiliaire comme suit :

En plus des coups ordinaires, le joueur 2 doit jouer une application de ${\displaystyle T_{s}}$ dans les ordinaux (sous un ordinal suffisamment grand κ) tels que :

• chaque nouveau coup étend l'application précédente et
• l'ordre des ordinaux est conforme à l'ordre de Kleene-Brouwer sur ${\displaystyle T_{s}}$.

Rappelons que l'ordre de Kleene-Brouwer est semblable à l'ordre lexicographique, sauf que si s étend strictement t alors s < t . C’est un bon ordre si et seulement si l'arbre est bien-fondé.

Ce jeu auxiliaire est un jeu ouvert. Preuve : Si le joueur II ne perd pas à un stade fini, alors l’union de tous ${\displaystyle T_{s}}$ (qui est l’arbre qui correspond au jeu) est bien fondé et le résultat des coups non auxiliaires n’est donc pas dans A.

Ainsi, le jeu auxiliaire est déterminé. Preuve : Par induction transfinie, calculez pour chaque ordinal α l'ensemble des positions avec lesquelles le joueur I peut forcer une victoire en α étapes. Une stratégie pour le joueur I consiste à réduire α à chaque position (par exemple, en choisissant le plus petit α et en choisissant le plus petit coup en cas d'égalité), et une stratégie pour le joueur II consiste à choisir le plus petit coup ne menant pas à une position avec un α assigné. Notez que ${\displaystyle L(r)}$ contient l’ensemble des positions gagnantes ainsi que les stratégies gagnantes indiquées ci-dessus.

Une stratégie gagnante pour le joueur II dans le jeu d'origine conduit à une stratégie gagnante dans le jeu auxiliaire : le sous-arbre de T correspondant à la stratégie gagnante est bien fondé, ainsi le joueur II peut choisir des ordinaux basés sur l'ordre de Kleene-Brouwer de l'arbre. En outre, trivialement, une stratégie gagnante pour le joueur II dans le jeu auxiliaire donne une stratégie gagnante pour le joueur II dans le jeu original.

Il reste à montrer que, grâce à r^#, la stratégie gagnante susmentionnée pour le joueur I dans le jeu auxiliaire peut être convertie en une stratégie gagnante dans le jeu original. Si la réponse auxiliaire utilise uniquement des ordinaux indiscernables, alors (par indiscernabilité) les coups du joueur I ne dépendent pas des coups auxiliaires, de sorte que la stratégie peut être convertie en une stratégie pour le jeu d'origine (car le joueur II peut jouer avec des indiscernables aussi longtemps que nécessaire). Supposons que le joueur I perd dans le jeu d'origine. L'arbre correspondant est alors bien fondé. Par conséquent, le joueur II peut gagner le jeu auxiliaire grâce à des coups auxiliaires basés sur les indiscernables (puisque le type d'ordre des indiscernables dépasse l'ordre Kleene-Brouwer de l'arbre), ce qui contredit le fait que le joueur I remporte le jeu auxiliaire.

L'existence d'un cardinal de Woodin avec un cardinal mesurable au-dessus implique la détermination ${\displaystyle \mathbf {\Pi } _{2}^{1}}$. Plus généralement, l'existence de n cardinaux de Woodin avec un cardinal mesurable au-dessus d'eux entraîne la détermination ${\displaystyle \mathbf {\Pi } _{n+1}^{1}}$. À partir de la détermination ${\displaystyle \mathbf {\Pi } _{n+1}^{1}}$, on peut prouver l'existence d'un modèle interne transitif contenant n cardinaux de Woodin. La détermination ${\displaystyle \Delta _{2}^{1}}$ (lightface) est équiconsistant à l'existence d’un cardinal de Woodin. Si la détermination ${\displaystyle \Delta _{2}^{1}}$ est vérifiée, alors pour un cône de Turing de x (c'est-à-dire pour tout réel x de degré de Turing suffisamment élevé), ${\displaystyle L[x]}$ vérifie la détermination OD (c'est-à-dire la détermination des jeux avec des entiers de longueur ${\displaystyle \omega }$ et dont l'ensemble de gain est définissable à partir des ordinaux), et dans ${\displaystyle {\text{HOD}}^{L[x]}}$, ${\displaystyle \omega _{2}^{L[x]}}$ est un cardinal de Woodin.

L'existence d'une infinité de cardinaux de Woodin entraîne la détermination projective, c'est-à-dire que chaque jeu dont l'ensemble de gain est un ensemble projectif (en) est déterminé. Du déterminisme projectif, il en résulte que, pour tout entier naturel n, il existe un modèle interne transitif ayant n cardinaux de Woodin.

L'axiome de détermination, ou AD, affirme que chaque jeu à deux joueurs à information parfaite de longueur ω, dans laquelle les joueurs jouent des entiers naturels, est déterminé.

AD est faux dans ZFC. En effet, grâce à l'axiome de choix, on peut prouver l’existence d’un jeu non déterminé. Cependant, s'il y a une infinité de cardinaux de Woodin avec un cardinal mesurable au-dessus d'eux, alors L(R) (en) est un modèle de ZF qui satisfait également AD.