# Criterion of elementary equivalence

I know a criterion of an elementary equivalence.

Let $$\frak A$$ and $$\frak B$$ be systems of a signature $$\Sigma.$$ For $$\frak A$$ and $$\frak B$$ to be elementary equivalent it is necessary and sufficient that for any natural $$n$$ and any finite signature $$\Sigma_1\subseteq\Sigma$$ there be nonempty sets $$F_1(\Sigma_1,n),\dots,F_n(\Sigma_1,n)$$ of finite partial isomorphisms $$\frak A|_{\Sigma_1}\to\frak B|_{\Sigma_1}$$ possessing the following property: if $$f\in F_i(\Sigma_1,n),1\leqslant i then for any $$a\in A$$ and $$b\in B$$ there are $$g_1,g_2\in F_{i+1}(\Sigma_1,n)$$ for which $$a\in\textrm{dom }g_1,\:b\in\textrm{rang }g_2,$$ and $$f\subseteq g_1\cap g_2.$$

Fixing finite $$\Sigma_1,$$ consider $$F_i(\Sigma_1,n)$$ for different $$n.$$ Evidently, for $$i\leqslant m we may suppose $$F_i(\Sigma_1,m)=F_i(\Sigma_1,n).$$ My questions are: Do we really need the last index? Cannot we replace finite sequences of sets $$F_i(\Sigma_1,n)$$ with an infinite one of $$F_i(\Sigma_1)$$? And if we can why don't we do that?

• Consider any pair of countable, elementarily equivalent, non-isomorphic structures. Mar 25 at 18:49
• @NoahSchweber, I've already tried but my pair ($\frak A$ is an infinite set of constants and $\frak{A\subset B}$) didn't get a counterexample. Mar 25 at 20:24
• Sorry, I should have specified "in a finite language." Consider the linear orders $\mathbb{Z}$ and $\mathbb{Z}+\mathbb{Z}$. The point is that the infinite system version, in this case, implies isomorphism if the structures are countable. Mar 25 at 20:56

Consider two countable elementarily equivalent non-isomorphic structures in a finite language, $$\mathfrak{A}$$ and $$\mathfrak{B}$$. The existence of an "infinite-length" system of partial isomorphisms between them would imply their isomorphism - this is essentially the content of the back-and-forth method. On the other hand, such pairs do indeed exist. The standard example in my opinion is a pair of linear orders of ordertypes $$\zeta$$ and $$\zeta+\zeta$$ respectively. (Here $$\zeta$$ is the ordertype of the integers; for a concrete example, take $$\mathfrak{A}=\mathbb{Z}$$ and $$\mathfrak{B}=\{-(2^z):z\in\mathbb{Z}\}\cup\{2^z:z\in\mathbb{Z}\}$$, each ordered as usual.) Essentially, such a pair of structures is "barely elementarily equivalent."
That said, the infinite-length system idea does correspond to equivalence with respect to a natural logic, it's just that the logic in question is stronger: $$\mathcal{L}_{\infty,\omega}$$ instead of finitary first-order logic $$\mathcal{L}_{\omega,\omega}$$. (A third characterization is "potentially isomorphic," that is, isomorphic in some forcing extension of the universe; this is extremely powerful but rather technical, so I'll leave it aside for now.)
Interestingly, the infinitary logic $$\mathcal{L}_{\omega_1,\omega}$$ - which is in many other ways much nicer than $$\mathcal{L}_{\infty,\omega}$$, and in particular is nice enough to have a decent model theory even if it's rather worse than first-order logic (cf. "Barwise compactness") - is rather difficult to characterize via systems of partial isomorphisms or EF-game analogues. This is not to say that no such characterization exists, and in particular Vaananen/Wang gave such a game-theoretic characterization, but any such characterization is substantially messier than the usual characterization of first-order equivalence. One precise statement along these lines was proved by Schlutzenberg at MO.