4
$\begingroup$

Do there exist elementarily equivalent models $\mathcal{M}, \mathcal{N}$ of the cardinality $\kappa=\omega$ such that neither can be elementarily embedded into the other?

If the models were not required to be of the cardinality $\omega$, then one could consider models of the theory of 3 equivalence classes where each class has to be infinite: $\mathcal{M}$ would have its domain $M = M_1 \sqcup M_2 \sqcup M_3$ and $dom(\mathcal{N})=N_1 \sqcup N_2 \sqcup N_3$ where $M_1, M_2, M_3, N_1, N_2, N_3$ are equivalence classes of their respective cardinalities $\omega_1, \omega_1, \omega_2, \omega_0, \omega_2, \omega_2$. Because of the incompatible cardinalities, there is no embedding from $\mathcal{M}$ to $\mathcal{N}$ or vice versa. Therefore this is the answer to my question for the cardinality $\kappa \gt \omega_1$. For $\kappa=\omega_1$ one could use a similar trick with equivalence classes over two relations and the incompatibility of the cardinalities $\omega_0, \omega_1$. But what about the cardinality $\kappa=\omega_0$?

$\endgroup$
  • 1
    $\begingroup$ You probably wanna change "elementary substructure" to "can be elementarily embedded into" before the pedantic folks come and point out that you can easily arrange two copies of $\Bbb N$ which are not subsets of one another and therefore neither is a substructure of the other. $\endgroup$ – Asaf Karagila Jan 18 '15 at 20:50
2
$\begingroup$

The language contains a relation symbol $<$ and the constants $a_i,b_i$ for $i\in\omega$. Consider two models, both with domain $\mathbb Q$ and the natural interpretation of $<$. In both models $b_{i+1}<b_i<a_i<a_{i+1}$. In the first model $a_i\to+\infty$ and $b_i\to-1$ in the second model $a_i\to+1$ and $b_i\to-\infty$.

By quantifier elimination the two models are elementary equivalent. Clearly, they do not embed into each other.

$\endgroup$
  • $\begingroup$ I do not understand how you can apply back-and-forth property: let $h:\mathcal{M} \rightharpoonup \mathcal{N}$ be a finite partial isomorphism between your first and the second model. Then there exists $a_N \in L$ such that $a_N^{\mathcal{M}}>1$ and $a_N^{\mathcal{N}}<1$ so you cannot extend $h$ by $a_N^{\mathcal{M}}$ as any such extended bijection would not preserve the interpretation of the constant $a_N$ and hence would not be an isomorphism. $\endgroup$ – Dávid Natingga Jan 23 '15 at 7:32
  • 1
    $\begingroup$ @david Indeed to mention back-and-forth is misleading (I erased it). Reason as follows: ${\mathbb Q},<$ has quantifier elimination and this is preserved if after naming some elements. So, naming a different set of elements, if they are order-isomorphic, results in elementary equivalent models. $\endgroup$ – Primo Petri Jan 23 '15 at 9:12
1
$\begingroup$

Hint: consider models of the theory of linear orders where every element has a successor and a predecessor and their quotient by the (undefinable) equivalence relation $x\sim y$ iff there are finitely many elements betwen $x$ and $y$.

To show that the theory is complete, I think that if add symbols for (definable) successor and predecessor functions, it should have quantifier elimination, and it easily follows that it is complete; alternatively, you can use Ehrenfeucht-Fraisse games to that end.

$\endgroup$

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.