diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 36 |
1 files changed, 18 insertions, 18 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 672c428..92db678 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -417,7 +417,7 @@ son gain en changeant \emph{unilatéralement} la stratégie employée) : l'un où Alice joue colombe et Bob joue faucon, un deuxième où c'est le contraire, et un troisième où chacun joue colombe ou faucon avec les probabilités respectives $\frac{L-X}{W-T + L-X}$ et $\frac{W-T}{W-T + - L-X}$ (avec les valeurs ci-desssus : $\frac{2}{3}$ et + L-X}$ (avec les valeurs ci-dessus : $\frac{2}{3}$ et $\frac{1}{3}$), pour un gain espéré de $\frac{LW - TX}{W-T + L-X}$ (avec les valeurs ci-dessus : $\frac{4}{3}$). @@ -438,7 +438,7 @@ Ou plus généralement, en remplaçant $2,1,0$ par trois nombres $P$ (préféré), $Q$ (autre), $N$ (nul) tels que $P>Q>N$. Ce jeu présente par exemple un intérêt en sociologie, notamment pour -ce qui est de la synchronisation aoutour d'une ressource commune (par +ce qui est de la synchronisation autour d'une ressource commune (par exemple l'adoption d'un standard). On pourra se convaincre que ce jeu a trois équilibres de Nash @@ -510,7 +510,7 @@ un graphe orienté (cf. \ref{definitions-graphs} ci-dessous pour la définition) et $x_0$ un sommet de $G$. Partant de $x_0$, Alice et Bob choisissent tour à tour une arête à emprunter pour arriver dans un nouveau sommet (c'est-à-dire : Alice choisit un voisin sortant $x_1$ -de $x_0$, puis Bob un voisins ortant $x_2$ de $x_1$, puis Alice $x_3$ +de $x_0$, puis Bob un voisin sortant $x_2$ de $x_1$, puis Alice $x_3$ de $x_2$ et ainsi de suite). \emph{Le perdant est celui qui ne peut plus jouer}, et si ceci ne se produit jamais (si on définit un chemin infini $x_0, x_1, x_2, x_3,\ldots$) alors la partie est @@ -1559,7 +1559,7 @@ $\underline{x} := (x_0,\ldots,x_{\ell-1})$, on a $\underline{x}^\$ A = x_{\ell-1}^{\$} \cdots x_1^{\$} x_0^{\$} A$.) \thingy\label{gale-stewart-positions-as-games} Toute position -$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart peut être considéré +$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart peut être considérée comme définissant un nouveau jeu de Gale-Stewart consistant à jouer \textbf{à partir de là}, c'est-à-dire, comme si les $\ell$ premiers coups étaient imposés. @@ -1586,7 +1586,7 @@ $G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.) $(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart $G_X(A)$ est \textbf{gagnante} pour Alice lorsque Alice a une stratégie gagnante dans le jeu qui consiste à jouer à partir de cette position -(cf. \ref{gale-stewart-positions-as-games}). On définit de meme une +(cf. \ref{gale-stewart-positions-as-games}). On définit de même une position gagnante pour Bob. \medbreak @@ -1718,7 +1718,7 @@ contient une suite $\underline{x} := (x_0,x_1,x_2,\ldots)$, il existe un rang $\ell$ tel que $A$ contienne n'importe quelle suite obtenue en modifiant la suite $\underline{x}$ à partir du rang $\ell$. -Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dite \textbf{fermé} +Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \textbf{fermé} lorsque son complémentaire $B := X^{\mathbb{N}} \setminus A$ est ouvert. \end{defn} @@ -1766,7 +1766,7 @@ topologie produit) : L'affirmation (i) est triviale. Montrons (ii) : si les $A_i$ sont ouverts et si $\underline{x} \in -\bigcup_{i\in I} A_i$, alors la définion d'une réunion fait qu'il +\bigcup_{i\in I} A_i$, alors la définition d'une réunion fait qu'il existe $i$ tel que $\underline{x} \in A_i$, et comme $A_i$ est ouvert il existe un voisinage fondamental de $\underline{x}$ inclus dans $A_i$, donc inclus dans $\bigcup_{i\in I} A_i$ : ceci montre que @@ -1911,7 +1911,7 @@ Réciproquement, si la position initiale $()$ n'est pas gagnante en $\alpha$ coups par Alice quel que soit $\alpha$ (appelons-la « non comptée »), alors Bob possède une stratégie consistant à jouer toujours sur des telles positions non décomptées : d'après la -définition des positiosn gagnantes en $\alpha$ coup, quand c'est à +définition des positions gagnantes en $\alpha$ coup, quand c'est à Alice de jouer, une position non comptée ne conduit qu'à des positions non comptées, et quand c'est à Bob de jouer, une position non comptée conduit à au moins une condition non comptée. Ainsi, si Bob joue @@ -1962,7 +1962,7 @@ 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 + projective », indémontrable 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 @@ -1998,7 +1998,7 @@ finie ou infinie $(x_i)$ de sommets de $G$ telle que $x_0$ soit la position initiale et que pour chaque $i$ pour lequel $x_{i+1}$ soit défini, ce dernier soit un voisin sortant de $x_i$. Lorsque le dernier $x_i$ défini l'est pour un $i$ pair, on dit que le premier -joueur \textbf{perd} et que les second \textbf{gagne}, tandis que +joueur \textbf{perd} et que le second \textbf{gagne}, tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que le premier joueur gagne et que le second perd ; enfin, lorsque $x_i$ est défini pour tout entier naturel $i$, on dit que la confrontation @@ -2315,7 +2315,7 @@ $\varsigma'$ l'est. \end{proof} \thingy\label{notation-n-and-p-sets-for-combinatorial-games} En -contituant les notations introduites +continuant les notations introduites en \ref{set-of-everywhere-winning-positional-strategies}, on fixe maintenant $\varsigma \in \mathcal{S}$ maximal pour l'inclusion (dont l'existence est garantie par la @@ -2515,7 +2515,7 @@ démontré l'existence d'une plus petite $f$). Le but de cette section est de présenter les outils fondamentaux sur les graphes orientés bien-fondés (cf. \ref{definitions-graphs}) -permettant utiles à la théorie combinatoire des jeux impartiaux. Il +utiles à la théorie combinatoire des jeux impartiaux. Il s'agit notamment de la théorie de l'induction bien-fondée (cf. \ref{scholion-well-founded-induction} et \ref{scholion-well-founded-definition}). @@ -2707,7 +2707,7 @@ f(x) = \Phi(x,\, f|_{\outnb(x)}) \end{thm} \begin{proof} Montrons d'abord l'unicité : si $f$ et $f'$ vérifient toutes les deux -la propriété anoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels +la propriété annoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels que $f(x) = f'(x)$. Si $x \in G$ est tel que $\outnb(x) \subseteq P$, c'est-à-dire que $f|_{\outnb(x)} = f'|_{\outnb(x)}$, alors $f(x) = \Phi(x,\, @@ -3074,7 +3074,7 @@ l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que $f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe -orienté) s'appelle l'écasement transitif du sommet $x$. +orienté) s'appelle l'écrasement transitif du sommet $x$. On considérera l'écrasement $f(G)$ de $G$ comme un graphe orienté, en plaçant une arête de $u$ vers $v$ lorsque $v \in u$ ; autrement dit, @@ -3110,7 +3110,7 @@ sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x) Pour bien comprendre et utiliser la définition ci-dessus, il est pertinent de rappeler que \emph{deux ensembles sont égaux si et - seulement si il sont les mêmes éléments} (\textbf{axiome + seulement si ils ont les mêmes éléments} (\textbf{axiome d'extensionalité}). \begin{prop}\label{extensional-iff-collapse-injective} @@ -3363,7 +3363,7 @@ Par exemple, on peut imaginer que le dessin de la figure ci-dessus qu'on pourrait utiliser dans un jeu de nim (cf. \ref{introduction-nim-game}) : si on convient que les allumettes doivent être effacées \emph{par la droite}, ce qui revient à diminuer -strictement l'ordinal qui les compte (intialement $\omega^2$), la +strictement l'ordinal qui les compte (initalement $\omega^2$), la ligne sera toujours vidée en temps fini même si les joueurs essaient de la faire durer le plus longtemps possible (le premier coup va faire tomber l'ordinal $\omega^2$ à $\omega\cdot k + n$ avec @@ -3446,7 +3446,7 @@ n'est pas vraiment nécessaire à la théorie des ordinaux, et nous tâcherons d'éviter d'en dépendre. Mais il faut au moins retenir une idée : -\thingy Tout ensemble $S$ d'ordinaux, il existe un ordinal qui est +\thingy Pour tout ensemble $S$ d'ordinaux, il existe un ordinal qui est plus grand que tous les éléments de $S$ ; il existe même un \emph{plus petit} ordinal plus grand que tous les éléments de $S$, c'est-à-dire, une \emph{borne supérieure} de $S$. Ce fait est la clé @@ -3529,7 +3529,7 @@ distinction étant souvent utile dans les inductions : \item l'ordinal nul $0$, qui est souvent un cas spécial, \item les ordinaux « successeurs », c'est-à-dire ceux qui sont de la forme $\beta+1$ pour $\beta$ un ordinal plus petit (de façon - équialente, il y a un plus grand ordinal strictement plus petit), + équivalente, il y a un plus grand ordinal strictement plus petit), \item les ordinaux qui sont la borne supérieure (ou « limite ») des ordinaux strictement plus petits et qu'on appelle, pour cette raison, « ordinaux limites » (autrement dit, $\delta$ est limite |