1
$\begingroup$

Do the following statements mean the same thing? If not, what's the difference? Assume that $T_0, T_1$ are first-order languages and that $T_1$ is a model-theoretic extension of $T_0$.

Every model for $T_0$ can be expanded into a model for $T_1$.

vs.

For any model $M$ of $T_0$ there is a model $N$ of $T_1$ such that $M \equiv N\upharpoonright L_0$.

Notes:

  • "$N\upharpoonright L_0$" means the reduct of $N$ to the language of $M$.

  • "$\equiv$" means elementary equivalence, not isomorphism, so that, for instance, $(\mathbb{N},<)\equiv(\mathbb{N}+\mathbb{Z},<)$, as can be proved e.g. via quantifier elimination, but, clearly, $(\mathbb{N},<)\not\cong(\mathbb{N}+\mathbb{Z},<)$.


My confusion may arise from an inadequate understanding of the meanings of one or more of the terms model-theoretic extension, expansion, reduct, elementary equivalence and isomorphism.

Please assume in your answer minimal knowledge of logic on my part.

$\endgroup$
  • $\begingroup$ It seems that you need a more detailed answer than I am able to provide with my superficial understanding of logic. I have deleted my answer in the hope that some more knowledgeable person will help you. $\endgroup$ – bof Feb 8 '17 at 9:42
  • $\begingroup$ @bof: I'm sorry that you deleted your answer. I feel I was on my way to understanding. Thanks anyway. $\endgroup$ – Evan Aad Feb 8 '17 at 9:45
  • $\begingroup$ @EvanAad Does my answer help? $\endgroup$ – Noah Schweber Feb 11 '17 at 3:41
  • $\begingroup$ @NoahSchweber: Helps a lot. Thank you! $\endgroup$ – Evan Aad Feb 11 '17 at 15:39
2
$\begingroup$

This was explained in my answer to part 3b of your previous question: they are not equivalent (although the first trivially implies the second). Isomorphism (= existence of a structure-preserving bijection) is strictly stronger than elementary equivalence (= satisfy the same first-order sentences), and this drives the separation.

In more detail:

Let $L_0$ be the language of arithmetic, and $L_1$ be that language expanded with a new constant symbol $c$. Let $T_0$ be the theory of $(\mathbb{N}; +, \times, 0, 1)$, and $T_1$ be that theory together with the sentences $$\mbox{"$c>1+1+1+...+1$"}$$ ($n$ "1"s) for each $n\in\mathbb{N}$. Then:

  • Clearly $T_1$ is a model-theoretic (in fact, proof-theoretic) extension of $T_0$.

  • For any model $N$ of $T_1$ and any model $M$ of $T_0$, $M\equiv N$. (This is because $T_0$ is a complete theory in the language $L_0$.)

  • But the model $(\mathbb{N}; +, \times, 0, 1)$ has no expansion to a model of $T_1$: wherever we "put" $c$, we wind up violating one of the axioms of $T_1$.

(Note, to allay possible worries, that $T_1$ does indeed have models - this can be proved using the compactness theorem, and is a good exercise.)


You asked in a comment to bof's answer how to tell that two structures are elementarily equivalent. There are several ways to do this:

  • If (the deductive closure of) $S$ is a complete $L$-theory and $A, B\models S$ are $L$-structures, then $A\equiv B$ by definition: if $A\models \varphi$, then we can't have $\neg\varphi\in S$, so since $S$ is complete we have $\varphi\in S$, but then $B\models\varphi$ since $B\models S$.

  • We can use Ehrenfeucht-Fraisse games to show that two structures are elementarily equivalent.

  • Los' Theorem says that we can show that two structures are elementarily equivalent if they have isomorphic ultrapowers (the converse is the Keisler-Shelah isomorphism theorem).

  • Quantifier elimination, model completeness, or similar can be used to give a complete description of the theory of a structure, and so facilitate proofs of elementary equivalence.

  • And sometimes you can come up with really silly model chain constructions too.

And there are lots of other methods.

$\endgroup$
  • $\begingroup$ Thanks. How can it be shown that $T_0$ is a complete theory in $L_0$? $\endgroup$ – Evan Aad Feb 11 '17 at 6:39
  • 1
    $\begingroup$ @EvanAad Any theory of the form "$Th(M)$" for an $L$-structure $M$ is a complete theory in $L$ - for each $\varphi$ in $L$, either $M\models \varphi$ (in which case $\varphi\in Th(M)$) or $M\models\neg\varphi$ (in which case $\neg\varphi\in Th(M)$). And here, $T_0=Th(\mathbb{N}; +, \times, 0, 1)$, so is a complete $L_0$-theory. $\endgroup$ – Noah Schweber Feb 11 '17 at 15:13

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.