# From elementary equivalence to isomorphism

A few years ago, when I took the basic course in Logic, I was very surprised to discover that given a signature $\sigma$ and two structures $M$ and $N$ of $\sigma$ which are elementarily equivalent (that is, they satisfy the same first-order $\sigma$-sentences), they are not necessarily isomorphic, even if they are of the same cardinality.

My question is, are there some "reasonable" conditions that one may pose on either the signature $\sigma$ or the structures $M$ and $N$ that guarantee the implication: "If $M$ and $N$ are elementarily equivalent, then $M \cong N$"?

• This happens if and only if whenever $\operatorname{Th}(M)=\{\varphi\mid M\models\varphi\}$ is a $\kappa$-categorical theory, where $|M|=\kappa$. – Asaf Karagila Nov 27 '13 at 16:59
• It happens for finite structures :) – Benjamin Steinberg Nov 27 '13 at 17:19
• Saturated structures of the same cardinality are isomorphic. More generally, special structures of the same cardinality are isomorphic. Also, any pair of homogeneous structures of the same cardinality that realize the same $n$-types are isomorphic. Here a structure $A$ is said to be homogeneous if whenever $\lambda<|A|$, and the structures $(A,(a_{\alpha})_{\alpha<\lambda}),(A,(b_{\alpha})_{\alpha<\lambda})$ are elementarily equivalent, then for each $a\in A$ there is a $b\in B$ where $(A,(a_{\alpha})_{\alpha<\lambda},a),(A,(b_{\alpha})_{\alpha<\lambda},b)$ are elementarily equivalent. – Joseph Van Name Nov 27 '13 at 23:00

For your question, I don't think much can be done in the realm of first order logic. Asaf's answer is correct that you need $Th(M)$ to be categorical for $M \equiv N$ to imply $M \cong N$. Fixing the language is even worse as, for every signature, there are non-categorical theories in it.
Things get a little more interesting when you move to infinitary languages. $L_{\omega_1, \omega}$ is the logic formed by allowing countably many conjunctions and disjunctions (as opposed to finitely many in first order), while still requiring that there are only finitely many free variables. In this logic, every countable structure has a Scott sentence which characterizes its countable isomorphism type. That is: if $M$ is a countable structure, then there is a sentence $\phi_M \in L_{\omega_1, \omega}$ (of the language of $M$) such that if $N$ is a countable structure so $N \vDash \phi_M$, then $M \cong N$.
This doesn't generalize as nicely to larger infinitary languages as one might like, but I believe that if $cf(\lambda)=\omega$ and $M$ is a $\lambda$ sized model, then there is a $L_{\lambda^+, \omega}$ sentence with the same property.
• You’d need something like $L_{\lambda^+,\lambda^+}$ for uncountable structures, finite quantifiers won’t do. For example, every two dense linear orders are $L_{\infty,\omega}$-equivalent (that is, $L_{\lambda,\omega}$-equivalent for every $\lambda$). – Emil Jeřábek Nov 27 '13 at 19:25
• Aha, $L_{\lambda^+,\lambda^+}$ always works (for rather trivial reasons), but if $\mathrm{cf}(\lambda)=\omega$, there is also a $L_{\infty,\lambda}$ such sentence (more precisely, $L_{(\lambda^{<\lambda})^+,\lambda}$). This might be what you had in mind. – Emil Jeřábek Nov 27 '13 at 23:02