Criterion of elementary equivalence

Question

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<n,$ 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<n$ 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?

Answer 1

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.