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].

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.

Si A est un sous-ensemble de l'espace de Baire tel que le jeu de Banach-Mazur (en) pour A soit déterminé, alors soit II dispose d'une stratégie gagnante, auquel cas A est maigre, soit I a une stratégie gagnante, auquel cas A est comaigre dans un voisinage ouvert.

Cela n'implique pas forcément que A possède la propriété de Baire, mais cela s'en rapproche : une simple modification de l'argument montre que si Γ est une classe d'ensembles adéquate (en) telle que chaque jeu de Γ soit déterminé, alors chaque ensemble de réels de Γ a la propriété de Baire.

Ce résultat n'est pas optimal. En considérant le jeu déplié de Banach-Mazur, nous pouvons montrer que la détermination de Γ (pour Γ avec des propriétés de fermeture suffisantes) implique que chaque ensemble de réels qui est la projection d'un ensemble dans Γ a la propriété de Baire. Ainsi, par exemple, l’existence d’un cardinal mesurable implique la détermination ${\displaystyle \mathbf {\Pi } _{1}^{1}}$, ce qui implique que chaque jeu ${\displaystyle \mathbf {\Sigma } _{2}^{1}}$ de réels a la propriété de Baire.

En considérant d’autres jeux, nous pouvons montrer que la détermination ${\displaystyle \mathbf {\Pi } _{n}^{1}}$ implique que chaque ensemble de réels ${\displaystyle \mathbf {\Sigma } _{n+1}^{1}}$ a la propriété de Baire, est Lebesgue-mesurable (en fait, universellement mesurable (en)) et possède la propriété de l'ensemble parfait.

• Le premier théorème de périodicité implique que, pour chaque entier naturel n, si la détermination ${\displaystyle \mathbf {\Delta } _{2n+1}^{1}}$ est vérifiée, alors ${\displaystyle \mathbf {\Pi } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Sigma } _{2n+2}^{1}}$ ont la propriété du pré-bon ordre (et que ${\displaystyle \mathbf {\Sigma } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Pi } _{2n+2}^{1}}$ n'ont pas la propriété du pré-bon ordre, mais ont plutôt la propriété de séparation).
• Le second théorème de périodicité implique que, pour chaque entier naturel n, si la détermination ${\displaystyle \mathbf {\Delta } _{2n+1}^{1}}$ est vérifiée, alors ${\displaystyle \mathbf {\Pi } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Sigma } _{2n}^{1}}$ ont la propriété d'échelle (en)[4]. En particulier, si la détermination projective est vérifiée, alors chaque relation projective a une uniformisation (en) projective.
• Le troisième théorème de périodicité donne une condition suffisante pour qu'un jeu ait une stratégie gagnante définissable.

En 1969, Michael O. Rabin a prouvé que la théorie du second ordre de n successeurs est décidable[5]. Un élément clé de la preuve consiste à montrer la détermination des jeux de parité, qui se situent au troisième niveau de la hiérarchie borélienne.

La détermination de Wadge est l’affirmation que pour toutes les paires A, B de sous-ensembles de l'espace de Baire, le jeu de Wadge (en) G(A, B) est déterminé. De même, pour une classe d'ensembles (en) ${\displaystyle \Gamma }$, la détermination de Wadge pour ${\displaystyle \Gamma }$ est l'affirmation que pour tous les ensembles A, B dans ${\displaystyle \Gamma }$, le jeu de Wadge G(A, B) est déterminé.

La détermination de Wadge implique le principe d'ordre semi linéaire pour l'ordre de Wadge (en). Une autre conséquence de la détermination de Wadge est la propriété de l'ensemble parfait.

En général, la détermination de Wadge pour ${\displaystyle \Gamma }$ est une conséquence de la détermination des combinaisons booléennes d'ensembles de ${\displaystyle \Gamma }$. Dans la hiérarchie projective, la détermination de Wadge ${\displaystyle \mathbf {\Pi } _{1}^{1}}$ est équivalente à la détermination ${\displaystyle \mathbf {\Pi } _{1}^{1}}$, résultat prouvé par Harrington. Ce résultat a été étendu par Hjorth, qui a prouvé que la détermination de Wadge ${\displaystyle \mathbf {\Pi } _{2}^{1}}$ (et en fait le principe d'ordre semi linéaire pour ${\displaystyle \mathbf {\Pi } _{2}^{1}}$) implique la détermination ${\displaystyle \mathbf {\Pi } _{2}^{1}}$.

