I am attempting to show that if two sentences have the same enumerable models, then they are logically equivalent. I am told that I need to apply the Löwenheim-Skolem theorem (if a set of sentences has a model, then it has an enumerable model) in some way. Is the following the correct line of thought?

Let $\Gamma$ and $\Omega$ be sets of sentences that have the same enumerable model, $\mathcal{M}$. Thus $\mathcal{M}\models\Gamma$ and $\mathcal{M}\models\Omega$. Then (am I missing a step here?) $\mathcal{M}\models\Gamma\cup\Omega$. By the Löwenheim-Skolem theorem, because we have shown there exists a model that makes true the set of sentences $\Gamma\cup\Omega$, we are guaranteed the existence of an enumerable model that makes true $\Gamma\cup\Omega$.

At this point I'm grasping at straws. I am not totally sure how to prove that they are equivalent under every interpretation (or how exactly the L-S theorem comes into play).

  • 3
    $\begingroup$ When you say "they have the same enumerable model" do you mean that there is a unique enumerable model which satisfies both, or just that "All enumerable models which satisfy one of the sentences satisfy both"? As it stands right now, you might say that there is just one enumerable model which satisfy both sentences, in which case the statement is false. $\endgroup$ – Ove Ahlman Feb 29 '16 at 8:50
  • $\begingroup$ @OveAhlman This is a typo, my mistake. I am attempting to prove if two sentences have the same enumerable model(S!), then they are logically equivalent. I've edited my post. $\endgroup$ – faux Feb 29 '16 at 9:01
  • $\begingroup$ @faux maybe you should correct also the body of the post $\endgroup$ – Marco Disce Mar 2 '16 at 12:15

So in order to prove that $\Gamma$ and $\Omega$ are logically equivalent we need to show that each model which satisfy one of the sets also satisfies the other.

Hint: Assume that $\mathcal{N}_1\models \Gamma$, if we now can prove that $\mathcal{N_1}\models\Omega$ then we are done. Now use the Löwenheim-Skolem theorem to get a relation to countable models, and use what you know about the countable models to get the desired conclusion.

Solution: Assume that $\mathcal{N}\models \Gamma$. By the Löwenheim-Skolem theorem, there is a countable model $\mathcal{M}$ such that $\mathcal{M}\equiv \mathcal{N}$ i.e. they satisfy the same sentences. However as $\mathcal{N}\models\Gamma$ is it follows that $\mathcal{M}\models\Gamma$, and since $\mathcal{M}$ is countable it follows from the assumption that $\mathcal{M}\models \Omega$. Again using $\mathcal{M}\equiv \mathcal{N}$ it now follows that $\mathcal{N}\models \Omega$.

Thus we have shown that if any structure $\mathcal{N}\models\Gamma$ then $\mathcal{N}\models \Omega$. By symmetry (or by doing the same thing again) we may show that if $\mathcal{N}\models \Omega$ then $\mathcal{N}\models \Gamma$. Thus we can draw the conclusion that $\Gamma$ and $\Omega$ are logically equivalent.

  • $\begingroup$ My attempt: Suppose $\mathcal{N}_1\models\Gamma$ By L-S, because $\Gamma$ has a model it has a countable model up to some arbitrary size $n$. But then the two sentences have exactly the same number of models, all of which make both $\Gamma$ and $\Omega$ true. (?) I feel like I'm definitely missing a major chunk of intuition about the next step which links the proof together. $\endgroup$ – faux Feb 29 '16 at 10:00
  • $\begingroup$ @faux Added a complete solution. $\endgroup$ – Ove Ahlman Feb 29 '16 at 10:13
  • $\begingroup$ Thank you for the explanation. Do you think you might be able to elaborate on why L-S is a requirement for this proof? This may be a question that comes from a lack of deeper understanding, but why do we only initially assume $\mathcal{N}\models\Gamma$ and not that $\mathcal{N}\models\Gamma$ and $\mathcal{N}\models\Omega$ at the beginning of the proof? Is this unnecessary? $\endgroup$ – faux Feb 29 '16 at 10:20
  • $\begingroup$ We want to show that any model which satisfy $\Gamma$ also satisfy $\Omega$. Thus if we assume both that $\mathcal{N}\models \Gamma$ and $\mathcal{N}\models\Omega$ we have not necessarily taken an arbitrary model (as there might be models which satisfy $\Gamma$ but not $\Omega$). Arbitrary models are not necessarily enumerable, and thus the assumption is not usefull for $\mathcal{N}$, but we need to get to the countable case in order to use the assumption, and this is wher the L-S theorem is usefull. $\endgroup$ – Ove Ahlman Feb 29 '16 at 10:49

L-S theorem sometimes is simply stated as: "If a set of sentences has a model, then it has an enumerable model". It's not clear why "By the Löwenheim-Skolem theorem, there is a countable model $\mathcal{M}$ such that $\mathcal{M} \equiv \mathcal{N}$" in Ove Ahlman's answer must be true with this version of theorem.

We can make this more explicit by considering $\{\alpha, \neg \beta\}$ (without loss of generality), which has a model iff they are not equivalent. If the model is not enumerable, then by L-S theorem, the set has another model that is enumerable. Then use the fact that $\alpha$ and $\beta$ have the same enumerable models to show that it must be the case that $\alpha$ and $\beta$ are equivalent.


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.