Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  André Nicolas Jun 23 '12 at 16:13

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.