If two sentences have the same enumerable models, then they are logically equivalent.

Question

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).

Answer 1

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.

Answer 2

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.