summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-25 10:27:16 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-02-25 10:27:16 (GMT)
commita42a0029c3399bf6d3e0fefbcca58ee7cfc5475e (patch)
tree710b44fababbfabc5157232ff39ced2e11b87739 /notes-mitro206.tex
parent8636acf6762500dd295b3bbea6a4f8af4e7404bf (diff)
downloadmitro206-a42a0029c3399bf6d3e0fefbcca58ee7cfc5475e.zip
mitro206-a42a0029c3399bf6d3e0fefbcca58ee7cfc5475e.tar.gz
mitro206-a42a0029c3399bf6d3e0fefbcca58ee7cfc5475e.tar.bz2
Prove the essentially trivial proposition about strategies (exists/forall).
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex59
1 files changed, 58 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 7d5f1b3..30f16f2 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -68,6 +68,9 @@ Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}
+\pretolerance=8000
+\tolerance=50000
+
%
@@ -1378,7 +1381,61 @@ Dans le jeu de Gale-Stewart $G_X(A)$ :
\end{itemize}
\end{prop}
\begin{proof}
-\textcolor{red}{...}
+La démonstration suivante ne fait que (laborieusement) formaliser
+l'argument « une stratégie gagnante pour Alice détermine un premier
+coup, après quoi elle a une stratégie gagnante, et une stratégie
+gagnante pour Bob est prête à répondre à n'importe quel coup d'Alice
+après quoi il a une stratégie gagnante » :
+
+Si Alice (premier joueur) possède une stratégie $\varsigma$ gagnante
+dans $G_X(A)$, on pose $x := \varsigma(())$ le premier coup préconisé
+par cette stratégie, et on définit
+$\varsigma'((x_1,x_2,\ldots,x_{i-1})) =
+\varsigma((x,x_1,x_2,\ldots,x_{i-1}))$ pour $i$ pair : cette
+définition fait que si $(x_1,x_2,x_3,\ldots)$ est une confrontation où
+Alice joue en second selon $\varsigma'$ alors $(x,x_1,x_2,x_3,\ldots)$
+en est une où elle joue en premier selon $\varsigma$, donc cette suite
+appartient à $A$ puisque $\varsigma$ est gagnante pour Alice
+dans $G_X(A)$, donc $(x_1,x_2,x_3,\ldots)$ appartient à $x^{\$} A$, et
+Alice a bien une stratégie gagnante, $\varsigma'$, en jouant en second
+dans $G_X(x^{\$} A)$.
+
+Réciproquement, si Alice possède une stratégie gagnante $\varsigma'$
+en jouant en second dans $G_X(x^{\$} A)$, on définit $\varsigma$ par
+$\varsigma(()) = x$ et $\varsigma((x,x_1,x_2,\ldots,x_{i-1})) =
+\varsigma'((x_1,x_2,\ldots,x_{i-1}))$ pour $i > 0$ pair : cette
+définition fait que si $(x_0,x_1,x_2,x_3,\ldots)$ est une
+confrontation où Alice joue en premier selon $\varsigma$ alors $x_0 =
+x$ et $(x_1,x_2,x_3,\ldots)$ est confrontation où elle (Alice) joue en
+second selon $\varsigma'$, donc cette suite appartient à $x^{\$} A$
+puisque $\varsigma'$ est gagnante pour Alice second joueur
+dans $G_X(x^{\$} A)$, donc $(x_0,x_1,x_2,x_3,\ldots)$ appartient
+à $A$, et Alice a bien une stratégie gagnante, $\varsigma$, en jouant
+en premier dans $G_X(A)$.
+
+Si Bob (second joueur) possède une stratégie $\tau$ gagnante
+dans $G_X(A)$ et si $x \in X$ est quelconque, on définit
+$\tau'((x_1,x_2,\ldots,x_{i-1})) = \tau((x,x_1,x_2,\ldots,x_{i-1}))$
+pour $i$ impair : cette définition fait que si $(x_1,x_2,x_3,\ldots)$
+est une confrontation où Bob joue en premier selon $\tau'$ alors
+$(x,x_1,x_2,x_3,\ldots)$ en est une où il joue en second selon $\tau$,
+donc cette suite n'appartient pas à $A$ puisque $\tau$ est gagnante
+pour Bob dans $G_X(A)$, donc $(x_1,x_2,x_3,\ldots)$ n'appartient pas
+à $x^{\$} A$, et Bob a bien une stratégie gagnante, $\tau'$, en jouant
+en premier dans $G_X(x^{\$} A)$.
+
+Réciproquement, si Bob possède une stratégie gagnante en jouant en
+second dans $G_X(x^{\$} A)$ pour chaque $x\in X$, on en choisit une
+$\tau_x$ pour chaque $x$, et on définit $\tau$ par
+$\tau((x,x_1,x_2,\ldots,x_{i-1})) = \tau_x((x_1,x_2,\ldots,x_{i-1}))$
+pour $i$ impair : cette définition fait que si
+$(x_0,x_1,x_2,x_3,\ldots)$ est une confrontation où Bob joue en second
+selon $\tau$ alors $(x_1,x_2,x_3,\ldots)$ est confrontation où il
+(Bob) joue en premier selon $\tau_{x_0}$, donc cette suite
+n'appartient pas à ${x_0}^{\$} A$ puisque $\tau_{x_0}$ est gagnante
+pour Bob premier joueur dans $G_X({x_0}^{\$} A)$, donc
+$(x_0,x_1,x_2,x_3,\ldots)$ n'appartient pas à $A$, et Bob a bien une
+stratégie gagnante, $\tau$, en jouant en second dans $G_X(A)$.
\end{proof}