# Local isomorphism question in logics

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?

• 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. – Alex Kruckman Aug 8 '15 at 0:04
• Yeah thanks, apparently my book gives the wrong definition. – 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.