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$"?

  • $\begingroup$ This happens if and only if whenever $\operatorname{Th}(M)=\{\varphi\mid M\models\varphi\}$ is a $\kappa$-categorical theory, where $|M|=\kappa$. $\endgroup$ – Asaf Karagila Nov 27 '13 at 16:59
  • 4
    $\begingroup$ It happens for finite structures :) $\endgroup$ – Benjamin Steinberg Nov 27 '13 at 17:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Joseph Van Name Nov 27 '13 at 23:00

First, you should note that the signature is determined by the structures and any two structures that are elementarily equivalent or isomorphic have to have the same signature.

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.

| cite | improve this answer | |
  • $\begingroup$ 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$). $\endgroup$ – Emil Jeřábek Nov 27 '13 at 19:25
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Nov 27 '13 at 23:02
  • $\begingroup$ "Fixing the language is even worse as, for every signature, there are non-categorical theories in it." Well, except for the empty signature! (assuming "categorical" means "categorical in every cardinality") $\endgroup$ – Alex Kruckman Jul 19 '14 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.