0
$\begingroup$

Let $\Sigma$ be a set of formulas. There's a finite set $\Lambda \subseteq \Sigma$.

I'm asked to prove or disprove that $\Sigma$ has a model if and only if $\Lambda$ has a model.

It seems to me it's just true using compactness, but that sounds too easy.

$\endgroup$
  • 1
    $\begingroup$ It is certainly true that (in first-order logic) $\Sigma$ has a model iff every finite subset of $\Sigma$ has a model. And naturally it is perfectly possible for some finite subset of $\Sigma$ to have a model while $\Sigma$ doesn't. One needs a more precise statement of the problem. $\endgroup$ – André Nicolas Jun 23 '12 at 16:13
2
$\begingroup$

It is not enough that there is a finite $\Lambda$ that has a model. In order for compactness to be applicable (or for the claim to be true at all), you need to assume that for every possible finite $\Lambda$ it has a model.

On the other hand, if you rewrite the assumption in that way, what you're being asked to prove is just compactness theorem. And then you shouldn't be using that theorem itself in the proof.

On the other hand, it looks like the exercise also allows for the solution to be a disproof -- so if you're sure you have reproduced the claim correctly, you should be looking for a counterexample instead. (If so, hint: The empty set is finite, and the empty theory has a model).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Assume $\Lambda$ has a model. Let $\varphi$ be a sentence in $\Lambda$ and let $\Sigma = \Lambda \cup \left\{ \neg\varphi \right\}$. Clearly $\Sigma$ is inconsistent and thus is unsatisfiable (by the soundness theorem).

So as Henning says, it's not enough for some finite subset of your theory to have a model for compactness to hold: all finite subsets must be satisfiable.

| cite | improve this answer | |
$\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.