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
  • 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$ Jun 23, 2012 at 16:13

2 Answers 2

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

$\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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .