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?

  • $\begingroup$ Consider any pair of countable, elementarily equivalent, non-isomorphic structures. $\endgroup$ Mar 25 at 18:49
  • $\begingroup$ @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. $\endgroup$ Mar 25 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 25 at 20:56

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .