3
$\begingroup$

Let us consider $L$ a first order language with no function symbols, and $\mathfrak{A,B}$ two $L$-structures.

We consider this variant of the Ehrenfeucht-Fraïssé game : player I (Spoiler) picks at each step an element of $A$ or $B$ (the underlying sets of the given structure), and when it's his turn, player II (Duplicator) does the same.

We add the following rules, that can be modelled by a tree : If I picks an element of $A$ at his turn, then II must pick an element of $B$ and similarly if I picks an element of $B$, II must pick an element of $A$.

Now II wins if after each of his turns, there is an isomorphism between the induced structures of the elements chosen from $A$ and those chosen from $B$.

Notice that thus condition can be expressed as "the sequence obtained belongs to the body of the tree $T$" where $T$ is a subtree of the tree representing the rules, and thus this game is a Gale-Stewart game with rules where the payoff set is closed, and therefore by a theorem of Gale and Stewart, it is determined (assuming the axiom of choice).

One can see that if Duplicator has a winning strategy in all Ehrenfeucht-Fraïssé games $G_n(\mathfrak{A,B})$ then he has one in this variant, and conversely. In such a case, it is known that $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent.

Moreover, if the set of relation symbols is finite, and if $\mathfrak{A,B}$ are elementarily equivalent, then Duplicator has a winning strategy in all games $G_n(\mathfrak{A,B})$ and therefore he has one in the variant.

Therefore we have : if the set of relation symbols is finite, then Duplicator wins (in the variant) if and only if $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent, and therefore (the game being determined) Spoiler wins if and only if they are not.

Now my questions are :

Q1: Is this variant interesting beyond simply "It's only one game, as opposed to an infinity of games" ? If yes, has it been studied before ? Does the Gale-Stewart theorem (and other theorems concerning Gale-Stewart games) bring any new information to Ehrenfeucht-Fraïssé games ?

Q2 : What happens when there's an infinite set of relation symbols ?

EDIT : If it wasn't clear, in my variant, the isomorphisms don't have to be extensions of each other, they can change at each step. However I now realize that I went too fast with this sentence "and conversely" (when I mentioned the strategies for $G_n(\mathfrak{A,B})$, and it may actually be false. It would be true if Duplicator played the same way on the first $n$ rounds of $G_n(\mathfrak{A,B})$ and $G_m(\mathfrak{A,B})$ for $n<m$ (given a play by Spoiler) but maybe the strategy of Duplicator can change according to $n$

$\endgroup$
3
$\begingroup$

Let's call your game $G_\omega(\mathfrak{A},\mathfrak{B})$. It's clear that a winning strategy for Duplicator in $G_\omega(\mathfrak{A},\mathfrak{B})$ provides a winning strategy in $G_n(\mathfrak{A},\mathfrak{B})$ for all $n$. But the converse is not true - essentially, this is because the winning strategies for the games of length $n$ for various $n$ might not agree, and therefore might not cohere to a strategy in the infinite game.

For an explicit counterexample, let $\mathfrak{A} = (\mathbb{N},\leq)$ and let $\mathfrak{B} = (\mathbb{N}+\mathbb{Z},\leq)$. The theory of a discrete linear order with a least element is complete, so these structures are elementarily equivalent. But Sploiler has a winning strategy in $G_\omega(\mathfrak{A},\mathfrak{B})$: First, Spoiler chooses any element in the copy of $\mathbb{Z}$ in $\mathfrak{B}$. Duplicator is forced to respond with an element $k$ in $\mathfrak{A}$. Then, in the next $k$ turns, Spoiler chooses the elements $0,1,\dots,k-1$ in the copy of $\mathbb{N}$ in $\mathfrak{B}$, and Duplicator is forced to respond with $0,1,\dots,k-1$ in $\mathfrak{A}$. When Spoiler chooses $k$ in the next turn, Duplicator has no way to extend the partial isomorphism.

In fact, Duplicator has a winning strategy in $G_\omega(\mathfrak{A},\mathfrak{B})$ if and only if $\mathfrak{A}\equiv_{\infty,\omega}\mathfrak{B}$, meaning that $\mathfrak{A}$ and $\mathfrak{B}$ agree on every sentence of the infinitary logic $\mathcal{L}_{\infty,\omega}$. Needless to say, this is a much stronger condition than elementary equivalence. This is essentially Karp's Theorem. See Hodges Model Theory Section 3.5 (actually, the whole of Chapter 3 on EF games is quite informative).

$\endgroup$
  • $\begingroup$ I see your point but I don't see how your counterexample works : in $G_\omega(\mathfrak{A,B})$, the isomorphisms don't have to extend each other (not in the way I described it at least). And here, no matter what the chosen elements are, as long as they are as numerous, there will in fact be an isomorphism (formally : for any finite subsets $S,T$ of $\mathbb{N, N}+\mathbb{Z}$ respectively, there is an isomorphism between $S$ and $T$ if and only if they have the same cardinal). $\endgroup$ – Max May 13 '17 at 14:09
  • $\begingroup$ And so in your example, Duplicator has a winning strategy (just choose elements accordingly so that the cardinals stay equal). The fact that here equality of cardinals implies isomorphism comes from the fact that any finite linear order is a well ordering, and there is only one finite ordinal per finite cardinal $\endgroup$ – Max May 13 '17 at 14:53
  • $\begingroup$ Oh! I didn't read your definition of the win condition for Duplicator carefully enough. But then this is not the EF game, and it has nothing to do with elementary equivalence. For example, Duplicator has a winning strategy in the game $G_n(\mathbb{Q},\mathbb{N})$ for all $n$... $\endgroup$ – Alex Kruckman May 13 '17 at 15:00
  • $\begingroup$ In the EF game, if $a_i$ is the element of $\mathfrak{A}$ chosen in round $i$ and $b_i$ is the element of $\mathfrak{B}$ chosen in round $i$, the Duplicator's goal is to ensure that the map $a_i\mapsto b_i$ is a partial isomorphism, not just that there exists and isomorphism. $\endgroup$ – Alex Kruckman May 13 '17 at 15:02
  • $\begingroup$ Oh right ! My bad, I had misread the definition of the EF game then . You're right, it has nothing to do with elementary equivalence. But now I'm curious, has my variant (which is actually a different game, not just a variant) any interest at all ? What are the pairs of structures such that Duplicator wins ? (And for any pair, one of the two players has to win) $\endgroup$ – Max May 13 '17 at 15:09

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.