5
$\begingroup$

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

$\endgroup$
3
  • $\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
    Commented Nov 27, 2013 at 16:59
  • 5
    $\begingroup$ It happens for finite structures :) $\endgroup$ Commented Nov 27, 2013 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$ Commented Nov 27, 2013 at 23:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented Nov 27, 2013 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$ Commented Nov 27, 2013 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$ Commented Jul 19, 2014 at 1:33

You must log in to answer this question.

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