axiome de détermination

Imaginez deux joueurs qui écrivent chacun leur tour un entier naturel : 0, 1, 2, etc. La suite infinie obtenue décide qui gagne, selon une règle fixée avant la partie. Une stratégie gagnante est un plan qui conduit à la victoire, quels que soient les nombres choisis par l'autre joueur.

L'axiome de détermination affirme qu'une telle stratégie existe toujours pour les jeux de la classe considérée : le premier joueur en a une, ou bien le second en a une. Il ne dit pas laquelle ; il garantit seulement que le jeu ne reste pas sans vainqueur stratégique.

Un jeu de la classe considérée oppose deux joueurs, I et II. Ils choisissent alternativement des entiers naturels et produisent une suite infinie x = (x₀, x₁, x₂, …). On fixe à l'avance un ensemble A de suites qui sont gagnantes pour I ; les suites qui ne sont pas dans A sont gagnantes pour II.

Une stratégie pour I associe un entier à chaque suite finie de coups antérieurs autorisant un coup de I ; une stratégie pour II fait de même pour chaque suite finie de coups antérieurs autorisant un coup de II. Ces suites décrivent l'historique complet de la partie, et non seulement les coups de l'adversaire. Une stratégie est gagnante si toutes les parties compatibles avec elle donnent le gain au joueur qui l'emploie. Le jeu est déterminé lorsque I possède une stratégie gagnante ou II en possède une.

L'axiome de détermination, souvent abrégé AD, affirme que tous les jeux de cette forme sont déterminés, pour la classe de conditions de victoire visée par l'axiome. Il ne s'agit pas d'une méthode pour construire la stratégie. AD est incompatible avec ZFC, c'est-à-dire ZF augmentée de l'axiome du choix ; son statut par rapport à ZF seule se formule au moyen de résultats de cohérence relative, sous les hypothèses métathéoriques appropriées. En particulier, AD entraîne la négation de l'axiome du choix. Il a des conséquences profondes en théorie descriptive des ensembles.

Pour un jeu à deux joueurs où chacun choisit à son tour un entier naturel et où l'issue dépend de la suite infinie produite, l'axiome de détermination énonce : si la condition de victoire appartient à la classe considérée par AD, alors I possède une stratégie gagnante ou II possède une stratégie gagnante. Les deux possibilités peuvent être écrites ainsi :

Dans cette formule, Γ désigne la classe de conditions de victoire couverte par l'énoncé d'AD.

Ici, A désigne l'ensemble des suites gagnantes pour I ; la formule rappelle le schéma général, tandis que la portée exacte de l'axiome dépend de la classe de jeux adoptée.

Le jeu doit avoir deux joueurs, des coups choisis alternativement et une partie infinie décrite par une suite d'entiers naturels. La condition de victoire doit être fixée avant les choix et appartenir à la classe de jeux concernée par l'axiome. Le résultat attendu est une stratégie gagnante pour I ou pour II, pas nécessairement une description explicite de cette stratégie.

Un jeu fini n'est pas un exemple direct de cette formulation : la partie ne produit pas de suite infinie, et d'autres résultats de détermination peuvent alors s'appliquer. De même, si l'on change la classe de conditions de victoire, il faut vérifier séparément que l'axiome invoqué la couvre ; on ne peut pas conclure par simple analogie.

Considérons un jeu infini où I choisit le premier entier, puis II et I alternent indéfiniment. I gagne exactement lorsque le premier entier choisi vaut 1. Les données du jeu sont :

Joueurs : I puis II, à tour de rôle.
Coups : des entiers naturels.
Condition : I gagne si x₀ = 1 ; sinon II gagne.
Stratégie proposée : I choisit 1 dès son premier coup.

La première opération est le choix de I : x₀ = 1.
La deuxième opération est le choix de II : il peut choisir n'importe quel entier, sans modifier x₀.
La troisième opération consiste à lire la condition de victoire : x₀ = 1 est vraie.
Le résultat est donc que I gagne, quelle que soit la suite des coups de II.

Le contrôle est immédiat : toutes les parties compatibles avec le premier coup 1 ont leur premier terme égal à 1. Pour voir le rôle de l'historique, I peut ensuite répondre au coup x₁ de II en choisissant x₂ = x₁ ; cette réponse dépend du coup antérieur, mais ne change pas x₀ = 1. La stratégie reste donc gagnante dans ce jeu particulier ; l'axiome de détermination généralise l'alternative de détermination à une classe étendue de jeux infinis.

En théorie des ensembles, on utilise l'axiome de détermination pour transformer une question d'existence de stratégie en propriété de la condition de victoire. Le geste consiste à identifier le jeu, le joueur gagnant et la classe d'ensembles de suites à laquelle appartient la condition.

Dans un raisonnement de théorie descriptive des ensembles, AD sert à étudier les conséquences de la détermination pour la classe de jeux et de suites considérée. L'alternative pertinente est alors un résultat établi dans ZF ou dans une autre théorie, si l'on ne souhaite pas supposer AD.

Pour lire un énoncé, commencez par repérer la règle qui décide le vainqueur. Vérifiez ensuite que les coups, la durée et la classe de cette règle correspondent bien au cadre annoncé.

L'axiome de détermination ne se confond pas avec une stratégie gagnante particulière. Une stratégie est un objet construit pour un jeu donné ; AD est une affirmation générale garantissant qu'un des deux joueurs en possède une dans la classe de jeux considérée. Le cas conducteur tranche : le choix initial 1 fournit ici la stratégie de I, mais ce choix n'est pas le contenu de l'axiome lui-même.

Il ne se confond pas non plus avec le fait qu'une partie possède une issue. Chaque partie peut bien produire un résultat, sans qu'un joueur dispose d'un plan qui gagne contre tous les choix adverses. La détermination porte sur l'existence d'un tel plan universel pour l'un des deux joueurs.

Une première limite vient de la classe de jeux. AD ne peut être appliqué que si la condition de victoire appartient au domaine visé par l'énoncé adopté. Le symptôme d'un abus est une conclusion de détermination obtenue sans avoir décrit cette condition ; il faut alors préciser la classe ou suspendre la conclusion.

Le mot « stratégie » peut aussi induire en erreur. Elle doit répondre à chaque suite finie de coups autorisant encore une partie, et non seulement à la suite effectivement observée. Pour corriger la lecture, demandez si le plan résiste à toutes les réponses de l'adversaire.

Enfin, il faut distinguer les théories en présence : AD est incompatible avec ZFC, c'est-à-dire ZF augmentée de l'axiome du choix, tandis que son statut par rapport à ZF seule se décrit par des résultats de cohérence relative et leurs hypothèses métathéoriques. Cette distinction ne signifie ni que l'axiome est contradictoire, ni qu'une stratégie concrète est impossible à trouver dans chaque jeu particulier.

Un prolongement naturel consiste à étudier la théorie descriptive des ensembles : elle analyse la complexité des ensembles de suites et les propriétés qu'une hypothèse de détermination peut leur conférer. Le lecteur y gagne un cadre pour comprendre pourquoi un principe formulé comme un jeu produit des conséquences sur les ensembles de réels.