The definition of a local isomorphism between structures:

a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ (a_1,b_1),...,(a_n,b_n)\} \subset A \times B $$ such that the simple extensions $(\mathcal{A},a_1,...,a_n)$ and $(\mathcal{B},b_1,...,b_n)$ are elementary equivalent.

In a Ehrenfeucht-Fraïssé game the goal of the duplicator is to make a local isomorphism. Between $\mathcal{A}$ and $\mathcal{B}$. A theorem of these games is that $$\mathcal{A} \equiv^n \mathcal{B} \Leftrightarrow \mathcal{A} \sim_n \mathcal{B} $$ We have if $\mathcal{A} \sim_n \mathcal{B}$, then $(\mathcal{A},a_1,...,a_n)$ and $(\mathcal{B},b_1,...,b_n)$ are elementary equivalent. But doesn't this mean that also $\mathcal{A}$ and $\mathcal{B}$ are equivalent and so the previous theorem doesn't say anything in the $\Leftarrow$ direction?

  • 3
    $\begingroup$ Where did you find this definition of local isomorphism? The usual definition is that $(\mathcal{A},a_1,\dots,a_n)$ and $(\mathcal{B},b_1,\dots,b_n)$ satisfy the same quantifier-free sentences. $\endgroup$ – Alex Kruckman Aug 8 '15 at 0:04
  • $\begingroup$ Yeah thanks, apparently my book gives the wrong definition. $\endgroup$ – abcdef Aug 23 '15 at 9:16

Long Comment

It seems to me that the symbolism for local isomorphism is not so "stable"; thus, I'm not sure about the equivalences...

I'll refer to :

We have :

$\mathcal{A} \equiv \mathcal{B}$, i.e. elementary equivalence, when the two structures satisfy the same FO sentences,

and :

$\mathcal{A} \equiv_n \mathcal{B}$, when they satisfy the same FO sentences of quantifier rank $\le n$.

Next we have [page 69] :

$\mathcal{A} \sim^n_p \mathcal{B}$ if there is a back-and-forth sequence of length $n$ for $\mathcal{A}$ and $\mathcal{B}$.

Some results :

  • page 70 :

Proposition 5.27 The following are equivalent:

  1. $\mathcal{A} \sim^n_p \mathcal{B}$

  2. II [Duplicator] has a winning strategy in $\text{EF}_n(\mathcal{A},\mathcal{B})$.

  • page 81 :

Proposition 6.4 Suppose $L$ is an arbitrary vocabulary. Suppose $\mathcal{A}$ and $\mathcal{B}$ are $L$-structures and $n \in \mathbb N$. Consider the conditions:

(i) $\mathcal{A} \equiv_n \mathcal{B}$

(ii) $\mathcal{A}\upharpoonright_{L'} \sim^n_p \mathcal{B}\upharpoonright_{L'}$ , for all finite $L' \subseteq L$.

We have always (ii) $\Rightarrow$ (i) and if $L$ has no function symbols, then (ii) $\Leftrightarrow$ (i).

Thus, "cooking all together", It seems to me that :

if $\mathcal{A} \sim^n_p \mathcal{B}$, for all $n$, then $\mathcal{A} \equiv \mathcal{B}$, i.e. $\mathcal{A}$ and $\mathcal{B}$ are elementary equivalent.


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.