1
$\begingroup$

I've read many descriptions and applications of a Winning Strategy, as much as many for a Strategy tout court, but when a formal, algebraic definition is called upon, I've found close to no input.

I recall that an Ehrenfeucht-Fraïssé game involves two players, namely spoiler and duplicator, and it is used to compare the similarities about two structures and also to inspect the power of expression in a first-order environment of such structures. The Ehrenfeucht theorem then states that "given two $S$-structures $\mathfrak A$ and $\mathfrak B$, with A$\cap$B=$\emptyset$, with $S$ a finite signature, the following expressions are equivalent:

$(I_i)_{i\leq n}$:$\mathfrak A\cong_f \mathfrak B$.

$\mathfrak A \equiv_n \mathfrak B$.

Duplicator has a Winning Strategy for an Ehrenfeucht-Fraïssé game."

Therefore my request for a proper definition of a Winning Strategy. Thank you.

$\endgroup$
3
$\begingroup$

A precise formal definition of a (winning) strategy for Duplicator really is not very enlightening. A strategy would tell how Duplicator should play given the position of the current play of the game. Each play of the game is essentially a sequence in $A \cup B$:

$$ \begin{array}{r|cccccccc} \text{Spoiler} & c_0 & & c_2 & & c_4 & & \cdots & & c_{2k-2} \\ \hline \text{Duplicator} & & c_1 & & c_3 & & c_5 & & \cdots & & c_{2k-1} \end{array} $$ where $c_{2i} \in A$ iff $c_{2i+1} \in B$. What Duplicator wants to do is preserve the play encapsulating a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$. Namely, for each $i < k$ we define $$ a_i = \begin{cases} c_{2i}, &\text{if }c_{2i} \in A \\ c_{2i+1}, &\text{otherwise} \end{cases} \qquad b_i = \begin{cases} c_{2i+1}, &\text{if }c_{2i+1} \in B \\ c_{2i}, &\text{otherwise} \end{cases} \quad $$ and consider the mapping $a_i \mapsto b_i$. If this is a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$ we require that the strategy tells Duplicator how to respond to any possible next move of Spoiler. In a bit more formality, for each $a \in A$ the strategy will return some $$\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , a ) \in B$$ such that extending the partial isomorphism above by the $a \mapsto \sigma ( c_0 , c_1 , \ldots , c_{2k-1} , a )$ is also a partial isomorphism, and (analogously) for any $b \in B$ the strategy returns some $$\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , b ) \in A$$ such that extending the partial isomorphism above by the $\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , b ) \mapsto b$ is also a partial isomorphism.


A proper formal definition of a winning strategy for Duplicator will then talk about a function $\sigma$ with domain the set of all odd-length sequences (of length $<2n$) in $A \cup B$ (or perhaps $(A \times \{ A \} ) \cup ( B \times \{ B \} )$ to ensure a disjoint union) such that for any $( c_0 , c_2 , \ldots , c_{2k-1} , c_{2k} )$ in the domain we have that $$\sigma ( c_0 , c_2 , \ldots , c_{2k-1} , c_{2k} ) \in A \quad \Leftrightarrow \quad c_{2k} \in B$$ and if the initial segment of this sequence of length $2k$ encapsulates a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$, as described above, then the extension of this function in the manner described above is also a partial isomorphism.

$\endgroup$
  • $\begingroup$ A very satisfactory and thorough answer indeed. The last section in particular explained very well what I was looking for. $\endgroup$ – Ezra Mar 27 '14 at 14:28
  • $\begingroup$ @Ezra: I hope this helped. A precise formulation of the definition is rather ugly, but the idea is pretty straightforward, I think. $\endgroup$ – user642796 Mar 27 '14 at 18:06
  • $\begingroup$ Thank you, it really helped. You clarified some minor things I wasn't able to condense in a rather concise exposition. $\endgroup$ – Ezra Mar 29 '14 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.