La détermination des jeux sur les ordinaux de longueur ${\displaystyle \omega }$ et dont l'ensemble de gain est définissable par ordinaux implique que pour chaque cardinal régulier κ> ω, il n'y a pas de sous-ensembles de ${\displaystyle \kappa }$ disjoints, stationnaires, formés d'éléments de cofinalité ${\displaystyle \omega }$ et définissable par des ordinaux. La force de cohérence de cette hypothèse de détermination est inconnue, mais elle devrait être très élevée.

L'existence de ${\displaystyle \omega _{1}}$ cardinaux de Woodin implique que pour chaque ordinal dénombrable α, tous les jeux sur des entiers de longueur α et avec ensemble de gain projectif sont déterminés. Grosso modo, l'existence de α cardinaux de Woodin correspond à la détermination des jeux sur des réels de longueur α (avec un ensemble de gain simple). En supposant que ${\displaystyle \kappa }$ est une limite de cardinaux de Woodin avec ${\displaystyle o(\kappa )=\kappa ^{++}}$et qu'il existe ${\displaystyle \omega }$ cardinaux de Woodin supérieurs à κ, alors les jeux de durée dénombrable variable se terminant dès que sa longueur est admissible par rapport à la ligne de jeu et avec ensemble de gain projectif sont déterminés. En supposant qu'une certaine conjecture d'itérabilité puisse être prouvée, l'existence d'un cardinal de Woodin mesurable implique la détermination des jeux ouverts de longueur ${\displaystyle \omega _{1}}$ et avec ensemble de gain projectif. (Dans ces jeux, une condition de gain pour le premier joueur est décidée à une étape dénombrable, raison pour laquelle le gain peut être codé comme un ensemble de réels).

Relativement à l'existence d'un cardinal de Woodin limite de cardinaux Woodin et à un cardinal mesurable au-dessus d'eux, il est cohérent que chaque jeu sur les entiers de longueur ${\displaystyle \omega _{1}}$ avec un ensemble de gain définissable par ordinaux est déterminé. Il est conjecturé que cette hypothèse de détermination est équiconsistant avec un cardinal de Woodin limite de cardinaux de Woodin. L'ordinal ${\displaystyle \omega _{1}}$ est maximal dans la mesure où il existe des jeux indéterminés sur les entiers de longueur ${\displaystyle \omega _{1}+\omega }$ dont l'ensemble de gain est définissable par ordinaux.

Dans la plupart des jeux intéressants à information imparfaite (en), une stratégie gagnante sera une stratégie mixte : c'est-à-dire qu'elle donnera une probabilité pour les différentes réponses à une même situation. Si les stratégies des deux joueurs sont des stratégies mixtes, alors le résultat du jeu ne peut pas être certainement décidé à l'avance (comme c'est le cas pour les stratégies pures, puisque celles-ci sont déterministes). Cependant, la distribution de probabilités des résultats pour des stratégies mixtes opposées peut être calculée. Un jeu qui nécessite des stratégies mixtes est dit déterminé s'il existe une stratégie qui donne une espérance minimale (sur l'ensemble des contre-stratégies possibles) qui dépasse une valeur donnée. Avec cette définition, tous les jeux finis à deux joueurs à somme nulle sont clairement déterminés. Cependant, la détermination des jeux infinis à information imparfaite (jeux de Blackwell) est moins claire[6].

En 1969, David Blackwell a prouvé que certains jeux infinis à information imparfaite (maintenant appelés « jeux de Blackwell ») étaient déterminés, et en 1998, Donald A. Martin a prouvé que le déterminisme ordinaire (pour les jeux à information parfaite) pour une classe grasse d'ensembles (en) implique la détermination de Blackwell pour cette classe d'ensembles. Ceci, combiné au théorème de détermination borélienne de Martin, implique que tous les jeux de Blackwell avec des fonctions de paiement boréliennes sont déterminés[7] - [8]. Martin a conjecturé que la détermination ordinaire et la détermination de Blackwell pour les jeux infinis sont équivalents dans un sens fort (c'est-à-dire que la détermination de Blackwell pour une classe grasse d'ensembles implique à son tour la détermination ordinaire pour cette classe d'ensembles), mais en 2010, il n'a toujours pas été prouvé que la détermination de Blackwell implique la détermination des jeux à information parfaite[9].