Logic question proving something about compactness

109 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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

0
On

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.